Research GitLab has introduced a user quota limitation. The new rule limits each user to have 50 Gb. The quota doesn't restrict group projects. If you have any concern with this, please talk to CECS Gitlab Admin at N110 (b) CSIT building.

inst_sel.rs 261 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
use compiler::backend::make_block_name;
qinsoon's avatar
qinsoon committed
37 38
use compiler::machine_code::CompiledFunction;
use compiler::frame::Frame;
39

40
use utils::math;
qinsoon's avatar
qinsoon committed
41
use utils::POINTER_SIZE;
42
use utils::BitSize;
43

44
use std::collections::HashMap;
45 46
use std::collections::LinkedList;

qinsoon's avatar
qinsoon committed
47
use std::any::Any;
48

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

qinsoon's avatar
qinsoon committed
56 57
    /// constant for converting unsigned integer to floating point
    static ref UITOFP_C0 : P<Value> = P(Value{
58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83
        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
84 85
    /// struct<int64, int64>
    static ref QUAD_2_TYPE : P<MuType> = P(
qinsoon's avatar
qinsoon committed
86 87
        MuType::new(new_internal_id(), MuType_::mustruct(Mu("quad_2"),
        vec![UINT64_TYPE.clone(); 2]))
88 89
    );

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

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

qinsoon's avatar
qinsoon committed
115
    /// constant for converting float to unsigned integer
qinsoon's avatar
qinsoon committed
116 117 118 119 120
    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))
    });
121 122
}

qinsoon's avatar
qinsoon committed
123 124 125 126
/// 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)
127
const INLINE_FASTPATH: bool = false;
128

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

qinsoon's avatar
qinsoon committed
134 135
    // information about the function being compiled
    /// ID of current function version being compiled
136
    current_fv_id: MuID,
137
    /// name of current function version being compiled
138
    current_fv_name: MuName,
139 140
    /// signature of current function being compiled
    current_sig: Option<P<MuFuncSig>>,
qinsoon's avatar
qinsoon committed
141
    /// used to create a unique callsite ID for current function
qinsoon's avatar
qinsoon committed
142
    current_callsite_id: usize,
qinsoon's avatar
qinsoon committed
143
    /// frame for current function
qinsoon's avatar
qinsoon committed
144
    current_frame: Option<Frame>,
qinsoon's avatar
qinsoon committed
145 146
    /// block that is currently being compiled
    /// the block may be created during instruction selection
qinsoon's avatar
qinsoon committed
147
    current_block: Option<MuName>,
qinsoon's avatar
qinsoon committed
148 149
    /// IR block that is currently being compiled
    /// use this block name to trace some information at IR level
150
    current_block_in_ir: Option<MuName>,
qinsoon's avatar
qinsoon committed
151
    /// start location of current function
qinsoon's avatar
qinsoon committed
152
    current_func_start: Option<ValueLocation>,
qinsoon's avatar
qinsoon committed
153 154 155 156
    /// 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
157
    current_callsites: LinkedList<(MuName, MuID, usize)>,
qinsoon's avatar
qinsoon committed
158
    // key: block id, val: block location
159
    current_exn_blocks: HashMap<MuID, MuName>,
qinsoon's avatar
qinsoon committed
160 161
    /// constants used in this function that are put to memory
    /// key: value id, val: constant value
162
    current_constants: HashMap<MuID, P<Value>>,
qinsoon's avatar
qinsoon committed
163 164
    /// constants used in this function that are put to memory
    /// key: value id, val: memory location
165
    current_constants_locs: HashMap<MuID, P<Value>>
166 167
}

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

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

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

            current_constants: HashMap::new(),
195
            current_constants_locs: HashMap::new()
196 197
        }
    }
qinsoon's avatar
qinsoon committed
198 199 200 201 202

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

    /// 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.
206 207 208 209 210
    fn instruction_select(
        &mut self,
        node: &'a TreeNode,
        f_content: &FunctionContent,
        f_context: &mut FunctionContext,
211
        vm: &VM
212
    ) {
213
        trace!("instsel on node#{} {}", node.id(), node);
214

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

227
                        let ref ops = inst.ops;
228 229
                        self.process_dest(&ops, fallthrough_dest, f_content, f_context, vm);
                        self.process_dest(&ops, branch_dest, f_content, f_context, vm);
230

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

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

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

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

276
                            let cond_reg = self.emit_ireg(cond, f_content, f_context, vm);
277

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

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

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

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

qinsoon's avatar
qinsoon committed
301
                        // generate comparison
302 303 304 305 306 307 308 309 310 311 312 313
                        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
314
                        // emit code to move values
qinsoon's avatar
qinsoon committed
315 316
                        if self.match_ireg(true_val) {
                            // moving integers/pointers
317
                            let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
318

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

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

                                    match cmpop {
334 335
                                        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
336
                                        SGE => self.backend.emit_cmovge_r_r(&tmp_res, &tmp_true),
337
                                        SGT => self.backend.emit_cmovg_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
338
                                        SLE => self.backend.emit_cmovle_r_r(&tmp_res, &tmp_true),
339
                                        SLT => self.backend.emit_cmovl_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
340
                                        UGE => self.backend.emit_cmovae_r_r(&tmp_res, &tmp_true),
341
                                        UGT => self.backend.emit_cmova_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
342
                                        ULE => self.backend.emit_cmovbe_r_r(&tmp_res, &tmp_true),
343
                                        ULT => self.backend.emit_cmovb_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
344

345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362
                                        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
363

qinsoon's avatar
qinsoon committed
364
                                        // FFALSE/FTRUE unimplemented
365
                                        _ => unimplemented!()
qinsoon's avatar
qinsoon committed
366 367
                                    }
                                }
qinsoon's avatar
qinsoon committed
368
                                // jcc - for 8-bits integer
qinsoon's avatar
qinsoon committed
369
                                _ => {
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
370 371 372
                                    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
373 374 375

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

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

qinsoon's avatar
qinsoon committed
394
                                        // FFALSE/FTRUE unimplemented
395
                                        _ => unimplemented!()
qinsoon's avatar
qinsoon committed
396 397
                                    }

398
                                    // finishing current block
qinsoon's avatar
qinsoon committed
399
                                    self.finish_block();
400 401

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

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

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

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
435 436 437
                            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");
438 439 440

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

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

459
                                _ => unimplemented!()
460 461 462
                            }

                            // finishing current block
