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

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

3
use compiler::backend;
qinsoon's avatar
qinsoon committed
4
use utils::ByteSize;
5
use compiler::backend::x86_64;
6
use compiler::backend::x86_64::CodeGenerator;
qinsoon's avatar
qinsoon committed
7
use vm::MachineCode;
qinsoon's avatar
qinsoon committed
8
use vm::VM;
9

10
11
use utils::string_utils;

12
13
use ast::ptr::P;
use ast::ir::*;
qinsoon's avatar
qinsoon committed
14
use ast::inst::*;
15

qinsoon's avatar
qinsoon committed
16
17
use std::collections::HashMap;
use std::str;
18
use std::usize;
19
use std::slice::Iter;
20
use std::ops;
qinsoon's avatar
qinsoon committed
21
22

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

46
47
48
49
impl MachineCode for ASMCode {
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
qinsoon's avatar
qinsoon committed
50
    
51
52
53
54
55
56
57
58
    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
59
60
61
62
    fn is_using_mem_op(&self, index: usize) -> bool {
        *self.mem_op_used.get(&index).unwrap()
    }
    
qinsoon's avatar
qinsoon committed
63
64
65
66
67
68
69
70
    fn get_succs(&self, index: usize) -> &Vec<usize> {
        &self.succs[index]
    }
    
    fn get_preds(&self, index: usize) -> &Vec<usize> {
        &self.preds[index]
    }
    
71
    fn get_inst_reg_uses(&self, index: usize) -> &Vec<MuID> {
qinsoon's avatar
qinsoon committed
72
        &self.code[index].uses
73
74
    }
    
75
    fn get_inst_reg_defines(&self, index: usize) -> &Vec<MuID> {
qinsoon's avatar
qinsoon committed
76
        &self.code[index].defines
77
    }
78
    
79
    fn replace_reg(&mut self, from: MuID, to: MuID) {
qinsoon's avatar
qinsoon committed
80
        let to_reg_tag : MuName = backend::all_regs()[to].tag;
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
        let to_reg_string = "%".to_string() + to_reg_tag;
        
        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 => {}
        }
    }
    
108
109
110
111
112
    fn set_inst_nop(&mut self, index: usize) {
        self.code.remove(index);
        self.code.insert(index, ASM::nop());
    }
    
113
114
115
116
117
118
119
120
121
122
123
    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
    }
    
124
125
    fn trace_mc(&self) {
        trace!("");
126

127
128
        trace!("code for {}: \n", self.name);
        
129
130
        let n_insts = self.code.len();
        for i in 0..n_insts {
131
            self.trace_inst(i);
132
133
        }
        
134
135
136
137
138
139
140
        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]);
141
    }
142
    
qinsoon's avatar
qinsoon committed
143
    fn get_ir_block_livein(&self, block: MuName) -> Option<&Vec<MuID>> {
144
145
146
        self.block_livein.get(&block)
    }
    
qinsoon's avatar
qinsoon committed
147
    fn get_ir_block_liveout(&self, block: MuName) -> Option<&Vec<MuID>> {
148
149
150
        self.block_liveout.get(&block)
    }
    
qinsoon's avatar
qinsoon committed
151
    fn get_all_blocks(&self) -> &Vec<MuName> {
152
153
154
        &self.blocks
    }
    
qinsoon's avatar
qinsoon committed
155
    fn get_block_range(&self, block: MuName) -> Option<ops::Range<usize>> {
156
157
158
159
160
        match self.block_range.get(&block) {
            Some(r) => Some(r.clone()),
            None => None
        }
    }
161
162
163
164
165
166
}

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

169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
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![]
        }
    }
193
194
195
196
197
198
199
200
    
    fn nop() -> ASM {
        ASM {
            code: "".to_string(),
            defines: vec![],
            uses: vec![]
        }
    }
qinsoon's avatar
qinsoon committed
201
202
}

203
#[derive(Clone, Debug)]
qinsoon's avatar
qinsoon committed
204
205
206
207
208
209
210
struct ASMLocation {
    line: usize,
    index: usize,
    len: usize
}

