inst_sel.rs 60.3 KB
Newer Older
1
use ast::ir::*;
2
use ast::ptr::*;
qinsoon's avatar
qinsoon committed
3
use ast::inst::*;
4
use ast::op;
qinsoon's avatar
qinsoon committed
5
use ast::op::OpCode;
qinsoon's avatar
qinsoon committed
6
use ast::types;
qinsoon's avatar
qinsoon committed
7
use ast::types::*;
qinsoon's avatar
qinsoon committed
8
use vm::VM;
9
use runtime::mm;
10 11 12 13
use runtime::ValueLocation;
use runtime::thread;
use runtime::entrypoints;
use runtime::entrypoints::RuntimeEntrypoint;
14 15

use compiler::CompilerPass;
16
use compiler::backend;
qinsoon's avatar
qinsoon committed
17
use compiler::backend::PROLOGUE_BLOCK_NAME;
qinsoon's avatar
qinsoon committed
18 19 20
use compiler::backend::x86_64;
use compiler::backend::x86_64::CodeGenerator;
use compiler::backend::x86_64::ASMCodeGen;
qinsoon's avatar
qinsoon committed
21 22
use compiler::machine_code::CompiledFunction;
use compiler::frame::Frame;
23

24
use std::collections::HashMap;
qinsoon's avatar
qinsoon committed
25
use std::any::Any;
26

27
pub struct InstructionSelection {
28
    name: &'static str,
29 30
    backend: Box<CodeGenerator>,
    
qinsoon's avatar
qinsoon committed
31
    current_callsite_id: usize,
qinsoon's avatar
qinsoon committed
32 33
    current_frame: Option<Frame>,
    current_block: Option<MuName>,
qinsoon's avatar
qinsoon committed
34 35 36 37 38
    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>     
39 40
}

41
impl <'a> InstructionSelection {
qinsoon's avatar
qinsoon committed
42
    #[cfg(feature = "aot")]
43
    pub fn new() -> InstructionSelection {
44 45
        InstructionSelection{
            name: "Instruction Selection (x64)",
46
            backend: Box::new(ASMCodeGen::new()),
qinsoon's avatar
qinsoon committed
47
            
qinsoon's avatar
qinsoon committed
48
            current_callsite_id: 0,
qinsoon's avatar
qinsoon committed
49 50 51
            current_frame: None,
            current_block: None,
            current_func_start: None,
qinsoon's avatar
qinsoon committed
52 53 54
            // key: block id, val: callsite that names the block as exception block
            current_exn_callsites: HashMap::new(), 
            current_exn_blocks: HashMap::new()
55 56
        }
    }
qinsoon's avatar
qinsoon committed
57 58 59 60 61

    #[cfg(feature = "jit")]
    pub fn new() -> InstructionSelection {
        unimplemented!()
    }
62 63 64 65 66 67 68
    
    // in this pass, we assume that
    // 1. all temporaries will use 64bit registers
    // 2. we do not need to backup/restore caller-saved registers
    // 3. we need to backup/restore all the callee-saved registers
    // if any of these assumption breaks, we will need to re-emit the code
    #[allow(unused_variables)]
