use crate::cursor::{Cursor, FuncCursor};
use crate::dominator_tree::DominatorTree;
use crate::entity::{EntityList, ListPool};
use crate::flowgraph::{BlockPredecessor, ControlFlowGraph};
use crate::fx::FxHashSet;
use crate::ir::{
Block, DataFlowGraph, Function, Inst, InstBuilder, InstructionData, Layout, Opcode, Type, Value,
};
use crate::loop_analysis::{Loop, LoopAnalysis};
use crate::timing;
use alloc::vec::Vec;
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: Block,
func: &mut Function,
cfg: &mut ControlFlowGraph,
domtree: &DominatorTree,
) -> Block {
let pool = &mut ListPool::<Value>::new();
let header_args_values = func.dfg.block_params(header).to_vec();
let header_args_types: Vec<Type> = header_args_values
.into_iter()
.map(|val| func.dfg.value_type(val))
.collect();
let pre_header = func.dfg.make_block();
let mut pre_header_args_value: EntityList<Value> = EntityList::new();
for typ in header_args_types {
pre_header_args_value.push(func.dfg.append_block_param(pre_header, typ), pool);
}
for BlockPredecessor {
inst: last_inst, ..
} in cfg.pred_iter(header)
{
if !domtree.dominates(header, last_inst, &func.layout) {
func.rewrite_branch_destination(last_inst, header, pre_header);
}
}
let mut pos = FuncCursor::new(func).at_top(header);
pos.insert_block(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: Block,
) -> Option<(Block, Inst)> {
let mut result = None;
for BlockPredecessor {
block: pred_block,
inst: branch_inst,
} in cfg.pred_iter(header)
{
if !domtree.dominates(header, branch_inst, layout) {
if result.is_some() {
return None;
}
if branch_inst != layout.last_inst(pred_block).unwrap()
|| cfg.succ_iter(pred_block).nth(1).is_some()
{
return None;
}
result = Some((pred_block, branch_inst));
}
}
result
}
fn trivially_unsafe_for_licm(opcode: Opcode) -> bool {
opcode.can_store()
|| opcode.is_call()
|| opcode.is_branch()
|| opcode.is_terminator()
|| opcode.is_return()
|| opcode.can_trap()
|| opcode.other_side_effects()
}
fn is_unsafe_load(inst_data: &InstructionData) -> bool {
match *inst_data {
InstructionData::Load { flags, .. } => !flags.readonly() || !flags.notrap(),
_ => inst_data.opcode().can_load(),
}
}
fn is_loop_invariant(inst: Inst, dfg: &DataFlowGraph, loop_values: &FxHashSet<Value>) -> bool {
if trivially_unsafe_for_licm(dfg.insts[inst].opcode()) {
return false;
}
if is_unsafe_load(&dfg.insts[inst]) {
return false;
}
for arg in dfg.inst_values(inst) {
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: FxHashSet<Value> = FxHashSet();
let mut invariant_insts: Vec<Inst> = Vec::new();
let mut pos = FuncCursor::new(func);
for block in postorder_blocks_loop(loop_analysis, cfg, lp).iter().rev() {
for val in pos.func.dfg.block_params(*block) {
loop_values.insert(*val);
}
pos.goto_top(*block);
#[cfg_attr(feature = "cargo-clippy", allow(clippy::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_blocks_loop(
loop_analysis: &LoopAnalysis,
cfg: &ControlFlowGraph,
lp: Loop,
) -> Vec<Block> {
let mut grey = FxHashSet();
let mut black = FxHashSet();
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
}