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.

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

3
use compiler::backend::AOT_EMIT_CONTEXT_FILE;
qinsoon's avatar
qinsoon committed
4
use compiler::backend::RegGroup;
qinsoon's avatar
qinsoon committed
5
use utils::ByteSize;
6
7
use utils::Address;
use utils::POINTER_SIZE;
8
use compiler::backend::x86_64;
9
use compiler::backend::x86_64::CodeGenerator;
qinsoon's avatar
qinsoon committed
10
use compiler::backend::{Reg, Mem};
qinsoon's avatar
qinsoon committed
11
use compiler::backend::x86_64::check_op_len;
qinsoon's avatar
qinsoon committed
12
use compiler::machine_code::MachineCode;
qinsoon's avatar
qinsoon committed
13
use vm::VM;
qinsoon's avatar
qinsoon committed
14
use runtime::ValueLocation;
15

qinsoon's avatar
qinsoon committed
16
use utils::vec_utils;
17
use utils::string_utils;
18
19
use utils::LinkedHashMap;

20
21
use ast::ptr::P;
use ast::ir::*;
qinsoon's avatar
qinsoon committed
22
use ast::types::*;
23

qinsoon's avatar
qinsoon committed
24
25
use std::collections::HashMap;
use std::str;
26
use std::usize;
27
use std::slice::Iter;
28
use std::ops;
qinsoon's avatar
qinsoon committed
29
30

struct ASMCode {
qinsoon's avatar
qinsoon committed
31
    name: MuName, 
qinsoon's avatar
qinsoon committed
32
    code: Vec<ASMInst>,
qinsoon's avatar
qinsoon committed
33

34
    blocks: LinkedHashMap<MuName, ASMBlock>,
qinsoon's avatar
qinsoon committed
35
36

    frame_size_patchpoints: Vec<ASMLocation>
qinsoon's avatar
qinsoon committed
37
38
}

qinsoon's avatar
qinsoon committed
39
40
41
unsafe impl Send for ASMCode {} 
unsafe impl Sync for ASMCode {}

42
impl ASMCode {
qinsoon's avatar
qinsoon committed
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
    fn get_use_locations(&self, reg: MuID) -> Vec<ASMLocation> {
        let mut ret = vec![];

        for inst in self.code.iter() {
            match inst.uses.get(&reg) {
                Some(ref locs) => {
                    ret.append(&mut locs.to_vec());
                },
                None => {}
            }
        }

        ret
    }

    fn get_define_locations(&self, reg: MuID) -> Vec<ASMLocation> {
        let mut ret = vec![];

        for inst in self.code.iter() {
            match inst.defines.get(&reg) {
                Some(ref locs) => {
                    ret.append(&mut locs.to_vec());
                },
                None => {}
            }
        }

        ret
    }

qinsoon's avatar
qinsoon committed
73
74
75
76
77
78
79
80
81
    fn is_block_start(&self, inst: usize) -> bool {
        for block in self.blocks.values() {
            if block.start_inst == inst {
                return true;
            }
        }
        false
    }

82
    fn is_last_inst_in_block(&self, inst: usize) -> bool {
qinsoon's avatar
qinsoon committed
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
        for block in self.blocks.values() {
            if block.end_inst == inst + 1 {
                return true;
            }
        }
        false
    }

