inst_sel.rs 291 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3 4 5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9 10 11 12 13 14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15
use ast::ir::*;
16
use ast::ptr::*;
qinsoon's avatar
qinsoon committed
17
use ast::inst::*;
18
use ast::op;
qinsoon's avatar
qinsoon committed
19
use ast::op::*;
qinsoon's avatar
qinsoon committed
20
use ast::types::*;
qinsoon's avatar
qinsoon committed
21
use vm::VM;
qinsoon's avatar
qinsoon committed
22
use runtime::mm;
qinsoon's avatar
qinsoon committed
23 24
use runtime::mm::OBJECT_HEADER_SIZE;
use runtime::mm::OBJECT_HEADER_OFFSET;
25 26 27 28
use runtime::ValueLocation;
use runtime::thread;
use runtime::entrypoints;
use runtime::entrypoints::RuntimeEntrypoint;
29 30

use compiler::CompilerPass;
31
use compiler::backend::RegGroup;
32
use compiler::PROLOGUE_BLOCK_NAME;
qinsoon's avatar
qinsoon committed
33 34 35
use compiler::backend::x86_64;
use compiler::backend::x86_64::CodeGenerator;
use compiler::backend::x86_64::ASMCodeGen;
36 37 38
use compiler::backend::x86_64::callconv;
use compiler::backend::x86_64::callconv::CallConvResult;
use compiler::backend::x86_64::CALLEE_SAVED_COUNT;
39
use compiler::backend::make_block_name;
qinsoon's avatar
qinsoon committed
40 41
use compiler::machine_code::CompiledFunction;
use compiler::frame::Frame;
42

43
use utils::math;
44
use utils::{POINTER_SIZE, WORD_SIZE};
45
use utils::{BitSize, ByteSize};
46

47
use std::collections::HashMap;
48
use std::collections::LinkedList;
49
use std::sync::Arc;
qinsoon's avatar
qinsoon committed
50
use std::any::Any;
51

52
lazy_static! {
qinsoon's avatar
qinsoon committed
53 54
    /// struct<int32, int32, int32, int32>
    static ref LONG_4_TYPE : P<MuType> = P(
qinsoon's avatar
qinsoon committed
55 56
        MuType::new(new_internal_id(), MuType_::mustruct(Mu("long_4"),
        vec![UINT32_TYPE.clone(); 4]))
57 58
    );

qinsoon's avatar
qinsoon committed
59 60
    /// constant for converting unsigned integer to floating point
    static ref UITOFP_C0 : P<Value> = P(Value{
61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
        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))
            })
        ]))
    });

qinsoon's avatar
qinsoon committed
87 88
    /// struct<int64, int64>
    static ref QUAD_2_TYPE : P<MuType> = P(
qinsoon's avatar
qinsoon committed
89 90
        MuType::new(new_internal_id(), MuType_::mustruct(Mu("quad_2"),
        vec![UINT64_TYPE.clone(); 2]))
91 92
    );

qinsoon's avatar
qinsoon committed
93 94
    /// constant for converting unsigned integer to floating point
    static ref UITOFP_C1 : P<Value> = P(Value{
95 96 97 98 99 100 101 102 103 104 105 106 107 108 109
        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))
            })
        ]))
    });
110

qinsoon's avatar
qinsoon committed
111 112
    /// constant for converting double to unsigned integer
    static ref FPTOUI_C_DOUBLE : P<Value> = P(Value{
qinsoon's avatar
qinsoon committed
113
        hdr: MuEntityHeader::named(new_internal_id(), Mu("FPTOUI_C_DOUBLE")),
114 115 116
        ty : UINT64_TYPE.clone(),
        v  : Value_::Constant(Constant::Int(4890909195324358656u64))
    });
qinsoon's avatar
qinsoon committed
117

qinsoon's avatar
qinsoon committed
118
    /// constant for converting float to unsigned integer
qinsoon's avatar
qinsoon committed
119 120 121 122 123
    pub static ref FPTOUI_C_FLOAT : P<Value> = P(Value{
        hdr: MuEntityHeader::named(new_internal_id(), Mu("FPTOUI_C_FLOAT")),
        ty : UINT32_TYPE.clone(),
        v  : Value_::Constant(Constant::Int(1593835520u64))
    });
124 125
}

qinsoon's avatar
qinsoon committed
126 127 128 129
/// for some IR instructions, we need a call into runtime
/// for efficiency, we may emit runtime fastpath directly in assembly
//  FIXME: we should have a separate pass to rewrite the instruction into a fastpath (in IR),
//         and a call to slowpath, then instruction selection (see Issue#6)
130
const INLINE_FASTPATH: bool = false;
131

