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

asm_backend.rs 41.3 KB
Newer Older
1
2
#![allow(unused_variables)]

3
use compiler::backend;
4
5
use compiler::backend::AOT_EMIT_CONTEXT_FILE;
use compiler::backend::AOT_EMIT_DIR;
qinsoon's avatar
qinsoon committed
6
use compiler::backend::RegGroup;
qinsoon's avatar
qinsoon committed
7
use utils::ByteSize;
8
use compiler::backend::x86_64;
9
use compiler::backend::x86_64::CodeGenerator;
qinsoon's avatar
qinsoon committed
10
11
use compiler::machine_code::CompiledFunction;
use compiler::machine_code::MachineCode;
qinsoon's avatar
qinsoon committed
12
use vm::VM;
qinsoon's avatar
qinsoon committed
13
use runtime::ValueLocation;
14

15
16
use utils::string_utils;

17
18
19
use ast::ptr::P;
use ast::ir::*;

qinsoon's avatar
qinsoon committed
20
21
use std::collections::HashMap;
use std::str;
22
use std::usize;
23
use std::slice::Iter;
24
use std::ops;
qinsoon's avatar
qinsoon committed
25
26

struct ASMCode {
qinsoon's avatar
qinsoon committed
27
    name: MuName, 
28
29
    code: Vec<ASM>,
    reg_defines: HashMap<MuID, Vec<ASMLocation>>,
30
31
    reg_uses: HashMap<MuID, Vec<ASMLocation>>,
    
qinsoon's avatar
qinsoon committed
32
33
    mem_op_used: HashMap<usize, bool>,
    
34
35
36
    preds: Vec<Vec<usize>>,
    succs: Vec<Vec<usize>>,
    
qinsoon's avatar
qinsoon committed
37
38
39
40
    idx_to_blk: HashMap<usize, MuName>,
    blk_to_idx: HashMap<MuName, usize>,
    cond_branches: HashMap<usize, MuName>,
    branches: HashMap<usize, MuName>,
41
    
qinsoon's avatar
qinsoon committed
42
43
44
    blocks: Vec<MuName>,
    block_start: HashMap<MuName, usize>,
    block_range: HashMap<MuName, ops::Range<usize>>,
45
    
qinsoon's avatar
qinsoon committed
46
47
    block_livein: HashMap<MuName, Vec<MuID>>,
    block_liveout: HashMap<MuName, Vec<MuID>>
qinsoon's avatar
qinsoon committed
48
49
}

qinsoon's avatar
qinsoon committed
50
51
52
unsafe impl Send for ASMCode {} 
unsafe impl Sync for ASMCode {}

53
54
55
56
impl MachineCode for ASMCode {
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
qinsoon's avatar
qinsoon committed
57
    
58
59
60
61
62
63
64
65
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
            Some(inst) => inst.code.starts_with("mov"),
            None => false
        }
    }
    
qinsoon's avatar
qinsoon committed
66
67
68
69
    fn is_using_mem_op(&self, index: usize) -> bool {
        *self.mem_op_used.get(&index).unwrap()
    }
    
qinsoon's avatar
qinsoon committed
70
71
72
73
74
75
76
77
    fn get_succs(&self, index: usize) -> &Vec<usize> {
        &self.succs[index]
    }
    
    fn get_preds(&self, index: usize) -> &Vec<usize> {
        &self.preds[index]
    }
    
78
    fn get_inst_reg_uses(&self, index: usize) -> &Vec<MuID> {
qinsoon's avatar
qinsoon committed
79
        &self.code[index].uses
80
81
    }
    
82
    fn get_inst_reg_defines(&self, index: usize) -> &Vec<MuID> {
qinsoon's avatar
qinsoon committed
83
        &self.code[index].defines
84
    }
85
    
86
    fn replace_reg(&mut self, from: MuID, to: MuID) {
87
        let to_reg_tag : MuName = backend::all_regs().get(&to).unwrap().name().unwrap();
88
        let to_reg_string = "%".to_string() + &to_reg_tag;
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
        
        match self.reg_defines.get(&from) {
            Some(defines) => {
                for loc in defines {
                    let ref mut inst_to_patch = self.code[loc.line];
                    for i in 0..loc.len {
                        string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
                    }
                }
            },
            None => {}
        }
        
        match self.reg_uses.get(&from) {
            Some(uses) => {
                for loc in uses {
                    let ref mut inst_to_patch = self.code[loc.line];
                    for i in 0..loc.len {
                        string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
                    }   
                }
            },
            None => {}
        }
    }
    
115
116
117
118
119
    fn set_inst_nop(&mut self, index: usize) {
        self.code.remove(index);
        self.code.insert(index, ASM::nop());
    }
    
120
121
122
123
124
125
126
127
128
129
130
    fn emit(&self) -> Vec<u8> {
        let mut ret = vec![];
        
        for inst in self.code.iter() {
            ret.append(&mut inst.code.clone().into_bytes());
            ret.append(&mut "\n".to_string().into_bytes());
        }
        
        ret
    }
    
131
132
    fn trace_mc(&self) {
        trace!("");
133

134
135
        trace!("code for {}: \n", self.name);
        
136
137
        let n_insts = self.code.len();
        for i in 0..n_insts {
138
            self.trace_inst(i);
139
140
        }
        
141
142
143
144
145
146
147
        trace!("")      
    }
    
    fn trace_inst(&self, i: usize) {
        trace!("#{}\t{:30}\t\tdefine: {:?}\tuses: {:?}\tpred: {:?}\tsucc: {:?}", 
            i, self.code[i].code, self.get_inst_reg_defines(i), self.get_inst_reg_uses(i),
            self.preds[i], self.succs[i]);
148
    }
