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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

qinsoon's avatar
qinsoon committed
312
                        // emit code to move values
qinsoon's avatar
qinsoon committed
313
314
                        if self.match_ireg(true_val) {
                            // moving integers/pointers
315
                            let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
316

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

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

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

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

qinsoon's avatar
qinsoon committed
362
                                        // FFALSE/FTRUE unimplemented
363
                                        _ => unimplemented!()
qinsoon's avatar
qinsoon committed
364
365
                                    }
                                }
qinsoon's avatar
qinsoon committed
366
                                // jcc - for 8-bits integer
qinsoon's avatar
qinsoon committed
367
                                _ => {
368
369
370
                                    let blk_true = make_block_name(
                                        &self.current_fv_name,
                                        node.id(),
371
                                        "select_true"
372
373
374
375
                                    );
                                    let blk_false = make_block_name(
                                        &self.current_fv_name,
                                        node.id(),
376
                                        "select_false"
377
378
379
380
                                    );
                                    let blk_end = make_block_name(
                                        &self.current_fv_name,
                                        node.id(),
381
                                        "select_end"
382
                                    );
qinsoon's avatar
qinsoon committed
383
384
385

                                    // jump to blk_true if true
                                    match cmpop {
386
387
                                        EQ => self.backend.emit_je(blk_true.clone()),
                                        NE => self.backend.emit_jne(blk_true.clone()),
qinsoon's avatar
qinsoon committed
388
                                        SGE => self.backend.emit_jge(blk_true.clone()),
389
                                        SGT => self.backend.emit_jg(blk_true.clone()),
qinsoon's avatar
qinsoon committed
390
                                        SLE => self.backend.emit_jle(blk_true.clone()),
391
                                        SLT => self.backend.emit_jl(blk_true.clone()),
qinsoon's avatar
qinsoon committed
392
                                        UGE => self.backend.emit_jae(blk_true.clone()),
393
                                        UGT => self.backend.emit_ja(blk_true.clone()),
qinsoon's avatar
qinsoon committed
394
                                        ULE => self.backend.emit_jbe(blk_true.clone()),
395
                                        ULT => self.backend.emit_jb(blk_true.clone()),
qinsoon's avatar
qinsoon committed
396

397
                                        FOEQ | FUEQ => self.backend.emit_je(blk_true.clone()),
qinsoon's avatar
qinsoon committed
398
                                        FONE | FUNE => self.backend.emit_jne(blk_true.clone()),
399
                                        FOGT | FUGT => self.backend.emit_ja(blk_true.clone()),
qinsoon's avatar
qinsoon committed
400
                                        FOGE | FUGE => self.backend.emit_jae(blk_true.clone()),
401
                                        FOLT | FULT => self.backend.emit_jb(blk_true.clone()),
qinsoon's avatar
qinsoon committed
402
403
                                        FOLE | FULE => self.backend.emit_jbe(blk_true.clone()),

qinsoon's avatar
qinsoon committed
404
                                        // FFALSE/FTRUE unimplemented
405
                                        _ => unimplemented!()
qinsoon's avatar
qinsoon committed
406
407
                                    }

408
                                    // finishing current block
qinsoon's avatar
qinsoon committed
409
                                    self.finish_block();
410
411

                                    // blk_false:
qinsoon's avatar
qinsoon committed
412
                                    self.start_block(blk_false.clone());
qinsoon's avatar
qinsoon committed
413
                                    // mov false result here
414
415
416
417
418
                                    self.emit_move_node_to_value(
                                        &tmp_res,
                                        &false_val,
                                        f_content,
                                        f_context,
419
                                        vm
420
                                    );
qinsoon's avatar
qinsoon committed
421
422
423
                                    // jmp to end
                                    self.backend.emit_jmp(blk_end.clone());
                                    // finishing current block
qinsoon's avatar
qinsoon committed
424
                                    self.finish_block();
qinsoon's avatar
qinsoon committed
425
426

                                    // blk_true:
qinsoon's avatar
qinsoon committed
427
                                    self.start_block(blk_true.clone());
qinsoon's avatar
qinsoon committed
428
                                    // mov true value -> result
429
430
431
432
433
                                    self.emit_move_node_to_value(
                                        &tmp_res,
                                        &true_val,
                                        f_content,
                                        f_context,
434
                                        vm
435
                                    );
436
                                    self.finish_block();
qinsoon's avatar
qinsoon committed
437
438

                                    // blk_end:
439
                                    self.start_block(blk_end.clone());
qinsoon's avatar
qinsoon committed
440
                                }
qinsoon's avatar
qinsoon committed
441
                            }