132
pub struct InstructionSelection {
133
    name: &'static str,
qinsoon's avatar
qinsoon committed
134
    /// backend code generator
135
    backend: Box<CodeGenerator>,
136

qinsoon's avatar
qinsoon committed
137 138
    // information about the function being compiled
    /// ID of current function version being compiled
139
    current_fv_id: MuID,
140
    /// name of current function version being compiled
141
    current_fv_name: MuName,
142 143
    /// signature of current function being compiled
    current_sig: Option<P<MuFuncSig>>,
qinsoon's avatar
qinsoon committed
144
    /// used to create a unique callsite ID for current function
qinsoon's avatar
qinsoon committed
145
    current_callsite_id: usize,
qinsoon's avatar
qinsoon committed
146
    /// frame for current function
qinsoon's avatar
qinsoon committed
147
    current_frame: Option<Frame>,
qinsoon's avatar
qinsoon committed
148 149
    /// block that is currently being compiled
    /// the block may be created during instruction selection
qinsoon's avatar
qinsoon committed
150
    current_block: Option<MuName>,
qinsoon's avatar
qinsoon committed
151 152
    /// IR block that is currently being compiled
    /// use this block name to trace some information at IR level
153
    current_block_in_ir: Option<MuName>,
qinsoon's avatar
qinsoon committed
154
    /// start location of current function
qinsoon's avatar
qinsoon committed
155
    current_func_start: Option<ValueLocation>,
qinsoon's avatar
qinsoon committed
156 157 158 159
    /// technically this is a map in that each Key is unique, but we will never try and
    /// add duplicate keys, or look things up, so a list of tuples is faster than a Map.
    /// A list of tuples, the first is the name of a callsite, the next is the callsite destination,
    /// the last is the size of arguments pushed on the stack
160
    current_callsites: LinkedList<(MuName, MuID, usize)>,
qinsoon's avatar
qinsoon committed
161
    // key: block id, val: block location
162
    current_exn_blocks: HashMap<MuID, MuName>,
qinsoon's avatar
qinsoon committed
163 164
    /// constants used in this function that are put to memory
    /// key: value id, val: constant value
165
    current_constants: HashMap<MuID, P<Value>>,
qinsoon's avatar
qinsoon committed
166 167
    /// constants used in this function that are put to memory
    /// key: value id, val: memory location
168
    current_constants_locs: HashMap<MuID, P<Value>>
169 170
}

171
impl<'a> InstructionSelection {
qinsoon's avatar
qinsoon committed
172
    #[cfg(feature = "aot")]
173
    pub fn new() -> InstructionSelection {
174
        InstructionSelection {
175
            name: "Instruction Selection (x64)",
176
            backend: Box::new(ASMCodeGen::new()),
177

178
            current_fv_id: 0,
179
            current_fv_name: Arc::new(String::new()),
180
            current_sig: None,
qinsoon's avatar
qinsoon committed
181
            current_callsite_id: 0,
qinsoon's avatar
qinsoon committed
182
            current_frame: None,
qinsoon's avatar
qinsoon committed
183 184 185 186
            // which block we are generating code for
            current_block: None,
            // it is possible the block is newly created in instruction
            // selection
187
            // but sometimes we want to know its control flow
qinsoon's avatar
qinsoon committed
188
            // so we need to track what block it is from the IR
189

qinsoon's avatar
qinsoon committed
190 191 192
            // FIXME: ideally we should not create new blocks in instruction selection
            // see Issue #6
            current_block_in_ir: None,
qinsoon's avatar
qinsoon committed
193
            current_func_start: None,
194
            current_callsites: LinkedList::new(),
195 196 197
            current_exn_blocks: HashMap::new(),

            current_constants: HashMap::new(),
198
            current_constants_locs: HashMap::new()
199 200
        }
    }
qinsoon's avatar
qinsoon committed
201 202 203 204 205

    #[cfg(feature = "jit")]
    pub fn new() -> InstructionSelection {
        unimplemented!()
    }
qinsoon's avatar
qinsoon committed
206 207 208

    /// we use hand-written pattern matching rules for instruction selection
    /// for a pattern that can match several rules, the first rule met will be executed, and chosen.
