asm_backend.rs

// Copyright 2017 The Australian National University
//
// 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
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// 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.

#![allow(unused_variables)]

use compiler::backend::AOT_EMIT_CONTEXT_FILE;
use compiler::backend::AOT_EMIT_SYM_TABLE_FILE;
use compiler::backend::RegGroup;
use utils::ByteSize;
use utils::Address;
use utils::POINTER_SIZE;
use compiler::backend::x86_64;
use compiler::backend::x86_64::CodeGenerator;
use compiler::backend::{Reg, Mem};
use compiler::backend::x86_64::check_op_len;
use compiler::machine_code::MachineCode;
use vm::VM;
use runtime::ValueLocation;

use utils::vec_utils;
use utils::string_utils;
use utils::LinkedHashMap;

use ast::ptr::P;
use ast::ir::*;
use ast::types;

use std::str;
use std::usize;
use std::slice::Iter;
use std::ops;
use std::collections::HashSet;
use std::sync::RwLock;
use std::any::Any;

/// 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.
struct ASMCode {
    /// function name for the code
    name: MuName,
    /// a list of all the assembly instructions
    code: Vec<ASMInst>,
    /// entry block name
    entry: MuName,
    /// all the blocks
    blocks: LinkedHashMap<MuName, ASMBlock>,
    /// 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
    frame_size_patchpoints: Vec<ASMLocation>
}

unsafe impl Send for ASMCode {}
unsafe impl Sync for ASMCode {}

/// 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
    branch: ASMBranchTarget
}

/// 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
    oplen: usize
}

/// 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
    liveout: Vec<MuID>
}

/// 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
    Return
}

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

impl ASMCode {
    /// returns a vector of ASMLocation for all the uses of the given reg/temp
    fn get_use_locations(&self, reg: MuID) -> Vec<ASMLocation> {
        let mut ret = vec![];

        for inst in self.code.iter() {
            match inst.uses.get(&reg) {
                Some(ref locs) => {
                    ret.append(&mut locs.to_vec());
                }
                None => {}
            }
        }

        ret
    }

    /// returns a vector of ASMLocation for all the defines of the given reg/temp
    fn get_define_locations(&self, reg: MuID) -> Vec<ASMLocation> {
        let mut ret = vec![];

        for inst in self.code.iter() {
            match inst.defines.get(&reg) {
                Some(ref locs) => {
                    ret.append(&mut locs.to_vec());
                }
                None => {}
            }
        }

        ret
    }

    /// is the given instruction the starting instruction of a block?
    fn is_block_start(&self, inst: usize) -> bool {
        for block in self.blocks.values() {
            if block.start_inst == inst {
                return true;
            }
        }
        false
    }

    /// is the given instruction the ending instruction of a block?
    fn is_last_inst_in_block(&self, inst: usize) -> bool {
        for block in self.blocks.values() {
            if block.end_inst == inst + 1 {
                return true;
            }
        }
        false
    }

