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

asm_backend.rs 117 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
22
use ast::ptr::P;
use ast::ir::*;

qinsoon's avatar
qinsoon committed
23
use std::str;
24
use std::usize;
25
use std::slice::Iter;
26
use std::ops;
qinsoon's avatar
qinsoon committed
27
28

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

32
    entry:  MuName,
33
    blocks: LinkedHashMap<MuName, ASMBlock>,
qinsoon's avatar
qinsoon committed
34
35

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

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

41
impl ASMCode {
qinsoon's avatar
qinsoon committed
42
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
    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
72
73
74
75
76
77
78
79
80
    fn is_block_start(&self, inst: usize) -> bool {
        for block in self.blocks.values() {
            if block.start_inst == inst {
                return true;
            }
        }
        false
    }

81
    fn is_last_inst_in_block(&self, inst: usize) -> bool {
qinsoon's avatar
qinsoon committed
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
        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
100
101
102
103
104
105
106
107
108
109
    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
    }

110
111
    fn rewrite_insert(
        &self,
112
113
        insert_before: LinkedHashMap<usize, Vec<Box<ASMCode>>>,
        insert_after: LinkedHashMap<usize, Vec<Box<ASMCode>>>) -> Box<ASMCode>
114
    {
115
        trace!("insert spilling code");
116
117
        let mut ret = ASMCode {
            name: self.name.clone(),
118
            entry: self.entry.clone(),
119
            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
        // inst N in old machine code is N' in new machine code
        // this map stores the relationship
130
        let mut location_map : LinkedHashMap<usize, usize> = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
131

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
                },
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
                ASMBranchTarget::PotentiallyExcepting(ref target) => {
                    // may trigger exception and jump to target - similar as conditional branch
                    let target_n = self.blocks.get(target).unwrap().start_inst;

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

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

                    asm[target_n].preds.push(i);

                    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 PEI fallthrough target {}", i, next_inst);
                        }
                    } else {
                        panic!("PEI does not have a fallthrough target");
                    }
                },
qinsoon's avatar
[wip]    
qinsoon committed
407
408
409
410
411
412
                ASMBranchTarget::Return => {
                    if TRACE_CFA {
                        trace!("inst {}: is a return", i);
                        trace!("inst {}: has no successor", i);
                    }
                }
qinsoon's avatar
qinsoon committed
413
414
415
416
417
                ASMBranchTarget::None => {
                    // not branch nor cond branch, succ is next inst
                    if TRACE_CFA {
                        trace!("inst {}: not a branch inst", i);
                    }
418
                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
qinsoon's avatar
qinsoon committed
419
                        if TRACE_CFA {
420
                            trace!("inst {}: set SUCCS as next inst {}", i, next_inst);
qinsoon's avatar
qinsoon committed
421
                        }
422
                        asm[i].succs.push(next_inst);
qinsoon's avatar
qinsoon committed
423
424
425
426
                    }
                }
            }
        }
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
    }

    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
449

450
451
452
453
454
455
456
457
458
459
460
    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
461
            }
462
463

            None
qinsoon's avatar
qinsoon committed
464
465
        }
    }
qinsoon's avatar
qinsoon committed
466

467
468
469
470
471
    fn find_last_inst(i: usize, asm: &Vec<ASMInst>) -> Option<usize> {
        if i == 0 {
            None
        } else {
            let mut cur = i;
472
            loop {
473
474
475
476
477
478
479
480
481
482
483
484
485
                if !asm[cur].is_symbol {
                    return Some(cur);
                }

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

qinsoon's avatar
qinsoon committed
486
487
488
    fn add_frame_size_patchpoint(&mut self, patchpoint: ASMLocation) {
        self.frame_size_patchpoints.push(patchpoint);
    }
489
490
491
492
}

use std::any::Any;

493
impl MachineCode for ASMCode {
494
495
496
    fn as_any(&self) -> &Any {
        self
    }
497
498
499
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
qinsoon's avatar
qinsoon committed
500
    
501
502
503
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
qinsoon's avatar
qinsoon committed
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
            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
                }
            },
520
521
522
523
            None => false
        }
    }
    
qinsoon's avatar
qinsoon committed
524
    fn is_using_mem_op(&self, index: usize) -> bool {
qinsoon's avatar
qinsoon committed
525
        self.code[index].is_mem_op_used
qinsoon's avatar
qinsoon committed
526
    }
