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

asm_backend.rs 134 KB
Newer Older
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1
// Copyright 2017 The Australian National University
2
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
3
4
5
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
6
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
9
10
11
12
13
14
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

15
16
#![allow(unused_variables)]

17
use compiler::backend::AOT_EMIT_CONTEXT_FILE;
qinsoon's avatar
qinsoon committed
18
use compiler::backend::RegGroup;
qinsoon's avatar
qinsoon committed
19
use utils::ByteSize;
20
21
use utils::Address;
use utils::POINTER_SIZE;
22
use compiler::backend::x86_64;
23
use compiler::backend::x86_64::CodeGenerator;
qinsoon's avatar
qinsoon committed
24
use compiler::backend::{Reg, Mem};
qinsoon's avatar
qinsoon committed
25
use compiler::backend::x86_64::check_op_len;
qinsoon's avatar
qinsoon committed
26
use compiler::machine_code::MachineCode;
qinsoon's avatar
qinsoon committed
27
use vm::VM;
qinsoon's avatar
qinsoon committed
28
use runtime::ValueLocation;
29

qinsoon's avatar
qinsoon committed
30
use utils::vec_utils;
31
use utils::string_utils;
32
33
use utils::LinkedHashMap;

34
35
use ast::ptr::P;
use ast::ir::*;
36
use ast::types;
37

qinsoon's avatar
qinsoon committed
38
use std::str;
39
use std::usize;
40
use std::slice::Iter;
41
use std::ops;
42
use std::collections::HashSet;
43
use std::sync::RwLock;
qinsoon's avatar
qinsoon committed
44
use std::any::Any;
qinsoon's avatar
qinsoon committed
45

qinsoon's avatar
qinsoon committed
46
47
48
49
50
51
52
/// ASMCode represents a segment of assembly machine code. Usually it is machine code for
/// a Mu function, but it could simply be a sequence of machine code.
/// This data structure implements MachineCode trait which allows compilation passes to
/// operate on the machine code in a machine independent way.
/// This data structure is also designed in a way to support in-place code generation. Though
/// in-place code generation is mostly irrelevant for ahead-of-time compilation, I tried
/// test the idea with this AOT backend.
qinsoon's avatar
qinsoon committed
53
struct ASMCode {
qinsoon's avatar
qinsoon committed
54
55
56
    /// function name for the code
    name: MuName,
    /// a list of all the assembly instructions
qinsoon's avatar
qinsoon committed
57
    code: Vec<ASMInst>,
qinsoon's avatar
qinsoon committed
58
    /// entry block name
59
    entry: MuName,
qinsoon's avatar
qinsoon committed
60
    /// all the blocks
61
    blocks: LinkedHashMap<MuName, ASMBlock>,
qinsoon's avatar
qinsoon committed
62
63
64
65
    /// the patch location for frame size growth/shrink
    /// we only know the exact frame size after register allocation, but we need to insert
    /// frame adjust code beforehand, so we insert adjust code with an empty frame size, and
    /// patch it later
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
66
    frame_size_patchpoints: Vec<ASMLocation>,
qinsoon's avatar
qinsoon committed
67
68
}

69
unsafe impl Send for ASMCode {}
qinsoon's avatar
qinsoon committed
70
71
unsafe impl Sync for ASMCode {}

qinsoon's avatar
qinsoon committed
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
/// ASMInst represents an assembly instruction.
/// This data structure contains enough information to implement MachineCode trait on ASMCode,
/// and it also supports in-place code generation.
#[derive(Clone, Debug)]
struct ASMInst {
    /// actual asm code
    code: String,
    /// defines of this instruction. a map from temporary/register ID to its location
    /// (where it appears in the code string)
    defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
    /// uses of this instruction
    uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
    /// is this instruction using memory operand?
    is_mem_op_used: bool,
    /// is this assembly code a symbol? (not an actual instruction)
    is_symbol: bool,
    /// is this instruction an inserted spill instruction (load from/store to memory)?
    spill_info: Option<SpillMemInfo>,
    /// predecessors of this instruction
    preds: Vec<usize>,
    /// successors of this instruction
    succs: Vec<usize>,
    /// branch target of this instruction
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
95
    branch: ASMBranchTarget,
qinsoon's avatar
qinsoon committed
96
97
98
99
100
101
102
103
104
105
106
107
108
}

