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 93.5 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
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284

    fn control_flow_analysis(&mut self) {
        const TRACE_CFA : bool = false;

        // 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() {
                ret.push(block.start_inst);
            }
            ret
        };

        for i in 0..n_insts {
qinsoon's avatar
[wip]    
qinsoon committed
285
286
287
            if TRACE_CFA {
                trace!("---inst {}---", i);
            }
qinsoon's avatar
qinsoon committed
288
289
290
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
320
321
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 predecessor - if cur is not block start, its predecessor is previous insts
            let is_block_start = block_start.contains(&i);
            if !is_block_start {
                if i > 0 {
                    if TRACE_CFA {
                        trace!("inst {}: not a block start", i);
                        trace!("inst {}: set PREDS as previous inst {}", i, i - 1);
                    }
                    asm[i].preds.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 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;

                    // cur insts' succ is target and next inst
                    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);
                    }

                    if i < n_insts - 1 {
                        if TRACE_CFA {
                            trace!("inst {}: set SUCCS as next inst", i + 1);
                        }
                        asm[i].succs.push(i + 1);
                    }

                    // target's pred is cur
                    asm[target_n].preds.push(i);
                    if TRACE_CFA {
                        trace!("inst {}: set PREDS as {}", target_n, i);
                    }
                },
qinsoon's avatar
[wip]    
qinsoon committed
349
350
351
352
353
354
                ASMBranchTarget::Return => {
                    if TRACE_CFA {
                        trace!("inst {}: is a return", i);
                        trace!("inst {}: has no successor", i);
                    }
                }
qinsoon's avatar
qinsoon committed
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
                ASMBranchTarget::None => {
                    // not branch nor cond branch, succ is next inst
                    if TRACE_CFA {
                        trace!("inst {}: not a branch inst", i);
                    }
                    if i < n_insts - 1 {
                        if TRACE_CFA {
                            trace!("inst {}: set SUCCS as next inst {}", i, i + 1);
                        }
                        asm[i].succs.push(i + 1);
                    }
                }
            }
        }

        // a sanity check for fallthrough blocks
        for i in 0..n_insts {
            if i != 0 && asm[i].preds.len() == 0 {
                asm[i].preds.push(i - 1);
            }
        }
    }
qinsoon's avatar
qinsoon committed
377
378
379
380

    fn add_frame_size_patchpoint(&mut self, patchpoint: ASMLocation) {
        self.frame_size_patchpoints.push(patchpoint);
    }
381
382
383
384
}

use std::any::Any;

385
impl MachineCode for ASMCode {
386
387
388
    fn as_any(&self) -> &Any {
        self
    }
389
390
391
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
qinsoon's avatar
qinsoon committed
392
    
393
394
395
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
qinsoon's avatar
qinsoon committed
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
            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
                }
            },
412
413
414
415
            None => false
        }
    }
    
qinsoon's avatar
qinsoon committed
416
    fn is_using_mem_op(&self, index: usize) -> bool {
qinsoon's avatar
qinsoon committed
417
        self.code[index].is_mem_op_used
qinsoon's avatar
qinsoon committed
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

    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
443
    
qinsoon's avatar
qinsoon committed
444
    fn get_succs(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
445
        &self.code[index].succs
qinsoon's avatar
qinsoon committed
446
447
448
    }
    
    fn get_preds(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
449
        &self.code[index].preds
qinsoon's avatar
qinsoon committed
450
451
    }
    
qinsoon's avatar
qinsoon committed
452
453
    fn get_inst_reg_uses(&self, index: usize) -> Vec<MuID> {
        self.code[index].uses.keys().map(|x| *x).collect()
454
455
    }
    
qinsoon's avatar
qinsoon committed
456
457
    fn get_inst_reg_defines(&self, index: usize) -> Vec<MuID> {
        self.code[index].defines.keys().map(|x| *x).collect()
458
    }
459
    
460
    fn replace_reg(&mut self, from: MuID, to: MuID) {
qinsoon's avatar
qinsoon committed
461
462
        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
463
464
465
466
467
468
469

            // 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());
470
        }
471

qinsoon's avatar
qinsoon committed
472
473
        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
474
475
476
477
478
479
480

            // 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());
481
482
        }
    }
