WARNING! Access to this system is limited to authorised users only.
Unauthorised users may be subject to prosecution.
Unauthorised access to this system is a criminal offence under Australian law (Federal Crimes Act 1914 Part VIA)
It is a criminal offence to:
(1) Obtain access to data without authority. -Penalty 2 years imprisonment.
(2) Damage, delete, alter or insert data without authority. -Penalty 10 years imprisonment.
User activity is monitored and recorded. Anyone using this system expressly consents to such monitoring and recording.

To protect your data, the CISO officer has suggested users to enable 2FA as soon as possible.
Currently 2.7% of users enabled 2FA.

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

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

qinsoon's avatar
qinsoon committed
14
use utils::vec_utils;
15
use utils::string_utils;
16
17
18
use ast::ptr::P;
use ast::ir::*;

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

struct ASMCode {
qinsoon's avatar
qinsoon committed
26
    name: MuName, 
qinsoon's avatar
qinsoon committed
27
    code: Vec<ASMInst>,
qinsoon's avatar
qinsoon committed
28
29

    blocks: HashMap<MuName, ASMBlock>
qinsoon's avatar
qinsoon committed
30
31
}

qinsoon's avatar
qinsoon committed
32
33
34
unsafe impl Send for ASMCode {} 
unsafe impl Sync for ASMCode {}

35
impl ASMCode {
qinsoon's avatar
qinsoon committed
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
    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
66
67
68
69
70
71
72
73
74
    fn is_block_start(&self, inst: usize) -> bool {
        for block in self.blocks.values() {
            if block.start_inst == inst {
                return true;
            }
        }
        false
    }

qinsoon's avatar
qinsoon committed
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
    fn is_block_end(&self, inst: usize) -> bool {
        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
94
95
96
97
98
99
100
101
102
103
    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
    }

104
105
106
107
108
109
110
111
    fn rewrite_insert(
        &self,
        insert_before: HashMap<usize, Vec<Box<ASMCode>>>,
        insert_after: HashMap<usize, Vec<Box<ASMCode>>>) -> Box<ASMCode>
    {
        let mut ret = ASMCode {
            name: self.name.clone(),
            code: vec![],
qinsoon's avatar
qinsoon committed
112
            blocks: hashmap!{},
113
114
115
116
        };

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

        for i in 0..self.number_of_insts() {
qinsoon's avatar
qinsoon committed
120
121
122
123
            if self.is_block_start(i) {
                cur_block_start = i + inst_offset;
            }

124
125
126
127
128
129
130
131
132
            // 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();
                }
            }

            // copy this instruction
qinsoon's avatar
qinsoon committed
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
            let mut inst = self.code[i].clone();

            // 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
150
151
152
            // 2. we need to delete existing preds/succs - CFA is required later
            inst.preds.clear();
            inst.succs.clear();
qinsoon's avatar
qinsoon committed
153
154
            // 3. add the inst
            ret.code.push(inst);
155
156
157
158


            // insert code after this instruction
            if insert_after.contains_key(&i) {
qinsoon's avatar
qinsoon committed
159
160
161
162
163
164
165
166
                for insert in insert_after.get(&i).unwrap() {
                    ret.append_code_sequence_all(insert);
                    inst_offset += insert.number_of_insts();
                }
            }

            if self.is_block_end(i) {
                let cur_block_end = i + inst_offset;
167

qinsoon's avatar
qinsoon committed
168
169
170
171
172
173
174
175
176
177
                // copy the block
                let (name, block) = self.get_block_by_inst(i);

                let mut new_block = block.clone();
                new_block.start_inst = cur_block_start;
                cur_block_start = usize::MAX;
                new_block.end_inst = cur_block_end;

                // add to the new code
                ret.blocks.insert(name.clone(), new_block);
178
179
180
            }
        }

qinsoon's avatar
qinsoon committed
181
182
183
        ret.control_flow_analysis();

        Box::new(ret)
184
185
186
187
188
189
190
191
    }

    fn append_code_sequence(
        &mut self,
        another: &Box<ASMCode>,
        start_inst: usize,
        n_insts: usize)
    {
qinsoon's avatar
qinsoon committed
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
        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);
        }