/// ASMLocation represents the location of a register/temporary in assembly code.
/// It contains enough information so that we can later patch the register.
#[derive(Clone, Debug, PartialEq, Eq)]
struct ASMLocation {
    /// which row it is in the assembly code vector
    line: usize,
    /// which column
    index: usize,
    /// length of spaces reserved for the register/temporary
    len: usize,
    /// bit-length of the register/temporary
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
109
    oplen: usize,
qinsoon's avatar
qinsoon committed
110
111
112
113
114
115
116
117
118
119
120
121
}

/// ASMBlock represents information about a basic block in assembly.
#[derive(Clone, Debug)]
struct ASMBlock {
    /// [start_inst, end_inst) (includes start_inst)
    start_inst: usize,
    /// [start_inst, end_inst) (excludes end_inst)
    end_inst: usize,
    /// livein reg/temp
    livein: Vec<MuID>,
    /// liveout reg/temp
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
122
    liveout: Vec<MuID>,
qinsoon's avatar
qinsoon committed
123
124
125
126
127
128
129
130
131
132
133
134
135
136
}

/// ASMBranchTarget represents branching control flow of machine instructions.
#[derive(Clone, Debug)]
enum ASMBranchTarget {
    /// not a branching instruction
    None,
    /// a conditional branch to target
    Conditional(MuName),
    /// an unconditional branch to target
    Unconditional(MuName),
    /// this instruction may throw exception to target
    PotentiallyExcepting(MuName),
    /// this instruction is a return
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
137
    Return,
qinsoon's avatar
qinsoon committed
138
139
140
141
142
143
144
}

/// SpillMemInfo represents inserted spilling instructions for loading/storing values
#[derive(Clone, Debug)]
enum SpillMemInfo {
    Load(P<Value>),
    Store(P<Value>),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
145
    CalleeSaved, // Callee saved record
qinsoon's avatar
qinsoon committed
146
147
}

148
impl ASMCode {
qinsoon's avatar
qinsoon committed
149
    /// returns a vector of ASMLocation for all the uses of the given reg/temp
qinsoon's avatar
qinsoon committed
150
151
152
153
154
155
156
    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());
157
                }
qinsoon's avatar
qinsoon committed
158
159
160
161
162
163
164
                None => {}
            }
        }

        ret
    }

qinsoon's avatar
qinsoon committed
165
    /// returns a vector of ASMLocation for all the defines of the given reg/temp
qinsoon's avatar
qinsoon committed
166
167
168
169
170
171
172
    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());
173
                }
qinsoon's avatar
qinsoon committed
174
175
176
177
178
179
180
                None => {}
            }
        }

        ret
    }

qinsoon's avatar
qinsoon committed
181
    /// is the given instruction the starting instruction of a block?
qinsoon's avatar
qinsoon committed
182
183
184
185
186
187
188
189
190
    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
191
    /// is the given instruction the ending instruction of a block?
192
    fn is_last_inst_in_block(&self, inst: usize) -> bool {
qinsoon's avatar
qinsoon committed
193
194
195
196
197
198
199
200
        for block in self.blocks.values() {
            if block.end_inst == inst + 1 {
                return true;
            }
        }
        false
    }

qinsoon's avatar
qinsoon committed
201
    /// finds block for a given instruction and returns the block
qinsoon's avatar
qinsoon committed
202
203
204
205
206
207
208
209
210
    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
211
212
    /// finds block that starts with the given instruction
    /// returns None if we cannot find such block
qinsoon's avatar
qinsoon committed
213
214
215
216
217
218
219
220
221
    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
    }

qinsoon's avatar
qinsoon committed
222
223
224
225
226
227
    /// rewrites code by inserting instructions in certain locations
    /// This function is used for inserting spilling instructions. It takes
    /// two hashmaps as arguments, the keys of which are line numbers where
    /// we should insert code, and the values are the code to be inserted.
    /// We need to carefully ensure the metadata for existing code is
    /// still correct after insertion. This function returns the resulting code.
