use cursor::{Cursor, FuncCursor};
use dominator_tree::DominatorTree;
use entity::{EntityList, ListPool};
use flowgraph::ControlFlowGraph;
use ir::{DataFlowGraph, Ebb, Function, Inst, InstBuilder, Layout, Opcode, Type, Value};
use loop_analysis::{Loop, LoopAnalysis};
use std::collections::HashSet;
use std::vec::Vec;
use timing;
pub fn do_licm(
func: &mut Function,
cfg: &mut ControlFlowGraph,
domtree: &mut DominatorTree,
loop_analysis: &mut LoopAnalysis,
) {
let _tt = timing::licm();
debug_assert!(cfg.is_valid());
debug_assert!(domtree.is_valid());
debug_assert!(loop_analysis.is_valid());
for lp in loop_analysis.loops() {
let invariant_insts = remove_loop_invariant_instructions(lp, func, cfg, loop_analysis);
if !invariant_insts.is_empty() {
let mut pos;
match has_pre_header(&func.layout, cfg, domtree, loop_analysis.loop_header(lp)) {
None => {
let pre_header =
create_pre_header(loop_analysis.loop_header(lp), func, cfg, domtree);
pos = FuncCursor::new(func).at_last_inst(pre_header);
}
Some((_, last_inst)) => {
pos = FuncCursor::new(func).at_inst(last_inst);
}
};
for inst in invariant_insts {
pos.insert_inst(inst);
}
}
}
cfg.compute(func);
domtree.compute(func, cfg);
}
fn create_pre_header(
header: Ebb,
func: &mut Function,
cfg: &mut ControlFlowGraph,
domtree: &DominatorTree,
) -> Ebb {
let pool = &mut ListPool::<Value>::new();
let header_args_values: Vec<Value> = func.dfg.ebb_params(header).into_iter().cloned().collect();
let header_args_types: Vec<Type> = header_args_values
.clone()
.into_iter()
.map(|val| func.dfg.value_type(val))
.collect();
let pre_header = func.dfg.make_ebb();
let mut pre_header_args_value: EntityList<Value> = EntityList::new();
for typ in header_args_types {
pre_header_args_value.push(func.dfg.append_ebb_param(pre_header, typ), pool);
}
for (_, last_inst) in cfg.pred_iter(header) {
if !domtree.dominates(header, last_inst, &func.layout) {
change_branch_jump_destination(last_inst, pre_header, func);
}
}
{
let mut pos = FuncCursor::new(func).at_top(header);
pos.insert_ebb(pre_header);
pos.next_inst();
pos.ins().jump(header, pre_header_args_value.as_slice(pool));
}
pre_header
}
fn has_pre_header(
layout: &Layout,
cfg: &ControlFlowGraph,
domtree: &DominatorTree,
header: Ebb,
) -> Option<(Ebb, Inst)> {
let mut result = None;
let mut found = false;
for (pred_ebb, last_inst) in cfg.pred_iter(header) {
if !domtree.dominates(header, last_inst, layout) {
if found {
return None;
} else {
result = Some((pred_ebb, last_inst));
found = true;
}
}
}
result
}
fn change_branch_jump_destination(inst: Inst, new_ebb: Ebb, func: &mut Function) {
match func.dfg[inst].branch_destination_mut() {
None => (),
Some(instruction_dest) => *instruction_dest = new_ebb,
}
}
fn trivially_unsafe_for_licm(opcode: Opcode) -> bool {
opcode.can_load() || opcode.can_store() || opcode.is_call() || opcode.is_branch() ||
opcode.is_terminator() || opcode.is_return() ||
opcode.can_trap() || opcode.other_side_effects() || opcode.writes_cpu_flags()
}
fn is_loop_invariant(inst: Inst, dfg: &DataFlowGraph, loop_values: &HashSet<Value>) -> bool {
if trivially_unsafe_for_licm(dfg[inst].opcode()) {
return false;
}
let inst_args = dfg.inst_args(inst);
for arg in inst_args {
let arg = dfg.resolve_aliases(*arg);
if loop_values.contains(&arg) {
return false;
}
}
true
}
fn remove_loop_invariant_instructions(
lp: Loop,
func: &mut Function,
cfg: &ControlFlowGraph,
loop_analysis: &LoopAnalysis,
) -> Vec<Inst> {
let mut loop_values: HashSet<Value> = HashSet::new();
let mut invariant_insts: Vec<Inst> = Vec::new();
let mut pos = FuncCursor::new(func);
for ebb in postorder_ebbs_loop(loop_analysis, cfg, lp).iter().rev() {
for val in pos.func.dfg.ebb_params(*ebb) {
loop_values.insert(*val);
}
pos.goto_top(*ebb);
#[cfg_attr(feature = "cargo-clippy", allow(block_in_if_condition_stmt))]
while let Some(inst) = pos.next_inst() {
if is_loop_invariant(inst, &pos.func.dfg, &loop_values) {
invariant_insts.push(inst);
pos.remove_inst_and_step_back();
} else {
for out in pos.func.dfg.inst_results(inst) {
loop_values.insert(*out);
}
}
}
}
invariant_insts
}
fn postorder_ebbs_loop(loop_analysis: &LoopAnalysis, cfg: &ControlFlowGraph, lp: Loop) -> Vec<Ebb> {
let mut grey = HashSet::new();
let mut black = HashSet::new();
let mut stack = vec![loop_analysis.loop_header(lp)];
let mut postorder = Vec::new();
while !stack.is_empty() {
let node = stack.pop().unwrap();
if !grey.contains(&node) {
grey.insert(node);
stack.push(node);
for child in cfg.succ_iter(node) {
if loop_analysis.is_in_loop(child, lp) && !grey.contains(&child) {
stack.push(child);
}
}
} else if !black.contains(&node) {
postorder.push(node);
black.insert(node);
}
}
postorder
}