WARNING! Access to this system is limited to authorised users only.
Unauthorised users may be subject to prosecution.
Unauthorised access to this system is a criminal offence under Australian law (Federal Crimes Act 1914 Part VIA)
It is a criminal offence to:
(1) Obtain access to data without authority. -Penalty 2 years imprisonment.
(2) Damage, delete, alter or insert data without authority. -Penalty 10 years imprisonment.
User activity is monitored and recorded. Anyone using this system expressly consents to such monitoring and recording.

To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.7% of users enabled 2FA.

inst_sel.rs 180 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#![allow(unused_variables)]
#![warn(unused_imports)]
#![warn(unreachable_code)]
#![warn(dead_code)]
use ast::ir::*;
use ast::ptr::*;
use ast::inst::*;
use ast::op;
use ast::op::*;
use ast::types;
use ast::types::*;
use vm::VM;
use runtime::mm;
use runtime::mm::objectmodel::OBJECT_HEADER_SIZE;

use runtime::ValueLocation;
use runtime::thread;
use runtime::entrypoints;
use runtime::entrypoints::RuntimeEntrypoint;

use compiler::CompilerPass;

use compiler::backend::PROLOGUE_BLOCK_NAME;
24
use compiler::backend::EPILOGUE_BLOCK_NAME;
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52

use compiler::backend::aarch64::*;
use compiler::machine_code::CompiledFunction;
use compiler::frame::Frame;

use std::collections::HashMap;
use std::any::Any;

const INLINE_FASTPATH : bool = false;

pub struct InstructionSelection {
    name: &'static str,
    backend: Box<CodeGenerator>,

    current_fv_id: MuID,
    current_callsite_id: usize,
    current_frame: Option<Frame>,
    current_block: Option<MuName>,
    current_func_start: Option<ValueLocation>,
    // key: block id, val: callsite that names the block as exception block
    current_exn_callsites: HashMap<MuID, Vec<ValueLocation>>,
    // key: block id, val: block location
    current_exn_blocks: HashMap<MuID, ValueLocation>,

    current_constants: HashMap<MuID, P<Value>>,
    current_constants_locs: HashMap<MuID, P<Value>>
}

