From ac12ef4ad22de941655c889f319a4c6923b77620 Mon Sep 17 00:00:00 2001 From: Stepan Dyatkovskiy Date: Wed, 14 Dec 2011 19:19:17 +0000 Subject: Fix for bug #11429: Wrong behaviour for switches. Small improvement for code size heuristics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146578 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnswitch.cpp | 93 ++++++++++++++++++++++++++++++---- 1 file changed, 82 insertions(+), 11 deletions(-) (limited to 'lib/Transforms/Scalar/LoopUnswitch.cpp') diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp index 301791a90d..a2d0e98cd3 100644 --- a/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -71,7 +71,9 @@ namespace { // LoopProcessWorklist - Used to check if second loop needs processing // after RewriteLoopBodyWithConditionConstant rewrites first loop. std::vector LoopProcessWorklist; - SmallPtrSet UnswitchedVals; + + // FIXME: Consider custom class for this. + std::map > UnswitchedVals; bool OptimizeForSize; bool redoLoop; @@ -117,7 +119,15 @@ namespace { private: virtual void releaseMemory() { - UnswitchedVals.clear(); + // We need to forget about all switches in the current loop. + // FIXME: Do it better than enumerating all blocks of code + // and see if it is a switch instruction. + for (Loop::block_iterator I = currentLoop->block_begin(), + E = currentLoop->block_end(); I != E; ++I) { + SwitchInst* SI = dyn_cast((*I)->getTerminator()); + if (SI) + UnswitchedVals.erase(SI); + } } /// RemoveLoopFromWorklist - If the specified loop is on the loop worklist, @@ -128,6 +138,12 @@ namespace { if (I != LoopProcessWorklist.end()) LoopProcessWorklist.erase(I); } + + /// For new loop switches we clone info about values that was + /// already unswitched and has redundant successors. + /// Note, that new loop data is stored inside the VMap. + void CloneUnswitchedVals(const ValueToValueMapTy& VMap, + const BasicBlock* SrcBB); void initLoopData() { loopHeader = currentLoop->getHeader(); @@ -255,13 +271,25 @@ bool LoopUnswitch::processCurrentLoop() { } else if (SwitchInst *SI = dyn_cast(TI)) { Value *LoopCond = FindLIVLoopCondition(SI->getCondition(), currentLoop, Changed); - if (LoopCond && SI->getNumCases() > 1) { + unsigned NumCases = SI->getNumCases(); + if (LoopCond && NumCases > 1) { // Find a value to unswitch on: // FIXME: this should chose the most expensive case! // FIXME: scan for a case with a non-critical edge? - Constant *UnswitchVal = SI->getCaseValue(1); + Constant *UnswitchVal = NULL; + // Do not process same value again and again. - if (!UnswitchedVals.insert(UnswitchVal)) + // At this point we have some cases already unswitched and + // some not yet unswitched. Let's find the first not yet unswitched one. + for (unsigned i = 1; i < NumCases; ++i) { + Constant* UnswitchValCandidate = SI->getCaseValue(i); + if (!UnswitchedVals[SI].count(UnswitchValCandidate)) { + UnswitchVal = UnswitchValCandidate; + break; + } + } + + if (!UnswitchVal) continue; if (UnswitchIfProfitable(LoopCond, UnswitchVal)) { @@ -287,6 +315,23 @@ bool LoopUnswitch::processCurrentLoop() { return Changed; } +/// For new loop switches we clone info about values that was +/// already unswitched and has redundant successors. +/// Not that new loop data is stored inside the VMap. +void LoopUnswitch::CloneUnswitchedVals(const ValueToValueMapTy& VMap, + const BasicBlock* SrcBB) { + + const SwitchInst* SI = dyn_cast(SrcBB->getTerminator()); + if (SI && UnswitchedVals.count(SI)) { + // Don't clone a totally simplified switch. + if (isa(SI->getCondition())) + return; + Value* I = VMap.lookup(SI); + assert(I && "All instructions that are in SrcBB must be in VMap."); + UnswitchedVals[cast(I)] = UnswitchedVals[SI]; + } +} + /// isTrivialLoopExitBlock - Check to see if all paths from BB exit the /// loop with no side effects (including infinite loops). /// @@ -378,14 +423,25 @@ bool LoopUnswitch::IsTrivialUnswitchCondition(Value *Cond, Constant **Val, // Check to see if a successor of the switch is guaranteed to go to the // latch block or exit through a one exit block without having any // side-effects. If so, determine the value of Cond that causes it to do - // this. Note that we can't trivially unswitch on the default case. - for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) - if ((LoopExitBB = isTrivialLoopExitBlock(currentLoop, + // this. + // Note that we can't trivially unswitch on the default case or + // on already unswitched cases. + for (unsigned i = 1, e = SI->getNumSuccessors(); i != e; ++i) { + BasicBlock* LoopExitCandidate; + if ((LoopExitCandidate = isTrivialLoopExitBlock(currentLoop, SI->getSuccessor(i)))) { // Okay, we found a trivial case, remember the value that is trivial. - if (Val) *Val = SI->getCaseValue(i); + ConstantInt* CaseVal = SI->getCaseValue(i); + + // Check that it was not unswitched before, since already unswitched + // trivial vals are looks trivial too. + if (UnswitchedVals[SI].count(CaseVal)) + continue; + LoopExitBB = LoopExitCandidate; + if (Val) *Val = CaseVal; break; } + } } // If we didn't find a single unique LoopExit block, or if the loop exit block @@ -447,8 +503,14 @@ bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val) { // expansion, and the number of basic blocks, to avoid loops with // large numbers of branches which cause loop unswitching to go crazy. // This is a very ad-hoc heuristic. - if (Metrics.NumInsts > Threshold || - Metrics.NumBlocks * 5 > Threshold || + + unsigned NumUnswitched = + (NumSwitches + NumBranches) + 1 /*take in account current iteration*/; + + unsigned NumInsts = Metrics.NumInsts * NumUnswitched; + unsigned NumBlocks = Metrics.NumBlocks * NumUnswitched; + + if (NumInsts > Threshold || NumBlocks * 5 > Threshold || Metrics.containsIndirectBr || Metrics.isRecursive) { DEBUG(dbgs() << "NOT unswitching loop %" << currentLoop->getHeader()->getName() << ", cost too high: " @@ -620,6 +682,12 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, ValueToValueMapTy VMap; for (unsigned i = 0, e = LoopBlocks.size(); i != e; ++i) { BasicBlock *NewBB = CloneBasicBlock(LoopBlocks[i], VMap, ".us", F); + + // Inherit simplified switches info for NewBB + // We needn't pass NewBB since its instructions are already contained + // inside the VMap. + CloneUnswitchedVals(VMap, LoopBlocks[i]); + NewBlocks.push_back(NewBB); VMap[LoopBlocks[i]] = NewBB; // Keep the BB mapping. LPM->cloneBasicBlockSimpleAnalysis(LoopBlocks[i], NewBB, L); @@ -945,6 +1013,9 @@ void LoopUnswitch::RewriteLoopBodyWithConditionConstant(Loop *L, Value *LIC, BasicBlock *Switch = SI->getParent(); BasicBlock *SISucc = SI->getSuccessor(DeadCase); BasicBlock *Latch = L->getLoopLatch(); + + UnswitchedVals[SI].insert(Val); + if (!SI->findCaseDest(SISucc)) continue; // Edge is critical. // If the DeadCase successor dominates the loop latch, then the // transformation isn't safe since it will delete the sole predecessor edge -- cgit v1.2.3