527
528
529
530
531
532
533

    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();

534
                Some(ASMCodeGen::unmangle_block_label(self.name.clone(), String::from(split[1])))
535
536
537
538
539
540
541
542
543
544
545
            }
            _ => 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();

546
                Some(ASMCodeGen::unmangle_block_label(self.name.clone(), String::from(split[0])))
547
548
549
550
            }
            _ => None
        }
    }
qinsoon's avatar
qinsoon committed
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572

    fn is_spill_load(&self, index: usize) -> Option<P<Value>> {
        if let Some(inst) = self.code.get(index) {
            match inst.spill_info {
                Some(SpillMemInfo::Load(ref p)) => Some(p.clone()),
                _ => None
            }
        } else {
            None
        }
    }

    fn is_spill_store(&self, index: usize) -> Option<P<Value>> {
        if let Some(inst) = self.code.get(index) {
            match inst.spill_info {
                Some(SpillMemInfo::Store(ref p)) => Some(p.clone()),
                _ => None
            }
        } else {
            None
        }
    }
qinsoon's avatar
qinsoon committed
573
    
qinsoon's avatar
qinsoon committed
574
    fn get_succs(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
575
        &self.code[index].succs
qinsoon's avatar
qinsoon committed
576
577
578
    }
    
    fn get_preds(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
579
        &self.code[index].preds
qinsoon's avatar
qinsoon committed
580
581
    }
    
qinsoon's avatar
qinsoon committed
582
583
    fn get_inst_reg_uses(&self, index: usize) -> Vec<MuID> {
        self.code[index].uses.keys().map(|x| *x).collect()
584
585
    }
    
qinsoon's avatar
qinsoon committed
586
587
    fn get_inst_reg_defines(&self, index: usize) -> Vec<MuID> {
        self.code[index].defines.keys().map(|x| *x).collect()
588
    }
589
    
590
    fn replace_reg(&mut self, from: MuID, to: MuID) {
qinsoon's avatar
qinsoon committed
591
592
        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
593
594
595
596
597
598
599

            // 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());
600
        }
601

qinsoon's avatar
qinsoon committed
602
603
        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
604
605
606
607
608
609
610

            // 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());
611
612
        }
    }
613

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

qinsoon's avatar
qinsoon committed
617
618
619
620
621
622
        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
623
                string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
624
625
            }

qinsoon's avatar
qinsoon committed
626
627
            // remove old key, insert new one
            asm.defines.remove(&from);
628
            asm.defines.insert(to, define_locs);
629
        }
630
631
632
    }

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

        let asm = &mut self.code[inst];
qinsoon's avatar
qinsoon committed
636
637
638
639
640
641

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

qinsoon's avatar
qinsoon committed
645
646
            // remove old key, insert new one
            asm.uses.remove(&from);
647
            asm.uses.insert(to, use_locs);
648
649
        }
    }
650
    
651
    fn set_inst_nop(&mut self, index: usize) {
652
653
654
        self.code[index].code.clear();
//        self.code.remove(index);
//        self.code.insert(index, ASMInst::nop());
655
    }
qinsoon's avatar
qinsoon committed
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705

    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
706

707
    #[allow(unused_variables)]
708
    fn patch_frame_size(&mut self, size: usize, size_used: usize) {
qinsoon's avatar
qinsoon committed
709
710
711
712
713
714
715
716
717
718
        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());
        }
    }
719
    
720
721
722
723
    fn emit(&self) -> Vec<u8> {
        let mut ret = vec![];
        
        for inst in self.code.iter() {
724
725
726
727
            if !inst.is_symbol {
                ret.append(&mut "\t".to_string().into_bytes());
            }

728
729
730
731
732
733
            ret.append(&mut inst.code.clone().into_bytes());
            ret.append(&mut "\n".to_string().into_bytes());
        }
        
        ret
    }
734
735
736
737
738
739
740
741
742
743
744
745
746
747

    fn emit_inst(&self, index: usize) -> Vec<u8> {
        let mut ret = vec![];

        let ref inst = self.code[index];

        if !inst.is_symbol {
            ret.append(&mut "\t".to_string().into_bytes());
        }

        ret.append(&mut inst.code.clone().into_bytes());

        ret
    }
