File: | lib/Transforms/Scalar/LoopUnswitch.cpp |
Location: | line 420, column 5 |
Description: | Forming reference to null pointer |
1 | //===-- LoopUnswitch.cpp - Hoist loop-invariant conditionals in loop ------===// | |||||
2 | // | |||||
3 | // The LLVM Compiler Infrastructure | |||||
4 | // | |||||
5 | // This file is distributed under the University of Illinois Open Source | |||||
6 | // License. See LICENSE.TXT for details. | |||||
7 | // | |||||
8 | //===----------------------------------------------------------------------===// | |||||
9 | // | |||||
10 | // This pass transforms loops that contain branches on loop-invariant conditions | |||||
11 | // to have multiple loops. For example, it turns the left into the right code: | |||||
12 | // | |||||
13 | // for (...) if (lic) | |||||
14 | // A for (...) | |||||
15 | // if (lic) A; B; C | |||||
16 | // B else | |||||
17 | // C for (...) | |||||
18 | // A; C | |||||
19 | // | |||||
20 | // This can increase the size of the code exponentially (doubling it every time | |||||
21 | // a loop is unswitched) so we only unswitch if the resultant code will be | |||||
22 | // smaller than a threshold. | |||||
23 | // | |||||
24 | // This pass expects LICM to be run before it to hoist invariant conditions out | |||||
25 | // of the loop, to make the unswitching opportunity obvious. | |||||
26 | // | |||||
27 | //===----------------------------------------------------------------------===// | |||||
28 | ||||||
29 | #include "llvm/Transforms/Scalar.h" | |||||
30 | #include "llvm/ADT/STLExtras.h" | |||||
31 | #include "llvm/ADT/SmallPtrSet.h" | |||||
32 | #include "llvm/ADT/Statistic.h" | |||||
33 | #include "llvm/Analysis/AssumptionCache.h" | |||||
34 | #include "llvm/Analysis/CodeMetrics.h" | |||||
35 | #include "llvm/Analysis/InstructionSimplify.h" | |||||
36 | #include "llvm/Analysis/LoopInfo.h" | |||||
37 | #include "llvm/Analysis/LoopPass.h" | |||||
38 | #include "llvm/Analysis/ScalarEvolution.h" | |||||
39 | #include "llvm/Analysis/TargetTransformInfo.h" | |||||
40 | #include "llvm/IR/Constants.h" | |||||
41 | #include "llvm/IR/DerivedTypes.h" | |||||
42 | #include "llvm/IR/Dominators.h" | |||||
43 | #include "llvm/IR/Function.h" | |||||
44 | #include "llvm/IR/Instructions.h" | |||||
45 | #include "llvm/IR/Module.h" | |||||
46 | #include "llvm/IR/MDBuilder.h" | |||||
47 | #include "llvm/Support/CommandLine.h" | |||||
48 | #include "llvm/Support/Debug.h" | |||||
49 | #include "llvm/Support/raw_ostream.h" | |||||
50 | #include "llvm/Transforms/Utils/BasicBlockUtils.h" | |||||
51 | #include "llvm/Transforms/Utils/Cloning.h" | |||||
52 | #include "llvm/Transforms/Utils/Local.h" | |||||
53 | #include <algorithm> | |||||
54 | #include <map> | |||||
55 | #include <set> | |||||
56 | using namespace llvm; | |||||
57 | ||||||
58 | #define DEBUG_TYPE"loop-unswitch" "loop-unswitch" | |||||
59 | ||||||
60 | STATISTIC(NumBranches, "Number of branches unswitched")static llvm::Statistic NumBranches = { "loop-unswitch", "Number of branches unswitched" , 0, 0 }; | |||||
61 | STATISTIC(NumSwitches, "Number of switches unswitched")static llvm::Statistic NumSwitches = { "loop-unswitch", "Number of switches unswitched" , 0, 0 }; | |||||
62 | STATISTIC(NumSelects , "Number of selects unswitched")static llvm::Statistic NumSelects = { "loop-unswitch", "Number of selects unswitched" , 0, 0 }; | |||||
63 | STATISTIC(NumTrivial , "Number of unswitches that are trivial")static llvm::Statistic NumTrivial = { "loop-unswitch", "Number of unswitches that are trivial" , 0, 0 }; | |||||
64 | STATISTIC(NumSimplify, "Number of simplifications of unswitched code")static llvm::Statistic NumSimplify = { "loop-unswitch", "Number of simplifications of unswitched code" , 0, 0 }; | |||||
65 | STATISTIC(TotalInsts, "Total number of instructions analyzed")static llvm::Statistic TotalInsts = { "loop-unswitch", "Total number of instructions analyzed" , 0, 0 }; | |||||
66 | ||||||
67 | // The specific value of 100 here was chosen based only on intuition and a | |||||
68 | // few specific examples. | |||||
69 | static cl::opt<unsigned> | |||||
70 | Threshold("loop-unswitch-threshold", cl::desc("Max loop size to unswitch"), | |||||
71 | cl::init(100), cl::Hidden); | |||||
72 | ||||||
73 | namespace { | |||||
74 | ||||||
75 | class LUAnalysisCache { | |||||
76 | ||||||
77 | typedef DenseMap<const SwitchInst*, SmallPtrSet<const Value *, 8> > | |||||
78 | UnswitchedValsMap; | |||||
79 | ||||||
80 | typedef UnswitchedValsMap::iterator UnswitchedValsIt; | |||||
81 | ||||||
82 | struct LoopProperties { | |||||
83 | unsigned CanBeUnswitchedCount; | |||||
84 | unsigned WasUnswitchedCount; | |||||
85 | unsigned SizeEstimation; | |||||
86 | UnswitchedValsMap UnswitchedVals; | |||||
87 | }; | |||||
88 | ||||||
89 | // Here we use std::map instead of DenseMap, since we need to keep valid | |||||
90 | // LoopProperties pointer for current loop for better performance. | |||||
91 | typedef std::map<const Loop*, LoopProperties> LoopPropsMap; | |||||
92 | typedef LoopPropsMap::iterator LoopPropsMapIt; | |||||
93 | ||||||
94 | LoopPropsMap LoopsProperties; | |||||
95 | UnswitchedValsMap *CurLoopInstructions; | |||||
96 | LoopProperties *CurrentLoopProperties; | |||||
97 | ||||||
98 | // A loop unswitching with an estimated cost above this threshold | |||||
99 | // is not performed. MaxSize is turned into unswitching quota for | |||||
100 | // the current loop, and reduced correspondingly, though note that | |||||
101 | // the quota is returned by releaseMemory() when the loop has been | |||||
102 | // processed, so that MaxSize will return to its previous | |||||
103 | // value. So in most cases MaxSize will equal the Threshold flag | |||||
104 | // when a new loop is processed. An exception to that is that | |||||
105 | // MaxSize will have a smaller value while processing nested loops | |||||
106 | // that were introduced due to loop unswitching of an outer loop. | |||||
107 | // | |||||
108 | // FIXME: The way that MaxSize works is subtle and depends on the | |||||
109 | // pass manager processing loops and calling releaseMemory() in a | |||||
110 | // specific order. It would be good to find a more straightforward | |||||
111 | // way of doing what MaxSize does. | |||||
112 | unsigned MaxSize; | |||||
113 | ||||||
114 | public: | |||||
115 | LUAnalysisCache() | |||||
116 | : CurLoopInstructions(nullptr), CurrentLoopProperties(nullptr), | |||||
117 | MaxSize(Threshold) {} | |||||
118 | ||||||
119 | // Analyze loop. Check its size, calculate is it possible to unswitch | |||||
120 | // it. Returns true if we can unswitch this loop. | |||||
121 | bool countLoop(const Loop *L, const TargetTransformInfo &TTI, | |||||
122 | AssumptionCache *AC); | |||||
123 | ||||||
124 | // Clean all data related to given loop. | |||||
125 | void forgetLoop(const Loop *L); | |||||
126 | ||||||
127 | // Mark case value as unswitched. | |||||
128 | // Since SI instruction can be partly unswitched, in order to avoid | |||||
129 | // extra unswitching in cloned loops keep track all unswitched values. | |||||
130 | void setUnswitched(const SwitchInst *SI, const Value *V); | |||||
131 | ||||||
132 | // Check was this case value unswitched before or not. | |||||
133 | bool isUnswitched(const SwitchInst *SI, const Value *V); | |||||
134 | ||||||
135 | // Returns true if another unswitching could be done within the cost | |||||
136 | // threshold. | |||||
137 | bool CostAllowsUnswitching(); | |||||
138 | ||||||
139 | // Clone all loop-unswitch related loop properties. | |||||
140 | // Redistribute unswitching quotas. | |||||
141 | // Note, that new loop data is stored inside the VMap. | |||||
142 | void cloneData(const Loop *NewLoop, const Loop *OldLoop, | |||||
143 | const ValueToValueMapTy &VMap); | |||||
144 | }; | |||||
145 | ||||||
146 | class LoopUnswitch : public LoopPass { | |||||
147 | LoopInfo *LI; // Loop information | |||||
148 | LPPassManager *LPM; | |||||
149 | AssumptionCache *AC; | |||||
150 | ||||||
151 | // Used to check if second loop needs processing after | |||||
152 | // RewriteLoopBodyWithConditionConstant rewrites first loop. | |||||
153 | std::vector<Loop*> LoopProcessWorklist; | |||||
154 | ||||||
155 | LUAnalysisCache BranchesInfo; | |||||
156 | ||||||
157 | bool OptimizeForSize; | |||||
158 | bool redoLoop; | |||||
159 | ||||||
160 | Loop *currentLoop; | |||||
161 | DominatorTree *DT; | |||||
162 | BasicBlock *loopHeader; | |||||
163 | BasicBlock *loopPreheader; | |||||
164 | ||||||
165 | // LoopBlocks contains all of the basic blocks of the loop, including the | |||||
166 | // preheader of the loop, the body of the loop, and the exit blocks of the | |||||
167 | // loop, in that order. | |||||
168 | std::vector<BasicBlock*> LoopBlocks; | |||||
169 | // NewBlocks contained cloned copy of basic blocks from LoopBlocks. | |||||
170 | std::vector<BasicBlock*> NewBlocks; | |||||
171 | ||||||
172 | public: | |||||
173 | static char ID; // Pass ID, replacement for typeid | |||||
174 | explicit LoopUnswitch(bool Os = false) : | |||||
175 | LoopPass(ID), OptimizeForSize(Os), redoLoop(false), | |||||
176 | currentLoop(nullptr), DT(nullptr), loopHeader(nullptr), | |||||
177 | loopPreheader(nullptr) { | |||||
178 | initializeLoopUnswitchPass(*PassRegistry::getPassRegistry()); | |||||
179 | } | |||||
180 | ||||||
181 | bool runOnLoop(Loop *L, LPPassManager &LPM) override; | |||||
182 | bool processCurrentLoop(); | |||||
183 | ||||||
184 | /// This transformation requires natural loop information & requires that | |||||
185 | /// loop preheaders be inserted into the CFG. | |||||
186 | /// | |||||
187 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||||
188 | AU.addRequired<AssumptionCacheTracker>(); | |||||
189 | AU.addRequiredID(LoopSimplifyID); | |||||
190 | AU.addPreservedID(LoopSimplifyID); | |||||
191 | AU.addRequired<LoopInfoWrapperPass>(); | |||||
192 | AU.addPreserved<LoopInfoWrapperPass>(); | |||||
193 | AU.addRequiredID(LCSSAID); | |||||
194 | AU.addPreservedID(LCSSAID); | |||||
195 | AU.addPreserved<DominatorTreeWrapperPass>(); | |||||
196 | AU.addPreserved<ScalarEvolutionWrapperPass>(); | |||||
197 | AU.addRequired<TargetTransformInfoWrapperPass>(); | |||||
198 | } | |||||
199 | ||||||
200 | private: | |||||
201 | ||||||
202 | void releaseMemory() override { | |||||
203 | BranchesInfo.forgetLoop(currentLoop); | |||||
204 | } | |||||
205 | ||||||
206 | void initLoopData() { | |||||
207 | loopHeader = currentLoop->getHeader(); | |||||
208 | loopPreheader = currentLoop->getLoopPreheader(); | |||||
209 | } | |||||
210 | ||||||
211 | /// Split all of the edges from inside the loop to their exit blocks. | |||||
212 | /// Update the appropriate Phi nodes as we do so. | |||||
213 | void SplitExitEdges(Loop *L, | |||||
214 | const SmallVectorImpl<BasicBlock *> &ExitBlocks); | |||||
215 | ||||||
216 | bool TryTrivialLoopUnswitch(bool &Changed); | |||||
217 | ||||||
218 | bool UnswitchIfProfitable(Value *LoopCond, Constant *Val, | |||||
219 | TerminatorInst *TI = nullptr); | |||||
220 | void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, | |||||
221 | BasicBlock *ExitBlock, TerminatorInst *TI); | |||||
222 | void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L, | |||||
223 | TerminatorInst *TI); | |||||
224 | ||||||
225 | void RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, | |||||
226 | Constant *Val, bool isEqual); | |||||
227 | ||||||
228 | void EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, | |||||
229 | BasicBlock *TrueDest, | |||||
230 | BasicBlock *FalseDest, | |||||
231 | Instruction *InsertPt, | |||||
232 | TerminatorInst *TI); | |||||
233 | ||||||
234 | void SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L); | |||||
235 | }; | |||||
236 | } | |||||
237 | ||||||
238 | // Analyze loop. Check its size, calculate is it possible to unswitch | |||||
239 | // it. Returns true if we can unswitch this loop. | |||||
240 | bool LUAnalysisCache::countLoop(const Loop *L, const TargetTransformInfo &TTI, | |||||
241 | AssumptionCache *AC) { | |||||
242 | ||||||
243 | LoopPropsMapIt PropsIt; | |||||
244 | bool Inserted; | |||||
245 | std::tie(PropsIt, Inserted) = | |||||
246 | LoopsProperties.insert(std::make_pair(L, LoopProperties())); | |||||
247 | ||||||
248 | LoopProperties &Props = PropsIt->second; | |||||
249 | ||||||
250 | if (Inserted) { | |||||
251 | // New loop. | |||||
252 | ||||||
253 | // Limit the number of instructions to avoid causing significant code | |||||
254 | // expansion, and the number of basic blocks, to avoid loops with | |||||
255 | // large numbers of branches which cause loop unswitching to go crazy. | |||||
256 | // This is a very ad-hoc heuristic. | |||||
257 | ||||||
258 | SmallPtrSet<const Value *, 32> EphValues; | |||||
259 | CodeMetrics::collectEphemeralValues(L, AC, EphValues); | |||||
260 | ||||||
261 | // FIXME: This is overly conservative because it does not take into | |||||
262 | // consideration code simplification opportunities and code that can | |||||
263 | // be shared by the resultant unswitched loops. | |||||
264 | CodeMetrics Metrics; | |||||
265 | for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E; | |||||
266 | ++I) | |||||
267 | Metrics.analyzeBasicBlock(*I, TTI, EphValues); | |||||
268 | ||||||
269 | Props.SizeEstimation = Metrics.NumInsts; | |||||
270 | Props.CanBeUnswitchedCount = MaxSize / (Props.SizeEstimation); | |||||
271 | Props.WasUnswitchedCount = 0; | |||||
272 | MaxSize -= Props.SizeEstimation * Props.CanBeUnswitchedCount; | |||||
273 | ||||||
274 | if (Metrics.notDuplicatable) { | |||||
275 | DEBUG(dbgs() << "NOT unswitching loop %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "NOT unswitching loop %" << L->getHeader()->getName() << ", contents cannot be " << "duplicated!\n"; } } while (0) | |||||
276 | << L->getHeader()->getName() << ", contents cannot be "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "NOT unswitching loop %" << L->getHeader()->getName() << ", contents cannot be " << "duplicated!\n"; } } while (0) | |||||
277 | << "duplicated!\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "NOT unswitching loop %" << L->getHeader()->getName() << ", contents cannot be " << "duplicated!\n"; } } while (0); | |||||
278 | return false; | |||||
279 | } | |||||
280 | } | |||||
281 | ||||||
282 | // Be careful. This links are good only before new loop addition. | |||||
283 | CurrentLoopProperties = &Props; | |||||
284 | CurLoopInstructions = &Props.UnswitchedVals; | |||||
285 | ||||||
286 | return true; | |||||
287 | } | |||||
288 | ||||||
289 | // Clean all data related to given loop. | |||||
290 | void LUAnalysisCache::forgetLoop(const Loop *L) { | |||||
291 | ||||||
292 | LoopPropsMapIt LIt = LoopsProperties.find(L); | |||||
293 | ||||||
294 | if (LIt != LoopsProperties.end()) { | |||||
295 | LoopProperties &Props = LIt->second; | |||||
296 | MaxSize += (Props.CanBeUnswitchedCount + Props.WasUnswitchedCount) * | |||||
297 | Props.SizeEstimation; | |||||
298 | LoopsProperties.erase(LIt); | |||||
299 | } | |||||
300 | ||||||
301 | CurrentLoopProperties = nullptr; | |||||
302 | CurLoopInstructions = nullptr; | |||||
303 | } | |||||
304 | ||||||
305 | // Mark case value as unswitched. | |||||
306 | // Since SI instruction can be partly unswitched, in order to avoid | |||||
307 | // extra unswitching in cloned loops keep track all unswitched values. | |||||
308 | void LUAnalysisCache::setUnswitched(const SwitchInst *SI, const Value *V) { | |||||
309 | (*CurLoopInstructions)[SI].insert(V); | |||||
310 | } | |||||
311 | ||||||
312 | // Check was this case value unswitched before or not. | |||||
313 | bool LUAnalysisCache::isUnswitched(const SwitchInst *SI, const Value *V) { | |||||
314 | return (*CurLoopInstructions)[SI].count(V); | |||||
315 | } | |||||
316 | ||||||
317 | bool LUAnalysisCache::CostAllowsUnswitching() { | |||||
318 | return CurrentLoopProperties->CanBeUnswitchedCount > 0; | |||||
319 | } | |||||
320 | ||||||
321 | // Clone all loop-unswitch related loop properties. | |||||
322 | // Redistribute unswitching quotas. | |||||
323 | // Note, that new loop data is stored inside the VMap. | |||||
324 | void LUAnalysisCache::cloneData(const Loop *NewLoop, const Loop *OldLoop, | |||||
325 | const ValueToValueMapTy &VMap) { | |||||
326 | ||||||
327 | LoopProperties &NewLoopProps = LoopsProperties[NewLoop]; | |||||
328 | LoopProperties &OldLoopProps = *CurrentLoopProperties; | |||||
329 | UnswitchedValsMap &Insts = OldLoopProps.UnswitchedVals; | |||||
330 | ||||||
331 | // Reallocate "can-be-unswitched quota" | |||||
332 | ||||||
333 | --OldLoopProps.CanBeUnswitchedCount; | |||||
334 | ++OldLoopProps.WasUnswitchedCount; | |||||
335 | NewLoopProps.WasUnswitchedCount = 0; | |||||
336 | unsigned Quota = OldLoopProps.CanBeUnswitchedCount; | |||||
337 | NewLoopProps.CanBeUnswitchedCount = Quota / 2; | |||||
338 | OldLoopProps.CanBeUnswitchedCount = Quota - Quota / 2; | |||||
339 | ||||||
340 | NewLoopProps.SizeEstimation = OldLoopProps.SizeEstimation; | |||||
341 | ||||||
342 | // Clone unswitched values info: | |||||
343 | // for new loop switches we clone info about values that was | |||||
344 | // already unswitched and has redundant successors. | |||||
345 | for (UnswitchedValsIt I = Insts.begin(); I != Insts.end(); ++I) { | |||||
346 | const SwitchInst *OldInst = I->first; | |||||
347 | Value *NewI = VMap.lookup(OldInst); | |||||
348 | const SwitchInst *NewInst = cast_or_null<SwitchInst>(NewI); | |||||
349 | assert(NewInst && "All instructions that are in SrcBB must be in VMap.")((NewInst && "All instructions that are in SrcBB must be in VMap." ) ? static_cast<void> (0) : __assert_fail ("NewInst && \"All instructions that are in SrcBB must be in VMap.\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 349, __PRETTY_FUNCTION__)); | |||||
350 | ||||||
351 | NewLoopProps.UnswitchedVals[NewInst] = OldLoopProps.UnswitchedVals[OldInst]; | |||||
352 | } | |||||
353 | } | |||||
354 | ||||||
355 | char LoopUnswitch::ID = 0; | |||||
356 | INITIALIZE_PASS_BEGIN(LoopUnswitch, "loop-unswitch", "Unswitch loops",static void* initializeLoopUnswitchPassOnce(PassRegistry & Registry) { | |||||
357 | false, false)static void* initializeLoopUnswitchPassOnce(PassRegistry & Registry) { | |||||
358 | INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)initializeTargetTransformInfoWrapperPassPass(Registry); | |||||
359 | INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)initializeAssumptionCacheTrackerPass(Registry); | |||||
360 | INITIALIZE_PASS_DEPENDENCY(LoopSimplify)initializeLoopSimplifyPass(Registry); | |||||
361 | INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)initializeLoopInfoWrapperPassPass(Registry); | |||||
362 | INITIALIZE_PASS_DEPENDENCY(LCSSA)initializeLCSSAPass(Registry); | |||||
363 | INITIALIZE_PASS_END(LoopUnswitch, "loop-unswitch", "Unswitch loops",PassInfo *PI = new PassInfo("Unswitch loops", "loop-unswitch" , & LoopUnswitch ::ID, PassInfo::NormalCtor_t(callDefaultCtor < LoopUnswitch >), false, false); Registry.registerPass (*PI, true); return PI; } void llvm::initializeLoopUnswitchPass (PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeLoopUnswitchPassOnce(Registry ); sys::MemoryFence(); ; ; initialized = 2; ; } else { sys::cas_flag tmp = initialized; sys::MemoryFence(); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; } | |||||
364 | false, false)PassInfo *PI = new PassInfo("Unswitch loops", "loop-unswitch" , & LoopUnswitch ::ID, PassInfo::NormalCtor_t(callDefaultCtor < LoopUnswitch >), false, false); Registry.registerPass (*PI, true); return PI; } void llvm::initializeLoopUnswitchPass (PassRegistry &Registry) { static volatile sys::cas_flag initialized = 0; sys::cas_flag old_val = sys::CompareAndSwap(&initialized , 1, 0); if (old_val == 0) { initializeLoopUnswitchPassOnce(Registry ); sys::MemoryFence(); ; ; initialized = 2; ; } else { sys::cas_flag tmp = initialized; sys::MemoryFence(); while (tmp != 2) { tmp = initialized; sys::MemoryFence(); } } ; } | |||||
365 | ||||||
366 | Pass *llvm::createLoopUnswitchPass(bool Os) { | |||||
367 | return new LoopUnswitch(Os); | |||||
368 | } | |||||
369 | ||||||
370 | /// Cond is a condition that occurs in L. If it is invariant in the loop, or has | |||||
371 | /// an invariant piece, return the invariant. Otherwise, return null. | |||||
372 | static Value *FindLIVLoopCondition(Value *Cond, Loop *L, bool &Changed) { | |||||
373 | ||||||
374 | // We started analyze new instruction, increment scanned instructions counter. | |||||
375 | ++TotalInsts; | |||||
376 | ||||||
377 | // We can never unswitch on vector conditions. | |||||
378 | if (Cond->getType()->isVectorTy()) | |||||
379 | return nullptr; | |||||
380 | ||||||
381 | // Constants should be folded, not unswitched on! | |||||
382 | if (isa<Constant>(Cond)) return nullptr; | |||||
383 | ||||||
384 | // TODO: Handle: br (VARIANT|INVARIANT). | |||||
385 | ||||||
386 | // Hoist simple values out. | |||||
387 | if (L->makeLoopInvariant(Cond, Changed)) | |||||
388 | return Cond; | |||||
389 | ||||||
390 | if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Cond)) | |||||
391 | if (BO->getOpcode() == Instruction::And || | |||||
392 | BO->getOpcode() == Instruction::Or) { | |||||
393 | // If either the left or right side is invariant, we can unswitch on this, | |||||
394 | // which will cause the branch to go away in one loop and the condition to | |||||
395 | // simplify in the other one. | |||||
396 | if (Value *LHS = FindLIVLoopCondition(BO->getOperand(0), L, Changed)) | |||||
397 | return LHS; | |||||
398 | if (Value *RHS = FindLIVLoopCondition(BO->getOperand(1), L, Changed)) | |||||
399 | return RHS; | |||||
400 | } | |||||
401 | ||||||
402 | return nullptr; | |||||
403 | } | |||||
404 | ||||||
405 | bool LoopUnswitch::runOnLoop(Loop *L, LPPassManager &LPM_Ref) { | |||||
406 | if (skipOptnoneFunction(L)) | |||||
| ||||||
407 | return false; | |||||
408 | ||||||
409 | AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache( | |||||
410 | *L->getHeader()->getParent()); | |||||
411 | LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); | |||||
412 | LPM = &LPM_Ref; | |||||
413 | DominatorTreeWrapperPass *DTWP = | |||||
414 | getAnalysisIfAvailable<DominatorTreeWrapperPass>(); | |||||
415 | DT = DTWP ? &DTWP->getDomTree() : nullptr; | |||||
416 | currentLoop = L; | |||||
417 | Function *F = currentLoop->getHeader()->getParent(); | |||||
418 | bool Changed = false; | |||||
419 | do { | |||||
420 | assert(currentLoop->isLCSSAForm(*DT))((currentLoop->isLCSSAForm(*DT)) ? static_cast<void> (0) : __assert_fail ("currentLoop->isLCSSAForm(*DT)", "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 420, __PRETTY_FUNCTION__)); | |||||
| ||||||
421 | redoLoop = false; | |||||
422 | Changed |= processCurrentLoop(); | |||||
423 | } while(redoLoop); | |||||
424 | ||||||
425 | if (Changed) { | |||||
426 | // FIXME: Reconstruct dom info, because it is not preserved properly. | |||||
427 | if (DT) | |||||
428 | DT->recalculate(*F); | |||||
429 | } | |||||
430 | return Changed; | |||||
431 | } | |||||
432 | ||||||
433 | /// Do actual work and unswitch loop if possible and profitable. | |||||
434 | bool LoopUnswitch::processCurrentLoop() { | |||||
435 | bool Changed = false; | |||||
436 | ||||||
437 | initLoopData(); | |||||
438 | ||||||
439 | // If LoopSimplify was unable to form a preheader, don't do any unswitching. | |||||
440 | if (!loopPreheader) | |||||
441 | return false; | |||||
442 | ||||||
443 | // Loops with indirectbr cannot be cloned. | |||||
444 | if (!currentLoop->isSafeToClone()) | |||||
445 | return false; | |||||
446 | ||||||
447 | // Without dedicated exits, splitting the exit edge may fail. | |||||
448 | if (!currentLoop->hasDedicatedExits()) | |||||
449 | return false; | |||||
450 | ||||||
451 | LLVMContext &Context = loopHeader->getContext(); | |||||
452 | ||||||
453 | // Probably we reach the quota of branches for this loop. If so | |||||
454 | // stop unswitching. | |||||
455 | if (!BranchesInfo.countLoop( | |||||
456 | currentLoop, getAnalysis<TargetTransformInfoWrapperPass>().getTTI( | |||||
457 | *currentLoop->getHeader()->getParent()), | |||||
458 | AC)) | |||||
459 | return false; | |||||
460 | ||||||
461 | // Try trivial unswitch first before loop over other basic blocks in the loop. | |||||
462 | if (TryTrivialLoopUnswitch(Changed)) { | |||||
463 | return true; | |||||
464 | } | |||||
465 | ||||||
466 | // Do not do non-trivial unswitch while optimizing for size. | |||||
467 | // FIXME: Use Function::optForSize(). | |||||
468 | if (OptimizeForSize || | |||||
469 | loopHeader->getParent()->hasFnAttribute(Attribute::OptimizeForSize)) | |||||
470 | return false; | |||||
471 | ||||||
472 | // Loop over all of the basic blocks in the loop. If we find an interior | |||||
473 | // block that is branching on a loop-invariant condition, we can unswitch this | |||||
474 | // loop. | |||||
475 | for (Loop::block_iterator I = currentLoop->block_begin(), | |||||
476 | E = currentLoop->block_end(); I != E; ++I) { | |||||
477 | TerminatorInst *TI = (*I)->getTerminator(); | |||||
478 | if (BranchInst *BI = dyn_cast<BranchInst>(TI)) { | |||||
479 | // If this isn't branching on an invariant condition, we can't unswitch | |||||
480 | // it. | |||||
481 | if (BI->isConditional()) { | |||||
482 | // See if this, or some part of it, is loop invariant. If so, we can | |||||
483 | // unswitch on it if we desire. | |||||
484 | Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), | |||||
485 | currentLoop, Changed); | |||||
486 | if (LoopCond && | |||||
487 | UnswitchIfProfitable(LoopCond, ConstantInt::getTrue(Context), TI)) { | |||||
488 | ++NumBranches; | |||||
489 | return true; | |||||
490 | } | |||||
491 | } | |||||
492 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(TI)) { | |||||
493 | Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), | |||||
494 | currentLoop, Changed); | |||||
495 | unsigned NumCases = SI->getNumCases(); | |||||
496 | if (LoopCond && NumCases) { | |||||
497 | // Find a value to unswitch on: | |||||
498 | // FIXME: this should chose the most expensive case! | |||||
499 | // FIXME: scan for a case with a non-critical edge? | |||||
500 | Constant *UnswitchVal = nullptr; | |||||
501 | ||||||
502 | // Do not process same value again and again. | |||||
503 | // At this point we have some cases already unswitched and | |||||
504 | // some not yet unswitched. Let's find the first not yet unswitched one. | |||||
505 | for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); | |||||
506 | i != e; ++i) { | |||||
507 | Constant *UnswitchValCandidate = i.getCaseValue(); | |||||
508 | if (!BranchesInfo.isUnswitched(SI, UnswitchValCandidate)) { | |||||
509 | UnswitchVal = UnswitchValCandidate; | |||||
510 | break; | |||||
511 | } | |||||
512 | } | |||||
513 | ||||||
514 | if (!UnswitchVal) | |||||
515 | continue; | |||||
516 | ||||||
517 | if (UnswitchIfProfitable(LoopCond, UnswitchVal)) { | |||||
518 | ++NumSwitches; | |||||
519 | return true; | |||||
520 | } | |||||
521 | } | |||||
522 | } | |||||
523 | ||||||
524 | // Scan the instructions to check for unswitchable values. | |||||
525 | for (BasicBlock::iterator BBI = (*I)->begin(), E = (*I)->end(); | |||||
526 | BBI != E; ++BBI) | |||||
527 | if (SelectInst *SI = dyn_cast<SelectInst>(BBI)) { | |||||
528 | Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), | |||||
529 | currentLoop, Changed); | |||||
530 | if (LoopCond && UnswitchIfProfitable(LoopCond, | |||||
531 | ConstantInt::getTrue(Context))) { | |||||
532 | ++NumSelects; | |||||
533 | return true; | |||||
534 | } | |||||
535 | } | |||||
536 | } | |||||
537 | return Changed; | |||||
538 | } | |||||
539 | ||||||
540 | /// Check to see if all paths from BB exit the loop with no side effects | |||||
541 | /// (including infinite loops). | |||||
542 | /// | |||||
543 | /// If true, we return true and set ExitBB to the block we | |||||
544 | /// exit through. | |||||
545 | /// | |||||
546 | static bool isTrivialLoopExitBlockHelper(Loop *L, BasicBlock *BB, | |||||
547 | BasicBlock *&ExitBB, | |||||
548 | std::set<BasicBlock*> &Visited) { | |||||
549 | if (!Visited.insert(BB).second) { | |||||
550 | // Already visited. Without more analysis, this could indicate an infinite | |||||
551 | // loop. | |||||
552 | return false; | |||||
553 | } | |||||
554 | if (!L->contains(BB)) { | |||||
555 | // Otherwise, this is a loop exit, this is fine so long as this is the | |||||
556 | // first exit. | |||||
557 | if (ExitBB) return false; | |||||
558 | ExitBB = BB; | |||||
559 | return true; | |||||
560 | } | |||||
561 | ||||||
562 | // Otherwise, this is an unvisited intra-loop node. Check all successors. | |||||
563 | for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI) { | |||||
564 | // Check to see if the successor is a trivial loop exit. | |||||
565 | if (!isTrivialLoopExitBlockHelper(L, *SI, ExitBB, Visited)) | |||||
566 | return false; | |||||
567 | } | |||||
568 | ||||||
569 | // Okay, everything after this looks good, check to make sure that this block | |||||
570 | // doesn't include any side effects. | |||||
571 | for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) | |||||
572 | if (I->mayHaveSideEffects()) | |||||
573 | return false; | |||||
574 | ||||||
575 | return true; | |||||
576 | } | |||||
577 | ||||||
578 | /// Return true if the specified block unconditionally leads to an exit from | |||||
579 | /// the specified loop, and has no side-effects in the process. If so, return | |||||
580 | /// the block that is exited to, otherwise return null. | |||||
581 | static BasicBlock *isTrivialLoopExitBlock(Loop *L, BasicBlock *BB) { | |||||
582 | std::set<BasicBlock*> Visited; | |||||
583 | Visited.insert(L->getHeader()); // Branches to header make infinite loops. | |||||
584 | BasicBlock *ExitBB = nullptr; | |||||
585 | if (isTrivialLoopExitBlockHelper(L, BB, ExitBB, Visited)) | |||||
586 | return ExitBB; | |||||
587 | return nullptr; | |||||
588 | } | |||||
589 | ||||||
590 | /// We have found that we can unswitch currentLoop when LoopCond == Val to | |||||
591 | /// simplify the loop. If we decide that this is profitable, | |||||
592 | /// unswitch the loop, reprocess the pieces, then return true. | |||||
593 | bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val, | |||||
594 | TerminatorInst *TI) { | |||||
595 | // Check to see if it would be profitable to unswitch current loop. | |||||
596 | if (!BranchesInfo.CostAllowsUnswitching()) { | |||||
597 | DEBUG(dbgs() << "NOT unswitching loop %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "NOT unswitching loop %" << currentLoop->getHeader()->getName() << " at non-trivial condition '" << *Val << "' == " << *LoopCond << "\n" << ". Cost too high.\n"; } } while (0) | |||||
598 | << currentLoop->getHeader()->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "NOT unswitching loop %" << currentLoop->getHeader()->getName() << " at non-trivial condition '" << *Val << "' == " << *LoopCond << "\n" << ". Cost too high.\n"; } } while (0) | |||||
599 | << " at non-trivial condition '" << *Valdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "NOT unswitching loop %" << currentLoop->getHeader()->getName() << " at non-trivial condition '" << *Val << "' == " << *LoopCond << "\n" << ". Cost too high.\n"; } } while (0) | |||||
600 | << "' == " << *LoopCond << "\n"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "NOT unswitching loop %" << currentLoop->getHeader()->getName() << " at non-trivial condition '" << *Val << "' == " << *LoopCond << "\n" << ". Cost too high.\n"; } } while (0) | |||||
601 | << ". Cost too high.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "NOT unswitching loop %" << currentLoop->getHeader()->getName() << " at non-trivial condition '" << *Val << "' == " << *LoopCond << "\n" << ". Cost too high.\n"; } } while (0); | |||||
602 | return false; | |||||
603 | } | |||||
604 | ||||||
605 | UnswitchNontrivialCondition(LoopCond, Val, currentLoop, TI); | |||||
606 | return true; | |||||
607 | } | |||||
608 | ||||||
609 | /// Recursively clone the specified loop and all of its children, | |||||
610 | /// mapping the blocks with the specified map. | |||||
611 | static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, | |||||
612 | LoopInfo *LI, LPPassManager *LPM) { | |||||
613 | Loop *New = new Loop(); | |||||
614 | LPM->insertLoop(New, PL); | |||||
615 | ||||||
616 | // Add all of the blocks in L to the new loop. | |||||
617 | for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); | |||||
618 | I != E; ++I) | |||||
619 | if (LI->getLoopFor(*I) == L) | |||||
620 | New->addBasicBlockToLoop(cast<BasicBlock>(VM[*I]), *LI); | |||||
621 | ||||||
622 | // Add all of the subloops to the new loop. | |||||
623 | for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) | |||||
624 | CloneLoop(*I, New, VM, LI, LPM); | |||||
625 | ||||||
626 | return New; | |||||
627 | } | |||||
628 | ||||||
629 | static void copyMetadata(Instruction *DstInst, const Instruction *SrcInst, | |||||
630 | bool Swapped) { | |||||
631 | if (!SrcInst || !SrcInst->hasMetadata()) | |||||
632 | return; | |||||
633 | ||||||
634 | SmallVector<std::pair<unsigned, MDNode *>, 4> MDs; | |||||
635 | SrcInst->getAllMetadata(MDs); | |||||
636 | for (auto &MD : MDs) { | |||||
637 | switch (MD.first) { | |||||
638 | default: | |||||
639 | break; | |||||
640 | case LLVMContext::MD_prof: | |||||
641 | if (Swapped && MD.second->getNumOperands() == 3 && | |||||
642 | isa<MDString>(MD.second->getOperand(0))) { | |||||
643 | MDString *MDName = cast<MDString>(MD.second->getOperand(0)); | |||||
644 | if (MDName->getString() == "branch_weights") { | |||||
645 | auto *ValT = cast_or_null<ConstantAsMetadata>( | |||||
646 | MD.second->getOperand(1))->getValue(); | |||||
647 | auto *ValF = cast_or_null<ConstantAsMetadata>( | |||||
648 | MD.second->getOperand(2))->getValue(); | |||||
649 | assert(ValT && ValF && "Invalid Operands of branch_weights")((ValT && ValF && "Invalid Operands of branch_weights" ) ? static_cast<void> (0) : __assert_fail ("ValT && ValF && \"Invalid Operands of branch_weights\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 649, __PRETTY_FUNCTION__)); | |||||
650 | auto NewMD = | |||||
651 | MDBuilder(DstInst->getParent()->getContext()) | |||||
652 | .createBranchWeights(cast<ConstantInt>(ValF)->getZExtValue(), | |||||
653 | cast<ConstantInt>(ValT)->getZExtValue()); | |||||
654 | MD.second = NewMD; | |||||
655 | } | |||||
656 | } | |||||
657 | // fallthrough. | |||||
658 | case LLVMContext::MD_make_implicit: | |||||
659 | case LLVMContext::MD_dbg: | |||||
660 | DstInst->setMetadata(MD.first, MD.second); | |||||
661 | } | |||||
662 | } | |||||
663 | } | |||||
664 | ||||||
665 | /// Emit a conditional branch on two values if LIC == Val, branch to TrueDst, | |||||
666 | /// otherwise branch to FalseDest. Insert the code immediately before InsertPt. | |||||
667 | void LoopUnswitch::EmitPreheaderBranchOnCondition(Value *LIC, Constant *Val, | |||||
668 | BasicBlock *TrueDest, | |||||
669 | BasicBlock *FalseDest, | |||||
670 | Instruction *InsertPt, | |||||
671 | TerminatorInst *TI) { | |||||
672 | // Insert a conditional branch on LIC to the two preheaders. The original | |||||
673 | // code is the true version and the new code is the false version. | |||||
674 | Value *BranchVal = LIC; | |||||
675 | bool Swapped = false; | |||||
676 | if (!isa<ConstantInt>(Val) || | |||||
677 | Val->getType() != Type::getInt1Ty(LIC->getContext())) | |||||
678 | BranchVal = new ICmpInst(InsertPt, ICmpInst::ICMP_EQ, LIC, Val); | |||||
679 | else if (Val != ConstantInt::getTrue(Val->getContext())) { | |||||
680 | // We want to enter the new loop when the condition is true. | |||||
681 | std::swap(TrueDest, FalseDest); | |||||
682 | Swapped = true; | |||||
683 | } | |||||
684 | ||||||
685 | // Insert the new branch. | |||||
686 | BranchInst *BI = BranchInst::Create(TrueDest, FalseDest, BranchVal, InsertPt); | |||||
687 | copyMetadata(BI, TI, Swapped); | |||||
688 | ||||||
689 | // If either edge is critical, split it. This helps preserve LoopSimplify | |||||
690 | // form for enclosing loops. | |||||
691 | auto Options = CriticalEdgeSplittingOptions(DT, LI).setPreserveLCSSA(); | |||||
692 | SplitCriticalEdge(BI, 0, Options); | |||||
693 | SplitCriticalEdge(BI, 1, Options); | |||||
694 | } | |||||
695 | ||||||
696 | /// Given a loop that has a trivial unswitchable condition in it (a cond branch | |||||
697 | /// from its header block to its latch block, where the path through the loop | |||||
698 | /// that doesn't execute its body has no side-effects), unswitch it. This | |||||
699 | /// doesn't involve any code duplication, just moving the conditional branch | |||||
700 | /// outside of the loop and updating loop info. | |||||
701 | void LoopUnswitch::UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, | |||||
702 | BasicBlock *ExitBlock, | |||||
703 | TerminatorInst *TI) { | |||||
704 | DEBUG(dbgs() << "loop-unswitch: Trivial-Unswitch loop %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %" << loopHeader->getName() << " [" << L-> getBlocks().size() << " blocks] in Function " << L ->getHeader()->getParent()->getName() << " on cond: " << *Val << " == " << *Cond << "\n"; } } while (0) | |||||
705 | << loopHeader->getName() << " [" << L->getBlocks().size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %" << loopHeader->getName() << " [" << L-> getBlocks().size() << " blocks] in Function " << L ->getHeader()->getParent()->getName() << " on cond: " << *Val << " == " << *Cond << "\n"; } } while (0) | |||||
706 | << " blocks] in Function "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %" << loopHeader->getName() << " [" << L-> getBlocks().size() << " blocks] in Function " << L ->getHeader()->getParent()->getName() << " on cond: " << *Val << " == " << *Cond << "\n"; } } while (0) | |||||
707 | << L->getHeader()->getParent()->getName() << " on cond: " << *Valdo { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %" << loopHeader->getName() << " [" << L-> getBlocks().size() << " blocks] in Function " << L ->getHeader()->getParent()->getName() << " on cond: " << *Val << " == " << *Cond << "\n"; } } while (0) | |||||
708 | << " == " << *Cond << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "loop-unswitch: Trivial-Unswitch loop %" << loopHeader->getName() << " [" << L-> getBlocks().size() << " blocks] in Function " << L ->getHeader()->getParent()->getName() << " on cond: " << *Val << " == " << *Cond << "\n"; } } while (0); | |||||
709 | ||||||
710 | // First step, split the preheader, so that we know that there is a safe place | |||||
711 | // to insert the conditional branch. We will change loopPreheader to have a | |||||
712 | // conditional branch on Cond. | |||||
713 | BasicBlock *NewPH = SplitEdge(loopPreheader, loopHeader, DT, LI); | |||||
714 | ||||||
715 | // Now that we have a place to insert the conditional branch, create a place | |||||
716 | // to branch to: this is the exit block out of the loop that we should | |||||
717 | // short-circuit to. | |||||
718 | ||||||
719 | // Split this block now, so that the loop maintains its exit block, and so | |||||
720 | // that the jump from the preheader can execute the contents of the exit block | |||||
721 | // without actually branching to it (the exit block should be dominated by the | |||||
722 | // loop header, not the preheader). | |||||
723 | assert(!L->contains(ExitBlock) && "Exit block is in the loop?")((!L->contains(ExitBlock) && "Exit block is in the loop?" ) ? static_cast<void> (0) : __assert_fail ("!L->contains(ExitBlock) && \"Exit block is in the loop?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 723, __PRETTY_FUNCTION__)); | |||||
724 | BasicBlock *NewExit = SplitBlock(ExitBlock, ExitBlock->begin(), DT, LI); | |||||
725 | ||||||
726 | // Okay, now we have a position to branch from and a position to branch to, | |||||
727 | // insert the new conditional branch. | |||||
728 | EmitPreheaderBranchOnCondition(Cond, Val, NewExit, NewPH, | |||||
729 | loopPreheader->getTerminator(), TI); | |||||
730 | LPM->deleteSimpleAnalysisValue(loopPreheader->getTerminator(), L); | |||||
731 | loopPreheader->getTerminator()->eraseFromParent(); | |||||
732 | ||||||
733 | // We need to reprocess this loop, it could be unswitched again. | |||||
734 | redoLoop = true; | |||||
735 | ||||||
736 | // Now that we know that the loop is never entered when this condition is a | |||||
737 | // particular value, rewrite the loop with this info. We know that this will | |||||
738 | // at least eliminate the old branch. | |||||
739 | RewriteLoopBodyWithConditionConstant(L, Cond, Val, false); | |||||
740 | ++NumTrivial; | |||||
741 | } | |||||
742 | ||||||
743 | /// Check if the first non-constant condition starting from the loop header is | |||||
744 | /// a trivial unswitch condition: that is, a condition controls whether or not | |||||
745 | /// the loop does anything at all. If it is a trivial condition, unswitching | |||||
746 | /// produces no code duplications (equivalently, it produces a simpler loop and | |||||
747 | /// a new empty loop, which gets deleted). Therefore always unswitch trivial | |||||
748 | /// condition. | |||||
749 | bool LoopUnswitch::TryTrivialLoopUnswitch(bool &Changed) { | |||||
750 | BasicBlock *CurrentBB = currentLoop->getHeader(); | |||||
751 | TerminatorInst *CurrentTerm = CurrentBB->getTerminator(); | |||||
752 | LLVMContext &Context = CurrentBB->getContext(); | |||||
753 | ||||||
754 | // If loop header has only one reachable successor (currently via an | |||||
755 | // unconditional branch or constant foldable conditional branch, but | |||||
756 | // should also consider adding constant foldable switch instruction in | |||||
757 | // future), we should keep looking for trivial condition candidates in | |||||
758 | // the successor as well. An alternative is to constant fold conditions | |||||
759 | // and merge successors into loop header (then we only need to check header's | |||||
760 | // terminator). The reason for not doing this in LoopUnswitch pass is that | |||||
761 | // it could potentially break LoopPassManager's invariants. Folding dead | |||||
762 | // branches could either eliminate the current loop or make other loops | |||||
763 | // unreachable. LCSSA form might also not be preserved after deleting | |||||
764 | // branches. The following code keeps traversing loop header's successors | |||||
765 | // until it finds the trivial condition candidate (condition that is not a | |||||
766 | // constant). Since unswitching generates branches with constant conditions, | |||||
767 | // this scenario could be very common in practice. | |||||
768 | SmallSet<BasicBlock*, 8> Visited; | |||||
769 | ||||||
770 | while (true) { | |||||
771 | // If we exit loop or reach a previous visited block, then | |||||
772 | // we can not reach any trivial condition candidates (unfoldable | |||||
773 | // branch instructions or switch instructions) and no unswitch | |||||
774 | // can happen. Exit and return false. | |||||
775 | if (!currentLoop->contains(CurrentBB) || !Visited.insert(CurrentBB).second) | |||||
776 | return false; | |||||
777 | ||||||
778 | // Check if this loop will execute any side-effecting instructions (e.g. | |||||
779 | // stores, calls, volatile loads) in the part of the loop that the code | |||||
780 | // *would* execute. Check the header first. | |||||
781 | for (BasicBlock::iterator I : *CurrentBB) | |||||
782 | if (I->mayHaveSideEffects()) | |||||
783 | return false; | |||||
784 | ||||||
785 | // FIXME: add check for constant foldable switch instructions. | |||||
786 | if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) { | |||||
787 | if (BI->isUnconditional()) { | |||||
788 | CurrentBB = BI->getSuccessor(0); | |||||
789 | } else if (BI->getCondition() == ConstantInt::getTrue(Context)) { | |||||
790 | CurrentBB = BI->getSuccessor(0); | |||||
791 | } else if (BI->getCondition() == ConstantInt::getFalse(Context)) { | |||||
792 | CurrentBB = BI->getSuccessor(1); | |||||
793 | } else { | |||||
794 | // Found a trivial condition candidate: non-foldable conditional branch. | |||||
795 | break; | |||||
796 | } | |||||
797 | } else { | |||||
798 | break; | |||||
799 | } | |||||
800 | ||||||
801 | CurrentTerm = CurrentBB->getTerminator(); | |||||
802 | } | |||||
803 | ||||||
804 | // CondVal is the condition that controls the trivial condition. | |||||
805 | // LoopExitBB is the BasicBlock that loop exits when meets trivial condition. | |||||
806 | Constant *CondVal = nullptr; | |||||
807 | BasicBlock *LoopExitBB = nullptr; | |||||
808 | ||||||
809 | if (BranchInst *BI = dyn_cast<BranchInst>(CurrentTerm)) { | |||||
810 | // If this isn't branching on an invariant condition, we can't unswitch it. | |||||
811 | if (!BI->isConditional()) | |||||
812 | return false; | |||||
813 | ||||||
814 | Value *LoopCond = FindLIVLoopCondition(BI->getCondition(), | |||||
815 | currentLoop, Changed); | |||||
816 | ||||||
817 | // Unswitch only if the trivial condition itself is an LIV (not | |||||
818 | // partial LIV which could occur in and/or) | |||||
819 | if (!LoopCond || LoopCond != BI->getCondition()) | |||||
820 | return false; | |||||
821 | ||||||
822 | // Check to see if a successor of the branch is guaranteed to | |||||
823 | // exit through a unique exit block without having any | |||||
824 | // side-effects. If so, determine the value of Cond that causes | |||||
825 | // it to do this. | |||||
826 | if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, | |||||
827 | BI->getSuccessor(0)))) { | |||||
828 | CondVal = ConstantInt::getTrue(Context); | |||||
829 | } else if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, | |||||
830 | BI->getSuccessor(1)))) { | |||||
831 | CondVal = ConstantInt::getFalse(Context); | |||||
832 | } | |||||
833 | ||||||
834 | // If we didn't find a single unique LoopExit block, or if the loop exit | |||||
835 | // block contains phi nodes, this isn't trivial. | |||||
836 | if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin())) | |||||
837 | return false; // Can't handle this. | |||||
838 | ||||||
839 | UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB, | |||||
840 | CurrentTerm); | |||||
841 | ++NumBranches; | |||||
842 | return true; | |||||
843 | } else if (SwitchInst *SI = dyn_cast<SwitchInst>(CurrentTerm)) { | |||||
844 | // If this isn't switching on an invariant condition, we can't unswitch it. | |||||
845 | Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), | |||||
846 | currentLoop, Changed); | |||||
847 | ||||||
848 | // Unswitch only if the trivial condition itself is an LIV (not | |||||
849 | // partial LIV which could occur in and/or) | |||||
850 | if (!LoopCond || LoopCond != SI->getCondition()) | |||||
851 | return false; | |||||
852 | ||||||
853 | // Check to see if a successor of the switch is guaranteed to go to the | |||||
854 | // latch block or exit through a one exit block without having any | |||||
855 | // side-effects. If so, determine the value of Cond that causes it to do | |||||
856 | // this. | |||||
857 | // Note that we can't trivially unswitch on the default case or | |||||
858 | // on already unswitched cases. | |||||
859 | for (SwitchInst::CaseIt i = SI->case_begin(), e = SI->case_end(); | |||||
860 | i != e; ++i) { | |||||
861 | BasicBlock *LoopExitCandidate; | |||||
862 | if ((LoopExitCandidate = isTrivialLoopExitBlock(currentLoop, | |||||
863 | i.getCaseSuccessor()))) { | |||||
864 | // Okay, we found a trivial case, remember the value that is trivial. | |||||
865 | ConstantInt *CaseVal = i.getCaseValue(); | |||||
866 | ||||||
867 | // Check that it was not unswitched before, since already unswitched | |||||
868 | // trivial vals are looks trivial too. | |||||
869 | if (BranchesInfo.isUnswitched(SI, CaseVal)) | |||||
870 | continue; | |||||
871 | LoopExitBB = LoopExitCandidate; | |||||
872 | CondVal = CaseVal; | |||||
873 | break; | |||||
874 | } | |||||
875 | } | |||||
876 | ||||||
877 | // If we didn't find a single unique LoopExit block, or if the loop exit | |||||
878 | // block contains phi nodes, this isn't trivial. | |||||
879 | if (!LoopExitBB || isa<PHINode>(LoopExitBB->begin())) | |||||
880 | return false; // Can't handle this. | |||||
881 | ||||||
882 | UnswitchTrivialCondition(currentLoop, LoopCond, CondVal, LoopExitBB, | |||||
883 | nullptr); | |||||
884 | ++NumSwitches; | |||||
885 | return true; | |||||
886 | } | |||||
887 | return false; | |||||
888 | } | |||||
889 | ||||||
890 | /// Split all of the edges from inside the loop to their exit blocks. | |||||
891 | /// Update the appropriate Phi nodes as we do so. | |||||
892 | void LoopUnswitch::SplitExitEdges(Loop *L, | |||||
893 | const SmallVectorImpl<BasicBlock *> &ExitBlocks){ | |||||
894 | ||||||
895 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { | |||||
896 | BasicBlock *ExitBlock = ExitBlocks[i]; | |||||
897 | SmallVector<BasicBlock *, 4> Preds(pred_begin(ExitBlock), | |||||
898 | pred_end(ExitBlock)); | |||||
899 | ||||||
900 | // Although SplitBlockPredecessors doesn't preserve loop-simplify in | |||||
901 | // general, if we call it on all predecessors of all exits then it does. | |||||
902 | SplitBlockPredecessors(ExitBlock, Preds, ".us-lcssa", DT, LI, | |||||
903 | /*PreserveLCSSA*/ true); | |||||
904 | } | |||||
905 | } | |||||
906 | ||||||
907 | /// We determined that the loop is profitable to unswitch when LIC equal Val. | |||||
908 | /// Split it into loop versions and test the condition outside of either loop. | |||||
909 | /// Return the loops created as Out1/Out2. | |||||
910 | void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, | |||||
911 | Loop *L, TerminatorInst *TI) { | |||||
912 | Function *F = loopHeader->getParent(); | |||||
913 | DEBUG(dbgs() << "loop-unswitch: Unswitching loop %"do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "loop-unswitch: Unswitching loop %" << loopHeader->getName() << " [" << L-> getBlocks().size() << " blocks] in Function " << F ->getName() << " when '" << *Val << "' == " << *LIC << "\n"; } } while (0) | |||||
914 | << loopHeader->getName() << " [" << L->getBlocks().size()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "loop-unswitch: Unswitching loop %" << loopHeader->getName() << " [" << L-> getBlocks().size() << " blocks] in Function " << F ->getName() << " when '" << *Val << "' == " << *LIC << "\n"; } } while (0) | |||||
915 | << " blocks] in Function " << F->getName()do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "loop-unswitch: Unswitching loop %" << loopHeader->getName() << " [" << L-> getBlocks().size() << " blocks] in Function " << F ->getName() << " when '" << *Val << "' == " << *LIC << "\n"; } } while (0) | |||||
916 | << " when '" << *Val << "' == " << *LIC << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "loop-unswitch: Unswitching loop %" << loopHeader->getName() << " [" << L-> getBlocks().size() << " blocks] in Function " << F ->getName() << " when '" << *Val << "' == " << *LIC << "\n"; } } while (0); | |||||
917 | ||||||
918 | if (auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>()) | |||||
919 | SEWP->getSE().forgetLoop(L); | |||||
920 | ||||||
921 | LoopBlocks.clear(); | |||||
922 | NewBlocks.clear(); | |||||
923 | ||||||
924 | // First step, split the preheader and exit blocks, and add these blocks to | |||||
925 | // the LoopBlocks list. | |||||
926 | BasicBlock *NewPreheader = SplitEdge(loopPreheader, loopHeader, DT, LI); | |||||
927 | LoopBlocks.push_back(NewPreheader); | |||||
928 | ||||||
929 | // We want the loop to come after the preheader, but before the exit blocks. | |||||
930 | LoopBlocks.insert(LoopBlocks.end(), L->block_begin(), L->block_end()); | |||||
931 | ||||||
932 | SmallVector<BasicBlock*, 8> ExitBlocks; | |||||
933 | L->getUniqueExitBlocks(ExitBlocks); | |||||
934 | ||||||
935 | // Split all of the edges from inside the loop to their exit blocks. Update | |||||
936 | // the appropriate Phi nodes as we do so. | |||||
937 | SplitExitEdges(L, ExitBlocks); | |||||
938 | ||||||
939 | // The exit blocks may have been changed due to edge splitting, recompute. | |||||
940 | ExitBlocks.clear(); | |||||
941 | L->getUniqueExitBlocks(ExitBlocks); | |||||
942 | ||||||
943 | // Add exit blocks to the loop blocks. | |||||
944 | LoopBlocks.insert(LoopBlocks.end(), ExitBlocks.begin(), ExitBlocks.end()); | |||||
945 | ||||||
946 | // Next step, clone all of the basic blocks that make up the loop (including | |||||
947 | // the loop preheader and exit blocks), keeping track of the mapping between | |||||
948 | // the instructions and blocks. | |||||
949 | NewBlocks.reserve(LoopBlocks.size()); | |||||
950 | ValueToValueMapTy VMap; | |||||
951 | for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { | |||||
952 | BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F); | |||||
953 | ||||||
954 | NewBlocks.push_back(NewBB); | |||||
955 | VMap[LoopBlocks[i]] = NewBB; // Keep the BB mapping. | |||||
956 | LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L); | |||||
957 | } | |||||
958 | ||||||
959 | // Splice the newly inserted blocks into the function right before the | |||||
960 | // original preheader. | |||||
961 | F->getBasicBlockList().splice(NewPreheader, F->getBasicBlockList(), | |||||
962 | NewBlocks[0], F->end()); | |||||
963 | ||||||
964 | // FIXME: We could register any cloned assumptions instead of clearing the | |||||
965 | // whole function's cache. | |||||
966 | AC->clear(); | |||||
967 | ||||||
968 | // Now we create the new Loop object for the versioned loop. | |||||
969 | Loop *NewLoop = CloneLoop(L, L->getParentLoop(), VMap, LI, LPM); | |||||
970 | ||||||
971 | // Recalculate unswitching quota, inherit simplified switches info for NewBB, | |||||
972 | // Probably clone more loop-unswitch related loop properties. | |||||
973 | BranchesInfo.cloneData(NewLoop, L, VMap); | |||||
974 | ||||||
975 | Loop *ParentLoop = L->getParentLoop(); | |||||
976 | if (ParentLoop) { | |||||
977 | // Make sure to add the cloned preheader and exit blocks to the parent loop | |||||
978 | // as well. | |||||
979 | ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI); | |||||
980 | } | |||||
981 | ||||||
982 | for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { | |||||
983 | BasicBlock *NewExit = cast<BasicBlock>(VMap[ExitBlocks[i]]); | |||||
984 | // The new exit block should be in the same loop as the old one. | |||||
985 | if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i])) | |||||
986 | ExitBBLoop->addBasicBlockToLoop(NewExit, *LI); | |||||
987 | ||||||
988 | assert(NewExit->getTerminator()->getNumSuccessors() == 1 &&((NewExit->getTerminator()->getNumSuccessors() == 1 && "Exit block should have been split to have one successor!") ? static_cast<void> (0) : __assert_fail ("NewExit->getTerminator()->getNumSuccessors() == 1 && \"Exit block should have been split to have one successor!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 989, __PRETTY_FUNCTION__)) | |||||
989 | "Exit block should have been split to have one successor!")((NewExit->getTerminator()->getNumSuccessors() == 1 && "Exit block should have been split to have one successor!") ? static_cast<void> (0) : __assert_fail ("NewExit->getTerminator()->getNumSuccessors() == 1 && \"Exit block should have been split to have one successor!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 989, __PRETTY_FUNCTION__)); | |||||
990 | BasicBlock *ExitSucc = NewExit->getTerminator()->getSuccessor(0); | |||||
991 | ||||||
992 | // If the successor of the exit block had PHI nodes, add an entry for | |||||
993 | // NewExit. | |||||
994 | for (BasicBlock::iterator I = ExitSucc->begin(); | |||||
995 | PHINode *PN = dyn_cast<PHINode>(I); ++I) { | |||||
996 | Value *V = PN->getIncomingValueForBlock(ExitBlocks[i]); | |||||
997 | ValueToValueMapTy::iterator It = VMap.find(V); | |||||
998 | if (It != VMap.end()) V = It->second; | |||||
999 | PN->addIncoming(V, NewExit); | |||||
1000 | } | |||||
1001 | ||||||
1002 | if (LandingPadInst *LPad = NewExit->getLandingPadInst()) { | |||||
1003 | PHINode *PN = PHINode::Create(LPad->getType(), 0, "", | |||||
1004 | ExitSucc->getFirstInsertionPt()); | |||||
1005 | ||||||
1006 | for (pred_iterator I = pred_begin(ExitSucc), E = pred_end(ExitSucc); | |||||
1007 | I != E; ++I) { | |||||
1008 | BasicBlock *BB = *I; | |||||
1009 | LandingPadInst *LPI = BB->getLandingPadInst(); | |||||
1010 | LPI->replaceAllUsesWith(PN); | |||||
1011 | PN->addIncoming(LPI, BB); | |||||
1012 | } | |||||
1013 | } | |||||
1014 | } | |||||
1015 | ||||||
1016 | // Rewrite the code to refer to itself. | |||||
1017 | for (unsigned i = 0, e = NewBlocks.size(); i != e; ++i) | |||||
1018 | for (BasicBlock::iterator I = NewBlocks[i]->begin(), | |||||
1019 | E = NewBlocks[i]->end(); I != E; ++I) | |||||
1020 | RemapInstruction(I, VMap,RF_NoModuleLevelChanges|RF_IgnoreMissingEntries); | |||||
1021 | ||||||
1022 | // Rewrite the original preheader to select between versions of the loop. | |||||
1023 | BranchInst *OldBR = cast<BranchInst>(loopPreheader->getTerminator()); | |||||
1024 | assert(OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] &&((OldBR->isUnconditional() && OldBR->getSuccessor (0) == LoopBlocks[0] && "Preheader splitting did not work correctly!" ) ? static_cast<void> (0) : __assert_fail ("OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] && \"Preheader splitting did not work correctly!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 1025, __PRETTY_FUNCTION__)) | |||||
1025 | "Preheader splitting did not work correctly!")((OldBR->isUnconditional() && OldBR->getSuccessor (0) == LoopBlocks[0] && "Preheader splitting did not work correctly!" ) ? static_cast<void> (0) : __assert_fail ("OldBR->isUnconditional() && OldBR->getSuccessor(0) == LoopBlocks[0] && \"Preheader splitting did not work correctly!\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 1025, __PRETTY_FUNCTION__)); | |||||
1026 | ||||||
1027 | // Emit the new branch that selects between the two versions of this loop. | |||||
1028 | EmitPreheaderBranchOnCondition(LIC, Val, NewBlocks[0], LoopBlocks[0], OldBR, | |||||
1029 | TI); | |||||
1030 | LPM->deleteSimpleAnalysisValue(OldBR, L); | |||||
1031 | OldBR->eraseFromParent(); | |||||
1032 | ||||||
1033 | LoopProcessWorklist.push_back(NewLoop); | |||||
1034 | redoLoop = true; | |||||
1035 | ||||||
1036 | // Keep a WeakVH holding onto LIC. If the first call to RewriteLoopBody | |||||
1037 | // deletes the instruction (for example by simplifying a PHI that feeds into | |||||
1038 | // the condition that we're unswitching on), we don't rewrite the second | |||||
1039 | // iteration. | |||||
1040 | WeakVH LICHandle(LIC); | |||||
1041 | ||||||
1042 | // Now we rewrite the original code to know that the condition is true and the | |||||
1043 | // new code to know that the condition is false. | |||||
1044 | RewriteLoopBodyWithConditionConstant(L, LIC, Val, false); | |||||
1045 | ||||||
1046 | // It's possible that simplifying one loop could cause the other to be | |||||
1047 | // changed to another value or a constant. If its a constant, don't simplify | |||||
1048 | // it. | |||||
1049 | if (!LoopProcessWorklist.empty() && LoopProcessWorklist.back() == NewLoop && | |||||
1050 | LICHandle && !isa<Constant>(LICHandle)) | |||||
1051 | RewriteLoopBodyWithConditionConstant(NewLoop, LICHandle, Val, true); | |||||
1052 | } | |||||
1053 | ||||||
1054 | /// Remove all instances of I from the worklist vector specified. | |||||
1055 | static void RemoveFromWorklist(Instruction *I, | |||||
1056 | std::vector<Instruction*> &Worklist) { | |||||
1057 | ||||||
1058 | Worklist.erase(std::remove(Worklist.begin(), Worklist.end(), I), | |||||
1059 | Worklist.end()); | |||||
1060 | } | |||||
1061 | ||||||
1062 | /// When we find that I really equals V, remove I from the | |||||
1063 | /// program, replacing all uses with V and update the worklist. | |||||
1064 | static void ReplaceUsesOfWith(Instruction *I, Value *V, | |||||
1065 | std::vector<Instruction*> &Worklist, | |||||
1066 | Loop *L, LPPassManager *LPM) { | |||||
1067 | DEBUG(dbgs() << "Replace with '" << *V << "': " << *I)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "Replace with '" << *V << "': " << *I; } } while (0); | |||||
1068 | ||||||
1069 | // Add uses to the worklist, which may be dead now. | |||||
1070 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) | |||||
1071 | if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i))) | |||||
1072 | Worklist.push_back(Use); | |||||
1073 | ||||||
1074 | // Add users to the worklist which may be simplified now. | |||||
1075 | for (User *U : I->users()) | |||||
1076 | Worklist.push_back(cast<Instruction>(U)); | |||||
1077 | LPM->deleteSimpleAnalysisValue(I, L); | |||||
1078 | RemoveFromWorklist(I, Worklist); | |||||
1079 | I->replaceAllUsesWith(V); | |||||
1080 | I->eraseFromParent(); | |||||
1081 | ++NumSimplify; | |||||
1082 | } | |||||
1083 | ||||||
1084 | /// We know either that the value LIC has the value specified by Val in the | |||||
1085 | /// specified loop, or we know it does NOT have that value. | |||||
1086 | /// Rewrite any uses of LIC or of properties correlated to it. | |||||
1087 | void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, | |||||
1088 | Constant *Val, | |||||
1089 | bool IsEqual) { | |||||
1090 | assert(!isa<Constant>(LIC) && "Why are we unswitching on a constant?")((!isa<Constant>(LIC) && "Why are we unswitching on a constant?" ) ? static_cast<void> (0) : __assert_fail ("!isa<Constant>(LIC) && \"Why are we unswitching on a constant?\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 1090, __PRETTY_FUNCTION__)); | |||||
1091 | ||||||
1092 | // FIXME: Support correlated properties, like: | |||||
1093 | // for (...) | |||||
1094 | // if (li1 < li2) | |||||
1095 | // ... | |||||
1096 | // if (li1 > li2) | |||||
1097 | // ... | |||||
1098 | ||||||
1099 | // FOLD boolean conditions (X|LIC), (X&LIC). Fold conditional branches, | |||||
1100 | // selects, switches. | |||||
1101 | std::vector<Instruction*> Worklist; | |||||
1102 | LLVMContext &Context = Val->getContext(); | |||||
1103 | ||||||
1104 | // If we know that LIC == Val, or that LIC == NotVal, just replace uses of LIC | |||||
1105 | // in the loop with the appropriate one directly. | |||||
1106 | if (IsEqual || (isa<ConstantInt>(Val) && | |||||
1107 | Val->getType()->isIntegerTy(1))) { | |||||
1108 | Value *Replacement; | |||||
1109 | if (IsEqual) | |||||
1110 | Replacement = Val; | |||||
1111 | else | |||||
1112 | Replacement = ConstantInt::get(Type::getInt1Ty(Val->getContext()), | |||||
1113 | !cast<ConstantInt>(Val)->getZExtValue()); | |||||
1114 | ||||||
1115 | for (User *U : LIC->users()) { | |||||
1116 | Instruction *UI = dyn_cast<Instruction>(U); | |||||
1117 | if (!UI || !L->contains(UI)) | |||||
1118 | continue; | |||||
1119 | Worklist.push_back(UI); | |||||
1120 | } | |||||
1121 | ||||||
1122 | for (std::vector<Instruction*>::iterator UI = Worklist.begin(), | |||||
1123 | UE = Worklist.end(); UI != UE; ++UI) | |||||
1124 | (*UI)->replaceUsesOfWith(LIC, Replacement); | |||||
1125 | ||||||
1126 | SimplifyCode(Worklist, L); | |||||
1127 | return; | |||||
1128 | } | |||||
1129 | ||||||
1130 | // Otherwise, we don't know the precise value of LIC, but we do know that it | |||||
1131 | // is certainly NOT "Val". As such, simplify any uses in the loop that we | |||||
1132 | // can. This case occurs when we unswitch switch statements. | |||||
1133 | for (User *U : LIC->users()) { | |||||
1134 | Instruction *UI = dyn_cast<Instruction>(U); | |||||
1135 | if (!UI || !L->contains(UI)) | |||||
1136 | continue; | |||||
1137 | ||||||
1138 | Worklist.push_back(UI); | |||||
1139 | ||||||
1140 | // TODO: We could do other simplifications, for example, turning | |||||
1141 | // 'icmp eq LIC, Val' -> false. | |||||
1142 | ||||||
1143 | // If we know that LIC is not Val, use this info to simplify code. | |||||
1144 | SwitchInst *SI = dyn_cast<SwitchInst>(UI); | |||||
1145 | if (!SI || !isa<ConstantInt>(Val)) continue; | |||||
1146 | ||||||
1147 | SwitchInst::CaseIt DeadCase = SI->findCaseValue(cast<ConstantInt>(Val)); | |||||
1148 | // Default case is live for multiple values. | |||||
1149 | if (DeadCase == SI->case_default()) continue; | |||||
1150 | ||||||
1151 | // Found a dead case value. Don't remove PHI nodes in the | |||||
1152 | // successor if they become single-entry, those PHI nodes may | |||||
1153 | // be in the Users list. | |||||
1154 | ||||||
1155 | BasicBlock *Switch = SI->getParent(); | |||||
1156 | BasicBlock *SISucc = DeadCase.getCaseSuccessor(); | |||||
1157 | BasicBlock *Latch = L->getLoopLatch(); | |||||
1158 | ||||||
1159 | BranchesInfo.setUnswitched(SI, Val); | |||||
1160 | ||||||
1161 | if (!SI->findCaseDest(SISucc)) continue; // Edge is critical. | |||||
1162 | // If the DeadCase successor dominates the loop latch, then the | |||||
1163 | // transformation isn't safe since it will delete the sole predecessor edge | |||||
1164 | // to the latch. | |||||
1165 | if (Latch && DT->dominates(SISucc, Latch)) | |||||
1166 | continue; | |||||
1167 | ||||||
1168 | // FIXME: This is a hack. We need to keep the successor around | |||||
1169 | // and hooked up so as to preserve the loop structure, because | |||||
1170 | // trying to update it is complicated. So instead we preserve the | |||||
1171 | // loop structure and put the block on a dead code path. | |||||
1172 | SplitEdge(Switch, SISucc, DT, LI); | |||||
1173 | // Compute the successors instead of relying on the return value | |||||
1174 | // of SplitEdge, since it may have split the switch successor | |||||
1175 | // after PHI nodes. | |||||
1176 | BasicBlock *NewSISucc = DeadCase.getCaseSuccessor(); | |||||
1177 | BasicBlock *OldSISucc = *succ_begin(NewSISucc); | |||||
1178 | // Create an "unreachable" destination. | |||||
1179 | BasicBlock *Abort = BasicBlock::Create(Context, "us-unreachable", | |||||
1180 | Switch->getParent(), | |||||
1181 | OldSISucc); | |||||
1182 | new UnreachableInst(Context, Abort); | |||||
1183 | // Force the new case destination to branch to the "unreachable" | |||||
1184 | // block while maintaining a (dead) CFG edge to the old block. | |||||
1185 | NewSISucc->getTerminator()->eraseFromParent(); | |||||
1186 | BranchInst::Create(Abort, OldSISucc, | |||||
1187 | ConstantInt::getTrue(Context), NewSISucc); | |||||
1188 | // Release the PHI operands for this edge. | |||||
1189 | for (BasicBlock::iterator II = NewSISucc->begin(); | |||||
1190 | PHINode *PN = dyn_cast<PHINode>(II); ++II) | |||||
1191 | PN->setIncomingValue(PN->getBasicBlockIndex(Switch), | |||||
1192 | UndefValue::get(PN->getType())); | |||||
1193 | // Tell the domtree about the new block. We don't fully update the | |||||
1194 | // domtree here -- instead we force it to do a full recomputation | |||||
1195 | // after the pass is complete -- but we do need to inform it of | |||||
1196 | // new blocks. | |||||
1197 | if (DT) | |||||
1198 | DT->addNewBlock(Abort, NewSISucc); | |||||
1199 | } | |||||
1200 | ||||||
1201 | SimplifyCode(Worklist, L); | |||||
1202 | } | |||||
1203 | ||||||
1204 | /// Now that we have simplified some instructions in the loop, walk over it and | |||||
1205 | /// constant prop, dce, and fold control flow where possible. Note that this is | |||||
1206 | /// effectively a very simple loop-structure-aware optimizer. During processing | |||||
1207 | /// of this loop, L could very well be deleted, so it must not be used. | |||||
1208 | /// | |||||
1209 | /// FIXME: When the loop optimizer is more mature, separate this out to a new | |||||
1210 | /// pass. | |||||
1211 | /// | |||||
1212 | void LoopUnswitch::SimplifyCode(std::vector<Instruction*> &Worklist, Loop *L) { | |||||
1213 | const DataLayout &DL = L->getHeader()->getModule()->getDataLayout(); | |||||
1214 | while (!Worklist.empty()) { | |||||
1215 | Instruction *I = Worklist.back(); | |||||
1216 | Worklist.pop_back(); | |||||
1217 | ||||||
1218 | // Simple DCE. | |||||
1219 | if (isInstructionTriviallyDead(I)) { | |||||
1220 | DEBUG(dbgs() << "Remove dead instruction '" << *I)do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "Remove dead instruction '" << *I; } } while (0); | |||||
1221 | ||||||
1222 | // Add uses to the worklist, which may be dead now. | |||||
1223 | for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i) | |||||
1224 | if (Instruction *Use = dyn_cast<Instruction>(I->getOperand(i))) | |||||
1225 | Worklist.push_back(Use); | |||||
1226 | LPM->deleteSimpleAnalysisValue(I, L); | |||||
1227 | RemoveFromWorklist(I, Worklist); | |||||
1228 | I->eraseFromParent(); | |||||
1229 | ++NumSimplify; | |||||
1230 | continue; | |||||
1231 | } | |||||
1232 | ||||||
1233 | // See if instruction simplification can hack this up. This is common for | |||||
1234 | // things like "select false, X, Y" after unswitching made the condition be | |||||
1235 | // 'false'. TODO: update the domtree properly so we can pass it here. | |||||
1236 | if (Value *V = SimplifyInstruction(I, DL)) | |||||
1237 | if (LI->replacementPreservesLCSSAForm(I, V)) { | |||||
1238 | ReplaceUsesOfWith(I, V, Worklist, L, LPM); | |||||
1239 | continue; | |||||
1240 | } | |||||
1241 | ||||||
1242 | // Special case hacks that appear commonly in unswitched code. | |||||
1243 | if (BranchInst *BI = dyn_cast<BranchInst>(I)) { | |||||
1244 | if (BI->isUnconditional()) { | |||||
1245 | // If BI's parent is the only pred of the successor, fold the two blocks | |||||
1246 | // together. | |||||
1247 | BasicBlock *Pred = BI->getParent(); | |||||
1248 | BasicBlock *Succ = BI->getSuccessor(0); | |||||
1249 | BasicBlock *SinglePred = Succ->getSinglePredecessor(); | |||||
1250 | if (!SinglePred) continue; // Nothing to do. | |||||
1251 | assert(SinglePred == Pred && "CFG broken")((SinglePred == Pred && "CFG broken") ? static_cast< void> (0) : __assert_fail ("SinglePred == Pred && \"CFG broken\"" , "/tmp/buildd/llvm-toolchain-snapshot-3.8~svn246424/lib/Transforms/Scalar/LoopUnswitch.cpp" , 1251, __PRETTY_FUNCTION__)); | |||||
1252 | ||||||
1253 | DEBUG(dbgs() << "Merging blocks: " << Pred->getName() << " <- "do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "Merging blocks: " << Pred->getName() << " <- " << Succ->getName () << "\n"; } } while (0) | |||||
1254 | << Succ->getName() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType ("loop-unswitch")) { dbgs() << "Merging blocks: " << Pred->getName() << " <- " << Succ->getName () << "\n"; } } while (0); | |||||
1255 | ||||||
1256 | // Resolve any single entry PHI nodes in Succ. | |||||
1257 | while (PHINode *PN = dyn_cast<PHINode>(Succ->begin())) | |||||
1258 | ReplaceUsesOfWith(PN, PN->getIncomingValue(0), Worklist, L, LPM); | |||||
1259 | ||||||
1260 | // If Succ has any successors with PHI nodes, update them to have | |||||
1261 | // entries coming from Pred instead of Succ. | |||||
1262 | Succ->replaceAllUsesWith(Pred); | |||||
1263 | ||||||
1264 | // Move all of the successor contents from Succ to Pred. | |||||
1265 | Pred->getInstList().splice(BI, Succ->getInstList(), Succ->begin(), | |||||
1266 | Succ->end()); | |||||
1267 | LPM->deleteSimpleAnalysisValue(BI, L); | |||||
1268 | BI->eraseFromParent(); | |||||
1269 | RemoveFromWorklist(BI, Worklist); | |||||
1270 | ||||||
1271 | // Remove Succ from the loop tree. | |||||
1272 | LI->removeBlock(Succ); | |||||
1273 | LPM->deleteSimpleAnalysisValue(Succ, L); | |||||
1274 | Succ->eraseFromParent(); | |||||
1275 | ++NumSimplify; | |||||
1276 | continue; | |||||
1277 | } | |||||
1278 | ||||||
1279 | continue; | |||||
1280 | } | |||||
1281 | } | |||||
1282 | } |