#![allow(unused_variables)] use compiler::backend; use compiler::backend::AOT_EMIT_CONTEXT_FILE; use compiler::backend::AOT_EMIT_DIR; use compiler::backend::RegGroup; use utils::ByteSize; use compiler::backend::x86_64; use compiler::backend::x86_64::CodeGenerator; use compiler::machine_code::MachineCode; use vm::VM; use runtime::ValueLocation; use utils::vec_utils; use utils::string_utils; use ast::ptr::P; use ast::ir::*; use std::collections::HashMap; use std::str; use std::usize; use std::slice::Iter; use std::ops; struct ASMCode { name: MuName, code: Vec, blocks: HashMap } unsafe impl Send for ASMCode {} unsafe impl Sync for ASMCode {} impl ASMCode { fn get_use_locations(&self, reg: MuID) -> Vec { let mut ret = vec![]; for inst in self.code.iter() { match inst.uses.get(®) { Some(ref locs) => { ret.append(&mut locs.to_vec()); }, None => {} } } ret } fn get_define_locations(&self, reg: MuID) -> Vec { let mut ret = vec![]; for inst in self.code.iter() { match inst.defines.get(®) { Some(ref locs) => { ret.append(&mut locs.to_vec()); }, None => {} } } ret } fn is_block_start(&self, inst: usize) -> bool { for block in self.blocks.values() { if block.start_inst == inst { return true; } } false } fn is_block_end(&self, inst: usize) -> bool { for block in self.blocks.values() { if block.end_inst == inst + 1 { return true; } } false } 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) } 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 } fn rewrite_insert( &self, insert_before: HashMap>>, insert_after: HashMap>>) -> Box { let mut ret = ASMCode { name: self.name.clone(), code: vec![], blocks: hashmap!{}, }; // iterate through old machine code let mut inst_offset = 0; // how many instructions has been inserted let mut cur_block_start = usize::MAX; for i in 0..self.number_of_insts() { if self.is_block_start(i) { cur_block_start = i + inst_offset; } // 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(); } } // copy this instruction let mut inst = self.code[i].clone(); // 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(); } } if self.is_block_end(i) { let cur_block_end = i + inst_offset; // copy the block let (name, block) = self.get_block_by_inst(i); let mut new_block = block.clone(); new_block.start_inst = cur_block_start; cur_block_start = usize::MAX; new_block.end_inst = cur_block_end; // add to the new code ret.blocks.insert(name.clone(), new_block); } } ret.control_flow_analysis(); Box::new(ret) } fn append_code_sequence( &mut self, another: &Box, 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); } } fn append_code_sequence_all(&mut self, another: &Box) { let n_insts = another.number_of_insts(); self.append_code_sequence(another, 0, n_insts) } fn control_flow_analysis(&mut self) { const TRACE_CFA : bool = false; // control flow analysis let n_insts = self.number_of_insts(); let ref blocks = self.blocks; let ref mut asm = self.code; let block_start = { let mut ret = vec![]; for block in blocks.values() { ret.push(block.start_inst); } ret }; for i in 0..n_insts { // determine predecessor - if cur is not block start, its predecessor is previous insts let is_block_start = block_start.contains(&i); if !is_block_start { if i > 0 { if TRACE_CFA { trace!("inst {}: not a block start", i); trace!("inst {}: set PREDS as previous inst {}", i, i - 1); } asm[i].preds.push(i - 1); } } else { // if cur is a branch target, we already set its predecessor // if cur is a fall-through block, we set it in a sanity check pass } // determine successor 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); if TRACE_CFA { trace!("inst {}: is a branch to {}", i, target); trace!("inst {}: branch target index is {}", i, target_n); trace!("inst {}: set SUCCS as branch target {}", i, target_n); trace!("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 and next inst asm[i].succs.push(target_n); if TRACE_CFA { trace!("inst {}: is a cond branch to {}", i, target); trace!("inst {}: branch target index is {}", i, target_n); trace!("inst {}: set SUCCS as branch target {}", i, target_n); } if i < n_insts - 1 { if TRACE_CFA { trace!("inst {}: set SUCCS as next inst", i + 1); } asm[i].succs.push(i + 1); } // target's pred is cur asm[target_n].preds.push(i); if TRACE_CFA { trace!("inst {}: set PREDS as {}", target_n, i); } }, ASMBranchTarget::None => { // not branch nor cond branch, succ is next inst if TRACE_CFA { trace!("inst {}: not a branch inst", i); } if i < n_insts - 1 { if TRACE_CFA { trace!("inst {}: set SUCCS as next inst {}", i, i + 1); } asm[i].succs.push(i + 1); } } } } // a sanity check for fallthrough blocks for i in 0..n_insts { if i != 0 && asm[i].preds.len() == 0 { asm[i].preds.push(i - 1); } } } } use std::any::Any; impl MachineCode for ASMCode { fn as_any(&self) -> &Any { self } fn number_of_insts(&self) -> usize { self.code.len() } fn is_move(&self, index: usize) -> bool { let inst = self.code.get(index); match inst { Some(inst) => inst.code.starts_with("mov"), None => false } } fn is_using_mem_op(&self, index: usize) -> bool { self.code[index].is_mem_op_used } fn get_succs(&self, index: usize) -> &Vec { &self.code[index].succs } fn get_preds(&self, index: usize) -> &Vec { &self.code[index].preds } fn get_inst_reg_uses(&self, index: usize) -> Vec { self.code[index].uses.keys().map(|x| *x).collect() } fn get_inst_reg_defines(&self, index: usize) -> Vec { self.code[index].defines.keys().map(|x| *x).collect() } fn replace_reg(&mut self, from: MuID, to: MuID) { let to_reg_tag : MuName = match backend::all_regs().get(&to) { Some(reg) => reg.name().unwrap(), None => panic!("expecting a machine register, but we are required to replace to {}", to) }; let to_reg_string = "%".to_string() + &to_reg_tag; for loc in self.get_define_locations(from) { let ref mut inst_to_patch = self.code[loc.line]; for i in 0..loc.len { // FIXME: why loop here? string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len()); } } for loc in self.get_use_locations(from) { let ref mut inst_to_patch = self.code[loc.line]; for i in 0..loc.len { string_utils::replace(&mut inst_to_patch.code, loc.index, &to_reg_string, to_reg_string.len()); } } } fn replace_define_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) { let to_reg_string : MuName = match backend::all_regs().get(&to) { Some(ref machine_reg) => { let name = machine_reg.name().unwrap(); "%".to_string() + &name }, None => 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() { for i in 0..loc.len { 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); } } fn replace_use_tmp_for_inst(&mut self, from: MuID, to: MuID, inst: usize) { let to_reg_string : MuName = match backend::all_regs().get(&to) { Some(ref machine_reg) => { let name = machine_reg.name().unwrap(); "%".to_string() + &name }, None => 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() { for i in 0..loc.len { 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); } } fn set_inst_nop(&mut self, index: usize) { self.code.remove(index); self.code.insert(index, ASMInst::nop()); } fn remove_unnecessary_callee_saved(&mut self, used_callee_saved: Vec) -> Vec { // we always save rbp let rbp = x86_64::RBP.extract_ssa_id().unwrap(); // every push/pop will use/define rsp let rsp = x86_64::RSP.extract_ssa_id().unwrap(); let find_op_other_than_rsp = |inst: &ASMInst| -> Option { for id in inst.defines.keys() { if *id != rsp && *id != rbp { return Some(*id); } } for id in inst.uses.keys() { if *id != rsp && *id != rbp { return Some(*id); } } None }; let mut inst_to_remove = vec![]; let mut regs_to_remove = vec![]; for i in 0..self.number_of_insts() { let ref inst = self.code[i]; if inst.code.contains("push") || inst.code.contains("pop") { match find_op_other_than_rsp(inst) { Some(op) => { // if this push/pop instruction is about a callee saved register // and the register is not used, we set the instruction as nop if x86_64::is_callee_saved(op) && !used_callee_saved.contains(&op) { trace!("removing instruction {:?} for save/restore unnecessary callee saved regs", inst); regs_to_remove.push(op); inst_to_remove.push(i); } } None => {} } } } for i in inst_to_remove { self.set_inst_nop(i); } regs_to_remove } fn emit(&self) -> Vec { let mut ret = vec![]; for inst in self.code.iter() { ret.append(&mut inst.code.clone().into_bytes()); ret.append(&mut "\n".to_string().into_bytes()); } ret } 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!("") } fn trace_inst(&self, i: usize) { trace!("#{}\t{:30}\t\tdefine: {:?}\tuses: {:?}\tpred: {:?}\tsucc: {:?}", i, self.code[i].code, self.get_inst_reg_defines(i), self.get_inst_reg_uses(i), self.code[i].preds, self.code[i].succs); } fn get_ir_block_livein(&self, block: &str) -> Option<&Vec> { match self.blocks.get(block) { Some(ref block) => Some(&block.livein), None => None } } fn get_ir_block_liveout(&self, block: &str) -> Option<&Vec> { match self.blocks.get(block) { Some(ref block) => Some(&block.liveout), None => None } } fn set_ir_block_livein(&mut self, block: &str, set: Vec) { let block = self.blocks.get_mut(block).unwrap(); block.livein = set; } fn set_ir_block_liveout(&mut self, block: &str, set: Vec) { let block = self.blocks.get_mut(block).unwrap(); block.liveout = set; } fn get_all_blocks(&self) -> Vec { self.blocks.keys().map(|x| x.clone()).collect() } fn get_block_range(&self, block: &str) -> Option> { match self.blocks.get(block) { Some(ref block) => Some(block.start_inst..block.end_inst), None => None } } } #[derive(Clone, Debug)] enum ASMBranchTarget { None, Conditional(MuName), Unconditional(MuName) } #[derive(Clone, Debug)] struct ASMInst { code: String, defines: HashMap>, uses: HashMap>, is_mem_op_used: bool, preds: Vec, succs: Vec, branch: ASMBranchTarget } impl ASMInst { fn symbolic(line: String) -> ASMInst { ASMInst { code: line, defines: HashMap::new(), uses: HashMap::new(), is_mem_op_used: false, preds: vec![], succs: vec![], branch: ASMBranchTarget::None } } fn inst( inst: String, defines: HashMap>, uses: HashMap>, is_mem_op_used: bool, target: ASMBranchTarget ) -> ASMInst { ASMInst { code: inst, defines: defines, uses: uses, is_mem_op_used: is_mem_op_used, preds: vec![], succs: vec![], branch: target } } fn nop() -> ASMInst { ASMInst { code: "".to_string(), defines: HashMap::new(), uses: HashMap::new(), is_mem_op_used: false, preds: vec![], succs: vec![], branch: ASMBranchTarget::None } } } #[derive(Clone, Debug, PartialEq, Eq)] struct ASMLocation { line: usize, index: usize, len: usize } impl ASMLocation { fn new(line: usize, index: usize, len: usize) -> ASMLocation { ASMLocation{ line: line, index: index, len: len } } } #[derive(Clone, Debug)] /// [start_inst, end_inst) struct ASMBlock { start_inst: usize, end_inst: usize, livein: Vec, liveout: Vec } impl ASMBlock { fn new() -> ASMBlock { ASMBlock { start_inst: usize::MAX, end_inst: usize::MAX, livein: vec![], liveout: vec![] } } } pub struct ASMCodeGen { cur: Option> } const REG_PLACEHOLDER_LEN : usize = 5; lazy_static! { pub static ref REG_PLACEHOLDER : String = { let blank_spaces = [' ' as u8; REG_PLACEHOLDER_LEN]; format!("%{}", str::from_utf8(&blank_spaces).unwrap()) }; } impl ASMCodeGen { pub fn new() -> ASMCodeGen { ASMCodeGen { cur: None } } fn cur(&self) -> &ASMCode { self.cur.as_ref().unwrap() } fn cur_mut(&mut self) -> &mut ASMCode { self.cur.as_mut().unwrap() } fn line(&self) -> usize { self.cur().code.len() } fn add_asm_label(&mut self, code: String) { let l = self.line(); self.cur_mut().code.push(ASMInst::symbolic(code)); } fn add_asm_block_label(&mut self, code: String, block_name: MuName) { let l = self.line(); self.cur_mut().code.push(ASMInst::symbolic(code)); } fn add_asm_symbolic(&mut self, code: String){ self.cur_mut().code.push(ASMInst::symbolic(code)); } fn prepare_machine_regs(&self, regs: Iter>) -> Vec { regs.map(|x| self.prepare_machine_reg(x)).collect() } fn add_asm_call(&mut self, code: String) { // a call instruction will use all the argument registers let mut uses : HashMap> = HashMap::new(); for reg in x86_64::ARGUMENT_GPRs.iter() { uses.insert(reg.id(), vec![]); } for reg in x86_64::ARGUMENT_FPRs.iter() { uses.insert(reg.id(), vec![]); } // defines: return registers let mut defines : HashMap> = HashMap::new(); for reg in x86_64::RETURN_GPRs.iter() { defines.insert(reg.id(), vec![]); } for reg in x86_64::RETURN_FPRs.iter() { defines.insert(reg.id(), vec![]); } for reg in x86_64::CALLER_SAVED_GPRs.iter() { if !defines.contains_key(®.id()) { defines.insert(reg.id(), vec![]); } } for reg in x86_64::CALLER_SAVED_FPRs.iter() { if !defines.contains_key(®.id()) { defines.insert(reg.id(), vec![]); } } self.add_asm_inst(code, defines, uses, false); } fn add_asm_ret(&mut self, code: String) { let uses : HashMap> = { let mut ret = HashMap::new(); for reg in x86_64::RETURN_GPRs.iter() { ret.insert(reg.id(), vec![]); } for reg in x86_64::RETURN_FPRs.iter() { ret.insert(reg.id(), vec![]); } ret }; self.add_asm_inst(code, hashmap!{}, uses, false); } fn add_asm_branch(&mut self, code: String, target: MuName) { self.add_asm_inst_internal(code, hashmap!{}, hashmap!{}, false, ASMBranchTarget::Unconditional(target)); } fn add_asm_branch2(&mut self, code: String, target: MuName) { self.add_asm_inst_internal(code, hashmap!{}, hashmap!{}, false, ASMBranchTarget::Conditional(target)); } fn add_asm_inst( &mut self, code: String, defines: HashMap>, uses: HashMap>, is_using_mem_op: bool) { self.add_asm_inst_internal(code, defines, uses, is_using_mem_op, ASMBranchTarget::None) } fn add_asm_inst_internal( &mut self, code: String, defines: HashMap>, uses: HashMap>, is_using_mem_op: bool, target: ASMBranchTarget) { let line = self.line(); trace!("asm: {}", code); trace!(" defines: {:?}", defines); trace!(" uses: {:?}", uses); let mc = self.cur_mut(); // put the instruction mc.code.push(ASMInst::inst(code, defines, uses, is_using_mem_op, target)); } fn prepare_reg(&self, op: &P, loc: usize) -> (String, MuID, ASMLocation) { if cfg!(debug_assertions) { match op.v { Value_::SSAVar(_) => {}, _ => panic!("expecting register op") } } let str = self.asm_reg_op(op); let len = str.len(); (str, op.extract_ssa_id().unwrap(), ASMLocation::new(self.line(), loc, len)) } fn prepare_machine_reg(&self, op: &P) -> MuID { if cfg!(debug_assertions) { match op.v { Value_::SSAVar(_) => {}, _ => panic!("expecting machine register op") } } op.extract_ssa_id().unwrap() } #[allow(unused_assignments)] fn prepare_mem(&self, op: &P, loc: usize) -> (String, HashMap>) { if cfg!(debug_assertions) { match op.v { Value_::Memory(_) => {}, _ => panic!("expecting register op") } } let mut ids : Vec = vec![]; let mut locs : Vec = vec![]; let mut result_str : String = "".to_string(); let mut loc_cursor : usize = loc; match op.v { // offset(base,index,scale) Value_::Memory(MemoryLocation::Address{ref base, ref offset, ref index, scale}) => { // deal with offset if offset.is_some() { let offset = offset.as_ref().unwrap(); match offset.v { Value_::SSAVar(id) => { // temp as offset let (str, id, loc) = self.prepare_reg(offset, 0); result_str.push_str(&str); ids.push(id); locs.push(loc); loc_cursor += str.len(); }, Value_::Constant(Constant::Int(val)) => { let str = (val as i32).to_string(); result_str.push_str(&str); loc_cursor += str.len(); }, _ => panic!("unexpected offset type: {:?}", offset) } } result_str.push('('); loc_cursor += 1; // deal with base, base is ssa let (str, id, loc) = self.prepare_reg(base, loc_cursor); result_str.push_str(&str); ids.push(id); locs.push(loc); loc_cursor += str.len(); // deal with index (ssa or constant) if index.is_some() { result_str.push(','); loc_cursor += 1; // plus 1 for , let index = index.as_ref().unwrap(); match index.v { Value_::SSAVar(id) => { // temp as offset let (str, id, loc) = self.prepare_reg(index, loc_cursor); result_str.push_str(&str); ids.push(id); locs.push(loc); loc_cursor += str.len(); }, Value_::Constant(Constant::Int(val)) => { let str = (val as i32).to_string(); result_str.push_str(&str); loc_cursor += str.len(); }, _ => panic!("unexpected index type: {:?}", index) } // scale if scale.is_some() { result_str.push(','); loc_cursor += 1; let scale = scale.unwrap(); let str = scale.to_string(); result_str.push_str(&str); loc_cursor += str.len(); } } result_str.push(')'); loc_cursor += 1; }, Value_::Memory(MemoryLocation::Symbolic{ref base, ref label}) => { result_str.push_str(&symbol(label.clone())); loc_cursor += label.len(); if base.is_some() { result_str.push('('); loc_cursor += 1; let (str, id, loc) = self.prepare_reg(base.as_ref().unwrap(), loc_cursor); result_str.push_str(&str); ids.push(id); locs.push(loc); loc_cursor += str.len(); result_str.push(')'); loc_cursor += 1; } }, _ => panic!("expect mem location as value") } let uses : HashMap> = { let mut map : HashMap> = hashmap!{}; for i in 0..ids.len() { let id = ids[i]; let loc = locs[i].clone(); if map.contains_key(&id) { map.get_mut(&id).unwrap().push(loc); } else { map.insert(id, vec![loc]); } } map }; (result_str, uses) } fn asm_reg_op(&self, op: &P) -> String { let id = op.extract_ssa_id().unwrap(); if id < MACHINE_ID_END { // machine reg format!("%{}", op.name().unwrap()) } else { // virtual register, use place holder REG_PLACEHOLDER.clone() } } fn mangle_block_label(&self, label: MuName) -> String { format!("{}_{}", self.cur().name, label) } fn control_flow_analysis(&mut self) { // control flow analysis let n_insts = self.line(); let code = self.cur_mut(); let ref blocks = code.blocks; let ref mut asm = code.code; let block_start = { let mut ret = vec![]; for block in blocks.values() { ret.push(block.start_inst); } ret }; for i in 0..n_insts { // determine predecessor - if cur is not block start, its predecessor is previous insts let is_block_start = block_start.contains(&i); if !is_block_start { if i > 0 { trace!("inst {}: not a block start", i); trace!("inst {}: set PREDS as previous inst {}", i, i-1); asm[i].preds.push(i - 1); } } else { // if cur is a branch target, we already set its predecessor // if cur is a fall-through block, we set it in a sanity check pass } // determine successor let branch = asm[i].branch.clone(); match branch { ASMBranchTarget::Unconditional(ref target) => { // branch to target trace!("inst {}: is a branch to {}", i, target); let target_n = code.blocks.get(target).unwrap().start_inst; trace!("inst {}: branch target index is {}", i, target_n); // cur inst's succ is target trace!("inst {}: set SUCCS as branch target {}", i, target_n); asm[i].succs.push(target_n); // target's pred is cur trace!("inst {}: set PREDS as branch source {}", target_n, i); asm[target_n].preds.push(i); }, ASMBranchTarget::Conditional(ref target) => { // branch to target trace!("inst {}: is a cond branch to {}", i, target); let target_n = code.blocks.get(target).unwrap().start_inst; trace!("inst {}: branch target index is {}", i, target_n); // cur insts' succ is target and next inst asm[i].succs.push(target_n); trace!("inst {}: set SUCCS as branch target {}", i, target_n); if i < n_insts - 1 { trace!("inst {}: set SUCCS as next inst", i + 1); asm[i].succs.push(i + 1); } // target's pred is cur asm[target_n].preds.push(i); trace!("inst {}: set PREDS as {}", target_n, i); }, ASMBranchTarget::None => { // not branch nor cond branch, succ is next inst trace!("inst {}: not a branch inst", i); if i < n_insts - 1 { trace!("inst {}: set SUCCS as next inst {}", i, i + 1); asm[i].succs.push(i + 1); } } } } // a sanity check for fallthrough blocks for i in 0..n_insts { if i != 0 && asm[i].preds.len() == 0 { asm[i].preds.push(i - 1); } } } fn finish_code_sequence_asm(&mut self) -> Box { self.cur.take().unwrap() } } #[inline(always)] fn op_postfix(op_len: usize) -> &'static str { match op_len { 8 => "b", 16 => "w", 32 => "l", 64 => "q", _ => panic!("unexpected op size: {}", op_len) } } // general instruction emission macro_rules! binop_no_def_r_r { ($func_name: ident, $inst: expr, $op_len: expr) => { fn $func_name (&mut self, op1: &P, op2: &P) { // with postfix let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {} {}", inst, op1, op2); let (reg1, id1, loc1) = self.prepare_reg(op1, inst.len() + 1); let (reg2, id2, loc2) = self.prepare_reg(op2, inst.len() + 1 + reg1.len() + 1); let asm = format!("{} {},{}", inst, reg1, reg2); self.add_asm_inst( asm, hashmap!{}, hashmap!{ id1 => vec![loc1], id2 => vec![loc2] }, false ) } } } macro_rules! binop_no_def_r_imm { ($func_name: ident, $inst: expr, $op_len: expr, $imm_ty: ty) => { fn $func_name (&mut self, op1: &P, op2: $imm_ty) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {} {}", inst, op1, op2); let (reg1, id1, loc1) = self.prepare_reg(op1, inst.len() + 1 + 1 + op2.to_string().len() + 1); let asm = format!("{} ${},{}", inst, op2, reg1); self.add_asm_inst( asm, hashmap!{}, hashmap!{ id1 => vec![loc1] }, false ) } } } macro_rules! binop_no_def_r_mem { ($func_name: ident, $inst:expr, $op_len: expr) => { fn $func_name (&mut self, op1: &P, op2: &P) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {} {}", inst, op1, op2); let (reg, id1, loc1) = self.prepare_reg(op1, inst.len() + 1); let (mem, mut uses) = self.prepare_mem(op2, inst.len() + 1 + reg.len() + 1); let asm = format!("{} {},{}", inst, reg, mem); // merge use vec if uses.contains_key(&id1) { let mut locs = uses.get_mut(&id1).unwrap(); vec_utils::add_unique(locs, loc1.clone()); } else { uses.insert(id1, vec![loc1]); } self.add_asm_inst( asm, hashmap!{}, uses, true ) } } } macro_rules! binop_def_r_r { ($func_name: ident, $inst: expr, $op_len: expr) => { fn $func_name (&mut self, dest: &P, src: &P) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {}, {} -> {}", inst, src, dest, dest); let (reg1, id1, loc1) = self.prepare_reg(src, inst.len() + 1); let (reg2, id2, loc2) = self.prepare_reg(dest, inst.len() + 1 + reg1.len() + 1); let asm = format!("{} {},{}", inst, reg1, reg2); self.add_asm_inst( asm, hashmap!{ id2 => vec![loc2.clone()] }, hashmap!{ id1 => vec![loc1], id2 => vec![loc2] }, false ) } } } macro_rules! binop_def_r_imm { ($func_name: ident, $inst: expr, $op_len: expr, $imm_ty: ty) => { fn $func_name (&mut self, dest: &P, src: $imm_ty) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {}, {} -> {}", inst, src, dest, dest); let (reg1, id1, loc1) = self.prepare_reg(dest, inst.len() + 1 + 1 + src.to_string().len() + 1); let asm = format!("{} ${},{}", inst, src, reg1); self.add_asm_inst( asm, hashmap!{ id1 => vec![loc1.clone()] }, hashmap!{ id1 => vec![loc1] }, false ) } } } macro_rules! binop_def_r_mem { ($func_name: ident, $inst: expr, $op_len: expr) => { fn $func_name (&mut self, dest: &P, src: &P) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {}, {} -> {}", inst, src, dest, dest); let (mem, mut uses) = self.prepare_mem(src, inst.len() + 1); let (reg, id1, loc1) = self.prepare_reg(dest, inst.len() + 1 + mem.len() + 1); if uses.contains_key(&id1) { let mut locs = uses.get_mut(&id1).unwrap(); vec_utils::add_unique(locs, loc1.clone()); } else { uses.insert(id1, vec![loc1.clone()]); } let asm = format!("{} {},{}", inst, mem, reg); self.add_asm_inst( asm, hashmap!{ id1 => vec![loc1] }, uses, true ) } } } macro_rules! mov_r_r { ($func_name: ident, $inst: expr, $op_len: expr) => { fn $func_name (&mut self, dest: &P, src: &P) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {} -> {}", inst, src, dest); let (reg1, id1, loc1) = self.prepare_reg(src, inst.len() + 1); let (reg2, id2, loc2) = self.prepare_reg(dest, inst.len() + 1 + reg1.len() + 1); let asm = format!("{} {},{}", inst, reg1, reg2); self.add_asm_inst( asm, hashmap!{ id2 => vec![loc2] }, hashmap!{ id1 => vec![loc1] }, false ) } } } macro_rules! mov_r_imm { ($func_name: ident, $inst: expr, $op_len: expr, $imm_ty: ty) => { fn $func_name (&mut self, dest: &P, src: $imm_ty) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {} -> {}", inst, src, dest); let (reg1, id1, loc1) = self.prepare_reg(dest, inst.len() + 1 + 1 + src.to_string().len() + 1); let asm = format!("{} ${},{}", inst, src, reg1); self.add_asm_inst( asm, hashmap!{ id1 => vec![loc1] }, hashmap!{}, false ) } } } /// load macro_rules! mov_r_mem { ($func_name: ident, $inst: expr, $op_len: expr) => { fn $func_name (&mut self, dest: &P, src: &P) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {} -> {}", inst, src, dest); let (mem, uses) = self.prepare_mem(src, inst.len() + 1); let (reg, id2, loc2) = self.prepare_reg(dest, inst.len() + 1 + mem.len() + 1); let asm = format!("{} {},{}", inst, mem, reg); self.add_asm_inst( asm, hashmap!{ id2 => vec![loc2] }, uses, true ) } } } /// store macro_rules! mov_mem_r { ($func_name: ident, $inst: expr, $op_len: expr) => { fn $func_name (&mut self, dest: &P, src: &P) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {} -> {}", inst, src, dest); let (reg, id1, loc1) = self.prepare_reg(src, inst.len() + 1); let (mem, mut uses) = self.prepare_mem(dest, inst.len() + 1 + reg.len() + 1); // the register we used for the memory location is counted as 'use' // use the vec from mem as 'use' (push use reg from src to it) if uses.contains_key(&id1) { let mut locs = uses.get_mut(&id1).unwrap(); vec_utils::add_unique(locs, loc1); } else { uses.insert(id1, vec![loc1]); } let asm = format!("{} {},{}", inst, reg, mem); self.add_asm_inst( asm, hashmap!{}, uses, true ) } } } macro_rules! mov_mem_imm { ($func_name: ident, $inst: expr, $op_len: expr, $imm_ty: ty) => { fn $func_name (&mut self, dest: &P, src: $imm_ty) { let inst = $inst.to_string() + &op_postfix($op_len); trace!("emit: {} {} -> {}", inst, src, dest); let (mem, uses) = self.prepare_mem(dest, inst.len() + 1 + 1 + src.to_string().len() + 1); let asm = format!("{} ${},{}", inst, src, mem); self.add_asm_inst( asm, hashmap!{}, uses, true ) } } } macro_rules! emit_lea_r { ($func_name: ident, $op_len: expr) => { fn $func_name (&mut self, dest: &P, src: &P) { trace!("emit: lea {} -> {}", src, dest); let (mem, uses) = self.prepare_mem(src, 4 + 1); let (reg, id2, loc2) = self.prepare_reg(dest, 4 + 1 + mem.len() + 1); let asm = format!("lea{} {},{}", op_postfix($op_len), mem, reg); self.add_asm_inst( asm, hashmap!{ id2 => vec![loc2] }, uses, true ) } } } impl CodeGenerator for ASMCodeGen { fn start_code(&mut self, func_name: MuName) -> ValueLocation { self.cur = Some(Box::new(ASMCode { name: func_name.clone(), code: vec![], blocks: hashmap! {}, })); // to link with C sources via gcc let func_symbol = symbol(func_name.clone()); self.add_asm_symbolic(directive_globl(func_symbol.clone())); self.add_asm_symbolic(format!("{}:", func_symbol.clone())); ValueLocation::Relocatable(RegGroup::GPR, func_name) } fn finish_code(&mut self, func_name: MuName) -> (Box, ValueLocation) { let func_end = { let mut symbol = func_name.clone(); symbol.push_str("_end"); symbol }; self.add_asm_symbolic(directive_globl(symbol(func_end.clone()))); self.add_asm_symbolic(format!("{}:", symbol(func_end.clone()))); self.control_flow_analysis(); ( self.cur.take().unwrap(), ValueLocation::Relocatable(RegGroup::GPR, func_end) ) } fn start_code_sequence(&mut self) { self.cur = Some(Box::new(ASMCode { name: "snippet".to_string(), code: vec![], blocks: hashmap! {} })); } fn finish_code_sequence(&mut self) -> Box { self.finish_code_sequence_asm() } fn print_cur_code(&self) { println!(""); if self.cur.is_some() { let code = self.cur.as_ref().unwrap(); println!("code for {}: ", code.name); let n_insts = code.code.len(); for i in 0..n_insts { let ref line = code.code[i]; println!("#{}\t{}", i, line.code); } } else { println!("no current code"); } println!(""); } fn start_block(&mut self, block_name: MuName) { let label = format!("{}:", symbol(self.mangle_block_label(block_name.clone()))); self.add_asm_block_label(label, block_name.clone()); self.cur_mut().blocks.insert(block_name.clone(), ASMBlock::new()); let start = self.line(); self.cur_mut().blocks.get_mut(&block_name).unwrap().start_inst = start; } fn start_exception_block(&mut self, block_name: MuName) -> ValueLocation { let mangled_name = self.mangle_block_label(block_name.clone()); self.add_asm_symbolic(directive_globl(symbol(mangled_name.clone()))); self.start_block(block_name.clone()); ValueLocation::Relocatable(RegGroup::GPR, mangled_name) } fn end_block(&mut self, block_name: MuName) { let line = self.line(); match self.cur_mut().blocks.get_mut(&block_name) { Some(ref mut block) => { block.end_inst = line; } None => panic!("trying to end block {} which hasnt been started", block_name) } } fn set_block_livein(&mut self, block_name: MuName, live_in: &Vec>) { let cur = self.cur_mut(); match cur.blocks.get_mut(&block_name) { Some(ref mut block) => { if block.livein.is_empty() { let mut live_in = { let mut ret = vec![]; for p in live_in { match p.extract_ssa_id() { Some(id) => ret.push(id), // this should not happen None => error!("{} as live-in of block {} is not SSA", p, block_name) } } ret }; block.livein.append(&mut live_in); } else { panic!("seems we are inserting livein to block {} twice", block_name); } } None => panic!("haven't created ASMBlock for {}", block_name) } } fn set_block_liveout(&mut self, block_name: MuName, live_out: &Vec>) { let cur = self.cur_mut(); match cur.blocks.get_mut(&block_name) { Some(ref mut block) => { if block.liveout.is_empty() { let mut live_out = { let mut ret = vec![]; for p in live_out { match p.extract_ssa_id() { Some(id) => ret.push(id), // the liveout are actually args out of this block // (they can be constants) None => trace!("{} as live-out of block {} is not SSA", p, block_name) } } ret }; block.liveout.append(&mut live_out); } else { panic!("seems we are inserting liveout to block {} twice", block_name); } } None => panic!("haven't created ASMBlock for {}", block_name) } } fn emit_nop(&mut self, bytes: usize) { trace!("emit: nop ({} bytes)", bytes); let asm = String::from("nop"); self.add_asm_inst( asm, hashmap! {}, hashmap! {}, false ); } // cmp binop_no_def_r_r!(emit_cmp_r64_r64, "cmp", 64); binop_no_def_r_r!(emit_cmp_r32_r32, "cmp", 32); binop_no_def_r_r!(emit_cmp_r16_r16, "cmp", 16); binop_no_def_r_r!(emit_cmp_r8_r8 , "cmp", 8 ); binop_no_def_r_imm!(emit_cmp_r64_imm32, "cmp", 64, i32); binop_no_def_r_imm!(emit_cmp_r32_imm32, "cmp", 32, i32); binop_no_def_r_imm!(emit_cmp_r16_imm16, "cmp", 16, i16); binop_no_def_r_imm!(emit_cmp_r8_imm8 , "cmp", 8 , i8 ); binop_no_def_r_mem!(emit_cmp_r64_mem64, "cmp", 64); binop_no_def_r_mem!(emit_cmp_r32_mem32, "cmp", 32); binop_no_def_r_mem!(emit_cmp_r16_mem16, "cmp", 16); binop_no_def_r_mem!(emit_cmp_r8_mem8 , "cmp", 8 ); // mov mov_r_imm!(emit_mov_r64_imm32, "mov", 64, i32); mov_r_imm!(emit_mov_r32_imm32, "mov", 32, i32); mov_r_imm!(emit_mov_r16_imm16, "mov", 16, i16); mov_r_imm!(emit_mov_r8_imm8 , "mov", 8 , i8 ); mov_r_mem!(emit_mov_r64_mem64, "mov", 64); mov_r_mem!(emit_mov_r32_mem32, "mov", 32); mov_r_mem!(emit_mov_r16_mem16, "mov", 16); mov_r_mem!(emit_mov_r8_mem8 , "mov", 8 ); mov_r_r!(emit_mov_r64_r64, "mov", 64); mov_r_r!(emit_mov_r32_r32, "mov", 32); mov_r_r!(emit_mov_r16_r16, "mov", 16); mov_r_r!(emit_mov_r8_r8 , "mov", 8 ); mov_mem_r!(emit_mov_mem64_r64, "mov", 64); mov_mem_r!(emit_mov_mem32_r32, "mov", 32); mov_mem_r!(emit_mov_mem16_r16, "mov", 16); mov_mem_r!(emit_mov_mem8_r8 , "mov", 8 ); mov_mem_imm!(emit_mov_mem64_imm32, "mov", 64, i32); mov_mem_imm!(emit_mov_mem32_imm32, "mov", 32, i32); mov_mem_imm!(emit_mov_mem16_imm16, "mov", 16, i16); mov_mem_imm!(emit_mov_mem8_imm8 , "mov", 8 , i8 ); // lea mov_r_mem!(emit_lea_r64, "lea", 64); // and binop_def_r_r!(emit_and_r64_r64, "and", 64); binop_def_r_r!(emit_and_r32_r32, "and", 32); binop_def_r_r!(emit_and_r16_r16, "and", 16); binop_def_r_r!(emit_and_r8_r8 , "and", 8 ); binop_def_r_imm!(emit_and_r64_imm32, "and", 64, i32); binop_def_r_imm!(emit_and_r32_imm32, "and", 32, i32); binop_def_r_imm!(emit_and_r16_imm16, "and", 16, i16); binop_def_r_imm!(emit_and_r8_imm8 , "and", 8 , i8 ); binop_def_r_mem!(emit_and_r64_mem64, "and", 64); binop_def_r_mem!(emit_and_r32_mem32, "and", 32); binop_def_r_mem!(emit_and_r16_mem16, "and", 16); binop_def_r_mem!(emit_and_r8_mem8 , "and", 8 ); // xor binop_def_r_r!(emit_xor_r64_r64, "xor", 64); binop_def_r_r!(emit_xor_r32_r32, "xor", 32); binop_def_r_r!(emit_xor_r16_r16, "xor", 16); binop_def_r_r!(emit_xor_r8_r8 , "xor", 8 ); binop_def_r_imm!(emit_xor_r64_imm32, "xor", 64, i32); binop_def_r_imm!(emit_xor_r32_imm32, "xor", 32, i32); binop_def_r_imm!(emit_xor_r16_imm16, "xor", 16, i16); binop_def_r_imm!(emit_xor_r8_imm8 , "xor", 8 , i8 ); binop_def_r_mem!(emit_xor_r64_mem64, "xor", 64); binop_def_r_mem!(emit_xor_r32_mem32, "xor", 32); binop_def_r_mem!(emit_xor_r16_mem16, "xor", 16); binop_def_r_mem!(emit_xor_r8_mem8 , "xor", 8 ); // add binop_def_r_r!(emit_add_r64_r64, "add", 64); binop_def_r_r!(emit_add_r32_r32, "add", 32); binop_def_r_r!(emit_add_r16_r16, "add", 16); binop_def_r_r!(emit_add_r8_r8 , "add", 8 ); binop_def_r_imm!(emit_add_r64_imm32, "add", 64, i32); binop_def_r_imm!(emit_add_r32_imm32, "add", 32, i32); binop_def_r_imm!(emit_add_r16_imm16, "add", 16, i16); binop_def_r_imm!(emit_add_r8_imm8 , "add", 8 , i8 ); binop_def_r_mem!(emit_add_r64_mem64, "add", 64); binop_def_r_mem!(emit_add_r32_mem32, "add", 32); binop_def_r_mem!(emit_add_r16_mem16, "add", 16); binop_def_r_mem!(emit_add_r8_mem8 , "add", 8 ); // sub binop_def_r_r!(emit_sub_r64_r64, "sub", 64); binop_def_r_r!(emit_sub_r32_r32, "sub", 32); binop_def_r_r!(emit_sub_r16_r16, "sub", 16); binop_def_r_r!(emit_sub_r8_r8 , "sub", 8 ); binop_def_r_imm!(emit_sub_r64_imm32, "sub", 64, i32); binop_def_r_imm!(emit_sub_r32_imm32, "sub", 32, i32); binop_def_r_imm!(emit_sub_r16_imm16, "sub", 16, i16); binop_def_r_imm!(emit_sub_r8_imm8 , "sub", 8 , i8 ); binop_def_r_mem!(emit_sub_r64_mem64, "sub", 64); binop_def_r_mem!(emit_sub_r32_mem32, "sub", 32); binop_def_r_mem!(emit_sub_r16_mem16, "sub", 16); binop_def_r_mem!(emit_sub_r8_mem8 , "sub", 8 ); fn emit_mul_r64(&mut self, src: &P) { trace!("emit: mul rax, {} -> (rdx, rax)", src); let (reg, id, loc) = self.prepare_reg(src, 3 + 1); let rax = self.prepare_machine_reg(&x86_64::RAX); let rdx = self.prepare_machine_reg(&x86_64::RDX); let asm = format!("mul {}", reg); self.add_asm_inst( asm, hashmap!{ rax => vec![], rdx => vec![] }, hashmap!{ id => vec![loc], rax => vec![] }, false ) } fn emit_mul_r32 (&mut self, src: &P) {unimplemented!()} fn emit_mul_r16 (&mut self, src: &P) {unimplemented!()} fn emit_mul_r8 (&mut self, src: &P) {unimplemented!()} fn emit_mul_mem64(&mut self, src: &P) {unimplemented!()} fn emit_mul_mem32(&mut self, src: &P) {unimplemented!()} fn emit_mul_mem16(&mut self, src: &P) {unimplemented!()} fn emit_mul_mem8 (&mut self, src: &P) {unimplemented!()} fn emit_div_r64 (&mut self, src: &P) { trace!("emit: div rdx:rax, {} -> quotient: rax + remainder: rdx", src); let rdx = self.prepare_machine_reg(&x86_64::RDX); let rax = self.prepare_machine_reg(&x86_64::RAX); let (reg, id, loc) = self.prepare_reg(src, 4 + 1); let asm = format!("divq {}", reg); self.add_asm_inst( asm, hashmap!{ rdx => vec![], rax => vec![], }, hashmap!{ id => vec![loc], rdx => vec![], rax => vec![] }, false ) } fn emit_div_r32 (&mut self, src: &P) {unimplemented!()} fn emit_div_r16 (&mut self, src: &P) {unimplemented!()} fn emit_div_r8 (&mut self, src: &P) {unimplemented!()} fn emit_div_mem64 (&mut self, src: &P) { trace!("emit: div rdx:rax, {} -> quotient: rax + remainder: rdx", src); let rdx = self.prepare_machine_reg(&x86_64::RDX); let rax = self.prepare_machine_reg(&x86_64::RAX); let (mem, mut uses) = self.prepare_mem(src, 4 + 1); // merge use vec if !uses.contains_key(&rdx) { uses.insert(rdx, vec![]); } if !uses.contains_key(&rax) { uses.insert(rax, vec![]); } let asm = format!("divq {}", mem); self.add_asm_inst( asm, hashmap!{ rdx => vec![], rax => vec![] }, uses, true ) } fn emit_div_mem32 (&mut self, src: &P) {unimplemented!()} fn emit_div_mem16 (&mut self, src: &P) {unimplemented!()} fn emit_div_mem8 (&mut self, src: &P) {unimplemented!()} fn emit_idiv_r64 (&mut self, src: &P) { trace!("emit: idiv rdx:rax, {} -> quotient: rax + remainder: rdx", src); let rdx = self.prepare_machine_reg(&x86_64::RDX); let rax = self.prepare_machine_reg(&x86_64::RAX); let (reg, id, loc) = self.prepare_reg(src, 4 + 1); let asm = format!("idivq {}", reg); self.add_asm_inst( asm, hashmap!{ rdx => vec![], rax => vec![], }, hashmap!{ id => vec![loc], rdx => vec![], rax => vec![] }, false ) } fn emit_idiv_r32 (&mut self, src: &P) {unimplemented!()} fn emit_idiv_r16 (&mut self, src: &P) {unimplemented!()} fn emit_idiv_r8 (&mut self, src: &P) {unimplemented!()} fn emit_idiv_mem64(&mut self, src: &P) { trace!("emit: idiv rdx:rax, {} -> quotient: rax + remainder: rdx", src); let rdx = self.prepare_machine_reg(&x86_64::RDX); let rax = self.prepare_machine_reg(&x86_64::RAX); let (mem, mut uses) = self.prepare_mem(src, 4 + 1); // merge use vec if !uses.contains_key(&rdx) { uses.insert(rdx, vec![]); } if !uses.contains_key(&rax) { uses.insert(rax, vec![]); } let asm = format!("idivq {}", mem); self.add_asm_inst( asm, hashmap!{ rdx => vec![], rax => vec![] }, uses, true ) } fn emit_idiv_mem32(&mut self, src: &P) {unimplemented!()} fn emit_idiv_mem16(&mut self, src: &P) {unimplemented!()} fn emit_idiv_mem8 (&mut self, src: &P) {unimplemented!()} fn emit_shl_r64_cl (&mut self, dest: &P) { trace!("emit shl {}, CL -> {}", dest, dest); let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 3 + 1); let rcx = self.prepare_machine_reg(&x86_64::RCX); let asm = format!("shlq %cl,{}", reg1); self.add_asm_inst( asm, hashmap!{ id1 => vec![loc1.clone()] }, hashmap!{ id1 => vec![loc1], rcx => vec![] }, false ) } fn emit_shl_mem64_cl (&mut self, dest: &P) { trace!("emit shl {}, CL -> {}", dest, dest); let (mem, mut uses) = self.prepare_mem(dest, 4 + 1 + 3 + 1); let rcx = self.prepare_machine_reg(&x86_64::RCX); if !uses.contains_key(&rcx) { uses.insert(rcx, vec![]); } let asm = format!("shlq %cl,{}", mem); self.add_asm_inst( asm, hashmap!{}, uses, true ) } fn emit_shl_r64_imm8 (&mut self, dest: &P, src: i8) { trace!("emit shl {},{} -> {}", dest, src, dest); let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1); let asm = format!("shlq ${},{}", src, reg1); self.add_asm_inst( asm, hashmap!{ id1 => vec![loc1.clone()] }, hashmap!{ id1 => vec![loc1] }, false ) } fn emit_shl_mem64_imm8(&mut self, dest: &P, src: i8) { trace!("emit shl {},{} -> {}", dest, src, dest); let (mem, mut uses) = self.prepare_mem(dest, 4 + 1 + 1 + src.to_string().len() + 1); let asm = format!("shlq ${},{}", src, mem); self.add_asm_inst( asm, hashmap!{}, uses, true ) } fn emit_shr_r64_cl (&mut self, dest: &P) { trace!("emit shr {}, CL -> {}", dest, dest); let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 3 + 1); let rcx = self.prepare_machine_reg(&x86_64::RCX); let asm = format!("shrq %cl,{}", reg1); self.add_asm_inst( asm, hashmap!{ id1 => vec![loc1.clone()] }, hashmap!{ id1 => vec![loc1], rcx => vec![] }, false ) } fn emit_shr_mem64_cl (&mut self, dest: &P) { trace!("emit shr {}, CL -> {}", dest, dest); let (mem, mut uses) = self.prepare_mem(dest, 4 + 1 + 3 + 1); let rcx = self.prepare_machine_reg(&x86_64::RCX); if !uses.contains_key(&rcx) { uses.insert(rcx, vec![]); } let asm = format!("shrq %cl,{}", mem); self.add_asm_inst( asm, hashmap!{}, uses, true ) } fn emit_shr_r64_imm8 (&mut self, dest: &P, src: i8) { trace!("emit shr {},{} -> {}", dest, src, dest); let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1); let asm = format!("shrq ${},{}", src, reg1); self.add_asm_inst( asm, hashmap!{ id1 => vec![loc1.clone()] }, hashmap!{ id1 => vec![loc1] }, false ) } fn emit_shr_mem64_imm8(&mut self, dest: &P, src: i8) { trace!("emit shr {},{} -> {}", dest, src, dest); let (mem, mut uses) = self.prepare_mem(dest, 4 + 1 + 1 + src.to_string().len() + 1); let asm = format!("shrq ${},{}", src, mem); self.add_asm_inst( asm, hashmap!{}, uses, true ) } fn emit_sar_r64_cl (&mut self, dest: &P) { trace!("emit sar {}, CL -> {}", dest, dest); let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 3 + 1); let rcx = self.prepare_machine_reg(&x86_64::RCX); let asm = format!("sarq %cl,{}", reg1); self.add_asm_inst( asm, hashmap!{ id1 => vec![loc1.clone()] }, hashmap!{ id1 => vec![loc1], rcx => vec![] }, false ) } fn emit_sar_mem64_cl (&mut self, dest: &P) { trace!("emit sar {}, CL -> {}", dest, dest); let (mem, mut uses) = self.prepare_mem(dest, 4 + 1 + 3 + 1); let rcx = self.prepare_machine_reg(&x86_64::RCX); if !uses.contains_key(&rcx) { uses.insert(rcx, vec![]); } let asm = format!("sarq %cl,{}", mem); self.add_asm_inst( asm, hashmap!{}, uses, true ) } fn emit_sar_r64_imm8 (&mut self, dest: &P, src: i8) { trace!("emit sar {},{} -> {}", dest, src, dest); let (reg1, id1, loc1) = self.prepare_reg(dest, 4 + 1 + 1 + src.to_string().len() + 1); let asm = format!("sarq ${},{}", src, reg1); self.add_asm_inst( asm, hashmap!{ id1 => vec![loc1.clone()] }, hashmap!{ id1 => vec![loc1] }, false ) } fn emit_sar_mem64_imm8(&mut self, dest: &P, src: i8) { trace!("emit sar {},{} -> {}", dest, src, dest); let (mem, mut uses) = self.prepare_mem(dest, 4 + 1 + 1 + src.to_string().len() + 1); let asm = format!("sarq ${},{}", src, mem); self.add_asm_inst( asm, hashmap!{}, uses, true ) } fn emit_cqo(&mut self) { trace!("emit: cqo rax -> rdx:rax"); let rax = self.prepare_machine_reg(&x86_64::RAX); let rdx = self.prepare_machine_reg(&x86_64::RDX); let asm = format!("cqto"); self.add_asm_inst( asm, hashmap!{ rdx => vec![] }, hashmap!{ rax => vec![], }, false ) } fn emit_jmp(&mut self, dest_name: MuName) { trace!("emit: jmp {}", dest_name); // symbolic label, we dont need to patch it let asm = format!("jmp {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch(asm, dest_name) } fn emit_je(&mut self, dest_name: MuName) { trace!("emit: je {}", dest_name); let asm = format!("je {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_jne(&mut self, dest_name: MuName) { trace!("emit: jne {}", dest_name); let asm = format!("jne {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_ja(&mut self, dest_name: MuName) { trace!("emit: ja {}", dest_name); let asm = format!("ja {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_jae(&mut self, dest_name: MuName) { trace!("emit: jae {}", dest_name); let asm = format!("jae {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_jb(&mut self, dest_name: MuName) { trace!("emit: jb {}", dest_name); let asm = format!("jb {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_jbe(&mut self, dest_name: MuName) { trace!("emit: jbe {}", dest_name); let asm = format!("jbe {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_jg(&mut self, dest_name: MuName) { trace!("emit: jg {}", dest_name); let asm = format!("jg {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_jge(&mut self, dest_name: MuName) { trace!("emit: jge {}", dest_name); let asm = format!("jge {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_jl(&mut self, dest_name: MuName) { trace!("emit: jl {}", dest_name); let asm = format!("jl {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_jle(&mut self, dest_name: MuName) { trace!("emit: jle {}", dest_name); let asm = format!("jle {}", symbol(self.mangle_block_label(dest_name.clone()))); self.add_asm_branch2(asm, dest_name); } fn emit_call_near_rel32(&mut self, callsite: String, func: MuName) -> ValueLocation { trace!("emit: call {}", func); let asm = format!("call {}", symbol(func)); self.add_asm_call(asm); let callsite_symbol = symbol(callsite.clone()); self.add_asm_symbolic(directive_globl(callsite_symbol.clone())); self.add_asm_symbolic(format!("{}:", callsite_symbol.clone())); ValueLocation::Relocatable(RegGroup::GPR, callsite) } fn emit_call_near_r64(&mut self, callsite: String, func: &P) -> ValueLocation { trace!("emit: call {}", func); unimplemented!() } fn emit_call_near_mem64(&mut self, callsite: String, func: &P) -> ValueLocation { trace!("emit: call {}", func); unimplemented!() } fn emit_ret(&mut self) { trace!("emit: ret"); let asm = format!("ret"); self.add_asm_ret(asm); } fn emit_push_r64(&mut self, src: &P) { trace!("emit: push {}", src); let (reg, id, loc) = self.prepare_reg(src, 5 + 1); let rsp = self.prepare_machine_reg(&x86_64::RSP); let asm = format!("pushq {}", reg); self.add_asm_inst( asm, hashmap!{ rsp => vec![] }, hashmap!{ id => vec![loc], rsp => vec![] }, false ) } fn emit_push_imm32(&mut self, src: i32) { trace!("emit: push {}", src); let rsp = self.prepare_machine_reg(&x86_64::RSP); let asm = format!("pushq ${}", src); self.add_asm_inst( asm, hashmap!{ rsp => vec![] }, hashmap!{ rsp => vec![] }, false ) } fn emit_pop_r64(&mut self, dest: &P) { trace!("emit: pop {}", dest); let (reg, id, loc) = self.prepare_reg(dest, 4 + 1); let rsp = self.prepare_machine_reg(&x86_64::RSP); let asm = format!("popq {}", reg); self.add_asm_inst( asm, hashmap!{ id => vec![loc.clone()], rsp => vec![] }, hashmap!{ rsp => vec![] }, false ) } fn emit_movsd_f64_f64 (&mut self, dest: &P, src: &P) { trace!("emit: movsd {} -> {}", src, dest); let (reg1, id1, loc1) = self.prepare_reg(src, 5 + 1); let (reg2, id2, loc2) = self.prepare_reg(dest, 5 + 1 + reg1.len() + 1); let asm = format!("movsd {},{}", reg1, reg2); self.add_asm_inst( asm, hashmap!{ id2 => vec![loc2] }, hashmap!{ id1 => vec![loc1] }, false ) } // load fn emit_movsd_f64_mem64(&mut self, dest: &P, src: &P) { trace!("emit: movsd {} -> {}", src, dest); let (mem, uses) = self.prepare_mem(src, 5 + 1); let (reg, id2, loc2) = self.prepare_reg(dest, 5 + 1 + mem.len() + 1); let asm = format!("movsd {},{}", mem, reg); self.add_asm_inst( asm, hashmap!{ id2 => vec![loc2] }, uses, true ) } // store fn emit_movsd_mem64_f64(&mut self, dest: &P, src: &P) { trace!("emit: movsd {} -> {}", src, dest); let (reg, id1, loc1) = self.prepare_reg(src, 5 + 1); let (mem, mut uses) = self.prepare_mem(dest, 5 + 1 + reg.len() + 1); // the register we used for the memory location is counted as 'use' // use the vec from mem as 'use' (push use reg from src to it) if uses.contains_key(&id1) { uses.get_mut(&id1).unwrap().push(loc1); } else { uses.insert(id1, vec![loc1]); } let asm = format!("movsd {},{}", reg, mem); self.add_asm_inst( asm, hashmap!{}, uses, true ) } fn emit_addsd_f64_f64 (&mut self, dest: &P, src: &P) { trace!("emit: addsd {}, {} -> {}", dest, src, dest); let (reg1, id1, loc1) = self.prepare_reg(src, 5 + 1); let (reg2, id2, loc2) = self.prepare_reg(dest, 5 + 1 + reg1.len() + 1); let asm = format!("addsd {},{}", reg1, reg2); self.add_asm_inst( asm, hashmap!{ id2 => vec![loc2.clone()] }, hashmap!{ id1 => vec![loc1], id2 => vec![loc2] }, false ) } fn emit_addsd_f64_mem64(&mut self, dest: &P, src: &P) { trace!("emit: addsd {}, {} -> {}", dest, src, dest); unimplemented!() } } fn create_emit_directory() { use std::fs; match fs::create_dir(AOT_EMIT_DIR) { Ok(_) => {}, Err(_) => {} } } pub fn emit_code(fv: &mut MuFunctionVersion, vm: &VM) { use std::io::prelude::*; use std::fs::File; use std::path; let funcs = vm.funcs().read().unwrap(); let func = funcs.get(&fv.func_id).unwrap().read().unwrap(); let compiled_funcs = vm.compiled_funcs().read().unwrap(); let cf = compiled_funcs.get(&fv.id()).unwrap().read().unwrap(); let code = cf.mc.as_ref().unwrap().emit(); // create 'emit' directory create_emit_directory(); let mut file_path = path::PathBuf::new(); file_path.push(AOT_EMIT_DIR); file_path.push(func.name().unwrap().to_string() + ".s"); let mut file = match File::create(file_path.as_path()) { Err(why) => panic!("couldn't create emission file {}: {}", file_path.to_str().unwrap(), why), Ok(file) => file }; match file.write_all(code.as_slice()) { Err(why) => panic!("couldn'd write to file {}: {}", file_path.to_str().unwrap(), why), Ok(_) => println!("emit code to {}", file_path.to_str().unwrap()) } } pub fn emit_context(vm: &VM) { use std::path; use std::fs::File; use std::io::prelude::*; use rustc_serialize::json; debug!("---Emit VM Context---"); create_emit_directory(); let mut file_path = path::PathBuf::new(); file_path.push(AOT_EMIT_DIR); file_path.push(AOT_EMIT_CONTEXT_FILE); let mut file = match File::create(file_path.as_path()) { Err(why) => panic!("couldn't create context file {}: {}", file_path.to_str().unwrap(), why), Ok(file) => file }; // bss { // put globals into bss section file.write_fmt(format_args!("\t.bss\n")).unwrap(); let globals = vm.globals().read().unwrap(); for global in globals.values() { debug!("emit global: {}", global); let (size, align) = { let alloc_ty = { match global.v { Value_::Global(ref ty) => ty, _ => panic!("expected a global") } }; debug!("getting type: {:?}", alloc_ty); let ty_info = vm.get_backend_type_info(alloc_ty.id()); (ty_info.size, ty_info.alignment) }; file.write_fmt(format_args!("\t{}\n", directive_globl(symbol(global.name().unwrap())))).unwrap(); file.write_fmt(format_args!("\t{}\n", directive_comm(symbol(global.name().unwrap()), size, align))).unwrap(); file.write("\n".as_bytes()).unwrap(); } } // data // serialize vm trace!("start serializing vm"); { let serialize_vm = json::encode(&vm).unwrap(); file.write("\t.data\n".as_bytes()).unwrap(); let vm_symbol = symbol("vm".to_string()); file.write_fmt(format_args!("{}\n", directive_globl(vm_symbol.clone()))).unwrap(); let escape_serialize_vm = serialize_vm.replace("\"", "\\\""); file.write_fmt(format_args!("\t{}: .asciz \"{}\"", vm_symbol, escape_serialize_vm)).unwrap(); file.write("\n".as_bytes()).unwrap(); } // main_thread // let primordial = vm.primordial.read().unwrap(); // if primordial.is_some() { // let primordial = primordial.as_ref().unwrap(); // } debug!("---finish---"); } //#[cfg(target_os = "macos")] fn directive_globl(name: String) -> String { format!(".globl {}", name) } // //#[cfg(target_os = "linux")] //fn directive_globl(name: String) -> String { // format!("global {}", name) //} fn directive_comm(name: String, size: ByteSize, align: ByteSize) -> String { format!(".comm {},{},{}", name, size, align) } #[cfg(target_os = "linux")] pub fn symbol(name: String) -> String { name } #[cfg(target_os = "macos")] pub fn symbol(name: String) -> String { format!("_{}", name) } use compiler::machine_code::CompiledFunction; pub fn spill_rewrite( spills: &HashMap>, func: &mut MuFunctionVersion, cf: &mut CompiledFunction, vm: &VM) -> Vec> { trace!("spill rewrite for x86_64 asm backend"); let mut new_nodes = vec![]; // record code and their insertion point, so we can do the copy/insertion all at once let mut spill_code_before: HashMap>> = HashMap::new(); let mut spill_code_after: HashMap>> = HashMap::new(); // iterate through all instructions for i in 0..cf.mc().number_of_insts() { trace!("---Inst {}---", i); // find use of any register that gets spilled { let reg_uses = cf.mc().get_inst_reg_uses(i).to_vec(); for reg in reg_uses { if spills.contains_key(®) { let val_reg = func.context.get_value(reg).unwrap().value().clone(); // a register used here is spilled let spill_mem = spills.get(®).unwrap(); // generate a random new temporary let temp_ty = val_reg.ty.clone(); let temp = func.new_ssa(vm.next_id(), temp_ty).clone_value(); vec_utils::add_unique(&mut new_nodes, temp.clone()); trace!("reg {} used in Inst{} is replaced as {}", val_reg, i, temp); // generate a load let code = { let mut codegen = ASMCodeGen::new(); codegen.start_code_sequence(); codegen.emit_mov_r64_mem64(&temp, spill_mem); codegen.finish_code_sequence_asm() }; // record that this load will be inserted at i trace!("insert before inst #{}", i); if spill_code_before.contains_key(&i) { spill_code_before.get_mut(&i).unwrap().push(code); } else { spill_code_before.insert(i, vec![code]); } // replace register reg with temp cf.mc_mut().replace_use_tmp_for_inst(reg, temp.id(), i); } } } // find define of any register that gets spilled { let reg_defines = cf.mc().get_inst_reg_defines(i).to_vec(); for reg in reg_defines { if spills.contains_key(®) { let val_reg = func.context.get_value(reg).unwrap().value().clone(); let spill_mem = spills.get(®).unwrap(); let temp_ty = val_reg.ty.clone(); let temp = func.new_ssa(vm.next_id(), temp_ty).clone_value(); vec_utils::add_unique(&mut new_nodes, temp.clone()); trace!("reg {} defined in Inst{} is replaced as {}", val_reg, i, temp); let code = { let mut codegen = ASMCodeGen::new(); codegen.start_code_sequence(); codegen.emit_mov_mem64_r64(spill_mem, &temp); codegen.finish_code_sequence_asm() }; trace!("insert after inst #{}", i); if spill_code_after.contains_key(&i) { spill_code_after.get_mut(&i).unwrap().push(code); } else { spill_code_after.insert(i, vec![code]); } cf.mc_mut().replace_define_tmp_for_inst(reg, temp.id(), i); } } } } // copy and insert the code let new_mc = { let old_mc = cf.mc.take().unwrap(); let old_mc_ref : &ASMCode = old_mc.as_any().downcast_ref().unwrap(); old_mc_ref.rewrite_insert(spill_code_before, spill_code_after) }; cf.mc = Some(new_mc); trace!("spill rewrite done"); new_nodes }