228
229
    fn rewrite_insert(
        &self,
230
        insert_before: LinkedHashMap<usize, Vec<Box<ASMCode>>>,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
231
        insert_after: LinkedHashMap<usize, Vec<Box<ASMCode>>>,
232
    ) -> Box<ASMCode> {
233
        trace!("insert spilling code");
234
235
        let mut ret = ASMCode {
            name: self.name.clone(),
236
            entry: self.entry.clone(),
237
            code: vec![],
238
            blocks: linked_hashmap!{},
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
239
            frame_size_patchpoints: vec![],
240
241
        };

qinsoon's avatar
qinsoon committed
242
243
        // how many instructions have been inserted
        let mut inst_offset = 0;
qinsoon's avatar
qinsoon committed
244
        let mut cur_block_start = usize::MAX;
245

qinsoon's avatar
qinsoon committed
246
247
        // inst N in old machine code is N' in new machine code
        // this map stores the relationship
248
        let mut location_map: LinkedHashMap<usize, usize> = LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
249

qinsoon's avatar
qinsoon committed
250
        // iterate through old machine code
251
        for i in 0..self.number_of_insts() {
252
253
            trace!("Inst{}", i);

qinsoon's avatar
qinsoon committed
254
255
            if self.is_block_start(i) {
                cur_block_start = i + inst_offset;
256
                trace!("  block start is shifted to {}", cur_block_start);
qinsoon's avatar
qinsoon committed
257
258
            }

259
260
261
262
263
            // 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();
264
                    trace!("  inserted {} insts before", insert.number_of_insts());
265
266
267
268
                }
            }

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

qinsoon's avatar
qinsoon committed
271
272
            // old ith inst is now the (i + inst_offset)th instruction
            location_map.insert(i, i + inst_offset);
273
            trace!("  Inst{} is now Inst{}", i, i + inst_offset);
qinsoon's avatar
qinsoon committed
274

qinsoon's avatar
qinsoon committed
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
            // 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
290
291
292
            // 2. we need to delete existing preds/succs - CFA is required later
            inst.preds.clear();
            inst.succs.clear();
qinsoon's avatar
qinsoon committed
293
294
            // 3. add the inst
            ret.code.push(inst);
295
296
297
298


            // insert code after this instruction
            if insert_after.contains_key(&i) {
qinsoon's avatar
qinsoon committed
299
300
301
                for insert in insert_after.get(&i).unwrap() {
                    ret.append_code_sequence_all(insert);
                    inst_offset += insert.number_of_insts();
302
                    trace!("  inserted {} insts after", insert.number_of_insts());
qinsoon's avatar
qinsoon committed
303
304
305
                }
            }

qinsoon's avatar
qinsoon committed
306
            // if we finish a block
307
308
            if self.is_last_inst_in_block(i) {
                let cur_block_end = i + 1 + inst_offset;
309

qinsoon's avatar
qinsoon committed
310
311
312
                // copy the block
                let (name, block) = self.get_block_by_inst(i);

313
                let new_block = ASMBlock {
314
315
316
317
                    start_inst: cur_block_start,
                    end_inst: cur_block_end,

                    livein: vec![],
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
318
                    liveout: vec![],
319
320
321
322
323
                };

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

qinsoon's avatar
qinsoon committed
324
325
326
327
                cur_block_start = usize::MAX;

                // add to the new code
                ret.blocks.insert(name.clone(), new_block);
328
329
330
            }
        }

qinsoon's avatar
qinsoon committed
331
        // fix patchpoints
qinsoon's avatar
qinsoon committed
332
333
334
335
        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
336
                len: patchpoint.len,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
337
                oplen: patchpoint.oplen,
qinsoon's avatar
qinsoon committed
338
339
340
341
342
            };

            ret.frame_size_patchpoints.push(new_patchpoint);
        }

qinsoon's avatar
qinsoon committed
343
344
345
        ret.control_flow_analysis();

        Box::new(ret)
346
347
    }

qinsoon's avatar
qinsoon committed
348
349
    /// appends a given part of assembly code sequence at the end of current code
    /// During appending, we need to fix line number.