impl ASMLocation {
211
212
    /// the 'line' field will be updated later
    fn new(index: usize, len: usize) -> ASMLocation {
qinsoon's avatar
qinsoon committed
213
        ASMLocation{
214
            line: usize::MAX,
qinsoon's avatar
qinsoon committed
215
216
217
218
219
220
            index: index,
            len: len
        }
    }
}

221
pub struct ASMCodeGen {
222
    cur: Option<Box<ASMCode>>
223
224
}

225
const REG_PLACEHOLDER_LEN : usize = 5;
qinsoon's avatar
qinsoon committed
226
227
228
229
230
231
lazy_static! {
    pub static ref REG_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN];
        
        format!("%{}", str::from_utf8(&blank_spaces).unwrap())
    };
232
233
234
235
}

impl ASMCodeGen {
    pub fn new() -> ASMCodeGen {
qinsoon's avatar
qinsoon committed
236
        ASMCodeGen {
237
            cur: None
qinsoon's avatar
qinsoon committed
238
239
240
241
242
243
244
245
246
247
248
        }
    }
    
    fn cur(&self) -> &ASMCode {
        self.cur.as_ref().unwrap()
    }
    
    fn cur_mut(&mut self) -> &mut ASMCode {
        self.cur.as_mut().unwrap()
    }
    
249
250
251
252
253
254
255
256
257
258
259
260
    fn line(&self) -> usize {
        self.cur().code.len()
    }
    
    fn add_asm_block_label(&mut self, code: String, block_name: &'static str) {
        let l = self.line();
        self.cur_mut().code.push(ASM::symbolic(code));
        
        self.cur_mut().idx_to_blk.insert(l, block_name);
        self.cur_mut().blk_to_idx.insert(block_name, l);
    }
    
261
262
263
264
    fn add_asm_symbolic(&mut self, code: String){
        self.cur_mut().code.push(ASM::symbolic(code));
    }
    
265
266
267
268
    fn prepare_machine_regs(&self, regs: Iter<P<Value>>) -> Vec<MuID> {
        regs.map(|x| self.prepare_machine_reg(x)).collect()
    } 
    
269
    fn add_asm_call(&mut self, code: String) {
270
271
272
273
274
275
        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
276
        self.add_asm_inst(code, defines, vec![], uses, vec![], false);
277
278
279
    }
    
    fn add_asm_ret(&mut self, code: String) {
280
281
282
        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
283
        self.add_asm_inst(code, vec![], vec![], uses, vec![], false);
284
285
286
287
288
    }
    
    fn add_asm_branch(&mut self, code: String, target: &'static str) {
        let l = self.line();
        self.cur_mut().branches.insert(l, target);
qinsoon's avatar
qinsoon committed
289
290
        
        self.add_asm_inst(code, vec![], vec![], vec![], vec![], false);
291
292
293
294
295
    }
    
    fn add_asm_branch2(&mut self, code: String, target: &'static str) {
        let l = self.line();
        self.cur_mut().cond_branches.insert(l, target);
qinsoon's avatar
qinsoon committed
296
297
        
        self.add_asm_inst(code, vec![], vec![], vec![], vec![], false);
298
299
300
301
302
303
    }
    
    fn add_asm_inst(
        &mut self, 
        code: String, 
        defines: Vec<MuID>,
304
        mut define_locs: Vec<ASMLocation>, 
305
        uses: Vec<MuID>,
qinsoon's avatar
qinsoon committed
306
307
        mut use_locs: Vec<ASMLocation>,
        is_using_mem_op: bool) 
308
    {
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
        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) {
339
                mc.reg_uses.get_mut(&id).unwrap().push(loc.clone());
340
            } else {
341
                mc.reg_uses.insert(id, vec![loc.clone()]);
342
343
            }
        }
344
       
345
346
        // put the instruction
        mc.code.push(ASM::inst(code, defines, uses));
qinsoon's avatar
qinsoon committed
347
        mc.mem_op_used.insert(line, is_using_mem_op);