748
    
749
750
    fn trace_mc(&self) {
        trace!("");
751

752
753
        trace!("code for {}: \n", self.name);
        
754
755
        let n_insts = self.code.len();
        for i in 0..n_insts {
756
            self.trace_inst(i);
757
758
        }
        
759
760
761
762
763
764
        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
765
            self.code[i].preds, self.code[i].succs);
766
    }
767
    
768
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
769
770
771
772
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
            None => None
        }
773
774
    }
    
775
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
776
777
778
779
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
            None => None
        }
780
781
    }
    
782
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
783
784
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
785
786
787
    }
    
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
788
789
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
790
791
    }
    
qinsoon's avatar
qinsoon committed
792
793
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
794
    }
795
796
797
798

    fn get_entry_block(&self) -> MuName {
        self.entry.clone()
    }
799
    
800
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
qinsoon's avatar
qinsoon committed
801
802
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
803
804
805
            None => None
        }
    }
806

807
808
809
810
811
812
813
814
815
816
    fn get_block_for_inst(&self, index: usize) -> Option<MuName> {
        for (name, block) in self.blocks.iter() {
            if index >= block.start_inst && index < block.end_inst {
                return Some(name.clone());
            }
        }

        None
    }

817
818
819
820
821
822
823
    fn get_next_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_next_inst(index, &self.code)
    }

    fn get_last_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_last_inst(index, &self.code)
    }
824
825
}

qinsoon's avatar
qinsoon committed
826
827
828
829
#[derive(Clone, Debug)]
enum ASMBranchTarget {
    None,
    Conditional(MuName),
qinsoon's avatar
[wip]    
qinsoon committed
830
    Unconditional(MuName),
831
    PotentiallyExcepting(MuName),
qinsoon's avatar
[wip]    
qinsoon committed
832
    Return
qinsoon's avatar
qinsoon committed
833
834
}

835
836
837
838
839
840
#[derive(Clone, Debug)]
enum SpillMemInfo {
    Load(P<Value>),
    Store(P<Value>)
}

qinsoon's avatar
qinsoon committed
841
#[derive(Clone, Debug)]
qinsoon's avatar
qinsoon committed
842
struct ASMInst {
843
    code: String,
qinsoon's avatar
qinsoon committed
844

845
846
    defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
    uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
847
848

    is_mem_op_used: bool,
849
850
    is_symbol: bool,

qinsoon's avatar
qinsoon committed
851
852
    preds: Vec<usize>,
    succs: Vec<usize>,
853
854
855
    branch: ASMBranchTarget,

    spill_info: Option<SpillMemInfo>
qinsoon's avatar
qinsoon committed
856
857
}

qinsoon's avatar
qinsoon committed
858
859
860
impl ASMInst {
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
861
            code: line,
862
863
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
864
            is_mem_op_used: false,
865
            is_symbol: true,
qinsoon's avatar
qinsoon committed
866
867
            preds: vec![],
            succs: vec![],
868
869
870
            branch: ASMBranchTarget::None,

            spill_info: None
871
872
873
        }
    }
    
qinsoon's avatar
qinsoon committed
874
875
    fn inst(
        inst: String,
876
877
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
878
        is_mem_op_used: bool,
879
880
        target: ASMBranchTarget,
        spill_info: Option<SpillMemInfo>
qinsoon's avatar
qinsoon committed
881
882
883
    ) -> ASMInst
    {
        ASMInst {
884
885
            code: inst,
            defines: defines,
qinsoon's avatar
qinsoon committed
886
            uses: uses,
887
            is_symbol: false,
qinsoon's avatar
qinsoon committed
888
889
890
            is_mem_op_used: is_mem_op_used,
            preds: vec![],
            succs: vec![],
891
892
893
            branch: target,

            spill_info: spill_info
894
895
        }
    }
896
    
qinsoon's avatar
qinsoon committed
897
898
    fn nop() -> ASMInst {
        ASMInst {
899
            code: "".to_string(),
900
901
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
902
            is_symbol: false,
qinsoon's avatar
qinsoon committed
903
904
905
            is_mem_op_used: false,
            preds: vec![],
            succs: vec![],
906
907
908
            branch: ASMBranchTarget::None,

            spill_info: None
909
910
        }
    }
qinsoon's avatar
qinsoon committed
911
912
}