69
    fn instruction_select(&mut self, node: &'a TreeNode, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) {
qinsoon's avatar
qinsoon committed
70 71 72
        trace!("instsel on node {}", node);
        
        match node.v {
73 74
            TreeNode_::Instruction(ref inst) => {
                match inst.v {
qinsoon's avatar
qinsoon committed
75 76 77
                    Instruction_::Branch2{cond, ref true_dest, ref false_dest, true_prob} => {
                        // move this to trace generation
                        // assert here
78 79 80 81 82
                        let (fallthrough_dest, branch_dest, branch_if_true) = {
                            if true_prob > 0.5f32 {
                                (true_dest, false_dest, false)
                            } else {
                                (false_dest, true_dest, true)
83
                            }
84
                        };
85
                        
qinsoon's avatar
qinsoon committed
86
                        let ops = inst.ops.read().unwrap();
87
                        
88 89
                        self.process_dest(&ops, fallthrough_dest, f_content, f_context, vm);
                        self.process_dest(&ops, branch_dest, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
90
                        
91
                        let branch_target = f_content.get_block(branch_dest.target).name().unwrap();
92 93 94
    
                        let ref cond = ops[cond];
                        
qinsoon's avatar
qinsoon committed
95 96
                        if self.match_cmp_res(cond) {
                            trace!("emit cmp_eq-branch2");
97
                            match self.emit_cmp_res(cond, f_content, f_context, vm) {
qinsoon's avatar
qinsoon committed
98 99 100 101 102 103 104 105 106 107
                                op::CmpOp::EQ => self.backend.emit_je(branch_target),
                                op::CmpOp::NE => self.backend.emit_jne(branch_target),
                                op::CmpOp::UGE => self.backend.emit_jae(branch_target),
                                op::CmpOp::UGT => self.backend.emit_ja(branch_target),
                                op::CmpOp::ULE => self.backend.emit_jbe(branch_target),
                                op::CmpOp::ULT => self.backend.emit_jb(branch_target),
                                op::CmpOp::SGE => self.backend.emit_jge(branch_target),
                                op::CmpOp::SGT => self.backend.emit_jg(branch_target),
                                op::CmpOp::SLE => self.backend.emit_jle(branch_target),
                                op::CmpOp::SLT => self.backend.emit_jl(branch_target),
qinsoon's avatar
qinsoon committed
108 109 110 111
                                _ => unimplemented!()
                            }
                        } else if self.match_ireg(cond) {
                            trace!("emit ireg-branch2");
112
                            
113
                            let cond_reg = self.emit_ireg(cond, f_content, f_context, vm);
114
                            
qinsoon's avatar
qinsoon committed
115 116 117
                            // emit: cmp cond_reg 1
                            self.backend.emit_cmp_r64_imm32(&cond_reg, 1);
                            // emit: je #branch_dest
qinsoon's avatar
qinsoon committed
118
                            self.backend.emit_je(branch_target);                            
qinsoon's avatar
qinsoon committed
119 120
                        } else {
                            unimplemented!();
121
                        }
122 123
                    },
                    
qinsoon's avatar
qinsoon committed
124
                    Instruction_::Branch1(ref dest) => {
qinsoon's avatar
qinsoon committed
125
                        let ops = inst.ops.read().unwrap();
126
                                            
127
                        self.process_dest(&ops, dest, f_content, f_context, vm);
128
                        
129
                        let target = f_content.get_block(dest.target).name().unwrap();
qinsoon's avatar
qinsoon committed
130
                        
qinsoon's avatar
qinsoon committed
131
                        trace!("emit branch1");
132
                        // jmp
qinsoon's avatar
qinsoon committed
133
                        self.backend.emit_jmp(target);
134 135
                    },
                    
qinsoon's avatar
qinsoon committed
136
                    Instruction_::ExprCall{ref data, is_abort} => {
qinsoon's avatar
qinsoon committed
137 138
                        if is_abort {
                            unimplemented!()
139
                        }
140
                        
qinsoon's avatar
qinsoon committed
141 142 143 144 145 146
                        self.emit_mu_call(
                            inst, // inst: &Instruction,
                            data, // calldata: &CallData,
                            None, // resumption: Option<&ResumptionData>,
                            node, // cur_node: &TreeNode, 
                            f_content, f_context, vm);                         
147 148
                    },
                    
qinsoon's avatar
qinsoon committed
149 150 151 152 153 154 155 156 157
                    Instruction_::Call{ref data, ref resume} => {
                        self.emit_mu_call(
                            inst, 
                            data, 
                            Some(resume), 
                            node, 
                            f_content, f_context, vm);
                    }
                    
158
                    Instruction_::Return(_) => {
159
                        self.emit_common_epilogue(inst, f_content, f_context, vm);
160
                        
qinsoon's avatar
qinsoon committed
161
                        self.backend.emit_ret();
162 163
                    },
                    
qinsoon's avatar
qinsoon committed
164
                    Instruction_::BinOp(op, op1, op2) => {
qinsoon's avatar
qinsoon committed
165
                        let ops = inst.ops.read().unwrap();
qinsoon's avatar
qinsoon committed
166
                        
167 168
                        match op {
                            op::BinOp::Add => {
qinsoon's avatar
qinsoon committed
169 170 171
                                if self.match_ireg(&ops[op1]) && self.match_ireg(&ops[op2]) {
                                    trace!("emit add-ireg-ireg");
                                    
172 173
                                    let reg_op1 = self.emit_ireg(&ops[op1], f_content, f_context, vm);
                                    let reg_op2 = self.emit_ireg(&ops[op2], f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
174 175 176 177 178 179 180 181 182
                                    let res_tmp = self.emit_get_result(node);
                                    
                                    // mov op1, res
                                    self.backend.emit_mov_r64_r64(&res_tmp, &reg_op1);
                                    // add op2 res
                                    self.backend.emit_add_r64_r64(&res_tmp, &reg_op2);
                                } else if self.match_ireg(&ops[op1]) && self.match_iimm(&ops[op2]) {
                                    trace!("emit add-ireg-imm");
                                    
183
                                    let reg_op1 = self.emit_ireg(&ops[op1], f_content, f_context, vm);
184
                                    let reg_op2 = self.node_iimm_to_i32(&ops[op2]);
qinsoon's avatar
qinsoon committed
185 186 187 188 189 190 191 192 193 194 195 196
                                    let res_tmp = self.emit_get_result(node);
                                    
                                    // mov op1, res
                                    self.backend.emit_mov_r64_r64(&res_tmp, &reg_op1);
                                    // add op2, res
                                    self.backend.emit_add_r64_imm32(&res_tmp, reg_op2);
                                } else if self.match_iimm(&ops[op1]) && self.match_ireg(&ops[op2]) {
                                    trace!("emit add-imm-ireg");
                                    unimplemented!();
                                } else if self.match_ireg(&ops[op1]) && self.match_mem(&ops[op2]) {
                                    trace!("emit add-ireg-mem");
                                    
197
                                    let reg_op1 = self.emit_ireg(&ops[op1], f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
198 199 200 201 202 203 204 205 206 207 208 209 210
                                    let reg_op2 = self.emit_mem(&ops[op2]);
                                    let res_tmp = self.emit_get_result(node);
                                    
                                    // mov op1, res
                                    self.backend.emit_mov_r64_r64(&res_tmp, &reg_op1);
                                    // add op2 res
                                    self.backend.emit_add_r64_mem64(&res_tmp, &reg_op2);
                                } else if self.match_mem(&ops[op1]) && self.match_ireg(&ops[op2]) {
                                    trace!("emit add-mem-ireg");
                                    unimplemented!();
                                } else {
                                    unimplemented!()
                                }
211 212
                            },
                            op::BinOp::Sub => {
qinsoon's avatar
qinsoon committed
213 214 215
                                if self.match_ireg(&ops[op1]) && self.match_ireg(&ops[op2]) {
                                    trace!("emit sub-ireg-ireg");
                                    
216 217
                                    let reg_op1 = self.emit_ireg(&ops[op1], f_content, f_context, vm);
                                    let reg_op2 = self.emit_ireg(&ops[op2], f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
218 219 220 221 222 223 224 225 226
                                    let res_tmp = self.emit_get_result(node);
                                    
                                    // mov op1, res
                                    self.backend.emit_mov_r64_r64(&res_tmp, &reg_op1);
                                    // add op2 res
                                    self.backend.emit_sub_r64_r64(&res_tmp, &reg_op2);
                                } else if self.match_ireg(&ops[op1]) && self.match_iimm(&ops[op2]) {
                                    trace!("emit sub-ireg-imm");

227
                                    let reg_op1 = self.emit_ireg(&ops[op1], f_content, f_context, vm);
228
                                    let imm_op2 = self.node_iimm_to_i32(&ops[op2]);
qinsoon's avatar
qinsoon committed
229 230 231 232 233
                                    let res_tmp = self.emit_get_result(node);
                                    
                                    // mov op1, res
                                    self.backend.emit_mov_r64_r64(&res_tmp, &reg_op1);
                                    // add op2, res
234
                                    self.backend.emit_sub_r64_imm32(&res_tmp, imm_op2);
qinsoon's avatar
qinsoon committed
235 236 237 238 239 240
                                } else if self.match_iimm(&ops[op1]) && self.match_ireg(&ops[op2]) {
                                    trace!("emit sub-imm-ireg");
                                    unimplemented!();
                                } else if self.match_ireg(&ops[op1]) && self.match_mem(&ops[op2]) {
                                    trace!("emit sub-ireg-mem");
                                    
241
                                    let reg_op1 = self.emit_ireg(&ops[op1], f_content, f_context, vm);
242
                                    let mem_op2 = self.emit_mem(&ops[op2]);
qinsoon's avatar
qinsoon committed
243 244 245 246 247
                                    let res_tmp = self.emit_get_result(node);
                                    
                                    // mov op1, res
                                    self.backend.emit_mov_r64_r64(&res_tmp, &reg_op1);
                                    // sub op2 res
248
                                    self.backend.emit_sub_r64_mem64(&res_tmp, &mem_op2);
qinsoon's avatar
qinsoon committed
249 250 251 252 253 254
                                } else if self.match_mem(&ops[op1]) && self.match_ireg(&ops[op2]) {
                                    trace!("emit add-mem-ireg");
                                    unimplemented!();
                                } else {
                                    unimplemented!()
                                }
255 256
                            },
                            op::BinOp::Mul => {
257 258 259 260
                                // mov op1 -> rax
                                let rax = x86_64::RAX.clone();
                                let op1 = &ops[op1];
                                if self.match_ireg(op1) {
261
                                    let reg_op1 = self.emit_ireg(op1, f_content, f_context, vm);
262 263 264
                                    
                                    self.backend.emit_mov_r64_r64(&rax, &reg_op1);
                                } else if self.match_iimm(op1) {
265
                                    let imm_op1 = self.node_iimm_to_i32(op1);
266 267 268 269 270 271 272 273 274 275 276 277 278
                                    
                                    self.backend.emit_mov_r64_imm32(&rax, imm_op1);
                                } else if self.match_mem(op1) {
                                    let mem_op1 = self.emit_mem(op1);
                                    
                                    self.backend.emit_mov_r64_mem64(&rax, &mem_op1);
                                } else {
                                    unimplemented!();
                                }
                                
                                // mul op2 -> rax
                                let op2 = &ops[op2];
                                if self.match_ireg(op2) {
279
                                    let reg_op2 = self.emit_ireg(op2, f_content, f_context, vm);
280 281 282
                                    
                                    self.backend.emit_mul_r64(&reg_op2);
                                } else if self.match_iimm(op2) {
283
                                    let imm_op2 = self.node_iimm_to_i32(op2);
284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301
                                    
                                    // put imm in a temporary
                                    // here we use result reg as temporary
                                    let res_tmp = self.emit_get_result(node);
                                    self.backend.emit_mov_r64_imm32(&res_tmp, imm_op2);
                                    
                                    self.backend.emit_mul_r64(&res_tmp);
                                } else if self.match_mem(op2) {
                                    let mem_op2 = self.emit_mem(op2);
                                    
                                    self.backend.emit_mul_mem64(&mem_op2);
                                } else {
                                    unimplemented!();
                                }
                                
                                // mov rax -> result
                                let res_tmp = self.emit_get_result(node);
                                self.backend.emit_mov_r64_r64(&res_tmp, &rax);
302 303 304
                            },
                            
                            _ => unimplemented!()
305 306
                        }
                    }
307
                    
308 309
                    // load on x64 generates mov inst (no matter what order is specified)
                    // https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html
310
                    Instruction_::Load{is_ptr, order, mem_loc} => {
qinsoon's avatar
qinsoon committed
311
                        let ops = inst.ops.read().unwrap();
312
                        let ref loc_op = ops[mem_loc];
313 314 315 316 317 318 319 320 321
                        
                        // check order
                        match order {
                            MemoryOrder::Relaxed 
                            | MemoryOrder::Consume 
                            | MemoryOrder::Acquire
                            | MemoryOrder::SeqCst => {},
                            _ => panic!("didnt expect order {:?} with store inst", order)
                        }                        
322

323
                        let resolved_loc = self.node_mem_to_value(loc_op, vm);
324 325 326 327
                        let res_temp = self.emit_get_result(node);
                        
                        if self.match_ireg(node) {
                            // emit mov(GPR)
328 329 330 331 332 333 334 335
                            self.backend.emit_mov_r64_mem64(&res_temp, &resolved_loc);
                        } else {
                            // emit mov(FPR)
                            unimplemented!()
                        }
                    }
                    
                    Instruction_::Store{is_ptr, order, mem_loc, value} => {
qinsoon's avatar
qinsoon committed
336
                        let ops = inst.ops.read().unwrap();
337 338 339 340 341 342 343 344 345 346 347
                        let ref loc_op = ops[mem_loc];
                        let ref val_op = ops[value];
                        
                        let generate_plain_mov : bool = {
                            match order {
                                MemoryOrder::Relaxed | MemoryOrder::Release => true,
                                MemoryOrder::SeqCst => false,
                                _ => panic!("didnt expect order {:?} with store inst", order)
                            }
                        };
                        
348
                        let resolved_loc = self.node_mem_to_value(loc_op, vm);
349 350
                        
                        if self.match_ireg(val_op) {
351
                            let val = self.emit_ireg(val_op, f_content, f_context, vm);
352 353 354 355 356 357
                            if generate_plain_mov {
                                self.backend.emit_mov_mem64_r64(&resolved_loc, &val);
                            } else {
                                unimplemented!()
                            }
                        } else if self.match_iimm(val_op) {
358
                            let val = self.node_iimm_to_i32(val_op);
359 360 361 362 363
                            if generate_plain_mov {
                                self.backend.emit_mov_mem64_imm32(&resolved_loc, val);
                            } else {
                                unimplemented!()
                            }
364 365 366 367 368
                        } else {
                            // emit mov(FPR)
                            unimplemented!()
                        }
                    }
369
                    
370 371 372 373 374 375
                    Instruction_::GetIRef(op_index) => {
                        let ops = inst.ops.read().unwrap();
                        
                        let ref op = ops[op_index];
                        let res_tmp = self.emit_get_result(node);
                        
376 377 378 379 380 381
                        let hdr_size = mm::objectmodel::OBJECT_HEADER_SIZE;
                        if hdr_size == 0 {
                            self.emit_general_move(&op, &res_tmp, f_content, f_context, vm);
                        } else {
                            self.emit_lea_base_offset(&res_tmp, &op.clone_value(), hdr_size as i32, vm);
                        }
382 383
                    }
                    
384
                    Instruction_::ThreadExit => {
385
                        // emit a call to swap_back_to_native_stack(sp_loc: Address)
386 387
                        
                        // get thread local and add offset to get sp_loc
qinsoon's avatar
qinsoon committed
388
                        let tl = self.emit_get_threadlocal(Some(node), f_content, f_context, vm);
389
                        self.backend.emit_add_r64_imm32(&tl, *thread::NATIVE_SP_LOC_OFFSET as i32);
390
                        
qinsoon's avatar
qinsoon committed
391
                        self.emit_runtime_entry(&entrypoints::SWAP_BACK_TO_NATIVE_STACK, vec![tl.clone()], None, Some(node), f_content, f_context, vm);
392
                    }
393 394 395
                    
                    Instruction_::New(ref ty) => {
                        let ty_info = vm.get_backend_type_info(ty.id());
396 397
                        let ty_size = ty_info.size;
                        let ty_align= ty_info.alignment;
398
                        
399
                        if ty_size > mm::LARGE_OBJECT_THRESHOLD {
400 401 402
                            // emit large object allocation
                            unimplemented!()
                        } else {
403 404 405
                            // emit immix allocation fast path
                            
                            // ASM: %tl = get_thread_local()
qinsoon's avatar
qinsoon committed
406
                            let tmp_tl = self.emit_get_threadlocal(Some(node), f_content, f_context, vm);
407 408 409
                            
                            // ASM: mov [%tl + allocator_offset + cursor_offset] -> %cursor
                            let cursor_offset = *thread::ALLOCATOR_OFFSET + *mm::ALLOCATOR_CURSOR_OFFSET;
qinsoon's avatar
qinsoon committed
410
                            let tmp_cursor = self.make_temporary(f_context, ADDRESS_TYPE.clone(), vm);
411
                            self.emit_load_base_offset(&tmp_cursor, &tmp_tl, cursor_offset as i32, vm);
412 413 414
                            
                            // alignup cursor (cursor + align - 1 & !(align - 1))
                            // ASM: lea align-1(%cursor) -> %start
415
                            let align = ty_info.alignment as i32;
qinsoon's avatar
qinsoon committed
416
                            let tmp_start = self.make_temporary(f_context, ADDRESS_TYPE.clone(), vm);
417
                            self.emit_lea_base_offset(&tmp_start, &tmp_cursor, align - 1, vm);
418
                            // ASM: and %start, !(align-1) -> %start
419
                            self.backend.emit_and_r64_imm32(&tmp_start, !(align - 1));
420 421 422
                            
                            // bump cursor
                            // ASM: lea size(%start) -> %end
qinsoon's avatar
qinsoon committed
423
                            let tmp_end = self.make_temporary(f_context, ADDRESS_TYPE.clone(), vm);
424
                            self.emit_lea_base_offset(&tmp_end, &tmp_start, ty_size as i32, vm);
425 426 427 428
                            
                            // check with limit
                            // ASM: cmp %end, [%tl + allocator_offset + limit_offset]
                            let limit_offset = *thread::ALLOCATOR_OFFSET + *mm::ALLOCATOR_LIMIT_OFFSET;
qinsoon's avatar
qinsoon committed
429
                            let mem_limit = self.make_memory_op_base_offset(&tmp_tl, limit_offset as i32, ADDRESS_TYPE.clone(), vm);
430 431 432
                            self.backend.emit_cmp_r64_mem64(&tmp_end, &mem_limit);
                            
                            // branch to slow path if end > limit
433
                            // ASM: jl alloc_slow
434
                            let slowpath = format!("{}_allocslow", node.id());
435
                            self.backend.emit_jl(slowpath.clone());
436 437
                            
                            // update cursor
438 439
                            // ASM: mov %end -> [%tl + allocator_offset + cursor_offset]
                            self.emit_store_base_offset(&tmp_tl, cursor_offset as i32, &tmp_end, vm);
440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458
                            
                            // put start as result
                            // ASM: mov %start -> %result
                            let tmp_res = self.emit_get_result(node);
                            self.backend.emit_mov_r64_r64(&tmp_res, &tmp_start);
                            
                            // ASM jmp alloc_end
                            let allocend = format!("{}_allocend", node.id());
                            self.backend.emit_jmp(allocend.clone());
                            
                            // finishing current block
                            self.backend.end_block(self.current_block.as_ref().unwrap().clone());
                            
                            // alloc_slow: 
                            // call alloc_slow(size, align) -> %ret
                            // new block (no livein)
                            self.current_block = Some(slowpath.clone());
                            self.backend.start_block(slowpath.clone());
                            self.backend.set_block_livein(slowpath.clone(), &vec![]); 
459 460 461

                            // arg1: allocator address                            
                            let allocator_offset = *thread::ALLOCATOR_OFFSET;
qinsoon's avatar
qinsoon committed
462
                            let tmp_allocator = self.make_temporary(f_context, ADDRESS_TYPE.clone(), vm);
463 464
                            self.emit_lea_base_offset(&tmp_allocator, &tmp_tl, allocator_offset as i32, vm);
                            // arg2: size                            
465
                            let const_size = self.make_value_int_const(ty_size as u64, vm);
466
                            // arg3: align
467
                            let const_align= self.make_value_int_const(ty_align as u64, vm);
468
                            
469 470
                            let rets = self.emit_runtime_entry(
                                &entrypoints::ALLOC_SLOW,
471
                                vec![tmp_allocator, const_size, const_align],
472 473 474
                                Some(vec![
                                    tmp_res.clone()
                                ]),
qinsoon's avatar
qinsoon committed
475
                                Some(node), f_content, f_context, vm
476 477
                            );
                            
478
                            // end block (no liveout other than result)
479 480 481 482 483 484
                            self.backend.end_block(slowpath.clone());
                            self.backend.set_block_liveout(slowpath.clone(), &vec![tmp_res.clone()]);
                            
                            // block: alloc_end
                            self.backend.start_block(allocend.clone());
                            self.current_block = Some(allocend.clone());
485 486
                        }
                    }
qinsoon's avatar
qinsoon committed
487 488 489 490 491 492 493 494 495
                    
                    Instruction_::Throw(op_index) => {
                        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,
qinsoon's avatar
qinsoon committed
496
                            Some(node), f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
497
                    }
498 499 500 501 502 503
    
                    _ => unimplemented!()
                } // main switch
            },
            
            TreeNode_::Value(ref p) => {
504
        
505 506 507 508
            }
        }
    }
    
509 510 511 512
    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()
    }
    
513
    fn make_memory_op_base_offset (&mut self, base: &P<Value>, offset: i32, ty: P<MuType>, vm: &VM) -> P<Value> {
514 515 516 517 518 519 520 521 522 523 524 525 526 527 528
        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_value_int_const (&mut self, val: u64, vm: &VM) -> P<Value> {
        P(Value{
            hdr: MuEntityHeader::unnamed(vm.next_id()),
qinsoon's avatar
qinsoon committed
529
            ty: UINT64_TYPE.clone(),
530 531 532 533
            v: Value_::Constant(Constant::Int(val))
        })
    } 
    
534
    fn emit_load_base_offset (&mut self, dest: &P<Value>, base: &P<Value>, offset: i32, vm: &VM) {
535 536 537 538 539
        let mem = self.make_memory_op_base_offset(base, offset, dest.ty.clone(), vm);
        
        self.backend.emit_mov_r64_mem64(dest, &mem);
    }
    
540
    fn emit_store_base_offset (&mut self, base: &P<Value>, offset: i32, src: &P<Value>, vm: &VM) {
541 542 543 544 545
        let mem = self.make_memory_op_base_offset(base, offset, src.ty.clone(), vm);
        
        self.backend.emit_mov_mem64_r64(&mem, src);
    }
    
546
    fn emit_lea_base_offset (&mut self, dest: &P<Value>, base: &P<Value>, offset: i32, vm: &VM) {
qinsoon's avatar
qinsoon committed
547
        let mem = self.make_memory_op_base_offset(base, offset, ADDRESS_TYPE.clone(), vm);
548 549 550 551
        
        self.backend.emit_lea_r64(dest, &mem);
    }
    
qinsoon's avatar
qinsoon committed
552 553
    fn emit_get_threadlocal (
        &mut self, 
qinsoon's avatar
qinsoon committed
554
        cur_node: Option<&TreeNode>,
qinsoon's avatar
qinsoon committed
555 556 557 558
        f_content: &FunctionContent, 
        f_context: &mut FunctionContext, 
        vm: &VM) -> P<Value> {
        let mut rets = self.emit_runtime_entry(&entrypoints::GET_THREAD_LOCAL, vec![], None, cur_node, f_content, f_context, vm);
559 560 561 562
        
        rets.pop().unwrap()
    }
    
563 564 565 566
    // ret: Option<Vec<P<Value>>
    // if ret is Some, return values will put stored in given temporaries
    // otherwise create temporaries
    // always returns result temporaries (given or created)
qinsoon's avatar
qinsoon committed
567 568 569 570 571
    fn emit_runtime_entry (
        &mut self, 
        entry: &RuntimeEntrypoint, 
        args: Vec<P<Value>>, 
        rets: Option<Vec<P<Value>>>,
qinsoon's avatar
qinsoon committed
572
        cur_node: Option<&TreeNode>, 
qinsoon's avatar
qinsoon committed
573 574 575
        f_content: &FunctionContent, 
        f_context: &mut FunctionContext, 
        vm: &VM) -> Vec<P<Value>> {
576 577 578 579 580 581 582 583 584 585 586 587 588 589 590
        let sig = entry.sig.clone();
        
        let entry_name = {
            if vm.is_running() {
                unimplemented!()
            } else {
                let ref entry_loc = entry.aot;
                
                match entry_loc {
                    &ValueLocation::Relocatable(_, ref name) => name.clone(),
                    _ => panic!("expecting a relocatable value")
                }
            }
        };
        
qinsoon's avatar
qinsoon committed
591
        self.emit_c_call(entry_name, sig, args, rets, cur_node, f_content, f_context, vm)
592 593
    }
    
594 595 596 597
    // returns the stack arg offset - we will need this to collapse stack after the call
    fn emit_precall_convention(
        &mut self,
        args: &Vec<P<Value>>, 
598
        vm: &VM) -> usize {
599 600 601 602 603 604
        // if we need to save caller saved regs
        // put it here (since this is fastpath compile, we wont have them)
        
        // put args into registers if we can
        // in the meantime record args that do not fit in registers
        let mut stack_args : Vec<P<Value>> = vec![];        
605 606 607 608 609 610 611 612
        let mut gpr_arg_count = 0;
        for arg in args.iter() {
            if arg.is_int_reg() {
                if gpr_arg_count < x86_64::ARGUMENT_GPRs.len() {
                    self.backend.emit_mov_r64_r64(&x86_64::ARGUMENT_GPRs[gpr_arg_count], &arg);
                    gpr_arg_count += 1;
                } else {
                    // use stack to pass argument
613
                    stack_args.push(arg.clone());
614 615 616
                }
            } else if arg.is_int_const() {
                if x86_64::is_valid_x86_imm(arg) {                
617
                    let int_const = arg.extract_int_const() as i32;
618 619 620 621 622 623
                    
                    if gpr_arg_count < x86_64::ARGUMENT_GPRs.len() {
                        self.backend.emit_mov_r64_imm32(&x86_64::ARGUMENT_GPRs[gpr_arg_count], int_const);
                        gpr_arg_count += 1;
                    } else {
                        // use stack to pass argument
624
                        stack_args.push(arg.clone());
625 626 627 628 629
                    }
                } else {
                    // put the constant to memory
                    unimplemented!()
                }
630 631 632 633 634 635
            } else if arg.is_mem() {
                if gpr_arg_count < x86_64::ARGUMENT_GPRs.len() {
                    self.backend.emit_mov_r64_mem64(&x86_64::ARGUMENT_GPRs[gpr_arg_count], &arg);
                    gpr_arg_count += 1;
                } else {
                    // use stack to pass argument
636
                    stack_args.push(arg.clone());
637
                }
638 639 640 641 642
            } else {
                // floating point
                unimplemented!()
            }
        }
643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677

        if !stack_args.is_empty() {
            // deal with stack arg, put them on stack
            // in reverse order, i.e. push the rightmost arg first to stack
            stack_args.reverse();

            // "The end of the input argument area shall be aligned on a 16
            // (32, if __m256 is passed on stack) byte boundary." - x86 ABI
            // if we need to special align the args, we do it now
            // (then the args will be put to stack following their regular alignment)
            let stack_arg_tys = stack_args.iter().map(|x| x.ty.clone()).collect();
            let (stack_arg_size, _, stack_arg_offsets) = backend::sequetial_layout(&stack_arg_tys, vm);
            let mut stack_arg_size_with_padding = stack_arg_size;
            if stack_arg_size % 16 == 0 {
                // do not need to adjust rsp
            } else if stack_arg_size % 8 == 0 {
                // adjust rsp by -8 (push a random padding value)
                self.backend.emit_push_imm32(0x7777);
                stack_arg_size_with_padding += 8;
            } else {
                panic!("expecting stack arguments to be at least 8-byte aligned, but it has size of {}", stack_arg_size);
            }

            // now, we just put all the args on the stack
            {
                let mut index = 0;
                for arg in stack_args {
                    self.emit_store_base_offset(&x86_64::RSP, - (stack_arg_offsets[index] as i32), &arg, vm);
                    index += 1;
                }

                self.backend.emit_add_r64_imm32(&x86_64::RSP, - (stack_arg_size as i32));
            }

            stack_arg_size_with_padding
678
        } else {
679
            0
680
        }
681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716
    }

    fn emit_postcall_convention(
        &mut self,
        sig: &P<CFuncSig>,
        rets: &Option<Vec<P<Value>>>,
        precall_stack_arg_size: usize,
        f_context: &mut FunctionContext,
        vm: &VM
    ) -> Vec<P<Value>> {
        // deal with ret vals
        let mut return_vals = vec![];

        let mut gpr_ret_count = 0;
        for ret_index in 0..sig.ret_tys.len() {
            let ref ty = sig.ret_tys[ret_index];

            let ret_val = match rets {
                &Some(ref rets) => rets[ret_index].clone(),
                &None => {
                    let tmp_node = f_context.make_temporary(vm.next_id(), ty.clone());
                    tmp_node.clone_value()
                }
            };

            if ret_val.is_int_reg() {
                if gpr_ret_count < x86_64::RETURN_GPRs.len() {
                    self.backend.emit_mov_r64_r64(&ret_val, &x86_64::RETURN_GPRs[gpr_ret_count]);
                    gpr_ret_count += 1;
                } else {
                    // get return value by stack
                    unimplemented!()
                }
            } else {
                // floating point register
                unimplemented!()
717
            }
718 719

            return_vals.push(ret_val);
720
        }
721 722 723 724 725 726 727

        // remove stack_args
        if precall_stack_arg_size != 0 {
            self.backend.emit_add_r64_imm32(&x86_64::RSP, precall_stack_arg_size as i32);
        }

        return_vals
728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745
    }
    
    #[allow(unused_variables)]
    // ret: Option<Vec<P<Value>>
    // if ret is Some, return values will put stored in given temporaries
    // otherwise create temporaries
    // always returns result temporaries (given or created)
    fn emit_c_call (
        &mut self, 
        func_name: CName, 
        sig: P<CFuncSig>, 
        args: Vec<P<Value>>, 
        rets: Option<Vec<P<Value>>>,
        cur_node: Option<&TreeNode>,
        f_content: &FunctionContent, 
        f_context: &mut FunctionContext, 
        vm: &VM) -> Vec<P<Value>> 
    {
746
        let stack_arg_size = self.emit_precall_convention(&args, vm);
747
        
748 749 750 751
        // make call
        if vm.is_running() {
            unimplemented!()
        } else {
qinsoon's avatar
qinsoon committed
752
            let callsite = self.new_callsite_label(cur_node);
qinsoon's avatar
qinsoon committed
753 754 755
            self.backend.emit_call_near_rel32(callsite, func_name);
            
            // record exception block (CCall may have an exception block)
qinsoon's avatar
qinsoon committed
756 757 758 759 760
            if cur_node.is_some() {
                let cur_node = cur_node.unwrap(); 
                if cur_node.op == OpCode::CCall {
                    unimplemented!()
                }
qinsoon's avatar
qinsoon committed
761
            }
762 763
        }
        
764
        self.emit_postcall_convention(&sig, &rets, stack_arg_size, f_context, vm)
765 766
    }
    
qinsoon's avatar
qinsoon committed
767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791
    fn emit_mu_call(
        &mut self,
        inst: &Instruction,
        calldata: &CallData,
        resumption: Option<&ResumptionData>,
        cur_node: &TreeNode, 
        f_content: &FunctionContent, 
        f_context: &mut FunctionContext, 
        vm: &VM) {
        trace!("deal with pre-call convention");
        
        let ops = inst.ops.read().unwrap();
        let ref func = ops[calldata.func];
        let ref func_sig = match func.v {
            TreeNode_::Value(ref pv) => {
                let ty : &MuType = &pv.ty;
                match ty.v {
                    MuType_::FuncRef(ref sig)
                    | MuType_::UFuncPtr(ref sig) => sig,
                    _ => panic!("expected funcref/ptr type")
                }
            },
            _ => panic!("expected funcref/ptr type")
        };
        
792
        debug_assert!(func_sig.arg_tys.len() == calldata.args.len());
qinsoon's avatar
qinsoon committed
793 794
        if cfg!(debug_assertions) {
            if inst.value.is_some() {
795
                assert!(func_sig.ret_tys.len() == inst.value.as_ref().unwrap().len());
qinsoon's avatar
qinsoon committed
796
            } else {
797
                assert!(func_sig.ret_tys.len() == 0, "expect call inst's value doesnt match reg args. value: {:?}, ret args: {:?}", inst.value, func_sig.ret_tys);
qinsoon's avatar
qinsoon committed
798 799
            }
        }
800

801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816
        // prepare args (they could be instructions, we need to emit inst and get value)
        let mut arg_values = vec![];
        for arg_index in calldata.args.iter() {
            let ref arg = ops[*arg_index];

            if self.match_ireg(arg) {
                let arg = self.emit_ireg(arg, f_content, f_context, vm);
                arg_values.push(arg);
            } else if self.match_iimm(arg) {
                let arg = self.node_iimm_to_value(arg);
                arg_values.push(arg);
            } else {
                unimplemented!();
            }
        }
        let stack_arg_size = self.emit_precall_convention(&arg_values, vm);
qinsoon's avatar
qinsoon committed
817
        
818
        trace!("generating call inst");
qinsoon's avatar
qinsoon committed
819 820 821
        // check direct call or indirect
        let callsite = {
            if self.match_funcref_const(func) {
822
                let target_id = self.node_funcref_const_to_id(func);
qinsoon's avatar
qinsoon committed
823 824 825 826 827 828
                let funcs = vm.funcs().read().unwrap();
                let target = funcs.get(&target_id).unwrap().read().unwrap();
                                            
                if vm.is_running() {
                    unimplemented!()
                } else {
qinsoon's avatar
qinsoon committed
829
                    let callsite = self.new_callsite_label(Some(cur_node));
qinsoon's avatar
qinsoon committed
830 831 832 833 834
                    self.backend.emit_call_near_rel32(callsite, target.name().unwrap())
                }
            } else if self.match_ireg(func) {
                let target = self.emit_ireg(func, f_content, f_context, vm);
                
qinsoon's avatar
qinsoon committed
835
                let callsite = self.new_callsite_label(Some(cur_node));
qinsoon's avatar
qinsoon committed
836 837 838 839
                self.backend.emit_call_near_r64(callsite, &target)
            } else if self.match_mem(func) {
                let target = self.emit_mem(func);
                
qinsoon's avatar
qinsoon committed
840
                let callsite = self.new_callsite_label(Some(cur_node));
qinsoon's avatar
qinsoon committed
841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862
                self.backend.emit_call_near_mem64(callsite, &target)
            } else {
                unimplemented!()
            }
        };
        
        // record exception branch
        if resumption.is_some() {
            let ref exn_dest = resumption.as_ref().unwrap().exn_dest;
            let target_block = exn_dest.target;
            
            if self.current_exn_callsites.contains_key(&target_block) {
                let callsites = self.current_exn_callsites.get_mut(&target_block).unwrap();
                callsites.push(callsite);
            } else {
                let mut callsites = vec![];
                callsites.push(callsite);
                self.current_exn_callsites.insert(target_block, callsites);
            } 
        }
        
        // deal with ret vals
863 864 865
        self.emit_postcall_convention(
            &func_sig, &inst.value,
            stack_arg_size, f_context, vm);
qinsoon's avatar
qinsoon committed
866 867
    }
    
868 869
    #[allow(unused_variables)]
    fn process_dest(&mut self, ops: &Vec<P<TreeNode>>, dest: &Destination, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) {
870 871
        for i in 0..dest.args.len() {
            let ref dest_arg = dest.args[i];
872 873
            match dest_arg {
                &DestArg::Normal(op_index) => {
qinsoon's avatar
qinsoon committed
874
                    let ref arg = ops[op_index];
875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890
//                    match arg.op {
//                        OpCode::RegI64 
//                        | OpCode::RegFP
//                        | OpCode::IntImmI64
//                        | OpCode::FPImm => {
//                            // do nothing
//                        },
//                        _ => {
//                            trace!("nested: compute arg for branch");
//                            // nested: compute arg
//                            self.instruction_select(arg, cur_func);
//                            
//                            self.emit_get_result(arg);
//                        }
//                    }
//                    
891
                    let ref target_args = f_content.get_block(dest.target).content.as_ref().unwrap().args;
892 893
                    let ref target_arg = target_args[i];
                    
894
                    self.emit_general_move(&arg, target_arg, f_content, f_context, vm);
895 896 897 898
                },
                &DestArg::Freshbound(_) => unimplemented!()
            }
        }
qinsoon's avatar
qinsoon committed
899 900
    }
    
qinsoon's avatar
qinsoon committed
901
    fn emit_common_prologue(&mut self, args: &Vec<P<Value>>, vm: &VM) {
qinsoon's avatar
qinsoon committed
902
        let block_name = PROLOGUE_BLOCK_NAME.to_string();
903
        self.backend.start_block(block_name.clone());
904 905 906
        
        // no livein
        // liveout = entry block's args
907 908
        self.backend.set_block_livein(block_name.clone(), &vec![]);
        self.backend.set_block_liveout(block_name.clone(), args);
909
        
910 911 912
        // push rbp
        self.backend.emit_push_r64(&x86_64::RBP);
        // mov rsp -> rbp
qinsoon's avatar
qinsoon committed
913
        self.backend.emit_mov_r64_r64(&x86_64::RBP, &x86_64::RSP);
914
        
915
        // push all callee-saved registers
qinsoon's avatar
qinsoon committed
916 917
        {
            let frame = self.current_frame.as_mut().unwrap();
qinsoon's avatar
qinsoon committed
918
            let rbp = x86_64::RBP.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
919 920
            for i in 0..x86_64::CALLEE_SAVED_GPRs.len() {
                let ref reg = x86_64::CALLEE_SAVED_GPRs[i];
qinsoon's avatar
qinsoon committed
921 922 923
                // not pushing rbp (as we have done that)
                if reg.extract_ssa_id().unwrap() !=  rbp {
                    trace!("allocate frame slot for reg {}", reg);
qinsoon's avatar
qinsoon committed
924 925 926
                    self.backend.emit_push_r64(&reg);
                    frame.alloc_slot_for_callee_saved_reg(reg.clone(), vm);
                }
927
            }
928 929 930 931
        }
        
        // unload arguments
        let mut gpr_arg_count = 0;
932
        // TODO: let mut fpr_arg_count = 0;
933 934 935 936 937
        // initial stack arg is at RBP+16
        //   arg           <- RBP + 16
        //   return addr
        //   old RBP       <- RBP
        let mut stack_arg_offset : i32 = 16;
938 939 940 941 942 943 944
        for arg in args {
            if arg.is_int_reg() {
                if gpr_arg_count < x86_64::ARGUMENT_GPRs.len() {
                    self.backend.emit_mov_r64_r64(&arg, &x86_64::ARGUMENT_GPRs[gpr_arg_count]);
                    gpr_arg_count += 1;
                } else {
                    // unload from stack
945 946 947 948 949
                    self.emit_load_base_offset(&arg, &x86_64::RBP.clone(), stack_arg_offset, vm);
                    
                    // move stack_arg_offset by the size of 'arg'
                    let arg_size = vm.get_backend_type_info(arg.ty.id()).size;
                    stack_arg_offset += arg_size as i32;
950 951 952 953
                }
            } else if arg.is_fp_reg() {
                unimplemented!();
            } else {
954 955
                // args that are not fp or int (possibly struct/array/etc)
                unimplemented!();
956 957
            }
        }
958 959
        
        self.backend.end_block(block_name);
960 961
    }
    
962
    fn emit_common_epilogue(&mut self, ret_inst: &Instruction, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) {
963 964
        // epilogue is not a block (its a few instruction inserted before return)
        // FIXME: this may change in the future
965
        
966
        // prepare return regs
qinsoon's avatar
qinsoon committed
967
        let ref ops = ret_inst.ops.read().unwrap();
968 969 970 971 972 973
        let ret_val_indices = match ret_inst.v {
            Instruction_::Return(ref vals) => vals,
            _ => panic!("expected ret inst")
        };
        
        let mut gpr_ret_count = 0;
974
        // TODO: let mut fpr_ret_count = 0;
975 976 977
        for i in ret_val_indices {
            let ref ret_val = ops[*i];
            if self.match_ireg(ret_val) {
978
                let reg_ret_val = self.emit_ireg(ret_val, f_content, f_context, vm);
979 980 981 982
                
                self.backend.emit_mov_r64_r64(&x86_64::RETURN_GPRs[gpr_ret_count], &reg_ret_val);
                gpr_ret_count += 1;
            } else if self.match_iimm(ret_val) {
983
                let imm_ret_val = self.node_iimm_to_i32(ret_val);
984 985 986 987 988 989
                
                self.backend.emit_mov_r64_imm32(&x86_64::RETURN_GPRs[gpr_ret_count], imm_ret_val);
                gpr_ret_count += 1;
            } else {
                unimplemented!();
            }
990 991 992 993 994 995 996 997
        }        
        
        // pop all callee-saved registers - reverse order
        for i in (0..x86_64::CALLEE_SAVED_GPRs.len()).rev() {
            let ref reg = x86_64::CALLEE_SAVED_GPRs[i];
            if reg.extract_ssa_id().unwrap() != x86_64::RBP.extract_ssa_id().unwrap() {
                self.backend.emit_pop_r64(&reg);
            }
998
        }
999 1000 1001
        
        // pop rbp
        self.backend.emit_pop_r64(&x86_64::RBP);
1002 1003
    }
    
qinsoon's avatar
qinsoon committed
1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015
    fn match_cmp_res(&mut self, op: &P<TreeNode>) -> bool {
        match op.v {
            TreeNode_::Instruction(ref inst) => {
                match inst.v {
                    Instruction_::CmpOp(_, _, _) => true,
                    _ => false
                }
            }
            TreeNode_::Value(_) => false
        }
    }
    
1016
    fn emit_cmp_res(&mut self, cond: &P<TreeNode>, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) -> op::CmpOp {
qinsoon's avatar
qinsoon committed
1017 1018
        match cond.v {
            TreeNode_::Instruction(ref inst) => {
qinsoon's avatar
qinsoon committed
1019
                let ops = inst.ops.read().unwrap();                
qinsoon's avatar
qinsoon committed
1020 1021 1022 1023 1024 1025 1026 1027
                
                match inst.v {
                    Instruction_::CmpOp(op, op1, op2) => {
                        let op1 = &ops[op1];
                        let op2 = &ops[op2];
                        
                        if op::is_int_cmp(op) {                        
                            if self.match_ireg(op1) && self.match_ireg(op2) {
1028 1029
                                let reg_op1 = self.emit_ireg(op1, f_content, f_context, vm);
                                let reg_op2 = self.emit_ireg(op2, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
1030 1031 1032
                                
                                self.backend.emit_cmp_r64_r64(&reg_op1, &reg_op2);
                            } else if self.match_ireg(op1) && self.match_iimm(op2) {
1033
                                let reg_op1 = self.emit_ireg(op1, f_content, f_context, vm);
1034
                                let iimm_op2 = self.node_iimm_to_i32(op2);
qinsoon's avatar
qinsoon committed
1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052 1053
                                
                                self.backend.emit_cmp_r64_imm32(&reg_op1, iimm_op2);
                            } else {
                                unimplemented!()
                            }
                        } else {
                            unimplemented!()
                        }
                        
                        op
                    }
                    
                    _ => panic!("expect cmp res to emit")
                }
            }
            _ => panic!("expect cmp res to emit")
        }
    }    
    
qinsoon's avatar
qinsoon committed
1054
    fn match_ireg(&mut self, op: &TreeNode) -> bool {
qinsoon's avatar
qinsoon committed
1055 1056 1057 1058 1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 1073 1074 1075 1076 1077 1078 1079
        match op.v {
            TreeNode_::Instruction(ref inst) => {
                if inst.value.is_some() {
                    if inst.value.as_ref().unwrap().len() > 1 {
                        return false;
                    }
                    
                    let ref value = inst.value.as_ref().unwrap()[0];
                    
                    if types::is_scalar(&value.ty) {
                        true
                    } else {
                        false
                    }
                } else {
                    false
                }
            }
            
            TreeNode_::Value(ref pv) => {
                pv.is_int_reg()
            }
        }
    }
    
1080
    fn emit_ireg(&mut self, op: &P<TreeNode>, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) -> P<Value> {
qinsoon's avatar
qinsoon committed
1081 1082
        match op.v {
            TreeNode_::Instruction(_) => {
1083
                self.instruction_select(op, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
1084 1085 1086 1087 1088
                
                self.emit_get_result(op)
            },
            TreeNode_::Value(ref pv) => {
                match pv.v {
1089
                    Value_::Constant(_)
1090
                    | Value_::Global(_)
1091
                    | Value_::Memory(_) => panic!("expected ireg"),
qinsoon's avatar
qinsoon committed
1092 1093
                    Value_::SSAVar(_) => {
                        pv.clone()
qinsoon's avatar
qinsoon committed
1094
                    },
qinsoon's avatar
qinsoon committed
1095 1096 1097 1098 1099
                }
            }
        }
    }
    
1100
    #[allow(unused_variables)]
1101 1102 1103 1104
    fn match_fpreg(&mut self, op: &P<TreeNode>) -> bool {
        unimplemented!()
    }
    
qinsoon's avatar
qinsoon committed
1105 1106 1107 1108 1109 1110 1111
    fn match_iimm(&mut self, op: &P<TreeNode>) -> bool {
        match op.v {
            TreeNode_::Value(ref pv) if x86_64::is_valid_x86_imm(pv) => true,
            _ => false
        }
    }
    
1112
    fn node_iimm_to_i32(&mut self, op: &P<TreeNode>) -> i32 {
qinsoon's avatar
qinsoon committed
1113 1114 1115 1116
        match op.v {
            TreeNode_::Value(ref pv) => {
                match pv.v {
                    Value_::Constant(Constant::Int(val)) => {
1117
                        val as i32
qinsoon's avatar
qinsoon committed
1118 1119 1120 1121 1122 1123 1124
                    },
                    _ => panic!("expected iimm")
                }
            },
            _ => panic!("expected iimm")
        }
    }
1125 1126 1127 1128 1129 1130 1131 1132 1133

    fn node_iimm_to_value(&mut self, op: &P<TreeNode>) -> P<Value> {
        match op.v {
            TreeNode_::Value(ref pv) => {
                pv.clone()
            }
            _ => panic!("expected iimm")
        }
    }
qinsoon's avatar
qinsoon committed
1134
    
1135
    fn node_mem_to_value(&mut self, op: &P<TreeNode>, vm: &VM) -> P<Value> {
1136 1137 1138 1139
        match op.v {
            TreeNode_::Value(ref pv) => {
                match pv.v {
                    Value_::SSAVar(_) => P(Value{
1140
                        hdr: MuEntityHeader::unnamed(vm.next_id()),
1141 1142 1143 1144 1145 1146 1147 1148
                        ty: types::get_referent_ty(& pv.ty).unwrap(),
                        v: Value_::Memory(MemoryLocation::Address{
                            base: pv.clone(),
                            offset: None,
                            index: None,
                            scale: None
                        })
                    }),
1149
                    Value_::Global(_) => {
1150 1151 1152 1153 1154 1155
                        if vm.is_running() {
                            // get address from vm
                            unimplemented!()
                        } else {
                            // symbolic
                            P(Value{
1156
                                hdr: MuEntityHeader::unnamed(vm.next_id()),
1157 1158 1159
                                ty: types::get_referent_ty(&pv.ty).unwrap(),
                                v: Value_::Memory(MemoryLocation::Symbolic{
                                    base: Some(x86_64::RIP.clone()),
1160
                                    label: pv.name().unwrap()
1161 1162 1163 1164 1165 1166 1167 1168
                                })
                            })
                        }
                    },
                    Value_::Memory(_) => pv.clone(),
                    Value_::Constant(_) => unimplemented!()
                }
            }
1169 1170 1171 1172 1173 1174 1175 1176 1177 1178 1179 1180 1181
            TreeNode_::Instruction(_) => self.emit_get_mem_from_inst(op, vm)
        }
    }
    
    fn emit_get_mem_from_inst(&mut self, op: &P<TreeNode>, vm: &VM) -> P<Value> {
        match op.v {
            TreeNode_::Instruction(ref inst) => {
                let ref ops = inst.ops.read().unwrap();
                
                match inst.v {
                    Instruction_::GetIRef(op_index) => {
                        let ref op = ops[op_index];
                        
qinsoon's avatar
qinsoon committed
1182
                        self.make_memory_op_base_offset(&op.clone_value(), mm::objectmodel::OBJECT_HEADER_SIZE as i32, ADDRESS_TYPE.clone(), vm) 
1183 1184 1185 1186 1187
                    }
                    _ => unimplemented!()
                }
            },
            _ => panic!("expecting a instruction that yields a memory address")
1188 1189 1190
        }
    }
    
1191 1192 1193 1194 1195 1196 1197 1198 1199 1200 1201 1202 1203
    fn match_funcref_const(&mut self, op: &P<TreeNode>) -> bool {
        match op.v {
            TreeNode_::Value(ref pv) => {
                match pv.v {
                    Value_::Constant(Constant::FuncRef(_)) => true,
                    Value_::Constant(Constant::UFuncRef(_)) => true,
                    _ => false
                }
            },
            _ => false 
        }
    }
    
1204
    fn node_funcref_const_to_id(&mut self, op: &P<TreeNode>) -> MuID {
1205 1206 1207
        match op.v {
            TreeNode_::Value(ref pv) => {
                match pv.v {
qinsoon's avatar
qinsoon committed
1208 1209
                    Value_::Constant(Constant::FuncRef(id))
                    | Value_::Constant(Constant::UFuncRef(id)) => id,
1210 1211 1212 1213 1214 1215 1216
                    _ => panic!("expected a (u)funcref const")
                }
            },
            _ => panic!("expected a (u)funcref const")
        }
    }
    
1217
    #[allow(unused_variables)]
1218 1219 1220 1221
    fn match_mem(&mut self, op: &P<TreeNode>) -> bool {
        unimplemented!()
    }
    
1222
    #[allow(unused_variables)]
1223 1224 1225 1226
    fn emit_mem(&mut self, op: &P<TreeNode>) -> P<Value> {
        unimplemented!()
    }
    
qinsoon's avatar
qinsoon committed
1227
    fn emit_get_result(&mut self, node: &TreeNode) -> P<Value> {
qinsoon's avatar
qinsoon committed
1228 1229 1230 1231 1232 1233 1234 1235 1236 1237 1238 1239 1240 1241 1242 1243 1244 1245 1246
        match node.v {
            TreeNode_::Instruction(ref inst) => {
                if inst.value.is_some() {
                    if inst.value.as_ref().unwrap().len() > 1 {
                        panic!("expected ONE result from the node {}", node);
                    }
                    
                    let ref value = inst.value.as_ref().unwrap()[0];
                    
                    value.clone()
                } else {
                    panic!("expected result from the node {}", node);
                }
            }
            
            TreeNode_::Value(ref pv) => {
                pv.clone()
            }
        }
1247 1248
    }
    
1249
    fn emit_general_move(&mut self, src: &P<TreeNode>, dest: &P<Value>, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) {
1250 1251 1252 1253
        let ref dst_ty = dest.ty;
        
        if !types::is_fp(dst_ty) && types::is_scalar(dst_ty) {
            if self.match_ireg(src) {
1254
                let src_reg = self.emit_ireg(src, f_content, f_context, vm);
1255 1256
                self.backend.emit_mov_r64_r64(dest, &src_reg);
            } else if self.match_iimm(src) {
1257
                let src_imm = self.node_iimm_to_i32(src);
1258 1259 1260 1261 1262 1263 1264 1265 1266 1267
                self.backend.emit_mov_r64_imm32(dest, src_imm);
            } else {
                panic!("expected an int type op");
            }
        } else if !types::is_fp(dst_ty) && types::is_scalar(dst_ty) {
            unimplemented!()
        } else {
            panic!("unexpected type for move");
        } 
    }
qinsoon's avatar
qinsoon committed
1268
    
qinsoon's avatar
qinsoon committed
1269 1270 1271 1272 1273 1274 1275 1276 1277 1278 1279 1280 1281 1282
    fn emit_landingpad(&mut self, exception_arg: &P<Value>, f_content: &FunctionContent, f_context: &mut FunctionContext, vm: &VM) {
        // get thread local and add offset to get exception_obj
        let tl = self.emit_get_threadlocal(None, f_content, f_context, vm);
        self.emit_load_base_offset(exception_arg, &tl, *thread::EXCEPTION_OBJ_OFFSET as i32, vm);
    }
    
    fn new_callsite_label(&mut self, cur_node: Option<&TreeNode>) -> String {
        let ret = {
            if cur_node.is_some() {
                format!("callsite_{}_{}", cur_node.unwrap().id(), self.current_callsite_id)
            } else {
                format!("callsite_anon_{}", self.current_callsite_id)
            }
        };
qinsoon's avatar
qinsoon committed
1283 1284 1285
        self.current_callsite_id += 1;
        ret
    }
1286
}
1287

1288 1289 1290
impl CompilerPass for InstructionSelection {
    fn name(&self) -> &'static str {
        self.name
1291
    }
1292

qinsoon's avatar
qinsoon committed
1293 1294 1295 1296
    fn as_any(&self) -> &Any {
        self
    }

1297
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
1298
    fn start_function(&mut self, vm: &VM, func_ver: &mut MuFunctionVersion) {
1299
        debug!("{}", self.name());
1300
        
1301
        self.current_frame = Some(Frame::new(func_ver.id()));
qinsoon's avatar
qinsoon committed
1302 1303 1304 1305 1306
        self.current_func_start = Some({
            let funcs = vm.funcs().read().unwrap();
            let func = funcs.get(&func_ver.func_id).unwrap().read().unwrap();
            self.backend.start_code(func.name().unwrap())        
        });
qinsoon's avatar
qinsoon committed
1307 1308 1309
        self.current_callsite_id = 0;
        self.current_exn_callsites.clear();
        self.current_exn_blocks.clear();
1310 1311
        
        // prologue (get arguments from entry block first)        
qinsoon's avatar
qinsoon committed
1312
        let entry_block = func_ver.content.as_ref().unwrap().get_entry_block();
1313
        let ref args = entry_block.content.as_ref().unwrap().args;
qinsoon's avatar
qinsoon committed
1314
        self.emit_common_prologue(args, vm);
1315 1316 1317
    }

    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
1318
    fn visit_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
1319 1320
        let f_content = func.content.as_ref().unwrap();
        
qinsoon's avatar
qinsoon committed
1321
        for block_id in func.block_trace.as_ref().unwrap() {
1322
            let block = f_content.get_block(*block_id);
1323
            let block_label = block.name().unwrap();
qinsoon's avatar
qinsoon committed
1324
            self.current_block = Some(block_label.clone());            
1325
            
qinsoon's avatar
qinsoon committed
1326 1327
            let block_content = block.content.as_ref().unwrap();
            
qinsoon's avatar
qinsoon committed
1328 1329 1330 1331
            if block.is_exception_block() {
                let loc = self.backend.start_exception_block(block_label.clone());
                self.current_exn_blocks.insert(block.id(), loc);
                
qinsoon's avatar
qinsoon committed
1332 1333 1334 1335 1336 1337 1338
                let exception_arg = block_content.exn_arg.as_ref().unwrap();
                
                // live in is args of the block + exception arg
                let mut livein = block_content.args.to_vec();
                livein.push(exception_arg.clone());
                self.backend.set_block_livein(block_label.clone(), &livein);
                
qinsoon's avatar
qinsoon committed
1339
                // need to insert a landing pad
qinsoon's avatar
qinsoon committed
1340
                self.emit_landingpad(&exception_arg, f_content, &mut func.context, vm);
qinsoon's avatar
qinsoon committed
1341
            } else {
qinsoon's avatar
qinsoon committed
1342 1343 1344 1345
                self.backend.start_block(block_label.clone());
                
                // live in is args of the block
                self.backend.set_block_livein(block_label.clone(), &block_content.args);                    
qinsoon's avatar
qinsoon committed
1346
            }
1347 1348 1349
            
            // live out is the union of all branch args of this block
            let live_out = block_content.get_out_arguments();
1350

1351
            for inst in block_content.body.iter() {
1352
                self.instruction_select(&inst, f_content, &mut func.context, vm);
1353
            }
1354
            
1355 1356 1357 1358 1359 1360 1361 1362
            // we may start block a, and end with block b (instruction selection may create blocks)
            // we set liveout to current block 
            {
                let current_block = self.current_block.as_ref().unwrap();
                self.backend.set_block_liveout(current_block.clone(), &live_out);
                self.backend.end_block(current_block.clone());
            }            
            self.current_block = None;
1363 1364
        }
    }
1365 1366
    
    #[allow(unused_variables)]
qinsoon's avatar
qinsoon committed
1367
    fn finish_function(&mut self, vm: &VM, func: &mut MuFunctionVersion) {
1368 1369
        self.backend.print_cur_code();
        
qinsoon's avatar
qinsoon committed
1370 1371 1372 1373 1374 1375 1376
        let func_name = {
            let funcs = vm.funcs().read().unwrap();
            let func = funcs.get(&func.func_id).unwrap().read().unwrap();
            func.name().unwrap()
        };
        
        let (mc, func_end) = self.backend.finish_code(func_name);
qinsoon's avatar
qinsoon committed
1377 1378 1379 1380 1381 1382 1383 1384 1385 1386 1387 1388
        
        // insert exception branch info
        let mut frame = self.current_frame.take().unwrap();
        for block_id in self.current_exn_blocks.keys() {
            let block_loc = self.current_exn_blocks.get(&block_id).unwrap();
            let callsites = self.current_exn_callsites.get(&block_id).unwrap();
            
            for callsite in callsites {
                frame.add_exception_callsite(callsite.clone(), block_loc.clone());
            }
        }
        
1389
        let compiled_func = CompiledFunction {
qinsoon's avatar
qinsoon committed
1390
            func_id: func.func_id,
1391
            func_ver_id: func.id(),
1392
            temps: HashMap::new(),
qinsoon's avatar
qinsoon committed
1393
            mc: Some(mc),
qinsoon's avatar
qinsoon committed
1394
            frame: frame,
qinsoon's avatar
qinsoon committed
1395 1396
            start: self.current_func_start.take().unwrap(),
            end: func_end 
1397 1398
        };
        
qinsoon's avatar