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 370 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.

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

qinsoon's avatar
qinsoon committed
28
use compiler::backend::x86_64;
29
30
use compiler::backend::x86_64::callconv;
use compiler::backend::x86_64::callconv::CallConvResult;
31
32
use compiler::backend::x86_64::*;
use compiler::backend::*;
qinsoon's avatar
qinsoon committed
33
use compiler::frame::Frame;
34
35
36
use compiler::machine_code::CompiledFunction;
use compiler::CompilerPass;
use compiler::PROLOGUE_BLOCK_NAME;
37

38
use utils::math;
39
use utils::{BitSize, ByteSize};
40
use utils::{POINTER_SIZE, WORD_SIZE};
41

42
use std::any::Any;
43
use std::collections::HashMap;
44
use std::collections::LinkedList;
45
use std::sync::Arc;
46

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

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

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

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

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

qinsoon's avatar
qinsoon committed
121
122
/// for some IR instructions, we need a call into runtime
/// for efficiency, we may emit runtime fastpath directly in assembly
123
124
125
//  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)
126
const INLINE_FASTPATH: bool = false;
127

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

qinsoon's avatar
qinsoon committed
133
134
    // information about the function being compiled
    /// ID of current function version being compiled
135
    current_fv_id: MuID,
136
    /// name of current function version being compiled
137
    current_fv_name: MuName,
138
139
    /// signature of current function being compiled
    current_sig: Option<P<MuFuncSig>>,
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>,
152
153
154
155
156
    /// 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
157
    current_callsites: LinkedList<(MuName, MuID, usize)>,
qinsoon's avatar
qinsoon committed
158
    // key: block id, val: block location
159
    current_exn_blocks: HashMap<MuID, MuName>,
qinsoon's avatar
qinsoon committed
160
161
    /// constants used in this function that are put to memory
    /// key: value id, val: constant value
162
    current_constants: HashMap<MuID, P<Value>>,
qinsoon's avatar
qinsoon committed
163
164
    /// constants used in this function that are put to memory
    /// key: value id, val: memory location
165
    current_constants_locs: HashMap<MuID, P<Value>>
166
167
}

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

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

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

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

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

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

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

230
                        let ref ops = inst.ops;
231
232
233
234
235
236
237
238
239
240
241
242
243
244
                        self.process_dest(
                            &ops,
                            fallthrough_dest,
                            f_content,
                            f_context,
                            vm
                        );
                        self.process_dest(
                            &ops,
                            branch_dest,
                            f_content,
                            f_context,
                            vm
                        );
245

246
247
                        let branch_target =
                            f_content.get_block(branch_dest.target.id()).name();
248

249
                        let ref cond = ops[cond];
qinsoon's avatar
qinsoon committed
250
                        if self.match_cmp_res(cond) {
qinsoon's avatar
qinsoon committed
251
                            // this branch2's cond is from a comparison result
252
                            trace!("emit cmp_res-branch2");
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
                            match self
                                .emit_cmp_res(cond, f_content, f_context, vm)
                            {
                                op::CmpOp::EQ => {
                                    self.backend.emit_je(branch_target)
                                }
                                op::CmpOp::NE => {
                                    self.backend.emit_jne(branch_target)
                                }
                                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
286
287
288

                                // floating point
                                op::CmpOp::FOEQ | op::CmpOp::FUEQ => {
qinsoon's avatar
qinsoon committed
289
                                    self.backend.emit_je(branch_target)
290
                                }
qinsoon's avatar
qinsoon committed
291
                                op::CmpOp::FONE | op::CmpOp::FUNE => {
qinsoon's avatar
qinsoon committed
292
                                    self.backend.emit_jne(branch_target)
293
                                }
qinsoon's avatar
qinsoon committed
294
                                op::CmpOp::FOGT | op::CmpOp::FUGT => {
qinsoon's avatar
qinsoon committed
295
                                    self.backend.emit_ja(branch_target)
296
                                }
qinsoon's avatar
qinsoon committed
297
                                op::CmpOp::FOGE | op::CmpOp::FUGE => {
qinsoon's avatar
qinsoon committed
298
                                    self.backend.emit_jae(branch_target)
299
                                }
qinsoon's avatar
qinsoon committed
300
                                op::CmpOp::FOLT | op::CmpOp::FULT => {
qinsoon's avatar
qinsoon committed
301
                                    self.backend.emit_jb(branch_target)
302
                                }
qinsoon's avatar
qinsoon committed
303
                                op::CmpOp::FOLE | op::CmpOp::FULE => {
qinsoon's avatar
qinsoon committed
304
                                    self.backend.emit_jbe(branch_target)
305
                                }
qinsoon's avatar
qinsoon committed
306

307
                                _ => unimplemented!()
qinsoon's avatar
qinsoon committed
308
309
                            }
                        } else if self.match_ireg(cond) {
310
311
                            // this branch2 cond is a temporary with value, or
                            // an instruction that
qinsoon's avatar
qinsoon committed
312
                            // emits a temporary
qinsoon's avatar
qinsoon committed
313
                            trace!("emit ireg-branch2");
314

315
316
                            let cond_reg =
                                self.emit_ireg(cond, f_content, f_context, vm);
317

qinsoon's avatar
qinsoon committed
318
                            // emit: cmp cond_reg 1
qinsoon's avatar
qinsoon committed
319
                            self.backend.emit_cmp_imm_r(1, &cond_reg);
qinsoon's avatar
qinsoon committed
320
                            // emit: je #branch_dest
321
                            self.backend.emit_je(branch_target);
qinsoon's avatar
qinsoon committed
322
                        } else {
qinsoon's avatar
qinsoon committed
323
                            panic!("unexpected cond in BRANCH2: {}", cond)
324
                        }