913
#[derive(Clone, Debug, PartialEq, Eq)]
qinsoon's avatar
qinsoon committed
914
915
916
struct ASMLocation {
    line: usize,
    index: usize,
qinsoon's avatar
qinsoon committed
917
918
    len: usize,
    oplen: usize,
qinsoon's avatar
qinsoon committed
919
920
921
}

impl ASMLocation {
qinsoon's avatar
qinsoon committed
922
    fn new(line: usize, index: usize, len: usize, oplen: usize) -> ASMLocation {
qinsoon's avatar
qinsoon committed
923
        ASMLocation{
qinsoon's avatar
qinsoon committed
924
            line: line,
qinsoon's avatar
qinsoon committed
925
            index: index,
qinsoon's avatar
qinsoon committed
926
927
            len: len,
            oplen: oplen
qinsoon's avatar
qinsoon committed
928
929
930
931
        }
    }
}

qinsoon's avatar
qinsoon committed
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
#[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![]
        }
    }
}

953
pub struct ASMCodeGen {
954
    cur: Option<Box<ASMCode>>
955
956
}

957
const REG_PLACEHOLDER_LEN : usize = 5;
qinsoon's avatar
qinsoon committed
958
959
960
961
962
963
lazy_static! {
    pub static ref REG_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN];
        
        format!("%{}", str::from_utf8(&blank_spaces).unwrap())
    };
964
965
}

qinsoon's avatar
qinsoon committed
966
967
968
969
970
971
972
973
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())
    };
}

974
975
impl ASMCodeGen {
    pub fn new() -> ASMCodeGen {
qinsoon's avatar
qinsoon committed
976
        ASMCodeGen {
977
            cur: None
qinsoon's avatar
qinsoon committed
978
979
980
981
982
983
984
985
986
987
988
        }
    }
    
    fn cur(&self) -> &ASMCode {
        self.cur.as_ref().unwrap()
    }
    
    fn cur_mut(&mut self) -> &mut ASMCode {
        self.cur.as_mut().unwrap()
    }
    
989
990
991
992
    fn line(&self) -> usize {
        self.cur().code.len()
    }
    
993
994
    fn add_asm_label(&mut self, code: String) {
        let l = self.line();
qinsoon's avatar
qinsoon committed
995
        self.cur_mut().code.push(ASMInst::symbolic(code));
996
997
    }
    
998
    fn add_asm_block_label(&mut self, code: String, block_name: MuName) {
999
        let l = self.line();
qinsoon's avatar
qinsoon committed
1000
        self.cur_mut().code.push(ASMInst::symbolic(code));
1001
1002
    }
    
1003
    fn add_asm_symbolic(&mut self, code: String){
qinsoon's avatar
qinsoon committed
1004
        self.cur_mut().code.push(ASMInst::symbolic(code));
1005
1006
    }
    
1007
1008
    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
1009
    }
1010
1011
1012
1013
1014
1015
1016
1017

    fn add_asm_call_with_extra_uses(&mut self,
                              code: String,
                              extra_uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
                              potentially_excepting: Option<MuName>) {
        let uses = extra_uses;

        // defines
1018
        let mut defines : LinkedHashMap<MuID, Vec<ASMLocation>> = LinkedHashMap::new();
1019
        // return registers get defined
qinsoon's avatar
qinsoon committed
1020
1021
1022
1023
1024
1025
        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![]);
        }
1026
        // caller saved register will be destroyed
qinsoon's avatar
qinsoon committed
1027
1028
1029
1030
1031
1032
1033
1034
1035
1036
        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![]);
            }
        }
1037

1038
1039
1040
1041
1042
1043
1044
        self.add_asm_inst_internal(code, defines, uses, false, {
            if potentially_excepting.is_some() {
                ASMBranchTarget::PotentiallyExcepting(potentially_excepting.unwrap())
            } else {
                ASMBranchTarget::None
            }
        }, None)
1045
1046
    }
    
1047
1048
1049
1050
    fn add_asm_call(&mut self, code: String, potentially_excepting: Option<MuName>) {
        self.add_asm_call_with_extra_uses(code, LinkedHashMap::new(), potentially_excepting);
    }
    
1051
    fn add_asm_ret(&mut self, code: String) {
1052
1053
1054
1055
        // 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
1056
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Return, None);
1057
1058
    }
    
