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

31
use utils::string_utils;
32
use utils::vec_utils;
33 34
use utils::LinkedHashMap;

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

qinsoon's avatar
qinsoon committed
39
use std::any::Any;
40
use std::collections::HashSet;
41
use std::io::prelude::*;
42 43 44 45 46 47
use std::ops;
use std::path;
use std::slice::Iter;
use std::str;
use std::sync::{Arc, RwLock};
use std::usize;
48

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

72
unsafe impl Send for ASMCode {}
qinsoon's avatar
qinsoon committed
73 74
unsafe impl Sync for ASMCode {}

qinsoon's avatar
qinsoon committed
75
/// ASMInst represents an assembly instruction.
76 77
/// This data structure contains enough information to implement MachineCode
/// trait on ASMCode, and it also supports in-place code generation.
qinsoon's avatar
qinsoon committed
78 79 80 81
#[derive(Clone, Debug)]
struct ASMInst {
    /// actual asm code
    code: String,
82 83
    /// defines of this instruction. a map from temporary/register ID to its
    /// location (where it appears in the code string)
qinsoon's avatar
qinsoon committed
84 85 86 87 88 89 90
    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,
91 92
    /// is this instruction an inserted spill instruction (load from/store to
    /// memory)?
qinsoon's avatar
qinsoon committed
93 94 95 96 97 98
    spill_info: Option<SpillMemInfo>,
    /// predecessors of this instruction
    preds: Vec<usize>,
    /// successors of this instruction
    succs: Vec<usize>,
    /// branch target of this instruction
99
    branch: ASMBranchTarget
qinsoon's avatar
qinsoon committed
100 101
}

102 103 104
/// ASMLocation represents the location of a register/temporary in assembly
/// code. It contains enough information so that we can later patch the
/// register.
qinsoon's avatar
qinsoon committed
105 106 107 108 109 110 111 112 113
#[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
114
    oplen: usize
qinsoon's avatar
qinsoon committed
115 116 117 118 119 120 121 122 123 124 125 126
}

/// 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
127
    liveout: Vec<MuID>
qinsoon's avatar
qinsoon committed
128 129 130 131 132 133 134 135 136 137 138 139 140 141
}

/// 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
142
    Return
qinsoon's avatar
qinsoon committed
143 144
}

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

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

        ret
    }

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

        ret
    }

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

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

qinsoon's avatar
qinsoon committed
249 250
        // how many instructions have been inserted
        let mut inst_offset = 0;
qinsoon's avatar
qinsoon committed
251
        let mut cur_block_start = usize::MAX;
252

qinsoon's avatar
qinsoon committed
253 254
        // inst N in old machine code is N' in new machine code
        // this map stores the relationship
255 256
        let mut location_map: LinkedHashMap<usize, usize> =
            LinkedHashMap::new();
qinsoon's avatar
qinsoon committed
257

qinsoon's avatar
qinsoon committed
258
        // iterate through old machine code
259
        for i in 0..self.number_of_insts() {
260 261
            trace!("Inst{}", i);

qinsoon's avatar
qinsoon committed
262 263
            if self.is_block_start(i) {
                cur_block_start = i + inst_offset;
264
                trace!("  block start is shifted to {}", cur_block_start);
qinsoon's avatar
qinsoon committed
265 266
            }

267 268 269 270 271
            // 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();
272 273 274 275
                    trace!(
                        "  inserted {} insts before",
                        insert.number_of_insts()
                    );
276 277 278 279
                }
            }

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

qinsoon's avatar
qinsoon committed
282 283
            // old ith inst is now the (i + inst_offset)th instruction
            location_map.insert(i, i + inst_offset);
284
            trace!("  Inst{} is now Inst{}", i, i + inst_offset);
qinsoon's avatar
qinsoon committed
285

286 287
            // this instruction has been offset by several
            // instructions('inst_offset') update its info
