GitLab will be upgraded on 31 Jan 2023 from 2.00 pm (AEDT) to 3.00 pm (AEDT). During the update, GitLab and Mattermost services will not be available. If you have any concerns with this, please talk to us at N110 (b) CSIT building.

inst_sel.rs 262 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;
qinsoon's avatar
qinsoon committed
31
use compiler::backend::BackendType;
32
use compiler::backend::RegGroup;
33
use compiler::PROLOGUE_BLOCK_NAME;
qinsoon's avatar
qinsoon committed
34
35
36
use compiler::backend::x86_64;
use compiler::backend::x86_64::CodeGenerator;
use compiler::backend::x86_64::ASMCodeGen;
37
use compiler::backend::make_block_name;
qinsoon's avatar
qinsoon committed
38
39
use compiler::machine_code::CompiledFunction;
use compiler::frame::Frame;
40

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

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

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

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

qinsoon's avatar
qinsoon committed
57
58
    /// constant for converting unsigned integer to floating point
    static ref UITOFP_C0 : P<Value> = P(Value{
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
84
        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
85
86
    /// struct<int64, int64>
    static ref QUAD_2_TYPE : P<MuType> = P(
qinsoon's avatar
qinsoon committed
87
88
        MuType::new(new_internal_id(), MuType_::mustruct(Mu("quad_2"),
        vec![UINT64_TYPE.clone(); 2]))
89
90
    );

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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