442
443
444
                        } else if self.match_fpreg(true_val) {
                            let tmp_res = self.get_result_value(node);

445
446
447
448
449
450
                            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");
451
452
453

                            // jump to blk_true if true
                            match cmpop {
454
455
                                EQ => self.backend.emit_je(blk_true.clone()),
                                NE => self.backend.emit_jne(blk_true.clone()),
456
                                SGE => self.backend.emit_jge(blk_true.clone()),
457
                                SGT => self.backend.emit_jg(blk_true.clone()),
458
                                SLE => self.backend.emit_jle(blk_true.clone()),
459
                                SLT => self.backend.emit_jl(blk_true.clone()),
460
                                UGE => self.backend.emit_jae(blk_true.clone()),
461
                                UGT => self.backend.emit_ja(blk_true.clone()),
462
                                ULE => self.backend.emit_jbe(blk_true.clone()),
463
                                ULT => self.backend.emit_jb(blk_true.clone()),
464

465
                                FOEQ | FUEQ => self.backend.emit_je(blk_true.clone()),
466
                                FONE | FUNE => self.backend.emit_jne(blk_true.clone()),
467
                                FOGT | FUGT => self.backend.emit_ja(blk_true.clone()),
468
                                FOGE | FUGE => self.backend.emit_jae(blk_true.clone()),
469
                                FOLT | FULT => self.backend.emit_jb(blk_true.clone()),
470
471
                                FOLE | FULE => self.backend.emit_jbe(blk_true.clone()),

472
                                _ => unimplemented!()
473
474
475
                            }

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

                            // blk_false:
qinsoon's avatar
qinsoon committed
479
                            self.start_block(blk_false.clone());
480
                            // mov false result here
481
482
483
484
485
                            self.emit_move_node_to_value(
                                &tmp_res,
                                &false_val,
                                f_content,
                                f_context,
486
                                vm
487
                            );
488
489
490
491
                            // jmp to end
                            self.backend.emit_jmp(blk_end.clone());

                            // finishing current block
qinsoon's avatar
qinsoon committed
492
                            self.finish_block();
493
494

                            // blk_true:
qinsoon's avatar
qinsoon committed
495
                            self.start_block(blk_true.clone());
496
                            // mov true value -> result
497
498
499
500
501
                            self.emit_move_node_to_value(
                                &tmp_res,
                                &true_val,
                                f_content,
                                f_context,
502
                                vm
503
                            );
qinsoon's avatar
qinsoon committed
504
                            self.finish_block();
505
506

                            // blk_end:
qinsoon's avatar
qinsoon committed
507
                            self.start_block(blk_end.clone());
qinsoon's avatar
qinsoon committed
508
509
510
                        } else {
                            unimplemented!()
                        }
511
                    }
qinsoon's avatar
qinsoon committed
512

qinsoon's avatar
qinsoon committed
513
                    Instruction_::CmpOp(_, _, _) => {
qinsoon's avatar
qinsoon committed
514
                        use ast::op::CmpOp::*;
qinsoon's avatar
qinsoon committed
515
                        trace!("instsel on CMPOP");
516

qinsoon's avatar
qinsoon committed
517
                        let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
518
519
                        assert!(tmp_res.ty.get_int_length().is_some());
                        assert!(tmp_res.ty.get_int_length().unwrap() == 1);
qinsoon's avatar
qinsoon committed
520

521
                        // set byte to result
qinsoon's avatar
qinsoon committed
522
                        match self.emit_cmp_res(node, f_content, f_context, vm) {
523
524
                            EQ => self.backend.emit_sete_r(&tmp_res),
                            NE => self.backend.emit_setne_r(&tmp_res),
525
                            SGE => self.backend.emit_setge_r(&tmp_res),
526
                            SGT => self.backend.emit_setg_r(&tmp_res),
527
                            SLE => self.backend.emit_setle_r(&tmp_res),
528
                            SLT => self.backend.emit_setl_r(&tmp_res),
529
                            UGE => self.backend.emit_setae_r(&tmp_res),
530
                            UGT => self.backend.emit_seta_r(&tmp_res),
531
                            ULE => self.backend.emit_setbe_r(&tmp_res),
532
                            ULT => self.backend.emit_setb_r(&tmp_res),
533

534
                            FOEQ | FUEQ => self.backend.emit_sete_r(&tmp_res),
535
                            FONE | FUNE => self.backend.emit_setne_r(&tmp_res),
536
                            FOGT | FUGT => self.backend.emit_seta_r(&tmp_res),
537
                            FOGE | FUGE => self.backend.emit_setae_r(&tmp_res),
538
                            FOLT | FULT => self.backend.emit_setb_r(&tmp_res),
539
                            FOLE | FULE => self.backend.emit_setbe_r(&tmp_res),
qinsoon's avatar
qinsoon committed
540

qinsoon's avatar
qinsoon committed
541
                            // FFALSE/FTRUE
542
                            _ => unimplemented!()
543
544
545
                        }
                    }