    fn get_block_by_inst(&self, inst: usize) -> (&String, &ASMBlock) {
        for (name, block) in self.blocks.iter() {
            if inst >= block.start_inst && inst < block.end_inst {
                return (name, block);
            }
        }

        panic!("didnt find any block for inst {}", inst)
    }

qinsoon's avatar
qinsoon committed
101
102
103
104
105
106
107
108
109
110
    fn get_block_by_start_inst(&self, inst: usize) -> Option<&ASMBlock> {
        for block in self.blocks.values() {
            if block.start_inst == inst {
                return Some(block);
            }
        }

        None
    }

111
112
113
114
115
    fn rewrite_insert(
        &self,
        insert_before: HashMap<usize, Vec<Box<ASMCode>>>,
        insert_after: HashMap<usize, Vec<Box<ASMCode>>>) -> Box<ASMCode>
    {
116
        trace!("insert spilling code");
117
118
119
        let mut ret = ASMCode {
            name: self.name.clone(),
            code: vec![],
120
            blocks: linked_hashmap!{},
qinsoon's avatar
qinsoon committed
121
            frame_size_patchpoints: vec![]
122
123
124
125
        };

        // iterate through old machine code
        let mut inst_offset = 0;    // how many instructions has been inserted
qinsoon's avatar
qinsoon committed
126
        let mut cur_block_start = usize::MAX;
127

qinsoon's avatar
qinsoon committed
128
129
130
131
        // inst N in old machine code is N' in new machine code
        // this map stores the relationship
        let mut location_map : HashMap<usize, usize> = HashMap::new();

132
        for i in 0..self.number_of_insts() {
133
134
            trace!("Inst{}", i);

qinsoon's avatar
qinsoon committed
135
136
            if self.is_block_start(i) {
                cur_block_start = i + inst_offset;
137
                trace!("  block start is shifted to {}", cur_block_start);
qinsoon's avatar
qinsoon committed
138
139
            }

140
141
142
143
144
            // insert code before this instruction
            if insert_before.contains_key(&i) {
                for insert in insert_before.get(&i).unwrap() {
                    ret.append_code_sequence_all(insert);
                    inst_offset += insert.number_of_insts();
145
                    trace!("  inserted {} insts before", insert.number_of_insts());
146
147
148
149
                }
            }

            // copy this instruction
qinsoon's avatar
qinsoon committed
150
151
            let mut inst = self.code[i].clone();

qinsoon's avatar
qinsoon committed
152
153
            // old ith inst is now the (i + inst_offset)th instruction
            location_map.insert(i, i + inst_offset);
154
            trace!("  Inst{} is now Inst{}", i, i + inst_offset);
qinsoon's avatar
qinsoon committed
155

qinsoon's avatar
qinsoon committed
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
            // this instruction has been offset by several instructions('inst_offset')
            // update its info
            // 1. fix defines and uses
            for locs in inst.defines.values_mut() {
                for loc in locs {
                    debug_assert!(loc.line == i);
                    loc.line += inst_offset;
                }
            }
            for locs in inst.uses.values_mut() {
                for loc in locs {
                    debug_assert!(loc.line == i);
                    loc.line += inst_offset;
                }
            }
qinsoon's avatar
qinsoon committed
171
172
173
            // 2. we need to delete existing preds/succs - CFA is required later
            inst.preds.clear();
            inst.succs.clear();
qinsoon's avatar
qinsoon committed
174
175
            // 3. add the inst
            ret.code.push(inst);
176
177
178
179


            // insert code after this instruction
            if insert_after.contains_key(&i) {
qinsoon's avatar
qinsoon committed
180
181
182
                for insert in insert_after.get(&i).unwrap() {
                    ret.append_code_sequence_all(insert);
                    inst_offset += insert.number_of_insts();
183
                    trace!("  inserted {} insts after", insert.number_of_insts());
qinsoon's avatar
qinsoon committed
184
185
186
                }
            }

187
188
            if self.is_last_inst_in_block(i) {
                let cur_block_end = i + 1 + inst_offset;
189

qinsoon's avatar
qinsoon committed
190
191
192
                // copy the block
                let (name, block) = self.get_block_by_inst(i);

qinsoon's avatar
qinsoon committed
193
                let new_block = ASMBlock{
194
195
196
197
198
199
200
201
202
203
                    start_inst: cur_block_start,
                    end_inst: cur_block_end,

                    livein: vec![],
                    liveout: vec![]
                };

                trace!("  old block: {:?}", block);
                trace!("  new block: {:?}", new_block);

qinsoon's avatar
qinsoon committed
204
205
206
207
                cur_block_start = usize::MAX;

                // add to the new code
                ret.blocks.insert(name.clone(), new_block);
208
209
210
            }
        }

qinsoon's avatar
qinsoon committed
211
212
213
214
215
        // fix patchpoint
        for patchpoint in self.frame_size_patchpoints.iter() {
            let new_patchpoint = ASMLocation {
                line: *location_map.get(&patchpoint.line).unwrap(),
                index: patchpoint.index,
qinsoon's avatar
qinsoon committed
216
217
                len: patchpoint.len,
                oplen: patchpoint.oplen
qinsoon's avatar
qinsoon committed
218
219
220
221
222
            };

            ret.frame_size_patchpoints.push(new_patchpoint);
        }

qinsoon's avatar
qinsoon committed
223
224
225
        ret.control_flow_analysis();

        Box::new(ret)
226
227
228
229
230
231
232
233
    }

    fn append_code_sequence(
        &mut self,
        another: &Box<ASMCode>,
        start_inst: usize,
        n_insts: usize)
    {
qinsoon's avatar
qinsoon committed
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
        let base_line = self.number_of_insts();

        for i in 0..n_insts {
            let cur_line_in_self = base_line + i;
            let cur_line_from_copy = start_inst + i;

            let mut inst = another.code[cur_line_from_copy].clone();

            // fix info
            for locs in inst.defines.values_mut() {
                for loc in locs {
                    debug_assert!(loc.line == i);
                    loc.line = cur_line_in_self;
                }
            }
            for locs in inst.uses.values_mut() {
                for loc in locs {
                    debug_assert!(loc.line == i);
                    loc.line = cur_line_in_self;
                }
            }
            // ignore preds/succs

            // add to self
            self.code.push(inst);
        }
260
261
262
263
264
265
    }

    fn append_code_sequence_all(&mut self, another: &Box<ASMCode>) {
        let n_insts = another.number_of_insts();
        self.append_code_sequence(another, 0, n_insts)
    }
qinsoon's avatar
qinsoon committed
266
267

