inst_sel.rs

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::ValueLocation;
use runtime::thread;
use runtime::entrypoints;
use runtime::entrypoints::RuntimeEntrypoint;

use compiler::CompilerPass;
use compiler::backend;
use compiler::backend::PROLOGUE_BLOCK_NAME;
use compiler::backend::x86_64;
use compiler::backend::x86_64::CodeGenerator;
use compiler::backend::x86_64::ASMCodeGen;
use compiler::machine_code::CompiledFunction;
use compiler::frame::Frame;

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

lazy_static! {
    pub static ref LONG_4_TYPE : P<MuType> = P(
        MuType::new(new_internal_id(), MuType_::mustruct(Mu("long_4"), vec![UINT32_TYPE.clone(); 4]))
    );

    pub static ref UITOFP_C0 : P<Value> = P(Value{
        hdr: MuEntityHeader::named(new_internal_id(), Mu("UITOFP_C0")),
        ty : LONG_4_TYPE.clone(),
        v  : Value_::Constant(Constant::List(vec![
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT32_TYPE.clone(),
                v : Value_::Constant(Constant::Int(1127219200u64))
            }),
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT32_TYPE.clone(),
                v : Value_::Constant(Constant::Int(1160773632u64))
            }),
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT32_TYPE.clone(),
                v : Value_::Constant(Constant::Int(0u64))
            }),
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT32_TYPE.clone(),
                v : Value_::Constant(Constant::Int(0u64))
            })
        ]))
    });

    pub static ref QUAD_2_TYPE : P<MuType> = P(
        MuType::new(new_internal_id(), MuType_::mustruct(Mu("quad_2"), vec![UINT64_TYPE.clone(); 2]))
    );

    pub static ref UITOFP_C1 : P<Value> = P(Value{
        hdr: MuEntityHeader::named(new_internal_id(), Mu("UITOFP_C1")),
        ty : QUAD_2_TYPE.clone(),
        v  : Value_::Constant(Constant::List(vec![
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT64_TYPE.clone(),
                v : Value_::Constant(Constant::Int(4841369599423283200u64))
            }),
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT64_TYPE.clone(),
                v : Value_::Constant(Constant::Int(4985484787499139072u64))
            })
        ]))
    });

    pub static ref FPTOUI_C : P<Value> = P(Value{
        hdr: MuEntityHeader::named(new_internal_id(), Mu("FPTOUI_C")),
        ty : UINT64_TYPE.clone(),
        v  : Value_::Constant(Constant::Int(4890909195324358656u64))
    });
}

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>>
}

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

    #[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
    #[allow(unused_variables)]
    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 {
                    Instruction_::Branch2{cond, ref true_dest, ref false_dest, true_prob} => {
                        trace!("instsel on BRANCH2");
                        // 'branch_if_true' == true, we emit cjmp the same as CmpOp  (je  for EQ, jne for NE)
                        // 'branch_if_true' == false, we emit opposite cjmp as CmpOp (jne for EQ, je  for NE)
                        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];
                        
                        if self.match_cmp_res(cond) {
                            trace!("emit cmp_res-branch2");
                            match self.emit_cmp_res(cond, f_content, f_context, vm) {
                                op::CmpOp::EQ => {
                                    if branch_if_true {
                                        self.backend.emit_je(branch_target);
                                    } else {
                                        self.backend.emit_jne(branch_target);
                                    }
                                },
                                op::CmpOp::NE => {
                                    if branch_if_true {
                                        self.backend.emit_jne(branch_target);
                                    } else {
                                        self.backend.emit_je(branch_target);
                                    }
                                },
                                op::CmpOp::UGE => {
                                    if branch_if_true {
                                        self.backend.emit_jae(branch_target);
                                    } else {
                                        self.backend.emit_jb(branch_target);
                                    }
                                },
                                op::CmpOp::UGT => {
                                    if branch_if_true {
                                        self.backend.emit_ja(branch_target);
                                    } else {
                                        self.backend.emit_jbe(branch_target);
                                    }
                                },
                                op::CmpOp::ULE => {
                                    if branch_if_true {
                                        self.backend.emit_jbe(branch_target);
                                    } else {
                                        self.backend.emit_ja(branch_target);
                                    }
                                },
                                op::CmpOp::ULT => {
                                    if branch_if_true {
                                        self.backend.emit_jb(branch_target);
                                    } else {
                                        self.backend.emit_jae(branch_target);
                                    }
                                },
                                op::CmpOp::SGE => {
                                    if branch_if_true {
                                        self.backend.emit_jge(branch_target);
                                    } else {
                                        self.backend.emit_jl(branch_target);
                                    }
                                },
                                op::CmpOp::SGT => {
                                    if branch_if_true {
                                        self.backend.emit_jg(branch_target);
                                    } else {
                                        self.backend.emit_jle(branch_target);
                                    }
                                },
                                op::CmpOp::SLE => {
                                    if branch_if_true {
                                        self.backend.emit_jle(branch_target);
                                    } else {
                                        self.backend.emit_jg(branch_target);
                                    }
                                },
                                op::CmpOp::SLT => {
                                    if branch_if_true {
                                        self.backend.emit_jl(branch_target);
                                    } else {
                                        self.backend.emit_jge(branch_target);
                                    }
                                },

                                // floating point

                                op::CmpOp::FOEQ | op::CmpOp::FUEQ => {
                                    if branch_if_true {
                                        self.backend.emit_je(branch_target);
                                    } else {
                                        self.backend.emit_jne(branch_target);
                                    }
                                },
                                op::CmpOp::FONE | op::CmpOp::FUNE => {
                                    if branch_if_true {
                                        self.backend.emit_jne(branch_target);
                                    } else {
                                        self.backend.emit_je(branch_target);
                                    }
                                },
                                op::CmpOp::FOGT | op::CmpOp::FUGT => {
                                    if branch_if_true {
                                        self.backend.emit_ja(branch_target);
                                    } else {
                                        self.backend.emit_jbe(branch_target);
                                    }
                                },
                                op::CmpOp::FOGE | op::CmpOp::FUGE => {
                                    if branch_if_true {
                                        self.backend.emit_jae(branch_target);
                                    } else {
                                        self.backend.emit_jb(branch_target);
                                    }
                                },
                                op::CmpOp::FOLT | op::CmpOp::FULT => {
                                    if branch_if_true {
                                        self.backend.emit_jb(branch_target);
                                    } else {
                                        self.backend.emit_jae(branch_target);
                                    }
                                },
                                op::CmpOp::FOLE | op::CmpOp::FULE => {
                                    if branch_if_true {
                                        self.backend.emit_jbe(branch_target);
                                    } else {
                                        self.backend.emit_ja(branch_target);
                                    }
                                },

                                _ => unimplemented!()
                            }
                        } else if self.match_ireg(cond) {
                            trace!("emit ireg-branch2");
                            
                            let cond_reg = self.emit_ireg(cond, f_content, f_context, vm);
                            
                            // emit: cmp cond_reg 1
                            self.backend.emit_cmp_imm_r(1, &cond_reg);
                            // emit: je #branch_dest
                            self.backend.emit_je(branch_target);
                        } else {
                            unimplemented!();
                        }
                    },

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

                        if self.match_ireg(true_val) {
                            // moving integers/pointers
                            let tmp_res   = self.get_result_value(node);

                            // generate compare
                            let cmpop = if self.match_cmp_res(cond) {
                                self.emit_cmp_res(cond, f_content, f_context, vm)
                            } else if self.match_ireg(cond) {
                                let tmp_cond = self.emit_ireg(cond, f_content, f_context, vm);
                                // emit: cmp cond_reg 1
                                self.backend.emit_cmp_imm_r(1, &tmp_cond);

                                EQ
                            } else {
                                panic!("expected ireg, found {}", cond)
                            };

                            // use cmov for 16/32/64bit integeer
                            // use jcc  for 8 bit
                            match tmp_res.ty.get_int_length() {
                                // cmov
                                Some(len) if len > 8 => {
                                    let tmp_true  = self.emit_ireg(true_val, f_content, f_context, vm);
                                    let tmp_false = self.emit_ireg(false_val, f_content, f_context, vm);

                                    // mov tmp_false -> tmp_res
                                    self.backend.emit_mov_r_r(&tmp_res, &tmp_false);

                                    match cmpop {
                                        EQ  => self.backend.emit_cmove_r_r (&tmp_res, &tmp_true),
                                        NE  => self.backend.emit_cmovne_r_r(&tmp_res, &tmp_true),
                                        SGE => self.backend.emit_cmovge_r_r(&tmp_res, &tmp_true),
                                        SGT => self.backend.emit_cmovg_r_r (&tmp_res, &tmp_true),
                                        SLE => self.backend.emit_cmovle_r_r(&tmp_res, &tmp_true),
                                        SLT => self.backend.emit_cmovl_r_r (&tmp_res, &tmp_true),
                                        UGE => self.backend.emit_cmovae_r_r(&tmp_res, &tmp_true),
                                        UGT => self.backend.emit_cmova_r_r (&tmp_res, &tmp_true),
                                        ULE => self.backend.emit_cmovbe_r_r(&tmp_res, &tmp_true),
                                        ULT => self.backend.emit_cmovb_r_r (&tmp_res, &tmp_true),

                                        FOEQ | FUEQ => self.backend.emit_cmove_r_r (&tmp_res, &tmp_true),
                                        FONE | FUNE => self.backend.emit_cmovne_r_r(&tmp_res, &tmp_true),
                                        FOGT | FUGT => self.backend.emit_cmova_r_r (&tmp_res, &tmp_true),
                                        FOGE | FUGE => self.backend.emit_cmovae_r_r(&tmp_res, &tmp_true),
                                        FOLT | FULT => self.backend.emit_cmovb_r_r (&tmp_res, &tmp_true),
                                        FOLE | FULE => self.backend.emit_cmovbe_r_r(&tmp_res, &tmp_true),

                                        _ => unimplemented!()
                                    }
                                }
                                // jcc
                                _ => {
                                    let blk_true  = format!("{}_select_true", node.id());
                                    let blk_false = format!("{}_select_false", node.id());
                                    let blk_end   = format!("{}_select_end", node.id());

                                    // jump to blk_true if true
                                    match cmpop {
                                        EQ  => self.backend.emit_je (blk_true.clone()),
                                        NE  => self.backend.emit_jne(blk_true.clone()),
                                        SGE => self.backend.emit_jge(blk_true.clone()),
                                        SGT => self.backend.emit_jg (blk_true.clone()),
                                        SLE => self.backend.emit_jle(blk_true.clone()),
                                        SLT => self.backend.emit_jl (blk_true.clone()),
                                        UGE => self.backend.emit_jae(blk_true.clone()),
                                        UGT => self.backend.emit_ja (blk_true.clone()),
                                        ULE => self.backend.emit_jbe(blk_true.clone()),
                                        ULT => self.backend.emit_jb (blk_true.clone()),

                                        FOEQ | FUEQ => self.backend.emit_je (blk_true.clone()),
                                        FONE | FUNE => self.backend.emit_jne(blk_true.clone()),
                                        FOGT | FUGT => self.backend.emit_ja (blk_true.clone()),
                                        FOGE | FUGE => self.backend.emit_jae(blk_true.clone()),
                                        FOLT | FULT => self.backend.emit_jb (blk_true.clone()),
                                        FOLE | FULE => self.backend.emit_jbe(blk_true.clone()),

                                        _ => unimplemented!()
                                    }

                                    // finishing current block
                                    let cur_block = self.current_block.as_ref().unwrap().clone();
                                    self.backend.end_block(cur_block.clone());

                                    // blk_false:
                                    self.current_block = Some(blk_false.clone());
                                    self.backend.start_block(blk_false.clone());

                                    // mov false result here
                                    self.emit_move_node_to_value(&tmp_res, &false_val, f_content, f_context, vm);

                                    // jmp to end
                                    self.backend.emit_jmp(blk_end.clone());

                                    // finishing current block
                                    let cur_block = self.current_block.as_ref().unwrap().clone();
                                    self.backend.end_block(cur_block.clone());

                                    // blk_true:
                                    self.current_block = Some(blk_true.clone());
                                    self.backend.start_block(blk_true.clone());
                                    // mov true value -> result
                                    self.emit_move_node_to_value(&tmp_res, &true_val, f_content, f_context, vm);

                                    self.backend.end_block(blk_true.clone());

                                    // blk_end:
                                    self.backend.start_block(blk_end.clone());
                                    self.current_block = Some(blk_end.clone());
                                }
                            }
                        } 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];

                        let tmp_res = self.get_result_value(node);
                        
                        debug_assert!(tmp_res.ty.get_int_length().is_some());
                        debug_assert!(tmp_res.ty.get_int_length().unwrap() == 1);

                        // set byte to result
                        match self.emit_cmp_res(node, f_content, f_context, vm) {
                            EQ  => self.backend.emit_sete_r (&tmp_res),
                            NE  => self.backend.emit_setne_r(&tmp_res),
                            SGE => self.backend.emit_setge_r(&tmp_res),
                            SGT => self.backend.emit_setg_r (&tmp_res),
                            SLE => self.backend.emit_setle_r(&tmp_res),
                            SLT => self.backend.emit_setl_r (&tmp_res),
                            UGE => self.backend.emit_setae_r(&tmp_res),
                            UGT => self.backend.emit_seta_r (&tmp_res),
                            ULE => self.backend.emit_setbe_r(&tmp_res),
                            ULT => self.backend.emit_setb_r (&tmp_res),

                            FOEQ | FUEQ => self.backend.emit_sete_r (&tmp_res),
                            FONE | FUNE => self.backend.emit_setne_r(&tmp_res),
                            FOGT | FUGT => self.backend.emit_seta_r (&tmp_res),
                            FOGE | FUGE => self.backend.emit_setae_r(&tmp_res),
                            FOLT | FULT => self.backend.emit_setb_r (&tmp_res),
                            FOLE | FULE => self.backend.emit_setbe_r(&tmp_res),

                            _ => unimplemented!()
                        }
                    }

                    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_jmp(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) {
                            let tmp_cond = self.emit_ireg(cond, f_content, f_context, vm);

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

                                if self.match_iimm(case_op) {
                                    let imm = self.node_iimm_to_i32(case_op);

                                    // cmp case cond
                                    self.backend.emit_cmp_imm_r(imm, &tmp_cond);
                                    // je dest
                                    self.backend.emit_je(target);
                                } else if self.match_ireg(case_op) {
                                    let tmp_case_op = self.emit_ireg(case_op, f_content, f_context, vm);

                                    // cmp case cond
                                    self.backend.emit_cmp_r_r(&tmp_case_op, &tmp_cond);
                                    // je dest
                                    self.backend.emit_je(target);
                                } else {
                                    panic!("expecting ireg cond to be either iimm or ireg: {}", cond);
                                }

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

                            // 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_jmp(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(_) => {
                        trace!("instsel on RETURN");

                        self.emit_common_epilogue(inst, f_content, f_context, vm);
                        
                        self.backend.emit_ret();
                    },
                    
                    Instruction_::BinOp(op, op1, op2) => {
                        trace!("instsel on BINOP");

                        self.emit_binop(node, inst, op, op1, op2, f_content, f_context, vm);
                    },

                    Instruction_::BinOpWithStatus(op, status, op1, op2) => {
                        trace!("instsel on BINOP_STATUS");

                        self.emit_binop(node, inst, op, op1, op2, f_content, f_context, vm);

                        let values = inst.value.as_ref().unwrap();
                        let mut status_value_index = 1;

                        // negative flag
                        if status.flag_n {
                            let tmp_status = values[status_value_index].clone();
                            status_value_index += 1;

                            self.backend.emit_sets_r8(&tmp_status);
                        }

                        // zero flag
                        if status.flag_z {
                            let tmp_status = values[status_value_index].clone();
                            status_value_index += 1;

                            self.backend.emit_setz_r8(&tmp_status);
                        }

                        // unsigned overflow
                        if status.flag_c {
                            let tmp_status = values[status_value_index].clone();
                            status_value_index += 1;

                            match op {
                                BinOp::Add | BinOp::Sub | BinOp::Mul => {
                                    self.backend.emit_setb_r8(&tmp_status);
                                }
                                _ => panic!("Only Add/Sub/Mul has #C flag")
                            }
                        }

                        // signed overflow
                        if status.flag_v {
                            let tmp_status = values[status_value_index].clone();

                            match op {
                                BinOp::Add | BinOp::Sub | BinOp::Mul => {
                                    self.backend.emit_seto_r8(&tmp_status);
                                }
                                _ => panic!("Only Add/Sub/Mul has #V flag")
                            }
                        }
                    }

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

                        match operation {
                            op::ConvOp::TRUNC => {
                                if self.match_ireg(op) {
                                    let tmp_op = self.emit_ireg(op, f_content, f_context, vm);

                                    let tmp_res = self.get_result_value(node);
                                    let dst_length = match tmp_res.ty.get_int_length() {
                                        Some(len) => len,
                                        None => panic!("dst of TRUNC is not int: {}", tmp_res)
                                    };

                                    // mov op -> result
                                    match dst_length {
                                        1  => self.backend.emit_mov_r_r(&tmp_res, unsafe {&tmp_op.as_type(UINT8_TYPE.clone())}),
                                        8  => self.backend.emit_mov_r_r(&tmp_res, unsafe {&tmp_op.as_type(UINT8_TYPE.clone())}),
                                        16 => self.backend.emit_mov_r_r(&tmp_res, unsafe {&tmp_op.as_type(UINT16_TYPE.clone())}),
                                        32 => self.backend.emit_mov_r_r(&tmp_res, unsafe {&tmp_op.as_type(UINT32_TYPE.clone())}),
                                        64 => self.backend.emit_mov_r_r(&tmp_res, unsafe {&tmp_op.as_type(UINT64_TYPE.clone())}),
                                        _  => panic!("unsupported int length: {}", dst_length)
                                    }
                                } else {
                                    panic!("unexpected op (expect ireg): {}", op);
                                }
                            }
                            op::ConvOp::ZEXT => {
                                if self.match_ireg(op) {
                                    let tmp_op = self.emit_ireg(op, f_content, f_context, vm);
                                    let tmp_res = self.get_result_value(node);

                                    // movz op -> result
                                    let from_ty_size = vm.get_backend_type_info(from_ty.id()).size;
                                    let to_ty_size   = vm.get_backend_type_info(to_ty.id()).size;

                                    if from_ty_size != to_ty_size {
                                        if from_ty_size == 4 && to_ty_size == 8 {
                                            // zero extend from 32 bits to 64 bits is a mov instruction
                                            // x86 does not have movzlq (32 to 64)

                                            // tmp_op is int32, but tmp_res is int64
                                            // we want to force a 32-to-32 mov, so high bits of the destination will be zeroed

                                            let tmp_res32 = unsafe {tmp_res.as_type(UINT32_TYPE.clone())};

                                            self.backend.emit_mov_r_r(&tmp_res32, &tmp_op);
                                        } else {
                                            self.backend.emit_movz_r_r(&tmp_res, &tmp_op);
                                        }
                                    } else {
                                        self.backend.emit_mov_r_r(&tmp_res, &tmp_op);
                                    }
                                } else {
                                    panic!("unexpected op (expect ireg): {}", op);
                                }
                            },
                            op::ConvOp::SEXT => {
                                if self.match_ireg(op) {
                                    let tmp_op = self.emit_ireg(op, f_content, f_context, vm);
                                    let tmp_res = self.get_result_value(node);

                                    // movs op -> result
                                    let from_ty_size = vm.get_backend_type_info(from_ty.id()).size;
                                    let to_ty_size   = vm.get_backend_type_info(to_ty.id()).size;

                                    if from_ty_size != to_ty_size {
                                        self.backend.emit_movs_r_r(&tmp_res, &tmp_op);
                                    } else {
                                        self.backend.emit_mov_r_r(&tmp_res, &tmp_op);
                                    }
                                } else {
                                    panic!("unexpected op (expect ireg): {}", op)
                                }
                            }
                            op::ConvOp::REFCAST | op::ConvOp::PTRCAST => {
                                // just a mov (and hopefully reg alloc will coalesce it)
                                let tmp_res = self.get_result_value(node);

                                if self.match_ireg(op) {
                                    let tmp_op = self.emit_ireg(op, f_content, f_context, vm);
                                    self.backend.emit_mov_r_r(&tmp_res, &tmp_op);
                                } else {
                                    panic!("unexpected op (expect ireg): {}", op)
                                }
                            }
                            op::ConvOp::SITOFP => {
                                let tmp_res = self.get_result_value(node);

                                if self.match_ireg(op) {
                                    let tmp_op = self.emit_ireg(op, f_content, f_context, vm);
                                    self.backend.emit_cvtsi2sd_f64_r(&tmp_res, &tmp_op);
                                } else {
                                    panic!("unexpected op (expected ireg): {}", op)
                                }
                            }
                            op::ConvOp::FPTOSI => {
                                let tmp_res = self.get_result_value(node);

                                if self.match_fpreg(op) {
                                    let tmp_op = self.emit_fpreg(op, f_content, f_context, vm);
                                    self.backend.emit_cvtsd2si_r_f64(&tmp_res, &tmp_op);
                                } else {
                                    panic!("unexpected op (expected fpreg): {}", op)
                                }
                            }
                            op::ConvOp::UITOFP => {
                                let tmp_res = self.get_result_value(node);

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

                                    let op_ty_size = vm.get_backend_type_info(tmp_op.ty.id()).size;

                                    match op_ty_size {
                                        8 => {
                                            // movd/movq op -> res
                                            self.backend.emit_mov_fpr_r64(&tmp_res, &tmp_op);

                                            // punpckldq UITOFP_C0, tmp_res -> tmp_res
                                            // (interleaving low bytes: xmm = xmm[0] mem[0] xmm[1] mem[1]
                                            let mem_c0 = self.get_mem_for_const(UITOFP_C0.clone(), vm);
                                            self.backend.emit_punpckldq_f64_mem128(&tmp_res, &mem_c0);

                                            // subpd UITOFP_C1, tmp_res -> tmp_res
                                            let mem_c1 = self.get_mem_for_const(UITOFP_C1.clone(), vm);
                                            self.backend.emit_subpd_f64_mem128(&tmp_res, &mem_c1);

                                            // haddpd tmp_res, tmp_res -> tmp_res
                                            self.backend.emit_haddpd_f64_f64(&tmp_res, &tmp_res);
                                        }
                                        4 => {
                                            let tmp = self.make_temporary(f_context, UINT64_TYPE.clone(), vm);

                                            // movl op -> tmp(32)
                                            let tmp32 = unsafe {tmp.as_type(UINT32_TYPE.clone())};
                                            self.backend.emit_mov_r_r(&tmp32, &tmp_op);

                                            // cvtsi2sd %tmp(64) -> %tmp_res
                                            self.backend.emit_cvtsi2sd_f64_r(&tmp_res, &tmp);
                                        }
                                        2 | 1 => {
                                            let tmp_op32 = unsafe {tmp_op.as_type(UINT32_TYPE.clone())};
                                            self.backend.emit_cvtsi2sd_f64_r(&tmp_res, &tmp_op32);
                                        }
                                        _ => panic!("not implemented int length {}", op_ty_size)
                                    }
                                } else {
                                    panic!("unexpected op (expected ireg): {}", op)
                                }
                            }
                            op::ConvOp::FPTOUI => {
                                let tmp_res = self.get_result_value(node);

                                let res_ty_size = vm.get_backend_type_info(tmp_res.ty.id()).size;

                                if self.match_fpreg(op) {
                                    let tmp_op = self.emit_fpreg(op, f_content, f_context, vm);

                                    match res_ty_size {
                                        8 => {
                                            let tmp1 = self.make_temporary(f_context, DOUBLE_TYPE.clone(), vm);
                                            let tmp2 = self.make_temporary(f_context, DOUBLE_TYPE.clone(), vm);

                                            // movsd FPTOUI_C -> %tmp1
                                            let mem_c = self.get_mem_for_const(FPTOUI_C.clone(), vm);
                                            self.backend.emit_movsd_f64_mem64(&tmp1, &mem_c);

                                            // movapd %tmp_op -> %tmp2
                                            self.backend.emit_movapd_f64_f64(&tmp2, &tmp_op);

                                            // subsd %tmp1, %tmp2 -> %tmp2
                                            self.backend.emit_subsd_f64_f64(&tmp2, &tmp1);

                                            // cvttsd2si %tmp2 -> %tmp_res
                                            self.backend.emit_cvttsd2si_r_f64(&tmp_res, &tmp2);

                                            let tmp_const = self.make_temporary(f_context, UINT64_TYPE.clone(), vm);
                                            // mov 0x8000000000000000 -> %tmp_const
                                            self.backend.emit_mov_r64_imm64(&tmp_const, -9223372036854775808i64);

                                            // xor %tmp_res, %tmp_const -> %tmp_const
                                            self.backend.emit_xor_r_r(&tmp_const, &tmp_res);

                                            // cvttsd2si %tmp_op -> %tmp_res
                                            self.backend.emit_cvttsd2si_r_f64(&tmp_res, &tmp_op);

                                            // ucomisd %tmp_op %tmp1
                                            self.backend.emit_ucomisd_f64_f64(&tmp1, &tmp_op);

                                            // cmovaeq %tmp_const -> %tmp_res
                                            self.backend.emit_cmovae_r_r(&tmp_res, &tmp_const);
                                        }
                                        4 => {
                                            let tmp_res64 = unsafe {tmp_res.as_type(UINT64_TYPE.clone())};

                                            // cvttsd2si %tmp_op -> %tmp_res(64)
                                            self.backend.emit_cvttsd2si_r_f64(&tmp_res64, &tmp_op);
                                        }
                                        2 | 1 => {
                                            let tmp_res32 = unsafe {tmp_res.as_type(UINT32_TYPE.clone())};

                                            // cvttsd2si %tmp_op -> %tmp_res(32)
                                            self.backend.emit_cvttsd2si_r_f64(&tmp_res32, &tmp_op);

                                            // movz %tmp_res -> %tmp_res(32)
                                            self.backend.emit_movz_r_r(&tmp_res32, &tmp_res);
                                        }
                                        _ => panic!("not implemented int length {}", res_ty_size)
                                    }
                                } else {
                                    panic!("unexpected op (expected ireg): {}", op)
                                }
                            }
                            _ => unimplemented!()
                        }
                    }
                    
                    // load on x64 generates mov inst (no matter what order is specified)
                    // https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
                    Instruction_::Load{is_ptr, order, mem_loc} => {
                        trace!("instsel on LOAD");

                        let ops = inst.ops.read().unwrap();
                        let ref loc_op = ops[mem_loc];
                        
                        // check order
                        match order {
                            MemoryOrder::Relaxed 
                            | MemoryOrder::Consume 
                            | MemoryOrder::Acquire
                            | MemoryOrder::SeqCst
                            | MemoryOrder::NotAtomic => {},
                            _ => panic!("didnt expect order {:?} with store inst", order)
                        }                        

                        let resolved_loc = self.emit_node_addr_to_value(loc_op, f_content, f_context, vm);
                        let res_temp = self.get_result_value(node);
                        
                        if self.match_ireg(node) {
                            // emit mov(GPR)
                            self.backend.emit_mov_r_mem(&res_temp, &resolved_loc);
                        } else {
                            // emit mov(FPR)
                            self.backend.emit_movsd_f64_mem64(&res_temp, &resolved_loc);
                        }
                    }
                    
                    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];
                        
                        let generate_plain_mov : bool = {
                            match order {
                                MemoryOrder::Relaxed
                                | MemoryOrder::Release
                                | MemoryOrder::NotAtomic => true,
                                MemoryOrder::SeqCst => false,
                                _ => panic!("didnt expect order {:?} with store inst", order)
                            }
                        };
                        
                        let resolved_loc = self.emit_node_addr_to_value(loc_op, f_content, f_context, vm);

                        if self.match_iimm(val_op) {
                            let val = self.node_iimm_to_i32(val_op);
                            if generate_plain_mov {
                                self.backend.emit_mov_mem_imm(&resolved_loc, val);
                            } else {
                                unimplemented!()
                            }
                        } else if self.match_ireg(val_op) {
                            let val = self.emit_ireg(val_op, f_content, f_context, vm);
                            if generate_plain_mov {
                                self.backend.emit_mov_mem_r(&resolved_loc, &val);
                            } else {
                                unimplemented!()
                            }
                        } else {
                            let val = self.emit_fpreg(val_op, f_content, f_context, vm);

                            // emit mov(FPR)
                            self.backend.emit_movsd_mem64_f64(&resolved_loc, &val);
                        }
                    }

                    // memory insts: calculate the address, then lea
                    Instruction_::GetIRef(_)
                    | Instruction_::GetFieldIRef{..}
                    | 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);

                        self.backend.emit_lea_r64(&tmp_res, &mem_addr);
                    }
                    
                    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(Some(node), f_content, f_context, vm);
                        self.backend.emit_add_r_imm(&tl, *thread::NATIVE_SP_LOC_OFFSET as i32);
                        
                        self.emit_runtime_entry(&entrypoints::SWAP_BACK_TO_NATIVE_STACK, vec![tl.clone()], None, Some(node), f_content, f_context, vm);
                    }

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

                        let tmp_res = self.get_result_value(node);

                        // load [tl + USER_TLS_OFFSET] -> tmp_res
                        self.emit_load_base_offset(&tmp_res, &tl, *thread::USER_TLS_OFFSET as i32, vm);
                    }
                    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));

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

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

                        // store tmp_op -> [tl + USER_TLS_OFFSTE]
                        self.emit_store_base_offset(&tl, *thread::USER_TLS_OFFSET as i32, &tmp_op, 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 ops = inst.ops.read().unwrap();
                            let ref op = ops[op];

                            let tmp_res = self.get_result_value(node);

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

                        let tmp_res = self.get_result_value(node);

                        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 = self.make_value_int_const(size as u64, vm);

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

                        // ASM: call muentry_init_object(%allocator, %tmp_res, %encode)
                        let encode = self.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_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];

                            if self.match_iimm(var_len) {
                                let var_len = self.node_iimm_to_i32(var_len);
                                let actual_size = fix_part_size + var_ty_size * (var_len as usize);

                                (
                                    self.make_value_int_const(actual_size as u64, vm),
                                    self.make_value_int_const(var_len as u64, vm)
                                )
                            } else {
                                let tmp_actual_size = self.make_temporary(f_context, UINT64_TYPE.clone(), vm);
                                let tmp_var_len = self.emit_ireg(var_len, f_content, f_context, vm);

                                let is_power_of_two = |x: usize| {
                                    use std::i8;

                                    let mut power_of_two = 1;
                                    let mut i: i8 = 0;
                                    while power_of_two < x && i < i8::MAX {
                                        power_of_two *= 2;
                                        i += 1;
                                    }

                                    if power_of_two == x {
                                        Some(i)
                                    } else {
                                        None
                                    }
                                };

                                match is_power_of_two(var_ty_size) {
                                    Some(shift) => {
                                        if shift != 0 {
                                            // a shift-left will get the total size of var part
                                            self.backend.emit_shl_r_imm8(&tmp_var_len, shift);
                                        }

                                        // add with fix-part size
                                        self.backend.emit_add_r_imm(&tmp_var_len, fix_part_size as i32);

                                        // mov result to tmp_actual_size
                                        self.backend.emit_mov_r_r(&tmp_actual_size, &tmp_var_len);
                                    }
                                    None => {
                                        // we need to do a multiply

                                        // mov var_ty_size -> rax
                                        self.backend.emit_mov_r_imm(&x86_64::RAX, var_ty_size as i32);

                                        // mul tmp_var_len, rax -> rdx:rax
                                        self.backend.emit_mul_r(&tmp_var_len);

                                        // add with fix-part size
                                        self.backend.emit_add_r_imm(&x86_64::RAX, fix_part_size as i32);

                                        // mov result to tmp_actual_size
                                        self.backend.emit_mov_r_r(&tmp_actual_size, &x86_64::RAX);
                                    }
                                }

                                (tmp_actual_size, tmp_var_len)
                            }
                        };

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

                        // ASM: call muentry_init_object(%allocator, %tmp_res, %encode)
                        let encode = self.make_value_int_const(mm::get_gc_type_encode(ty_info.gc_type.id), vm);
                        self.emit_runtime_entry(
                            &entrypoints::INIT_HYBRID,
                            vec![tmp_allocator.clone(), tmp_res.clone(), encode, length],
                            None,
                            Some(node), f_content, f_context, vm
                        );
                    }
                    
                    Instruction_::Throw(op_index) => {
                        trace!("instsel on THROW");

                        let ops = inst.ops.read().unwrap();
                        let ref exception_obj = ops[op_index];
                        
                        self.emit_runtime_entry(
                            &entrypoints::THROW_EXCEPTION, 
                            vec![exception_obj.clone_value()], 
                            None,
                            Some(node), f_content, f_context, vm);
                    }
    
                    _ => unimplemented!()
                } // main switch
            },
            
            TreeNode_::Value(ref p) => {
        
            }
        }
    }
    
    fn make_temporary(&mut self, f_context: &mut FunctionContext, ty: P<MuType>, vm: &VM) -> P<Value> {
        f_context.make_temporary(vm.next_id(), ty).clone_value()
    }
    
    fn make_memory_op_base_offset (&mut self, base: &P<Value>, offset: i32, ty: P<MuType>, vm: &VM) -> P<Value> {
        P(Value{
            hdr: MuEntityHeader::unnamed(vm.next_id()),
            ty: ty.clone(),
            v: Value_::Memory(MemoryLocation::Address{
                base: base.clone(),
                offset: Some(self.make_value_int_const(offset as u64, vm)),
                index: None,
                scale: None
            })
        })
    }

    fn make_memory_op_base_index(&mut self, base: &P<Value>, index: &P<Value>, scale: u8, ty: P<MuType>, vm: &VM) -> P<Value> {
        P(Value{
            hdr: MuEntityHeader::unnamed(vm.next_id()),
            ty: ty.clone(),
            v: Value_::Memory(MemoryLocation::Address{
                base: base.clone(),
                offset: None,
                index: Some(index.clone()),
                scale: Some(scale)
            })
        })
    }
    
    fn make_value_int_const (&mut self, val: u64, vm: &VM) -> P<Value> {
        P(Value{
            hdr: MuEntityHeader::unnamed(vm.next_id()),
            ty: UINT64_TYPE.clone(),
            v: Value_::Constant(Constant::Int(val))
        })
    }