483

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

qinsoon's avatar
qinsoon committed
487
488
489
490
491
492
        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
493
                string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
494
495
            }

qinsoon's avatar
qinsoon committed
496
497
            // remove old key, insert new one
            asm.defines.remove(&from);
498
            asm.defines.insert(to, define_locs);
499
        }
500
501
502
    }

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

        let asm = &mut self.code[inst];
qinsoon's avatar
qinsoon committed
506
507
508
509
510
511

        // 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
512
                string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
513
514
            }

qinsoon's avatar
qinsoon committed
515
516
            // remove old key, insert new one
            asm.uses.remove(&from);
517
            asm.uses.insert(to, use_locs);
518
519
        }
    }
520
    
521
522
    fn set_inst_nop(&mut self, index: usize) {
        self.code.remove(index);
qinsoon's avatar
qinsoon committed
523
        self.code.insert(index, ASMInst::nop());
524
    }
qinsoon's avatar
qinsoon committed
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 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
575
576
577
578
579
580
581
582
583
584
585
586

    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());
        }
    }
587
    
588
589
590
591
592
593
594
595
596
597
598
    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
    }
    
599
600
    fn trace_mc(&self) {
        trace!("");
601

602
603
        trace!("code for {}: \n", self.name);
        
604
605
        let n_insts = self.code.len();
        for i in 0..n_insts {
606
            self.trace_inst(i);
607
608
        }
        
609
610
611
612
613
614
        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
615
            self.code[i].preds, self.code[i].succs);
616
    }
617
    
618
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
619
620
621
622
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
            None => None
        }
623
624
    }
    
625
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
626
627
628
629
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
            None => None
        }
630
631
    }
    
632
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
633
634
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
635
636
637
    }
    
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
638
639
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
640
641
    }
    
qinsoon's avatar
qinsoon committed
642
643
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
644
645
    }
    
646
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
qinsoon's avatar
qinsoon committed
647
648
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
649
650
651
            None => None
        }
    }
652
653
}

qinsoon's avatar
qinsoon committed
654
655
656
657
#[derive(Clone, Debug)]
enum ASMBranchTarget {
    None,
    Conditional(MuName),
qinsoon's avatar
[wip]    
qinsoon committed
658
659
    Unconditional(MuName),
    Return
qinsoon's avatar
qinsoon committed
660
661
}

qinsoon's avatar
qinsoon committed
662
#[derive(Clone, Debug)]
qinsoon's avatar
qinsoon committed
663
struct ASMInst {
664
    code: String,
qinsoon's avatar
qinsoon committed
665

666
667
    defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
    uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
668
669
670
671
672

    is_mem_op_used: bool,
    preds: Vec<usize>,
    succs: Vec<usize>,
    branch: ASMBranchTarget
qinsoon's avatar
qinsoon committed
673
674
}

qinsoon's avatar
qinsoon committed
675
676
677
impl ASMInst {
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
678
            code: line,
679
680
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
681
682
683
684
            is_mem_op_used: false,
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None
685
686
687
        }
    }
    
qinsoon's avatar
qinsoon committed
688
689
    fn inst(
        inst: String,
690
691
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
692
693
694
695
696
        is_mem_op_used: bool,
        target: ASMBranchTarget
    ) -> ASMInst
    {
        ASMInst {
697
698
            code: inst,
            defines: defines,
qinsoon's avatar
qinsoon committed
699
700
701
702
703
            uses: uses,
            is_mem_op_used: is_mem_op_used,
            preds: vec![],
            succs: vec![],
            branch: target
704
705
        }
    }
706
    
qinsoon's avatar
qinsoon committed
707
708
    fn nop() -> ASMInst {
        ASMInst {
709
            code: "".to_string(),
710
711
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
712
713
714
715
            is_mem_op_used: false,
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None
716
717
        }
    }
qinsoon's avatar
qinsoon committed
718
719
}