qinsoon's avatar
qinsoon committed
288 289 290 291 292 293 294 295 296 297 298 299 300
            // 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
301 302 303
            // 2. we need to delete existing preds/succs - CFA is required later
            inst.preds.clear();
            inst.succs.clear();
qinsoon's avatar
qinsoon committed
304 305
            // 3. add the inst
            ret.code.push(inst);
306 307 308

            // insert code after this instruction
            if insert_after.contains_key(&i) {
qinsoon's avatar
qinsoon committed
309 310 311
                for insert in insert_after.get(&i).unwrap() {
                    ret.append_code_sequence_all(insert);
                    inst_offset += insert.number_of_insts();
312 313 314 315
                    trace!(
                        "  inserted {} insts after",
                        insert.number_of_insts()
                    );
qinsoon's avatar
qinsoon committed
316 317 318
                }
            }

qinsoon's avatar
qinsoon committed
319
            // if we finish a block
320 321
            if self.is_last_inst_in_block(i) {
                let cur_block_end = i + 1 + inst_offset;
322

qinsoon's avatar
qinsoon committed
323 324 325
                // copy the block
                let (name, block) = self.get_block_by_inst(i);

326
                let new_block = ASMBlock {
327 328 329 330
                    start_inst: cur_block_start,
                    end_inst: cur_block_end,

                    livein: vec![],
331
                    liveout: vec![]
332 333 334 335 336
                };

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

qinsoon's avatar
qinsoon committed
337 338 339 340
                cur_block_start = usize::MAX;

                // add to the new code
                ret.blocks.insert(name.clone(), new_block);
341 342 343
            }
        }

qinsoon's avatar
qinsoon committed
344
        // fix patchpoints
qinsoon's avatar
qinsoon committed
345 346 347 348
        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
349
                len: patchpoint.len,
350
                oplen: patchpoint.oplen
qinsoon's avatar
qinsoon committed
351 352 353 354 355
            };

            ret.frame_size_patchpoints.push(new_patchpoint);
        }

qinsoon's avatar
qinsoon committed
356 357 358
        ret.control_flow_analysis();

        Box::new(ret)
359 360
    }

361 362 363 364 365 366 367 368
    /// appends a given part of assembly code sequence at the end of current
    /// code During appending, we need to fix line number.
    fn append_code_sequence(
        &mut self,
        another: &Box<ASMCode>,
        start_inst: usize,
        n_insts: usize
    ) {
qinsoon's avatar
qinsoon committed
369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393
        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);
        }
394 395
    }

qinsoon's avatar
qinsoon committed
396
    /// appends assembly sequence at the end of current code
397 398 399 400
    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
401

qinsoon's avatar
qinsoon committed
402 403
    /// control flow analysis on current code
    /// calculating branch targets, preds/succs for each instruction
qinsoon's avatar
qinsoon committed
404
    fn control_flow_analysis(&mut self) {
405
        const TRACE_CFA: bool = true;
qinsoon's avatar
qinsoon committed
406 407 408 409 410 411

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

        for i in 0..n_insts {
412
            trace_if!(TRACE_CFA, "---inst {}---", i);
413 414 415 416 417 418

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

qinsoon's avatar
qinsoon committed
419
            // determine predecessor:
420 421
            // * if last instruction falls through to current instruction, the
            //   predecessor is last instruction
qinsoon's avatar
qinsoon committed
422 423
            // * otherwise, we set predecessor when we deal with the instruction
            //   that branches to current instruction
424 425 426 427 428 429
            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 {
430 431
                            // if it is a fallthrough, we set its preds as last
                            // inst
432 433 434
                            ASMBranchTarget::None => {
                                if !asm[i].preds.contains(&last_inst) {
                                    asm[i].preds.push(last_inst);
435 436 437 438 439 440
                                    trace_if!(
                                        TRACE_CFA,
                                        "inst {}: set PREDS as previous inst - fallthrough {}",
                                        i,
                                        last_inst
                                    );
441 442 443 444 445
                                }
                            }
                            // otherwise do nothing
                            _ => {}
                        }
qinsoon's avatar
qinsoon committed
446
                    }
447
                    None => {}
qinsoon's avatar
qinsoon committed
448 449 450 451
                }
            }

            // determine successor