218
219
220
221
222
223
    }

    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
224
225
226
227
228
229
230
231
232
233
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
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
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

    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 {
            // 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);
                    }
                },
                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);
            }
        }
    }
326
327
328
329
}

use std::any::Any;

330
impl MachineCode for ASMCode {
331
332
333
    fn as_any(&self) -> &Any {
        self
    }
334
335
336
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
qinsoon's avatar
qinsoon committed
337
    
338
339
340
341
342
343
344
345
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
            Some(inst) => inst.code.starts_with("mov"),
            None => false
        }
    }
    
qinsoon's avatar
qinsoon committed
346
    fn is_using_mem_op(&self, index: usize) -> bool {
qinsoon's avatar
qinsoon committed
347
        self.code[index].is_mem_op_used
qinsoon's avatar
qinsoon committed
348
349
    }
    
qinsoon's avatar
qinsoon committed
350
    fn get_succs(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
351
        &self.code[index].succs
qinsoon's avatar
qinsoon committed
352
353
354
    }
    
    fn get_preds(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
355
        &self.code[index].preds
qinsoon's avatar
qinsoon committed
356
357
    }
    
qinsoon's avatar
qinsoon committed
358
359
    fn get_inst_reg_uses(&self, index: usize) -> Vec<MuID> {
        self.code[index].uses.keys().map(|x| *x).collect()
360
361
    }
    
qinsoon's avatar
qinsoon committed
362
363
    fn get_inst_reg_defines(&self, index: usize) -> Vec<MuID> {
        self.code[index].defines.keys().map(|x| *x).collect()
364
    }
365
    
366
    fn replace_reg(&mut self, from: MuID, to: MuID) {
367
368
369
370
        let to_reg_tag : MuName = match backend::all_regs().get(&to) {
            Some(reg) => reg.name().unwrap(),
            None => panic!("expecting a machine register, but we are required to replace to {}", to)
        };
371
        let to_reg_string = "%".to_string() + &to_reg_tag;
qinsoon's avatar
qinsoon committed
372
373
374
375
376
377
378

        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
            for i in 0..loc.len {
                // FIXME: why loop here?
                string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
            }
379
        }
380

qinsoon's avatar
qinsoon committed
381
382
383
384
385
        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
            for i in 0..loc.len {
                string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len());
            }
386
387
        }
    }
388

389
    fn replace_define_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
390
391
392
393
394
395
396
397
        let to_reg_string : MuName = match backend::all_regs().get(&to) {
            Some(ref machine_reg) => {
                let name = machine_reg.name().unwrap();
                "%".to_string() + &name
            },
            None => REG_PLACEHOLDER.clone()
        };

qinsoon's avatar
qinsoon committed
398
399
400
401
402
403
404
405
406
        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() {
                for i in 0..loc.len {
                    string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
                }
407
408
            }

qinsoon's avatar
qinsoon committed
409
410
            // remove old key, insert new one
            asm.defines.remove(&from);
411
            asm.defines.insert(to, define_locs);
412
        }
413
414
415
416
417
418
419
420
421
422
423
424
    }

    fn replace_use_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
        let to_reg_string : MuName = match backend::all_regs().get(&to) {
            Some(ref machine_reg) => {
                let name = machine_reg.name().unwrap();
                "%".to_string() + &name
            },
            None => REG_PLACEHOLDER.clone()
        };

        let asm = &mut self.code[inst];
qinsoon's avatar
qinsoon committed
425
426
427
428
429
430
431
432

        // 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() {
                for i in 0..loc.len {
                    string_utils::replace(&mut asm.code, loc.index, &to_reg_string, to_reg_string.len());
433
434
435
                }
            }

qinsoon's avatar
qinsoon committed
436
437
            // remove old key, insert new one
            asm.uses.remove(&from);
438
            asm.uses.insert(to, use_locs);
439
440
        }
    }
441
    
442
443
    fn set_inst_nop(&mut self, index: usize) {
        self.code.remove(index);
qinsoon's avatar
qinsoon committed
444
        self.code.insert(index, ASMInst::nop());
445
    }