720
#[derive(Clone, Debug, PartialEq, Eq)]
qinsoon's avatar
qinsoon committed
721
722
723
struct ASMLocation {
    line: usize,
    index: usize,
qinsoon's avatar
qinsoon committed
724
725
    len: usize,
    oplen: usize,
qinsoon's avatar
qinsoon committed
726
727
728
}

impl ASMLocation {
qinsoon's avatar
qinsoon committed
729
    fn new(line: usize, index: usize, len: usize, oplen: usize) -> ASMLocation {
qinsoon's avatar
qinsoon committed
730
        ASMLocation{
qinsoon's avatar
qinsoon committed
731
            line: line,
qinsoon's avatar
qinsoon committed
732
            index: index,
qinsoon's avatar
qinsoon committed
733
734
            len: len,
            oplen: oplen
qinsoon's avatar
qinsoon committed
735
736
737
738
        }
    }
}

qinsoon's avatar
qinsoon committed
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
#[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![]
        }
    }
}

760
pub struct ASMCodeGen {
761
    cur: Option<Box<ASMCode>>
762
763
}

764
const REG_PLACEHOLDER_LEN : usize = 5;
qinsoon's avatar
qinsoon committed
765
766
767
768
769
770
lazy_static! {
    pub static ref REG_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN];
        
        format!("%{}", str::from_utf8(&blank_spaces).unwrap())
    };
771
772
}

qinsoon's avatar
qinsoon committed
773
774
775
776
777
778
779
780
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())
    };
}

781
782
impl ASMCodeGen {
    pub fn new() -> ASMCodeGen {
qinsoon's avatar
qinsoon committed
783
        ASMCodeGen {
784
            cur: None
qinsoon's avatar
qinsoon committed
785
786
787
788
789
790
791
792
793
794
795
        }
    }
    
    fn cur(&self) -> &ASMCode {
        self.cur.as_ref().unwrap()
    }
    
    fn cur_mut(&mut self) -> &mut ASMCode {
        self.cur.as_mut().unwrap()
    }
    
796
797
798
799
    fn line(&self) -> usize {
        self.cur().code.len()
    }
    
800
801
    fn add_asm_label(&mut self, code: String) {
        let l = self.line();
qinsoon's avatar
qinsoon committed
802
        self.cur_mut().code.push(ASMInst::symbolic(code));
803
804
    }
    
805
    fn add_asm_block_label(&mut self, code: String, block_name: MuName) {
806
        let l = self.line();
qinsoon's avatar
qinsoon committed
807
        self.cur_mut().code.push(ASMInst::symbolic(code));
808
809
    }
    
810
    fn add_asm_symbolic(&mut self, code: String){
qinsoon's avatar
qinsoon committed
811
        self.cur_mut().code.push(ASMInst::symbolic(code));
812
813
    }
    
814
815
    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
816
    }
817
    
818
    fn add_asm_call(&mut self, code: String) {
qinsoon's avatar
qinsoon committed
819
        // a call instruction will use all the argument registers
qinsoon's avatar
qinsoon committed
820
        // do not need
821
        let uses : LinkedHashMap<MuID, Vec<ASMLocation>> = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
822
823
824
825
826
827
//        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
828
829

        // defines: return registers
830
        let mut defines : LinkedHashMap<MuID, Vec<ASMLocation>> = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
        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![]);
            }
        }
847
          
qinsoon's avatar
qinsoon committed
848
        self.add_asm_inst(code, defines, uses, false);
849
850
851
    }
    
    fn add_asm_ret(&mut self, code: String) {
852
853
854
855
        // 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
856
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Return);
857
858
    }
    
859
    fn add_asm_branch(&mut self, code: String, target: MuName) {
860
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Unconditional(target));
861
862
    }
    
863
    fn add_asm_branch2(&mut self, code: String, target: MuName) {
864
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Conditional(target));
865
866
867
868
869
    }
    
    fn add_asm_inst(
        &mut self, 
        code: String, 
870
871
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
872
873
874
875
876
877
878
879
        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,
880
881
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
882
883
        is_using_mem_op: bool,
        target: ASMBranchTarget)