qinsoon's avatar
qinsoon committed
546
                    Instruction_::Branch1(ref dest) => {
qinsoon's avatar
qinsoon committed
547
                        trace!("instsel on BRANCH1");
548
                        let ref ops = inst.ops;
549

550
                        self.process_dest(&ops, dest, f_content, f_context, vm);
551

552
                        let target = f_content.get_block(dest.target).name();
553
                        // jmp
qinsoon's avatar
qinsoon committed
554
                        self.backend.emit_jmp(target);
555
                    }
qinsoon's avatar
qinsoon committed
556

557
558
559
                    Instruction_::Switch {
                        cond,
                        ref default,
560
                        ref branches
561
                    } => {
qinsoon's avatar
qinsoon committed
562
                        trace!("instsel on SWITCH");
563
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
564
565
566
567
568
                        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
569
570
571
572
                            // 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
573
574
575
576
577
578
579
                            // 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);

580
                                let target = f_content.get_block(case_dest.target).name();
qinsoon's avatar
qinsoon committed
581
582
583
584
585

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

                                    // cmp case cond
qinsoon's avatar
qinsoon committed
586
                                    self.backend.emit_cmp_imm_r(imm, &tmp_cond);
qinsoon's avatar
qinsoon committed
587
588
589
                                    // je dest
                                    self.backend.emit_je(target);
                                } else if self.match_ireg(case_op) {
590
591
                                    let tmp_case_op =
                                        self.emit_ireg(case_op, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
592
593

                                    // cmp case cond
qinsoon's avatar
qinsoon committed
594
                                    self.backend.emit_cmp_r_r(&tmp_case_op, &tmp_cond);
qinsoon's avatar
qinsoon committed
595
596
597
                                    // je dest
                                    self.backend.emit_je(target);
                                } else {
598
599
600
601
                                    panic!(
                                        "expecting ireg cond to be either iimm or ireg: {}",
                                        cond
                                    );
qinsoon's avatar
qinsoon committed
602
                                }
603
604

                                self.finish_block();
605
606
607
                                let block_name = make_block_name(
                                    &self.current_fv_name,
                                    node.id(),
608
                                    format!("switch_not_met_case_{}", case_op_index).as_str()
609
                                );
610
                                self.start_block(block_name);
qinsoon's avatar
qinsoon committed
611
612
613
614
                            }

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

616
                            let default_target = f_content.get_block(default.target).name();
qinsoon's avatar
qinsoon committed
617
618
                            self.backend.emit_jmp(default_target);
                        } else {
qinsoon's avatar
qinsoon committed
619
620
                            // other EQ-comparable types, e.g. floating point
                            unimplemented!()
qinsoon's avatar
qinsoon committed
621
622
                        }
                    }
623
624

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

qinsoon's avatar
qinsoon committed
627
                        if is_abort {
qinsoon's avatar
qinsoon committed
628
629
630
                            // if any exception throws from the callee,
                            // we should abort execution, otherwise rethrow the exception
                            // FIXME: implement is_abort
qinsoon's avatar
qinsoon committed
631
                            unimplemented!()
632
                        }
633

qinsoon's avatar
qinsoon committed
634
635
636
637
                        self.emit_mu_call(
                            inst, // inst: &Instruction,
                            data, // calldata: &CallData,
                            None, // resumption: Option<&ResumptionData>,
638
639
640
                            node, // cur_node: &TreeNode,
                            f_content,
                            f_context,
641
                            vm
642
643
644
645
646
                        );
                    }

                    Instruction_::Call {
                        ref data,
647
                        ref resume
648
                    } => {
qinsoon's avatar
qinsoon committed
649
650
                        trace!("instsel on CALL");

651
652
653
654
                        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
655
656
                        trace!("instsel on EXPRCCALL");

qinsoon's avatar
qinsoon committed
657
                        if is_abort {
qinsoon's avatar
qinsoon committed
658
659
660
                            // if any exception throws from the callee,
                            // we should abort execution, otherwise rethrow the exception
                            // FIXME: implement is_abort
qinsoon's avatar
qinsoon committed
661
662
663
                            unimplemented!()
                        }

664
                        self.emit_c_call_ir(inst, data, None, node, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
665
666
                    }

667
668
                    Instruction_::CCall {
                        ref data,
669
                        ref resume
670
                    } => {
qinsoon's avatar
qinsoon committed
671
672
                        trace!("instsel on CCALL");

qinsoon's avatar
qinsoon committed
673
674
675
676
677
                        self.emit_c_call_ir(
                            inst,
                            data,
                            Some(resume),
                            node,
678
679
                            f_content,
                            f_context,
680
                            vm
681
                        );
qinsoon's avatar
qinsoon committed
682
                    }
683

684
                    Instruction_::Return(_) => {
qinsoon's avatar
qinsoon committed
685
686
                        trace!("instsel on RETURN");

687
                        self.emit_common_epilogue(inst, f_content, f_context, vm);
688

qinsoon's avatar
qinsoon committed
689
                        self.backend.emit_ret();
690
691
                    }

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

qinsoon's avatar
qinsoon committed
695
                        self.emit_binop(node, inst, op, op1, op2, f_content, f_context, vm);
696
                    }