    fn control_flow_analysis(&mut self) {
268
        const TRACE_CFA : bool = true;
qinsoon's avatar
qinsoon committed
269
270
271
272
273
274
275
276
277
278

        // control flow analysis
        let n_insts = self.number_of_insts();

        let ref blocks = self.blocks;
        let ref mut asm = self.code;

        let block_start = {
            let mut ret = vec![];
            for block in blocks.values() {
279
280
281
                if TRACE_CFA {
                    trace!("Block starts at {}", block.start_inst);
                }
qinsoon's avatar
qinsoon committed
282
283
284
285
286
287
                ret.push(block.start_inst);
            }
            ret
        };

        for i in 0..n_insts {
qinsoon's avatar
[wip]    
qinsoon committed
288
289
290
            if TRACE_CFA {
                trace!("---inst {}---", i);
            }
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319

            // skip symbol
            if asm[i].is_symbol {
                continue;
            }

            // determine predecessor

            // we check if it is a fallthrough block
            if i != 0 {
                let last_inst = ASMCode::find_prev_inst(i, asm);

                match last_inst {
                    Some(last_inst) => {
                        let last_inst_branch = asm[last_inst].branch.clone();
                        match last_inst_branch {
                            // if it is a fallthrough, we set its preds as last inst
                            ASMBranchTarget::None => {
                                if !asm[i].preds.contains(&last_inst) {
                                    asm[i].preds.push(last_inst);

                                    if TRACE_CFA {
                                        trace!("inst {}: set PREDS as previous inst - fallthrough {}", i, last_inst);
                                    }
                                }
                            }
                            // otherwise do nothing
                            _ => {}
                        }
qinsoon's avatar
qinsoon committed
320
                    }
321
                    None => {}
qinsoon's avatar
qinsoon committed
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
                }
            }

            // determine successor
            let branch = asm[i].branch.clone();
            match branch {
                ASMBranchTarget::Unconditional(ref target) => {
                    // branch to target
                    let target_n = self.blocks.get(target).unwrap().start_inst;

                    // cur inst's succ is target
                    asm[i].succs.push(target_n);

                    // target's pred is cur
                    asm[target_n].preds.push(i);

                    if TRACE_CFA {
                        trace!("inst {}: is a branch to {}", i, target);
                        trace!("inst {}: branch target index is {}", i, target_n);
                        trace!("inst {}: set SUCCS as branch target {}", i, target_n);
                        trace!("inst {}: set PREDS as branch source {}", target_n, i);
                    }
                },
                ASMBranchTarget::Conditional(ref target) => {
                    // branch to target
                    let target_n = self.blocks.get(target).unwrap().start_inst;

349
                    // cur insts' succ is target
qinsoon's avatar
qinsoon committed
350
351
352
353
354
355
356
357
358
359
360
361
362
                    asm[i].succs.push(target_n);

                    if TRACE_CFA {
                        trace!("inst {}: is a cond branch to {}", i, target);
                        trace!("inst {}: branch target index is {}", i, target_n);
                        trace!("inst {}: set SUCCS as branch target {}", i, target_n);
                    }

                    // target's pred is cur
                    asm[target_n].preds.push(i);
                    if TRACE_CFA {
                        trace!("inst {}: set PREDS as {}", target_n, i);
                    }
363
364
365
366
367
368
369
370
371
372
373
374
375
376

                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
                        // cur succ is next inst
                        asm[i].succs.push(next_inst);

                        // next inst's pred is cur
                        asm[next_inst].preds.push(i);

                        if TRACE_CFA {
                            trace!("inst {}: SET SUCCS as c-branch fallthrough target {}", i, next_inst);
                        }
                    } else {
                        panic!("conditional branch does not have a fallthrough target");
                    }
qinsoon's avatar
qinsoon committed
377
                },
qinsoon's avatar
[wip]    
qinsoon committed
378
379
380
381
382
383
                ASMBranchTarget::Return => {
                    if TRACE_CFA {
                        trace!("inst {}: is a return", i);
                        trace!("inst {}: has no successor", i);
                    }
                }
qinsoon's avatar
qinsoon committed
384
385
386
387
388
                ASMBranchTarget::None => {
                    // not branch nor cond branch, succ is next inst
                    if TRACE_CFA {
                        trace!("inst {}: not a branch inst", i);
                    }
389
                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
qinsoon's avatar
qinsoon committed
390
                        if TRACE_CFA {
391
                            trace!("inst {}: set SUCCS as next inst {}", i, next_inst);
qinsoon's avatar
qinsoon committed
392
                        }
393
                        asm[i].succs.push(next_inst);
qinsoon's avatar
qinsoon committed
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
    }

    fn find_prev_inst(i: usize, asm: &Vec<ASMInst>) -> Option<usize> {
        if i == 0 {
            None
        } else {
            let mut cur = i - 1;
            while cur != 0 {
                if !asm[cur].is_symbol {
                    return Some(cur);
                }

                if cur == 0 {
                    return None;
                } else {
                    cur -= 1;
                }
            }

            None
        }
    }
qinsoon's avatar
qinsoon committed
420

421
422
423
424
425
426
427
428
429
430
431
    fn find_next_inst(i: usize, asm: &Vec<ASMInst>) -> Option<usize> {
        if i >= asm.len() - 1 {
            None
        } else {
            let mut cur = i + 1;
            while cur < asm.len() {
                if !asm[cur].is_symbol {
                    return Some(cur);
                }

                cur += 1;
qinsoon's avatar
qinsoon committed
432
            }
433
434

            None
qinsoon's avatar
qinsoon committed
435
436
        }
    }
qinsoon's avatar
qinsoon committed
437
438
439
440

    fn add_frame_size_patchpoint(&mut self, patchpoint: ASMLocation) {
        self.frame_size_patchpoints.push(patchpoint);
    }
441
442
443
444
}

use std::any::Any;

445
impl MachineCode for ASMCode {
446
447
448
    fn as_any(&self) -> &Any {
        self
    }
449
450
451
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
qinsoon's avatar
qinsoon committed
452
    
453
454
455
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
qinsoon's avatar
qinsoon committed
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
            Some(inst) => {
                let ref inst = inst.code;

                if inst.starts_with("movsd") || inst.starts_with("movss") {
                    // floating point move
                    true
                } else if inst.starts_with("movs") || inst.starts_with("movz") {
                    // sign extend, zero extend
                    false
                } else if inst.starts_with("mov") {
                    // normal mov
                    true
                } else {
                    false
                }
            },
472
473
474
475
            None => false
        }
    }
    
qinsoon's avatar
qinsoon committed
476
    fn is_using_mem_op(&self, index: usize) -> bool {
qinsoon's avatar
qinsoon committed
477
        self.code[index].is_mem_op_used
qinsoon's avatar
qinsoon committed
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

    fn is_jmp(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
            Some(inst) if inst.code.starts_with("jmp") => {
                let split : Vec<&str> = inst.code.split(' ').collect();

                Some(String::from(split[1]))
            }
            _ => None
        }
    }