209 210 211 212 213
    fn instruction_select(
        &mut self,
        node: &'a TreeNode,
        f_content: &FunctionContent,
        f_context: &mut FunctionContext,
214
        vm: &VM
215
    ) {
216
        trace!("instsel on node#{} {}", node.id(), node);
217

qinsoon's avatar
qinsoon committed
218
        match node.v {
219 220
            TreeNode_::Instruction(ref inst) => {
                match inst.v {
221 222 223 224 225 226
                    Instruction_::Branch2 {
                        cond,
                        ref true_dest,
                        ref false_dest,
                        ..
                    } => {
qinsoon's avatar
qinsoon committed
227
                        trace!("instsel on BRANCH2");
228
                        let (fallthrough_dest, branch_dest) = (false_dest, true_dest);
229

230
                        let ref ops = inst.ops;
231 232
                        self.process_dest(&ops, fallthrough_dest, f_content, f_context, vm);
                        self.process_dest(&ops, branch_dest, f_content, f_context, vm);
233

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

236
                        let ref cond = ops[cond];
qinsoon's avatar
qinsoon committed
237
                        if self.match_cmp_res(cond) {
qinsoon's avatar
qinsoon committed
238
                            // this branch2's cond is from a comparison result
239
                            trace!("emit cmp_res-branch2");
240
                            match self.emit_cmp_res(cond, f_content, f_context, vm) {
qinsoon's avatar
qinsoon committed
241 242
                                op::CmpOp::EQ => self.backend.emit_je(branch_target),
                                op::CmpOp::NE => self.backend.emit_jne(branch_target),
243 244 245 246 247 248 249 250
                                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
251 252 253

                                // floating point
                                op::CmpOp::FOEQ | op::CmpOp::FUEQ => {
qinsoon's avatar
qinsoon committed
254
                                    self.backend.emit_je(branch_target)
255
                                }
qinsoon's avatar
qinsoon committed
256
                                op::CmpOp::FONE | op::CmpOp::FUNE => {
qinsoon's avatar
qinsoon committed
257
                                    self.backend.emit_jne(branch_target)
258
                                }
qinsoon's avatar
qinsoon committed
259
                                op::CmpOp::FOGT | op::CmpOp::FUGT => {
qinsoon's avatar
qinsoon committed
260
                                    self.backend.emit_ja(branch_target)
261
                                }
qinsoon's avatar
qinsoon committed
262
                                op::CmpOp::FOGE | op::CmpOp::FUGE => {
qinsoon's avatar
qinsoon committed
263
                                    self.backend.emit_jae(branch_target)
264
                                }
qinsoon's avatar
qinsoon committed
265
                                op::CmpOp::FOLT | op::CmpOp::FULT => {
qinsoon's avatar
qinsoon committed
266
                                    self.backend.emit_jb(branch_target)
267
                                }
qinsoon's avatar
qinsoon committed
268
                                op::CmpOp::FOLE | op::CmpOp::FULE => {
qinsoon's avatar
qinsoon committed
269
                                    self.backend.emit_jbe(branch_target)
270
                                }
qinsoon's avatar
qinsoon committed
271

272
                                _ => unimplemented!()
qinsoon's avatar
qinsoon committed
273 274
                            }
                        } else if self.match_ireg(cond) {
qinsoon's avatar
qinsoon committed
275 276
                            // this branch2 cond is a temporary with value, or an instruction that
                            // emits a temporary
qinsoon's avatar
qinsoon committed
277
                            trace!("emit ireg-branch2");
278

279
                            let cond_reg = self.emit_ireg(cond, f_content, f_context, vm);
280

qinsoon's avatar
qinsoon committed
281
                            // emit: cmp cond_reg 1
qinsoon's avatar
qinsoon committed
282
                            self.backend.emit_cmp_imm_r(1, &cond_reg);
qinsoon's avatar
qinsoon committed
283
                            // emit: je #branch_dest
284
                            self.backend.emit_je(branch_target);
qinsoon's avatar
qinsoon committed
285
                        } else {
qinsoon's avatar
qinsoon committed
286
                            panic!("unexpected cond in BRANCH2: {}", cond)
287
                        }
288
                    }
qinsoon's avatar
qinsoon committed
289

290 291 292
                    Instruction_::Select {
                        cond,
                        true_val,
293
                        false_val
294
                    } => {
qinsoon's avatar
qinsoon committed
295 296
                        use ast::op::CmpOp::*;

qinsoon's avatar
qinsoon committed
297
                        trace!("instsel on SELECT");
298
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
299 300 301 302 303

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

qinsoon's avatar
qinsoon committed
304
                        // generate comparison
305 306 307 308 309 310 311 312 313 314 315 316
                        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 cond to be ireg, found {}", cond)
                        };

qinsoon's avatar
qinsoon committed
317
                        // emit code to move values
qinsoon's avatar
qinsoon committed
318 319
                        if self.match_ireg(true_val) {
                            // moving integers/pointers
320
                            let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
321

322
                            // use cmov for 16/32/64bit integer
qinsoon's avatar
qinsoon committed
323
                            // use jcc  for 8 bit
324
                            // FIXME: could use 32bit register to implement 8bit select
qinsoon's avatar
qinsoon committed
325 326 327
                            match tmp_res.ty.get_int_length() {
                                // cmov
                                Some(len) if len > 8 => {
328 329 330 331
                                    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);
qinsoon's avatar
qinsoon committed
332 333 334 335 336

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

                                    match cmpop {
337 338
                                        EQ => self.backend.emit_cmove_r_r(&tmp_res, &tmp_true),
                                        NE => self.backend.emit_cmovne_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
339
                                        SGE => self.backend.emit_cmovge_r_r(&tmp_res, &tmp_true),
340
                                        SGT => self.backend.emit_cmovg_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
341
                                        SLE => self.backend.emit_cmovle_r_r(&tmp_res, &tmp_true),
342
                                        SLT => self.backend.emit_cmovl_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
343
                                        UGE => self.backend.emit_cmovae_r_r(&tmp_res, &tmp_true),
344
                                        UGT => self.backend.emit_cmova_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
345
                                        ULE => self.backend.emit_cmovbe_r_r(&tmp_res, &tmp_true),
346
                                        ULT => self.backend.emit_cmovb_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
347

348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365
                                        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)
                                        }
qinsoon's avatar
qinsoon committed
366

qinsoon's avatar
qinsoon committed
367
                                        // FFALSE/FTRUE unimplemented
368
                                        _ => unimplemented!()
qinsoon's avatar
qinsoon committed
369 370
                                    }
                                }
qinsoon's avatar
qinsoon committed
371
                                // jcc - for 8-bits integer
qinsoon's avatar
qinsoon committed
372
                                _ => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
373 374 375
                                    let blk_true = make_block_name(&node.name(), "select_true");
                                    let blk_false = make_block_name(&node.name(), "select_false");
                                    let blk_end = make_block_name(&node.name(), "select_end");
qinsoon's avatar
qinsoon committed
376 377 378

                                    // jump to blk_true if true
                                    match cmpop {
379 380
                                        EQ => self.backend.emit_je(blk_true.clone()),
                                        NE => self.backend.emit_jne(blk_true.clone()),
qinsoon's avatar
qinsoon committed
381
                                        SGE => self.backend.emit_jge(blk_true.clone()),
382
                                        SGT => self.backend.emit_jg(blk_true.clone()),
qinsoon's avatar
qinsoon committed
383
                                        SLE => self.backend.emit_jle(blk_true.clone()),
384
                                        SLT => self.backend.emit_jl(blk_true.clone()),
qinsoon's avatar
qinsoon committed
385
                                        UGE => self.backend.emit_jae(blk_true.clone()),
386
                                        UGT => self.backend.emit_ja(blk_true.clone()),
qinsoon's avatar
qinsoon committed
387
                                        ULE => self.backend.emit_jbe(blk_true.clone()),
388
                                        ULT => self.backend.emit_jb(blk_true.clone()),
qinsoon's avatar
qinsoon committed
389

390
                                        FOEQ | FUEQ => self.backend.emit_je(blk_true.clone()),
qinsoon's avatar
qinsoon committed
391
                                        FONE | FUNE => self.backend.emit_jne(blk_true.clone()),
392
                                        FOGT | FUGT => self.backend.emit_ja(blk_true.clone()),
qinsoon's avatar
qinsoon committed
393
                                        FOGE | FUGE => self.backend.emit_jae(blk_true.clone()),
394
                                        FOLT | FULT => self.backend.emit_jb(blk_true.clone()),
qinsoon's avatar
qinsoon committed
395 396
                                        FOLE | FULE => self.backend.emit_jbe(blk_true.clone()),

qinsoon's avatar
qinsoon committed
397
                                        // FFALSE/FTRUE unimplemented
398
                                        _ => unimplemented!()
qinsoon's avatar
qinsoon committed
399 400
                                    }

401
                                    // finishing current block
qinsoon's avatar
qinsoon committed
402
                                    self.finish_block();
403 404

                                    // blk_false:
qinsoon's avatar
qinsoon committed
405
                                    self.start_block(blk_false.clone());
qinsoon's avatar
qinsoon committed
406
                                    // mov false result here
407 408 409 410 411
                                    self.emit_move_node_to_value(
                                        &tmp_res,
                                        &false_val,
                                        f_content,
                                        f_context,
412
                                        vm
413
                                    );
qinsoon's avatar
qinsoon committed
414 415 416
                                    // jmp to end
                                    self.backend.emit_jmp(blk_end.clone());
                                    // finishing current block
qinsoon's avatar
qinsoon committed
417
                                    self.finish_block();
qinsoon's avatar
qinsoon committed
418 419

                                    // blk_true:
qinsoon's avatar
qinsoon committed
420
                                    self.start_block(blk_true.clone());
qinsoon's avatar
qinsoon committed
421
                                    // mov true value -> result
422 423 424 425 426
                                    self.emit_move_node_to_value(
                                        &tmp_res,
                                        &true_val,
                                        f_content,
                                        f_context,
427
                                        vm
428
                                    );
429
                                    self.finish_block();
qinsoon's avatar
qinsoon committed
430 431

                                    // blk_end:
432
                                    self.start_block(blk_end.clone());
qinsoon's avatar
qinsoon committed
433
                                }
qinsoon's avatar
qinsoon committed
434
                            }
435 436 437
                        } else if self.match_fpreg(true_val) {
                            let tmp_res = self.get_result_value(node);

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
438 439 440
                            let blk_true = make_block_name(&node.name(), "select_true");
                            let blk_false = make_block_name(&node.name(), "select_false");
                            let blk_end = make_block_name(&node.name(), "select_end");
441 442 443

                            // jump to blk_true if true
                            match cmpop {
444 445
                                EQ => self.backend.emit_je(blk_true.clone()),
                                NE => self.backend.emit_jne(blk_true.clone()),
446
                                SGE => self.backend.emit_jge(blk_true.clone()),
447
                                SGT => self.backend.emit_jg(blk_true.clone()),
448
                                SLE => self.backend.emit_jle(blk_true.clone()),
449
                                SLT => self.backend.emit_jl(blk_true.clone()),
450
                                UGE => self.backend.emit_jae(blk_true.clone()),
451
                                UGT => self.backend.emit_ja(blk_true.clone()),
452
                                ULE => self.backend.emit_jbe(blk_true.clone()),
453
                                ULT => self.backend.emit_jb(blk_true.clone()),
454

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

462
                                _ => unimplemented!()
463 464 465
                            }

                            // finishing current block
qinsoon's avatar
qinsoon committed
466
                            self.finish_block();
467 468

                            // blk_false:
qinsoon's avatar
qinsoon committed
469
                            self.start_block(blk_false.clone());
470
                            // mov false result here
471 472 473 474 475
                            self.emit_move_node_to_value(
                                &tmp_res,
                                &false_val,
                                f_content,
                                f_context,
476
                                vm
477
                            );
478 479 480 481
                            // jmp to end
                            self.backend.emit_jmp(blk_end.clone());

                            // finishing current block
qinsoon's avatar
qinsoon committed
482
                            self.finish_block();
483 484

                            // blk_true:
qinsoon's avatar
qinsoon committed
485
                            self.start_block(blk_true.clone());
486
                            // mov true value -> result
487 488 489 490 491
                            self.emit_move_node_to_value(
                                &tmp_res,
                                &true_val,
                                f_content,
                                f_context,
492
                                vm
493
                            );
qinsoon's avatar
qinsoon committed
494
                            self.finish_block();
495 496

                            // blk_end:
qinsoon's avatar
qinsoon committed
497
                            self.start_block(blk_end.clone());
qinsoon's avatar
qinsoon committed
498 499 500
                        } else {
                            unimplemented!()
                        }