350
    fn append_code_sequence(&mut self, another: &Box<ASMCode>, start_inst: usize, n_insts: usize) {
qinsoon's avatar
qinsoon committed
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
        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);
        }
376
377
    }

qinsoon's avatar
qinsoon committed
378
    /// appends assembly sequence at the end of current code
379
380
381
382
    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
383

qinsoon's avatar
qinsoon committed
384
385
    /// control flow analysis on current code
    /// calculating branch targets, preds/succs for each instruction
qinsoon's avatar
qinsoon committed
386
    fn control_flow_analysis(&mut self) {
387
        const TRACE_CFA: bool = true;
qinsoon's avatar
qinsoon committed
388
389
390
391
392
393

        // control flow analysis
        let n_insts = self.number_of_insts();
        let ref mut asm = self.code;

        for i in 0..n_insts {
394
            trace_if!(TRACE_CFA, "---inst {}---", i);
395
396
397
398
399
400

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

qinsoon's avatar
qinsoon committed
401
402
403
404
405
            // determine predecessor:
            // * if last instruction falls through to current instruction,
            //   the predecessor is last instruction
            // * otherwise, we set predecessor when we deal with the instruction
            //   that branches to current instruction
406
407
408
409
410
411
412
413
414
415
            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);
416
417
418
419
420
421
                                    trace_if!(
                                        TRACE_CFA,
                                        "inst {}: set PREDS as previous inst - fallthrough {}",
                                        i,
                                        last_inst
                                    );
422
423
424
425
426
                                }
                            }
                            // otherwise do nothing
                            _ => {}
                        }
qinsoon's avatar
qinsoon committed
427
                    }
428
                    None => {}
qinsoon's avatar
qinsoon committed
429
430
431
432
                }
            }

            // determine successor
qinsoon's avatar
qinsoon committed
433
            let branch = asm[i].branch.clone(); // make a clone so that we are not borrowing anything
qinsoon's avatar
qinsoon committed
434
435
            match branch {
                ASMBranchTarget::Unconditional(ref target) => {
qinsoon's avatar
qinsoon committed
436
                    // branch-to target
qinsoon's avatar
qinsoon committed
437
438
439
440
441
442
443
444
                    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);

445
446
                    trace_if!(TRACE_CFA, "inst {}: is a branch to {}", i, target);
                    trace_if!(TRACE_CFA, "inst {}: branch target index is {}", i, target_n);
447
448
449
450
451
452
453
454
455
456
457
458
459
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set SUCCS as branch target {}",
                        i,
                        target_n
                    );
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set PREDS as branch source {}",
                        target_n,
                        i
                    );
                }
qinsoon's avatar
qinsoon committed
460
                ASMBranchTarget::Conditional(ref target) => {
qinsoon's avatar
qinsoon committed
461
                    // branch-to target
qinsoon's avatar
qinsoon committed
462
463
                    let target_n = self.blocks.get(target).unwrap().start_inst;

464
                    // cur insts' succ is target
qinsoon's avatar
qinsoon committed
465
466
                    asm[i].succs.push(target_n);

467
468
                    trace_if!(TRACE_CFA, "inst {}: is a cond branch to {}", i, target);
                    trace_if!(TRACE_CFA, "inst {}: branch target index is {}", i, target_n);
469
470
471
472
473
474
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set SUCCS as branch target {}",
                        i,
                        target_n
                    );
qinsoon's avatar
qinsoon committed
475
476
477

                    // target's pred is cur
                    asm[target_n].preds.push(i);
478
                    trace_if!(TRACE_CFA, "inst {}: set PREDS as {}", target_n, i);
479
480
481
482
483
484
485
486

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

487
488
489
490
491
492
                        trace_if!(
                            TRACE_CFA,
                            "inst {}: SET SUCCS as c-branch fallthrough target {}",
                            i,
                            next_inst
                        );
493
494
495
                    } else {
                        panic!("conditional branch does not have a fallthrough target");
                    }
496
                }
497
498
499
500
501
502
503
                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);

504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: is potentially excepting to {}",
                        i,
                        target
                    );
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: excepting target index is {}",
                        i,
                        target_n
                    );
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set SUCCS as excepting target {}",
                        i,
                        target_n
                    );