    fn is_label(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
            Some(inst) if inst.code.ends_with(':') => {
                let split : Vec<&str> = inst.code.split(':').collect();

                Some(String::from(split[0]))
            }
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
503
    
qinsoon's avatar
qinsoon committed
504
    fn get_succs(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
505
        &self.code[index].succs
qinsoon's avatar
qinsoon committed
506
507
508
    }
    
    fn get_preds(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
509
        &self.code[index].preds
qinsoon's avatar
qinsoon committed
510
511
    }
    
qinsoon's avatar
qinsoon committed
512
513
    fn get_inst_reg_uses(&self, index: usize) -> Vec<MuID> {
        self.code[index].uses.keys().map(|x| *x).collect()
514
515
    }
    
qinsoon's avatar
qinsoon committed
516
517
    fn get_inst_reg_defines(&self, index: usize) -> Vec<MuID> {
        self.code[index].defines.keys().map(|x| *x).collect()
518
    }
519
    
520
    fn replace_reg(&mut self, from: MuID, to: MuID) {
qinsoon's avatar
qinsoon committed
521
522
        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
523
524
525
526
527
528
529

            // pick the right reg based on length
            let to_reg = x86_64::get_alias_for_length(to, loc.oplen);
            let to_reg_tag = to_reg.name().unwrap();
            let to_reg_string = "%".to_string() + &to_reg_tag;

            string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
530
        }
531

qinsoon's avatar
qinsoon committed
532
533
        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
534
535
536
537
538
539
540

            // pick the right reg based on length
            let to_reg = x86_64::get_alias_for_length(to, loc.oplen);
            let to_reg_tag = to_reg.name().unwrap();
            let to_reg_string = "%".to_string() + &to_reg_tag;

            string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
541
542
        }
    }
543

544
    fn replace_define_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
qinsoon's avatar
qinsoon committed
545
        let to_reg_string : MuName = REG_PLACEHOLDER.clone();
546

qinsoon's avatar
qinsoon committed
547
548
549
550
551
552
        let asm = &mut self.code[inst];
        // if this reg is defined, replace the define
        if asm.defines.contains_key(&from) {
            let define_locs = asm.defines.get(&from).unwrap().to_vec();
            // replace temps
            for loc in define_locs.iter() {
qinsoon's avatar
qinsoon committed
553
                string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
554
555
            }

qinsoon's avatar
qinsoon committed
556
557
            // remove old key, insert new one
            asm.defines.remove(&from);
558
            asm.defines.insert(to, define_locs);
559
        }
560
561
562
    }

    fn replace_use_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
qinsoon's avatar
qinsoon committed
563
        let to_reg_string : MuName = REG_PLACEHOLDER.clone();
564
565

        let asm = &mut self.code[inst];
qinsoon's avatar
qinsoon committed
566
567
568
569
570
571

        // if this reg is used, replace the use
        if asm.uses.contains_key(&from) {
            let use_locs = asm.uses.get(&from).unwrap().to_vec();
            // replace temps
            for loc in use_locs.iter() {
qinsoon's avatar
qinsoon committed
572
                string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
573
574
            }

qinsoon's avatar
qinsoon committed
575
576
            // remove old key, insert new one
            asm.uses.remove(&from);
577
            asm.uses.insert(to, use_locs);
578
579
        }
    }
580
    
