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 141 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;
18
use compiler::backend::AOT_EMIT_SYM_TABLE_FILE;
qinsoon's avatar
qinsoon committed
19
use compiler::backend::RegGroup;
qinsoon's avatar
qinsoon committed
20
use utils::ByteSize;
21
22
use utils::Address;
use utils::POINTER_SIZE;
23
use compiler::backend::x86_64;
24
use compiler::backend::x86_64::CodeGenerator;
qinsoon's avatar
qinsoon committed
25
use compiler::backend::{Reg, Mem};
qinsoon's avatar
qinsoon committed
26
use compiler::backend::x86_64::check_op_len;
qinsoon's avatar
qinsoon committed
27
use compiler::machine_code::MachineCode;
qinsoon's avatar
qinsoon committed
28
use vm::VM;
qinsoon's avatar
qinsoon committed
29
use runtime::ValueLocation;
30

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

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

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

qinsoon's avatar
qinsoon committed
47
48
49
50
51
52
53
/// 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
54
struct ASMCode {
qinsoon's avatar
qinsoon committed
55
56
57
    /// function name for the code
    name: MuName,
    /// a list of all the assembly instructions
qinsoon's avatar
qinsoon committed
58
    code: Vec<ASMInst>,
qinsoon's avatar
qinsoon committed
59
    /// entry block name
60
    entry: MuName,
qinsoon's avatar
qinsoon committed
61
    /// all the blocks
62
    blocks: LinkedHashMap<MuName, ASMBlock>,
qinsoon's avatar
qinsoon committed
63
64
65
66
    /// 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
67
    frame_size_patchpoints: Vec<ASMLocation>
qinsoon's avatar
qinsoon committed
68
69
}

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

qinsoon's avatar
qinsoon committed
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
/// 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
96
    branch: ASMBranchTarget
qinsoon's avatar
qinsoon committed
97
98
99
100
101
102
103
104
105
106
107
108
109
}

/// 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
110
    oplen: usize
qinsoon's avatar
qinsoon committed
111
112
113
114
115
116
117
118
119
120
121
122
}

/// 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
123
    liveout: Vec<MuID>
qinsoon's avatar
qinsoon committed
124
125
126
127
128
129
130
131
132
133
134
135
136
137
}

/// 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
138
    Return
qinsoon's avatar
qinsoon committed
139
140
141
142
143
144
145
}

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

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

        ret
    }

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

        ret
    }

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

qinsoon's avatar
qinsoon committed
202
    /// finds block for a given instruction and returns the block
qinsoon's avatar
qinsoon committed
203
204
205
206
207
208
209
210
211
    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
212
213
    /// finds block that starts with the given instruction
    /// returns None if we cannot find such block
qinsoon's avatar
qinsoon committed
214
215
216
217
218
219
220
221
222
    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
223
224
225
226
227
228
    /// 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.
229
230
    fn rewrite_insert(
        &self,
231
        insert_before: LinkedHashMap<usize, Vec<Box<ASMCode>>>,
232
        insert_after: LinkedHashMap<usize, Vec<Box<ASMCode>>>
233
    ) -> Box<ASMCode> {
234
        trace!("insert spilling code");
235
236
        let mut ret = ASMCode {
            name: self.name.clone(),
237
            entry: self.entry.clone(),
238
            code: vec![],
239
            blocks: linked_hashmap!{},
240
            frame_size_patchpoints: vec![]
241
242
        };

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

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

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

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

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

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

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

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


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

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

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

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

                    livein: vec![],
319
                    liveout: vec![]
320
321
322
323
324
                };

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

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

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

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

            ret.frame_size_patchpoints.push(new_patchpoint);
        }

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

        Box::new(ret)
347
348
    }

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

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

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

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

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

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

qinsoon's avatar
qinsoon committed
402
403
404
405
406
            // 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
407
408
409
410
411
412
413
414
415
416
            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);
417
418
419
420
421
422
                                    trace_if!(
                                        TRACE_CFA,
                                        "inst {}: set PREDS as previous inst - fallthrough {}",
                                        i,
                                        last_inst
                                    );
423
424
425
426
427
                                }
                            }
                            // otherwise do nothing
                            _ => {}
                        }
qinsoon's avatar
qinsoon committed
428
                    }
429
                    None => {}
qinsoon's avatar
qinsoon committed
430
431
432
433
                }
            }

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