501
                    }
qinsoon's avatar
qinsoon committed
502

qinsoon's avatar
qinsoon committed
503
                    Instruction_::CmpOp(_, _, _) => {
qinsoon's avatar
qinsoon committed
504
                        use ast::op::CmpOp::*;
qinsoon's avatar
qinsoon committed
505
                        trace!("instsel on CMPOP");
506

qinsoon's avatar
qinsoon committed
507
                        let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
508 509
                        assert!(tmp_res.ty.get_int_length().is_some());
                        assert!(tmp_res.ty.get_int_length().unwrap() == 1);
qinsoon's avatar
qinsoon committed
510

511
                        // set byte to result
qinsoon's avatar
qinsoon committed
512
                        match self.emit_cmp_res(node, f_content, f_context, vm) {
513 514
                            EQ => self.backend.emit_sete_r(&tmp_res),
                            NE => self.backend.emit_setne_r(&tmp_res),
515
                            SGE => self.backend.emit_setge_r(&tmp_res),
516
                            SGT => self.backend.emit_setg_r(&tmp_res),
517
                            SLE => self.backend.emit_setle_r(&tmp_res),
518
                            SLT => self.backend.emit_setl_r(&tmp_res),
519
                            UGE => self.backend.emit_setae_r(&tmp_res),
520
                            UGT => self.backend.emit_seta_r(&tmp_res),
521
                            ULE => self.backend.emit_setbe_r(&tmp_res),
522
                            ULT => self.backend.emit_setb_r(&tmp_res),
523

524
                            FOEQ | FUEQ => self.backend.emit_sete_r(&tmp_res),
525
                            FONE | FUNE => self.backend.emit_setne_r(&tmp_res),
526
                            FOGT | FUGT => self.backend.emit_seta_r(&tmp_res),
527
                            FOGE | FUGE => self.backend.emit_setae_r(&tmp_res),
528
                            FOLT | FULT => self.backend.emit_setb_r(&tmp_res),
529
                            FOLE | FULE => self.backend.emit_setbe_r(&tmp_res),
qinsoon's avatar
qinsoon committed
530

qinsoon's avatar
qinsoon committed
531
                            // FFALSE/FTRUE
532
                            _ => unimplemented!()
533 534 535
                        }
                    }