581
582
    fn set_inst_nop(&mut self, index: usize) {
        self.code.remove(index);
qinsoon's avatar
qinsoon committed
583
        self.code.insert(index, ASMInst::nop());
584
    }
qinsoon's avatar
qinsoon committed
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634

    fn remove_unnecessary_callee_saved(&mut self, used_callee_saved: Vec<MuID>) -> Vec<MuID> {
        // we always save rbp
        let rbp = x86_64::RBP.extract_ssa_id().unwrap();
        // every push/pop will use/define rsp
        let rsp = x86_64::RSP.extract_ssa_id().unwrap();

        let find_op_other_than_rsp = |inst: &ASMInst| -> Option<MuID> {
            for id in inst.defines.keys() {
                if *id != rsp && *id != rbp {
                    return Some(*id);
                }
            }
            for id in inst.uses.keys() {
                if *id != rsp && *id != rbp {
                    return Some(*id);
                }
            }

            None
        };

        let mut inst_to_remove = vec![];
        let mut regs_to_remove = vec![];

        for i in 0..self.number_of_insts() {
            let ref inst = self.code[i];

            if inst.code.contains("push") || inst.code.contains("pop") {
                match find_op_other_than_rsp(inst) {
                    Some(op) => {
                        // if this push/pop instruction is about a callee saved register
                        // and the register is not used, we set the instruction as nop
                        if x86_64::is_callee_saved(op) && !used_callee_saved.contains(&op) {
                            trace!("removing instruction {:?} for save/restore unnecessary callee saved regs", inst);
                            regs_to_remove.push(op);
                            inst_to_remove.push(i);
                        }
                    }
                    None => {}
                }
            }
        }

        for i in inst_to_remove {
            self.set_inst_nop(i);
        }

        regs_to_remove
    }
qinsoon's avatar
qinsoon committed
635
636
637
638
639
640
641
642
643
644
645
646

    fn patch_frame_size(&mut self, size: usize) {
        let size = size.to_string();

        debug_assert!(size.len() <= FRAME_SIZE_PLACEHOLDER_LEN);

        for loc in self.frame_size_patchpoints.iter() {
            let ref mut inst = self.code[loc.line];

            string_utils::replace(&mut inst.code, loc.index, &size, size.len());
        }
    }
647
    
648
649
650
651
652
653
654
655
656
657
658
    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
    }
    
659
660
    fn trace_mc(&self) {
        trace!("");
661

662
663
        trace!("code for {}: \n", self.name);
        
664
665
        let n_insts = self.code.len();
        for i in 0..n_insts {
666
            self.trace_inst(i);
667
668
        }
        
669
670
671
672
673
674
        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),
qinsoon's avatar
qinsoon committed
675
            self.code[i].preds, self.code[i].succs);
676
    }
677
    
678
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
679
680
681
682
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
            None => None
        }
683
684
    }
    
685
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
686
687
688
689
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
            None => None
        }
690
691
    }
    
692
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
693
694
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
695
696
697
    }
    
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
698
699
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
700
701
    }
    
qinsoon's avatar
qinsoon committed
702
703
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
704
705
    }
    
706
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
qinsoon's avatar
qinsoon committed
707
708
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
709
710
711
            None => None
        }
    }
712
713
}

qinsoon's avatar
qinsoon committed
714
715
716
717
#[derive(Clone, Debug)]
enum ASMBranchTarget {
    None,
    Conditional(MuName),
qinsoon's avatar
[wip]    
qinsoon committed
718
719
    Unconditional(MuName),
    Return
qinsoon's avatar
qinsoon committed
720
721
}

qinsoon's avatar
qinsoon committed
722
#[derive(Clone, Debug)]
qinsoon's avatar
qinsoon committed
723
struct ASMInst {
724
    code: String,
qinsoon's avatar
qinsoon committed
725

726
727
    defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
    uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
728
729

    is_mem_op_used: bool,
730
731
    is_symbol: bool,

qinsoon's avatar
qinsoon committed
732
733
734
    preds: Vec<usize>,
    succs: Vec<usize>,
    branch: ASMBranchTarget
qinsoon's avatar
qinsoon committed
735
736
}

qinsoon's avatar
qinsoon committed
737
738
739
impl ASMInst {
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
740
            code: line,
741
742
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
743
            is_mem_op_used: false,
744
            is_symbol: true,
qinsoon's avatar
qinsoon committed
745
746
747
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None
748
749
750
        }
    }
    
qinsoon's avatar
qinsoon committed
751
752
    fn inst(
        inst: String,
753
754
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
755
756
757
758
759
        is_mem_op_used: bool,
        target: ASMBranchTarget
    ) -> ASMInst
    {
        ASMInst {
760
761
            code: inst,
            defines: defines,
qinsoon's avatar
qinsoon committed
762
            uses: uses,
763
            is_symbol: false,
qinsoon's avatar
qinsoon committed
764
765
766
767
            is_mem_op_used: is_mem_op_used,
            preds: vec![],
            succs: vec![],
            branch: target
768
769
        }
    }
770
    
