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