qinsoon's avatar
qinsoon committed
463
                            self.finish_block();
464 465

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

                            // finishing current block
qinsoon's avatar
qinsoon committed
479
                            self.finish_block();
480 481

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

                            // blk_end:
qinsoon's avatar
qinsoon committed
494
                            self.start_block(blk_end.clone());
qinsoon's avatar
qinsoon committed
495 496 497
                        } else {
                            unimplemented!()
                        }
498
                    }
qinsoon's avatar
qinsoon committed
499

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

qinsoon's avatar
qinsoon committed
504
                        let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
505 506
                        assert!(tmp_res.ty.get_int_length().is_some());
                        assert!(tmp_res.ty.get_int_length().unwrap() == 1);
qinsoon's avatar
qinsoon committed
507

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

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

qinsoon's avatar
qinsoon committed
528
                            // FFALSE/FTRUE
529
                            _ => unimplemented!()
530 531 532
                        }
                    }

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

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

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

544 545 546
                    Instruction_::Switch {
                        cond,
                        ref default,
547
                        ref branches
548
                    } => {
qinsoon's avatar
qinsoon committed
549
                        trace!("instsel on SWITCH");
550
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
551 552 553 554 555
                        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
556 557 558 559
                            // 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
560 561 562 563 564 565 566
                            // 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);

567
                                let target = f_content.get_block(case_dest.target).name();
qinsoon's avatar
qinsoon committed
568 569 570 571 572

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

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

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

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

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

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

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

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

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

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

637 638 639 640
                        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
641 642
                        trace!("instsel on EXPRCCALL");

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

650
                        self.emit_c_call_ir(inst, data, None, node, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
651 652
                    }

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

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

670
                    Instruction_::Return(_) => {
qinsoon's avatar
qinsoon committed
671 672
                        trace!("instsel on RETURN");

673
                        self.emit_common_epilogue(inst, f_content, f_context, vm);
674

qinsoon's avatar
qinsoon committed
675
                        self.backend.emit_ret();
676 677
                    }

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

qinsoon's avatar
qinsoon committed
681
                        self.emit_binop(node, inst, op, op1, op2, f_content, f_context, vm);
682
                    }
qinsoon's avatar
qinsoon committed
683

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

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

qinsoon's avatar
qinsoon committed
689 690
                        let values = inst.value.as_ref().unwrap();
                        let mut status_value_index = 1;
qinsoon's avatar
qinsoon committed
691

692
                        // status flags only works with int operations
693
                        if RegGroup::get_from_value(&values[0]) == RegGroup::GPR {
qinsoon's avatar
qinsoon committed
694 695 696 697 698
                            // 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

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

704 705
                                self.backend.emit_sets_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
706

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

712 713
                                self.backend.emit_setz_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
714

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

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

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

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

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

754
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
755 756 757
                        let ref op = ops[operand];

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

qinsoon's avatar
qinsoon committed
763 764
                                if self.match_ireg(op) {
                                    let tmp_op = self.emit_ireg(op, f_content, f_context, vm);
765

qinsoon's avatar
qinsoon committed
766
                                    // mov op -> result
qinsoon's avatar
qinsoon committed
767
                                    match to_ty_size {
768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787
                                        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())
                                            })
                                        }
788
                                        _ => panic!("unsupported int size: {}", to_ty_size)
qinsoon's avatar
qinsoon committed
789 790
                                    }
                                } else if self.match_ireg_ex(op) {
qinsoon's avatar
qinsoon committed
791
                                    let (op_l, _) = self.emit_ireg_ex(op, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
792 793

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

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

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

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

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

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

842 843 844 845 846 847 848 849 850 851 852 853 854
                                                // 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
855 856
                                                self.backend.emit_mov_r_imm(&res_h, 0);
                                            }
qinsoon's avatar
[wip]  
qinsoon committed
857
                                            // other cases
qinsoon's avatar
qinsoon committed
858 859 860
                                            _ => {
                                                self.backend.emit_movz_r_r(&tmp_res, &tmp_op);
                                            }
qinsoon's avatar
qinsoon committed
861
                                        }
qinsoon's avatar
qinsoon committed
862
                                    } else {
863
                                        self.backend.emit_mov_r_r(&tmp_res, &tmp_op);
qinsoon's avatar
qinsoon committed
864
                                    }
865 866
                                } else {
                                    panic!("unexpected op (expect ireg): {}", op);
qinsoon's avatar
qinsoon committed
867
                                }
868
                            }
qinsoon's avatar
[wip]  
qinsoon committed
869
                            // Sign extend (from int to int)
qinsoon's avatar
qinsoon committed
870
                            op::ConvOp::SEXT => {
871 872 873
                                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);