qinsoon's avatar
qinsoon committed
771
772
    fn nop() -> ASMInst {
        ASMInst {
773
            code: "".to_string(),
774
775
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
776
            is_symbol: false,
qinsoon's avatar
qinsoon committed
777
778
779
780
            is_mem_op_used: false,
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None
781
782
        }
    }
qinsoon's avatar
qinsoon committed
783
784
}

785
#[derive(Clone, Debug, PartialEq, Eq)]
qinsoon's avatar
qinsoon committed
786
787
788
struct ASMLocation {
    line: usize,
    index: usize,
qinsoon's avatar
qinsoon committed
789
790
    len: usize,
    oplen: usize,
qinsoon's avatar
qinsoon committed
791
792
793
}

impl ASMLocation {
qinsoon's avatar
qinsoon committed
794
    fn new(line: usize, index: usize, len: usize, oplen: usize) -> ASMLocation {
qinsoon's avatar
qinsoon committed
795
        ASMLocation{
qinsoon's avatar
qinsoon committed
796
            line: line,
qinsoon's avatar
qinsoon committed
797
            index: index,
qinsoon's avatar
qinsoon committed
798
799
            len: len,
            oplen: oplen
qinsoon's avatar
qinsoon committed
800
801
802
803
        }
    }
}

qinsoon's avatar
qinsoon committed
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
#[derive(Clone, Debug)]
/// [start_inst, end_inst)
struct ASMBlock {
    start_inst: usize,
    end_inst: usize,

    livein: Vec<MuID>,
    liveout: Vec<MuID>
}

impl ASMBlock {
    fn new() -> ASMBlock {
        ASMBlock {
            start_inst: usize::MAX,
            end_inst: usize::MAX,
            livein: vec![],
            liveout: vec![]
        }
    }
}

825
pub struct ASMCodeGen {
826
    cur: Option<Box<ASMCode>>
827
828
}

829
const REG_PLACEHOLDER_LEN : usize = 5;
qinsoon's avatar
qinsoon committed
830
831
832
833
834
835
lazy_static! {
    pub static ref REG_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN];
        
        format!("%{}", str::from_utf8(&blank_spaces).unwrap())
    };
836
837
}

qinsoon's avatar
qinsoon committed
838
839
840
841
842
843
844
845
const FRAME_SIZE_PLACEHOLDER_LEN : usize = 10; // a frame is smaller than 1 << 10
lazy_static! {
    pub static ref FRAME_SIZE_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; FRAME_SIZE_PLACEHOLDER_LEN];
        format!("{}", str::from_utf8(&blank_spaces).unwrap())
    };
}

846
847
impl ASMCodeGen {
    pub fn new() -> ASMCodeGen {
qinsoon's avatar
qinsoon committed
848
        ASMCodeGen {
849
            cur: None
qinsoon's avatar
qinsoon committed
850
851
852
853
854
855
856
857
858
859
860
        }
    }
    
    fn cur(&self) -> &ASMCode {
        self.cur.as_ref().unwrap()
    }
    
    fn cur_mut(&mut self) -> &mut ASMCode {
        self.cur.as_mut().unwrap()
    }
    
861
862
863
864
    fn line(&self) -> usize {
        self.cur().code.len()
    }
    
865
866
    fn add_asm_label(&mut self, code: String) {
        let l = self.line();
qinsoon's avatar
qinsoon committed
867
        self.cur_mut().code.push(ASMInst::symbolic(code));
868
869
    }
    
870
    fn add_asm_block_label(&mut self, code: String, block_name: MuName) {
871
        let l = self.line();
qinsoon's avatar
qinsoon committed
872
        self.cur_mut().code.push(ASMInst::symbolic(code));
873
874
    }
    
875
    fn add_asm_symbolic(&mut self, code: String){
qinsoon's avatar
qinsoon committed
876
        self.cur_mut().code.push(ASMInst::symbolic(code));
877
878
    }
    
879
880
    fn prepare_machine_regs(&self, regs: Iter<P<Value>>) -> Vec<MuID> {
        regs.map(|x| self.prepare_machine_reg(x)).collect()
qinsoon's avatar
qinsoon committed
881
    }
882
    
883
    fn add_asm_call(&mut self, code: String) {
qinsoon's avatar
qinsoon committed
884
        // a call instruction will use all the argument registers
qinsoon's avatar
qinsoon committed
885
        // do not need
886
        let uses : LinkedHashMap<MuID, Vec<ASMLocation>> = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
887
888
889
890
891
892
//        for reg in x86_64::ARGUMENT_GPRs.iter() {
//            uses.insert(reg.id(), vec![]);
//        }
//        for reg in x86_64::ARGUMENT_FPRs.iter() {
//            uses.insert(reg.id(), vec![]);
//        }
qinsoon's avatar
qinsoon committed
893
894

        // defines: return registers
895
        let mut defines : LinkedHashMap<MuID, Vec<ASMLocation>> = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
        for reg in x86_64::RETURN_GPRs.iter() {
            defines.insert(reg.id(), vec![]);
        }
        for reg in x86_64::RETURN_FPRs.iter() {
            defines.insert(reg.id(), vec![]);
        }
        for reg in x86_64::CALLER_SAVED_GPRs.iter() {
            if !defines.contains_key(&reg.id()) {
                defines.insert(reg.id(), vec![]);
            }
        }
        for reg in x86_64::CALLER_SAVED_FPRs.iter() {
            if !defines.contains_key(&reg.id()) {
                defines.insert(reg.id(), vec![]);
            }
        }
912
          
qinsoon's avatar
qinsoon committed
913
        self.add_asm_inst(code, defines, uses, false);
914
915
916
    }
    