53
// TODO: Move all functions that are in here that don't need access to 'self' (or only call functions that don't need access to self (even if called on self)) to Mod.rs
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
impl <'a> InstructionSelection {
    #[cfg(feature = "aot")]
    pub fn new() -> InstructionSelection {
        InstructionSelection {
            name: "Instruction Selection (x64)",
            backend: Box::new(ASMCodeGen::new()),

            current_fv_id: 0,
            current_callsite_id: 0,
            current_frame: None,
            current_block: None,
            current_func_start: None,
            // key: block id, val: callsite that names the block as exception block
            current_exn_callsites: HashMap::new(),
            current_exn_blocks: HashMap::new(),

            current_constants: HashMap::new(),
            current_constants_locs: HashMap::new()
        }
73

74
75
76
77
78
79
80
81
82
83
    }

    #[cfg(feature = "jit")]
    pub fn new() -> InstructionSelection {
        unimplemented!()
    }

    // in this pass, we assume that
    // * we do not need to backup/restore caller-saved registers
    // if any of these assumption breaks, we will need to re-emit the code
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
84
    fn instruction_select(&mut self, node: &'a TreeNode, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) {
85
86
87
88
89
        trace!("instsel on node#{} {}", node.id(), node);

        match node.v {
            TreeNode_::Instruction(ref inst) => {
                match inst.v {
90
                    // TODO: Optimise if cond is a flag from a binary operation?
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
                    Instruction_::Branch2 { cond, ref true_dest, ref false_dest, true_prob } => {
                        trace!("instsel on BRANCH2");
                        let (fallthrough_dest, branch_dest, branch_if_true) = {
                            if true_prob > 0.5f32 {
                                (true_dest, false_dest, false)
                            } else {
                                (false_dest, true_dest, true)
                            }
                        };

                        let ops = inst.ops.read().unwrap();

                        self.process_dest(&ops, fallthrough_dest, f_content, f_context, vm);
                        self.process_dest(&ops, branch_dest, f_content, f_context, vm);

                        let branch_target = f_content.get_block(branch_dest.target).name().unwrap();

                        let ref cond = ops[cond];

110
                        if self.match_cmp_res(cond) {
111
                            trace!("emit cmp_res-branch2");
112
113
114
115
                            let mut cmpop = self.emit_cmp_res(cond, f_content, f_context, vm);
                            if !branch_if_true {
                                cmpop = cmpop.invert();
                            }
116

117
                            let cond = get_condition_codes(cmpop);
118

119
120
121
122
123
124
                            if cmpop == op::CmpOp::FFALSE {
                                ; // Do nothing
                            } else if cmpop == op::CmpOp::FTRUE {
                                self.backend.emit_b(branch_target);
                            } else {
                                self.backend.emit_b_cond(cond[0], branch_target.clone());
125

126
127
128
129
                                if cond.len() == 2 {
                                    self.backend.emit_b_cond(cond[1], branch_target);
                                }
                            }
130
                        } else {
131
                            let cond_reg = self.emit_ireg(cond, f_content, f_context, vm);
132

133
134
135
136
                            if branch_if_true {
                                self.backend.emit_tbnz(&cond_reg, 0, branch_target.clone());
                            } else {
                                self.backend.emit_tbz(&cond_reg, 0, branch_target.clone());
137
                            }
138
                        };
139
140
141
142
143
144
145
146
147
148
149
150
                    },

                    Instruction_::Select { cond, true_val, false_val } => {
                        use ast::op::CmpOp::*;

                        trace!("instsel on SELECT");
                        let ops = inst.ops.read().unwrap();

                        let ref cond = ops[cond];
                        let ref true_val = ops[true_val];
                        let ref false_val = ops[false_val];

151
                        let tmp_res = self.get_result_value(node, 0);
152
153
154
155

                        // moving integers/pointers
                        // generate compare
                        let cmpop = if self.match_cmp_res(cond) {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
156
                            self.emit_cmp_res(cond, f_content, f_context, vm)
157
                        } else if self.match_ireg(cond) {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
158
                            let tmp_cond = self.emit_ireg(cond, f_content, f_context, vm);
159
160
161
162
163
164
                            self.backend.emit_cmp_imm(&tmp_cond, 0, false);
                            NE
                        } else {
                            panic!("expected ireg, found {}", cond)
                        };

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
165
166
                        let tmp_true = self.emit_reg(true_val, f_content, f_context, vm);
                        let tmp_false = self.emit_reg(false_val, f_content, f_context, vm);
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207

                        let cond = get_condition_codes(cmpop);

                        if self.match_ireg(true_val) {
                            if cmpop == FFALSE {
                                self.backend.emit_mov(&tmp_res, &tmp_false);
                            } else if cmpop == FTRUE {
                                self.backend.emit_mov(&tmp_res, &tmp_true);
                            } else {
                                self.backend.emit_csel(&tmp_res, &tmp_true, &tmp_false, cond[0]);

                                if cond.len() == 2 {
                                    self.backend.emit_csel(&tmp_res, &tmp_true, &tmp_res, cond[1]);
                                }
                            }
                        } else if self.match_fpreg(true_val) {
                            if cmpop == FFALSE {
                                self.backend.emit_fmov(&tmp_res, &tmp_false);
                            } else if cmpop == FTRUE {
                                self.backend.emit_fmov(&tmp_res, &tmp_true);
                            } else {
                                self.backend.emit_fcsel(&tmp_res, &tmp_true, &tmp_false, cond[0]);

                                if cond.len() == 2 {
                                    self.backend.emit_fcsel(&tmp_res, &tmp_true, &tmp_res, cond[1]);
                                }
                            }
                        } else {
                            // moving vectors, floatingpoints
                            unimplemented!()
                        }
                    },

                    Instruction_::CmpOp(op, op1, op2) => {
                        use ast::op::CmpOp::*;

                        trace!("instsel on CMPOP");
                        let ops = inst.ops.read().unwrap();
                        let ref op1 = ops[op1];
                        let ref op2 = ops[op2];

208
                        let tmp_res = self.get_result_value(node, 0);
209
210
211
212

                        debug_assert!(tmp_res.ty.get_int_length().is_some());
                        debug_assert!(tmp_res.ty.get_int_length().unwrap() == 1);

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
213
                        let cmpop = self.emit_cmp_res_op(op, &op1, &op2, f_content, f_context, vm);
214
215
216
                        let cond = get_condition_codes(cmpop);

                        if cmpop == FFALSE {
217
                            emit_mov_u64(self.backend.as_mut(), &tmp_res, 0);
218
                        } else if cmpop == FTRUE {
219
                            emit_mov_u64(self.backend.as_mut(), &tmp_res, 1);
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
                        } else {
                            self.backend.emit_cset(&tmp_res, cond[0]);

                            // Note: some compariosns can't be computed based on a single aarch64 flag
                            // insted they are computed as a condition OR NOT another condition.
                            if cond.len() == 2 {
                                self.backend.emit_csinc(&tmp_res, &tmp_res, &WZR, invert_condition_code(cond[1]));
                            }
                        }
                    }

                    Instruction_::Branch1(ref dest) => {
                        trace!("instsel on BRANCH1");
                        let ops = inst.ops.read().unwrap();

                        self.process_dest(&ops, dest, f_content, f_context, vm);

                        let target = f_content.get_block(dest.target).name().unwrap();

                        trace!("emit branch1");
                        // jmp
                        self.backend.emit_b(target);
                    },

                    Instruction_::Switch { cond, ref default, ref branches } => {
                        trace!("instsel on SWITCH");
                        let ops = inst.ops.read().unwrap();

                        let ref cond = ops[cond];

                        if self.match_ireg(cond) {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
251
252
                            let tmp_cond = self.emit_ireg(cond, f_content, f_context, vm);
                            self.emit_zext(&tmp_cond);
253
254
255
256
257
258
259
260
261
262
263
264

                            // emit each branch
                            for &(case_op_index, ref case_dest) in branches {
                                let ref case_op = ops[case_op_index];

                                // process dest
                                self.process_dest(&ops, case_dest, f_content, f_context, vm);

                                let target = f_content.get_block(case_dest.target).name().unwrap();

                                let mut imm_val = 0 as u64;
                                // Is one of the arguments a valid immediate?
265
266
                                let emit_imm = if match_node_int_imm(&case_op) {
                                    imm_val = node_imm_to_u64(&case_op);
267
268
269
270
271
272
273
274
275
276
                                    is_valid_arithmetic_imm(imm_val)
                                } else {
                                    false
                                };

                                if emit_imm {
                                    let imm_shift = imm_val > 4096;
                                    let imm_op2 = if imm_shift { imm_val >> 12 } else { imm_val };
                                    self.backend.emit_cmp_imm(&tmp_cond, imm_op2 as u16, imm_shift);
                                } else {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
277
278
                                    let tmp_case_op = self.emit_ireg(case_op, f_content, f_context, vm);
                                    self.emit_zext(&tmp_case_op);
279
280
281
282
283
                                    self.backend.emit_cmp(&tmp_cond, &tmp_case_op);
                                }

                                self.backend.emit_b_cond("EQ", target);

284
285
                                self.finish_block(&vec![]);
                                self.start_block(format!("{}_switch_not_met_case_{}", node.id(), case_op_index), &vec![]);
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
                            }

                            // emit default
                            self.process_dest(&ops, default, f_content, f_context, vm);

                            let default_target = f_content.get_block(default.target).name().unwrap();
                            self.backend.emit_b(default_target);
                        } else {
                            panic!("expecting cond in switch to be ireg: {}", cond);
                        }
                    }

                    Instruction_::ExprCall { ref data, is_abort } => {
                        trace!("instsel on EXPRCALL");

                        if is_abort {
                            unimplemented!()
                        }

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
305
                        self.emit_mu_call(
306
307
308
309
310
311
312
313
314
315
                            inst, // inst: &Instruction,
                            data, // calldata: &CallData,
                            None, // resumption: Option<&ResumptionData>,
                            node, // cur_node: &TreeNode, 
                            f_content, f_context, vm);
                    },

                    Instruction_::Call { ref data, ref resume } => {
                        trace!("instsel on CALL");

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
316
                        self.emit_mu_call(
317
318
319
320
321
322
323
324
325
326
327
328
329
330
                            inst,
                            data,
                            Some(resume),
                            node,
                            f_content, f_context, vm);
                    },

                    Instruction_::ExprCCall { ref data, is_abort } => {
                        trace!("instsel on EXPRCCALL");

                        if is_abort {
                            unimplemented!()
                        }

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
331
                        self.emit_c_call_ir(inst, data, None, node, f_content, f_context, vm);
332
333
334
335
336
                    }

                    Instruction_::CCall { ref data, ref resume } => {
                        trace!("instsel on CCALL");

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
337
                        self.emit_c_call_ir(inst, data, Some(resume), node, f_content, f_context, vm);
338
339
340
341
342
                    }

                    Instruction_::Return(_) => {
                        trace!("instsel on RETURN");

343
344
345
346
347
348
349
350
                        // prepare return regs
                        let ref ops = inst.ops.read().unwrap();
                        // TODO: Are ret_val_indices in the same order as the return types in the functions signature?
                        let ret_val_indices = match inst.v {
                            Instruction_::Return(ref vals) => vals,
                            _ => panic!("expected ret inst")
                        };

351
                        let ret_tys = ret_val_indices.iter().map(|i| node_type(&ops[*i])).collect();
352
353
                        let ret_type = self.combine_return_types(&ret_tys);
                        // Note: this shouldn't cause any overhead in the generated code if the register is never used
354
                        let temp_xr = make_temporary(f_context, ADDRESS_TYPE.clone(), vm);
355
356
357
358
359
360
361
362
363
364
365
366
367
368

                        if self.compute_return_allocation(&ret_type, &vm) > 0 {
                            // Load the saved value of XR into temp_xr
                            self.emit_load_base_offset(&temp_xr, &FP, -8, f_context, vm);
                        }

                        let n = ret_tys.len(); // number of return values
                        if n == 0 {
                            // Do nothing
                        } else if n == 1{
                            let ret_loc = self.compute_return_locations(&ret_type, &temp_xr, &vm);
                            self.emit_move_node_to_value(&ret_loc, &ops[ret_val_indices[0]], f_content, f_context, vm);
                        } else {
                            let ret_loc = self.compute_return_locations(&ret_type, &temp_xr, &vm);
369

370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
                            let mut i = 0;
                            for ret_index in ret_val_indices {
                                let ret_val = self.emit_node_value(&ops[*ret_index], f_content, f_context, vm);
                                let ref ty = ret_val.ty;
                                let offset = self.get_field_offset(&ret_type, i, &vm);

                                match ty.v {
                                    MuType_::Vector(_, _) | MuType_::Tagref64 => unimplemented!(),
                                    MuType_::Void => panic!("Unexpected void"),
                                    MuType_::Struct(_) | MuType_::Array(_, _) => unimplemented!(),

                                    // Integral, pointer of floating point type
                                    _ => self.insert_bytes(&ret_loc, &ret_val, offset as i64, f_context, vm),
                                }

                                i += 1;
                            }
                        }
388

389
                        self.backend.emit_b(EPILOGUE_BLOCK_NAME.to_string());
390
391
392
393
                    },

                    Instruction_::BinOp(op, op1, op2) => {
                        trace!("instsel on BINOP");
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
394
                        self.emit_binop(node, inst, op, BinOpStatus { flag_n: false, flag_z: false, flag_c: false, flag_v: false }, op1, op2, f_content, f_context, vm);
395
396
397
398
                    },

                    Instruction_::BinOpWithStatus(op, status, op1, op2) => {
                        trace!("instsel on BINOP_STATUS");
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
399
                        self.emit_binop(node, inst, op, status, op1, op2, f_content, f_context, vm);
400
401
402
403
404
405
406
407
408
                    }

                    Instruction_::ConvOp { operation, ref from_ty, ref to_ty, operand } => {
                        trace!("instsel on CONVOP");

                        let ops = inst.ops.read().unwrap();

                        let ref op = ops[operand];

409
                        let tmp_res = self.get_result_value(node, 0);
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
410
                        let tmp_op = self.emit_reg(op, f_content, f_context, vm);
411
412
413
414
415
416

                        let from_ty_size = get_bit_size(&from_ty, vm);
                        let to_ty_size = get_bit_size(&to_ty, vm);

                        match operation {
                            op::ConvOp::TRUNC => {
417
                                self.backend.emit_mov(&tmp_res, &cast_value(&tmp_op, &to_ty));
418
419
420
                            },
                            op::ConvOp::ZEXT => {
                                if from_ty_size != to_ty_size {
421
                                    self.backend.emit_ubfx(&tmp_res, &cast_value(&tmp_op, &to_ty), 0, from_ty_size as u8);
422
423
424
425
426
427
                                } else {
                                    self.backend.emit_mov(&tmp_res, &tmp_op);
                                }
                            },
                            op::ConvOp::SEXT => {
                                if from_ty_size != to_ty_size {
428
                                    self.backend.emit_sbfx(&tmp_res, &cast_value(&tmp_op, &to_ty), 0, from_ty_size as u8);
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
                                } else {
                                    self.backend.emit_mov(&tmp_res, &tmp_op);
                                }
                            },
                            op::ConvOp::REFCAST | op::ConvOp::PTRCAST => {
                                // just a mov (and hopefully reg alloc will coalesce it)
                                self.backend.emit_mov(&tmp_res, &tmp_op);
                            },

                            op::ConvOp::UITOFP => {
                                self.backend.emit_ucvtf(&tmp_res, &tmp_op);
                            },

                            op::ConvOp::SITOFP => {
                                self.backend.emit_scvtf(&tmp_res, &tmp_op);
                            },

                            op::ConvOp::FPTOUI => {
                                self.backend.emit_fcvtzu(&tmp_res, &tmp_op);
                            },

                            op::ConvOp::FPTOSI => {
                                self.backend.emit_fcvtzs(&tmp_res, &tmp_op);
                            },

                            op::ConvOp::BITCAST => {
                                self.backend.emit_fmov(&tmp_res, &tmp_op);
                            },
                            op::ConvOp::FPTRUNC | op::ConvOp::FPEXT => {
                                self.backend.emit_fcvt(&tmp_res, &tmp_op);
                            },
                        }
                    }

                    Instruction_::Load { is_ptr, order, mem_loc } => {
                        trace!("instsel on LOAD");
                        let ops = inst.ops.read().unwrap();
                        let ref loc_op = ops[mem_loc];

                        // Whether to use a load acquire
                        let use_acquire = match order {
                            MemoryOrder::Relaxed | MemoryOrder::NotAtomic => false,
                            MemoryOrder::Consume | MemoryOrder::Acquire | MemoryOrder::SeqCst => true,
                            _ => panic!("didnt expect order {:?} with load inst", order)
                        };

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
475
                        let resolved_loc = self.emit_node_addr_to_value(loc_op, f_content, f_context, vm);
476
                        let res = self.get_result_value(node, 0);
477
478
479

                        if use_acquire {
                            // Can only have a base for a LDAR
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
480
                            let temp_loc = self.emit_mem_base(&resolved_loc, f_context, vm);
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
                            match res.ty.v {
                                // Have to load a temporary GPR first
                                MuType_::Float => {
                                    let temp = make_temporary(f_context, UINT32_TYPE.clone(), vm);
                                    self.backend.emit_ldar(&temp, &temp_loc);
                                    self.backend.emit_fmov(&res, &temp);
                                }
                                MuType_::Double => {
                                    let temp = make_temporary(f_context, UINT64_TYPE.clone(), vm);
                                    self.backend.emit_ldar(&temp, &temp_loc);
                                    self.backend.emit_fmov(&res, &temp);
                                }
                                // Can load the register directly
                                _ =>  self.backend.emit_ldar(&res, &temp_loc)
                            };
496
                        } else {
497
498
                            let temp_loc = emit_mem(self.backend.as_mut(), &resolved_loc, f_context, vm);
                            self.backend.emit_ldr(&res, &temp_loc, false);
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
                        }
                    }

                    Instruction_::Store { is_ptr, order, mem_loc, value } => {
                        trace!("instsel on STORE");
                        let ops = inst.ops.read().unwrap();
                        let ref loc_op = ops[mem_loc];
                        let ref val_op = ops[value];

                        // Whether to use a store release or not
                        let use_release = match order {
                            MemoryOrder::Relaxed | MemoryOrder::NotAtomic => false,
                            MemoryOrder::Release | MemoryOrder::SeqCst => true,
                            _ => panic!("didnt expect order {:?} with load inst", order)
                        };

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
515
516
                        let resolved_loc = self.emit_node_addr_to_value(loc_op, f_content, f_context, vm);
                        let val = self.emit_reg(val_op, f_content, f_context, vm);
517
518
519

                        if use_release {
                            // Can only have a base for a STLR
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
520
                            let temp_loc = self.emit_mem_base(&resolved_loc, f_context, vm);
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536

                            match val.ty.v {
                                // Have to store a temporary GPR
                                MuType_::Float => {
                                    let temp = make_temporary(f_context, UINT32_TYPE.clone(), vm);
                                    self.backend.emit_fmov(&temp, &val);
                                    self.backend.emit_stlr(&temp_loc, &temp);
                                }
                                MuType_::Double => {
                                    let temp = make_temporary(f_context, UINT64_TYPE.clone(), vm);
                                    self.backend.emit_fmov(&temp, &val);
                                    self.backend.emit_stlr(&temp_loc, &temp);
                                }
                                // Can load the register directly
                                _ => self.backend.emit_stlr(&temp_loc, &val)
                            };
537
                        } else {
538
                            let temp_loc = emit_mem(self.backend.as_mut(), &resolved_loc, f_context, vm);
539
540
541
542
                            self.backend.emit_str(&temp_loc, &val);
                        }
                    }

543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
                    Instruction_::CmpXchg{is_ptr, is_weak, success_order, fail_order, mem_loc, expected_value, desired_value} => {
                        // Note: this uses the same operations as GCC (for the C++ atomic cmpxchg)
                        // Clang is slightly different and ignores the 'fail_order'
                        let use_acquire = match fail_order {
                            MemoryOrder::Acquire | MemoryOrder::SeqCst => true,
                            MemoryOrder::Relaxed => match success_order {
                                MemoryOrder::Acquire | MemoryOrder::AcqRel | MemoryOrder::SeqCst => true,
                                MemoryOrder::Relaxed | MemoryOrder::Release => false,
                                _ => panic!("didnt expect success order {:?} for cmpxchg", success_order)
                            },
                            _ => panic!("didnt expect fail order {:?} for cmpxchg", fail_order)
                        };
                        let use_release = match fail_order {
                            MemoryOrder::Acquire => match success_order {
                                MemoryOrder::Relaxed | MemoryOrder::Release | MemoryOrder::AcqRel | MemoryOrder::SeqCst => true,
                                MemoryOrder::Acquire => false,
                                _ => panic!("didnt expect success order {:?} for cmpxchg", success_order)
                            },
                            MemoryOrder::SeqCst => true,
                            MemoryOrder::Relaxed => match success_order {
                                MemoryOrder::Release | MemoryOrder::AcqRel | MemoryOrder::SeqCst => true,
                                MemoryOrder::Relaxed | MemoryOrder::Acquire => false,
                                _ => panic!("didnt expect success order {:?} for cmpxchg", success_order)
                            },
                            _ => panic!("didnt expect fail order {:?} for cmpxchg", fail_order)
                        };


                        let ops = inst.ops.read().unwrap();
                        let loc = self.emit_node_addr_to_value(&ops[mem_loc], f_content, f_context, vm);
                        let expected = self.emit_reg(&ops[expected_value], f_content, f_context, vm);
                        let desired = self.emit_reg(&ops[desired_value], f_content, f_context, vm);

                        let res_value = self.get_result_value(node, 0);
                        let res_success = self.get_result_value(node, 1);


                        let blk_cmpxchg_start = format!("{}_cmpxchg_start", node.id());
                        let blk_cmpxchg_failed = format!("{}_cmpxchg_failed", node.id());
                        let blk_cmpxchg_succeded = format!("{}_cmpxchg_succeded", node.id());

                        self.finish_block(&vec![loc.clone(),expected.clone(), desired.clone()]);

586
                        // cmpxchg_start:
587
588
589
                        self.start_block(blk_cmpxchg_start.clone(), &vec![loc.clone(),expected.clone(), desired.clone()]);

                        if use_acquire {
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
                            match res_value.ty.v {
                                // Have to load a temporary GPR first
                                MuType_::Float => {
                                    let temp = make_temporary(f_context, UINT32_TYPE.clone(), vm);
                                    self.backend.emit_ldaxr(&temp, &loc);
                                    self.backend.emit_fmov(&res_value, &temp);
                                }
                                MuType_::Double => {
                                    let temp = make_temporary(f_context, UINT64_TYPE.clone(), vm);
                                    self.backend.emit_ldaxr(&temp, &loc);
                                    self.backend.emit_fmov(&res_value, &temp);
                                }
                                // Can load the register directly
                                _ => self.backend.emit_ldaxr(&res_value, &loc)
                            };
605
                        } else {
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
                            match res_value.ty.v {
                                // Have to load a temporary GPR first
                                MuType_::Float => {
                                    let temp = make_temporary(f_context, UINT32_TYPE.clone(), vm);
                                    self.backend.emit_ldxr(&temp, &loc);
                                    self.backend.emit_fmov(&res_value, &temp);
                                }
                                MuType_::Double => {
                                    let temp = make_temporary(f_context, UINT64_TYPE.clone(), vm);
                                    self.backend.emit_ldxr(&temp, &loc);
                                    self.backend.emit_fmov(&res_value, &temp);
                                }
                                // Can load the register directly
                                _ => self.backend.emit_ldxr(&res_value, &loc)
                            };
621
622
623
624
625
626
627
628
629
630
                        }

                        if expected.is_int_reg() {
                            self.backend.emit_cmp(&res_value, &expected);
                        } else {
                            self.backend.emit_fcmp(&res_value, &expected);
                        }
                        self.backend.emit_b_cond("NE", blk_cmpxchg_failed.clone());

                        if use_release {
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
                            match desired.ty.v {
                                // Have to store a temporary GPR
                                MuType_::Float => {
                                    let temp = make_temporary(f_context, UINT32_TYPE.clone(), vm);
                                    self.backend.emit_fmov(&temp, &desired);
                                    self.backend.emit_stlxr(&loc, &res_success, &temp);
                                }
                                MuType_::Double => {
                                    let temp = make_temporary(f_context, UINT64_TYPE.clone(), vm);
                                    self.backend.emit_fmov(&temp, &desired);
                                    self.backend.emit_stlxr(&loc, &res_success, &temp);
                                }
                                // Can load the register directly
                                _ => self.backend.emit_stlxr(&loc, &res_success, &desired)
                            };
646
                        } else {
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
                            match desired.ty.v {
                                // Have to store a temporary GPR
                                MuType_::Float => {
                                    let temp = make_temporary(f_context, UINT32_TYPE.clone(), vm);
                                    self.backend.emit_fmov(&temp, &desired);
                                    self.backend.emit_stxr(&loc, &res_success, &temp);
                                }
                                MuType_::Double => {
                                    let temp = make_temporary(f_context, UINT64_TYPE.clone(), vm);
                                    self.backend.emit_fmov(&temp, &desired);
                                    self.backend.emit_stxr(&loc, &res_success, &temp);
                                }
                                // Can load the register directly
                                _ => self.backend.emit_stxr(&loc, &res_success, &desired)
                            };
662
663
664
665
666
667
668
669
670
671
672
                        }

                        if !is_weak {
                            // Store failed, try again
                            self.backend.emit_cbnz(&res_success, blk_cmpxchg_start.clone());
                        }

                        self.backend.emit_b(blk_cmpxchg_succeded.clone());

                        self.finish_block(&vec![res_success.clone(), res_value.clone()]);

673
                        // cmpxchg_failed:
674
675
676
677
678
679
680
681
                        self.start_block(blk_cmpxchg_failed.clone(), &vec![res_success.clone(), res_value.clone()]);

                        self.backend.emit_clrex();
                        // Set res_success to 1 (the same value STXR/STLXR uses to indicate failure)
                        self.backend.emit_mov_imm(&res_success, 1);

                        self.finish_block(&vec![res_success.clone(), res_value.clone()]);

682
                        // cmpxchg_succeded:
683
684
685
686
                        self.start_block(blk_cmpxchg_succeded.clone(), &vec![res_success.clone(), res_value.clone()]);
                        // this NOT is needed as STXR/STLXR returns sucess as '0', wheras the Mu spec says it should be 1
                        self.backend.emit_eor_imm(&res_success, &res_success, 1);
                    }
687
688
689
690
691
692
                    Instruction_::GetIRef(_)
                    | Instruction_::GetFieldIRef { .. }
                    | Instruction_::GetElementIRef{..}
                    | Instruction_::GetVarPartIRef { .. }
                    | Instruction_::ShiftIRef { .. } => {
                        trace!("instsel on GET/FIELD/VARPARTIREF, SHIFTIREF");
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
693
                        let mem_addr = self.emit_get_mem_from_inst(node, f_content, f_context, vm);
694
                        let tmp_res = self.get_result_value(node, 0);
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
695
                        self.emit_calculate_address(&tmp_res, &mem_addr, f_context, vm);
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
                    }

                    Instruction_::Fence(order) => {
                        trace!("instsel on FENCE");

                        // Whether to emit a load fence or a normal one
                        let use_load = match order {
                            MemoryOrder::Release | MemoryOrder::SeqCst | MemoryOrder::AcqRel => false,
                            MemoryOrder::Acquire => true,
                            _ => panic!("didnt expect order {:?} with load inst", order)
                        };

                        if use_load {
                            // Data Memory Barrirer for Inner Shariable Domain (for Load accesses only)
                            self.backend.emit_dmb("ISHLD");
                        } else {
                            // Data Memory Barrirer for Inner Shariable Domain
                            self.backend.emit_dmb("ISH");
                        }
                    }
716

717
718
719
                    // TODO: Implement this similar to a return (where theres a common exit block)
                    // and change SWAP_BACK_TO_NATIV_STACK and swap_to_mu_stack so they don't handle the callee saved registers
                    // (this instruction should then guarentee that they are restored (in the same way a Return does)
720
721
722
723
724
                    Instruction_::ThreadExit => {
                        trace!("instsel on THREADEXIT");
                        // emit a call to swap_back_to_native_stack(sp_loc: Address)

                        // get thread local and add offset to get sp_loc
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
725
                        let tl = self.emit_get_threadlocal(Some(node), f_content, f_context, vm);
726
727
                        self.backend.emit_add_imm(&tl, &tl, *thread::NATIVE_SP_LOC_OFFSET as u16, false);

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
728
                        self.emit_runtime_entry(&entrypoints::SWAP_BACK_TO_NATIVE_STACK, vec![tl.clone()], None, Some(node), f_content, f_context, vm);
729
730
                    }

731

732
733
734
                    Instruction_::CommonInst_GetThreadLocal => {
                        trace!("instsel on GETTHREADLOCAL");
                        // get thread local
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
735
                        let tl = self.emit_get_threadlocal(Some(node), f_content, f_context, vm);
736

737
                        let tmp_res = self.get_result_value(node, 0);
738
739

                        // load [tl + USER_TLS_OFFSET] -> tmp_res
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
740
                        self.emit_load_base_offset(&tmp_res, &tl, *thread::USER_TLS_OFFSET as i64, f_context, vm);
741
742
                    }

743

744
745
746
747
748
749
750
                    Instruction_::CommonInst_SetThreadLocal(op) => {
                        trace!("instsel on SETTHREADLOCAL");
                        let ops = inst.ops.read().unwrap();
                        let ref op = ops[op];

                        debug_assert!(self.match_ireg(op));

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
751
                        let tmp_op = self.emit_ireg(op, f_content, f_context, vm);
752
753

                        // get thread local
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
754
                        let tl = self.emit_get_threadlocal(Some(node), f_content, f_context, vm);
755
756

                        // store tmp_op -> [tl + USER_TLS_OFFSTE]
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
757
                        self.emit_store_base_offset(&tl, *thread::USER_TLS_OFFSET as i64, &tmp_op, f_context, vm);
758
759
760
761
762
763
764
765
766
                    }

                    Instruction_::CommonInst_Pin(op) => {
                        trace!("instsel on PIN");
                        if !mm::GC_MOVES_OBJECT {
                            // non-moving GC: pin is a nop (move from op to result)
                            let ops = inst.ops.read().unwrap();
                            let ref op = ops[op];

767
                            let tmp_res = self.get_result_value(node, 0);
768

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
769
                            self.emit_move_node_to_value(&tmp_res, op, f_content, f_context, vm);
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
                        } else {
                            unimplemented!()
                        }
                    }

                    Instruction_::CommonInst_Unpin(_) => {
                        trace!("instsel on UNPIN");
                        if !mm::GC_MOVES_OBJECT {
                            // do nothing
                        } else {
                            unimplemented!()
                        }
                    }

                    Instruction_::Move(op) => {
                        trace!("instsel on MOVE (internal IR)");
                        let ops = inst.ops.read().unwrap();
                        let ref op = ops[op];

789
                        let tmp_res = self.get_result_value(node, 0);
790

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
791
                        self.emit_move_node_to_value(&tmp_res, op, f_content, f_context, vm);
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
                    }

                    Instruction_::New(ref ty) => {
                        trace!("instsel on NEW");
                        if cfg!(debug_assertions) {
                            match ty.v {
                                MuType_::Hybrid(_) => panic!("cannot use NEW for hybrid, use NEWHYBRID instead"),
                                _ => {}
                            }
                        }

                        let ty_info = vm.get_backend_type_info(ty.id());
                        let size = ty_info.size;
                        let ty_align = ty_info.alignment;

807
                        let const_size = make_value_int_const(size as u64, vm);
808

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
809
810
                        let tmp_allocator = self.emit_get_allocator(node, f_content, f_context, vm);
                        let tmp_res = self.emit_alloc_sequence(tmp_allocator.clone(), const_size, ty_align, node, f_content, f_context, vm);
811
812

                        // ASM: call muentry_init_object(%allocator, %tmp_res, %encode)
813
                        let encode = make_value_int_const(mm::get_gc_type_encode(ty_info.gc_type.id), vm);
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
814
                        self.emit_runtime_entry(
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
                            &entrypoints::INIT_OBJ,
                            vec![tmp_allocator.clone(), tmp_res.clone(), encode],
                            None,
                            Some(node), f_content, f_context, vm
                        );
                    }

                    Instruction_::NewHybrid(ref ty, var_len) => {
                        trace!("instsel on NEWHYBRID");
                        if cfg!(debug_assertions) {
                            match ty.v {
                                MuType_::Hybrid(_) => {},
                                _ => panic!("NEWHYBRID is only for allocating hybrid types, use NEW for others")
                            }
                        }

                        let ty_info = vm.get_backend_type_info(ty.id());
                        let ty_align = ty_info.alignment;
                        let fix_part_size = ty_info.size;
                        let var_ty_size = match ty.v {
                            MuType_::Hybrid(ref name) => {
                                let map_lock = HYBRID_TAG_MAP.read().unwrap();
                                let hybrid_ty_ = map_lock.get(name).unwrap();
                                let var_ty = hybrid_ty_.get_var_ty();

                                vm.get_backend_type_info(var_ty.id()).size
                            },
                            _ => panic!("only expect HYBRID type here")
                        };

                        // actual size = fix_part_size + var_ty_size * len
                        let (actual_size, length) = {
                            let ops = inst.ops.read().unwrap();
                            let ref var_len = ops[var_len];

850
851
                            if match_node_int_imm(var_len) {
                                let var_len = node_imm_to_u64(var_len);
852
853
                                let actual_size = fix_part_size + var_ty_size * (var_len as usize);
                                (
854
855
                                    make_value_int_const(actual_size as u64, vm),
                                    make_value_int_const(var_len as u64, vm)
856
857
                                )
                            } else {
858
                                let tmp_actual_size = make_temporary(f_context, UINT64_TYPE.clone(), vm);
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
859
                                let tmp_var_len = self.emit_ireg(var_len, f_content, f_context, vm);
860
861

                                // tmp_actual_size = tmp_var_len*var_ty_size
862
                                emit_mul_u64(self.backend.as_mut(), &tmp_actual_size, &tmp_var_len, f_context, vm, var_ty_size as u64);
863
                                // tmp_actual_size = tmp_var_len*var_ty_size + fix_part_size
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
864
                                self.emit_add_u64(&tmp_actual_size, &tmp_actual_size, f_context, vm, fix_part_size as u64);
865
866
867
868
                                (tmp_actual_size, tmp_var_len)
                            }
                        };

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
869
870
                        let tmp_allocator = self.emit_get_allocator(node, f_content, f_context, vm);
                        let tmp_res = self.emit_alloc_sequence(tmp_allocator.clone(), actual_size, ty_align, node, f_content, f_context, vm);
871
872

                        // ASM: call muentry_init_object(%allocator, %tmp_res, %encode)
873
                        let encode = make_value_int_const(mm::get_gc_type_encode(ty_info.gc_type.id), vm);
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
874
                        self.emit_runtime_entry(
875
876
877
878
879
880
881
882
883
884
885
886
887
                            &entrypoints::INIT_HYBRID,
                            vec![tmp_allocator.clone(), tmp_res.clone(), encode, length],
                            None,
                            Some(node), f_content, f_context, vm
                        );
                    }

                    // Runtime Entry
                    Instruction_::Throw(op_index) => {
                        trace!("instsel on THROW");
                        let ops = inst.ops.read().unwrap();
                        let ref exception_obj = ops[op_index];

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
888
                        self.emit_runtime_entry(
889
890
891
892
893
894
895
896
897
898
899
900
                            &entrypoints::THROW_EXCEPTION,
                            vec![exception_obj.clone_value()],
                            None,
                            Some(node), f_content, f_context, vm);
                    }

                    // Runtime Entry
                    Instruction_::PrintHex(index) => {
                        trace!("instsel on PRINTHEX");
                        let ops = inst.ops.read().unwrap();
                        let ref op = ops[index];

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
901
                        self.emit_runtime_entry(
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
                            &entrypoints::PRINT_HEX,
                            vec![op.clone_value()],
                            None,
                            Some(node), f_content, f_context, vm
                        );
                    }

                    _ => unimplemented!()
                } // main switch
            },

            TreeNode_::Value(_) => {}
        }
    }

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
917
918
919
    fn make_value_base_offset(&mut self, base: &P<Value>, offset: i64, ty: &P<MuType>, vm: &VM) -> P<Value> {
        let mem = self.make_memory_location_base_offset(base, offset, vm);
        self.make_value_from_memory(mem, ty, vm)
920
921
    }

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
922
    fn make_value_from_memory(&mut self, mem: MemoryLocation, ty: &P<MuType>, vm: &VM) -> P<Value> {
923
924
925
926
927
928
929
        P(Value {
            hdr: MuEntityHeader::unnamed(vm.next_id()),
            ty: ty.clone(),
            v: Value_::Memory(mem)
        })
    }

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
930
    fn make_memory_location_base_offset(&mut self, base: &P<Value>, offset: i64, vm: &VM) -> MemoryLocation {
931
932
933
934
935
936
937
938
939
940
        if offset == 0 {
            MemoryLocation::VirtualAddress{
                base: base.clone(),
                offset: None,
                scale: 1,
                signed: true,
            }
        } else {
            MemoryLocation::VirtualAddress{
                base: base.clone(),
941
                offset: Some(make_value_int_const(offset as u64, vm)),
942
943
944
945
946
947
                scale: 1,
                signed: true,
            }
        }
    }

