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