To protect your data, the CISO officer has suggested users to enable GitLab 2FA as soon as possible.

inst_sel.rs 263 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;
qinsoon's avatar
qinsoon committed
33
use compiler::backend::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

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

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

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

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

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

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

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

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

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

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

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

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

                                        // FIXME: ideally we should not create new blocks in instruction selection
                                        // see Issue #6
qinsoon's avatar
qinsoon committed
182
            current_func_start: None,
183
            current_callsites: LinkedList::new(),
184
185
186
            current_exn_blocks: HashMap::new(),

            current_constants: HashMap::new(),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
187
            current_constants_locs: HashMap::new(),
188
189
        }
    }
qinsoon's avatar
qinsoon committed
190
191
192
193
194

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

    /// 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.
198
199
200
201
202
    fn instruction_select(
        &mut self,
        node: &'a TreeNode,
        f_content: &FunctionContent,
        f_context: &mut FunctionContext,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
203
        vm: &VM,
204
    ) {
205
        trace!("instsel on node#{} {}", node.id(), node);
206

qinsoon's avatar
qinsoon committed
207
        match node.v {
208
209
            TreeNode_::Instruction(ref inst) => {
                match inst.v {
210
211
212
213
214
215
                    Instruction_::Branch2 {
                        cond,
                        ref true_dest,
                        ref false_dest,
                        ..
                    } => {
qinsoon's avatar
qinsoon committed
216
                        trace!("instsel on BRANCH2");
217
218
                        // 'branch_if_true' == true, we emit cjmp the same as CmpOp  (je  for EQ, jne for NE)
                        // 'branch_if_true' == false, we emit opposite cjmp as CmpOp (jne for EQ, je  for NE)
qinsoon's avatar
qinsoon committed
219
220
                        // FIXME: we should move this to machine independent code
                        // e.g. as a subpass after trace scheduling, see Issue#27
221
                        let (fallthrough_dest, branch_dest, branch_if_true) = {
222
                            // get current block and next block in trace (fallthrough block)
223
                            let cur_block = f_content.get_block_by_name(
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
224
                                self.current_block_in_ir.as_ref().unwrap().clone(),
225
226
227
                            );
                            let next_block_in_trace =
                                cur_block.control_flow.get_hottest_succ().unwrap();
228
229

                            if next_block_in_trace == true_dest.target {
230
231
232
                                (true_dest, false_dest, false)
                            } else {
                                (false_dest, true_dest, true)
233
                            }
234
                        };
235

236
                        let ref ops = inst.ops;
237
238
                        self.process_dest(&ops, fallthrough_dest, f_content, f_context, vm);
                        self.process_dest(&ops, branch_dest, f_content, f_context, vm);
239

240
                        let branch_target = f_content.get_block(branch_dest.target).name();
241

242
                        let ref cond = ops[cond];
qinsoon's avatar
qinsoon committed
243
                        if self.match_cmp_res(cond) {
qinsoon's avatar
qinsoon committed
244
                            // this branch2's cond is from a comparison result
245
                            trace!("emit cmp_res-branch2");
246
                            match self.emit_cmp_res(cond, f_content, f_context, vm) {
247
248
249
250
251
252
                                op::CmpOp::EQ => {
                                    if branch_if_true {
                                        self.backend.emit_je(branch_target);
                                    } else {
                                        self.backend.emit_jne(branch_target);
                                    }
253
                                }
254
255
256
257
258
259
                                op::CmpOp::NE => {
                                    if branch_if_true {
                                        self.backend.emit_jne(branch_target);
                                    } else {
                                        self.backend.emit_je(branch_target);
                                    }
260
                                }
261
262
263
264
265
266
                                op::CmpOp::UGE => {
                                    if branch_if_true {
                                        self.backend.emit_jae(branch_target);
                                    } else {
                                        self.backend.emit_jb(branch_target);
                                    }
267
                                }
268
269
270
271
272
273
                                op::CmpOp::UGT => {
                                    if branch_if_true {
                                        self.backend.emit_ja(branch_target);
                                    } else {
                                        self.backend.emit_jbe(branch_target);
                                    }
274
                                }
275
276
277
278
279
280
                                op::CmpOp::ULE => {
                                    if branch_if_true {
                                        self.backend.emit_jbe(branch_target);
                                    } else {
                                        self.backend.emit_ja(branch_target);
                                    }
281
                                }
282
283
284
285
286
287
                                op::CmpOp::ULT => {
                                    if branch_if_true {
                                        self.backend.emit_jb(branch_target);
                                    } else {
                                        self.backend.emit_jae(branch_target);
                                    }
288
                                }
289
290
291
292
293
294
                                op::CmpOp::SGE => {
                                    if branch_if_true {
                                        self.backend.emit_jge(branch_target);
                                    } else {
                                        self.backend.emit_jl(branch_target);
                                    }
295
                                }
296
297
298
299
300
301
                                op::CmpOp::SGT => {
                                    if branch_if_true {
                                        self.backend.emit_jg(branch_target);
                                    } else {
                                        self.backend.emit_jle(branch_target);
                                    }
302
                                }
303
304
305
306
307
308
                                op::CmpOp::SLE => {
                                    if branch_if_true {
                                        self.backend.emit_jle(branch_target);
                                    } else {
                                        self.backend.emit_jg(branch_target);
                                    }
309
                                }
310
311
312
313
314
315
                                op::CmpOp::SLT => {
                                    if branch_if_true {
                                        self.backend.emit_jl(branch_target);
                                    } else {
                                        self.backend.emit_jge(branch_target);
                                    }
316
                                }
qinsoon's avatar
qinsoon committed
317
318
319
320
321
322
323
324

                                // floating point
                                op::CmpOp::FOEQ | op::CmpOp::FUEQ => {
                                    if branch_if_true {
                                        self.backend.emit_je(branch_target);
                                    } else {
                                        self.backend.emit_jne(branch_target);
                                    }
325
                                }
qinsoon's avatar
qinsoon committed
326
327
328
329
330
331
                                op::CmpOp::FONE | op::CmpOp::FUNE => {
                                    if branch_if_true {
                                        self.backend.emit_jne(branch_target);
                                    } else {
                                        self.backend.emit_je(branch_target);
                                    }
332
                                }
qinsoon's avatar
qinsoon committed
333
334
335
336
337
338
                                op::CmpOp::FOGT | op::CmpOp::FUGT => {
                                    if branch_if_true {
                                        self.backend.emit_ja(branch_target);
                                    } else {
                                        self.backend.emit_jbe(branch_target);
                                    }
339
                                }
qinsoon's avatar
qinsoon committed
340
341
342
343
344
345
                                op::CmpOp::FOGE | op::CmpOp::FUGE => {
                                    if branch_if_true {
                                        self.backend.emit_jae(branch_target);
                                    } else {
                                        self.backend.emit_jb(branch_target);
                                    }
346
                                }
qinsoon's avatar
qinsoon committed
347
348
349
350
351
352
                                op::CmpOp::FOLT | op::CmpOp::FULT => {
                                    if branch_if_true {
                                        self.backend.emit_jb(branch_target);
                                    } else {
                                        self.backend.emit_jae(branch_target);
                                    }
353
                                }
qinsoon's avatar
qinsoon committed
354
355
356
357
358
359
                                op::CmpOp::FOLE | op::CmpOp::FULE => {
                                    if branch_if_true {
                                        self.backend.emit_jbe(branch_target);
                                    } else {
                                        self.backend.emit_ja(branch_target);
                                    }
360
                                }
qinsoon's avatar
qinsoon committed
361

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
362
                                _ => unimplemented!(),
qinsoon's avatar
qinsoon committed
363
364
                            }
                        } else if self.match_ireg(cond) {
qinsoon's avatar
qinsoon committed
365
366
                            // this branch2 cond is a temporary with value, or an instruction that
                            // emits a temporary
qinsoon's avatar
qinsoon committed
367
                            trace!("emit ireg-branch2");
368

369
                            let cond_reg = self.emit_ireg(cond, f_content, f_context, vm);
370

qinsoon's avatar
qinsoon committed
371
                            // emit: cmp cond_reg 1
qinsoon's avatar
qinsoon committed
372
                            self.backend.emit_cmp_imm_r(1, &cond_reg);
qinsoon's avatar
qinsoon committed
373
                            // emit: je #branch_dest
374
375
376
377
378
                            if branch_if_true {
                                self.backend.emit_je(branch_target);
                            } else {
                                self.backend.emit_jne(branch_target);
                            }
qinsoon's avatar
qinsoon committed
379
                        } else {
qinsoon's avatar
qinsoon committed
380
                            panic!("unexpected cond in BRANCH2: {}", cond)
381
                        }
382
383

                        // it is possible that the fallthrough block is scheduled somewhere else
qinsoon's avatar
qinsoon committed
384
385
                        // we need to explicitly jump to it (this jump will get eliminated in
                        // peephole pass if the fallthrough block immediate follows the jump)
386
387
                        self.finish_block();

388
389
                        let fallthrough_temp_block =
                            make_block_name(&self.current_fv_name, node.id(), "branch_fallthrough");
390
391
                        self.start_block(fallthrough_temp_block);

392
393
                        let fallthrough_target =
                            f_content.get_block(fallthrough_dest.target).name();
394
                        self.backend.emit_jmp(fallthrough_target);
395
                    }
qinsoon's avatar
qinsoon committed
396

397
398
399
                    Instruction_::Select {
                        cond,
                        true_val,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
400
                        false_val,
401
                    } => {
qinsoon's avatar
qinsoon committed
402
403
                        use ast::op::CmpOp::*;

qinsoon's avatar
qinsoon committed
404
                        trace!("instsel on SELECT");
405
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
406
407
408
409
410

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

qinsoon's avatar
qinsoon committed
411
                        // generate comparison
412
413
414
415
416
417
418
419
420
421
422
423
                        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
424
                        // emit code to move values
qinsoon's avatar
qinsoon committed
425
426
                        if self.match_ireg(true_val) {
                            // moving integers/pointers
427
                            let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
428

429
                            // use cmov for 16/32/64bit integer
qinsoon's avatar
qinsoon committed
430
                            // use jcc  for 8 bit
431
                            // FIXME: could use 32bit register to implement 8bit select
qinsoon's avatar
qinsoon committed
432
433
434
                            match tmp_res.ty.get_int_length() {
                                // cmov
                                Some(len) if len > 8 => {
435
436
437
438
                                    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
439
440
441
442
443

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

                                    match cmpop {
444
445
                                        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
446
                                        SGE => self.backend.emit_cmovge_r_r(&tmp_res, &tmp_true),
447
                                        SGT => self.backend.emit_cmovg_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
448
                                        SLE => self.backend.emit_cmovle_r_r(&tmp_res, &tmp_true),
449
                                        SLT => self.backend.emit_cmovl_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
450
                                        UGE => self.backend.emit_cmovae_r_r(&tmp_res, &tmp_true),
451
                                        UGT => self.backend.emit_cmova_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
452
                                        ULE => self.backend.emit_cmovbe_r_r(&tmp_res, &tmp_true),
453
                                        ULT => self.backend.emit_cmovb_r_r(&tmp_res, &tmp_true),
qinsoon's avatar
qinsoon committed
454

455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
                                        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
473

qinsoon's avatar
qinsoon committed
474
                                        // FFALSE/FTRUE unimplemented
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
475
                                        _ => unimplemented!(),
qinsoon's avatar
qinsoon committed
476
477
                                    }
                                }
qinsoon's avatar
qinsoon committed
478
                                // jcc - for 8-bits integer
qinsoon's avatar
qinsoon committed
479
                                _ => {
480
481
482
                                    let blk_true = make_block_name(
                                        &self.current_fv_name,
                                        node.id(),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
483
                                        "select_true",
484
485
486
487
                                    );
                                    let blk_false = make_block_name(
                                        &self.current_fv_name,
                                        node.id(),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
488
                                        "select_false",
489
490
491
492
                                    );
                                    let blk_end = make_block_name(
                                        &self.current_fv_name,
                                        node.id(),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
493
                                        "select_end",
494
                                    );
qinsoon's avatar
qinsoon committed
495
496
497

                                    // jump to blk_true if true
                                    match cmpop {
498
499
                                        EQ => self.backend.emit_je(blk_true.clone()),
                                        NE => self.backend.emit_jne(blk_true.clone()),
qinsoon's avatar
qinsoon committed
500
                                        SGE => self.backend.emit_jge(blk_true.clone()),
501
                                        SGT => self.backend.emit_jg(blk_true.clone()),
qinsoon's avatar
qinsoon committed
502
                                        SLE => self.backend.emit_jle(blk_true.clone()),
503
                                        SLT => self.backend.emit_jl(blk_true.clone()),
qinsoon's avatar
qinsoon committed
504
                                        UGE => self.backend.emit_jae(blk_true.clone()),
505
                                        UGT => self.backend.emit_ja(blk_true.clone()),
qinsoon's avatar
qinsoon committed
506
                                        ULE => self.backend.emit_jbe(blk_true.clone()),
507
                                        ULT => self.backend.emit_jb(blk_true.clone()),
qinsoon's avatar
qinsoon committed
508

509
                                        FOEQ | FUEQ => self.backend.emit_je(blk_true.clone()),
qinsoon's avatar
qinsoon committed
510
                                        FONE | FUNE => self.backend.emit_jne(blk_true.clone()),
511
                                        FOGT | FUGT => self.backend.emit_ja(blk_true.clone()),
qinsoon's avatar
qinsoon committed
512
                                        FOGE | FUGE => self.backend.emit_jae(blk_true.clone()),
513
                                        FOLT | FULT => self.backend.emit_jb(blk_true.clone()),
qinsoon's avatar
qinsoon committed
514
515
                                        FOLE | FULE => self.backend.emit_jbe(blk_true.clone()),

qinsoon's avatar
qinsoon committed
516
                                        // FFALSE/FTRUE unimplemented
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
517
                                        _ => unimplemented!(),
qinsoon's avatar
qinsoon committed
518
519
                                    }

520
                                    // finishing current block
qinsoon's avatar
qinsoon committed
521
                                    self.finish_block();
522
523

                                    // blk_false:
qinsoon's avatar
qinsoon committed
524
                                    self.start_block(blk_false.clone());
qinsoon's avatar
qinsoon committed
525
                                    // mov false result here
526
527
528
529
530
                                    self.emit_move_node_to_value(
                                        &tmp_res,
                                        &false_val,
                                        f_content,
                                        f_context,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
531
                                        vm,
532
                                    );
qinsoon's avatar
qinsoon committed
533
534
535
                                    // jmp to end
                                    self.backend.emit_jmp(blk_end.clone());
                                    // finishing current block
qinsoon's avatar
qinsoon committed
536
                                    self.finish_block();
qinsoon's avatar
qinsoon committed
537
538

                                    // blk_true:
qinsoon's avatar
qinsoon committed
539
                                    self.start_block(blk_true.clone());
qinsoon's avatar
qinsoon committed
540
                                    // mov true value -> result
541
542
543
544
545
                                    self.emit_move_node_to_value(
                                        &tmp_res,
                                        &true_val,
                                        f_content,
                                        f_context,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
546
                                        vm,
547
                                    );
548
                                    self.finish_block();
qinsoon's avatar
qinsoon committed
549
550

                                    // blk_end:
551
                                    self.start_block(blk_end.clone());
qinsoon's avatar
qinsoon committed
552
                                }
qinsoon's avatar
qinsoon committed
553
                            }
554
555
556
                        } else if self.match_fpreg(true_val) {
                            let tmp_res = self.get_result_value(node);

557
558
559
560
561
562
                            let blk_true =
                                make_block_name(&self.current_fv_name, node.id(), "select_true");
                            let blk_false =
                                make_block_name(&self.current_fv_name, node.id(), "select_false");
                            let blk_end =
                                make_block_name(&self.current_fv_name, node.id(), "select_end");
563
564
565

                            // jump to blk_true if true
                            match cmpop {
566
567
                                EQ => self.backend.emit_je(blk_true.clone()),
                                NE => self.backend.emit_jne(blk_true.clone()),
568
                                SGE => self.backend.emit_jge(blk_true.clone()),
569
                                SGT => self.backend.emit_jg(blk_true.clone()),
570
                                SLE => self.backend.emit_jle(blk_true.clone()),
571
                                SLT => self.backend.emit_jl(blk_true.clone()),
572
                                UGE => self.backend.emit_jae(blk_true.clone()),
573
                                UGT => self.backend.emit_ja(blk_true.clone()),
574
                                ULE => self.backend.emit_jbe(blk_true.clone()),
575
                                ULT => self.backend.emit_jb(blk_true.clone()),
576

577
                                FOEQ | FUEQ => self.backend.emit_je(blk_true.clone()),
578
                                FONE | FUNE => self.backend.emit_jne(blk_true.clone()),
579
                                FOGT | FUGT => self.backend.emit_ja(blk_true.clone()),
580
                                FOGE | FUGE => self.backend.emit_jae(blk_true.clone()),
581
                                FOLT | FULT => self.backend.emit_jb(blk_true.clone()),
582
583
                                FOLE | FULE => self.backend.emit_jbe(blk_true.clone()),

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
584
                                _ => unimplemented!(),
585
586
587
                            }

                            // finishing current block
qinsoon's avatar
qinsoon committed
588
                            self.finish_block();
589
590

                            // blk_false:
qinsoon's avatar
qinsoon committed
591
                            self.start_block(blk_false.clone());
592
                            // mov false result here
593
594
595
596
597
                            self.emit_move_node_to_value(
                                &tmp_res,
                                &false_val,
                                f_content,
                                f_context,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
598
                                vm,
599
                            );
600
601
602
603
                            // jmp to end
                            self.backend.emit_jmp(blk_end.clone());

                            // finishing current block
qinsoon's avatar
qinsoon committed
604
                            self.finish_block();
605
606

                            // blk_true:
qinsoon's avatar
qinsoon committed
607
                            self.start_block(blk_true.clone());
608
                            // mov true value -> result
609
610
611
612
613
                            self.emit_move_node_to_value(
                                &tmp_res,
                                &true_val,
                                f_content,
                                f_context,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
614
                                vm,
615
                            );
qinsoon's avatar
qinsoon committed
616
                            self.finish_block();
617
618

                            // blk_end:
qinsoon's avatar
qinsoon committed
619
                            self.start_block(blk_end.clone());
qinsoon's avatar
qinsoon committed
620
621
622
                        } else {
                            unimplemented!()
                        }
623
                    }
qinsoon's avatar
qinsoon committed
624

qinsoon's avatar
qinsoon committed
625
                    Instruction_::CmpOp(_, _, _) => {
qinsoon's avatar
qinsoon committed
626
                        use ast::op::CmpOp::*;
qinsoon's avatar
qinsoon committed
627
                        trace!("instsel on CMPOP");
628

qinsoon's avatar
qinsoon committed
629
                        let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
630
631
                        assert!(tmp_res.ty.get_int_length().is_some());
                        assert!(tmp_res.ty.get_int_length().unwrap() == 1);
qinsoon's avatar
qinsoon committed
632

633
                        // set byte to result
qinsoon's avatar
qinsoon committed
634
                        match self.emit_cmp_res(node, f_content, f_context, vm) {
635
636
                            EQ => self.backend.emit_sete_r(&tmp_res),
                            NE => self.backend.emit_setne_r(&tmp_res),
637
                            SGE => self.backend.emit_setge_r(&tmp_res),
638
                            SGT => self.backend.emit_setg_r(&tmp_res),
639
                            SLE => self.backend.emit_setle_r(&tmp_res),
640
                            SLT => self.backend.emit_setl_r(&tmp_res),
641
                            UGE => self.backend.emit_setae_r(&tmp_res),
642
                            UGT => self.backend.emit_seta_r(&tmp_res),
643
                            ULE => self.backend.emit_setbe_r(&tmp_res),
644
                            ULT => self.backend.emit_setb_r(&tmp_res),
645

646
                            FOEQ | FUEQ => self.backend.emit_sete_r(&tmp_res),
647
                            FONE | FUNE => self.backend.emit_setne_r(&tmp_res),
648
                            FOGT | FUGT => self.backend.emit_seta_r(&tmp_res),
649
                            FOGE | FUGE => self.backend.emit_setae_r(&tmp_res),
650
                            FOLT | FULT => self.backend.emit_setb_r(&tmp_res),
651
                            FOLE | FULE => self.backend.emit_setbe_r(&tmp_res),
qinsoon's avatar
qinsoon committed
652

qinsoon's avatar
qinsoon committed
653
                            // FFALSE/FTRUE
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
654
                            _ => unimplemented!(),
655
656
657
                        }
                    }

qinsoon's avatar
qinsoon committed
658
                    Instruction_::Branch1(ref dest) => {
qinsoon's avatar
qinsoon committed
659
                        trace!("instsel on BRANCH1");
660
                        let ref ops = inst.ops;
661

662
                        self.process_dest(&ops, dest, f_content, f_context, vm);
663

664
                        let target = f_content.get_block(dest.target).name();
665
                        // jmp
qinsoon's avatar
qinsoon committed
666
                        self.backend.emit_jmp(target);
667
                    }
qinsoon's avatar
qinsoon committed
668

669
670
671
                    Instruction_::Switch {
                        cond,
                        ref default,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
672
                        ref branches,
673
                    } => {
qinsoon's avatar
qinsoon committed
674
                        trace!("instsel on SWITCH");
675
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
676
677
678
679
680
                        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
681
682
683
684
                            // 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
685
686
687
688
689
690
691
                            // 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);

692
                                let target = f_content.get_block(case_dest.target).name();
qinsoon's avatar
qinsoon committed
693
694
695
696
697

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

                                    // cmp case cond
qinsoon's avatar
qinsoon committed
698
                                    self.backend.emit_cmp_imm_r(imm, &tmp_cond);
qinsoon's avatar
qinsoon committed
699
700
701
                                    // je dest
                                    self.backend.emit_je(target);
                                } else if self.match_ireg(case_op) {
702
703
                                    let tmp_case_op =
                                        self.emit_ireg(case_op, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
704
705

                                    // cmp case cond
qinsoon's avatar
qinsoon committed
706
                                    self.backend.emit_cmp_r_r(&tmp_case_op, &tmp_cond);
qinsoon's avatar
qinsoon committed
707
708
709
                                    // je dest
                                    self.backend.emit_je(target);
                                } else {
710
711
712
713
                                    panic!(
                                        "expecting ireg cond to be either iimm or ireg: {}",
                                        cond
                                    );
qinsoon's avatar
qinsoon committed
714
                                }
715
716

                                self.finish_block();
717
718
719
                                let block_name = make_block_name(
                                    &self.current_fv_name,
                                    node.id(),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
720
                                    format!("switch_not_met_case_{}", case_op_index).as_str(),
721
                                );
722
                                self.start_block(block_name);
qinsoon's avatar
qinsoon committed
723
724
725
726
                            }

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

728
                            let default_target = f_content.get_block(default.target).name();
qinsoon's avatar
qinsoon committed
729
730
                            self.backend.emit_jmp(default_target);
                        } else {
qinsoon's avatar
qinsoon committed
731
732
                            // other EQ-comparable types, e.g. floating point
                            unimplemented!()
qinsoon's avatar
qinsoon committed
733
734
                        }
                    }
735
736

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

qinsoon's avatar
qinsoon committed
739
                        if is_abort {
qinsoon's avatar
qinsoon committed
740
741
742
                            // if any exception throws from the callee,
                            // we should abort execution, otherwise rethrow the exception
                            // FIXME: implement is_abort
qinsoon's avatar
qinsoon committed
743
                            unimplemented!()
744
                        }
745

qinsoon's avatar
qinsoon committed
746
747
748
749
                        self.emit_mu_call(
                            inst, // inst: &Instruction,
                            data, // calldata: &CallData,
                            None, // resumption: Option<&ResumptionData>,
750
751
752
                            node, // cur_node: &TreeNode,
                            f_content,
                            f_context,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
753
                            vm,
754
755
756
757
758
                        );
                    }

                    Instruction_::Call {
                        ref data,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
759
                        ref resume,
760
                    } => {
qinsoon's avatar
qinsoon committed
761
762
                        trace!("instsel on CALL");

763
764
765
766
                        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
767
768
                        trace!("instsel on EXPRCCALL");

qinsoon's avatar
qinsoon committed
769
                        if is_abort {
qinsoon's avatar
qinsoon committed
770
771
772
                            // if any exception throws from the callee,
                            // we should abort execution, otherwise rethrow the exception
                            // FIXME: implement is_abort
qinsoon's avatar
qinsoon committed
773
774
775
                            unimplemented!()
                        }

776
                        self.emit_c_call_ir(inst, data, None, node, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
777
778
                    }

779
780
                    Instruction_::CCall {
                        ref data,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
781
                        ref resume,
782
                    } => {
qinsoon's avatar
qinsoon committed
783
784
                        trace!("instsel on CCALL");

qinsoon's avatar
qinsoon committed
785
786
787
788
789
                        self.emit_c_call_ir(
                            inst,
                            data,
                            Some(resume),
                            node,
790
791
                            f_content,
                            f_context,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
792
                            vm,
793
                        );
qinsoon's avatar
qinsoon committed
794
                    }
795

796
                    Instruction_::Return(_) => {
qinsoon's avatar
qinsoon committed
797
798
                        trace!("instsel on RETURN");

799
                        self.emit_common_epilogue(inst, f_content, f_context, vm);
800

qinsoon's avatar
qinsoon committed
801
                        self.backend.emit_ret();
802
803
                    }

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

qinsoon's avatar
qinsoon committed
807
                        self.emit_binop(node, inst, op, op1, op2, f_content, f_context, vm);
808
                    }
qinsoon's avatar
qinsoon committed
809

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

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

qinsoon's avatar
qinsoon committed
815
816
                        let values = inst.value.as_ref().unwrap();
                        let mut status_value_index = 1;
qinsoon's avatar
qinsoon committed
817

818
                        // status flags only works with int operations
819
                        if RegGroup::get_from_value(&values[0]) == RegGroup::GPR {
qinsoon's avatar
qinsoon committed
820
821
822
823
824
                            // 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

825
826
827
828
                            // negative flag
                            if status.flag_n {
                                let tmp_status = values[status_value_index].clone();
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
829

830
831
                                self.backend.emit_sets_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
832

833
834
835
836
                            // zero flag
                            if status.flag_z {
                                let tmp_status = values[status_value_index].clone();
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
837

838
839
                                self.backend.emit_setz_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
840

841
842
843
844
                            // unsigned overflow
                            if status.flag_c {
                                let tmp_status = values[status_value_index].clone();
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
845

846
847
848
849
                                match op {
                                    BinOp::Add | BinOp::Sub | BinOp::Mul => {
                                        self.backend.emit_setb_r8(&tmp_status);
                                    }
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
850
                                    _ => panic!("Only Add/Sub/Mul has #C flag"),
qinsoon's avatar
qinsoon committed
851
852
                                }
                            }
qinsoon's avatar
qinsoon committed
853

854
855
856
                            // signed overflow
                            if status.flag_v {
                                let tmp_status = values[status_value_index].clone();
qinsoon's avatar
qinsoon committed
857

858
859
860
861
                                match op {
                                    BinOp