948
    // Same as emit_mem except returns a memory location with only a base
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
949
950
    // NOTE: This code duplicates allot of code in emit_mem and emit_calculate_address
    fn emit_mem_base(&mut self, pv: &P<Value>, f_context: &mut FunctionContext, vm: &VM) -> P<Value> {
951
952
953
954
955
956
        match pv.v {
            Value_::Memory(ref mem) => {
                let base = match mem {
                    &MemoryLocation::VirtualAddress{ref base, ref offset, scale, signed} => {
                        if offset.is_some() {
                            let offset = offset.as_ref().unwrap();
957
958
                            if match_value_int_imm(offset) {
                                let offset_val = value_imm_to_i64(offset);
959
960
961
                                if offset_val == 0 {
                                    base.clone() // trivial
                                } else {
962
                                    let temp = make_temporary(f_context, pv.ty.clone(), vm);
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
963
                                    self.emit_add_u64(&temp, &base, f_context, vm, (offset_val * scale as i64) as u64);
964
965
966
                                    temp
                                }
                            } else {
967
                                let offset = emit_ireg_value(self.backend.as_mut(), offset, f_context, vm);
968
969
970
971

                                // TODO: If scale == r*m (for some 0 <= m <= 4), multiply offset by r
                                // then use and add_ext(,...,m)
                                if scale.is_power_of_two() && is_valid_immediate_extension(log2(scale)) {
972
973
                                    let temp = make_temporary(f_context, pv.ty.clone(), vm);
                                    // temp = base + offset << log2(scale)
974
975
976
                                    self.backend.emit_add_ext(&temp, &base, &offset, signed, log2(scale) as u8);
                                    temp
                                } else {
977
                                    let temp_offset = make_temporary(f_context, offset.ty.clone(), vm);
978

979
980
                                    // temp_offset = offset * scale
                                    emit_mul_u64(self.backend.as_mut(), &temp_offset, &offset, f_context, vm, scale);
981
982

                                    // Don't need to create a new register, just overwrite temp_offset
983
                                    let temp = cast_value(&temp_offset, &pv.ty);
984
985
986
987
988
989
                                    // Need to use add_ext, in case offset is 32-bits
                                    self.backend.emit_add_ext(&temp, &base, &temp_offset, signed, 0);
                                    temp
                                }
                            }
                        }
990
991
992
                            else {
                                base.clone() // trivial
                            }
993
994
995
996
997
                    }
                    &MemoryLocation::Address{ref base, ref offset, shift, signed} => {
                        if offset.is_some() {
                            let ref offset = offset.as_ref().unwrap();

998
999
                            if match_value_int_imm(&offset) {
                                let offset = value_imm_to_u64(&offset);
1000
1001
1002
1003
                                if offset == 0 {
                                    // Offset is 0, it can be ignored
                                    base.clone()
                                } else {
1004
                                    let temp = make_temporary(f_context, pv.ty.clone(), vm);
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1005
                                    self.emit_add_u64(&temp, &base, f_context, vm, offset as u64);
1006
1007
1008
                                    temp
                                }
                            } else if offset.is_int_reg() {
1009
                                let temp = make_temporary(f_context, pv.ty.clone(), vm);
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
                                self.backend.emit_add_ext(&temp, &base, &offset, signed, shift);
                                temp
                            } else {
                                panic!("Offset should be an integer register or a constant")
                            }
                        } else {
                            // Simple base address
                            base.clone()
                        }
                    }
1020
                    &MemoryLocation::Symbolic{ref label, is_global} => {
1021
1022
                        let temp = make_temporary(f_context, pv.ty.clone(), vm);
                        emit_addr_sym(self.backend.as_mut(), &temp, &pv, vm);
1023
1024
1025
1026
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
                        temp
                    },
                };

                P(Value {
                    hdr: MuEntityHeader::unnamed(vm.next_id()),
                    ty: pv.ty.clone(),
                    v: Value_::Memory(MemoryLocation::Address {
                        base: base.clone(),
                        offset: None,
                        shift: 0,
                        signed: false
                    })
                })
            }
            _ => panic!("expected memory")
        }
    }

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1042
    fn make_memory_location_base_offset_scale(&mut self, base: &P<Value>, offset: &P<Value>, scale: u64, signed: bool) -> MemoryLocation {
1043
1044
1045
1046
1047
1048
1049
1050
1051
        MemoryLocation::VirtualAddress{
            base: base.clone(),
            offset: Some(offset.clone()),
            scale: scale,
            signed: signed
        }
    }

    // Returns a memory location that points to 'Base + offset*scale + more_offset'
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1052
    fn memory_location_shift(&mut self, mem: MemoryLocation, more_offset: i64, f_context: &mut FunctionContext, vm: &VM) -> MemoryLocation {
1053
1054
1055
        if more_offset == 0 {
            return mem; // No need to do anything
        }
1056
        match mem {
1057
            MemoryLocation::VirtualAddress { ref base, ref offset, scale, signed } => {
1058
1059
                let mut new_scale = 1;
                let new_offset =
1060
                    if offset.is_some() {
1061
1062
                        let offset = offset.as_ref().unwrap();
                        if match_value_int_imm(&offset) {
1063
                            let offset = offset.extract_int_const()*scale + (more_offset as u64);
1064
                            make_value_int_const(offset as u64, vm)
1065
                        } else {
1066
1067
                            let offset = emit_ireg_value(self.backend.as_mut(), &offset, f_context, vm);
                            let temp = make_temporary(f_context, offset.ty.clone(), vm);
1068

1069
1070
1071
1072
                            if more_offset % (scale as i64) == 0 {
                                // temp = offset + more_offset/scale
                                self.emit_add_u64(&temp, &offset, f_context, vm, (more_offset/(scale as i64)) as u64);
                                new_scale = scale;
1073
                            } else {
1074
                                // temp = offset*scale + more_offset
1075
                                emit_mul_u64(self.backend.as_mut(), &temp, &offset, f_context, vm, scale);
1076
                                self.emit_add_u64(&temp, &temp, f_context, vm, more_offset as u64);
1077
1078
1079
1080
1081
                            }

                            temp
                        }
                    }
1082
1083
1084
                        else {
                            make_value_int_const(more_offset as u64, vm)
                        };
1085
1086
1087
1088
1089
1090
1091
1092

                // if offset was an immediate or more_offset % scale != 0:
                //      new_offset = offset*scale+more_offset
                //      new_scale = 1
                // otherwise:
                //      new_offset = offset + more_offset/scale
                //      new_scale = scale
                // Either way: (new_offset*new_scale) = offset*scale+more_offset
1093
1094
                MemoryLocation::VirtualAddress {
                    base: base.clone(),
1095
1096
                    offset: Some(new_offset),
                    scale: new_scale,
1097
1098
1099
1100
1101
1102
1103
1104
                    signed: signed,
                }
            },
            _ => panic!("expected a VirtualAddress memory location")
        }
    }

    // Returns a memory location that points to 'Base + offset*scale + more_offset*new_scale'
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1105
    fn memory_location_shift_scale(&mut self, mem: MemoryLocation, more_offset:  &P<Value>, new_scale: u64, f_context: &mut FunctionContext, vm: &VM) -> MemoryLocation {
1106
1107
1108
        if match_value_int_imm(&more_offset) {
            let more_offset = value_imm_to_i64(&more_offset);
            self.memory_location_shift(mem, more_offset * (new_scale as i64), f_context, vm)
1109
        } else {
1110
            let mut new_scale = new_scale;
1111
            match mem {
1112
                MemoryLocation::VirtualAddress { ref base, ref offset, scale, signed } => {
1113
1114
                    let offset =
                        if offset.is_some() {
1115
1116
1117
                            let offset = offset.as_ref().unwrap();
                            if match_value_int_imm(&offset) {
                                let temp = make_temporary(f_context, offset.ty.clone(), vm);
1118
1119
1120
1121
1122
1123
1124
                                let offset_scaled = (offset.extract_int_const() as i64)*(scale as i64);
                                if offset_scaled % (new_scale as i64) == 0 {
                                    self.emit_add_u64(&temp, &more_offset, f_context, vm, (offset_scaled / (new_scale as i64)) as u64);
                                    // new_scale*temp = (more_offset + (offset*scale)/new_scale)
                                    //                = more_offset*new_scale + offset*scale
                                } else {
                                    // temp = more_offset*new_scale + offset*scale
1125
                                    emit_mul_u64(self.backend.as_mut(), &temp, &more_offset, f_context, vm, new_scale);
1126
1127
1128
                                    self.emit_add_u64(&temp, &temp, f_context, vm, offset_scaled as u64);
                                    new_scale = 1;
                                }
1129
1130
                                temp
                            } else {
1131
1132
                                let offset = emit_ireg_value(self.backend.as_mut(), &offset, f_context, vm);
                                let temp = make_temporary(f_context, offset.ty.clone(), vm);
1133

1134
1135
1136
1137
                                if new_scale == scale {
                                    // just add the offsets
                                    self.backend.emit_add_ext(&temp, &more_offset, &temp, signed, 0);
                                }  else {
1138
                                    // temp = offset * scale
1139
                                    emit_mul_u64(self.backend.as_mut(), &temp, &offset, f_context, vm, scale);
1140

1141
1142
1143
1144
1145
                                    if new_scale.is_power_of_two() && is_valid_immediate_extension(log2(new_scale)) {
                                        // temp = (offset * scale) + more_offset << log2(new_scale)
                                        self.backend.emit_add_ext(&temp, &temp, &more_offset, signed, log2(new_scale) as u8);
                                    } else {
                                        // temp_more = more_offset * new_scale
1146
1147
                                        let temp_more = make_temporary(f_context, offset.ty.clone(), vm);
                                        emit_mul_u64(self.backend.as_mut(), &temp_more, &more_offset, f_context, vm, new_scale);
1148

1149
1150
1151
                                        // temp = (offset * scale) + (more_offset * new_scale);
                                        self.backend.emit_add_ext(&temp, &temp_more, &temp, signed, 0);
                                    }
1152

1153
1154
                                    new_scale = 1;
                                }
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
1169
1170
1171
1172
1173
                                temp
                            }
                        } else {
                            more_offset.clone()
                        };
                    MemoryLocation::VirtualAddress {
                        base: base.clone(),
                        offset: Some(offset),
                        scale: new_scale,
                        signed: signed,
                    }
                },
                _ => panic!("expected a VirtualAddress memory location")
            }
        }
    }

    // Returns the size of the operation
    // TODO: If the RHS of an ADD is negative change it to a SUB (and vice versa)