qinsoon's avatar
qinsoon committed
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495

    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
    }
496
    
497
498
499
500
501
502
503
504
505
506
507
    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
    }
    
508
509
    fn trace_mc(&self) {
        trace!("");
510

511
512
        trace!("code for {}: \n", self.name);
        
513
514
        let n_insts = self.code.len();
        for i in 0..n_insts {
515
            self.trace_inst(i);
516
517
        }
        
518
519
520
521
522
523
        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
524
            self.code[i].preds, self.code[i].succs);
525
    }
526
    
527
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
528
529
530
531
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
            None => None
        }
532
533
    }
    
534
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
535
536
537
538
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
            None => None
        }
539
540
    }
    
541
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
542
543
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
544
545
546
    }
    
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
547
548
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
549
550
    }
    
qinsoon's avatar
qinsoon committed
551
552
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
553
554
    }
    
555
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
qinsoon's avatar
qinsoon committed
556
557
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
558
559
560
            None => None
        }
    }
561
562
}

qinsoon's avatar
qinsoon committed
563
564
565
566
567
568
569
#[derive(Clone, Debug)]
enum ASMBranchTarget {
    None,
    Conditional(MuName),
    Unconditional(MuName)
}

qinsoon's avatar
qinsoon committed
570
#[derive(Clone, Debug)]
qinsoon's avatar
qinsoon committed
571
struct ASMInst {
572
    code: String,
qinsoon's avatar
qinsoon committed
573
574
575
576
577
578
579
580

    defines: HashMap<MuID, Vec<ASMLocation>>,
    uses: HashMap<MuID, Vec<ASMLocation>>,

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

qinsoon's avatar
qinsoon committed
583
584
585
impl ASMInst {
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
586
            code: line,
qinsoon's avatar
qinsoon committed
587
588
589
590
591
592
            defines: HashMap::new(),
            uses: HashMap::new(),
            is_mem_op_used: false,
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None
593
594
595
        }
    }
    
qinsoon's avatar
qinsoon committed
596
597
598
599
600
601
602
603
604
    fn inst(
        inst: String,
        defines: HashMap<MuID, Vec<ASMLocation>>,
        uses: HashMap<MuID, Vec<ASMLocation>>,
        is_mem_op_used: bool,
        target: ASMBranchTarget
    ) -> ASMInst
    {
        ASMInst {
605
606
            code: inst,
            defines: defines,
qinsoon's avatar
qinsoon committed
607
608
609
610
611
            uses: uses,
            is_mem_op_used: is_mem_op_used,
            preds: vec![],
            succs: vec![],
            branch: target
612
613
        }
    }
614
    
qinsoon's avatar
qinsoon committed
615
616
    fn nop() -> ASMInst {
        ASMInst {
617
            code: "".to_string(),
qinsoon's avatar
qinsoon committed
618
619
620
621
622
623
            defines: HashMap::new(),
            uses: HashMap::new(),
            is_mem_op_used: false,
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None
624
625
        }
    }
qinsoon's avatar
qinsoon committed
626
627
}

628
#[derive(Clone, Debug, PartialEq, Eq)]
qinsoon's avatar
qinsoon committed
629
630
631
632
633
634
635
struct ASMLocation {
    line: usize,
    index: usize,
    len: usize
}

impl ASMLocation {
qinsoon's avatar
qinsoon committed
636
    fn new(line: usize, index: usize, len: usize) -> ASMLocation {
qinsoon's avatar
qinsoon committed
637
        ASMLocation{
qinsoon's avatar
qinsoon committed
638
            line: line,
qinsoon's avatar
qinsoon committed
639
640
641
642
643
644
            index: index,
            len: len
        }
    }
}

qinsoon's avatar
qinsoon committed
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
#[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![]
        }
    }
}

666
pub struct ASMCodeGen {
667
    cur: Option<Box<ASMCode>>
668
669
}

670
const REG_PLACEHOLDER_LEN : usize = 5;
qinsoon's avatar
qinsoon committed
671
672
673
674
675
676
lazy_static! {
    pub static ref REG_PLACEHOLDER : String = {
        let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN];
        
        format!("%{}", str::from_utf8(&blank_spaces).unwrap())
    };