    fn add_asm_ret(&mut self, code: String) {
917
918
919
920
        // return instruction does not use anything (not RETURN REGS)
        // otherwise it will keep RETURN REGS alive
        // and if there is no actual move into RETURN REGS, it will keep RETURN REGS for alive for very long
        // and prevents anything using those regsiters
921
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Return);
922
923
    }
    
924
    fn add_asm_branch(&mut self, code: String, target: MuName) {
925
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Unconditional(target));
926
927
    }
    
928
    fn add_asm_branch2(&mut self, code: String, target: MuName) {
929
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Conditional(target));
930
931
932
933
934
    }
    
    fn add_asm_inst(
        &mut self, 
        code: String, 
935
936
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
937
938
939
940
941
942
943
944
        is_using_mem_op: bool)
    {
        self.add_asm_inst_internal(code, defines, uses, is_using_mem_op, ASMBranchTarget::None)
    }

    fn add_asm_inst_internal(
        &mut self,
        code: String,
945
946
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
947
948
        is_using_mem_op: bool,
        target: ASMBranchTarget)
949
    {
950
951
        let line = self.line();
        trace!("asm: {}", code);
qinsoon's avatar
qinsoon committed
952
953
        trace!("     defines: {:?}", defines);
        trace!("     uses: {:?}", uses);
954
        let mc = self.cur_mut();
qinsoon's avatar
qinsoon committed
955

956
        // put the instruction
qinsoon's avatar
qinsoon committed
957
        mc.code.push(ASMInst::inst(code, defines, uses, is_using_mem_op, target));
qinsoon's avatar
qinsoon committed
958
959
    }
    
960
    fn prepare_reg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
961
962
963
964
965
966
967
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting register op")
            }
        }
        
968
969
        let str = self.asm_reg_op(op);
        let len = str.len();
qinsoon's avatar
qinsoon committed
970
971
972
973
974
975
976
977
978
979
980
981
982
983
        (str, op.extract_ssa_id().unwrap(), ASMLocation::new(self.line(), loc, len, check_op_len(op)))
    }

    fn prepare_fpreg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting register op")
            }
        }

        let str = self.asm_reg_op(op);
        let len = str.len();
        (str, op.extract_ssa_id().unwrap(), ASMLocation::new(self.line(), loc, len, 64))
984
985
986
    }
    
    fn prepare_machine_reg(&self, op: &P<Value>) -> MuID {
987
988
989
990
991
992
993
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting machine register op")
            }
        }        
        
994
        op.extract_ssa_id().unwrap()
995
    }
996
    
997
    #[allow(unused_assignments)]
998
    fn prepare_mem(&self, op: &P<Value>, loc: usize) -> (String, LinkedHashMap<MuID, Vec<ASMLocation>>) {
999
1000
1001
        if cfg!(debug_assertions) {
            match op.v {
                Value_::Memory(_) => {},
qinsoon's avatar
qinsoon committed
1002
                _ => panic!("expecting memory op")
1003
1004
            }
        }        
qinsoon's avatar
qinsoon committed
1005

1006
1007
1008
1009
        let mut ids : Vec<MuID> = vec![];
        let mut locs : Vec<ASMLocation> = vec![];
        let mut result_str : String = "".to_string();
        
1010
        let mut loc_cursor : usize = loc;
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
        
        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
qinsoon's avatar
qinsoon committed
1022
                            let (str, id, loc) = self.prepare_reg(offset, loc_cursor);
1023
1024
1025
1026
1027
1028
1029
1030
                            
                            result_str.push_str(&str);
                            ids.push(id);
                            locs.push(loc);
                            
                            loc_cursor += str.len();
                        },
                        Value_::Constant(Constant::Int(val)) => {
qinsoon's avatar
qinsoon committed
1031
                            let str = (val as i32).to_string();
1032
1033
1034
1035
1036
1037
1038
1039
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
1050
1051
1052
1053
1054
1055
1056
1057
1058
1059
1060
1061
1062
1063
1064
1065
1066
1067
1068
                            
                            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)) => {
qinsoon's avatar
qinsoon committed
1069
                            let str = (val as i32).to_string();
1070
1071
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
1086
1087
1088
1089
1090
1091
1092
                            
                            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;
            },