qinsoon's avatar
qinsoon committed
452 453
            // make a clone so that we are not borrowing anything
            let branch = asm[i].branch.clone();
qinsoon's avatar
qinsoon committed
454 455
            match branch {
                ASMBranchTarget::Unconditional(ref target) => {
qinsoon's avatar
qinsoon committed
456
                    // branch-to target
qinsoon's avatar
qinsoon committed
457 458 459 460 461 462 463 464
                    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);

465 466 467 468 469 470 471 472 473 474 475 476
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: is a branch to {}",
                        i,
                        target
                    );
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: branch target index is {}",
                        i,
                        target_n
                    );
477 478 479 480 481 482 483 484 485 486 487 488 489
                    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
490
                ASMBranchTarget::Conditional(ref target) => {
qinsoon's avatar
qinsoon committed
491
                    // branch-to target
qinsoon's avatar
qinsoon committed
492 493
                    let target_n = self.blocks.get(target).unwrap().start_inst;

494
                    // cur insts' succ is target
qinsoon's avatar
qinsoon committed
495 496
                    asm[i].succs.push(target_n);

497 498 499 500 501 502 503 504 505 506 507 508
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: is a cond branch to {}",
                        i,
                        target
                    );
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: branch target index is {}",
                        i,
                        target_n
                    );
509 510 511 512 513 514
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set SUCCS as branch target {}",
                        i,
                        target_n
                    );
qinsoon's avatar
qinsoon committed
515 516 517

                    // target's pred is cur
                    asm[target_n].preds.push(i);
518 519 520 521 522 523
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set PREDS as {}",
                        target_n,
                        i
                    );
524 525 526 527 528 529 530 531

                    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 c-branch fallthrough target {}",
                            i,
                            next_inst
                        );
538 539 540
                    } else {
                        panic!("conditional branch does not have a fallthrough target");
                    }
541
                }
542
                ASMBranchTarget::PotentiallyExcepting(ref target) => {
543 544
                    // may trigger exception and jump to target - similar as
                    // conditional branch
545 546 547 548 549
                    let target_n = self.blocks.get(target).unwrap().start_inst;

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

550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567
                    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
                    );
568 569 570 571 572 573 574 575 576 577

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

578 579 580 581 582 583
                        trace_if!(
                            TRACE_CFA,
                            "inst {}: SET SUCCS as PEI fallthrough target {}",
                            i,
                            next_inst
                        );
584 585 586
                    } else {
                        panic!("PEI does not have a fallthrough target");
                    }
587
                }
qinsoon's avatar
[wip]  
qinsoon committed
588
                ASMBranchTarget::Return => {
589 590
                    trace_if!(TRACE_CFA, "inst {}: is a return", i);
                    trace_if!(TRACE_CFA, "inst {}: has no successor", i);
qinsoon's avatar
[wip]  
qinsoon committed
591
                }
qinsoon's avatar
qinsoon committed
592 593
                ASMBranchTarget::None => {
                    // not branch nor cond branch, succ is next inst
594
                    trace_if!(TRACE_CFA, "inst {}: not a branch inst", i);
595
                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
596 597 598 599 600 601
                        trace_if!(
                            TRACE_CFA,
                            "inst {}: set SUCCS as next inst {}",
                            i,
                            next_inst
                        );
602
                        asm[i].succs.push(next_inst);
qinsoon's avatar
qinsoon committed
603 604 605 606
                    }
                }
            }
        }
607 608
    }

qinsoon's avatar
qinsoon committed
609
    /// finds the previous instruction (skip non-instruction assembly)
610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629
    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
630