149
    
150
151
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
        self.block_livein.get(&block.to_string())
152
153
    }
    
154
155
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
        self.block_liveout.get(&block.to_string())
156
157
    }
    
158
159
160
161
162
163
164
165
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
        self.block_livein.insert(block.to_string(), set);
    }
    
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
        self.block_liveout.insert(block.to_string(), set);
    }
    
qinsoon's avatar
qinsoon committed
166
    fn get_all_blocks(&self) -> &Vec<MuName> {
167
168
169
        &self.blocks
    }
    
170
171
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
        match self.block_range.get(&block.to_string()) {
172
173
174
175
            Some(r) => Some(r.clone()),
            None => None
        }
    }
176
177
178
179
180
181
}

struct ASM {
    code: String,
    defines: Vec<MuID>,
    uses: Vec<MuID>
qinsoon's avatar
qinsoon committed
182
183
}

184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
impl ASM {
    fn symbolic(line: String) -> ASM {
        ASM {
            code: line,
            defines: vec![],
            uses: vec![]
        }
    }
    
    fn inst(inst: String, defines: Vec<MuID>, uses: Vec<MuID>) -> ASM {
        ASM {
            code: inst,
            defines: defines,
            uses: uses
        }
    }
    
    fn branch(line: String) -> ASM {
        ASM {
            code: line,
            defines: vec![],
            uses: vec![]
        }
    }
208
209
210
211
212
213
214
215
    
    fn nop() -> ASM {
        ASM {
            code: "".to_string(),
            defines: vec![],
            uses: vec![]
        }
    }
qinsoon's avatar
qinsoon committed
216
217
}

218
#[derive(Clone, Debug)]
qinsoon's avatar
qinsoon committed
219
220
221
222
223
224
225
struct ASMLocation {
    line: usize,
    index: usize,
    len: usize
}

impl ASMLocation {
226
227
    /// the 'line' field will be updated later
    fn new(index: usize, len: usize) -> ASMLocation {
qinsoon's avatar
qinsoon committed
228
        ASMLocation{
229
            line: usize::MAX,
qinsoon's avatar
qinsoon committed
230
231
232
233
234
235
            index: index,
            len: len
        }
    }
}

236
pub struct ASMCodeGen {
237
    cur: Option<Box<ASMCode>>
238
239
}

240
const REG_PLACEHOLDER_LEN : usize = 5;
qinsoon's avatar
qinsoon committed
241
242
243
244
245
246
lazy_static! {
    pub static ref REG_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN];
        
        format!("%{}", str::from_utf8(&blank_spaces).unwrap())
    };
247
248
249
250
}

impl ASMCodeGen {
    pub fn new() -> ASMCodeGen {
qinsoon's avatar
qinsoon committed
251
        ASMCodeGen {
252
            cur: None
qinsoon's avatar
qinsoon committed
253
254
255
256
257
258
259
260
261
262
263
        }
    }
    
    fn cur(&self) -> &ASMCode {
        self.cur.as_ref().unwrap()
    }
    
    fn cur_mut(&mut self) -> &mut ASMCode {
        self.cur.as_mut().unwrap()
    }
    
264
265
266
267
    fn line(&self) -> usize {
        self.cur().code.len()
    }
    
268
269
270
271
272
    fn add_asm_label(&mut self, code: String) {
        let l = self.line();
        self.cur_mut().code.push(ASM::symbolic(code));
    }
    
273
    fn add_asm_block_label(&mut self, code: String, block_name: MuName) {
274
275
276
        let l = self.line();
        self.cur_mut().code.push(ASM::symbolic(code));
        
277
        self.cur_mut().idx_to_blk.insert(l, block_name.clone());
278
279
280
        self.cur_mut().blk_to_idx.insert(block_name, l);
    }
    
281
282
283
284
    fn add_asm_symbolic(&mut self, code: String){
        self.cur_mut().code.push(ASM::symbolic(code));
    }
    
285
286
287
288
    fn prepare_machine_regs(&self, regs: Iter<P<Value>>) -> Vec<MuID> {
        regs.map(|x| self.prepare_machine_reg(x)).collect()
    } 
    
289
    fn add_asm_call(&mut self, code: String) {
290
291
292
293
294
295
        let mut uses : Vec<MuID> = self.prepare_machine_regs(x86_64::ARGUMENT_GPRs.iter());
        uses.append(&mut self.prepare_machine_regs(x86_64::ARGUMENT_FPRs.iter()));
        
        let mut defines : Vec<MuID> = self.prepare_machine_regs(x86_64::RETURN_GPRs.iter());
        defines.append(&mut self.prepare_machine_regs(x86_64::RETURN_FPRs.iter()));
          
qinsoon's avatar
qinsoon committed
296
        self.add_asm_inst(code, defines, vec![], uses, vec![], false);
297
298
299
    }
    
