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

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

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

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

47
use std::collections::HashMap;
48
49
use std::collections::LinkedList;

qinsoon's avatar
qinsoon committed
50
use std::any::Any;
51

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

qinsoon's avatar
qinsoon committed
59
60
    /// constant for converting unsigned integer to floating point
    static ref UITOFP_C0 : P<Value> = P(Value{
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
        hdr: MuEntityHeader::named(new_internal_id(), Mu("UITOFP_C0")),
        ty : LONG_4_TYPE.clone(),
        v  : Value_::Constant(Constant::List(vec![
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT32_TYPE.clone(),
                v : Value_::Constant(Constant::Int(1127219200u64))
            }),
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT32_TYPE.clone(),
                v : Value_::Constant(Constant::Int(1160773632u64))
            }),
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT32_TYPE.clone(),
                v : Value_::Constant(Constant::Int(0u64))
            }),
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT32_TYPE.clone(),
                v : Value_::Constant(Constant::Int(0u64))
            })
        ]))
    });

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

qinsoon's avatar
qinsoon committed
93
94
    /// constant for converting unsigned integer to floating point
    static ref UITOFP_C1 : P<Value> = P(Value{
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
        hdr: MuEntityHeader::named(new_internal_id(), Mu("UITOFP_C1")),
        ty : QUAD_2_TYPE.clone(),
        v  : Value_::Constant(Constant::List(vec![
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT64_TYPE.clone(),
                v : Value_::Constant(Constant::Int(4841369599423283200u64))
            }),
            P(Value{
                hdr: MuEntityHeader::unnamed(new_internal_id()),
                ty: UINT64_TYPE.clone(),
                v : Value_::Constant(Constant::Int(4985484787499139072u64))
            })
        ]))
    });
110

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

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

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

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

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

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

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

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

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

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

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

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

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

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

236
                        let ref cond = ops[cond];
qinsoon's avatar
qinsoon committed
237
                        if self.match_cmp_res(cond) {
qinsoon's avatar
qinsoon committed
238
                            // this branch2's cond is from a comparison result
239
                            trace!("emit cmp_res-branch2");
240
                            match self.emit_cmp_res(cond, f_content, f_context, vm) {
qinsoon's avatar
qinsoon committed
241
242
                                op::CmpOp::EQ => self.backend.emit_je(branch_target),
                                op::CmpOp::NE => self.backend.emit_jne(branch_target),
243
244
245
246
247
248
249
250
                                op::CmpOp::UGE => self.backend.emit_jae(branch_target),
                                op::CmpOp::UGT => self.backend.emit_ja(branch_target),
                                op::CmpOp::ULE => self.backend.emit_jbe(branch_target),
                                op::CmpOp::ULT => self.backend.emit_jb(branch_target),
                                op::CmpOp::SGE => self.backend.emit_jge(branch_target),
                                op::CmpOp::SGT => self.backend.emit_jg(branch_target),
                                op::CmpOp::SLE => self.backend.emit_jle(branch_target),
                                op::CmpOp::SLT => self.backend.emit_jl(branch_target),
qinsoon's avatar
qinsoon committed
251
252
253

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

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

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

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

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

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

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

qinsoon's avatar
qinsoon committed
304
                        // generate comparison
305
306
307
308
309
310
311
312
313
314
315
316
                        let cmpop = if self.match_cmp_res(cond) {
                            self.emit_cmp_res(cond, f_content, f_context, vm)
                        } else if self.match_ireg(cond) {
                            let tmp_cond = self.emit_ireg(cond, f_content, f_context, vm);
                            // emit: cmp cond_reg 1
                            self.backend.emit_cmp_imm_r(1, &tmp_cond);

                            EQ
                        } else {
                            panic!("expected cond to be ireg, found {}", cond)
                        };

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

322
                            // use cmov for 16/32/64bit integer
qinsoon's avatar
qinsoon committed
323
                            // use jcc  for 8 bit
324
                            // FIXME: could use 32bit register to implement 8bit select
qinsoon's avatar
qinsoon committed
325
326
327
                            match tmp_res.ty.get_int_length() {
                                // cmov
                                Some(len) if len > 8 => {
328
329
330
331
                                    let tmp_true =
                                        self.emit_ireg(true_val, f_content, f_context, vm);
                                    let tmp_false =
                                        self.emit_ireg(false_val, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
332
333
334
335
336

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

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

348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
                                        FOEQ | FUEQ => {
                                            self.backend.emit_cmove_r_r(&tmp_res, &tmp_true)
                                        }
                                        FONE | FUNE => {
                                            self.backend.emit_cmovne_r_r(&tmp_res, &tmp_true)
                                        }
                                        FOGT | FUGT => {
                                            self.backend.emit_cmova_r_r(&tmp_res, &tmp_true)
                                        }
                                        FOGE | FUGE => {
                                            self.backend.emit_cmovae_r_r(&tmp_res, &tmp_true)
                                        }
                                        FOLT | FULT => {
                                            self.backend.emit_cmovb_r_r(&tmp_res, &tmp_true)
                                        }
                                        FOLE | FULE => {
                                            self.backend.emit_cmovbe_r_r(&tmp_res, &tmp_true)
                                        }
qinsoon's avatar
qinsoon committed
366

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

qinsoon's avatar
qinsoon committed
563
564
565
566
567
568
569
                            // emit each branch
                            for &(case_op_index, ref case_dest) in branches {
                                let ref case_op = ops[case_op_index];

                                // process dest
                                self.process_dest(&ops, case_dest, f_content, f_context, vm);

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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