1059
    fn add_asm_branch(&mut self, code: String, target: MuName) {
1060
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Unconditional(target), None);
1061
1062
    }
    
1063
    fn add_asm_branch2(&mut self, code: String, target: MuName) {
1064
        self.add_asm_inst_internal(code, linked_hashmap!{}, linked_hashmap!{}, false, ASMBranchTarget::Conditional(target), None);
1065
1066
1067
1068
1069
    }
    
    fn add_asm_inst(
        &mut self, 
        code: String, 
1070
1071
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
1072
1073
1074
1075
1076
1077
1078
1079
1080
1081
1082
1083
1084
1085
        is_using_mem_op: bool
    ) {
        self.add_asm_inst_internal(code, defines, uses, is_using_mem_op, ASMBranchTarget::None, None)
    }

    fn add_asm_inst_with_spill(
        &mut self,
        code: String,
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
        is_using_mem_op: bool,
        spill_info: SpillMemInfo
    ) {
        self.add_asm_inst_internal(code, defines, uses, is_using_mem_op, ASMBranchTarget::None, Some(spill_info))
qinsoon's avatar
qinsoon committed
1086
1087
1088
1089
1090
    }

    fn add_asm_inst_internal(
        &mut self,
        code: String,
1091
1092
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
1093
        is_using_mem_op: bool,
1094
1095
        target: ASMBranchTarget,
        spill_info: Option<SpillMemInfo>)
1096
    {
1097
1098
        let line = self.line();
        trace!("asm: {}", code);
qinsoon's avatar
qinsoon committed
1099
1100
        trace!("     defines: {:?}", defines);
        trace!("     uses: {:?}", uses);
1101
        let mc = self.cur_mut();
qinsoon's avatar
qinsoon committed
1102

1103
        // put the instruction
1104
        mc.code.push(ASMInst::inst(code, defines, uses, is_using_mem_op, target, spill_info));
qinsoon's avatar
qinsoon committed
1105
1106
    }
    
1107
    fn prepare_reg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
1108
1109
1110
1111
1112
1113
1114
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting register op")
            }
        }
        
1115
1116
        let str = self.asm_reg_op(op);
        let len = str.len();
qinsoon's avatar
qinsoon committed
1117
1118
1119
1120
1121
1122
1123
1124
1125
1126
1127
1128
1129
1130
        (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))
1131
1132
1133
    }
    
    fn prepare_machine_reg(&self, op: &P<Value>) -> MuID {
1134
1135
1136
1137
1138
1139
1140
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting machine register op")
            }
        }        
        
1141
        op.extract_ssa_id().unwrap()
1142
    }
1143
    
1144
    #[allow(unused_assignments)]
1145
    fn prepare_mem(&self, op: &P<Value>, loc: usize) -> (String, LinkedHashMap<MuID, Vec<ASMLocation>>) {
1146
1147
1148
        if cfg!(debug_assertions) {
            match op.v {
                Value_::Memory(_) => {},
qinsoon's avatar
qinsoon committed
1149
                _ => panic!("expecting memory op")
1150
1151
            }
        }        
qinsoon's avatar
qinsoon committed
1152

1153
1154
1155
1156
        let mut ids : Vec<MuID> = vec![];
        let mut locs : Vec<ASMLocation> = vec![];
        let mut result_str : String = "".to_string();
        
1157
        let mut loc_cursor : usize = loc;
1158
1159
1160
1161
1162
1163
1164
1165
1166
1167
1168
        
        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
1169
                            let (str, id, loc) = self.prepare_reg(offset, loc_cursor);
1170
1171
1172
1173
1174
1175
1176
1177
                            
                            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
1178
                            let str = (val as i32).to_string();
1179
1180
1181
1182
1183
1184
1185
1186
1187
1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
                            
                            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
1216
                            let str = (val as i32).to_string();
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
1230
1231
1232
1233
1234
1235
1236
1237
1238
1239
                            
                            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;
            },
1240
1241
            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
1242
                    // pc relative address
1243
1244
                    let pic_symbol = pic_symbol(label.clone());
//                    let pic_symbol = symbol(label.clone()); // not sure if we need this
qinsoon's avatar
qinsoon committed
1245
1246
1247
1248
1249
1250
1251
                    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();
                }