qinsoon's avatar
qinsoon committed
631
    /// finds the next instruction (skip non-instruction assembly)
632 633 634 635 636 637 638 639 640 641 642
    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
643
            }
644 645

            None
qinsoon's avatar
qinsoon committed
646 647
        }
    }
qinsoon's avatar
qinsoon committed
648

qinsoon's avatar
qinsoon committed
649 650
    /// finds the last instruction that appears on or before the given index
    /// (skip non-instruction assembly)
651 652 653 654 655
    fn find_last_inst(i: usize, asm: &Vec<ASMInst>) -> Option<usize> {
        if i == 0 {
            None
        } else {
            let mut cur = i;
656
            loop {
657 658 659 660 661 662 663 664 665 666 667 668 669
                if !asm[cur].is_symbol {
                    return Some(cur);
                }

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

qinsoon's avatar
qinsoon committed
670 671 672
    fn add_frame_size_patchpoint(&mut self, patchpoint: ASMLocation) {
        self.frame_size_patchpoints.push(patchpoint);
    }
673 674
}

675
impl MachineCode for ASMCode {
676 677 678
    fn as_any(&self) -> &Any {
        self
    }
qinsoon's avatar
qinsoon committed
679 680

    /// returns the count of instructions in this machine code
681 682 683
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }
qinsoon's avatar
qinsoon committed
684 685

    /// is the specified index a move instruction?
686 687 688
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
qinsoon's avatar
qinsoon committed
689 690 691 692 693 694 695 696 697 698 699 700 701 702 703
            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
                }
704
            }
705
            None => false
706 707
        }
    }
qinsoon's avatar
qinsoon committed
708 709

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

qinsoon's avatar
qinsoon committed
714 715
    /// is the specified index a jump instruction? (unconditional jump)
    /// returns an Option for target block
716 717 718 719
    fn is_jmp(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
            Some(inst) if inst.code.starts_with("jmp") => {
720
                let split: Vec<&str> = inst.code.split(' ').collect();
721

722
                Some(demangle_name(String::from(split[1])))
723
            }
724
            _ => None
725 726 727
        }
    }

qinsoon's avatar
qinsoon committed
728
    /// is the specified index a label? returns an Option for the label
729 730 731 732
    fn is_label(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
            Some(inst) if inst.code.ends_with(':') => {
733
                let split: Vec<&str> = inst.code.split(':').collect();
734

735
                Some(demangle_name(String::from(split[0])))
736
            }
737
            _ => None
738 739
        }
    }
qinsoon's avatar
qinsoon committed
740

qinsoon's avatar
qinsoon committed
741 742
    /// is the specified index loading a spilled register?
    /// returns an Option for the register that is loaded into
qinsoon's avatar
qinsoon committed
743 744 745 746
    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()),
747
                _ => None
qinsoon's avatar
qinsoon committed
748 749 750 751 752 753
            }
        } else {
            None
        }
    }

qinsoon's avatar
qinsoon committed
754 755
    /// is the specified index storing a spilled register?
    /// returns an Option for the register that is stored
qinsoon's avatar
qinsoon committed
756 757 758 759
    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()),
760
                _ => None
qinsoon's avatar
qinsoon committed
761 762 763 764 765
            }
        } else {
            None
        }
    }
qinsoon's avatar
qinsoon committed
766 767

    /// gets successors of a specified index
qinsoon's avatar
qinsoon committed
768
    fn get_succs(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
769
        &self.code[index].succs
qinsoon's avatar
qinsoon committed
770
    }
qinsoon's avatar
qinsoon committed
771 772

    /// gets predecessors of a specified index
qinsoon's avatar
qinsoon committed
773
    fn get_preds(&self, index: usize) -> &Vec<usize> {
qinsoon's avatar
qinsoon committed
774
        &self.code[index].preds
qinsoon's avatar
qinsoon committed
775
    }
qinsoon's avatar
qinsoon committed
776 777

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

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