qinsoon's avatar
qinsoon committed
536
                    Instruction_::Branch1(ref dest) => {
qinsoon's avatar
qinsoon committed
537
                        trace!("instsel on BRANCH1");
538
                        let ref ops = inst.ops;
539

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

542
                        let target = f_content.get_block(dest.target).name();
543
                        // jmp
qinsoon's avatar
qinsoon committed
544
                        self.backend.emit_jmp(target);
545
                    }
qinsoon's avatar
qinsoon committed
546

547 548 549
                    Instruction_::Switch {
                        cond,
                        ref default,
550
                        ref branches
551
                    } => {
qinsoon's avatar
qinsoon committed
552
                        trace!("instsel on SWITCH");
553
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
554 555 556 557 558
                        let ref cond = ops[cond];

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

qinsoon's avatar
qinsoon committed
559 560 561 562
                            // currently implementing switch as cascading conditional branch
                            // This is slow if there are many 'case' arms. We should consider
                            // using a switch table

qinsoon's avatar
qinsoon committed
563 564 565 566 567 568 569
                            // 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);

570
                                let target = f_content.get_block(case_dest.target).name();
qinsoon's avatar
qinsoon committed
571 572 573 574 575

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

                                    // cmp case cond
qinsoon's avatar
qinsoon committed
576
                                    self.backend.emit_cmp_imm_r(imm, &tmp_cond);
qinsoon's avatar
qinsoon committed
577 578 579
                                    // je dest
                                    self.backend.emit_je(target);
                                } else if self.match_ireg(case_op) {
580 581
                                    let tmp_case_op =
                                        self.emit_ireg(case_op, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
582 583

                                    // cmp case cond
qinsoon's avatar
qinsoon committed
584
                                    self.backend.emit_cmp_r_r(&tmp_case_op, &tmp_cond);
qinsoon's avatar
qinsoon committed
585 586 587
                                    // je dest
                                    self.backend.emit_je(target);
                                } else {
588 589 590 591
                                    panic!(
                                        "expecting ireg cond to be either iimm or ireg: {}",
                                        cond
                                    );
qinsoon's avatar
qinsoon committed
592
                                }
593 594

                                self.finish_block();
595
                                let block_name = make_block_name(
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
596
                                    &node.name(),
597
                                    format!("switch_not_met_case_{}", case_op_index).as_str()
598
                                );
599
                                self.start_block(block_name);
qinsoon's avatar
qinsoon committed
600 601 602 603
                            }

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