884
    {
885
886
        let line = self.line();
        trace!("asm: {}", code);
qinsoon's avatar
qinsoon committed
887
888
        trace!("     defines: {:?}", defines);
        trace!("     uses: {:?}", uses);
889
        let mc = self.cur_mut();
qinsoon's avatar
qinsoon committed
890

891
        // put the instruction
qinsoon's avatar
qinsoon committed
892
        mc.code.push(ASMInst::inst(code, defines, uses, is_using_mem_op, target));
qinsoon's avatar
qinsoon committed
893
894
    }
    
895
    fn prepare_reg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
896
897
898
899
900
901
902
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting register op")
            }
        }
        
903
904
        let str = self.asm_reg_op(op);
        let len = str.len();
qinsoon's avatar
qinsoon committed
905
906
907
908
909
910
911
912
913
914
915
916
917
918
        (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))
919
920
921
    }
    
    fn prepare_machine_reg(&self, op: &P<Value>) -> MuID {
922
923
924
925
926
927
928
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting machine register op")
            }
        }        
        
929
        op.extract_ssa_id().unwrap()
930
    }
931
    
932
    #[allow(unused_assignments)]
933
    fn prepare_mem(&self, op: &P<Value>, loc: usize) -> (String, LinkedHashMap<MuID, Vec<ASMLocation>>) {
934
935
936
        if cfg!(debug_assertions) {
            match op.v {
                Value_::Memory(_) => {},
qinsoon's avatar
qinsoon committed
937
                _ => panic!("expecting memory op")
938
939
            }
        }        
qinsoon's avatar
qinsoon committed
940

941
942
943
944
        let mut ids : Vec<MuID> = vec![];
        let mut locs : Vec<ASMLocation> = vec![];
        let mut result_str : String = "".to_string();
        
945
        let mut loc_cursor : usize = loc;
946
947
948
949
950
951
952
953
954
955
956
        
        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
957
                            let (str, id, loc) = self.prepare_reg(offset, loc_cursor);
958
959
960
961
962
963
964
965
                            
                            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
966
                            let str = (val as i32).to_string();
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
                            
                            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
1004
                            let str = (val as i32).to_string();
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
1023
1024
1025
1026
1027
                            
                            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;
            },
1028
            Value_::Memory(MemoryLocation::Symbolic{ref base, ref label}) => {
qinsoon's avatar
qinsoon committed
1029
1030
1031
1032
1033
1034
1035
1036
1037
1038
1039
                if base.is_some() && base.as_ref().unwrap().id() == x86_64::RIP.id() {
                    // pc relative address
//                    let pic_symbol = pic_symbol(label.clone());
                    let pic_symbol = symbol(label.clone()); // not sure if we need this
                    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();
                }
1040
1041
1042
1043
1044
1045
1046
1047
1048
1049
                
                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
1050

1051
                    result_str.push(')');
qinsoon's avatar
qinsoon committed
1052
                    loc_cursor += 1;
1053
1054
1055
1056
                }
            },
            _ => panic!("expect mem location as value")
        }
qinsoon's avatar
qinsoon committed
1057

1058
1059
        let uses : LinkedHashMap<MuID, Vec<ASMLocation>> = {
            let mut map : LinkedHashMap<MuID, Vec<ASMLocation>> = linked_hashmap!{};
qinsoon's avatar
qinsoon committed
1060
1061
1062
1063
1064
1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
            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)
1075
    }
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085

    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!()
        }
    }
1086
    
qinsoon's avatar
qinsoon committed
1087
1088
    fn asm_reg_op(&self, op: &P<Value>) -> String {
        let id = op.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
1089
        if id < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
1090
            // machine reg
1091
            format!("%{}", op.name().unwrap())
qinsoon's avatar
qinsoon committed
1092
1093
1094
1095
1096
1097
        } else {
            // virtual register, use place holder
            REG_PLACEHOLDER.clone()
        }
    }
    
qinsoon's avatar
qinsoon committed
1098
1099
    fn mangle_block_label(&self, label: MuName) -> String {
        format!("{}_{}", self.cur().name, label)
1100
    }
