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

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

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

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

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

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

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

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

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

229
                        let branch_target = f_content.get_block(branch_dest.target).name();
230

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

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

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

274
                            let cond_reg = self.emit_ireg(cond, f_content, f_context, vm);
275

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

457
                                _ => unimplemented!()
458
459
460
                            }

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

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

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

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

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

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

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

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

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

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

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

535
                        self.process_dest(&ops, dest, f_content, f_context, vm);
536

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

671
                        self.emit_common_epilogue(inst, f_content, f_context, vm);
672

qinsoon's avatar
qinsoon committed
673
                        self.backend.emit_ret();
674
675
                    }

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

811
                                    // movz op -> result
qinsoon's avatar
vm.rs    
qinsoon committed