    fn add_asm_ret(&mut self, code: String) {
300
301
302
        let mut uses : Vec<MuID> = self.prepare_machine_regs(x86_64::RETURN_GPRs.iter());
        uses.append(&mut self.prepare_machine_regs(x86_64::RETURN_FPRs.iter()));
        
qinsoon's avatar
qinsoon committed
303
        self.add_asm_inst(code, vec![], vec![], uses, vec![], false);
304
305
    }
    
306
    fn add_asm_branch(&mut self, code: String, target: MuName) {
307
308
        let l = self.line();
        self.cur_mut().branches.insert(l, target);
qinsoon's avatar
qinsoon committed
309
310
        
        self.add_asm_inst(code, vec![], vec![], vec![], vec![], false);
311
312
    }
    
313
    fn add_asm_branch2(&mut self, code: String, target: MuName) {
314
315
        let l = self.line();
        self.cur_mut().cond_branches.insert(l, target);
qinsoon's avatar
qinsoon committed
316
317
        
        self.add_asm_inst(code, vec![], vec![], vec![], vec![], false);
318
319
320
321
322
323
    }
    
    fn add_asm_inst(
        &mut self, 
        code: String, 
        defines: Vec<MuID>,
324
        mut define_locs: Vec<ASMLocation>, 
325
        uses: Vec<MuID>,
qinsoon's avatar
qinsoon committed
326
327
        mut use_locs: Vec<ASMLocation>,
        is_using_mem_op: bool) 
328
    {
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
        let line = self.line();
        
        trace!("asm: {}", code);
        trace!("     defines: {:?}, def_locs: {:?}", defines, define_locs);
        trace!("     uses: {:?}, use_locs: {:?}", uses, use_locs);
        let mc = self.cur_mut();
       
        // add locations of defined registers
        for i in 0..define_locs.len() {
            let id = defines[i];
            
            // update line in location
            let ref mut loc = define_locs[i];
            loc.line = line;
            
            if mc.reg_defines.contains_key(&id) {
                mc.reg_defines.get_mut(&id).unwrap().push(loc.clone());
            } else {
                mc.reg_defines.insert(id, vec![loc.clone()]);
            }
        }
       
        for i in 0..use_locs.len() {
            let id = uses[i];
            
            // update line in location
            let ref mut loc = use_locs[i];
            loc.line = line;
            
            if mc.reg_uses.contains_key(&id) {
359
                mc.reg_uses.get_mut(&id).unwrap().push(loc.clone());
360
            } else {
361
                mc.reg_uses.insert(id, vec![loc.clone()]);
362
363
            }
        }
364
       
365
366
        // put the instruction
        mc.code.push(ASM::inst(code, defines, uses));
qinsoon's avatar
qinsoon committed
367
        mc.mem_op_used.insert(line, is_using_mem_op);
368
369
370
371
    }
    
    fn define_reg(&mut self, reg: &P<Value>, loc: ASMLocation) {
        let id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
372
        
373
374
375
376
377
378
379
        let code = self.cur_mut();
        if code.reg_defines.contains_key(&id) {
            let regs = code.reg_defines.get_mut(&id).unwrap();
            regs.push(loc);
        } else {
            code.reg_defines.insert(id, vec![loc]);
        } 
qinsoon's avatar
qinsoon committed
380
381
382
383
384
385
    }
    
    fn use_reg(&mut self, reg: &P<Value>, loc: ASMLocation) {
        let id = reg.extract_ssa_id().unwrap();
        
        let code = self.cur_mut();
386
387
388
        if code.reg_uses.contains_key(&id) {
            let reg_uses = code.reg_uses.get_mut(&id).unwrap();
            reg_uses.push(loc);
qinsoon's avatar
qinsoon committed
389
        } else {
390
            code.reg_uses.insert(id, vec![loc]);
qinsoon's avatar
qinsoon committed
391
392
393
        } 
    }
    
394
    fn prepare_reg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
395
396
397
398
399
400
401
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting register op")
            }
        }
        
402
403
404
405
406
407
        let str = self.asm_reg_op(op);
        let len = str.len();
        (str, op.extract_ssa_id().unwrap(), ASMLocation::new(loc, len)) 
    }
    
    fn prepare_machine_reg(&self, op: &P<Value>) -> MuID {
408
409
410
411
412
413
414
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting machine register op")
            }
        }        
        
415
        op.extract_ssa_id().unwrap()
416
    }
417
    