787 788
    /// replace a temp with a machine register (to_reg must be a machine
    /// register)
789
    fn replace_reg(&mut self, from: MuID, to: MuID) {
qinsoon's avatar
qinsoon committed
790
        // replace defines
qinsoon's avatar
qinsoon committed
791 792
        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
793 794 795

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

799 800 801 802
            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
803
                to_reg_string.len()
804
            );
805
        }
806

qinsoon's avatar
qinsoon committed
807
        // replace uses
qinsoon's avatar
qinsoon committed
808 809
        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];
qinsoon's avatar
qinsoon committed
810 811 812

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

816 817 818 819
            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
820
                to_reg_string.len()
821
            );
822 823
        }
    }
824

qinsoon's avatar
qinsoon committed
825
    /// replace a temp that is defined in the inst with another temp
826 827 828 829 830 831
    fn replace_define_tmp_for_inst(
        &mut self,
        from: MuID,
        to: MuID,
        inst: usize
    ) {
832
        let to_reg_string: MuName = REG_PLACEHOLDER.clone();
833

qinsoon's avatar
qinsoon committed
834 835 836 837 838 839
        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() {
840 841 842 843
                string_utils::replace(
                    &mut asm.code,
                    loc.index,
                    &to_reg_string,
844
                    to_reg_string.len()
845
                );
846 847
            }

qinsoon's avatar
qinsoon committed
848 849
            // remove old key, insert new one
            asm.defines.remove(&from);
850
            asm.defines.insert(to, define_locs);
851
        }
852 853
    }

qinsoon's avatar
qinsoon committed
854
    /// replace a temp that is used in the inst with another temp
855
    fn replace_use_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
856
        let to_reg_string: MuName = REG_PLACEHOLDER.clone();
857 858

        let asm = &mut self.code[inst];
qinsoon's avatar
qinsoon committed
859 860 861 862 863 864

        // 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() {
865 866 867 868
                string_utils::replace(
                    &mut asm.code,
                    loc.index,
                    &to_reg_string,
869
                    to_reg_string.len()
870
                );
871 872
            }

qinsoon's avatar
qinsoon committed
873 874
            // remove old key, insert new one
            asm.uses.remove(&from);
875
            asm.uses.insert(to, use_locs);
876 877
        }
    }
qinsoon's avatar
qinsoon committed
878

879
    /// replace destination for a jump instruction
880 881 882 883 884 885 886
    fn replace_branch_dest(
        &mut self,
        inst: usize,
        old_succ: usize,
        new_dest: &str,
        succ: MuID
    ) {
887 888 889
        {
            let asm = &mut self.code[inst];

890 891 892 893
            asm.code = format!(
                "jmp {}",
                symbol(&mangle_name(Arc::new(new_dest.to_string())))
            );
894
            asm.succs.retain(|&x| x != old_succ);
895 896 897 898
            asm.succs.push(succ);
        }
        {
            let asm = &mut self.code[succ];
899

900 901 902 903
            if !asm.preds.contains(&inst) {
                asm.preds.push(inst);
            }
        }
904 905
    }

qinsoon's avatar
qinsoon committed
906
    /// set an instruction as nop
907
    fn set_inst_nop(&mut self, index: usize) {
908
        self.code[index].code.clear();
909
    }
qinsoon's avatar
qinsoon committed
910

qinsoon's avatar
qinsoon committed
911 912 913 914 915 916 917 918 919 920
    /// is the specified index is a nop?
    fn is_nop(&self, index: usize) -> bool {
        let ref inst = self.code[index];
        if inst.code == "" || inst.code == "nop" {
            true
        } else {
            false
        }
    }

qinsoon's avatar
qinsoon committed
921
    /// remove unnecessary push/pop if the callee saved register is not used