348
349
350
351
    }
    
    fn define_reg(&mut self, reg: &P<Value>, loc: ASMLocation) {
        let id = reg.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
352
        
353
354
355
356
357
358
359
        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
360
361
362
363
364
365
    }
    
    fn use_reg(&mut self, reg: &P<Value>, loc: ASMLocation) {
        let id = reg.extract_ssa_id().unwrap();
        
        let code = self.cur_mut();
366
367
368
        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
369
        } else {
370
            code.reg_uses.insert(id, vec![loc]);
qinsoon's avatar
qinsoon committed
371
372
373
        } 
    }
    
374
    fn prepare_reg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
375
376
377
378
379
380
381
        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 {
        op.extract_ssa_id().unwrap()
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
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
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
    #[allow(unused_assignments)]
    fn prepare_mem(&self, op: &P<Value>, loc: usize) -> (String, Vec<MuID>, Vec<ASMLocation>) {
        let mut ids : Vec<MuID> = vec![];
        let mut locs : Vec<ASMLocation> = vec![];
        let mut result_str : String = "".to_string();
        
        let mut loc_cursor : usize = 0;
        
        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;
            },
            Value_::Memory(MemoryLocation::Symbolic{ref base, label}) => {
qinsoon's avatar
qinsoon committed
474
                result_str.push_str(&symbol(label));
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
                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
497
498
499
500
501
502
503
504
505
506
507
    fn asm_reg_op(&self, op: &P<Value>) -> String {
        let id = op.extract_ssa_id().unwrap();
        if id < RESERVED_NODE_IDS_FOR_MACHINE {
            // machine reg
            format!("%{}", op.tag)
        } else {
            // virtual register, use place holder
            REG_PLACEHOLDER.clone()
        }
    }
    
qinsoon's avatar
qinsoon committed
508
    fn asm_block_label(&self, label: MuName) -> String {
qinsoon's avatar
qinsoon committed
509
        symbol(&format!("{}_{}", self.cur().name, label))
510
    }
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
    
    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 {
                    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();
                let target_n = code.blk_to_idx.get(target).unwrap();
                
                // cur inst's succ is target
                code.succs[i].push(*target_n);
                
                // target's pred is cur
                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();
                    let target_n = code.blk_to_idx.get(target).unwrap();
                    
                    // cur insts' succ is target and next inst
                    code.succs[i].push(*target_n);
                    if i < n_insts - 1 {
                        code.succs[i].push(i + 1);
                    }
                    
                    // target's pred is cur
                    code.preds[*target_n].push(i);
                } else {
                    // not branch nor cond branch, succ is next inst
                    if i < n_insts - 1 {
                        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);
            }
        }        
    }
575
576
577
}

impl CodeGenerator for ASMCodeGen {
qinsoon's avatar
qinsoon committed
578
    fn start_code(&mut self, func_name: MuName) {
579
        self.cur = Some(Box::new(ASMCode {
qinsoon's avatar
qinsoon committed
580
581
                name: func_name,
                code: vec![],
582
                reg_defines: HashMap::new(),
583
584
                reg_uses: HashMap::new(),
                
qinsoon's avatar
qinsoon committed
585
586
                mem_op_used: HashMap::new(),
                
587
588
589
590
591
592
                preds: vec![],
                succs: vec![],
                
                idx_to_blk: HashMap::new(),
                blk_to_idx: HashMap::new(),
                cond_branches: HashMap::new(),
593
594
                branches: HashMap::new(),
                
595
596
597
598
                blocks: vec![],
                block_start: HashMap::new(),
                block_range: HashMap::new(),
                
599
600
                block_livein: HashMap::new(),
                block_liveout: HashMap::new()
601
            }));
qinsoon's avatar
qinsoon committed
602
        
qinsoon's avatar
qinsoon committed
603
        // to link with C sources via gcc
qinsoon's avatar
qinsoon committed
604
605
        self.add_asm_symbolic(directive_globl(symbol(func_name)));
        self.add_asm_symbolic(format!("{}:", symbol(func_name)));
qinsoon's avatar
qinsoon committed
606
607
    }
    
608
609
610
    fn finish_code(&mut self) -> Box<MachineCode> {
        self.control_flow_analysis();
        self.cur.take().unwrap()
qinsoon's avatar
qinsoon committed
611
612
613
614
615
616
617
618
619
    }
    