418
419
    #[allow(unused_assignments)]
    fn prepare_mem(&self, op: &P<Value>, loc: usize) -> (String, Vec<MuID>, Vec<ASMLocation>) {
420
421
422
423
424
425
426
        if cfg!(debug_assertions) {
            match op.v {
                Value_::Memory(_) => {},
                _ => panic!("expecting register op")
            }
        }        
        
427
428
429
430
        let mut ids : Vec<MuID> = vec![];
        let mut locs : Vec<ASMLocation> = vec![];
        let mut result_str : String = "".to_string();
        
431
        let mut loc_cursor : usize = loc;
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
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
511
512
513
        
        match op.v {
            // offset(base,index,scale)
            Value_::Memory(MemoryLocation::Address{ref base, ref offset, ref index, scale}) => {
                // deal with offset
                if offset.is_some() {
                    let offset = offset.as_ref().unwrap();
                    
                    match offset.v {
                        Value_::SSAVar(id) => {
                            // temp as offset
                            let (str, id, loc) = self.prepare_reg(offset, 0);
                            
                            result_str.push_str(&str);
                            ids.push(id);
                            locs.push(loc);
                            
                            loc_cursor += str.len();
                        },
                        Value_::Constant(Constant::Int(val)) => {
                            let str = val.to_string();
                            
                            result_str.push_str(&str);
                            loc_cursor += str.len();
                        },
                        _ => panic!("unexpected offset type: {:?}", offset)
                    }
                }
                
                result_str.push('(');
                loc_cursor += 1; 
                
                // deal with base, base is ssa
                let (str, id, loc) = self.prepare_reg(base, loc_cursor);
                result_str.push_str(&str);
                ids.push(id);
                locs.push(loc);
                loc_cursor += str.len();
                
                // deal with index (ssa or constant)
                if index.is_some() {
                    result_str.push(',');
                    loc_cursor += 1; // plus 1 for ,                    
                    
                    let index = index.as_ref().unwrap();
                    
                    match index.v {
                        Value_::SSAVar(id) => {
                            // temp as offset
                            let (str, id, loc) = self.prepare_reg(index, loc_cursor);
                            
                            result_str.push_str(&str);
                            ids.push(id);
                            locs.push(loc);
                            
                            loc_cursor += str.len();
                        },
                        Value_::Constant(Constant::Int(val)) => {
                            let str = val.to_string();
                            
                            result_str.push_str(&str);
                            loc_cursor += str.len();
                        },
                        _ => panic!("unexpected index type: {:?}", index)
                    }
                    
                    // scale
                    if scale.is_some() {
                        result_str.push(',');
                        loc_cursor += 1;
                        
                        let scale = scale.unwrap();
                        let str = scale.to_string();
                        
                        result_str.push_str(&str);
                        loc_cursor += str.len();
                    }
                }
                
                result_str.push(')');
                loc_cursor += 1;
            },
514
515
            Value_::Memory(MemoryLocation::Symbolic{ref base, ref label}) => {
                result_str.push_str(&symbol(label.clone()));
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
                loc_cursor += label.len();
                
                if base.is_some() {
                    result_str.push('(');
                    loc_cursor += 1;
                    
                    let (str, id, loc) = self.prepare_reg(base.as_ref().unwrap(), loc_cursor);
                    result_str.push_str(&str);
                    ids.push(id);
                    locs.push(loc);
                    loc_cursor += str.len();
                    
                    result_str.push(')');
                    loc_cursor += 1;                    
                }
            },
            _ => panic!("expect mem location as value")
        }
        
        (result_str, ids, locs)
    }
    
qinsoon's avatar
qinsoon committed
538
539
    fn asm_reg_op(&self, op: &P<Value>) -> String {
        let id = op.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
540
        if id < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
541
            // machine reg
542
            format!("%{}", op.name().unwrap())
qinsoon's avatar
qinsoon committed
543
544
545
546
547
548
        } else {
            // virtual register, use place holder
            REG_PLACEHOLDER.clone()
        }
    }
    
qinsoon's avatar
qinsoon committed
549
    fn asm_block_label(&self, label: MuName) -> String {
550
        symbol(format!("{}_{}", self.cur().name, label))
551
    }
552
553
554
555
556
557
558
559
560
561
562
563
564
565
    
    fn control_flow_analysis(&mut self) {
        // control flow analysis
        let n_insts = self.line();
        
        let code = self.cur_mut();
        code.preds = vec![vec![]; n_insts];
        code.succs = vec![vec![]; n_insts];
        
        for i in 0..n_insts {
            // determine predecessor - if cur is not block start, its predecessor is previous insts
            let is_block_start = code.idx_to_blk.get(&i);
            if is_block_start.is_none() {
                if i > 0 {
566
567
                    trace!("inst {}: not a block start", i);
                    trace!("inst {}: set PREDS as previous inst {}", i, i-1);
568
569
570
571
572
573
574
575
576
577
578
579
                    code.preds[i].push(i - 1);
                }
            } else {
                // if cur is a branch target, we already set its predecessor
                // if cur is a fall-through block, we set it in a sanity check pass
            }
            
            // determine successor
            let is_branch = code.branches.get(&i);
            if is_branch.is_some() {
                // branch to target
                let target = is_branch.unwrap();
580
581
                trace!("inst {}: is a branch to {}", i, target);
                                
582
                let target_n = code.blk_to_idx.get(target).unwrap();
583
                trace!("inst {}: branch target index is {}", i, target_n);
584
585
                
                // cur inst's succ is target
586
                trace!("inst {}: set SUCCS as branch target {}", i, target_n);
587
588
589
                code.succs[i].push(*target_n);
                
                // target's pred is cur
590
                trace!("inst {}: set PREDS as branch source {}", target_n, i);
591
592
593
594
595
596
                code.preds[*target_n].push(i);
            } else {
                let is_cond_branch = code.cond_branches.get(&i);
                if is_cond_branch.is_some() {
                    // branch to target
                    let target = is_cond_branch.unwrap();
597
598
                    trace!("inst {}: is a cond branch to {}", i, target);
                    
599
                    let target_n = code.blk_to_idx.get(target).unwrap();
600
                    trace!("inst {}: branch target index is {}", i, target_n);
601
602
603
                    
                    // cur insts' succ is target and next inst
                    code.succs[i].push(*target_n);
604
                    trace!("inst {}: set SUCCS as branch target {}", i, target_n);
605
                    if i < n_insts - 1 {
606
                        trace!("inst {}: set SUCCS as next inst", i + 1);                        
607
608
609
610
611
                        code.succs[i].push(i + 1);
                    }
                    
                    // target's pred is cur
                    code.preds[*target_n].push(i);
612
                    trace!("inst {}: set PREDS as {}", *target_n, i);
613
614
                } else {
                    // not branch nor cond branch, succ is next inst
615
                    trace!("inst {}: not a branch inst", i);
616
                    if i < n_insts - 1 {
617
                        trace!("inst {}: set SUCCS as next inst {}", i, i + 1);
618
619
620
621
622
623
624
625
626
627
628
629
630
                        code.succs[i].push(i + 1);
                    }
                }
            } 
        }
        
        // a sanity check for fallthrough blocks
        for i in 0..n_insts {
            if i != 0 && code.preds[i].len() == 0 {
                code.preds[i].push(i - 1);
            }
        }        
    }