1101
1102
1103
1104

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

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

qinsoon's avatar
qinsoon committed
1109
1110
1111
        // with postfix
        let inst = inst.to_string() + &op_postfix(len);
        trace!("emit: {} {} {}", inst, op1, op2);
1112

qinsoon's avatar
qinsoon committed
1113
1114
        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);
1115

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

qinsoon's avatar
qinsoon committed
1118
1119
        self.add_asm_inst(
            asm,
1120
            linked_hashmap!{},
qinsoon's avatar
qinsoon committed
1121
1122
            {
                if id1 == id2 {
1123
                    linked_hashmap!{
qinsoon's avatar
qinsoon committed
1124
                        id1 => vec![loc1, loc2]
1125
                    }
qinsoon's avatar
qinsoon committed
1126
                } else {
1127
                    linked_hashmap!{
qinsoon's avatar
qinsoon committed
1128
1129
1130
1131
1132
1133
1134
                        id1 => vec![loc1],
                        id2 => vec![loc2]
                    }
                }
            },
            false
        )
1135
1136
    }

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

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

1143
1144
        let imm = self.prepare_imm(op1, len);
        let (reg2, id2, loc2) = self.prepare_reg(op2, inst.len() + 1 + 1 + imm.to_string().len() + 1);
1145

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

qinsoon's avatar
qinsoon committed
1148
1149
        self.add_asm_inst(
            asm,
1150
1151
            linked_hashmap!{},
            linked_hashmap!{
qinsoon's avatar
qinsoon committed
1152
1153
1154
1155
                id2 => vec![loc2]
            },
            false
        )
1156
1157
    }

qinsoon's avatar
qinsoon committed
1158
1159
    fn internal_binop_no_def_mem_r(&mut self, inst: &str, op1: &P<Value>, op2: &P<Value>) {
        let len = check_op_len(op2);
1160

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

qinsoon's avatar
qinsoon committed
1164
1165
        let (mem, mut uses)  = self.prepare_mem(op1, inst.len() + 1);
        let (reg, id1, loc1) = self.prepare_reg(op2, inst.len() + 1 + mem.len() + 1);
1166

qinsoon's avatar
qinsoon committed
1167
        let asm = format!("{} {},{}", inst, mem, reg);
1168

qinsoon's avatar
qinsoon committed
1169
1170
1171
1172
1173
1174
        // merge use vec
        if uses.contains_key(&id1) {
            let mut locs = uses.get_mut(&id1).unwrap();
            vec_utils::add_unique(locs, loc1.clone());
        } else {
            uses.insert(id1, vec![loc1]);
1175
        }
qinsoon's avatar
qinsoon committed
1176
1177
1178

        self.add_asm_inst(
            asm,
1179
            linked_hashmap!{},
qinsoon's avatar
qinsoon committed
1180
1181
1182
            uses,
            true
        )
1183
1184
    }

qinsoon's avatar
qinsoon committed
1185
1186
    fn internal_binop_no_def_r_mem(&mut self, inst: &str, op1: &P<Value>, op2: &P<Value>) {
        let len = check_op_len(op1);
1187

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

qinsoon's avatar
qinsoon committed
1191
1192
        let (mem, mut uses) = self.prepare_mem(op2, inst.len() + 1);
        let (reg, id1, loc1) = self.prepare_reg(op1, inst.len() + 1 + mem.len() + 1);
1193

qinsoon's avatar
qinsoon committed
1194
1195
1196
1197
1198
        if uses.contains_key(&id1) {
            let mut locs = uses.get_mut(&id1).unwrap();
            vec_utils::add_unique(locs, loc1.clone());
        } else {
            uses.insert(id1, vec![loc1.clone()]);
1199
1200
        }

qinsoon's avatar
qinsoon committed
1201
        let asm = format!("{} {},{}", inst, mem, reg);
1202

qinsoon's avatar
qinsoon committed
1203
1204
        self.add_asm_inst(
            asm,
1205
            linked_hashmap!{},
qinsoon's avatar
qinsoon committed
1206
1207
1208
            uses,
            true
        )
qinsoon's avatar