    fn print_cur_code(&self) {
        println!("");
        
        if self.cur.is_some() {
            let code = self.cur.as_ref().unwrap();
            
            println!("code for {}: ", code.name);
620
621
622
623
            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
624
625
626
627
628
629
630
631
            }
        } else {
            println!("no current code");
        }
        
        println!("");
    }
    
qinsoon's avatar
qinsoon committed
632
    fn start_block(&mut self, block_name: MuName) {
633
634
        let label = format!("{}:", self.asm_block_label(block_name));        
        self.add_asm_block_label(label, block_name);
635
636
637
638
639
640
        self.cur_mut().blocks.push(block_name);
        
        let start = self.line();
        self.cur_mut().block_start.insert(block_name, start);
    }
    
qinsoon's avatar
qinsoon committed
641
    fn end_block(&mut self, block_name: MuName) {
642
643
644
645
        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
646
647
    }
    
qinsoon's avatar
qinsoon committed
648
    fn set_block_livein(&mut self, block_name: MuName, live_in: &Vec<P<Value>>) {
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
        let cur = self.cur_mut();
        
        let mut res = {
            if !cur.block_livein.contains_key(&block_name) {
                cur.block_livein.insert(block_name, vec![]);
            } 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
666
    fn set_block_liveout(&mut self, block_name: MuName, live_out: &Vec<P<Value>>) {
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
        let cur = self.cur_mut();
        
        let mut res = {
            if !cur.block_liveout.contains_key(&block_name) {
                cur.block_liveout.insert(block_name, vec![]);
            } 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 => {}
            }
        }        
    }
    
687
    fn emit_cmp_r64_r64(&mut self, op1: &P<Value>, op2: &P<Value>) {
qinsoon's avatar
qinsoon committed
688
        trace!("emit: cmp {} {}", op1, op2);
qinsoon's avatar
qinsoon committed
689
        
690
691
        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
692
        
qinsoon's avatar
qinsoon committed
693
        let asm = format!("cmpq {},{}", reg1, reg2);
qinsoon's avatar
qinsoon committed
694
        
695
696
697
698
699
        self.add_asm_inst(
            asm,
            vec![],
            vec![],
            vec![id1, id2],
qinsoon's avatar
qinsoon committed
700
701
            vec![loc1, loc2],
            false
702
        );
703
704
    }
    
qinsoon's avatar
qinsoon committed
705
706
    fn emit_cmp_r64_imm32(&mut self, op1: &P<Value>, op2: u32) {
        trace!("emit: cmp {} {}", op1, op2);
qinsoon's avatar
qinsoon committed
707
        
708
        let (reg1, id1, loc1) = self.prepare_reg(op1, 4 + 1 + 1 + op2.to_string().len() + 1);
qinsoon's avatar
qinsoon committed
709
        
qinsoon's avatar
qinsoon committed
710
        let asm = format!("cmpq ${},{}", op2, reg1);
qinsoon's avatar
qinsoon committed
711
        
712
713
714
715
716
        self.add_asm_inst(
            asm,
            vec![],
            vec![],
            vec![id1],
qinsoon's avatar
qinsoon committed
717
718
            vec![loc1],
            false
719
        )
720
721
722
    }
    
    fn emit_cmp_r64_mem64(&mut self, op1: &P<Value>, op2: &P<Value>) {
qinsoon's avatar
qinsoon committed
723
        trace!("emit: cmp {} {}", op1, op2);
qinsoon's avatar
qinsoon committed
724
        unimplemented!()
725
726
    }
    
qinsoon's avatar
qinsoon committed
727
728
    fn emit_mov_r64_imm32(&mut self, dest: &P<Value>, src: u32) {
        trace!("emit: mov {} -> {}", src, dest);
qinsoon's avatar
qinsoon committed
729
        
730
        let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1);
qinsoon's avatar
qinsoon committed
731
        
qinsoon's avatar
qinsoon committed
732
        let asm = format!("movq ${},{}", src, reg1);
qinsoon's avatar
qinsoon committed
733
        
734
735
736
        self.add_asm_inst(
            asm,
            vec![id1],
737
738
            vec![loc1],
            vec![],
qinsoon's avatar
qinsoon committed
739
740
            vec![],
            false
741
        )
742
743
744
    }
    
    fn emit_mov_r64_mem64(&mut self, dest: &P<Value>, src: &P<Value>) {
qinsoon's avatar
qinsoon committed
745
        trace!("emit: mov {} -> {}", src, dest);
746
747
748
749
750
751
752
753
754
755
756
        
        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
757
758
            loc1,
            true
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
        )
    }
    
    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'
        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