447
448
                    trace_if!(TRACE_CFA, "inst {}: is a branch to {}", i, target);
                    trace_if!(TRACE_CFA, "inst {}: branch target index is {}", i, target_n);
449
450
451
452
453
454
455
456
457
458
459
460
461
                    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
462
                ASMBranchTarget::Conditional(ref target) => {
qinsoon's avatar
qinsoon committed
463
                    // branch-to target
qinsoon's avatar
qinsoon committed
464
465
                    let target_n = self.blocks.get(target).unwrap().start_inst;

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

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

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

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

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

506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
                    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
                    );
524
525
526
527
528
529
530
531
532
533

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

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

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

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

            None
qinsoon's avatar
qinsoon committed
602
603
        }
    }
qinsoon's avatar
qinsoon committed
604

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

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

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

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

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

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

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

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

678
                Some(demangle_name(String::from(split[1])))
679
            }
680
            _ => None
681
682
683
        }
    }

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

691
                Some(demangle_name(String::from(split[0])))
692
            }
693
            _ => None
694
695
        }
    }
qinsoon's avatar
qinsoon committed
696

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

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

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

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

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

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

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

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

754
755
756
757
            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
758
                to_reg_string.len()
759
            );
760
        }
761

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

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

771
772
773
774
            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
775
                to_reg_string.len()
776
            );
777
778
        }
    }
779

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

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

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

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

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

        // 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() {
815
816
817
818
                string_utils::replace(
                    &mut asm.code,
                    loc.index,
                    &to_reg_string,
819
                    to_reg_string.len()
820
                );
821
822
            }

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

829
    /// replace destination for a jump instruction
830
831
832
833
834
835
836
837
838
839
    fn replace_branch_dest(&mut self, inst: usize, new_dest: &str, succ: MuID) {
        {
            let asm = &mut self.code[inst];

            asm.code = format!("jmp {}", symbol(mangle_name(String::from(new_dest))));
            asm.succs.clear();
            asm.succs.push(succ);
        }
        {
            let asm = &mut self.code[succ];
840

841
842
843
844
            if !asm.preds.contains(&inst) {
                asm.preds.push(inst);
            }
        }
845
846
    }

qinsoon's avatar
qinsoon committed
847
    /// set an instruction as nop
848
    fn set_inst_nop(&mut self, index: usize) {
849
        self.code[index].code.clear();
850
    }
qinsoon's avatar
qinsoon committed
851

qinsoon's avatar
qinsoon committed
852
853
854
    /// 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
855
    fn remove_unnecessary_callee_saved(&mut self, used_callee_saved: Vec<MuID>) -> HashSet<MuID> {
qinsoon's avatar
qinsoon committed
856
857
858
        // we always save rbp
        let rbp = x86_64::RBP.extract_ssa_id().unwrap();

859
        let find_op_other_than_rbp = |inst: &ASMInst| -> MuID {
qinsoon's avatar
qinsoon committed
860
            for id in inst.defines.keys() {
861
862
                if *id != rbp {
                    return *id;
qinsoon's avatar
qinsoon committed
863
864
865
                }
            }
            for id in inst.uses.keys() {
866
867
                if *id != rbp {
                    return *id;
qinsoon's avatar
qinsoon committed
868
869
                }
            }
870
            panic!("Expected to find a used register other than the rbp");
qinsoon's avatar
qinsoon committed
871
872
873
        };

        let mut inst_to_remove = vec![];
874
        let mut regs_to_remove = HashSet::new();
qinsoon's avatar
qinsoon committed
875
876
877

        for i in 0..self.number_of_insts() {
            let ref inst = self.code[i];
878
879
880
881
            match inst.spill_info {
                Some(SpillMemInfo::CalleeSaved) => {
                    let reg = find_op_other_than_rbp(inst);
                    if !used_callee_saved.contains(&reg) {
882
                        trace!(
qinsoon's avatar
qinsoon committed
883
884
                            "removing instruction {:?} for save/restore \
                             unnecessary callee saved regs",
885
886
                            inst
                        );
887
888
                        regs_to_remove.insert(reg);
                        inst_to_remove.push(i);
qinsoon's avatar
qinsoon committed
889
890
                    }
                }
891
                _ => {}
qinsoon's avatar
qinsoon committed
892
893
894
895
896
897
898
            }
        }

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

899
        regs_to_remove
qinsoon's avatar
qinsoon committed
900
    }