605
                            let default_target = f_content.get_block(default.target).name();
qinsoon's avatar
qinsoon committed
606 607
                            self.backend.emit_jmp(default_target);
                        } else {
qinsoon's avatar
qinsoon committed
608 609
                            // other EQ-comparable types, e.g. floating point
                            unimplemented!()
qinsoon's avatar
qinsoon committed
610 611
                        }
                    }
612 613

                    Instruction_::ExprCall { ref data, is_abort } => {
qinsoon's avatar
qinsoon committed
614 615
                        trace!("instsel on EXPRCALL");

qinsoon's avatar
qinsoon committed
616
                        if is_abort {
qinsoon's avatar
qinsoon committed
617 618 619
                            // if any exception throws from the callee,
                            // we should abort execution, otherwise rethrow the exception
                            // FIXME: implement is_abort
qinsoon's avatar
qinsoon committed
620
                            unimplemented!()
621
                        }
622

qinsoon's avatar
qinsoon committed
623 624 625 626
                        self.emit_mu_call(
                            inst, // inst: &Instruction,
                            data, // calldata: &CallData,
                            None, // resumption: Option<&ResumptionData>,
627 628 629
                            node, // cur_node: &TreeNode,
                            f_content,
                            f_context,
630
                            vm
631 632 633 634 635
                        );
                    }

                    Instruction_::Call {
                        ref data,
636
                        ref resume
637
                    } => {
qinsoon's avatar
qinsoon committed
638 639
                        trace!("instsel on CALL");

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

                    Instruction_::ExprCCall { ref data, is_abort } => {
qinsoon's avatar
qinsoon committed
644 645
                        trace!("instsel on EXPRCCALL");

qinsoon's avatar
qinsoon committed
646
                        if is_abort {
qinsoon's avatar
qinsoon committed
647 648 649
                            // if any exception throws from the callee,
                            // we should abort execution, otherwise rethrow the exception
                            // FIXME: implement is_abort
qinsoon's avatar
qinsoon committed
650 651 652
                            unimplemented!()
                        }

653
                        self.emit_c_call_ir(inst, data, None, node, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
654 655
                    }

656 657
                    Instruction_::CCall {
                        ref data,
658
                        ref resume
659
                    } => {
qinsoon's avatar
qinsoon committed
660 661
                        trace!("instsel on CCALL");

qinsoon's avatar
qinsoon committed
662 663 664 665 666
                        self.emit_c_call_ir(
                            inst,
                            data,
                            Some(resume),
                            node,
667 668
                            f_content,
                            f_context,
669
                            vm
670
                        );
qinsoon's avatar
qinsoon committed
671
                    }
672

673
                    Instruction_::Return(_) => {
qinsoon's avatar
qinsoon committed
674 675
                        trace!("instsel on RETURN");

676
                        self.emit_common_epilogue(inst, f_content, f_context, vm);
677

qinsoon's avatar
qinsoon committed
678
                        self.backend.emit_ret();
679 680
                    }

qinsoon's avatar
qinsoon committed
681
                    Instruction_::BinOp(op, op1, op2) => {
qinsoon's avatar
qinsoon committed
682 683
                        trace!("instsel on BINOP");

qinsoon's avatar
qinsoon committed
684
                        self.emit_binop(node, inst, op, op1, op2, f_content, f_context, vm);
685
                    }
qinsoon's avatar
qinsoon committed
686

qinsoon's avatar
qinsoon committed
687 688
                    Instruction_::BinOpWithStatus(op, status, op1, op2) => {
                        trace!("instsel on BINOP_STATUS");
qinsoon's avatar
qinsoon committed
689

qinsoon's avatar
qinsoon committed
690
                        self.emit_binop(node, inst, op, op1, op2, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
691

qinsoon's avatar
qinsoon committed
692 693
                        let values = inst.value.as_ref().unwrap();
                        let mut status_value_index = 1;
qinsoon's avatar
qinsoon committed
694

695
                        // status flags only works with int operations
696
                        if RegGroup::get_from_value(&values[0]) == RegGroup::GPR {
qinsoon's avatar
qinsoon committed
697 698 699 700 701
                            // for mul, div, idiv, some of the flags may not generated
                            // from the computation, and we may need extra code
                            // to get the flags
                            // FIXME: See Issue#22

702 703 704 705
                            // negative flag
                            if status.flag_n {
                                let tmp_status = values[status_value_index].clone();
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
706

707 708
                                self.backend.emit_sets_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
709

710 711 712 713
                            // zero flag
                            if status.flag_z {
                                let tmp_status = values[status_value_index].clone();
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
714

715 716
                                self.backend.emit_setz_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
717

718 719 720 721
                            // unsigned overflow
                            if status.flag_c {
                                let tmp_status = values[status_value_index].clone();
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
722

723 724 725 726
                                match op {
                                    BinOp::Add | BinOp::Sub | BinOp::Mul => {
                                        self.backend.emit_setb_r8(&tmp_status);
                                    }
727
                                    _ => panic!("Only Add/Sub/Mul has #C flag")
qinsoon's avatar
qinsoon committed
728 729
                                }
                            }
qinsoon's avatar
qinsoon committed
730

731 732 733
                            // signed overflow
                            if status.flag_v {
                                let tmp_status = values[status_value_index].clone();
qinsoon's avatar
qinsoon committed
734

735 736 737 738
                                match op {
                                    BinOp::Add | BinOp::Sub | BinOp::Mul => {
                                        self.backend.emit_seto_r8(&tmp_status);
                                    }
739
                                    _ => panic!("Only Add/Sub/Mul has #V flag")
qinsoon's avatar
qinsoon committed
740 741
                                }
                            }
742 743 744
                        } else if RegGroup::get_from_value(&values[0]) == RegGroup::GPREX {
                            unimplemented!()
                        } else {
qinsoon's avatar
[wip]  
qinsoon committed
745
                            panic!("only int operations allow binop status flags")
746 747
                        }
                    }
qinsoon's avatar
qinsoon committed
748

749 750 751 752
                    Instruction_::ConvOp {
                        operation,
                        ref from_ty,
                        ref to_ty,
753
                        operand
754
                    } => {
qinsoon's avatar
qinsoon committed
755 756
                        trace!("instsel on CONVOP");

757
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
758 759 760
                        let ref op = ops[operand];

                        match operation {
qinsoon's avatar
[wip]  
qinsoon committed
761
                            // Truncate (from int to int)
qinsoon's avatar
qinsoon committed
762
                            op::ConvOp::TRUNC => {
qinsoon's avatar
qinsoon committed
763
                                let tmp_res = self.get_result_value(node);
qinsoon's avatar
vm.rs  
qinsoon committed
764
                                let to_ty_size = vm.get_backend_type_size(tmp_res.ty.id());
qinsoon's avatar
qinsoon committed
765

qinsoon's avatar
qinsoon committed
766 767
                                if self.match_ireg(op) {
                                    let tmp_op = self.emit_ireg(op, f_content, f_context, vm);
768

qinsoon's avatar
qinsoon committed
769
                                    // mov op -> result
qinsoon's avatar
qinsoon committed
770
                                    match to_ty_size {
771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790
                                        1 => {
                                            self.backend.emit_mov_r_r(&tmp_res, unsafe {
                                                &tmp_op.as_type(UINT8_TYPE.clone())
                                            })
                                        }
                                        2 => {
                                            self.backend.emit_mov_r_r(&tmp_res, unsafe {
                                                &tmp_op.as_type(UINT16_TYPE.clone())
                                            })
                                        }
                                        4 => {
                                            self.backend.emit_mov_r_r(&tmp_res, unsafe {
                                                &tmp_op.as_type(UINT32_TYPE.clone())
                                            })
                                        }
                                        8 => {
                                            self.backend.emit_mov_r_r(&tmp_res, unsafe {
                                                &tmp_op.as_type(UINT64_TYPE.clone())
                                            })
                                        }
791
                                        _ => panic!("unsupported int size: {}", to_ty_size)
qinsoon's avatar
qinsoon committed
792 793
                                    }
                                } else if self.match_ireg_ex(op) {
qinsoon's avatar
qinsoon committed
794
                                    let (op_l, _) = self.emit_ireg_ex(op, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
795 796

                                    match to_ty_size {
797 798 799
                                        1 | 2 => {
                                            self.backend.emit_movz_r_r(
                                                unsafe { &tmp_res.as_type(UINT32_TYPE.clone()) },
800
                                                &op_l
801 802
                                            )
                                        }
qinsoon's avatar
qinsoon committed
803
                                        4 | 8 => self.backend.emit_mov_r_r(&tmp_res, &op_l),
804
                                        _ => panic!("unsupported int size: {}", to_ty_size)
805
                                    }
qinsoon's avatar
qinsoon committed
806 807 808 809
                                } else {
                                    panic!("unexpected op (expect ireg): {}", op);
                                }
                            }
qinsoon's avatar
[wip]  
qinsoon committed
810
                            // Zero extend (from int to int)
qinsoon's avatar
qinsoon committed
811
                            op::ConvOp::ZEXT => {
812 813 814
                                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);
qinsoon's avatar
qinsoon committed
815

816
                                    // movz op -> result
qinsoon's avatar
vm.rs  
qinsoon committed
817
                                    let from_ty_size = vm.get_backend_type_size(from_ty.id());
818
                                    let to_ty_size = vm.get_backend_type_size(to_ty.id());
qinsoon's avatar
qinsoon committed
819

qinsoon's avatar
qinsoon committed
820 821
                                    // we treat int1 as int8, so it is possible
                                    // from_ty_size == to_ty_size == 1 byte
qinsoon's avatar
[wip]  
qinsoon committed
822 823
                                    assert!(from_ty_size <= to_ty_size);

824
                                    if from_ty_size != to_ty_size {
qinsoon's avatar
qinsoon committed
825 826 827
                                        match (from_ty_size, to_ty_size) {
                                            // int32 to int64
                                            (4, 8) => {
qinsoon's avatar
qinsoon committed
828 829
                                                // zero extend from 32 bits to 64 bits is
                                                // a mov instruction
qinsoon's avatar
qinsoon committed
830 831 832
                                                // x86 does not have movzlq (32 to 64)

                                                // tmp_op is int32, but tmp_res is int64
qinsoon's avatar
qinsoon committed
833 834
                                                // we want to force a 32-to-32 mov, so high bits
                                                // of the destination will be zeroed
835 836
                                                let tmp_res32 =
                                                    unsafe { tmp_res.as_type(UINT32_TYPE.clone()) };
qinsoon's avatar
qinsoon committed
837 838 839 840 841

                                                self.backend.emit_mov_r_r(&tmp_res32, &tmp_op);
                                            }
                                            // any int to int128
                                            (_, 16) => {
842 843
                                                let (res_l, res_h) =
                                                    self.split_int128(&tmp_res, f_context, vm);
qinsoon's avatar
qinsoon committed
844

845 846 847 848 849 850 851 852 853 854 855 856 857
                                                // use the temp as 64bit temp, mask it
                                                let tmp_op64 =
                                                    unsafe { &tmp_op.as_type(UINT64_TYPE.clone()) };
                                                self.emit_apply_mask(
                                                    &tmp_op64,
                                                    from_ty_size * 8,
                                                    f_context,
                                                    vm
                                                );

                                                // use temp as lower bits
                                                // clear higher bits
                                                self.backend.emit_mov_r_r(&res_l, &tmp_op64);
qinsoon's avatar
qinsoon committed
858 859
                                                self.backend.emit_mov_r_imm(&res_h, 0);
                                            }
qinsoon's avatar
[wip]  
qinsoon committed
860
                                            // other cases
qinsoon's avatar
qinsoon committed
861 862 863
                                            _ => {
                                                self.backend.emit_movz_r_r(&tmp_res, &tmp_op);
                                            }
qinsoon's avatar
qinsoon committed
864
                                        }
qinsoon's avatar
qinsoon committed
865
                                    } else {
866
                                        self.backend.emit_mov_r_r(&tmp_res, &tmp_op);
qinsoon's avatar
qinsoon committed
867
                                    }
868 869
                                } else {
                                    panic!("unexpected op (expect ireg): {}", op);
qinsoon's avatar
qinsoon committed
870
                                }
871
                            }
qinsoon's avatar
[wip]  
qinsoon committed
872
                            // Sign extend (from int to int)
qinsoon's avatar
qinsoon committed
873
                            op