522
523
524
525
526
527
528
529
530
531

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

532
533
534
535
536
537
                        trace_if!(
                            TRACE_CFA,
                            "inst {}: SET SUCCS as PEI fallthrough target {}",
                            i,
                            next_inst
                        );
538
539
540
                    } else {
                        panic!("PEI does not have a fallthrough target");
                    }
541
                }
qinsoon's avatar
[wip]    
qinsoon committed
542
                ASMBranchTarget::Return => {
543
544
                    trace_if!(TRACE_CFA, "inst {}: is a return", i);
                    trace_if!(TRACE_CFA, "inst {}: has no successor", i);
qinsoon's avatar
[wip]    
qinsoon committed
545
                }
qinsoon's avatar
qinsoon committed
546
547
                ASMBranchTarget::None => {
                    // not branch nor cond branch, succ is next inst
548
                    trace_if!(TRACE_CFA, "inst {}: not a branch inst", i);
549
                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
550
551
552
553
554
555
                        trace_if!(
                            TRACE_CFA,
                            "inst {}: set SUCCS as next inst {}",
                            i,
                            next_inst
                        );
556
                        asm[i].succs.push(next_inst);
qinsoon's avatar
qinsoon committed
557
558
559
560
                    }
                }
            }
        }
561
562
    }

qinsoon's avatar
qinsoon committed
563
    /// finds the previous instruction (skip non-instruction assembly)
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
    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
584

qinsoon's avatar
qinsoon committed
585
    /// finds the next instruction (skip non-instruction assembly)
586
587
588
589
590
591
592
593
594
595
596
    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
597
            }
598
599

            None
qinsoon's avatar
qinsoon committed
600
601
        }
    }
qinsoon's avatar
qinsoon committed
602

qinsoon's avatar
qinsoon committed
603
604
    /// finds the last instruction that appears on or before the given index
    /// (skip non-instruction assembly)
605
606
607
608
609
    fn find_last_inst(i: usize, asm: &Vec<ASMInst>) -> Option<usize> {
        if i == 0 {
            None
        } else {
            let mut cur = i;
610
            loop {
611
612
613
614
615
616
617
618
619
620
621
622
623
                if !asm[cur].is_symbol {
                    return Some(cur);
                }

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

qinsoon's avatar
qinsoon committed
624
625
626
    fn add_frame_size_patchpoint(&mut self, patchpoint: ASMLocation) {
        self.frame_size_patchpoints.push(patchpoint);
    }
627
628
}

629
impl MachineCode for ASMCode {
630
631
632
    fn as_any(&self) -> &Any {
        self
    }
qinsoon's avatar
qinsoon committed
633
634

    /// returns the count of instructions in this machine code
635
636
637
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
qinsoon's avatar
qinsoon committed
638
639

    /// is the specified index a move instruction?
640
641
642
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
qinsoon's avatar
qinsoon committed
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
            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
                }
658
            }
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
659
            None => false,
660
661
        }
    }
qinsoon's avatar
qinsoon committed
662
663

    /// is the specified index using memory operands?
qinsoon's avatar
qinsoon committed
664
    fn is_using_mem_op(&self, index: usize) -> bool {
qinsoon's avatar
qinsoon committed
665
        self.code[index].is_mem_op_used
qinsoon's avatar
qinsoon committed
666
    }
667

qinsoon's avatar
qinsoon committed
668
669
    /// is the specified index a jump instruction? (unconditional jump)
    /// returns an Option for target block
670
671
672
673
    fn is_jmp(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
            Some(inst) if inst.code.starts_with("jmp") => {
674
                let split: Vec<&str> = inst.code.split(' ').collect();
675

676
                Some(demangle_name(String::from(split[1])))
677
            }
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
678
            _ => None,
679
680
681
        }
    }

qinsoon's avatar
qinsoon committed
682
    /// is the specified index a label? returns an Option for the label
683
684
685
686
    fn is_label(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
            Some(inst) if inst.code.ends_with(':') => {
687
                let split: Vec<&str> = inst.code.split(':').collect();
688

689
                Some(demangle_name(String::from(split[0])))
690
            }
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
691
            _ => None,
692
693
        }
    }