qinsoon's avatar
qinsoon committed
901

qinsoon's avatar
qinsoon committed
902
    /// patch frame size
903
    fn patch_frame_size(&mut self, size: usize) {
qinsoon's avatar
qinsoon committed
904
        let size = size.to_string();
qinsoon's avatar
qinsoon committed
905
        assert!(size.len() <= FRAME_SIZE_PLACEHOLDER_LEN);
qinsoon's avatar
qinsoon committed
906
907
908
909
910
911

        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
912
913

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

917
        for inst in self.code.iter() {
918
919
920
921
            if !inst.is_symbol {
                ret.append(&mut "\t".to_string().into_bytes());
            }

922
923
924
            ret.append(&mut inst.code.clone().into_bytes());
            ret.append(&mut "\n".to_string().into_bytes());
        }
925

926
927
        ret
    }
928

qinsoon's avatar
qinsoon committed
929
    /// emit the machine instruction at the given index as a byte array
930
931
932
933
934
935
936
937
938
939
940
941
942
    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
943
944

    /// print the whole machine code by trace level log
945
946
947
    fn trace_mc(&self) {
        trace!("");
        trace!("code for {}: \n", self.name);
948

949
950
        let n_insts = self.code.len();
        for i in 0..n_insts {
951
            self.trace_inst(i);
952
        }
953
954

        trace!("")
955
    }
qinsoon's avatar
qinsoon committed
956
957

    /// print an inst for the given index
958
    fn trace_inst(&self, i: usize) {
959
960
961
962
963
964
965
966
967
        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
        );
968
    }
qinsoon's avatar
qinsoon committed
969
970

    /// gets block livein
971
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
972
973
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
974
            None => None
qinsoon's avatar
qinsoon committed
975
        }
976
    }
qinsoon's avatar
qinsoon committed
977
978

    /// gets block liveout
979
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
qinsoon's avatar
qinsoon committed
980
981
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
982
            None => None
qinsoon's avatar
qinsoon committed
983
        }
984
    }
qinsoon's avatar
qinsoon committed
985
986

    /// sets block livein
987
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
988
989
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
990
    }
qinsoon's avatar
qinsoon committed
991
992

    /// sets block liveout
993
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
qinsoon's avatar
qinsoon committed
994
995
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
996
    }
qinsoon's avatar
qinsoon committed
997
998

    /// gets all the blocks
qinsoon's avatar
qinsoon committed
999
1000
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
1001
    }
1002

qinsoon's avatar
qinsoon committed
1003
    /// gets the entry block
1004
1005
1006
    fn get_entry_block(&self) -> MuName {
        self.entry.clone()
    }
qinsoon's avatar
qinsoon committed
1007
1008

    /// gets the range of a given block, returns [start_inst, end_inst) (end_inst not included)
1009
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
qinsoon's avatar
qinsoon committed
1010
1011
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
1012
            None => None
1013
1014
        }
    }
1015

qinsoon's avatar
qinsoon committed
1016
    /// gets the block for a given index, returns an Option for the block
1017
1018
1019
1020
1021
1022
1023
1024
1025
    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
1026
    /// gets the next instruction of a specified index (labels are not instructions)
1027
1028
1029
1030
    fn get_next_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_next_inst(index, &self.code)
    }

qinsoon's avatar
qinsoon committed
1031
    /// gets the previous instruction of a specified index (labels are not instructions)
1032
1033
1034
    fn get_last_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_last_inst(index, &self.code)
    }
1035
1036
}

qinsoon's avatar
qinsoon committed
1037
impl ASMInst {
qinsoon's avatar
qinsoon committed
1038
    /// creates a symbolic assembly code (not an instruction)
qinsoon's avatar
qinsoon committed
1039
1040
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
1041
            code: line,
1042
1043
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
1044
            is_mem_op_used: false,
1045
            is_symbol: true,
qinsoon's avatar
qinsoon committed
1046
1047
            preds: vec![],
            succs: vec![],
1048
1049
            branch: ASMBranchTarget::None,

1050
            spill_info: None
1051
1052
        }
    }
qinsoon's avatar
qinsoon committed
1053
1054

    /// creates an instruction
qinsoon's avatar
qinsoon committed
1055
1056
    fn inst(
        inst: String,