922 923 924 925 926 927
    /// returns what registers push/pop have been deleted, and the number of
    /// callee saved registers that weren't deleted
    fn remove_unnecessary_callee_saved(
        &mut self,
        used_callee_saved: Vec<MuID>
    ) -> HashSet<MuID> {
qinsoon's avatar
qinsoon committed
928 929 930
        // we always save rbp
        let rbp = x86_64::RBP.extract_ssa_id().unwrap();

931
        let find_op_other_than_rbp = |inst: &ASMInst| -> MuID {
qinsoon's avatar
qinsoon committed
932
            for id in inst.defines.keys() {
933 934
                if *id != rbp {
                    return *id;
qinsoon's avatar
qinsoon committed
935 936 937
                }
            }
            for id in inst.uses.keys() {
938 939
                if *id != rbp {
                    return *id;
qinsoon's avatar
qinsoon committed
940 941
                }
            }
942
            panic!("Expected to find a used register other than the rbp");
qinsoon's avatar
qinsoon committed
943 944 945
        };

        let mut inst_to_remove = vec![];
946
        let mut regs_to_remove = HashSet::new();
qinsoon's avatar
qinsoon committed
947 948 949

        for i in 0..self.number_of_insts() {
            let ref inst = self.code[i];
950 951 952 953
            match inst.spill_info {
                Some(SpillMemInfo::CalleeSaved) => {
                    let reg = find_op_other_than_rbp(inst);
                    if !used_callee_saved.contains(&reg) {
954
                        trace!(
qinsoon's avatar
qinsoon committed
955 956
                            "removing instruction {:?} for save/restore \
                             unnecessary callee saved regs",
957 958
                            inst
                        );
959 960
                        regs_to_remove.insert(reg);
                        inst_to_remove.push(i);
qinsoon's avatar
qinsoon committed
961 962
                    }
                }
963
                _ => {}
qinsoon's avatar
qinsoon committed
964 965 966 967 968 969 970
            }
        }

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

971
        regs_to_remove
qinsoon's avatar
qinsoon committed
972
    }
qinsoon's avatar
qinsoon committed
973

qinsoon's avatar
qinsoon committed
974
    /// patch frame size
975
    fn patch_frame_size(&mut self, size: usize) {
qinsoon's avatar
qinsoon committed
976
        let size = size.to_string();
qinsoon's avatar
qinsoon committed
977
        assert!(size.len() <= FRAME_SIZE_PLACEHOLDER_LEN);
qinsoon's avatar
qinsoon committed
978 979 980 981 982 983

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

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

989
        for inst in self.code.iter() {
990 991 992 993
            if !inst.is_symbol {
                ret.append(&mut "\t".to_string().into_bytes());
            }

994 995 996
            ret.append(&mut inst.code.clone().into_bytes());
            ret.append(&mut "\n".to_string().into_bytes());
        }
997

998 999
        ret
    }
1000

qinsoon's avatar
qinsoon committed
1001
    /// emit the machine instruction at the given index as a byte array
1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014
    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
1015 1016

    /// print the whole machine code by trace level log
1017 1018 1019
    fn trace_mc(&self) {
        trace!("");
        trace!("code for {}: \n", self.name);
1020

1021 1022
        let n_insts = self.code.len();
        for i in 0..n_insts {
1023
            self.trace_inst(i);
1024
        }
1025 1026

        trace!("")
1027
    }
qinsoon's avatar
qinsoon committed
1028 1029

    /// print an inst for the given index
1030
    fn trace_inst(&self, i: usize) {
1031 1032 1033
        trace!(
            "#{}\t{:60}\t\tdefine: {:?}\tuses: {:?}\tpred: {:?}\tsucc: {:?}",
            i,
1034
            demangle_text(&self.code[i].code),
1035 1036 1037 1038 1039
            self.get_inst_reg_defines(i),
            self.get_inst_reg_uses(i),
            self.code[i].preds,
            self.code[i].succs
        );
1040
    }
qinsoon's avatar
qinsoon committed
1041 1042

    /// gets block livein