qinsoon's avatar
qinsoon committed
694

qinsoon's avatar
qinsoon committed
695
696
    /// is the specified index loading a spilled register?
    /// returns an Option for the register that is loaded into
qinsoon's avatar
qinsoon committed
697
698
699
700
    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()),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
701
                _ => None,
qinsoon's avatar
qinsoon committed
702
703
704
705
706
707
            }
        } else {
            None
        }
    }

qinsoon's avatar
qinsoon committed
708
709
    /// is the specified index storing a spilled register?
    /// returns an Option for the register that is stored
qinsoon's avatar
qinsoon committed
710
711
712
713
    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()),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
714
                _ => None,
qinsoon's avatar
qinsoon committed
715
716
717
718
719
            }
        } else {
            None
        }
    }
qinsoon's avatar
qinsoon committed
720
721

    /// gets successors of a specified index
qinsoon's avatar
qinsoon committed
722
    fn get_succs(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
723
        &self.code[index].succs
qinsoon's avatar
qinsoon committed
724
    }
qinsoon's avatar
qinsoon committed
725
726

    /// gets predecessors of a specified index
qinsoon's avatar
qinsoon committed
727
    fn get_preds(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
728
        &self.code[index].preds
qinsoon's avatar
qinsoon committed
729
    }
qinsoon's avatar
qinsoon committed
730
731

    /// gets the register uses of a specified index
qinsoon's avatar
qinsoon committed
732
733
    fn get_inst_reg_uses(&self, index: usize) -> Vec<MuID> {
        self.code[index].uses.keys().map(|x| *x).collect()
734
    }
qinsoon's avatar
qinsoon committed
735
736

    /// gets the register defines of a specified index
qinsoon's avatar
qinsoon committed
737
738
    fn get_inst_reg_defines(&self, index: usize) -> Vec<MuID> {
        self.code[index].defines.keys().map(|x| *x).collect()
739
    }
qinsoon's avatar
qinsoon committed
740
741

    /// replace a temp with a machine register (to_reg must be a machine register)
742
    fn replace_reg(&mut self, from: MuID, to: MuID) {
qinsoon's avatar
qinsoon committed
743
        // replace defines
qinsoon's avatar
qinsoon committed
744
745
        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
746
747
748

            // pick the right reg based on length
            let to_reg = x86_64::get_alias_for_length(to, loc.oplen);
749
            let to_reg_tag = to_reg.name();
qinsoon's avatar
qinsoon committed
750
751
            let to_reg_string = "%".to_string() + &to_reg_tag;

752
753
754
755
            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
756
                to_reg_string.len(),
757
            );
758
        }
759

qinsoon's avatar
qinsoon committed
760
        // replace uses
qinsoon's avatar
qinsoon committed
761
762
        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
763
764
765

            // pick the right reg based on length
            let to_reg = x86_64::get_alias_for_length(to, loc.oplen);
766
            let to_reg_tag = to_reg.name();
qinsoon's avatar
qinsoon committed
767
768
            let to_reg_string = "%".to_string() + &to_reg_tag;

769
770
771
772
            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
773
                to_reg_string.len(),
774
            );
775
776
        }
    }
777

qinsoon's avatar
qinsoon committed
778
    /// replace a temp that is defined in the inst with another temp
779
    fn replace_define_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
780
        let to_reg_string: MuName = REG_PLACEHOLDER.clone();
781

qinsoon's avatar
qinsoon committed
782
783
784
785
786
787
        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() {
788
789
790
791
                string_utils::replace(
                    &mut asm.code,
                    loc.index,
                    &to_reg_string,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
792
                    to_reg_string.len(),
793
                );
794
795
            }

qinsoon's avatar
qinsoon committed
796
797
            // remove old key, insert new one
            asm.defines.remove(&from);
798
            asm.defines.insert(to, define_locs);
799
        }
800
801
    }

qinsoon's avatar
qinsoon committed
802
    /// replace a temp that is used in the inst with another temp
803
    fn replace_use_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
804
        let to_reg_string: MuName = REG_PLACEHOLDER.clone();
805
806

        let asm = &mut self.code[inst];