779
780
            loc2,
            true
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
        )
    }
    
    fn emit_mov_mem64_imm32(&mut self, dest: &P<Value>, src: u32) {
        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
796
797
            loc,
            true
798
        )
qinsoon's avatar
qinsoon committed
799
800
801
802
    }
    
    fn emit_mov_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: mov {} -> {}", src, dest);
qinsoon's avatar
qinsoon committed
803
        
804
805
        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
806
        
qinsoon's avatar
qinsoon committed
807
        let asm = format!("movq {},{}", reg1, reg2);
qinsoon's avatar
qinsoon committed
808
        
809
810
811
        self.add_asm_inst(
            asm,
            vec![id2],
812
813
            vec![loc2],
            vec![id1],
qinsoon's avatar
qinsoon committed
814
815
            vec![loc1],
            false
816
        )
qinsoon's avatar
qinsoon committed
817
818
819
820
    }
    
    fn emit_add_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: add {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
821
        
822
823
        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
824
        
qinsoon's avatar
qinsoon committed
825
        let asm = format!("addq {},{}", reg1, reg2);
qinsoon's avatar
qinsoon committed
826
        
827
828
        self.add_asm_inst(
            asm,
829
830
            vec![id2],
            vec![loc2.clone()],
831
            vec![id1, id2],
qinsoon's avatar
qinsoon committed
832
833
            vec![loc1, loc2],
            false
834
        )
qinsoon's avatar
qinsoon committed
835
836
837
838
    }
    
    fn emit_add_r64_mem64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: add {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
839
        unimplemented!()
qinsoon's avatar
qinsoon committed
840
841
842
843
    }
    
    fn emit_add_r64_imm32(&mut self, dest: &P<Value>, src: u32) {
        trace!("emit: add {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
844
        
845
        let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1);
qinsoon's avatar
qinsoon committed
846
        
qinsoon's avatar
qinsoon committed
847
        let asm = format!("addq {},${}", src, reg1);
qinsoon's avatar
qinsoon committed
848
        
849
850
851
852
853
        self.add_asm_inst(
            asm,
            vec![id1],
            vec![loc1.clone()],
            vec![id1],
qinsoon's avatar
qinsoon committed
854
855
            vec![loc1],
            false
856
        )
qinsoon's avatar
qinsoon committed
857
858
859
860
    }
    
    fn emit_sub_r64_r64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: sub {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
861
        
862
863
        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
864
        
qinsoon's avatar
qinsoon committed
865
        let asm = format!("subq {},{}", reg1, reg2);
qinsoon's avatar
qinsoon committed
866
        
867
868
        self.add_asm_inst(
            asm,
869
870
            vec![id2],
            vec![loc2.clone()],
871
            vec![id1, id2],
qinsoon's avatar
qinsoon committed
872
873
            vec![loc1, loc2],
            false
874
        )        
qinsoon's avatar
qinsoon committed
875
876
877
878
    }
    
    fn emit_sub_r64_mem64(&mut self, dest: &P<Value>, src: &P<Value>) {
        trace!("emit: sub {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
879
        unimplemented!()
qinsoon's avatar
qinsoon committed
880
881
882
883
    }
    
    fn emit_sub_r64_imm32(&mut self, dest: &P<Value>, src: u32) {
        trace!("emit: sub {}, {} -> {}", dest, src, dest);
qinsoon's avatar
qinsoon committed
884
        
885
        let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1);
qinsoon's avatar
qinsoon committed
886
        
qinsoon's avatar
qinsoon committed
887
        let asm = format!("subq ${},{}", src, reg1);
qinsoon's avatar
qinsoon committed
888
        
889
890
891
892
893
        self.add_asm_inst(
            asm,
            vec![id1],
            vec![loc1.clone()],
            vec![id1],
qinsoon's avatar
qinsoon committed
894
895
            vec![loc1],
            false
896
        )        
qinsoon's avatar
qinsoon committed
897
898
    }
    