qinsoon's avatar
qinsoon committed
697

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

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

qinsoon's avatar
qinsoon committed
703
704
                        let values = inst.value.as_ref().unwrap();
                        let mut status_value_index = 1;
qinsoon's avatar
qinsoon committed
705

706
                        // status flags only works with int operations
707
                        if RegGroup::get_from_value(&values[0]) == RegGroup::GPR {
qinsoon's avatar
qinsoon committed
708
709
710
711
712
                            // 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

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

718
719
                                self.backend.emit_sets_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
720

721
722
723
724
                            // zero flag
                            if status.flag_z {
                                let tmp_status = values[status_value_index].clone();
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
725

726
727
                                self.backend.emit_setz_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
728

729
730
731
732
                            // unsigned overflow
                            if status.flag_c {
                                let tmp_status = values[status_value_index].clone();
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
733

734
735
736
737
                                match op {
                                    BinOp::Add | BinOp::Sub | BinOp::Mul => {
                                        self.backend.emit_setb_r8(&tmp_status);
                                    }
738
                                    _ => panic!("Only Add/Sub/Mul has #C flag")
qinsoon's avatar
qinsoon committed
739
740
                                }
                            }
qinsoon's avatar
qinsoon committed
741

742
743
744
                            // signed overflow
                            if status.flag_v {
                                let tmp_status = values[status_value_index].clone();
qinsoon's avatar
qinsoon committed
745

746
747
748
749
                                match op {
                                    BinOp::Add | BinOp::Sub | BinOp::Mul => {
                                        self.backend.emit_seto_r8(&tmp_status);
                                    }
750
                                    _ => panic!("Only Add/Sub/Mul has #V flag")
qinsoon's avatar
qinsoon committed
751
752
                                }
                            }
753
754
755
                        } else if RegGroup::get_from_value(&values[0]) == RegGroup::GPREX {
                            unimplemented!()
                        } else {
qinsoon's avatar
[wip]    
qinsoon committed
756
                            panic!("only int operations allow binop status flags")
757
758
                        }
                    }
qinsoon's avatar
qinsoon committed
759

760
761
762
763
                    Instruction_::ConvOp {
                        operation,
                        ref from_ty,
                        ref to_ty,
764
                        operand
765
                    } => {
qinsoon's avatar
qinsoon committed
766
767
                        trace!("instsel on CONVOP");

768
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
769
770
771
                        let ref op = ops[operand];

                        match operation {
qinsoon's avatar
[wip]    
qinsoon committed
772
                            // Truncate (from int to int)
qinsoon's avatar
qinsoon committed
773
                            op::ConvOp::TRUNC => {
qinsoon's avatar
qinsoon committed
774
                                let tmp_res = self.get_result_value(node);
qinsoon's avatar
vm.rs    
qinsoon committed
775
                                let to_ty_size = vm.get_backend_type_size(tmp_res.ty.id());
qinsoon's avatar
qinsoon committed
776

qinsoon's avatar
qinsoon committed
777
778
                                if self.match_ireg(op) {
                                    let tmp_op = self.emit_ireg(op, f_content, f_context, vm);
779

qinsoon's avatar
qinsoon committed
780
                                    // mov op -> result
qinsoon's avatar
qinsoon committed
781
                                    match to_ty_size {
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
                                        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())
                                            })
                                        }
802
                                        _ => panic!("unsupported int size: {}", to_ty_size)
qinsoon's avatar
qinsoon committed
803
804
                                    }
                                } else if self.match_ireg_ex(op) {
qinsoon's avatar
qinsoon committed
805
                                    let (op_l, _) = self.emit_ireg_ex(op, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
806
807

                                    match to_ty_size {
808
809
810
                                        1 | 2 => {
                                            self.backend.emit_movz_r_r(
                                                unsafe { &tmp_res.as_type(UINT32_TYPE.clone()) },
811
                                                &op_l
812
813
                                            )
                                        }
qinsoon's avatar
qinsoon committed
814
                                        4 | 8 => self.backend.emit_mov_r_r(&tmp_res, &op_l),
815
                                        _ => panic!("unsupported int size: {}", to_ty_size)
816
                                    }
qinsoon's avatar
qinsoon committed
817
818