677
678
679
680
}

impl ASMCodeGen {
    pub fn new() -> ASMCodeGen {
qinsoon's avatar
qinsoon committed
681
        ASMCodeGen {
682
            cur: None
qinsoon's avatar
qinsoon committed
683
684
685
686
687
688
689
690
691
692
693
        }
    }
    
    fn cur(&self) -> &ASMCode {
        self.cur.as_ref().unwrap()
    }
    
    fn cur_mut(&mut self) -> &mut ASMCode {
        self.cur.as_mut().unwrap()
    }
    
694
695
696
697
    fn line(&self) -> usize {
        self.cur().code.len()
    }
    
698
699
    fn add_asm_label(&mut self, code: String) {
        let l = self.line();
qinsoon's avatar
qinsoon committed
700
        self.cur_mut().code.push(ASMInst::symbolic(code));
701
702
    }
    
703
    fn add_asm_block_label(&mut self, code: String, block_name: MuName) {
704
        let l = self.line();
qinsoon's avatar
qinsoon committed
705
        self.cur_mut().code.push(ASMInst::symbolic(code));
706
707
    }
    
708
    fn add_asm_symbolic(&mut self, code: String){
qinsoon's avatar
qinsoon committed
709
        self.cur_mut().code.push(ASMInst::symbolic(code));
710
711
    }
    
712
713
    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
714
    }
715
    
716
    fn add_asm_call(&mut self, code: String) {
qinsoon's avatar
qinsoon committed
717
        // a call instruction will use all the argument registers
qinsoon's avatar
qinsoon committed
718
719
720
721
722
723
724
        let mut uses : HashMap<MuID, Vec<ASMLocation>> = HashMap::new();
        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
725
726

        // defines: return registers
qinsoon's avatar
qinsoon committed
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
        let mut defines : HashMap<MuID, Vec<ASMLocation>> = HashMap::new();
        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![]);
            }
        }
744
          
qinsoon's avatar
qinsoon committed
745
        self.add_asm_inst(code, defines, uses, false);
746
747
748
    }
    
    fn add_asm_ret(&mut self, code: String) {
qinsoon's avatar
qinsoon committed
749
        let uses : HashMap<MuID, Vec<ASMLocation>> = {
qinsoon's avatar
qinsoon committed
750
751
752
753
754
755
756
757
758
            let mut ret = HashMap::new();
            for reg in x86_64::RETURN_GPRs.iter() {
                ret.insert(reg.id(), vec![]);
            }
            for reg in x86_64::RETURN_FPRs.iter() {
                ret.insert(reg.id(), vec![]);
            }
            ret
        };
759
        
qinsoon's avatar
qinsoon committed
760
        self.add_asm_inst(code, hashmap!{}, uses, false);
761
762
    }
    
763
    fn add_asm_branch(&mut self, code: String, target: MuName) {
qinsoon's avatar
qinsoon committed
764
        self.add_asm_inst_internal(code, hashmap!{}, hashmap!{}, false, ASMBranchTarget::Unconditional(target));
765
766
    }
    
767
    fn add_asm_branch2(&mut self, code: String, target: MuName) {
qinsoon's avatar
qinsoon committed
768
        self.add_asm_inst_internal(code, hashmap!{}, hashmap!{}, false, ASMBranchTarget::Conditional(target));
769
770
771
772
773
    }
    
    fn add_asm_inst(
        &mut self, 
        code: String, 
qinsoon's avatar
qinsoon committed
774
775
776
777
778
779
780
781
782
783
784
785
786
787
        defines: HashMap<MuID, Vec<ASMLocation>>,
        uses: HashMap<MuID, Vec<ASMLocation>>,
        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,
        defines: HashMap<MuID, Vec<ASMLocation>>,
        uses: HashMap<MuID, Vec<ASMLocation>>,
        is_using_mem_op: bool,
        target: ASMBranchTarget)
