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