631
632
633
}

impl CodeGenerator for ASMCodeGen {
qinsoon's avatar
qinsoon committed
634
    fn start_code(&mut self, func_name: MuName) -> ValueLocation {
635
        self.cur = Some(Box::new(ASMCode {
636
                name: func_name.clone(),
qinsoon's avatar
qinsoon committed
637
                code: vec![],
638
                reg_defines: HashMap::new(),
639
640
                reg_uses: HashMap::new(),
                
qinsoon's avatar
qinsoon committed
641
642
                mem_op_used: HashMap::new(),
                
643
644
645
646
647
648
                preds: vec![],
                succs: vec![],
                
                idx_to_blk: HashMap::new(),
                blk_to_idx: HashMap::new(),
                cond_branches: HashMap::new(),
649
650
                branches: HashMap::new(),
                
651
652
653
654
                blocks: vec![],
                block_start: HashMap::new(),
                block_range: HashMap::new(),
                
655
656
                block_livein: HashMap::new(),
                block_liveout: HashMap::new()
657
            }));
qinsoon's avatar
qinsoon committed
658
        
qinsoon's avatar
qinsoon committed
659
        // to link with C sources via gcc
qinsoon's avatar
qinsoon committed
660
661
662
663
        let func_symbol = symbol(func_name.clone());
        self.add_asm_symbolic(directive_globl(func_symbol.clone()));
        self.add_asm_symbolic(format!("{}:", func_symbol.clone()));
        
664
        ValueLocation::Relocatable(RegGroup::GPR, func_name)
qinsoon's avatar
qinsoon committed
665
666
    }
    
667
    fn finish_code(&mut self, func_name: MuName) -> (Box<MachineCode + Sync + Send>, ValueLocation) {
668
669
        let func_end = {
            let mut symbol = func_name.clone();
qinsoon's avatar
qinsoon committed
670
671
672
            symbol.push_str("_end");
            symbol
        };
673
674
        self.add_asm_symbolic(directive_globl(symbol(func_end.clone())));
        self.add_asm_symbolic(format!("{}:", symbol(func_end.clone())));
qinsoon's avatar
qinsoon committed
675
        
676
        self.control_flow_analysis();
qinsoon's avatar
qinsoon committed
677
678
679
        
        (
            self.cur.take().unwrap(),
680
            ValueLocation::Relocatable(RegGroup::GPR, func_end)
qinsoon's avatar
qinsoon committed
681
        )
qinsoon's avatar
qinsoon committed
682
683
684
685
686
687
688
689
690
    }
    