788
    {
789
790
        let line = self.line();
        trace!("asm: {}", code);
qinsoon's avatar
qinsoon committed
791
792
        trace!("     defines: {:?}", defines);
        trace!("     uses: {:?}", uses);
793
        let mc = self.cur_mut();
qinsoon's avatar
qinsoon committed
794

795
        // put the instruction
qinsoon's avatar
qinsoon committed
796
        mc.code.push(ASMInst::inst(code, defines, uses, is_using_mem_op, target));
qinsoon's avatar
qinsoon committed
797
798
    }
    
799
    fn prepare_reg(&self, op: &P<Value>, loc: usize) -> (String, MuID, ASMLocation) {
800
801
802
803
804
805
806
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting register op")
            }
        }
        
807
808
        let str = self.asm_reg_op(op);
        let len = str.len();
qinsoon's avatar
qinsoon committed
809
        (str, op.extract_ssa_id().unwrap(), ASMLocation::new(self.line(), loc, len))
810
811
812
    }
    
    fn prepare_machine_reg(&self, op: &P<Value>) -> MuID {
813
814
815
816
817
818
819
        if cfg!(debug_assertions) {
            match op.v {
                Value_::SSAVar(_) => {},
                _ => panic!("expecting machine register op")
            }
        }        
        
820
        op.extract_ssa_id().unwrap()
821
    }
822
    
823
    #[allow(unused_assignments)]