1174
1175
    // TODO: Treat XOR 1....1, arg and XOR arg, 1....1 specially (1....1 is an invalid logical immediate, but the operation is non trivial so it should be optimised to res = MVN arg)
    // Note: Assume that trivial operations are to be optimised by the Mu IR compiler (but this function still needs to work correctly if they aren't optimsed away)
1176
    // TODO: Use a shift when dividing or multiplying by a power of two
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1177
    fn emit_binop(&mut self, node: &TreeNode, inst: &Instruction, op: BinOp, status: BinOpStatus, op1: OpIndex, op2: OpIndex, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) {
1178
1179
1180
1181
        use std;
        let mut op1 = op1;
        let mut op2 = op2;
        let ops = inst.ops.read().unwrap();
1182
        let res = self.get_result_value(node, 0);
1183
1184
1185
1186
1187
1188
1189
1190

        // Get the size (in bits) of the type the operation is on
        let n = get_bit_size(&res.ty, vm);
        let output_status = status.flag_n || status.flag_z || status.flag_c || status.flag_v;
        let mut status_value_index = 0;
        // NOTE: XZR is just a dummy value here (it will not be used)
        let tmp_status_n = if status.flag_n {
            status_value_index += 1;
1191
            self.get_result_value(node, status_value_index)
1192
1193
1194
        } else { XZR.clone() };
        let tmp_status_z = if status.flag_z {
            status_value_index += 1;
1195
            self.get_result_value(node, status_value_index)
1196
1197
1198
        } else { XZR.clone() };
        let tmp_status_c = if status.flag_c {
            status_value_index += 1;
1199
            self.get_result_value(node, status_value_index)
1200
1201
1202
        } else { XZR.clone() };
        let tmp_status_v = if status.flag_v {
            status_value_index += 1;
1203
            self.get_result_value(node, status_value_index)
1204
1205
1206
1207
1208
1209
1210
1211
1212
        } else { XZR.clone() };

        // TODO: Division by zero exception (note: must explicitly check for this, arm dosn't do it)
        match op {
            // The lower n bits of the result will be correct, and will not depend
            // on the > n bits of op1 or op2
            op::BinOp::Add => {
                let mut imm_val = 0 as u64;
                // Is one of the arguments a valid immediate?
1213
1214
                let emit_imm = if match_node_int_imm(&ops[op2]) {
                    imm_val = node_imm_to_u64(&ops[op2]);
1215
                    is_valid_arithmetic_imm(imm_val)
1216
1217
                } else if match_node_int_imm(&ops[op1]) {
                    imm_val = node_imm_to_u64(&ops[op1]);
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
                    // if op1 is a valid immediate, swap it with op2
                    if is_valid_arithmetic_imm(imm_val) {
                        std::mem::swap(&mut op1, &mut op2);
                        true
                    } else {
                        false
                    }
                } else {
                    false
                };

                if emit_imm {
                    trace!("emit add-ireg-imm");

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1232
                    let reg_op1 = self.emit_ireg(&ops[op1], f_content, f_context, vm);
1233
1234
1235
1236
                    let imm_shift = imm_val > 4096;
                    let imm_op2 = if imm_shift { imm_val >> 12 } else { imm_val };

                    if output_status {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1237
                        self.emit_zext(&reg_op1);
1238
1239
1240
1241
1242
1243
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258
1259
1260
1261
1262
1263
1264
1265
1266
1267
1268
1269
1270
1271
1272
1273
1274
1275
1276
1277
1278
                        self.backend.emit_adds_imm(&res, &reg_op1, imm_op2 as u16, imm_shift);

                        if status.flag_v {
                            if n < 32 {
                                // tmp_status[n-1] = 1 iff res and op1 have different signs
                                self.backend.emit_eor(&tmp_status_v, &res, &reg_op1);
                                // tmp[n-1] = 1 iff op1 and op2 have different signs

                                // Sign bit of op2 is 0
                                if !get_bit(imm_val, n - 1) {
                                    // tmp_status[n-1] = 1 iff res and op1 have different signs
                                    //      and op1 has the same sign as op2 (which is 0)
                                    self.backend.emit_bic(&tmp_status_v, &tmp_status_v, &reg_op1);
                                } else {
                                    // tmp_status[n-1] = 1 iff res and op1 have different signs
                                    //      and op1 has the same sign as op2 (which is 1)
                                    self.backend.emit_and(&tmp_status_v, &tmp_status_v, &reg_op1);
                                }

                                // Check the sign bit of tmp_status (i.e. tmp_status[n-1])
                                self.backend.emit_tst_imm(&tmp_status_v, 1 << (n - 1));
                                self.backend.emit_cset(&tmp_status_v, "NE");
                            } else {
                                self.backend.emit_cset(&tmp_status_v, "VS");
                            }
                        }
                        if status.flag_c {
                            if n < 32 {
                                // Test the carry bit of res
                                self.backend.emit_tst_imm(&res, 1 << n);
                                self.backend.emit_cset(&tmp_status_c, "NE");
                            } else {
                                self.backend.emit_cset(&tmp_status_c, "CS");
                            }
                        }
                    } else {
                        self.backend.emit_add_imm(&res, &reg_op1, imm_op2 as u16, imm_shift);
                    }
                } else {
                    trace!("emit add-ireg-ireg");

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1279
1280
                    let reg_op1 = self.emit_ireg(&ops[op1], f_content, f_context, vm);
                    let reg_op2 = self.emit_ireg(&ops[op2], f_content, f_context, vm);
1281
1282

                    if output_status {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1283
                        self.emit_zext(&reg_op1);
1284
1285
                        if n == 1 {
                            // adds_ext dosn't support extending 1 bit numbers
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1286
                            self.emit_zext(&reg_op2);
1287
1288
1289
1290
1291
1292
1293
1294
                            self.backend.emit_adds(&res, &reg_op1, &reg_op2);
                        } else {
                            // Emit an adds that zero extends op2
                            self.backend.emit_adds_ext(&res, &reg_op1, &reg_op2, false, 0);
                        }

                        if status.flag_v {
                            if n < 32 {
1295
                                let tmp = make_temporary(f_context, UINT32_TYPE.clone(), vm);
1296
1297
1298
1299
1300
1301
1302
1303
1304
1305
1306
1307
1308
1309
1310
1311
1312
1313
1314
1315
1316
1317
1318
1319
1320
1321
1322
1323
1324
1325
1326
1327
1328

                                // tmp_status[n-1] = 1 iff res and op1 have different signs
                                self.backend.emit_eor(&tmp_status_v, &res, &reg_op1);
                                // tmp[n-1] = 1 iff op1 and op2 have different signs
                                self.backend.emit_eor(&tmp, &reg_op1, &reg_op2);

                                // tmp_status[n-1] = 1 iff res and op1 have different signs
                                //      and op1 and op2 have the same sign
                                self.backend.emit_bic(&tmp_status_v, &tmp_status_v, &tmp);

                                // Check tmp_status[n-1]
                                self.backend.emit_tst_imm(&tmp_status_v, 1 << (n - 1));
                                self.backend.emit_cset(&tmp_status_v, "NE");
                            } else {
                                self.backend.emit_cset(&tmp_status_v, "VS");
                            }
                        }

                        if status.flag_c {
                            if n < 32 {
                                // Test the carry bit of res
                                self.backend.emit_tst_imm(&res, 1 << n);
                                self.backend.emit_cset(&tmp_status_c, "NE");
                            } else {
                                self.backend.emit_cset(&tmp_status_c, "CS");
                            }
                        }
                    } else {
                        self.backend.emit_add(&res, &reg_op1, &reg_op2);
                    }
                }
            },
            op::BinOp::Sub => {
1329
1330
                if match_node_int_imm(&ops[op2]) &&
                    is_valid_arithmetic_imm(node_imm_to_u64(&ops[op2])) &&