inst_sel.rs

// Copyright 2017 The Australian National University
// 
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
// 
//     http://www.apache.org/licenses/LICENSE-2.0
// 
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#![warn(unused_imports)]
#![warn(unreachable_code)]

use ast::ir::*;
use ast::ptr::*;
use ast::inst::*;
use ast::op;
use ast::op::*;
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;
use compiler::backend::EPILOGUE_BLOCK_NAME;

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

use std::collections::HashMap;
use std::collections::LinkedList;
use std::mem;
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_block_in_ir: Option<MuName>,
    current_func_start: Option<ValueLocation>,

    // A list of all callsites, with the corresponding exception block (if there is one)

    // Technically this is a map in that each Key is unique, but we will never try and add duplicate
    // keys, or look things up, so a list of pairs is faster than a Map.
    current_callsites: LinkedList<(MuName, MuID, usize)>,
    // key: block id, val: block location
    current_exn_blocks: HashMap<MuID, MuName>,
    current_xr_value: Option<P<Value>>, // A temporary that holds to saved XR value (if needed)
    current_constants: HashMap<MuID, P<Value>>,
    current_constants_locs: HashMap<MuID, P<Value>>
}

// 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
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_block_in_ir: None,  // it is possible the block is newly created in instruction selection
                                        // but sometimes we want to know its control flow
                                        // so we need to track what block it is from the IR

                                        // FIXME: ideally we should not create new blocks in instruction selection
                                        // see Issue #6
            current_func_start: None,
            current_callsites: LinkedList::new(),
            current_exn_blocks: HashMap::new(),
            current_xr_value: None,
            current_constants: HashMap::new(),
            current_constants_locs: HashMap::new()
        }

    }

    #[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
    fn instruction_select(&mut self, node: &'a TreeNode, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) {
        trace!("instsel on node#{} {}", node.id(), node);

        match node.v {
            TreeNode_::Instruction(ref inst) => {
                match inst.v {
                    // TODO: Optimise if cond is a flag from a binary operation?
                    Instruction_::Branch2 { cond, ref true_dest, ref false_dest, .. } => {
                        trace!("instsel on BRANCH2");
                        let (fallthrough_dest, branch_dest, branch_if_true) = {
                            let cur_block = f_content.get_block_by_name(self.current_block_in_ir.as_ref().unwrap().clone());
                            let next_block_in_trace = cur_block.control_flow.get_hottest_succ().unwrap();

                            if next_block_in_trace == true_dest.target {
                                (true_dest, false_dest, false)
                            } else {
                                (false_dest, true_dest, true)
                            }
                        };

                        let ref ops = inst.ops;

                        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();

                        let ref cond = ops[cond];

                        if self.match_cmp_res(cond) {
                            trace!("emit cmp_res-branch2");
                            // Emit a CBNZ for 128-bit comparisons that are not symmetric
                            let use_cbnz = self.is_int128_asym_cmp(cond);
                            let tmp_cond =
                                if use_cbnz { Some(make_temporary(f_context, UINT1_TYPE.clone(), vm)) }
                                else { None };
                            let cond_box =
                                if use_cbnz { Some(Box::new(tmp_cond.as_ref().unwrap().clone())) }
                                else { None };

                            let mut cmpop = self.emit_cmp_res(cond, cond_box, f_content, f_context, vm);

                            if use_cbnz {
                                if !branch_if_true {
                                    self.backend.emit_cbz(tmp_cond.as_ref().unwrap(), branch_target);
                                } else {
                                    self.backend.emit_cbnz(tmp_cond.as_ref().unwrap(), branch_target);
                                }

                            } else {
                                if !branch_if_true {
                                    cmpop = cmpop.invert();
                                }

                                let cond = get_condition_codes(cmpop);

                                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());

                                    if cond.len() == 2 {
                                        self.backend.emit_b_cond(cond[1], branch_target);
                                    }
                                }
                            }
                        } else {
                            let cond_reg = self.emit_ireg(cond, f_content, f_context, vm);

                            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());
                            }
                        };

                        // it is possible that the fallthrough block is scheduled somewhere else
                        // we need to explicitly jump to it
                        self.finish_block();
                        let fallthrough_temp_block = format!("{}_{}_branch_fallthrough", self.current_fv_id, node.id());
                        self.start_block(fallthrough_temp_block, &vec![]);

                        let fallthrough_target = f_content.get_block(fallthrough_dest.target).name();
                        self.backend.emit_b(fallthrough_target);
                    },

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

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

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

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

                        // moving integers/pointers
                        // generate compare
                        let cmpop = if self.match_cmp_res(cond) {
                            self.emit_cmp_res(cond, None, f_content, f_context, vm)
                        } else if self.match_ireg(cond) {
                            let tmp_cond = self.emit_ireg(cond, f_content, f_context, vm);
                            self.backend.emit_cmp_imm(&tmp_cond, 0, false);
                            NE
                        } else {
                            panic!("expected ireg, found {}", cond)
                        };

                        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);

                        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
                            unimplemented!()
                        }
                    },

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

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

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

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

                        let cmpop = self.emit_cmp_res_op(op, Some(Box::new(tmp_res.clone())), &op1, &op2, f_content, f_context, vm);
                        let cond = get_condition_codes(cmpop);

                        // emit_cmp_res_op will set tmp_res for 128-bit assymettric comparisons
                        if !self.is_int128_asym_cmp(node) {
                            if cmpop == FFALSE {
                                emit_mov_u64(self.backend.as_mut(), &tmp_res, 0);
                            } else if cmpop == FTRUE {
                                emit_mov_u64(self.backend.as_mut(), &tmp_res, 1);
                            } 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 ref ops = inst.ops;

                        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 ref ops = inst.ops;

                        let ref cond = ops[cond];

                        if self.match_ireg(cond) {
                            let tmp_cond = self.emit_ireg(cond, f_content, f_context, vm);
                            emit_zext(self.backend.as_mut(), &tmp_cond);

                            // 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?
                                let emit_imm = if match_node_int_imm(&case_op) {
                                    imm_val = node_imm_to_u64(&case_op);
                                    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 {
                                    let tmp_case_op = self.emit_ireg(case_op, f_content, f_context, vm);
                                    emit_zext(self.backend.as_mut(), &tmp_case_op);
                                    self.backend.emit_cmp(&tmp_cond, &tmp_case_op);
                                }

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

                                self.finish_block();
                                self.start_block(format!("{}_switch_not_met_case_{}", node.id(), case_op_index), &vec![]);
                            }

                            // 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!()
                        }

                        self.emit_mu_call(
                            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");

                        self.emit_mu_call(
                            inst,
                            data,
                            Some(resume),
                            node,
                            f_content, f_context, vm);
                    },

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

                        if is_abort {
                            unimplemented!()
                        }

                        self.emit_c_call_ir(inst, data, None, node, f_content, f_context, vm);
                    }

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

                        self.emit_c_call_ir(inst, data, Some(resume), node, f_content, f_context, vm);
                    }

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

                        // prepare return regs
                        let ref ops = inst.ops;
                        // TODO: Are vals in the same order as the return types in the functions signature?

                        let ret_tys = vals.iter().map(|i| node_type(&ops[*i])).collect();
                        let ret_type = self.combine_return_types(&ret_tys);

                        let n = ret_tys.len(); // number of return values
                        let xr_value = self.current_xr_value.as_ref().unwrap().clone();

                        if n == 0 {
                            // Do nothing
                        } else if n == 1 {
                            let ret_loc = self.compute_return_locations(&ret_type, &xr_value, &vm);
                            let ret_val = self.emit_node_value(&ops[vals[0]], f_content, f_context, vm);

                            if is_machine_reg(&ret_loc) && is_int_ex_reg(&ret_val) {
                                let (val_l, val_h) = split_int128(&ret_val, f_context, vm);
                                let ret_loc_h = get_register_from_id(ret_loc.id() + 2);
                                // nothing special needs to be done
                                emit_move_value_to_value(self.backend.as_mut(), &ret_loc, &val_l, f_context, vm);
                                emit_move_value_to_value(self.backend.as_mut(), &ret_loc_h, &val_h, f_context, vm);
                            } else {
                                emit_move_value_to_value(self.backend.as_mut(), &ret_loc, &ret_val, f_context, vm);
                            }
                        } else {
                            let ret_loc = self.compute_return_locations(&ret_type, &xr_value, &vm);

                            let mut i = 0;
                            for ret_index in vals {
                                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(_, _) => unimplemented!(),
                                    MuType_::Void => panic!("Unexpected void"),
                                    MuType_::Struct(_) | MuType_::Array(_, _) => unimplemented!(),
                                    MuType_::Hybrid(_) => panic!("Can't return a hybrid"),
                                    // Integral, pointer or floating point type
                                    _ => self.insert_bytes(&ret_loc, &ret_val, offset as i64, f_context, vm),
                                }

                                i += 1;
                            }
                        }

                        self.backend.emit_b(EPILOGUE_BLOCK_NAME.to_string());
                    },

                    Instruction_::BinOp(op, op1, op2) => {
                        trace!("instsel on BINOP");
                        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);
                    },

                    Instruction_::BinOpWithStatus(op, status, op1, op2) => {
                        trace!("instsel on BINOP_STATUS");
                        self.emit_binop(node, inst, op, status, op1, op2, f_content, f_context, vm);
                    }

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

                        let ref ops = inst.ops;

                        let ref op = ops[operand];

                        let tmp_res = self.get_result_value(node, 0);
                        let tmp_op = self.emit_reg(op, f_content, f_context, vm);

                        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 => {
                                // src is in one register
                                if self.match_ireg(op) {
                                    self.backend.emit_mov(&tmp_res, &cast_value(&tmp_op, &to_ty));
                                } else if self.match_ireg_ex(op) {
                                    // Move the lower word
                                    if from_ty_size != to_ty_size {
                                        let (op_l, _) = self.emit_ireg_ex(op, f_content, f_context, vm);
                                        self.backend.emit_mov(&tmp_res, &cast_value(&op_l, &to_ty));
                                    } else {
                                        self.emit_move_node_to_value(&tmp_res, op, f_content, f_context, vm);
                                    }
                                } else {
                                    panic!("unexpected op (expect ireg): {}", op);
                                }

                            },

                            op::ConvOp::ZEXT => {
                                if from_ty_size != to_ty_size {
                                    if to_ty_size <= 64 {
                                        self.backend.emit_ubfx(&tmp_res, &cast_value(&tmp_op, &to_ty), 0, from_ty_size as u8);
                                    } else if to_ty_size == 128 {
                                        let (res_l, res_h) = split_int128(&tmp_res, f_context, vm);

                                        // res_l = ZEXT src
                                        self.backend.emit_ubfx(&res_l, &cast_value(&tmp_op, &UINT64_TYPE), 0, from_ty_size as u8);
                                        self.backend.emit_mov(&res_h, &XZR); // res_h = 0

                                    } else {
                                        panic!("unexpected int length {}", to_ty_size);
                                    }
                                } else {
                                    // Trivial, just do a move
                                    emit_move_value_to_value(self.backend.as_mut(), &tmp_res, &tmp_op, f_context, vm);
                                }
                            },


                            op::ConvOp::SEXT => {
                                if from_ty_size != to_ty_size {
                                    if to_ty_size <= 64 {
                                        self.backend.emit_sbfx(&tmp_res, &cast_value(&tmp_op, &to_ty), 0, from_ty_size as u8);
                                    } else if to_ty_size == 128 {
                                        let (res_l, res_h) = split_int128(&tmp_res, f_context, vm);

                                        // res_l = SEXT src
                                        self.backend.emit_sbfx(&res_l, &cast_value(&tmp_op, &UINT64_TYPE), 0, from_ty_size as u8);
                                        self.backend.emit_asr_imm(&res_h, &tmp_op, 63); // res_h = ASHR src, 63

                                    } else {
                                        panic!("unexpected int length {}", to_ty_size);
                                    }

                                } else {
                                    // Trivial, just do a move
                                    emit_move_value_to_value(self.backend.as_mut(), &tmp_res, &tmp_op, f_context, vm);
                                }
                            },
                            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 => {
                                if from_ty_size == 128 {
                                    if to_ty_size == 64 {
                                        self.emit_runtime_entry(&entrypoints::UITOFP_U128_DOUBLE,
                                            vec![tmp_op.clone()],
                                            Some(vec![tmp_res.clone()]),
                                            Some(node), f_context, vm);
                                    } else {
                                        self.emit_runtime_entry(&entrypoints::UITOFP_U128_FLOAT,
                                            vec![tmp_op.clone()],
                                            Some(vec![tmp_res.clone()]),
                                            Some(node), f_context, vm);
                                    }
                                } else {
                                    emit_zext(self.backend.as_mut(), &tmp_op);
                                    self.backend.emit_ucvtf(&tmp_res, &tmp_op);
                                }
                            },

                            op::ConvOp::SITOFP => {
                                if from_ty_size == 128 {
                                    if to_ty_size == 64 {
                                        self.emit_runtime_entry(&entrypoints::SITOFP_I128_DOUBLE,
                                            vec![tmp_op.clone()],
                                            Some(vec![tmp_res.clone()]),
                                            Some(node), f_context, vm);
                                    } else {
                                        self.emit_runtime_entry(&entrypoints::SITOFP_I128_FLOAT,
                                            vec![tmp_op.clone()],
                                            Some(vec![tmp_res.clone()]),
                                            Some(node), f_context, vm);
                                    }
                                } else {
                                    emit_sext(self.backend.as_mut(), &tmp_op);
                                    self.backend.emit_scvtf(&tmp_res, &tmp_op);
                                }
                            },

                            op::ConvOp::FPTOUI => {
                                if to_ty_size == 128 {
                                    if from_ty_size == 64 {
                                        self.emit_runtime_entry(&entrypoints::FPTOUI_DOUBLE_U128,
                                            vec![tmp_op.clone()],
                                            Some(vec![tmp_res.clone()]),
                                            Some(node), f_context, vm);
                                    } else {
                                        self.emit_runtime_entry(&entrypoints::FPTOUI_FLOAT_U128,
                                            vec![tmp_op.clone()],
                                            Some(vec![tmp_res.clone()]),
                                            Some(node), f_context, vm);
                                    }
                                } else {
                                    self.backend.emit_fcvtzu(&tmp_res, &tmp_op);

                                    // We have to emmit code to handle the case when the real result
                                    // overflows to_ty_size, but not to_ty_reg_size
                                    let to_ty_reg_size = check_op_len(&tmp_res.ty); // The size of the aarch64 register
                                    if to_ty_size != to_ty_reg_size {
                                        // Compare the bits of the result after the lower
                                        // to_ty_size bits
                                        self.backend.emit_tst_imm(&tmp_res, bits_ones(to_ty_reg_size-to_ty_size) << to_ty_size);

                                        // If the above condition is true, the an overflow occurred
                                        // So set tmp_res to !0 (i.e. all ones, the maximum value)
                                        self.backend.emit_csinv(&tmp_res, &tmp_res, &get_alias_for_length(XZR.id(), to_ty_size), "EQ");
                                    }
                                }
                            },

                            op::ConvOp::FPTOSI => {
                                if to_ty_size == 128 {
                                    if from_ty_size == 64 {
                                        self.emit_runtime_entry(&entrypoints::FPTOSI_DOUBLE_I128, vec![tmp_op.clone()],
                                                                Some(vec![tmp_res.clone()]), Some(node), f_context, vm);
                                    } else {
                                        self.emit_runtime_entry(&entrypoints::FPTOSI_FLOAT_I128, vec![tmp_op.clone()],
                                                                Some(vec![tmp_res.clone()]), Some(node), f_context, vm);
                                    }
                                } else {
                                    self.backend.emit_fcvtzs(&tmp_res, &tmp_op);

                                    // TODO This code is horrible and inefficient due to branches and duplication
                                    // is there a better way?

                                    // We have to emmit code to handle the case when the real result
                                    // overflows to_ty_size, but not to_ty_reg_size
                                    let to_ty_reg_size = check_op_len(&tmp_res.ty); // The size of the aarch64 register
                                    if to_ty_size != to_ty_reg_size {
                                        let blk_positive = format!("{}_positive", node.id());
                                        let blk_negative = format!("{}_negative", node.id());
                                        let blk_end      = format!("{}_end", node.id());
                                        let tmp          = make_temporary(f_context, to_ty.clone(), vm);

                                        self.backend.emit_tbnz(&tmp_res, (to_ty_size - 1) as u8, blk_negative.clone());
                                        self.finish_block();

                                        self.start_block(blk_positive.clone(), &vec![]);
                                        {
                                            // check to see if the higher bits are the same as the
                                            // sign bit (which is 0), if their not there's an overflow
                                            self.backend.emit_tst_imm(&tmp_res, bits_ones(to_ty_reg_size - to_ty_size) << to_ty_size);
                                            self.backend.emit_mov_imm(&tmp, bits_ones(to_ty_size - 1));

                                            // if the above test fails (i.e. results in zero)
                                            // then set temp_res to tmp
                                            self.backend.emit_csel(&tmp_res, &tmp, &tmp_res, "EQ");

                                            self.backend.emit_b(blk_end.clone());
                                            self.finish_block();
                                        }
                                        self.start_block(blk_negative.clone(), &vec![]);
                                        {
                                            self.backend.emit_mvn(&tmp, &tmp_res);
                                            // check to see if the higher bits of temp are the same as the
                                            // sign bit (which is 1), if their not there's an overflow
                                            self.backend.emit_tst_imm(&tmp_res, bits_ones(to_ty_reg_size - to_ty_size) << to_ty_size);

                                            // Set just the sign bit (this is smallest representable signed number)
                                            self.backend.emit_mov_imm(&tmp, 1 << to_ty_size);

                                            // if the above test fails (i.e. results in zero), then set temp_res to tmp
                                            self.backend.emit_csel(&tmp_res, &tmp, &tmp_res, "EQ");
                                            self.finish_block();
                                        }
                                        self.start_block(blk_end.clone(), &vec![]);
                                    }
                                }
                            },

                            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 { order, mem_loc, .. } => {
                        trace!("instsel on LOAD");
                        let ref ops = inst.ops;
                        let ref loc_op = ops[mem_loc];

                        let resolved_loc = self.emit_node_addr_to_value(loc_op, f_content, f_context, vm);
                        let res = self.get_result_value(node, 0);

                        if self.match_ireg(node) || self.match_fpreg(node) {
                            // 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)
                            };


                            if use_acquire {
                                // Can only have a base for a LDAR
                                let temp_loc = emit_mem_base(self.backend.as_mut(), &resolved_loc, f_context, vm);
                                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)
                                };
                            } else {
                                let temp_loc = emit_mem(self.backend.as_mut(), &resolved_loc, get_type_alignment(&res.ty, vm), f_context, vm);
                                self.backend.emit_ldr(&res, &temp_loc, false);
                            }
                        } else if self.match_ireg_ex(node) {
                            let (res_l, res_h) = split_int128(&res, f_context, vm);

                            match order {
                                MemoryOrder::NotAtomic => {
                                    let temp_loc = emit_mem(self.backend.as_mut(), &resolved_loc, get_type_alignment(&res.ty, vm), f_context, vm);
                                    self.backend.emit_ldp(&res_l, &res_h, &temp_loc);
                                }

                                // Aarch64 dosn't have a load acquire pair instruction
                                // So instead we have to write a loop using load/store exclusive pairs
                                _ => {
                                    // Whether to use a load exclusive acquire
                                    let use_acquire = match order {
                                        MemoryOrder::Relaxed  => false,
                                        MemoryOrder::Consume | MemoryOrder::Acquire | MemoryOrder::SeqCst => true,
                                        _ => panic!("didnt expect order {:?} with atomic load inst", order)
                                    };
                                    // Whether to use a store exclusive release
                                    let use_release = match order {
                                        MemoryOrder::Relaxed | MemoryOrder::Consume | MemoryOrder::Acquire  => false,
                                        MemoryOrder::SeqCst => true,
                                        _ => panic!("didnt expect order {:?} with atomic load inst", order)
                                    };

                                    // Exclusive loads/stores, only supports a base address
                                    let temp_loc = emit_mem_base(self.backend.as_mut(), &resolved_loc, f_context, vm);

                                    self.finish_block();

                                    let blk_load_start = format!("{}_load_start", node.id());

                                    // load_start:
                                    self.start_block(blk_load_start.clone(), &vec![temp_loc.clone()]);


                                    // Load the value:
                                    if use_acquire {
                                        self.backend.emit_ldaxp(&res_l, &res_h, &temp_loc);
                                    } else {
                                        self.backend.emit_ldxp(&res_l, &res_h, &temp_loc);
                                    }

                                    let success = make_temporary(f_context, UINT1_TYPE.clone(), vm);

                                    // Store the value we just read back to memory
                                    if use_release {
                                        self.backend.emit_stlxp(&temp_loc, &success, &res_l, &res_h);
                                    } else {
                                        self.backend.emit_stxp(&temp_loc, &success, &res_l, &res_h);
                                    }

                                    // If the store failed, then branch back to 'load_start:'
                                    self.backend.emit_cbnz(&success, blk_load_start.clone())
                                }
                            }
                        } else {
                            unimplemented!();
                        }
                    }

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

                        let resolved_loc = self.emit_node_addr_to_value(loc_op, f_content, f_context, vm);

                        if self.match_ireg(val_op) || self.match_fpreg(val_op) {
                            // 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)
                            };

                            let val = self.emit_reg(val_op, f_content, f_context, vm);

                            if use_release {
                                // Can only have a base for a STLR
                                let temp_loc = emit_mem_base(self.backend.as_mut(), &resolved_loc, f_context, vm);

                                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)
                                };
                            } else {
                                let temp_loc = emit_mem(self.backend.as_mut(), &resolved_loc, get_type_alignment(&val.ty, vm), f_context, vm);
                                self.backend.emit_str(&temp_loc, &val);
                            }
                        } else if self.match_ireg_ex(val_op) {
                            let (val_l, val_h) = self.emit_ireg_ex(val_op, f_content, f_context, vm);

                            match order {
                                MemoryOrder::NotAtomic => {
                                    let temp_loc = emit_mem(self.backend.as_mut(), &resolved_loc, 16, f_context, vm);
                                    self.backend.emit_stp(&temp_loc, &val_l, &val_h);
                                }

                                // Aarch64 dosn't have a store release pair instruction
                                // So instead we have to write a loop using load/store exclusive pairs
                                _ => {
                                    // Whether to use a load exclusive acquire
                                    let use_acquire = match order {
                                        MemoryOrder::Relaxed | MemoryOrder::Release => false,
                                        MemoryOrder::SeqCst => true,
                                        _ => panic!("didnt expect order {:?} with atomic store inst", order)
                                    };
                                    // Whether to use a store exclusive release
                                    let use_release = match order {
                                        MemoryOrder::Relaxed  => false,
                                        MemoryOrder::Release | MemoryOrder::SeqCst => true,
                                        _ => panic!("didnt expect order {:?} with atomic store inst", order)
                                    };

                                    // Exclusive loads/stores, only supports a base address
                                    let temp_loc = emit_mem_base(self.backend.as_mut(), &resolved_loc, f_context, vm);

                                    self.finish_block();

                                    let blk_store_start = format!("{}_store_start", node.id());

                                    // store_start:
                                    self.start_block(blk_store_start.clone(), &vec![temp_loc.clone()]);

                                    let success = make_temporary(f_context, UINT1_TYPE.clone(), vm);
                                    let discard_reg = cast_value(&success, &UINT64_TYPE);
                                    // Load a value (discard it)
                                    if use_acquire {
                                        self.backend.emit_ldaxp(&XZR, &discard_reg, &temp_loc);
                                    } else {
                                        self.backend.emit_ldxp(&XZR, &discard_reg, &temp_loc);
                                    }

                                    // Store the value
                                    if use_release {
                                        self.backend.emit_stlxp(&temp_loc, &success, &val_l, &val_h);
                                    } else {
                                        self.backend.emit_stxp(&temp_loc, &success, &val_l, &val_h);
                                    }

                                    // If the store failed, then branch back to 'store_start:'
                                    self.backend.emit_cbnz(&success, blk_store_start.clone())
                                }
                            }
                        } else {
                            unimplemented!();
                        }

                    }

                    Instruction_::CmpXchg{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 ref ops = inst.ops;
                        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();

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

                        if use_acquire {
                            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)
                            };
                        } else {
                            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)
                            };
                        }

                        if is_int_reg(&expected) {
                            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 {
                            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)
                            };
                        } else {
                            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)
                            };
                        }

                        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();

                        // cmpxchg_failed:
                        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();

                        // cmpxchg_succeded:
                        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);
                    }
                    Instruction_::GetIRef(_)
                    | Instruction_::GetFieldIRef { .. }
                    | Instruction_::GetElementIRef{..}
                    | Instruction_::GetVarPartIRef { .. }
                    | Instruction_::ShiftIRef { .. } => {
                        trace!("instsel on GET/FIELD/VARPARTIREF, SHIFTIREF");
                        let mem_addr = self.emit_get_mem_from_inst(node, f_content, f_context, vm);
                        let tmp_res = self.get_result_value(node, 0);
                        emit_calculate_address(self.backend.as_mut(), &tmp_res, &mem_addr, f_context, vm);
                    }

                    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");
                        }
                    }

                    // 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)
                    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
                        let tl = self.emit_get_threadlocal(f_context, vm);
                        self.backend.emit_add_imm(&tl, &tl, *thread::NATIVE_SP_LOC_OFFSET as u16, false);

                        self.emit_runtime_entry(&entrypoints::SWAP_BACK_TO_NATIVE_STACK, vec![tl.clone()], None, Some(node), f_context, vm);
                    }


                    Instruction_::CommonInst_GetThreadLocal => {
                        trace!("instsel on GETTHREADLOCAL");
                        // get thread local
                        let tl = self.emit_get_threadlocal(f_context, vm);

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

                        // load [tl + USER_TLS_OFFSET] -> tmp_res
                        emit_load_base_offset(self.backend.as_mut(), &tmp_res, &tl, *thread::USER_TLS_OFFSET as i64, f_context, vm);
                    }


                    Instruction_::CommonInst_SetThreadLocal(op) => {
                        trace!("instsel on SETTHREADLOCAL");
                        let ref ops = inst.ops;
                        let ref op = ops[op];

                        debug_assert!(self.match_ireg(op));

                        let tmp_op = self.emit_ireg(op, f_content, f_context, vm);

                        // get thread local
                        let tl = self.emit_get_threadlocal(f_context, vm);

                        // store tmp_op -> [tl + USER_TLS_OFFSTE]
                        emit_store_base_offset(self.backend.as_mut(), &tl, *thread::USER_TLS_OFFSET as i64, &tmp_op, f_context, vm);
                    }

                    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 ref ops = inst.ops;
                            let ref op = ops[op];

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

                            self.emit_move_node_to_value(&tmp_res, op, f_content, f_context, vm);
                        } 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 ref ops = inst.ops;
                        let ref op = ops[op];

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

                        self.emit_move_node_to_value(&tmp_res, op, f_content, f_context, vm);
                    }

                    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;

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

                        let tmp_allocator = self.emit_get_allocator(f_context, vm);
                        let tmp_res = self.emit_alloc_sequence(tmp_allocator.clone(), const_size, ty_align, node, f_context, vm);

                        // ASM: call muentry_init_object(%allocator, %tmp_res, %encode)
                        let encode = make_value_int_const(mm::get_gc_type_encode(ty_info.gc_type.id), vm);
                        self.emit_runtime_entry(
                            &entrypoints::INIT_OBJ,
                            vec![tmp_allocator.clone(), tmp_res.clone(), encode],
                            None,
                            Some(node), 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 ref ops = inst.ops;
                            let ref var_len = ops[var_len];

                            if match_node_int_imm(var_len) {
                                let var_len = node_imm_to_u64(var_len);
                                let actual_size = fix_part_size + var_ty_size * (var_len as usize);
                                (
                                    make_value_int_const(actual_size as u64, vm),
                                    make_value_int_const(var_len as u64, vm)
                                )
                            } else {
                                let tmp_actual_size = make_temporary(f_context, UINT64_TYPE.clone(), vm);
                                let tmp_var_len = self.emit_ireg(var_len, f_content, f_context, vm);

                                // tmp_actual_size = tmp_var_len*var_ty_size
                                emit_mul_u64(self.backend.as_mut(), &tmp_actual_size, &tmp_var_len, f_context, vm, var_ty_size as u64);
                                // tmp_actual_size = tmp_var_len*var_ty_size + fix_part_size
                                emit_add_u64(self.backend.as_mut(), &tmp_actual_size, &tmp_actual_size, f_context, vm, fix_part_size as u64);
                                (tmp_actual_size, tmp_var_len)
                            }
                        };

                        let tmp_allocator = self.emit_get_allocator(f_context, vm);
                        let tmp_res = self.emit_alloc_sequence(tmp_allocator.clone(), actual_size, ty_align, node, f_context, vm);

                        // ASM: call muentry_init_object(%allocator, %tmp_res, %encode)