    /// finds block for a given instruction and returns the block
    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)
    }

    /// finds block that starts with the given instruction
    /// returns None if we cannot find such block
    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
    }

    /// 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.
    fn rewrite_insert(
        &self,
        insert_before: LinkedHashMap<usize, Vec<Box<ASMCode>>>,
        insert_after: LinkedHashMap<usize, Vec<Box<ASMCode>>>
    ) -> Box<ASMCode> {
        trace!("insert spilling code");
        let mut ret = ASMCode {
            name: self.name.clone(),
            entry: self.entry.clone(),
            code: vec![],
            blocks: linked_hashmap!{},
            frame_size_patchpoints: vec![]
        };

        // how many instructions have been inserted
        let mut inst_offset = 0;
        let mut cur_block_start = usize::MAX;

        // inst N in old machine code is N' in new machine code
        // this map stores the relationship
        let mut location_map: LinkedHashMap<usize, usize> = LinkedHashMap::new();

        // iterate through old machine code
        for i in 0..self.number_of_insts() {
            trace!("Inst{}", i);

            if self.is_block_start(i) {
                cur_block_start = i + inst_offset;
                trace!("  block start is shifted to {}", cur_block_start);
            }

            // 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();
                    trace!("  inserted {} insts before", insert.number_of_insts());
                }
            }

            // copy this instruction
            let mut inst = self.code[i].clone();

            // old ith inst is now the (i + inst_offset)th instruction
            location_map.insert(i, i + inst_offset);
            trace!("  Inst{} is now Inst{}", i, i + inst_offset);

            // 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;
                }
            }
            // 2. we need to delete existing preds/succs - CFA is required later
            inst.preds.clear();
            inst.succs.clear();
            // 3. add the inst
            ret.code.push(inst);


            // insert code after this instruction
            if insert_after.contains_key(&i) {
                for insert in insert_after.get(&i).unwrap() {
                    ret.append_code_sequence_all(insert);
                    inst_offset += insert.number_of_insts();
                    trace!("  inserted {} insts after", insert.number_of_insts());
                }
            }

            // if we finish a block
            if self.is_last_inst_in_block(i) {
                let cur_block_end = i + 1 + inst_offset;

                // copy the block
                let (name, block) = self.get_block_by_inst(i);

                let new_block = ASMBlock {
                    start_inst: cur_block_start,
                    end_inst: cur_block_end,

                    livein: vec![],
                    liveout: vec![]
                };

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

                cur_block_start = usize::MAX;

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

        // fix patchpoints
        for patchpoint in self.frame_size_patchpoints.iter() {
            let new_patchpoint = ASMLocation {
                line: *location_map.get(&patchpoint.line).unwrap(),
                index: patchpoint.index,
                len: patchpoint.len,
                oplen: patchpoint.oplen
            };

            ret.frame_size_patchpoints.push(new_patchpoint);
        }

        ret.control_flow_analysis();

        Box::new(ret)
    }

    /// 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) {
        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);
        }
    }

    /// appends assembly sequence at the end of current code
    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)
    }

    /// control flow analysis on current code
    /// calculating branch targets, preds/succs for each instruction
    fn control_flow_analysis(&mut self) {
        const TRACE_CFA: bool = true;

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

        for i in 0..n_insts {
            trace_if!(TRACE_CFA, "---inst {}---", i);

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

            // 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
            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);
                                    trace_if!(
                                        TRACE_CFA,
                                        "inst {}: set PREDS as previous inst - fallthrough {}",
                                        i,
                                        last_inst
                                    );
                                }
                            }
                            // otherwise do nothing
                            _ => {}
                        }
                    }
                    None => {}
                }
            }

            // determine successor
            // make a clone so that we are not borrowing anything
            let branch = asm[i].branch.clone();
            match branch {
                ASMBranchTarget::Unconditional(ref target) => {
                    // branch-to target
                    let target_n = self.blocks.get(target).unwrap().start_inst;

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

                    // target's pred is cur
                    asm[target_n].preds.push(i);

                    trace_if!(TRACE_CFA, "inst {}: is a branch to {}", i, target);
                    trace_if!(TRACE_CFA, "inst {}: branch target index is {}", i, target_n);
                    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
                    );
                }
                ASMBranchTarget::Conditional(ref target) => {
                    // branch-to target
                    let target_n = self.blocks.get(target).unwrap().start_inst;

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

                    trace_if!(TRACE_CFA, "inst {}: is a cond branch to {}", i, target);
                    trace_if!(TRACE_CFA, "inst {}: branch target index is {}", i, target_n);
                    trace_if!(
                        TRACE_CFA,
                        "inst {}: set SUCCS as branch target {}",
                        i,
                        target_n
                    );

                    // target's pred is cur
                    asm[target_n].preds.push(i);
                    trace_if!(TRACE_CFA, "inst {}: set PREDS as {}", target_n, 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);

                        trace_if!(
                            TRACE_CFA,
                            "inst {}: SET SUCCS as c-branch fallthrough target {}",
                            i,
                            next_inst
                        );
                    } else {
                        panic!("conditional branch does not have a fallthrough target");
                    }
                }
                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);

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

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

                        trace_if!(
                            TRACE_CFA,
                            "inst {}: SET SUCCS as PEI fallthrough target {}",
                            i,
                            next_inst
                        );
                    } else {
                        panic!("PEI does not have a fallthrough target");
                    }
                }
                ASMBranchTarget::Return => {
                    trace_if!(TRACE_CFA, "inst {}: is a return", i);
                    trace_if!(TRACE_CFA, "inst {}: has no successor", i);
                }
                ASMBranchTarget::None => {
                    // not branch nor cond branch, succ is next inst
                    trace_if!(TRACE_CFA, "inst {}: not a branch inst", i);
                    if let Some(next_inst) = ASMCode::find_next_inst(i, asm) {
                        trace_if!(
                            TRACE_CFA,
                            "inst {}: set SUCCS as next inst {}",
                            i,
                            next_inst
                        );
                        asm[i].succs.push(next_inst);
                    }
                }
            }
        }
    }

    /// finds the previous instruction (skip non-instruction assembly)
    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
        }
    }

    /// finds the next instruction (skip non-instruction assembly)
    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;
            }

            None
        }
    }

    /// finds the last instruction that appears on or before the given index
    /// (skip non-instruction assembly)
    fn find_last_inst(i: usize, asm: &Vec<ASMInst>) -> Option<usize> {
        if i == 0 {
            None
        } else {
            let mut cur = i;
            loop {
                if !asm[cur].is_symbol {
                    return Some(cur);
                }

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

    fn add_frame_size_patchpoint(&mut self, patchpoint: ASMLocation) {
        self.frame_size_patchpoints.push(patchpoint);
    }
}

impl MachineCode for ASMCode {
    fn as_any(&self) -> &Any {
        self
    }

    /// returns the count of instructions in this machine code
    fn number_of_insts(&self) -> usize {
        self.code.len()
    }

    /// is the specified index a move instruction?
    fn is_move(&self, index: usize) -> bool {
        let inst = self.code.get(index);
        match inst {
            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
                }
            }
            None => false
        }
    }

    /// is the specified index using memory operands?
    fn is_using_mem_op(&self, index: usize) -> bool {
        self.code[index].is_mem_op_used
    }

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

                Some(demangle_name(String::from(split[1])))
            }
            _ => None
        }
    }

    /// is the specified index a label? returns an Option for the label
    fn is_label(&self, index: usize) -> Option<MuName> {
        let inst = self.code.get(index);
        match inst {
            Some(inst) if inst.code.ends_with(':') => {
                let split: Vec<&str> = inst.code.split(':').collect();

                Some(demangle_name(String::from(split[0])))
            }
            _ => None
        }
    }

    /// is the specified index loading a spilled register?
    /// returns an Option for the register that is loaded into
    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()),
                _ => None
            }
        } else {
            None
        }
    }

    /// is the specified index storing a spilled register?
    /// returns an Option for the register that is stored
    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()),
                _ => None
            }
        } else {
            None
        }
    }

    /// gets successors of a specified index
    fn get_succs(&self, index: usize) -> &Vec<usize> {
        &self.code[index].succs
    }

    /// gets predecessors of a specified index
    fn get_preds(&self, index: usize) -> &Vec<usize> {
        &self.code[index].preds
    }

    /// gets the register uses of a specified index
    fn get_inst_reg_uses(&self, index: usize) -> Vec<MuID> {
        self.code[index].uses.keys().map(|x| *x).collect()
    }

    /// gets the register defines of a specified index
    fn get_inst_reg_defines(&self, index: usize) -> Vec<MuID> {
        self.code[index].defines.keys().map(|x| *x).collect()
    }

    /// replace a temp with a machine register (to_reg must be a machine register)
    fn replace_reg(&mut self, from: MuID, to: MuID) {
        // replace defines
        for loc in self.get_define_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];

            // pick the right reg based on length
            let to_reg = x86_64::get_alias_for_length(to, loc.oplen);
            let to_reg_tag = to_reg.name();
            let to_reg_string = "%".to_string() + &to_reg_tag;

            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
                to_reg_string.len()
            );
        }

        // replace uses
        for loc in self.get_use_locations(from) {
            let ref mut inst_to_patch = self.code[loc.line];

            // pick the right reg based on length
            let to_reg = x86_64::get_alias_for_length(to, loc.oplen);
            let to_reg_tag = to_reg.name();
            let to_reg_string = "%".to_string() + &to_reg_tag;

            string_utils::replace(
                &mut inst_to_patch.code,
                loc.index,
                &to_reg_string,
                to_reg_string.len()
            );
        }
    }

    /// replace a temp that is defined in the inst with another temp
    fn replace_define_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
        let to_reg_string: MuName = REG_PLACEHOLDER.clone();

        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() {
                string_utils::replace(
                    &mut asm.code,
                    loc.index,
                    &to_reg_string,
                    to_reg_string.len()
                );
            }

            // remove old key, insert new one
            asm.defines.remove(&from);
            asm.defines.insert(to, define_locs);
        }
    }

    /// replace a temp that is used in the inst with another temp
    fn replace_use_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) {
        let to_reg_string: MuName = REG_PLACEHOLDER.clone();

        let asm = &mut self.code[inst];

        // 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() {
                string_utils::replace(
                    &mut asm.code,
                    loc.index,
                    &to_reg_string,
                    to_reg_string.len()
                );
            }

            // remove old key, insert new one
            asm.uses.remove(&from);
            asm.uses.insert(to, use_locs);
        }
    }

    /// replace destination for a jump instruction
    fn replace_branch_dest(&mut self, inst: usize, new_dest: &str, succ: MuID) {
        {
            let asm = &mut self.code[inst];

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

            if !asm.preds.contains(&inst) {
                asm.preds.push(inst);
            }
        }
    }

    /// set an instruction as nop
    fn set_inst_nop(&mut self, index: usize) {
        self.code[index].code.clear();
    }

    /// 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
    fn remove_unnecessary_callee_saved(&mut self, used_callee_saved: Vec<MuID>) -> HashSet<MuID> {
        // we always save rbp
        let rbp = x86_64::RBP.extract_ssa_id().unwrap();

        let find_op_other_than_rbp = |inst: &ASMInst| -> MuID {
            for id in inst.defines.keys() {
                if *id != rbp {
                    return *id;
                }
            }
            for id in inst.uses.keys() {
                if *id != rbp {
                    return *id;
                }
            }
            panic!("Expected to find a used register other than the rbp");
        };

        let mut inst_to_remove = vec![];
        let mut regs_to_remove = HashSet::new();

        for i in 0..self.number_of_insts() {
            let ref inst = self.code[i];
            match inst.spill_info {
                Some(SpillMemInfo::CalleeSaved) => {
                    let reg = find_op_other_than_rbp(inst);
                    if !used_callee_saved.contains(&reg) {
                        trace!(
                            "removing instruction {:?} for save/restore \
                             unnecessary callee saved regs",
                            inst
                        );
                        regs_to_remove.insert(reg);
                        inst_to_remove.push(i);
                    }
                }
                _ => {}
            }
        }

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

        regs_to_remove
    }

    /// patch frame size
    fn patch_frame_size(&mut self, size: usize) {
        let size = size.to_string();
        assert!(size.len() <= FRAME_SIZE_PLACEHOLDER_LEN);

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

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

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

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

        ret
    }

    /// emit the machine instruction at the given index as a byte array
    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
    }

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

        let n_insts = self.code.len();
        for i in 0..n_insts {
            self.trace_inst(i);
        }

        trace!("")
    }

    /// print an inst for the given index
    fn trace_inst(&self, i: usize) {
        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
        );
    }

    /// gets block livein
    fn get_ir_block_livein(&self, block: &str) -> Option<&Vec<MuID>> {
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.livein),
            None => None
        }
    }

    /// gets block liveout
    fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec<MuID>> {
        match self.blocks.get(block) {
            Some(ref block) => Some(&block.liveout),
            None => None
        }
    }

    /// sets block livein
    fn set_ir_block_livein(&mut self, block: &str, set: Vec<MuID>) {
        let block = self.blocks.get_mut(block).unwrap();
        block.livein = set;
    }

    /// sets block liveout
    fn set_ir_block_liveout(&mut self, block: &str, set: Vec<MuID>) {
        let block = self.blocks.get_mut(block).unwrap();
        block.liveout = set;
    }

    /// gets all the blocks
    fn get_all_blocks(&self) -> Vec<MuName> {
        self.blocks.keys().map(|x| x.clone()).collect()
    }

    /// gets the entry block
    fn get_entry_block(&self) -> MuName {
        self.entry.clone()
    }

    /// gets the range of a given block, returns [start_inst, end_inst) (end_inst not included)
    fn get_block_range(&self, block: &str) -> Option<ops::Range<usize>> {
        match self.blocks.get(block) {
            Some(ref block) => Some(block.start_inst..block.end_inst),
            None => None
        }
    }

    /// gets the block for a given index, returns an Option for the block
    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
    }

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

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

impl ASMInst {
    /// creates a symbolic assembly code (not an instruction)
    fn symbolic(line: String) -> ASMInst {
        ASMInst {
            code: line,
            defines: LinkedHashMap::new(),
            uses: LinkedHashMap::new(),
            is_mem_op_used: false,
            is_symbol: true,
            preds: vec![],
            succs: vec![],
            branch: ASMBranchTarget::None,

            spill_info: None
        }
    }

    /// creates an instruction
    fn inst(
        inst: String,