Research GitLab has introduced a user quota limitation. The new rule limits each user to have 50 Gb. The quota doesn't restrict group projects. If you have any concern with this, please talk to CECS Gitlab Admin at N110 (b) CSIT building.

inst_sel.rs 295 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
use std::collections::LinkedList;
49
use std::sync::Arc;
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: Arc::new(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) {
                                    let tmp_op = self.emit_ireg(op, f_content, f_context, vm);
                                    let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
815

816
                                    // movz op -> result
qinsoon's avatar
vm.rs  
qinsoon committed
817
                                    let from_ty_size = vm.get_backend_type_size(from_ty.id());
818
                                    let to_ty_size = vm.get_backend_type_size(to_ty.id());
qinsoon's avatar
qinsoon committed
819

qinsoon's avatar
qinsoon committed
820 821
                                    // we treat int1 as int8, so it is possible
                                    // from_ty_size == to_ty_size == 1 byte
qinsoon's avatar
[wip]  
qinsoon committed
822 823
                                    assert!(from_ty_size <= to_ty_size);

824
                                    if from_ty_size != to_ty_size {
qinsoon's avatar
qinsoon committed
825 826 827
                                        match (from_ty_size, to_ty_size) {
                                            // int32 to int64
                                            (4, 8) => {
qinsoon's avatar
qinsoon committed
828 829
                                                // zero extend from 32 bits to 64 bits is
                                                // a mov instruction
qinsoon's avatar
qinsoon committed
830 831 832
                                                // x86 does not have movzlq (32 to 64)

                                                // tmp_op is int32, but tmp_res is int64
qinsoon's avatar
qinsoon committed
833 834
                                                // we want to force a 32-to-32 mov, so high bits
                                                // of the destination will be zeroed
835 836
                                                let tmp_res32 =
                                                    unsafe { tmp_res.as_type(UINT32_TYPE.clone()) };
qinsoon's avatar
qinsoon committed
837 838 839 840 841

                                                self.backend.emit_mov_r_r(&tmp_res32, &tmp_op);
                                            }
                                            // any int to int128
                                            (_, 16) => {
842 843
                                                let (res_l, res_h) =
                                                    self.split_int128(&tmp_res, f_context, vm);
qinsoon's avatar
qinsoon committed
844

845 846 847 848 849 850 851 852 853 854 855 856 857
                                                // use the temp as 64bit temp, mask it
                                                let tmp_op64 =
                                                    unsafe { &tmp_op.as_type(UINT64_TYPE.clone()) };
                                                self.emit_apply_mask(
                                                    &tmp_op64,
                                                    from_ty_size * 8,
                                                    f_context,
                                                    vm
                                                );

                                                // use temp as lower bits
                                                // clear higher bits
                                                self.backend.emit_mov_r_r(&res_l, &tmp_op64);
qinsoon's avatar
qinsoon committed
858 859
                                                self.backend.emit_mov_r_imm(&res_h, 0);
                                            }
qinsoon's avatar
[wip]  
qinsoon committed
860
                                            // other cases
qinsoon's avatar
qinsoon committed
861 862 863
                                            _ => {
                                                self.backend.emit_movz_r_r(&tmp_res, &tmp_op);
                                            }
qinsoon's avatar
qinsoon committed
864
                                        }
qinsoon's avatar
qinsoon committed
865
                                    } else {
866
                                        self.backend.emit_mov_r_r(&tmp_res, &tmp_op);
qinsoon's avatar
qinsoon committed
867
                                    }
868 869
                                } else {
                                    panic!("unexpected op (expect ireg): {}", op);
qinsoon's avatar
qinsoon committed
870
                                }
871
                            }
qinsoon's avatar
[wip]  
qinsoon committed
872
                            // Sign extend (from int to int)