    fn print_cur_code(&self) {
        println!("");
        
        if self.cur.is_some() {
            let code = self.cur.as_ref().unwrap();
            
            println!("code for {}: ", code.name);
691
692
693
694
            let n_insts = code.code.len();
            for i in 0..n_insts {
                let ref line = code.code[i];
                println!("#{}\t{}", i, line.code);
qinsoon's avatar
qinsoon committed
695
696
697
698
699
700
701
702
            }
        } else {
            println!("no current code");
        }
        
        println!("");
    }
    
qinsoon's avatar
qinsoon committed
703
    fn start_block(&mut self, block_name: MuName) {
704
705
706
        let label = format!("{}:", self.asm_block_label(block_name.clone()));        
        self.add_asm_block_label(label, block_name.clone());
        self.cur_mut().blocks.push(block_name.clone());
707
708
709
710
711
        
        let start = self.line();
        self.cur_mut().block_start.insert(block_name, start);
    }
    
qinsoon's avatar
qinsoon committed
712
    fn start_exception_block(&mut self, block_name: MuName) -> ValueLocation {
713
714
715
        let block = self.asm_block_label(block_name.clone());
        self.add_asm_symbolic(directive_globl(symbol(block.clone())));
        self.add_asm_symbolic(format!("{}:", symbol(block.clone())));
qinsoon's avatar
qinsoon committed
716
717
718
        
        self.start_block(block_name);
        
719
        ValueLocation::Relocatable(RegGroup::GPR, block)
qinsoon's avatar
qinsoon committed
720
721
    }
    
qinsoon's avatar
qinsoon committed
722
    fn end_block(&mut self, block_name: MuName) {
723
724
725
726
        let start : usize = *self.cur().block_start.get(&block_name).unwrap();
        let end : usize = self.line();
        
        self.cur_mut().block_range.insert(block_name, (start..end));
qinsoon's avatar
qinsoon committed
727
728
    }
    
qinsoon's avatar
qinsoon committed
729
    fn set_block_livein(&mut self, block_name: MuName, live_in: &Vec<P<Value>>) {
730
731
732
733
        let cur = self.cur_mut();
        
        let mut res = {
            if !cur.block_livein.contains_key(&block_name) {
734
                cur.block_livein.insert(block_name.clone(), vec![]);
735
736
737
738
739
740
741
742
743
744
745
746
            } else {
                panic!("seems we are inserting livein to block {} twice", block_name);
            }
            
            cur.block_livein.get_mut(&block_name).unwrap()
        };
        
        for value in live_in {
            res.push(value.extract_ssa_id().unwrap());
        }
    }
    
qinsoon's avatar
qinsoon committed
747
    fn set_block_liveout(&mut self, block_name: MuName, live_out: &Vec<P<Value>>) {
748
749
750
751
        let cur = self.cur_mut();
        
        let mut res = {
            if !cur.block_liveout.contains_key(&block_name) {
752
                cur.block_liveout.insert(block_name.clone(), vec![]);
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
            } else {
                panic!("seems we are inserting livein to block {} twice", block_name);
            }
            
            cur.block_liveout.get_mut(&block_name).unwrap()
        };
        
        for value in live_out {
            match value.extract_ssa_id() {
                Some(id) => res.push(id),
                None => {}
            }
        }        
    }
    
768
    fn emit_cmp_r64_r64(&mut self, op1: &P<Value>, op2: &P<Value>) {
qinsoon's avatar
qinsoon committed
769
        trace!("emit: cmp {} {}", op1, op2);
qinsoon's avatar
qinsoon committed
770
        
771
772
        let (reg1, id1, loc1) = self.prepare_reg(op1, 4 + 1);
        let (reg2, id2, loc2) = self.prepare_reg(op2, 4 + 1 + reg1.len() + 1);
qinsoon's avatar
qinsoon committed
773
        
qinsoon's avatar
qinsoon committed
774
        let asm = format!("cmpq {},{}", reg1, reg2);
qinsoon's avatar
qinsoon committed
775
        
776
777
778
779
780
        self.add_asm_inst(
            asm,
            vec![],
            vec![],
            vec![id1, id2],
qinsoon's avatar
qinsoon committed
781
782
            vec![loc1, loc2],
            false
783
        );
784
785
    }
    
786
    fn emit_cmp_r64_imm32(&mut self, op1: &P<Value>, op2: i32) {
qinsoon's avatar
qinsoon committed
787
        trace!("emit: cmp {} {}", op1, op2);
qinsoon's avatar
qinsoon committed
788
        
789
        let (reg1, id1, loc1) = self.prepare_reg(op1, 4 + 1 + 1 + op2.to_string().len() + 1);
qinsoon's avatar
qinsoon committed
790
        
qinsoon's avatar
qinsoon committed
791
        let asm = format!("cmpq ${},{}", op2, reg1);
qinsoon's avatar
qinsoon committed
792
        
793
794
795
796
797
        self.add_asm_inst(
            asm,
            vec![],
            vec![],
            vec![id1],
qinsoon's avatar
qinsoon committed
798
799
            vec![loc1],
            false
800
        )
801
802
803
    }
    
    fn emit_cmp_r64_mem64(&mut self, op1: &P<Value>, op2: &P<Value>) {
qinsoon's avatar
qinsoon committed
804
        trace!("emit: cmp {} {}", op1, op2);
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
        
        let (reg, id1, loc1) = self.prepare_reg(op1, 4 + 1);
        let (mem, mut id2, mut loc2) = self.prepare_mem(op2, 4 + 1 + reg.len() + 1);
        
        let asm = format!("cmpq {},{}", reg, mem);
        
        // merge use vec
        id2.push(id1);
        loc2.push(loc1);
        
        self.add_asm_inst(
            asm,
            vec![],
            vec![],
            id2,
            loc2,
            true
        )
823
824
    }
    
825
    fn emit_mov_r64_imm32(&mut self, dest: &P<Value>, src: i32) {
qinsoon's avatar
qinsoon committed
826
        trace!("emit: mov {} -> {}", src, dest);
qinsoon's avatar
qinsoon committed
827
        
828
        let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1);
qinsoon's avatar
qinsoon committed
829
        
qinsoon's avatar
qinsoon committed
830
        let asm = format!("movq ${},{}", src, reg1);
qinsoon's avatar
qinsoon committed
831
        
832
833
834
        self.add_asm_inst(
            asm,
            vec![id1],
835
836
            vec![loc1],
            vec![],
qinsoon's avatar
qinsoon committed
837
838
            vec![],
            false
839
        )
840
841
    }
    
842
    // load
843
    fn emit_mov_r64_mem64(&mut self, dest: &P<Value>, src: &P<Value>) {
qinsoon's avatar
qinsoon committed
844
        trace!("emit: mov {} -> {}", src, dest);
845
846
847
848
849
850
851
852
853
854
855
        
        let (mem, id1, loc1) = self.prepare_mem(src, 4 + 1);
        let (reg, id2, loc2) = self.prepare_reg(dest, 4 + 1 + mem.len() + 1);
        
        let asm = format!("movq {},{}", mem, reg);
        
        self.add_asm_inst(
            asm,
            vec![id2],
            vec![loc2],
            id1,
qinsoon's avatar
qinsoon committed
856
857
            loc1,
            true
858
859
860
        )
    }
    
861
    // store
862
863
864
865
866
867
868
    fn emit_mov_mem64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: mov {} -> {}", src, dest);
        
        let (reg, id1, loc1) = self.prepare_reg(src, 4 + 1);
        let (mem, mut id2, mut loc2) = self.prepare_mem(dest, 4 + 1 + reg.len() + 1);
        
        // the register we used for the memory location is counted as 'use'