325
                    }
qinsoon's avatar
qinsoon committed
326

327
328
329
                    Instruction_::Select {
                        cond,
                        true_val,
330
                        false_val
331
                    } => {
qinsoon's avatar
qinsoon committed
332
333
                        use ast::op::CmpOp::*;

qinsoon's avatar
qinsoon committed
334
                        trace!("instsel on SELECT");
335
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
336
337
338
339
340

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

qinsoon's avatar
qinsoon committed
341
                        // generate comparison
342
343
344
                        let cmpop = if self.match_cmp_res(cond) {
                            self.emit_cmp_res(cond, f_content, f_context, vm)
                        } else if self.match_ireg(cond) {
345
346
                            let tmp_cond =
                                self.emit_ireg(cond, f_content, f_context, vm);
347
348
349
350
351
352
353
354
                            // 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
355
                        // emit code to move values
qinsoon's avatar
qinsoon committed
356
357
                        if self.match_ireg(true_val) {
                            // moving integers/pointers
358
                            let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
359

360
                            // use cmov for 16/32/64bit integer
qinsoon's avatar
qinsoon committed
361
                            // use jcc  for 8 bit
362
363
                            // FIXME: could use 32bit register to implement 8bit
                            // select
qinsoon's avatar
qinsoon committed
364
365
366
                            match tmp_res.ty.get_int_length() {
                                // cmov
                                Some(len) if len > 8 => {
367
368
369
370
371
372
                                    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
373
374

                                    // mov tmp_false -> tmp_res
375
376
                                    self.backend
                                        .emit_mov_r_r(&tmp_res, &tmp_false);
qinsoon's avatar
qinsoon committed
377
378

                                    match cmpop {
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
                                        EQ => self.backend.emit_cmove_r_r(
                                            &tmp_res, &tmp_true
                                        ),
                                        NE => self.backend.emit_cmovne_r_r(
                                            &tmp_res, &tmp_true
                                        ),
                                        SGE => self.backend.emit_cmovge_r_r(
                                            &tmp_res, &tmp_true
                                        ),
                                        SGT => self.backend.emit_cmovg_r_r(
                                            &tmp_res, &tmp_true
                                        ),
                                        SLE => self.backend.emit_cmovle_r_r(
                                            &tmp_res, &tmp_true
                                        ),
                                        SLT => self.backend.emit_cmovl_r_r(
                                            &tmp_res, &tmp_true
                                        ),
                                        UGE => self.backend.emit_cmovae_r_r(
                                            &tmp_res, &tmp_true
                                        ),
                                        UGT => self.backend.emit_cmova_r_r(
                                            &tmp_res, &tmp_true
                                        ),
                                        ULE => self.backend.emit_cmovbe_r_r(
                                            &tmp_res, &tmp_true
                                        ),
                                        ULT => self.backend.emit_cmovb_r_r(
                                            &tmp_res, &tmp_true
                                        ),
qinsoon's avatar
qinsoon committed
409

410
                                        FOEQ | FUEQ => {
411
412
413
                                            self.backend.emit_cmove_r_r(
                                                &tmp_res, &tmp_true
                                            )
414
415
                                        }
                                        FONE | FUNE => {
416
417
418
                                            self.backend.emit_cmovne_r_r(
                                                &tmp_res, &tmp_true
                                            )
419
420
                                        }
                                        FOGT | FUGT => {
421
422
423
                                            self.backend.emit_cmova_r_r(
                                                &tmp_res, &tmp_true
                                            )
424
425
                                        }
                                        FOGE | FUGE => {
426
427
428
                                            self.backend.emit_cmovae_r_r(
                                                &tmp_res, &tmp_true
                                            )
429
430
                                        }
                                        FOLT | FULT => {
431
432
433
                                            self.backend.emit_cmovb_r_r(
                                                &tmp_res, &tmp_true
                                            )
434
435
                                        }
                                        FOLE | FULE => {
436
437
438
                                            self.backend.emit_cmovbe_r_r(
                                                &tmp_res, &tmp_true
                                            )
439
                                        }
qinsoon's avatar
qinsoon committed
440

qinsoon's avatar
qinsoon committed
441
                                        // FFALSE/FTRUE unimplemented
442
                                        _ => unimplemented!()
qinsoon's avatar
qinsoon committed
443
444
                                    }
                                }
qinsoon's avatar
qinsoon committed
445
                                // jcc - for 8-bits integer
qinsoon's avatar
qinsoon committed
446
                                _ => {
447
448
449
450
451
452
453
454
455
456
457
458
                                    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
459
460
461

                                    // jump to blk_true if true
                                    match cmpop {
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
                                        EQ => self
                                            .backend
                                            .emit_je(blk_true.clone()),
                                        NE => self
                                            .backend
                                            .emit_jne(blk_true.clone()),
                                        SGE => self
                                            .backend
                                            .emit_jge(blk_true.clone()),
                                        SGT => self
                                            .backend
                                            .emit_jg(blk_true.clone()),
                                        SLE => self
                                            .backend
                                            .emit_jle(blk_true.clone()),
                                        SLT => self
                                            .backend
                                            .emit_jl(blk_true.clone()),
                                        UGE => self
                                            .backend
                                            .emit_jae(blk_true.clone()),
                                        UGT => self
                                            .backend
                                            .emit_ja(blk_true.clone()),
                                        ULE => self
                                            .backend
                                            .emit_jbe(blk_true.clone()),
                                        ULT => self
                                            .backend
                                            .emit_jb(blk_true.clone()),

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

qinsoon's avatar
qinsoon committed
512
                                        // FFALSE/FTRUE unimplemented
513
                                        _ => unimplemented!()
qinsoon's avatar
qinsoon committed
514
515
                                    }

516
                                    // finishing current block
qinsoon's avatar
qinsoon committed
517
                                    self.finish_block();
518
519

                                    // blk_false:
qinsoon's avatar
qinsoon committed
520
                                    self.start_block(blk_false.clone());
qinsoon's avatar
qinsoon committed
521
                                    // mov false result here
522
                                    self.emit_move_node_to_value(
523
524
                                        &tmp_res, &false_val, f_content,
                                        f_context, vm
525
                                    );
qinsoon's avatar
qinsoon committed
526
527
528
                                    // jmp to end
                                    self.backend.emit_jmp(blk_end.clone());
                                    // finishing current block
qinsoon's avatar
qinsoon committed
529
                                    self.finish_block();
qinsoon's avatar
qinsoon committed
530
531

                                    // blk_true:
qinsoon's avatar
qinsoon committed
532
                                    self.start_block(blk_true.clone());
qinsoon's avatar
qinsoon committed
533
                                    // mov true value -> result
534
                                    self.emit_move_node_to_value(
535
536
                                        &tmp_res, &true_val, f_content,
                                        f_context, vm
537
                                    );
538
                                    self.finish_block();
qinsoon's avatar
qinsoon committed
539
540

                                    // blk_end:
541
                                    self.start_block(blk_end.clone());
qinsoon's avatar
qinsoon committed
542
                                }
qinsoon's avatar
qinsoon committed
543
                            }
544
545
546
                        } else if self.match_fpreg(true_val) {
                            let tmp_res = self.get_result_value(node);

547
548
549
550
551
552
                            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");
553
554
555

                            // jump to blk_true if true
                            match cmpop {
556
557
                                EQ => self.backend.emit_je(blk_true.clone()),
                                NE => self.backend.emit_jne(blk_true.clone()),
558
                                SGE => self.backend.emit_jge(blk_true.clone()),
559
                                SGT => self.backend.emit_jg(blk_true.clone()),
560
                                SLE => self.backend.emit_jle(blk_true.clone()),
561
                                SLT => self.backend.emit_jl(blk_true.clone()),
562
                                UGE => self.backend.emit_jae(blk_true.clone()),
563
                                UGT => self.backend.emit_ja(blk_true.clone()),
564
                                ULE => self.backend.emit_jbe(blk_true.clone()),
565
                                ULT => self.backend.emit_jb(blk_true.clone()),
566

567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
                                FOEQ | FUEQ => {
                                    self.backend.emit_je(blk_true.clone())
                                }
                                FONE | FUNE => {
                                    self.backend.emit_jne(blk_true.clone())
                                }
                                FOGT | FUGT => {
                                    self.backend.emit_ja(blk_true.clone())
                                }
                                FOGE | FUGE => {
                                    self.backend.emit_jae(blk_true.clone())
                                }
                                FOLT | FULT => {
                                    self.backend.emit_jb(blk_true.clone())
                                }
                                FOLE | FULE => {
                                    self.backend.emit_jbe(blk_true.clone())
                                }
585

586
                                _ => unimplemented!()
587
588
589
                            }

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

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

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

                            // blk_true:
qinsoon's avatar
qinsoon committed
605
                            self.start_block(blk_true.clone());
606
                            // mov true value -> result
607
                            self.emit_move_node_to_value(
608
                                &tmp_res, &true_val, f_content, f_context, vm
609
                            );
qinsoon's avatar
qinsoon committed
610
                            self.finish_block();
611
612

                            // blk_end:
qinsoon's avatar
qinsoon committed
613
                            self.start_block(blk_end.clone());
qinsoon's avatar
qinsoon committed
614
615
616
                        } else {
                            unimplemented!()
                        }
617
                    }
qinsoon's avatar
qinsoon committed
618

qinsoon's avatar
qinsoon committed
619
                    Instruction_::CmpOp(_, _, _) => {
qinsoon's avatar
qinsoon committed
620
                        use ast::op::CmpOp::*;
qinsoon's avatar
qinsoon committed
621
                        trace!("instsel on CMPOP");
622

qinsoon's avatar
qinsoon committed
623
                        let tmp_res = self.get_result_value(node);
qinsoon's avatar
qinsoon committed
624
625
                        assert!(tmp_res.ty.get_int_length().is_some());
                        assert!(tmp_res.ty.get_int_length().unwrap() == 1);
qinsoon's avatar
qinsoon committed
626

627
                        // set byte to result
628
629
                        match self.emit_cmp_res(node, f_content, f_context, vm)
                        {
630
631
                            EQ => self.backend.emit_sete_r(&tmp_res),
                            NE => self.backend.emit_setne_r(&tmp_res),
632
                            SGE => self.backend.emit_setge_r(&tmp_res),
633
                            SGT => self.backend.emit_setg_r(&tmp_res),
634
                            SLE => self.backend.emit_setle_r(&tmp_res),
635
                            SLT => self.backend.emit_setl_r(&tmp_res),
636
                            UGE => self.backend.emit_setae_r(&tmp_res),
637
                            UGT => self.backend.emit_seta_r(&tmp_res),
638
                            ULE => self.backend.emit_setbe_r(&tmp_res),
639
                            ULT => self.backend.emit_setb_r(&tmp_res),
640

641
                            FOEQ | FUEQ => self.backend.emit_sete_r(&tmp_res),
642
                            FONE | FUNE => self.backend.emit_setne_r(&tmp_res),
643
                            FOGT | FUGT => self.backend.emit_seta_r(&tmp_res),
644
                            FOGE | FUGE => self.backend.emit_setae_r(&tmp_res),
645
                            FOLT | FULT => self.backend.emit_setb_r(&tmp_res),
646
                            FOLE | FULE => self.backend.emit_setbe_r(&tmp_res),
qinsoon's avatar
qinsoon committed
647

qinsoon's avatar
qinsoon committed
648
                            // FFALSE/FTRUE
649
                            _ => unimplemented!()
650
651
652
                        }
                    }

qinsoon's avatar
qinsoon committed
653
                    Instruction_::Branch1(ref dest) => {
qinsoon's avatar
qinsoon committed
654
                        trace!("instsel on BRANCH1");
655
                        let ref ops = inst.ops;
656

657
                        self.process_dest(&ops, dest, f_content, f_context, vm);
658

659
660
                        let target =
                            f_content.get_block(dest.target.id()).name();
661
                        // jmp
qinsoon's avatar
qinsoon committed
662
                        self.backend.emit_jmp(target);
663
                    }
qinsoon's avatar
qinsoon committed
664

665
666
667
                    Instruction_::Switch {
                        cond,
                        ref default,
668
                        ref branches
669
                    } => {
qinsoon's avatar
qinsoon committed
670
                        trace!("instsel on SWITCH");
671
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
672
673
674
                        let ref cond = ops[cond];

                        if self.match_ireg(cond) {
675
676
                            let tmp_cond =
                                self.emit_ireg(cond, f_content, f_context, vm);
qinsoon's avatar
qinsoon committed
677

678
679
680
681
682
                            // 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
683

qinsoon's avatar
qinsoon committed
684
685
686
687
688
                            // emit each branch
                            for &(case_op_index, ref case_dest) in branches {
                                let ref case_op = ops[case_op_index];

                                // process dest
689
690
691
                                self.process_dest(
                                    &ops, case_dest, f_content, f_context, vm
                                );
qinsoon's avatar
qinsoon committed
692

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

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

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

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

                                self.finish_block();
722
                                let block_name = make_block_name(
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
723
                                    &node.name(),
724
725
726
727
728
                                    format!(
                                        "switch_not_met_case_{}",
                                        case_op_index
                                    )
                                    .as_str()
729
                                );
730
                                self.start_block(block_name);
qinsoon's avatar
qinsoon committed
731
732
733
                            }

                            // emit default
734
735
736
                            self.process_dest(
                                &ops, default, f_content, f_context, vm
                            );
737

738
739
                            let default_target =
                                f_content.get_block(default.target.id()).name();
qinsoon's avatar
qinsoon committed
740
741
                            self.backend.emit_jmp(default_target);
                        } else {
qinsoon's avatar
qinsoon committed
742
743
                            // other EQ-comparable types, e.g. floating point
                            unimplemented!()
qinsoon's avatar
qinsoon committed
744
745
                        }
                    }
746
747

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

qinsoon's avatar
qinsoon committed
750
                        if is_abort {
qinsoon's avatar
qinsoon committed
751
                            // if any exception throws from the callee,
752
753
                            // we should abort execution, otherwise rethrow the
                            // exception
qinsoon's avatar
qinsoon committed
754
                            // FIXME: implement is_abort
qinsoon's avatar
qinsoon committed
755
                            unimplemented!()
756
                        }
757

qinsoon's avatar
qinsoon committed
758
759
760
761
                        self.emit_mu_call(
                            inst, // inst: &Instruction,
                            data, // calldata: &CallData,
                            None, // resumption: Option<&ResumptionData>,
762
                            node, // cur_node: &TreeNode,
763
                            f_content, f_context, vm
764
765
766
767
768
                        );
                    }

                    Instruction_::Call {
                        ref data,
769
                        ref resume
770
                    } => {
qinsoon's avatar
qinsoon committed
771
772
                        trace!("instsel on CALL");

773
774
775
776
777
778
779
780
781
                        self.emit_mu_call(
                            inst,
                            data,
                            Some(resume),
                            node,
                            f_content,
                            f_context,
                            vm
                        );
782
783
784
                    }

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