qinsoon's avatar
qinsoon committed
824
    fn prepare_mem(&self, op: &P<Value>, loc: usize) -> (String, HashMap<MuID, Vec<ASMLocation>>) {
825
826
827
828
829
830
        if cfg!(debug_assertions) {
            match op.v {
                Value_::Memory(_) => {},
                _ => panic!("expecting register op")
            }
        }        
qinsoon's avatar
qinsoon committed
831

832
833
834
835
        let mut ids : Vec<MuID> = vec![];
        let mut locs : Vec<ASMLocation> = vec![];
        let mut result_str : String = "".to_string();
        
836
        let mut loc_cursor : usize = loc;
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
        
        match op.v {
            // offset(base,index,scale)
            Value_::Memory(MemoryLocation::Address{ref base, ref offset, ref index, scale}) => {
                // deal with offset
                if offset.is_some() {
                    let offset = offset.as_ref().unwrap();
                    
                    match offset.v {
                        Value_::SSAVar(id) => {
                            // temp as offset
                            let (str, id, loc) = self.prepare_reg(offset, 0);
                            
                            result_str.push_str(&str);
                            ids.push(id);
                            locs.push(loc);
                            
                            loc_cursor += str.len();
                        },
                        Value_::Constant(Constant::Int(val)) => {
qinsoon's avatar
qinsoon committed
857
                            let str = (val as i32).to_string();
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
                            
                            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
895
                            let str = (val as i32).to_string();
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
                            
                            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;
            },
919
920
            Value_::Memory(MemoryLocation::Symbolic{ref base, ref label}) => {
                result_str.push_str(&symbol(label.clone()));
921
922
923
924
925
926
927
928
929
930
931
                loc_cursor += label.len();
                
                if base.is_some() {
                    result_str.push('(');
                    loc_cursor += 1;
                    
                    let (str, id, loc) = self.prepare_reg(base.as_ref().unwrap(), loc_cursor);
                    result_str.push_str(&str);
                    ids.push(id);
                    locs.push(loc);
                    loc_cursor += str.len();
qinsoon's avatar
qinsoon committed
932

933
                    result_str.push(')');
qinsoon's avatar
qinsoon committed
934
                    loc_cursor += 1;
935
936
937
938
                }
            },
            _ => panic!("expect mem location as value")
        }
qinsoon's avatar
qinsoon committed
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956

        let uses : HashMap<MuID, Vec<ASMLocation>> = {
            let mut map : HashMap<MuID, Vec<ASMLocation>> = hashmap!{};
            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)
957
958
    }
    
qinsoon's avatar
qinsoon committed
959
960
    fn asm_reg_op(&self, op: &P<Value>) -> String {
        let id = op.extract_ssa_id().unwrap();
qinsoon's avatar
qinsoon committed
961
        if id < MACHINE_ID_END {
qinsoon's avatar
qinsoon committed
962
            // machine reg
963
            format!("%{}", op.name().unwrap())
qinsoon's avatar
qinsoon committed
964
965
966
967
968
969
        } else {
            // virtual register, use place holder
            REG_PLACEHOLDER.clone()
        }
    }
    
qinsoon's avatar
qinsoon committed
970
971
    fn mangle_block_label(&self, label: MuName) -> String {
        format!("{}_{}", self.cur().name, label)
972
    }
973
974
975
976
    
    fn control_flow_analysis(&mut self) {
        // control flow analysis
        let n_insts = self.line();
qinsoon's avatar
qinsoon committed
977

978
        let code = self.cur_mut();
qinsoon's avatar
qinsoon committed
979
        let ref blocks = code.blocks;
qinsoon's avatar
qinsoon committed
980
        let ref mut asm = code.code;
qinsoon's avatar
qinsoon committed
981
982
983
984
985
986
987
988

        let block_start = {
            let mut ret = vec![];
            for block in blocks.values() {
                ret.push(block.start_inst);
            }
            ret
        };
989
990
991
        
        for i in 0..n_insts {
            // determine predecessor - if cur is not block start, its predecessor is previous insts
qinsoon's avatar
qinsoon committed
992
993
            let is_block_start = block_start.contains(&i);
            if !is_block_start {
994
                if i > 0 {
995
996
                    trace!("inst {}: not a block start", i);
                    trace!("inst {}: set PREDS as previous inst {}", i, i-1);
qinsoon's avatar
qinsoon committed
997
                    asm[i].preds.push(i - 1);
998
999
1000
1001
1002
1003
1004
                }
            } 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
qinsoon's avatar
qinsoon committed
1005
1006
1007
1008
1009
1010
            let branch = asm[i].branch.clone();
            match branch {
                ASMBranchTarget::Unconditional(ref target) => {
                    // branch to target
                    trace!("inst {}: is a branch to {}", i, target);

qinsoon's avatar
qinsoon committed
1011
                    let target_n = code.blocks.get(target).unwrap().start_inst;
qinsoon's avatar
qinsoon committed
1012
1013
1014
1015
                    trace!("inst {}: branch target index is {}", i, target_n);

                    // cur inst's succ is target
                    trace!("inst {}: set SUCCS as branch target {}", i, target_n);
qinsoon's avatar
qinsoon committed
1016
                    asm[i].succs.push(target_n);
qinsoon's avatar
qinsoon committed
1017
1018
1019

                    // target's pred is cur
                    trace!("inst {}: set PREDS as branch source {}", target_n, i);
qinsoon's avatar
qinsoon committed
1020
                    asm[target_n].preds.push(i);
qinsoon's avatar
qinsoon committed
1021
1022
                },
                ASMBranchTarget::Conditional(ref target) => {
1023
                    // branch to target
1024
                    trace!("inst {}: is a cond branch to {}", i, target);
qinsoon's avatar
qinsoon committed
1025

qinsoon's avatar
qinsoon committed
1026
                    let target_n = code.blocks.get(target).unwrap().start_inst;
1027
                    trace!("inst {}: branch target index is {}", i, target_n);
qinsoon's avatar
qinsoon committed
1028

1029
                    // cur insts' succ is target and next inst
qinsoon's avatar
qinsoon committed
1030
                    asm[i].succs.push(target_n);
1031
                    trace!("inst {}: set SUCCS as branch target {}", i, target_n);
1032
                    if i < n_insts - 1 {
qinsoon's avatar
qinsoon committed
1033
1034
                        trace!("inst {}: set SUCCS as next inst", i + 1);
                        asm[i].succs.push(i + 1);
1035
                    }
qinsoon's avatar
qinsoon committed
1036

1037
                    // target's pred is cur
qinsoon's avatar
qinsoon committed
1038
1039
                    asm[target_n].preds.push(i);
                    trace!("inst {}: set PREDS as {}", target_n, i);
qinsoon's avatar
qinsoon committed
1040
1041
                },
                ASMBranchTarget::None => {
1042
                    // not branch nor cond branch, succ is next inst
1043
                    trace!("inst {}: not a branch inst", i);
1044
                    if i < n_insts - 1 {
1045
                        trace!("inst {}: set SUCCS as next inst {}", i, i + 1);
qinsoon's avatar
qinsoon committed
1046
                        asm[i].succs.push(i + 1);
1047
1048
                    }
                }
qinsoon's avatar
qinsoon committed
1049
            }
1050
1051
1052
1053
        }
        
        // a sanity check for fallthrough blocks
        for i in 0..n_insts {
qinsoon's avatar
qinsoon committed
1054
1055
            if i != 0 && asm[i].preds.len() == 0 {
                asm[i].preds.push(i - 1);
1056
1057
1058
            }
        }        
    }
1059
1060
1061
1062

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

1065
1066
1067
1068
1069
1070
1071
1072
1073
1074
1075
#[inline(always)]
fn op_postfix(op_len: usize) -> &'static str {
    match op_len {
        8  => "b",
        16 => "w",
        32 => "l",
        64 => "q",
        _  => panic!("unexpected op size: {}", op_len)
    }
}

1076
1077
// general instruction emission
macro_rules! binop_no_def_r_r {
1078
1079
    ($func_name: ident, $inst: expr, $op_len: expr) => {
        fn $func_name (&mut self, op1: &P<Value>, op2: &P<Value>) {
1080
1081
            // with postfix
            let inst = $inst.to_string() + &op_postfix($op_len);
1082
            trace!("emit: {} {} {}", inst, op1, op2);
1083

1084
1085
            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);
1086

1087
            let asm = format!("{} {},{}", inst, reg1, reg2);
1088

1089
            self.add_asm_inst(
1090
1091
1092
1093
1094
1095
1096
                asm,
                hashmap!{},
                hashmap!{
                    id1 => vec![loc1],
                    id2 => vec![loc2]
                },
                false
1097
            )
1098
1099
1100
1101
        }
    }
}

1102
macro_rules! binop_no_def_r_imm {
1103
1104
    ($func_name: ident, $inst: expr, $op_len: expr, $imm_ty: ty) => {
        fn $func_name (&mut self, op1: &P<Value>, op2: $imm_ty) {
1105
            let inst = $inst.to_string() + &op_postfix($op_len);
1106
            trace!("emit: {} {} {}", inst, op1, op2);
1107

1108
            let (reg1, id1, loc1) = self.prepare_reg(op1, inst.len() + 1 + 1 + op2.to_string().len() + 1);
1109

1110
            let asm = format!("{} ${},{}", inst, op2, reg1);
1111

1112
            self.add_asm_inst(
1113
1114
1115
1116
1117
1118
1119
                asm,
                hashmap!{},
                hashmap!{
                    id1 => vec![loc1]
                },
                false
            )
1120

1121
1122
1123
1124
        }
    }
}

1125
macro_rules! binop_no_def_r_mem {
1126
1127
    ($func_name: ident, $inst:expr, $op_len: expr) => {
        fn $func_name (&mut self, op1: &P<Value>, op2: &P<Value>) {
1128
            let inst = $inst.to_string() + &op_postfix($op_len);
1129
            trace!("emit: {} {} {}", inst, op1, op2);
1130

1131
1132
            let (reg, id1, loc1) = self.prepare_reg(op1, inst.len() + 1);
            let (mem, mut uses)  = self.prepare_mem(op2, inst.len() + 1 + reg.len() + 1);
1133

1134
            let asm = format!("{} {},{}", inst, reg, mem);
1135
1136
1137

            // merge use vec
            if uses.contains_key(&id1) {
1138
1139
                let mut locs = uses.get_mut(&id1).unwrap();
                vec_utils::add_unique(locs, loc1.clone());
1140
1141
1142
1143
            } else {
                uses.insert(id1, vec![loc1]);
            }

1144
            self.add_asm_inst(
1145
1146
1147
1148
1149
1150
1151
1152
1153
                asm,
                hashmap!{},
                uses,
                true
            )
        }
    }
}

1154
macro_rules! binop_def_r_r {
1155
1156
    ($func_name: ident, $inst: expr, $op_len: expr) => {
        fn $func_name (&mut self, dest: &P<Value>, src: &P<Value>) {
1157
            let inst = $inst.to_string() + &op_postfix($op_len);
1158
            trace!("emit: {} {}, {} -> {}", inst, src, dest, dest);
1159

1160
1161
            let (reg1, id1, loc1) = self.prepare_reg(src, inst.len() + 1);
            let (reg2, id2, loc2) = self.prepare_reg(dest, inst.len() + 1 + reg1.len() + 1);
1162
1163
1164

            let asm = format!("{} {},{}", inst, reg1, reg2);

1165
            self.add_asm_inst(
1166
1167
1168
1169
1170
1171
1172
1173
1174
1175
1176
1177
1178
1179
                asm,
                hashmap!{
                    id2 => vec![loc2.clone()]
                },
                hashmap!{
                    id1 => vec![loc1],
                    id2 => vec![loc2]
                },
                false
            )
        }
    }
}

1180
1181
1182
1183
1184
macro_rules! binop_def_r_imm {
    ($func_name: ident, $inst: expr, $op_len: expr, $imm_ty: ty) => {
        fn $func_name (&mut self, dest: &P<Value>, src: $imm_ty) {
            let inst = $inst.to_string() + &op_postfix($op_len);
            trace!("emit: {} {}, {} -> {}", inst, src, dest, dest);
1185

1186
            let (reg1, id1, loc1) = self.prepare_reg(dest, inst.len() + 1 + 1 + src.to_string().len() + 1);
1187

1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
            let asm = format!("{} ${},{}", inst, src, reg1);

            self.add_asm_inst(
                asm,
                hashmap!{
                    id1 => vec![loc1.clone()]
                },
                hashmap!{
                    id1 => vec![loc1]
                },
                false
            )
1200
1201
1202
1203
        }
    }
}

1204
1205
1206
1207
1208
1209
1210
1211
1212
1213
1214
1215
1216
1217
1218
1219
1220
1221
1222
1223
1224
1225
1226
1227
1228
1229
macro_rules! binop_def_r_mem {
    ($func_name: ident, $inst: expr, $op_len: expr) => {
        fn $func_name (&mut self, dest: &P<Value>, src: &P<Value>) {
            let inst = $inst.to_string() + &op_postfix($op_len);
            trace!("emit: {} {}, {} -> {}", inst, src, dest, dest);

            let (mem, mut uses) = self.prepare_mem(src, inst.len() + 1);
            let (reg, id1, loc1) = self.prepare_reg(dest, inst.len() + 1 + mem.len() + 1);

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

            let asm = format!("{} {},{}", inst, mem, reg);

            self.add_asm_inst(
                asm,
                hashmap!{
                    id1 => vec![loc1]
                },
                uses,
                true
            )
1230
1231
1232
1233
        }
    }
}

1234
1235
macro_rules! mov_r_r {
    ($func_name: ident, $inst: expr, $op_len: expr) => {
1236
        fn $func_name (&mut self, dest: &P<Value>, src: &P<Value>) {
1237
1238
            let inst = $inst.to_string() + &op_postfix($op_len);
            trace!("emit: {} {} -> {}", inst, src, dest);
1239

1240
1241
            let (reg1, id1, loc1) = self.prepare_reg(src, inst.len() + 1);
            let (reg2, id2, loc2) = self.prepare_reg(dest, inst.len() + 1 + reg1.len() + 1);
1242

1243
            let asm = format!("{} {},{}", inst, reg1, reg2);
1244
1245
1246
1247
1248
1249
1250
1251
1252
1253
1254
1255
1256
1257
1258

            self.add_asm_inst(
                asm,
                hashmap!{
                    id2 => vec![loc2]
                },
                hashmap!{
                    id1 => vec![loc1]
                },
                false
            )
        }
    }
}

1259
1260
macro_rules! mov_r_imm {
    ($func_name: ident, $inst: expr, $op_len: expr, $imm_ty: ty) => {
1261
        fn $func_name (&mut self, dest: &P<Value>, src: $imm_ty) {
1262
1263
            let inst = $inst.to_string() + &op_postfix($op_len);
            trace!("emit: {} {} -> {}", inst, src, dest);