899
    fn emit_mul_r64(&mut self, src: &P<Value>) {
900
        trace!("emit: mul rax, {} -> (rdx, rax)", src);
qinsoon's avatar
qinsoon committed
901
        
902
        let (reg, id, loc) = self.prepare_reg(src, 3 + 1);
903
904
        let rax = self.prepare_machine_reg(&x86_64::RAX);
        let rdx = self.prepare_machine_reg(&x86_64::RDX);
qinsoon's avatar
qinsoon committed
905
906
907
        
        let asm = format!("mul {}", reg);
        
908
909
910
911
912
        self.add_asm_inst(
            asm,
            vec![rax, rdx],
            vec![],
            vec![id, rax],
qinsoon's avatar
qinsoon committed
913
914
            vec![loc],
            false
915
        )
916
917
918
919
    }
    
    fn emit_mul_mem64(&mut self, src: &P<Value>) {
        trace!("emit: mul rax, {} -> rax", src);
qinsoon's avatar
qinsoon committed
920
        unimplemented!()
921
922
    }
    
qinsoon's avatar
qinsoon committed
923
924
    fn emit_jmp(&mut self, dest: &Destination) {
        trace!("emit: jmp {}", dest.target);
qinsoon's avatar
qinsoon committed
925
926
927
        
        // symbolic label, we dont need to patch it
        let asm = format!("jmp {}", self.asm_block_label(dest.target));
928
        self.add_asm_branch(asm, dest.target)
qinsoon's avatar
qinsoon committed
929
930
931
932
    }
    
    fn emit_je(&mut self, dest: &Destination) {
        trace!("emit: je {}", dest.target);
qinsoon's avatar
qinsoon committed
933
934
        
        let asm = format!("je {}", self.asm_block_label(dest.target));
935
        self.add_asm_branch2(asm, dest.target);        
qinsoon's avatar
qinsoon committed
936
937
938
939
    }
    
    fn emit_jne(&mut self, dest: &Destination) {
        trace!("emit: jne {}", dest.target);
qinsoon's avatar
qinsoon committed
940
941
        
        let asm = format!("jne {}", self.asm_block_label(dest.target));
942
        self.add_asm_branch2(asm, dest.target);
qinsoon's avatar
qinsoon committed
943
944
945
946
    }
    
    fn emit_ja(&mut self, dest: &Destination) {
        trace!("emit: ja {}", dest.target);
qinsoon's avatar
qinsoon committed
947
948
        
        let asm = format!("ja {}", self.asm_block_label(dest.target));
949
        self.add_asm_branch2(asm, dest.target);
qinsoon's avatar
qinsoon committed
950
951
952
953
    }
    
    fn emit_jae(&mut self, dest: &Destination) {
        trace!("emit: jae {}", dest.target);
qinsoon's avatar
qinsoon committed
954
955
        
        let asm = format!("jae {}", self.asm_block_label(dest.target));
956
        self.add_asm_branch2(asm, dest.target);        
qinsoon's avatar
qinsoon committed
957
958
959
960
    }
    
    fn emit_jb(&mut self, dest: &Destination) {
        trace!("emit: jb {}", dest.target);
qinsoon's avatar
qinsoon committed
961
962
        
        let asm = format!("jb {}", self.asm_block_label(dest.target));
963
        self.add_asm_branch2(asm, dest.target);
qinsoon's avatar
qinsoon committed
964
965
966
967
    }
    
    fn emit_jbe(&mut self, dest: &Destination) {
        trace!("emit: jbe {}", dest.target);
qinsoon's avatar
qinsoon committed
968
969
        
        let asm = format!("jbe {}", self.asm_block_label(dest.target));
970
        self.add_asm_branch2(asm, dest.target);        
qinsoon's avatar
qinsoon committed
971
972
    }
    