qinsoon's avatar
qinsoon committed
787
                        if is_abort {
qinsoon's avatar
qinsoon committed
788
                            // if any exception throws from the callee,
789
790
                            // we should abort execution, otherwise rethrow the
                            // exception
qinsoon's avatar
qinsoon committed
791
                            // FIXME: implement is_abort
qinsoon's avatar
qinsoon committed
792
793
794
                            unimplemented!()
                        }

795
796
797
                        self.emit_c_call_ir(
                            inst, data, None, node, f_content, f_context, vm
                        );
qinsoon's avatar
qinsoon committed
798
799
                    }

800
801
                    Instruction_::CCall {
                        ref data,
802
                        ref resume
803
                    } => {
qinsoon's avatar
qinsoon committed
804
805
                        trace!("instsel on CCALL");

qinsoon's avatar
qinsoon committed
806
807
808
809
810
                        self.emit_c_call_ir(
                            inst,
                            data,
                            Some(resume),
                            node,
811
812
                            f_content,
                            f_context,
813
                            vm
814
                        );
qinsoon's avatar
qinsoon committed
815
                    }
816

817
                    Instruction_::Return(_) => {
qinsoon's avatar
qinsoon committed
818
819
                        trace!("instsel on RETURN");

820
821
822
                        self.emit_common_epilogue(
                            inst, f_content, f_context, vm
                        );
823

qinsoon's avatar
qinsoon committed
824
                        self.backend.emit_ret();
825
826
                    }

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