869
        // use the vec from mem as 'use' (push use reg from src to it)
870
871
872
873
874
875
876
877
878
879
        id2.push(id1);
        loc2.push(loc1);
        
        let asm = format!("movq {},{}", reg, mem);
        
        self.add_asm_inst(
            asm,
            vec![], // not defining anything (write to memory)
            vec![],
            id2,
qinsoon's avatar
qinsoon committed
880
881
            loc2,
            true
882
883
884
        )
    }
    
885
    fn emit_mov_mem64_imm32(&mut self, dest: &P<Value>, src: i32) {
886
887
888
889
890
891
892
893
894
895
896
        trace!("emit: mov {} -> {}", src, dest);
        
        let (mem, id, loc) = self.prepare_mem(dest, 4 + 1 + 1 + src.to_string().len() + 1);
        
        let asm = format!("movq ${},{}", src, mem);
        
        self.add_asm_inst(
            asm,
            vec![],
            vec![],
            id,
qinsoon's avatar
qinsoon committed
897
898
            loc,
            true
899
        )
qinsoon's avatar
qinsoon committed
900
901
902
903
    }
    
    fn emit_mov_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: mov {} -> {}", src, dest);
qinsoon's avatar
qinsoon committed
904
        
905
906
        let (reg1, id1, loc1) = self.prepare_reg(src, 4 + 1);
        let (reg2, id2, loc2) = self.prepare_reg(dest, 4 + 1 + reg1.len() + 1);
qinsoon's avatar
qinsoon committed
907
        
qinsoon's avatar
qinsoon committed
908
        let asm = format!("movq {},{}", reg1, reg2);
qinsoon's avatar
qinsoon committed
909
        
910
911
912
        self.add_asm_inst(
            asm,
            vec![id2],
913
914
            vec![loc2],
            vec![id1],
qinsoon's avatar
qinsoon committed
915
916
            vec![loc1],
            false
917
        )
qinsoon's avatar
qinsoon committed
918
919
920
921
    }
    
    fn emit_add_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: add {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
922
        
923
924
        let (reg1, id1, loc1) = self.prepare_reg(src, 4 + 1);
        let (reg2, id2, loc2) = self.prepare_reg(dest, 4 + 1 + reg1.len() + 1);
qinsoon's avatar
qinsoon committed
925
        
qinsoon's avatar
qinsoon committed
926
        let asm = format!("addq {},{}", reg1, reg2);
qinsoon's avatar
qinsoon committed
927
        
928
929
        self.add_asm_inst(
            asm,
930
931
            vec![id2],
            vec![loc2.clone()],
932
            vec![id1, id2],
qinsoon's avatar
qinsoon committed
933
934
            vec![loc1, loc2],
            false
935
        )
qinsoon's avatar
qinsoon committed
936
937
    }
    
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
    fn emit_lea_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: lea {} -> {}", src, dest);
        
        let (mem, id1, loc1) = self.prepare_mem(src, 4 + 1);
        let (reg, id2, loc2) = self.prepare_reg(dest, 4 + 1 + mem.len() + 1);
        
        let asm = format!("leaq {},{}", mem, reg);
        
        self.add_asm_inst(
            asm,
            vec![id2],
            vec![loc2],
            id1,
            loc1,
            true
        ) 
    }
    
956
    fn emit_and_r64_imm32(&mut self, dest: &P<Value>, src: i32) {
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
        trace!("emit: and {}, {} -> {}", src, dest, dest);
        
        let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1);

        let asm = format!("andq ${},{}", src, reg1);
        
        self.add_asm_inst(
            asm,
            vec![id1],
            vec![loc1.clone()],
            vec![id1],
            vec![loc1],
            false
        )
    }
    
    fn emit_and_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: and {}, {} -> {}", src, dest, dest);
        
        let (reg1, id1, loc1) = self.prepare_reg(src, 4 + 1);
        let (reg2, id2, loc2) = self.prepare_reg(dest, 4 + 1 + reg1.len() + 1); 

        let asm = format!("andq {},{}", reg1, reg2);
        
        self.add_asm_inst(
            asm,
            vec![id2],
            vec![loc2.clone()],
            vec![id1, id2],
            vec![loc1, loc2],
            false
        )
    }    
    
qinsoon's avatar
qinsoon committed
991
992
    fn emit_add_r64_mem64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: add {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
993
        unimplemented!()
qinsoon's avatar
qinsoon committed
994
995
    }
    
