1 //! A Loop Invariant Code Motion optimization pass
2
3 use crate::cursor::{Cursor, EncCursor, FuncCursor};
4 use crate::dominator_tree::DominatorTree;
5 use crate::entity::{EntityList, ListPool};
6 use crate::flowgraph::{BlockPredecessor, ControlFlowGraph};
7 use crate::fx::FxHashSet;
8 use crate::ir::{
9 Block, DataFlowGraph, Function, Inst, InstBuilder, InstructionData, Layout, Opcode, Type, Value,
10 };
11 use crate::isa::TargetIsa;
12 use crate::loop_analysis::{Loop, LoopAnalysis};
13 use crate::timing;
14 use alloc::vec::Vec;
15
16 /// Performs the LICM pass by detecting loops within the CFG and moving
17 /// loop-invariant instructions out of them.
18 /// Changes the CFG and domtree in-place during the operation.
do_licm( isa: &dyn TargetIsa, func: &mut Function, cfg: &mut ControlFlowGraph, domtree: &mut DominatorTree, loop_analysis: &mut LoopAnalysis, )19 pub fn do_licm(
20 isa: &dyn TargetIsa,
21 func: &mut Function,
22 cfg: &mut ControlFlowGraph,
23 domtree: &mut DominatorTree,
24 loop_analysis: &mut LoopAnalysis,
25 ) {
26 let _tt = timing::licm();
27 debug_assert!(cfg.is_valid());
28 debug_assert!(domtree.is_valid());
29 debug_assert!(loop_analysis.is_valid());
30
31 for lp in loop_analysis.loops() {
32 // For each loop that we want to optimize we determine the set of loop-invariant
33 // instructions
34 let invariant_insts = remove_loop_invariant_instructions(lp, func, cfg, loop_analysis);
35 // Then we create the loop's pre-header and fill it with the invariant instructions
36 // Then we remove the invariant instructions from the loop body
37 if !invariant_insts.is_empty() {
38 // If the loop has a natural pre-header we use it, otherwise we create it.
39 let mut pos;
40 match has_pre_header(&func.layout, cfg, domtree, loop_analysis.loop_header(lp)) {
41 None => {
42 let pre_header =
43 create_pre_header(isa, loop_analysis.loop_header(lp), func, cfg, domtree);
44 pos = FuncCursor::new(func).at_last_inst(pre_header);
45 }
46 // If there is a natural pre-header we insert new instructions just before the
47 // related jumping instruction (which is not necessarily at the end).
48 Some((_, last_inst)) => {
49 pos = FuncCursor::new(func).at_inst(last_inst);
50 }
51 };
52 // The last instruction of the pre-header is the termination instruction (usually
53 // a jump) so we need to insert just before this.
54 for inst in invariant_insts {
55 pos.insert_inst(inst);
56 }
57 }
58 }
59 // We have to recompute the domtree to account for the changes
60 cfg.compute(func);
61 domtree.compute(func, cfg);
62 }
63
64 // Insert a pre-header before the header, modifying the function layout and CFG to reflect it.
65 // A jump instruction to the header is placed at the end of the pre-header.
create_pre_header( isa: &dyn TargetIsa, header: Block, func: &mut Function, cfg: &mut ControlFlowGraph, domtree: &DominatorTree, ) -> Block66 fn create_pre_header(
67 isa: &dyn TargetIsa,
68 header: Block,
69 func: &mut Function,
70 cfg: &mut ControlFlowGraph,
71 domtree: &DominatorTree,
72 ) -> Block {
73 let pool = &mut ListPool::<Value>::new();
74 let header_args_values = func.dfg.block_params(header).to_vec();
75 let header_args_types: Vec<Type> = header_args_values
76 .into_iter()
77 .map(|val| func.dfg.value_type(val))
78 .collect();
79 let pre_header = func.dfg.make_block();
80 let mut pre_header_args_value: EntityList<Value> = EntityList::new();
81 for typ in header_args_types {
82 pre_header_args_value.push(func.dfg.append_block_param(pre_header, typ), pool);
83 }
84 for BlockPredecessor {
85 inst: last_inst, ..
86 } in cfg.pred_iter(header)
87 {
88 // We only follow normal edges (not the back edges)
89 if !domtree.dominates(header, last_inst, &func.layout) {
90 func.change_branch_destination(last_inst, pre_header);
91 }
92 }
93 {
94 let mut pos = EncCursor::new(func, isa).at_top(header);
95 // Inserts the pre-header at the right place in the layout.
96 pos.insert_block(pre_header);
97 pos.next_inst();
98 pos.ins().jump(header, pre_header_args_value.as_slice(pool));
99 }
100 pre_header
101 }
102
103 // Detects if a loop header has a natural pre-header.
104 //
105 // A loop header has a pre-header if there is only one predecessor that the header doesn't
106 // dominate.
107 // Returns the pre-header Block and the instruction jumping to the header.
has_pre_header( layout: &Layout, cfg: &ControlFlowGraph, domtree: &DominatorTree, header: Block, ) -> Option<(Block, Inst)>108 fn has_pre_header(
109 layout: &Layout,
110 cfg: &ControlFlowGraph,
111 domtree: &DominatorTree,
112 header: Block,
113 ) -> Option<(Block, Inst)> {
114 let mut result = None;
115 for BlockPredecessor {
116 block: pred_block,
117 inst: branch_inst,
118 } in cfg.pred_iter(header)
119 {
120 // We only count normal edges (not the back edges)
121 if !domtree.dominates(header, branch_inst, layout) {
122 if result.is_some() {
123 // We have already found one, there are more than one
124 return None;
125 }
126 if branch_inst != layout.last_inst(pred_block).unwrap()
127 || cfg.succ_iter(pred_block).nth(1).is_some()
128 {
129 // It's along a critical edge, so don't use it.
130 return None;
131 }
132 result = Some((pred_block, branch_inst));
133 }
134 }
135 result
136 }
137
138 /// Test whether the given opcode is unsafe to even consider for LICM.
trivially_unsafe_for_licm(opcode: Opcode) -> bool139 fn trivially_unsafe_for_licm(opcode: Opcode) -> bool {
140 opcode.can_store()
141 || opcode.is_call()
142 || opcode.is_branch()
143 || opcode.is_terminator()
144 || opcode.is_return()
145 || opcode.can_trap()
146 || opcode.other_side_effects()
147 || opcode.writes_cpu_flags()
148 }
149
is_unsafe_load(inst_data: &InstructionData) -> bool150 fn is_unsafe_load(inst_data: &InstructionData) -> bool {
151 match *inst_data {
152 InstructionData::Load { flags, .. } | InstructionData::LoadComplex { flags, .. } => {
153 !flags.readonly() || !flags.notrap()
154 }
155 _ => inst_data.opcode().can_load(),
156 }
157 }
158
159 /// Test whether the given instruction is loop-invariant.
is_loop_invariant(inst: Inst, dfg: &DataFlowGraph, loop_values: &FxHashSet<Value>) -> bool160 fn is_loop_invariant(inst: Inst, dfg: &DataFlowGraph, loop_values: &FxHashSet<Value>) -> bool {
161 if trivially_unsafe_for_licm(dfg[inst].opcode()) {
162 return false;
163 }
164
165 if is_unsafe_load(&dfg[inst]) {
166 return false;
167 }
168
169 let inst_args = dfg.inst_args(inst);
170 for arg in inst_args {
171 let arg = dfg.resolve_aliases(*arg);
172 if loop_values.contains(&arg) {
173 return false;
174 }
175 }
176 true
177 }
178
179 // Traverses a loop in reverse post-order from a header block and identify loop-invariant
180 // instructions. These loop-invariant instructions are then removed from the code and returned
181 // (in reverse post-order) for later use.
remove_loop_invariant_instructions( lp: Loop, func: &mut Function, cfg: &ControlFlowGraph, loop_analysis: &LoopAnalysis, ) -> Vec<Inst>182 fn remove_loop_invariant_instructions(
183 lp: Loop,
184 func: &mut Function,
185 cfg: &ControlFlowGraph,
186 loop_analysis: &LoopAnalysis,
187 ) -> Vec<Inst> {
188 let mut loop_values: FxHashSet<Value> = FxHashSet();
189 let mut invariant_insts: Vec<Inst> = Vec::new();
190 let mut pos = FuncCursor::new(func);
191 // We traverse the loop block in reverse post-order.
192 for block in postorder_blocks_loop(loop_analysis, cfg, lp).iter().rev() {
193 // Arguments of the block are loop values
194 for val in pos.func.dfg.block_params(*block) {
195 loop_values.insert(*val);
196 }
197 pos.goto_top(*block);
198 #[cfg_attr(feature = "cargo-clippy", allow(clippy::block_in_if_condition_stmt))]
199 while let Some(inst) = pos.next_inst() {
200 if is_loop_invariant(inst, &pos.func.dfg, &loop_values) {
201 // If all the instruction's argument are defined outside the loop
202 // then this instruction is loop-invariant
203 invariant_insts.push(inst);
204 // We remove it from the loop
205 pos.remove_inst_and_step_back();
206 } else {
207 // If the instruction is not loop-invariant we push its results in the set of
208 // loop values
209 for out in pos.func.dfg.inst_results(inst) {
210 loop_values.insert(*out);
211 }
212 }
213 }
214 }
215 invariant_insts
216 }
217
218 /// Return blocks from a loop in post-order, starting from an entry point in the block.
postorder_blocks_loop( loop_analysis: &LoopAnalysis, cfg: &ControlFlowGraph, lp: Loop, ) -> Vec<Block>219 fn postorder_blocks_loop(
220 loop_analysis: &LoopAnalysis,
221 cfg: &ControlFlowGraph,
222 lp: Loop,
223 ) -> Vec<Block> {
224 let mut grey = FxHashSet();
225 let mut black = FxHashSet();
226 let mut stack = vec![loop_analysis.loop_header(lp)];
227 let mut postorder = Vec::new();
228
229 while !stack.is_empty() {
230 let node = stack.pop().unwrap();
231 if !grey.contains(&node) {
232 // This is a white node. Mark it as gray.
233 grey.insert(node);
234 stack.push(node);
235 // Get any children we've never seen before.
236 for child in cfg.succ_iter(node) {
237 if loop_analysis.is_in_loop(child, lp) && !grey.contains(&child) {
238 stack.push(child);
239 }
240 }
241 } else if !black.contains(&node) {
242 postorder.push(node);
243 black.insert(node);
244 }
245 }
246 postorder
247 }
248