1043
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
1044
        match self.blocks.get(&block.to_string()) {
qinsoon's avatar
qinsoon committed
1045
            Some(ref block) => Some(&block.livein),
1046
            None => None
qinsoon's avatar
qinsoon committed
1047
        }
1048
    }
qinsoon's avatar
qinsoon committed
1049 1050

    /// gets block liveout
1051
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
1052
        match self.blocks.get(&block.to_string()) {
qinsoon's avatar
qinsoon committed
1053
            Some(ref block) => Some(&block.liveout),
1054
            None => None
qinsoon's avatar
qinsoon committed
1055
        }
1056
    }
qinsoon's avatar
qinsoon committed
1057 1058

    /// sets block livein
1059
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
1060
        let block = self.blocks.get_mut(&block.to_string()).unwrap();
qinsoon's avatar
qinsoon committed
1061
        block.livein = set;
1062
    }
qinsoon's avatar
qinsoon committed
1063 1064

    /// sets block liveout
1065
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
1066
        let block = self.blocks.get_mut(&block.to_string()).unwrap();
qinsoon's avatar
qinsoon committed
1067
        block.liveout = set;
1068
    }
qinsoon's avatar
qinsoon committed
1069 1070

    /// gets all the blocks
qinsoon's avatar
qinsoon committed
1071 1072
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
1073
    }
1074

qinsoon's avatar
qinsoon committed
1075
    /// gets the entry block
1076 1077 1078
    fn get_entry_block(&self) -> MuName {
        self.entry.clone()
    }
qinsoon's avatar
qinsoon committed
1079

1080 1081
    /// gets the range of a given block, returns [start_inst, end_inst)
    /// (end_inst not included)
1082
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
1083
        match self.blocks.get(&block.to_string()) {
qinsoon's avatar
qinsoon committed
1084
            Some(ref block) => Some(block.start_inst..block.end_inst),
1085
            None => None
1086 1087
        }
    }
1088

qinsoon's avatar
qinsoon committed
1089
    /// gets the block for a given index, returns an Option for the block
1090 1091 1092 1093 1094 1095 1096 1097 1098
    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
    }

1099 1100
    /// gets the next instruction of a specified index (labels are not
    /// instructions)
1101 1102 1103 1104
    fn get_next_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_next_inst(index, &self.code)
    }

1105 1106
    /// gets the previous instruction of a specified index (labels are not
    /// instructions)
1107 1108 1109
    fn get_last_inst(&self, index: usize) -> Option<usize> {
        ASMCode::find_last_inst(index, &self.code)
    }
1110 1111
}

qinsoon's avatar
qinsoon committed
1112
impl ASMInst {
qinsoon's avatar
qinsoon committed
1113
    /// creates a symbolic assembly code (not an instruction)
qinsoon's avatar
qinsoon committed
1114 1115
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
1116
            code: line,
1117 1118
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
qinsoon's avatar
qinsoon committed
1119
            is_mem_op_used: false,
1120
            is_symbol: true,
qinsoon's avatar
qinsoon committed
1121 1122
            preds: vec![],
            succs: vec![],
1123 1124
            branch: ASMBranchTarget::None,

1125
            spill_info: None
1126 1127
        }
    }
qinsoon's avatar
qinsoon committed
1128 1129

    /// creates an instruction
qinsoon's avatar
qinsoon committed
1130 1131
    fn inst(
        inst: String,
1132 1133
        defines: LinkedHashMap<MuID, Vec<ASMLocation>>,
        uses: LinkedHashMap<MuID, Vec<ASMLocation>>,
qinsoon's avatar
qinsoon committed
1134
        is_mem_op_used: bool,
1135
        target: ASMBranchTarget,
1136
        spill_info: Option<SpillMemInfo>
1137
    ) -> ASMInst {
qinsoon's avatar
qinsoon committed
1138
        ASMInst {
1139 1140
            code: inst,
            defines: defines,
qinsoon's avatar
qinsoon committed
1141
            uses: uses,