// 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. extern crate hprof; use compiler::machine_code::CompiledFunction; use ast::ir::*; use compiler::backend; use utils::LinkedHashSet; use utils::LinkedHashMap; use compiler::backend::reg_alloc::graph_coloring::petgraph; use compiler::backend::reg_alloc::graph_coloring::petgraph::Graph; use compiler::backend::reg_alloc::graph_coloring::petgraph::graph::NodeIndex; /// GraphNode represents a node in the interference graph. #[derive(Clone, Copy, Debug, PartialEq)] pub struct GraphNode { /// temp ID (could be register) temp: MuID, /// assigned color color: Option, /// temp register group (which machine register class we should assign) group: backend::RegGroup, /// cost to spill this temp spill_cost: f32 } /// Move represents a move between two nodes (referred by index) /// We need to know the moves so that we can coalesce. #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)] pub struct Move { pub from: NodeIndex, pub to: NodeIndex } /// InterferenceGraph represents the interference graph, including /// * the graph /// * all the nodes and its NodeIndex (a node is referred to by NodeIndex) /// * all the moves pub struct InterferenceGraph { /// the internal graph graph: Graph, /// a map of all nodes (from temp ID to node index) /// node index is how nodes are referred to with pet_graph nodes: LinkedHashMap, /// a set of all moves moves: LinkedHashSet } impl InterferenceGraph { /// creates a new graph fn new() -> InterferenceGraph { InterferenceGraph { graph: Graph::new_undirected(), nodes: LinkedHashMap::new(), moves: LinkedHashSet::new() } } /// creates a new node for a temp (if we already created a temp for the temp, returns the node) /// This function will increase spill cost for the node by 1 each tiem it is called for the temp fn new_node(&mut self, reg_id: MuID, context: &FunctionContext) -> NodeIndex { let entry = context.get_value(reg_id).unwrap(); // if it is the first time, create the node if !self.nodes.contains_key(®_id) { let node = GraphNode { temp: reg_id, color: None, group: backend::RegGroup::get_from_ty(entry.ty()), spill_cost: 0.0f32 }; // add to the graph let index = self.graph.add_node(node); // save index self.nodes.insert(reg_id, index); } // get the node index let node_index = *self.nodes.get(®_id).unwrap(); // get node let node_mut = self.graph.node_weight_mut(node_index).unwrap(); // increase node spill cost node_mut.spill_cost += 1.0f32; node_index } /// returns the node index for a temp pub fn get_node(&self, reg: MuID) -> NodeIndex { match self.nodes.get(®) { Some(index) => *index, None => panic!("do not have a node for {}", reg) } } /// returns all the nodes in the graph pub fn nodes(&self) -> Vec { let mut ret = vec![]; for index in self.nodes.values() { ret.push(*index); } ret } /// returns all the moves in the graph pub fn moves(&self) -> &LinkedHashSet { &self.moves } /// adds a move edge between two nodes fn add_move(&mut self, src: NodeIndex, dst: NodeIndex) { let src = { let temp_src = self.get_temp_of(src); if temp_src < MACHINE_ID_END { // get the color for the machine register, e.g. rax for eax/ax/al/ah let alias = backend::get_color_for_precolored(temp_src); self.get_node(alias) } else { src } }; let dst = { let temp_dst = self.get_temp_of(dst); if temp_dst < MACHINE_ID_END { let alias = backend::get_color_for_precolored(temp_dst); self.get_node(alias) } else { dst } }; self.moves.insert(Move { from: src, to: dst }); } /// adds an interference edge between two nodes pub fn add_interference_edge(&mut self, from: NodeIndex, to: NodeIndex) { // adds edge to the internal graph self.graph.update_edge(from, to, ()); // if one of the node is machine register, we also add // interference edge to its alias // e.g. if we have %a - %edi interfered, // we also add %a - %rdi interference let from_tmp = self.graph.node_weight(from).unwrap().temp; let to_tmp = self.graph.node_weight(to).unwrap().temp; if from_tmp < MACHINE_ID_END || to_tmp < MACHINE_ID_END { let from_tmp = if from_tmp < MACHINE_ID_END { backend::get_color_for_precolored(from_tmp) } else { from_tmp }; let to_tmp = if to_tmp < MACHINE_ID_END { backend::get_color_for_precolored(to_tmp) } else { to_tmp }; let from_tmp_node = self.get_node(from_tmp); let to_tmp_node = self.get_node(to_tmp); self.graph.update_edge(from_tmp_node, to_tmp_node, ()); } } /// is two nodes interfered? pub fn is_interfered_with(&self, node1: NodeIndex, node2: NodeIndex) -> bool { let edge = self.graph.find_edge(node1, node2); edge.is_some() } /// set color for a node pub fn color_node(&mut self, node: NodeIndex, color: MuID) { self.graph.node_weight_mut(node).unwrap().color = Some(color); } /// is a node colored yet? pub fn is_colored(&self, node: NodeIndex) -> bool { self.graph.node_weight(node).unwrap().color.is_some() } /// gets the color of a node pub fn get_color_of(&self, node: NodeIndex) -> Option { self.graph.node_weight(node).unwrap().color } /// gets the reg group of a node pub fn get_group_of(&self, node: NodeIndex) -> backend::RegGroup { self.graph.node_weight(node).unwrap().group } /// gets the temporary of a node pub fn get_temp_of(&self, node: NodeIndex) -> MuID { self.graph.node_weight(node).unwrap().temp } /// gets the spill cost of a node pub fn get_spill_cost(&self, node: NodeIndex) -> f32 { self.graph.node_weight(node).unwrap().spill_cost } /// are two nodes the same node? fn is_same_node(&self, node1: NodeIndex, node2: NodeIndex) -> bool { node1 == node2 } /// are two nodes from the same reg group? fn is_same_group(&self, node1: NodeIndex, node2: NodeIndex) -> bool { let node1 = self.graph.node_weight(node1).unwrap(); let node2 = self.graph.node_weight(node2).unwrap(); node1.group == node2.group } /// are two nodes adjacent? pub fn is_adj(&self, from: NodeIndex, to: NodeIndex) -> bool { self.is_interfered_with(from, to) } /// gets edges from a node pub fn get_edges_of(&self, node: NodeIndex) -> Vec { self.graph.neighbors(node).collect() } /// gets degree of a node (number of edges from the node) pub fn get_degree_of(&self, node: NodeIndex) -> usize { self.get_edges_of(node).len() } /// prints current graph for debugging (via trace log) pub fn print(&self, context: &FunctionContext) { use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Dot; use compiler::backend::reg_alloc::graph_coloring::petgraph::dot::Config; trace!(""); trace!("Interference Graph"); trace!("nodes:"); for id in self.nodes.keys() { let val = context.get_value(*id).unwrap().value(); trace!("Reg {} -> {:?}", val, self.nodes.get(&id).unwrap()); } trace!("moves:"); for mov in self.moves.iter() { trace!("Move {:?} -> {:?}", mov.from, mov.to); } trace!("graph:"); trace!( "\n\n{:?}\n", Dot::with_config(&self.graph, &[Config::EdgeNoLabel]) ); trace!(""); } } /// prints trace during building liveness for debugging? const TRACE_LIVENESS: bool = false; /// builds interference graph based on chaitin briggs algorithms /// (reference: Tailoring Graph-coloring Register Allocation For Runtime Compilation - CGO'06, Figure 4) pub fn build_interference_graph_chaitin_briggs( cf: &mut CompiledFunction, func: &MuFunctionVersion ) -> InterferenceGraph { let _p = hprof::enter("regalloc: build global liveness"); build_global_liveness(cf, func); drop(_p); let _p = hprof::enter("regalloc: build interference graph"); info!("---start building interference graph---"); let mut ig = InterferenceGraph::new(); // precolor machine register nodes for reg in backend::all_regs().values() { let reg_id = reg.extract_ssa_id().unwrap(); let node = ig.new_node(reg_id, &func.context); let precolor = backend::get_color_for_precolored(reg_id); ig.color_node(node, precolor); } // initialize and creates nodes for all the involved temps/regs for i in 0..cf.mc().number_of_insts() { for reg_id in cf.mc().get_inst_reg_defines(i) { ig.new_node(reg_id, &func.context); } for reg_id in cf.mc().get_inst_reg_uses(i) { ig.new_node(reg_id, &func.context); } } // for each basic block, insert interference edge while reversely traversing instructions for block in cf.mc().get_all_blocks() { // Current_Live(B) = LiveOut(B) let mut current_live = LinkedHashSet::from_vec(match cf.mc().get_ir_block_liveout(&block) { Some(liveout) => liveout.to_vec(), None => panic!("cannot find liveout for block {}", block) }); if TRACE_LIVENESS { trace!("Block{}: live out", block); for ele in current_live.iter() { trace!("{}", func.context.get_temp_display(*ele)); } } let range = cf.mc().get_block_range(&block); if range.is_none() { warn!("Block{}: has no range (no instructions?)", block); continue; } trace_if!( TRACE_LIVENESS, "Block{}: range = {:?}", block, range.as_ref().unwrap() ); // for every inst I in reverse order for i in range.unwrap().rev() { if TRACE_LIVENESS { trace!("Block{}: Inst{}", block, i); cf.mc().trace_inst(i); trace!("current live: "); for ele in current_live.iter() { trace!("{}", func.context.get_temp_display(*ele)); } } let src: Option = { if cf.mc().is_move(i) { let src = cf.mc().get_inst_reg_uses(i); let dst = cf.mc().get_inst_reg_defines(i); // src: reg/imm/mem // dest: reg/mem // we dont care if src/dest is mem if cf.mc().is_using_mem_op(i) { None } else { if src.len() == 1 { let node1 = ig.get_node(src[0]); let node2 = ig.get_node(dst[0]); trace_if!( TRACE_LIVENESS, "add move between {} and {}", func.context.get_temp_display(src[0]), func.context.get_temp_display(dst[0]) ); ig.add_move(node1, node2); Some(src[0]) } else { None } } } else { None } }; trace_if!(TRACE_LIVENESS, "Block{}: Inst{}: src={:?}", block, i, src); let defines = cf.mc().get_inst_reg_defines(i); for d in defines.iter() { current_live.insert(*d); } // for every definition D in I for d in defines { trace_if!( TRACE_LIVENESS, "Block{}: Inst{}: for definition {}", block, i, func.context.get_temp_display(d) ); // add an interference from D to every element E in Current_Live - {D} // creating nodes if necessary for e in current_live.iter() { trace_if!( TRACE_LIVENESS, "Block{}: Inst{}: for each live {}", block, i, func.context.get_temp_display(*e) ); if src.is_none() || (src.is_some() && *e != src.unwrap()) { let from = ig.get_node(d); let to = ig.get_node(*e); if !ig.is_same_node(from, to) && ig.is_same_group(from, to) && !ig.is_adj(from, to) { if !ig.is_colored(from) { trace_if!( TRACE_LIVENESS, "Block{}: Inst{}: add interference between {} and {}", block, i, func.context.get_temp_display(d), func.context.get_temp_display(*e) ); ig.add_interference_edge(from, to); } if !ig.is_colored(to) { trace_if!( TRACE_LIVENESS, "Block{}: Inst{}: add interference between {} and {}", block, i, func.context.get_temp_display(*e), func.context.get_temp_display(d) ); ig.add_interference_edge(to, from); } } } } } // for every definition D in I for d in cf.mc().get_inst_reg_defines(i) { trace_if!( TRACE_LIVENESS, "Block{}: Inst{}: remove define {} from current_live", block, i, func.context.get_temp_display(d) ); // remove D from Current_Live current_live.remove(&d); } // for every use U in I for u in cf.mc().get_inst_reg_uses(i) { trace_if!( TRACE_LIVENESS, "Block{}: Inst{}: add use {} to current_live", block, i, func.context.get_temp_display(u) ); // add U to Current_live current_live.insert(u); } if TRACE_LIVENESS { trace!("Block{}: Inst{}: done. current_live:", block, i); for ele in current_live.iter() { trace!("{}", func.context.get_temp_display(*ele)); } } } } drop(_p); info!("---finish building interference graph---"); ig } /// builds global liveness for a compiled function fn build_global_liveness(cf: &mut CompiledFunction, func: &MuFunctionVersion) { info!("---start building live set---"); // build control flow graphs, treat a whole block as one node in the graph let cfg = build_cfg_nodes(cf); // do liveness analysis global_liveness_analysis(cfg, cf, func); info!("---finish building live set---"); } /// CFGBlockNode represents a basic block as a whole for global liveness analysis #[derive(Clone, Debug)] struct CFGBlockNode { block: String, pred: Vec, succ: Vec, uses: Vec, defs: Vec } /// builds a LinkedHashMap from basic block names to CFGBlockNode /// We need to collect for each basic block: /// * predecessors /// * successors /// * uses /// * defs fn build_cfg_nodes(cf: &mut CompiledFunction) -> LinkedHashMap { info!("---local liveness analysis---"); let mc = cf.mc(); let mut ret = LinkedHashMap::new(); let all_blocks = mc.get_all_blocks(); // create maps (start_inst -> name) and (end_inst -> name) // we will use it to find basic blocks when given a inst index let (start_inst_map, end_inst_map) = { let mut start_inst_map: LinkedHashMap = LinkedHashMap::new(); let mut end_inst_map: LinkedHashMap = LinkedHashMap::new(); for block in all_blocks.iter() { let range = match mc.get_block_range(block) { Some(range) => range, None => panic!("cannot find range for block {}", block) }; // start inst let first_inst = range.start; // last inst (we need to skip symbols) let last_inst = match mc.get_last_inst(range.end) { Some(last) => last, None => { panic!( "cannot find last instruction in block {}, this block contains no instruction?", block ) } }; trace_if!( TRACE_LIVENESS, "Block {}: start_inst={}, end_inst(inclusive)={}", block, first_inst, last_inst ); start_inst_map.insert(first_inst, block); end_inst_map.insert(last_inst, block); } (start_inst_map, end_inst_map) }; // collect info for each basic block for block in mc.get_all_blocks().iter() { trace_if!(TRACE_LIVENESS, "---block {}---", block); let range = mc.get_block_range(block).unwrap(); let start_inst = range.start; let end = range.end; // livein set of this block is what temps this block uses from other blocks // defs is what temps this block defines in the block let (livein, defs) = { // we gradually build livein let mut livein = vec![]; // we need to know all temporaries defined in the block // if a temporary is not defined in this block, it is a livein for this block let mut all_defined: LinkedHashSet = LinkedHashSet::new(); for i in start_inst..end { let reg_uses = mc.get_inst_reg_uses(i); // if a reg is used but not defined before, it is a live-in for reg in reg_uses { if !all_defined.contains(®) { livein.push(reg); } } let reg_defs = mc.get_inst_reg_defines(i); for reg in reg_defs { all_defined.insert(reg); } } let defs: Vec = all_defined.iter().map(|x| *x).collect(); (livein, defs) }; let preds: Vec = { let mut ret = vec![]; // predecessors of the first instruction is the predecessors of this block for pred in mc.get_preds(start_inst).into_iter() { match end_inst_map.get(pred) { Some(str) => ret.push(String::from(*str)), None => {} } } ret }; let succs: Vec = { let mut ret = vec![]; // successors of the last instruction is the successors of this block for succ in mc.get_succs(mc.get_last_inst(end).unwrap()).into_iter() { match start_inst_map.get(succ) { Some(str) => ret.push(String::from(*str)), None => {} } } ret }; let node = CFGBlockNode { block: block.clone(), pred: preds, succ: succs, uses: livein, defs: defs }; trace_if!(TRACE_LIVENESS, "as CFGNode {:?}", node); ret.insert(block.clone(), node); } ret } /// global analysis, the iterative algorithm to compute livenss until livein/out reaches a fix point fn global_liveness_analysis( blocks: LinkedHashMap, cf: &mut CompiledFunction, func: &MuFunctionVersion ) { info!("---global liveness analysis---"); info!("{} blocks", blocks.len()); // init live in and live out let mut livein: LinkedHashMap> = { let mut ret = LinkedHashMap::new(); for name in blocks.keys() { ret.insert(name.clone(), LinkedHashSet::new()); } ret }; let mut liveout: LinkedHashMap> = { let mut ret = LinkedHashMap::new(); for name in blocks.keys() { ret.insert(name.clone(), LinkedHashSet::new()); } ret }; // is the result changed in this iteration? let mut is_changed = true; // record iteration count let mut i = 0; while is_changed { trace_if!(TRACE_LIVENESS, "---iteration {}---", i); i += 1; // reset is_changed = false; for node in blocks.keys() { let cfg_node = blocks.get(node).unwrap(); // old livein/out let in_set_old = livein.get(node).unwrap().clone(); let out_set_old = liveout.get(node).unwrap().clone(); // in <- use + (out - def) { let mut inset = livein.get_mut(node).unwrap(); inset.clear(); // (1) out - def inset.add_all(liveout.get(node).unwrap().clone()); for def in cfg_node.defs.iter() { inset.remove(def); } // (2) in + (out - def) for in_reg in cfg_node.uses.iter() { inset.insert(*in_reg); } } // out[n] <- union(in[s] for every successor s of n) { let mut outset = liveout.get_mut(node).unwrap(); outset.clear(); for s in cfg_node.succ.iter() { outset.add_all(livein.get(s).unwrap().clone()); } } // is in/out changed in this iteration? let n_changed = !in_set_old.equals(livein.get(node).unwrap()) || !out_set_old.equals(liveout.get(node).unwrap()); if TRACE_LIVENESS { trace!("block {}", node); trace!("in(old) = {:?}", in_set_old); trace!("in(new) = {:?}", livein.get(node).unwrap()); trace!("out(old) = {:?}", out_set_old); trace!("out(new) = {:?}", liveout.get(node).unwrap()); } is_changed = is_changed || n_changed; } } info!("finished in {} iterations", i); // set live in and live out for block in blocks.keys() { let livein: Vec = livein .get(block) .unwrap() .clone() .iter() .map(|x| *x) .collect(); if TRACE_LIVENESS { let display_array: Vec = livein .iter() .map(|x| func.context.get_temp_display(*x)) .collect(); trace!("livein for block {}: {:?}", block, display_array); } cf.mc_mut().set_ir_block_livein(block, livein); let liveout: Vec = liveout .get(block) .unwrap() .clone() .iter() .map(|x| *x) .collect(); if TRACE_LIVENESS { let display_array: Vec = liveout .iter() .map(|x| func.context.get_temp_display(*x)) .collect(); trace!("liveout for block {}: {:?}", block, display_array); } cf.mc_mut().set_ir_block_liveout(block, liveout); } }