1093
1094
            Value_::Memory(MemoryLocation::Symbolic{ref base, ref label, is_global}) => {
                if base.is_some() && base.as_ref().unwrap().id() == x86_64::RIP.id() && is_global {
qinsoon's avatar
qinsoon committed
1095
                    // pc relative address
1096
1097
                    let pic_symbol = pic_symbol(label.clone());
//                    let pic_symbol = symbol(label.clone()); // not sure if we need this
qinsoon's avatar
qinsoon committed
1098
1099
1100
1101
1102
1103
1104
                    result_str.push_str(&pic_symbol);
                    loc_cursor += label.len();
                } else {
                    let symbol = symbol(label.clone());
                    result_str.push_str(&symbol);
                    loc_cursor += label.len();
                }
1105
1106
1107
1108
1109
1110
1111
1112
1113
1114
                
                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();
qinsoon's avatar
qinsoon committed
1115

1116
                    result_str.push(')');
qinsoon's avatar
qinsoon committed
1117
                    loc_cursor += 1;
1118
1119
1120
1121
                }
            },
            _ => panic!("expect mem location as value")
        }
qinsoon's avatar
qinsoon committed
1122

1123
1124
        let uses : LinkedHashMap<MuID, Vec<ASMLocation>> = {
            let mut map : LinkedHashMap<MuID, Vec<ASMLocation>> = linked_hashmap!{};
qinsoon's avatar
qinsoon committed
1125
1126
1127
1128
1129
1130
1131
1132
1133
1134
1135
1136
1137
1138
1139
            for i in 0..ids.len() {
                let id = ids[i];
                let loc = locs[i].clone();

                if map.contains_key(&id) {
                    map.get_mut(&id).unwrap().push(loc);
                } else {
                    map.insert(id, vec![loc]);
                }
            }
            map
        };


        (result_str, uses)
1140
    }
1141
1142
1143
1144
1145
1146
1147
1148
1149
1150

    fn prepare_imm(&self, op: i32, len: usize) -> i32 {
        match len {
            64 => op,
            32 => op,
            16 => op as i16 as i32,
            8  => op as i8  as i32,
            _ => unimplemented!()
        }
    }
1151
    
qinsoon's avatar
qinsoon committed
1152
1153
    fn asm_reg_op(&self, op: &P<Value>) -> String {
        let id = op.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
1154
        if id < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
1155
            // machine reg
1156
            format!("%{}", op.name().unwrap())
qinsoon's avatar
qinsoon committed
1157
1158
1159
1160
1161
1162
        } else {
            // virtual register, use place holder
            REG_PLACEHOLDER.clone()
        }
    }
    
qinsoon's avatar
qinsoon committed
1163
1164
    fn mangle_block_label(&self, label: MuName) -> String {
        format!("{}_{}", self.cur().name, label)
1165
    }
1166
1167
1168
1169

    fn finish_code_sequence_asm(&mut self) -> Box<ASMCode> {
        self.cur.take().unwrap()
    }
1170

qinsoon's avatar
qinsoon committed
1171
1172
    fn internal_binop_no_def_r_r(&mut self, inst: &str, op1: &P<Value>, op2: &P<Value>) {
        let len = check_op_len(op1);
1173

qinsoon's avatar
qinsoon committed
1174
1175
1176
        // with postfix
        let inst = inst.to_string() + &op_postfix(len);
        trace!("emit: {} {} {}", inst, op1, op2);
1177

qinsoon's avatar
qinsoon committed
1178
1179
        let (reg1, id1, loc1) = self.prepare_reg(op1, inst.len() + 1);
        let (reg2, id2, loc2) = self.prepare_reg(op2, inst.len() + 1 + reg1.len() + 1);
1180

qinsoon's avatar
qinsoon committed
1181
        let asm = format!("{} {},{}", inst, reg1, reg2);
1182

qinsoon's avatar
qinsoon committed
1183
1184
        self.add_asm_inst(
            asm,
1185
            linked_hashmap!{},
qinsoon's avatar
qinsoon committed
1186
1187
            {
                if id1 == id2 {
1188
                    linked_hashmap!{
qinsoon's avatar
qinsoon committed
1189
                        id1 => vec![loc1, loc2]
1190
                    }
qinsoon's avatar
qinsoon committed
1191
                } else {
1192
                    linked_hashmap!{
qinsoon's avatar
qinsoon committed
1193
1194
1195
1196
1197
1198
1199
                        id1 => vec![loc1],
                        id2 => vec![loc2]
                    }
                }
            },
            false
        )
1200
1201
    }

qinsoon's avatar
qinsoon committed
1202
1203
    fn internal_binop_no_def_imm_r(&mut self, inst: &str, op1: i32, op2: &P<Value>) {
        let len = check_op_len(op2);
1204

qinsoon's avatar
qinsoon committed
1205
1206
        let inst = inst.to_string() + &op_postfix(len);
        trace!("emit: {} {} {}", inst, op1, op2);
1207

1208
1209
        let imm = self.prepare_imm(op1, len);
        let (reg2, id2, loc2) = self.prepare_reg(op2, inst.len() + 1 + 1 + imm.to_string().len() + 1);
1210

1211
        let asm = format!("{} ${},{}", inst, imm, reg2);
1212

qinsoon's avatar
qinsoon committed