qinsoon's avatar
qinsoon committed
973
974
    fn emit_jg(&mut self, dest: &Destination) {
        trace!("emit: jg {}", dest.target);
qinsoon's avatar
qinsoon committed
975
976
        
        let asm = format!("jg {}", self.asm_block_label(dest.target));
977
        self.add_asm_branch2(asm, dest.target);        
qinsoon's avatar
qinsoon committed
978
979
980
981
    }
    
    fn emit_jge(&mut self, dest: &Destination) {
        trace!("emit: jge {}", dest.target);
qinsoon's avatar
qinsoon committed
982
983
        
        let asm = format!("jge {}", self.asm_block_label(dest.target));
984
        self.add_asm_branch2(asm, dest.target);        
qinsoon's avatar
qinsoon committed
985
986
987
988
    }
    
    fn emit_jl(&mut self, dest: &Destination) {
        trace!("emit: jl {}", dest.target);
qinsoon's avatar
qinsoon committed
989
990
        
        let asm = format!("jl {}", self.asm_block_label(dest.target));
991
        self.add_asm_branch2(asm, dest.target);        
qinsoon's avatar
qinsoon committed
992
993
994
995
    }
    
    fn emit_jle(&mut self, dest: &Destination) {
        trace!("emit: jle {}", dest.target);
qinsoon's avatar
qinsoon committed
996
997
        
        let asm = format!("jle {}", self.asm_block_label(dest.target));
998
        self.add_asm_branch2(asm, dest.target);        
qinsoon's avatar
qinsoon committed
999
1000
    }    
    
qinsoon's avatar
qinsoon committed
1001
    fn emit_call_near_rel32(&mut self, func: MuName) {
1002
        trace!("emit: call {}", func);
qinsoon's avatar
qinsoon committed
1003
        
qinsoon's avatar
qinsoon committed
1004
        let asm = format!("call {}", symbol(func));
1005
        self.add_asm_call(asm);
1006
1007
        
        // FIXME: call interferes with machine registers
1008
1009
1010
1011
    }
    
    fn emit_call_near_r64(&mut self, func: &P<Value>) {
        trace!("emit: call {}", func);
qinsoon's avatar
qinsoon committed
1012
        unimplemented!()
1013
1014
1015
    }
    
    fn emit_call_near_mem64(&mut self, func: &P<Value>) {
qinsoon's avatar
qinsoon committed
1016
        trace!("emit: call {}", func);
qinsoon's avatar
qinsoon committed
1017
        unimplemented!()
qinsoon's avatar
qinsoon committed
1018
1019
1020
1021
    }
    
    fn emit_ret(&mut self) {
        trace!("emit: ret");
qinsoon's avatar
qinsoon committed
1022
1023
        
        let asm = format!("ret");
1024
        self.add_asm_ret(asm);
1025
    }
1026
    
qinsoon's avatar
qinsoon committed
1027
    fn emit_push_r64(&mut self, src: &P<Value>) {
1028
        trace!("emit: push {}", src);
qinsoon's avatar
qinsoon committed
1029
        
1030
        let (reg, id, loc) = self.prepare_reg(src, 5 + 1);
1031
        let rsp = self.prepare_machine_reg(&x86_64::RSP);
qinsoon's avatar
qinsoon committed
1032
1033
1034
        
        let asm = format!("pushq {}", reg);
        
1035
1036
        self.add_asm_inst(
            asm,
1037
            vec![rsp],
1038
1039
            vec![],
            vec![id, rsp],
qinsoon's avatar
qinsoon committed
1040
1041
            vec![loc],
            false
1042
        )
1043
1044
    }
    
qinsoon's avatar
qinsoon committed
1045
    fn emit_pop_r64(&mut self, dest: &P<Value>) {
1046
        trace!("emit: pop {}", dest);
qinsoon's avatar
qinsoon committed
1047
        
1048
        let (reg, id, loc) = self.prepare_reg(dest, 4 + 1);
1049
        let rsp = self.prepare_machine_reg(&x86_64::RSP);
qinsoon's avatar
qinsoon committed
1050
1051
1052
        
        let asm = format!("popq {}", reg);
        
1053
1054
        self.add_asm_inst(
            asm,
1055
            vec![id, rsp],
1056
            vec![loc.clone()],
1057
            vec![rsp],
qinsoon's avatar
qinsoon committed
1058
1059
            vec![],
            false
1060
        )        
1061
    }    