830
831
832
                        self.emit_binop(
                            node, inst, op, op1, op2, f_content, f_context, vm
                        );
833
                    }
qinsoon's avatar
qinsoon committed
834

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

838
839
840
                        self.emit_binop(
                            node, inst, op, op1, op2, f_content, f_context, vm
                        );
qinsoon's avatar
qinsoon committed
841

qinsoon's avatar
qinsoon committed
842
843
                        let values = inst.value.as_ref().unwrap();
                        let mut status_value_index = 1;
qinsoon's avatar
qinsoon committed
844

845
                        // status flags only works with int operations
846
847
848
849
                        if RegGroup::get_from_value(&values[0]) == RegGroup::GPR
                        {
                            // for mul, div, idiv, some of the flags may not
                            // generated
qinsoon's avatar
qinsoon committed
850
851
852
853
                            // from the computation, and we may need extra code
                            // to get the flags
                            // FIXME: See Issue#22

854
855
                            // negative flag
                            if status.flag_n {
856
857
                                let tmp_status =
                                    values[status_value_index].clone();
858
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
859

860
861
                                self.backend.emit_sets_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
862

863
864
                            // zero flag
                            if status.flag_z {
865
866
                                let tmp_status =
                                    values[status_value_index].clone();
867
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
868

869
870
                                self.backend.emit_setz_r8(&tmp_status);
                            }
qinsoon's avatar
qinsoon committed
871

872
873
                            // unsigned overflow
                            if status.flag_c {
874
875
                                let tmp_status =
                                    values[status_value_index].clone();
876
                                status_value_index += 1;
qinsoon's avatar
qinsoon committed
877

878
879
880
881
                                match op {
                                    BinOp::Add | BinOp::Sub | BinOp::Mul => {
                                        self.backend.emit_setb_r8(&tmp_status);
                                    }
882
                                    _ => panic!("Only Add/Sub/Mul has #C flag")
qinsoon's avatar
qinsoon committed
883
884
                                }
                            }
qinsoon's avatar
qinsoon committed
885

886
887
                            // signed overflow
                            if status.flag_v {
888
889
                                let tmp_status =
                                    values[status_value_index].clone();
qinsoon's avatar
qinsoon committed
890

891
892
893
894
                                match op {
                                    BinOp::Add | BinOp::Sub | BinOp::Mul => {
                                        self.backend.emit_seto_r8(&tmp_status);
                                    }
895
                                    _ => panic!("Only Add/Sub/Mul has #V flag")
qinsoon's avatar
qinsoon committed
896
897
                                }
                            }
898
899
900
                        } else if RegGroup::get_from_value(&values[0])
                            == RegGroup::GPREX
                        {
901
902
                            unimplemented!()
                        } else {
903
904
905
                            panic!(
                                "only int operations allow binop status flags"
                            )
906
907
                        }
                    }
qinsoon's avatar
qinsoon committed
908

909
910
911
912
                    Instruction_::ConvOp {
                        operation,
                        ref from_ty,
                        ref to_ty,
913
                        operand
914
                    } => {
qinsoon's avatar
qinsoon committed
915
916
                        trace!("instsel on CONVOP");

917
                        let ref ops = inst.ops;
qinsoon's avatar
qinsoon committed
918
919
920
                        let ref op = ops[operand];

                        match operation {