qinsoon's avatar
qinsoon committed
807
808
809
810
811
812

        // 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() {
813
814
815
816
                string_utils::replace(
                    &mut asm.code,
                    loc.index,
                    &to_reg_string,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
817
                    to_reg_string.len(),
818
                );
819
820
            }

qinsoon's avatar
qinsoon committed
821
822
            // remove old key, insert new one
            asm.uses.remove(&from);
823
            asm.uses.insert(to, use_locs);
824
825
        }
    }
qinsoon's avatar
qinsoon committed
826
827

    /// set an instruction as nop
828
    fn set_inst_nop(&mut self, index: usize) {
829
        self.code[index].code.clear();
830
    }
qinsoon's avatar
qinsoon committed
831

qinsoon's avatar
qinsoon committed
832
833
834
    /// remove unnecessary push/pop if the callee saved register is not used
    /// returns what registers push/pop have been deleted, and the number of callee saved registers
    /// that weren't deleted
835
    fn remove_unnecessary_callee_saved(&mut self, used_callee_saved: Vec<MuID>) -> HashSet<MuID> {
qinsoon's avatar
qinsoon committed
836
837
838
        // we always save rbp
        let rbp = x86_64::RBP.extract_ssa_id().unwrap();

839
        let find_op_other_than_rbp = |inst: &ASMInst| -> MuID {
qinsoon's avatar
qinsoon committed
840
            for id in inst.defines.keys() {
841
842
                if *id != rbp {
                    return *id;
qinsoon's avatar
qinsoon committed
843
844
845
                }
            }
            for id in inst.uses.keys() {
846
847
                if *id != rbp {
                    return *id;
qinsoon's avatar
qinsoon committed
848
849
                }
            }
850
            panic!("Expected to find a used register other than the rbp");
qinsoon's avatar
qinsoon committed
851
852
853
        };

        let mut inst_to_remove = vec![];
854
        let mut regs_to_remove = HashSet::new();
qinsoon's avatar
qinsoon committed
855
856
857

        for i in 0..self.number_of_insts() {
            let ref inst = self.code[i];
858
859
860
861
            match inst.spill_info {
                Some(SpillMemInfo::CalleeSaved) => {
                    let reg = find_op_other_than_rbp(inst);
                    if !used_callee_saved.contains(&reg) {
862
863
864
865
                        trace!(
                            "removing instruction {:?} for save/restore unnecessary callee saved regs",
                            inst
                        );
866
867
                        regs_to_remove.insert(reg);
                        inst_to_remove.push(i);
qinsoon's avatar
qinsoon committed
868
869
                    }
                }
870
                _ => {}
qinsoon's avatar
qinsoon committed
871
872
873
874
875
876
877
            }
        }

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

878
        regs_to_remove
qinsoon's avatar
qinsoon committed
879
    }
qinsoon's avatar
qinsoon committed
880

qinsoon's avatar
qinsoon committed
881
    /// patch frame size
882
    fn patch_frame_size(&mut self, size: usize) {
qinsoon's avatar
qinsoon committed
883
        let size = size.to_string();
qinsoon's avatar
qinsoon committed
884
        assert!(size.len() <= FRAME_SIZE_PLACEHOLDER_LEN);
qinsoon's avatar
qinsoon committed
885
886
887
888
889
890

        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());
        }
    }
qinsoon's avatar
qinsoon committed
891
892

    /// emit the machine code as a byte array
893
894
    fn emit(&self) -> Vec<u8> {
        let mut ret = vec![];
895

896
        for inst in self.code.iter() {
897
898
899
900
            if !inst.is_symbol {
                ret.append(&mut "\t".to_string().into_bytes());
            }

901
902
903
            ret.append(&mut inst.code.clone().into_bytes());
            ret.append(&mut "\n".to_string().into_bytes());
        }
904

905
906
        ret
    }
907

qinsoon's avatar
qinsoon committed
908
    /// emit the machine instruction at the given index as a byte array
909
910
911
912
913
914
915
916
917
918
919
920
921
    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
    }
qinsoon's avatar
qinsoon committed
922
923

    /// print the whole machine code by trace level log