1062
}
1063

qinsoon's avatar
qinsoon committed
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
const EMIT_DIR : &'static str = "emit";

fn create_emit_directory() {
    use std::fs;    
    match fs::create_dir(EMIT_DIR) {
        Ok(_) => {},
        Err(_) => {}
    }    
}

qinsoon's avatar
qinsoon committed
1074
pub fn emit_code(func: &mut MuFunctionVersion, vm: &VM) {
1075
1076
    use std::io::prelude::*;
    use std::fs::File;
qinsoon's avatar
qinsoon committed
1077
    use std::path;
1078
1079
1080
1081
1082
1083

    let compiled_funcs = vm.compiled_funcs().read().unwrap();
    let cf = compiled_funcs.get(func.fn_name).unwrap().borrow();

    let code = cf.mc.emit();

qinsoon's avatar
qinsoon committed
1084
1085
    // create 'emit' directory
    create_emit_directory();
1086

qinsoon's avatar
qinsoon committed
1087
1088
1089
1090
1091
    let mut file_path = path::PathBuf::new();
    file_path.push(EMIT_DIR);
    file_path.push(func.fn_name.to_string() + ".s");
    let mut file = match File::create(file_path.as_path()) {
        Err(why) => panic!("couldn't create emission file {}: {}", file_path.to_str().unwrap(), why),
1092
1093
1094
1095
        Ok(file) => file
    };

    match file.write_all(code.as_slice()) {
qinsoon's avatar
qinsoon committed
1096
1097
        Err(why) => panic!("couldn'd write to file {}: {}", file_path.to_str().unwrap(), why),
        Ok(_) => println!("emit code to {}", file_path.to_str().unwrap())
1098
1099
1100
    }
}

qinsoon's avatar
qinsoon committed
1101
const CONTEXT_FILE : &'static str = "context.s";
qinsoon's avatar
qinsoon committed
1102
pub fn emit_context(vm: &VM) {
qinsoon's avatar
qinsoon committed
1103
1104
1105
1106
    use std::path;
    use std::fs::File;
    use std::io::prelude::*;
    
1107
    debug!("---Emit VM Context---");
qinsoon's avatar
qinsoon committed
1108
1109
1110
1111
1112
1113
1114
1115
1116
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
1131
1132
    create_emit_directory();
    
    let mut file_path = path::PathBuf::new();
    file_path.push(EMIT_DIR);
    file_path.push(CONTEXT_FILE);
    
    let mut file = match File::create(file_path.as_path()) {
        Err(why) => panic!("couldn't create context file {}: {}", file_path.to_str().unwrap(), why),
        Ok(file) => file
    };
    
    // put globals into bss section
    file.write_fmt(format_args!("\t.bss\n")).unwrap();
    
    let globals = vm.globals().read().unwrap();
    for cell in globals.values() {
        let (size, align) = {
            let ty_info = vm.get_backend_type_info(&cell.ty);
            (ty_info.size, ty_info.alignment)
        };
        
        file.write_fmt(format_args!("\t{}\n", directive_globl(symbol(cell.tag)))).unwrap();
        file.write_fmt(format_args!("\t{}\n", directive_comm(symbol(cell.tag), size, align))).unwrap();
        file.write("\n".as_bytes()).unwrap();
    }
1133
1134
    
    debug!("---finish---");
qinsoon's avatar
qinsoon committed
1135
1136
1137
1138
1139
1140
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150
1151
1152
}

fn directive_globl(name: String) -> String {
    format!(".globl {}", name)
}

fn directive_comm(name: String, size: ByteSize, align: ByteSize) -> String {
    format!(".comm {},{},{}", name, size, align)
}

#[cfg(target_os = "linux")]
fn symbol(name: &str) -> String {
    name.to_string()
}

#[cfg(target_os = "macos")]
fn symbol(name: &str) -> String {
    format!("_{}", name)
qinsoon's avatar
qinsoon committed
1153
}