996
    fn emit_add_r64_imm32(&mut self, dest: &P<Value>, src: i32) {
qinsoon's avatar
qinsoon committed
997
        trace!("emit: add {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
998
        
999
        let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1);
qinsoon's avatar
qinsoon committed
1000
        
1001
        let asm = format!("addq ${},{}", src, reg1);
qinsoon's avatar
qinsoon committed
1002
        
1003
1004
1005
1006
1007
        self.add_asm_inst(
            asm,
            vec![id1],
            vec![loc1.clone()],
            vec![id1],
qinsoon's avatar
qinsoon committed
1008
1009
            vec![loc1],
            false
1010
        )
qinsoon's avatar
qinsoon committed
1011
1012
1013
1014
    }
    
    fn emit_sub_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: sub {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
1015
        
1016
1017
        let (reg1, id1, loc1) = self.prepare_reg(src, 4 + 1);
        let (reg2, id2, loc2) = self.prepare_reg(dest, 4 + 1 + reg1.len() + 1);
qinsoon's avatar
qinsoon committed
1018
        
qinsoon's avatar
qinsoon committed
1019
        let asm = format!("subq {},{}", reg1, reg2);
qinsoon's avatar
qinsoon committed
1020
        
1021
1022
        self.add_asm_inst(
            asm,
1023
1024
            vec![id2],
            vec![loc2.clone()],
1025
            vec![id1, id2],
qinsoon's avatar
qinsoon committed
1026
1027
            vec![loc1, loc2],
            false
1028
        )        
qinsoon's avatar
qinsoon committed
1029
1030
1031
1032
    }
    
    fn emit_sub_r64_mem64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: sub {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
1033
        unimplemented!()
qinsoon's avatar
qinsoon committed
1034
1035
    }
    
1036
    fn emit_sub_r64_imm32(&mut self, dest: &P<Value>, src: i32) {
qinsoon's avatar
qinsoon committed
1037
        trace!("emit: sub {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
1038
        
1039
        let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1);
qinsoon's avatar
qinsoon committed
1040
        
qinsoon's avatar
qinsoon committed
1041
        let asm = format!("subq ${},{}", src, reg1);
qinsoon's avatar
qinsoon committed
1042
        
1043
1044
1045
1046
1047
        self.add_asm_inst(
            asm,
            vec![id1],
            vec![loc1.clone()],
            vec![id1],
qinsoon's avatar
qinsoon committed
1048
1049
            vec![loc1],
            false
1050
        )        
qinsoon's avatar
qinsoon committed
1051
1052
    }
    
1053
    fn emit_mul_r64(&mut self, src: &P<Value>) {
1054
        trace!("emit: mul rax, {} -> (rdx, rax)", src);
qinsoon's avatar
qinsoon committed
1055
        
1056
        let (reg, id, loc) = self.prepare_reg(src, 3 + 1);
1057
1058
        let rax = self.prepare_machine_reg(&x86_64::RAX);
        let rdx = self.prepare_machine_reg(&x86_64::RDX);
qinsoon's avatar
qinsoon committed
1059
1060
1061
        
        let asm = format!("mul {}", reg);
        
1062
1063
1064
1065
1066
        self.add_asm_inst(
            asm,
            vec![rax, rdx],
            vec![],
            vec![id, rax],
qinsoon's avatar
qinsoon committed
1067
1068
            vec![loc],
            false
1069
        )
1070
1071
1072
1073
    }
    
    fn emit_mul_mem64(&mut self, src: &P<Value>) {
        trace!("emit: mul rax, {} -> rax", src);
qinsoon's avatar
qinsoon committed
1074
        unimplemented!()
1075
1076
    }
    
1077
    fn emit_jmp(&mut self, dest_name: MuName) {
qinsoon's avatar
qinsoon committed
1078
        trace!("emit: jmp {}", dest_name);
qinsoon's avatar
qinsoon committed
1079
1080
        
        // symbolic label, we dont need to patch it
1081
        let asm = format!("jmp {}", self.asm_block_label(dest_name.clone()));
qinsoon's avatar
qinsoon committed
1082
        self.add_asm_branch(asm, dest_name)
qinsoon's avatar
qinsoon committed
1083
1084
    }
    
1085
    fn emit_je(&mut self, dest_name: MuName) {
qinsoon's avatar
qinsoon committed
1086
        trace!("emit: je {}", dest_name);
qinsoon's avatar
qinsoon committed
1087
        
1088
        let asm = format!("je {}", self.asm_block_label(dest_name.clone()));
qinsoon's avatar
qinsoon committed
1089
        self.add_asm_branch2(asm, dest_name);        
qinsoon's avatar
qinsoon committed
1090
1091
    }
    
1092
    fn emit_jne(&mut self, dest_name: MuName) {
qinsoon's avatar
qinsoon committed
1093
        trace!("emit: jne {}", dest_name);
qinsoon's avatar
qinsoon committed
1094
        
1095
        let asm = format!("jne {}", self.asm_block_label(dest_name.clone()));
qinsoon's avatar
qinsoon committed
1096
        self.add_asm_branch2(asm, dest_name);
qinsoon's avatar
qinsoon committed
1097
1098
    }
    
1099
    fn emit_ja(&mut self, dest_name: MuName) {
qinsoon's avatar
qinsoon committed
1100
        trace!("emit: ja {}", dest_name);
qinsoon's avatar
qinsoon committed
1101
        
1102
        let asm = format!("ja {}", self.asm_block_label(dest_name.clone()));
qinsoon's avatar
qinsoon committed
1103
        self.add_asm_branch2(asm, dest_name);
qinsoon's avatar
qinsoon committed
1104
1105
    }
    
1106
    fn emit_jae(&mut self, dest_name: MuName) {
qinsoon's avatar
qinsoon committed
1107
        trace!("emit: jae {}", dest_name);
qinsoon's avatar
qinsoon committed
1108
        
1109
        let asm = format!("jae {}", self.asm_block_label(dest_name.clone()));
qinsoon's avatar
qinsoon committed
1110
        self.add_asm_branch2(asm, dest_name);        
qinsoon's avatar
qinsoon committed
1111
1112
    }
    
1113
    fn emit_jb(&mut self, dest_name: MuName) {