924
925
926
    fn trace_mc(&self) {
        trace!("");
        trace!("code for {}: \n", self.name);
927

928
929
        let n_insts = self.code.len();
        for i in 0..n_insts {
930
            self.trace_inst(i);
931
        }
932
933

        trace!("")
934
    }
qinsoon's avatar
qinsoon committed
935
936

    /// print an inst for the given index
937
    fn trace_inst(&self, i: usize) {
938
939
940
941
942
943
944
945
946
        trace!(
            "#{}\t{:60}\t\tdefine: {:?}\tuses: {:?}\tpred: {:?}\tsucc: {:?}",
            i,
            demangle_text(self.code[i].code.clone()),
            self.get_inst_reg_defines(i),
            self.get_inst_reg_uses(i),
            self.code[i].preds,
            self.code[i].succs
        );
947
    }
qinsoon's avatar
qinsoon committed
948
949

    /// gets block livein
950
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
951
952
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
953
            None => None,
qinsoon's avatar
qinsoon committed
954
        }
955
    }
qinsoon's avatar
qinsoon committed
956
957

    /// gets block liveout
958
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
959
960
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
961
            None => None,
qinsoon's avatar
qinsoon committed
962
        }
963
    }
qinsoon's avatar
qinsoon committed
964
965

    /// sets block livein
966
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
967
968
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
969
    }
qinsoon's avatar
qinsoon committed
970
971

    /// sets block liveout
972
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
973
974
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
975
    }
qinsoon's avatar
qinsoon committed
976
977

    /// gets all the blocks
qinsoon's avatar
qinsoon committed
978
979
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
980
    }
981

qinsoon's avatar
qinsoon committed
982
    /// gets the entry block
983
984
985
    fn get_entry_block(&self) -> MuName {
        self.entry.clone()
    }
qinsoon's avatar
qinsoon committed
986
987

    /// gets the range of a given block, returns [start_inst, end_inst) (end_inst not included)
988
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
qinsoon's avatar
qinsoon committed
989
990
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
991
            None => None,
992
993
        }
    }
994

qinsoon's avatar
qinsoon committed
995
    /// gets the block for a given index, returns an Option for the block
996
997
998
999
1000
1001
1002
1003
1004
    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
    }

qinsoon's avatar
qinsoon committed
1005
    /// gets the next instruction of a specified index (labels are not instructions)
1006
1007
1008
1009
    fn get_next_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_next_inst(index, &self.code)
    }

qinsoon's avatar
qinsoon committed
1010
    /// gets the previous instruction of a specified index (labels are not instructions)
1011
1012
1013
    fn get_last_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_last_inst(index, &self.code)
    }
1014
1015
}

qinsoon's avatar
qinsoon committed
1016
impl ASMInst {
qinsoon's avatar
qinsoon committed
1017
    /// creates a symbolic assembly code (not an instruction)
qinsoon's avatar
qinsoon committed
1018
1019
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
1020
            code: line,
1021
1022
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
1023
            is_mem_op_used: false,
1024
            is_symbol: true,
qinsoon's avatar
qinsoon committed
1025
1026
            preds: vec![],
            succs: vec![],
1027
1028
            branch: ASMBranchTarget::None,

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1029
            spill_info: None,
1030
1031
        }
    }
qinsoon's avatar
qinsoon committed
1032
1033

    /// creates an instruction
qinsoon's avatar
qinsoon committed
1034
1035
    fn inst(
        inst: String,
1036
1037
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
1038
        is_mem_op_used: bool,
1039
        target: ASMBranchTarget,
Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1040
        spill_info: Option<SpillMemInfo>,
1041
    ) -> ASMInst {
qinsoon's avatar
qinsoon committed
1042
        ASMInst {
1043
1044
            code: inst,
            defines: defines,
qinsoon's avatar
qinsoon committed
1045
            uses: uses,
1046
            is_symbol: false,
qinsoon's avatar
qinsoon committed
1047
1048
1049
            is_mem_op_used: is_mem_op_used,
            preds: vec![],
            succs: vec![],
1050
1051
            branch: target,

Isaac Oscar Gariano's avatar
Isaac Oscar Gariano committed
1052
            spill_info