From cd53f64367b3d9e2b1a82e589d09682a42f538ea Mon Sep 17 00:00:00 2001 From: Dan Gohman Date: Tue, 20 Oct 2009 20:06:09 +0000 Subject: [PATCH] Restore LoopUnswitch's block-oriented threshold. LoopUnswitch now checks both the estimated code size and the number of blocks when deciding whether to do a non-trivial unswitch. This protects it from some very undesirable worst-case behavior on large numbers of loop-unswitchable conditions, such as in the testcase in PR5259. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@84661 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Scalar/LoopUnswitch.cpp | 63 +++++++++++--------------- 1 file changed, 27 insertions(+), 36 deletions(-) diff --git a/lib/Transforms/Scalar/LoopUnswitch.cpp b/lib/Transforms/Scalar/LoopUnswitch.cpp index f6de3629260..223d2b9869c 100644 --- a/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -138,7 +138,6 @@ namespace { void SplitExitEdges(Loop *L, const SmallVector &ExitBlocks); bool UnswitchIfProfitable(Value *LoopCond, Constant *Val); - unsigned getLoopUnswitchCost(Value *LIC); void UnswitchTrivialCondition(Loop *L, Value *Cond, Constant *Val, BasicBlock *ExitBlock); void UnswitchNontrivialCondition(Value *LIC, Constant *OnVal, Loop *L); @@ -400,25 +399,6 @@ bool LoopUnswitch::IsTrivialUnswitchCondition(Value *Cond, Constant **Val, return true; } -/// getLoopUnswitchCost - Return the cost (code size growth) that will happen if -/// we choose to unswitch current loop on the specified value. -/// -unsigned LoopUnswitch::getLoopUnswitchCost(Value *LIC) { - // If the condition is trivial, always unswitch. There is no code growth for - // this case. - if (IsTrivialUnswitchCondition(LIC)) - return 0; - - // FIXME: This is overly conservative because it does not take into - // consideration code simplification opportunities. - CodeMetrics Metrics; - for (Loop::block_iterator I = currentLoop->block_begin(), - E = currentLoop->block_end(); - I != E; ++I) - Metrics.analyzeBasicBlock(*I); - return Metrics.NumInsts; -} - /// UnswitchIfProfitable - We have found that we can unswitch currentLoop when /// LoopCond == Val to simplify the loop. If we decide that this is profitable, /// unswitch the loop, reprocess the pieces, then return true. @@ -427,24 +407,35 @@ bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val){ initLoopData(); Function *F = loopHeader->getParent(); + // If the condition is trivial, always unswitch. There is no code growth for + // this case. + if (!IsTrivialUnswitchCondition(LoopCond)) { + // Check to see if it would be profitable to unswitch current loop. - // Check to see if it would be profitable to unswitch current loop. - unsigned Cost = getLoopUnswitchCost(LoopCond); - - // Do not do non-trivial unswitch while optimizing for size. - if (Cost && OptimizeForSize) - return false; - if (Cost && !F->isDeclaration() && F->hasFnAttr(Attribute::OptimizeForSize)) - return false; + // Do not do non-trivial unswitch while optimizing for size. + if (OptimizeForSize || F->hasFnAttr(Attribute::OptimizeForSize)) + return false; - if (Cost > Threshold) { - // FIXME: this should estimate growth by the amount of code shared by the - // resultant unswitched loops. - // - DEBUG(errs() << "NOT unswitching loop %" - << currentLoop->getHeader()->getName() << ", cost too high: " - << currentLoop->getBlocks().size() << "\n"); - return false; + // FIXME: This is overly conservative because it does not take into + // consideration code simplification opportunities and code that can + // be shared by the resultant unswitched loops. + CodeMetrics Metrics; + for (Loop::block_iterator I = currentLoop->block_begin(), + E = currentLoop->block_end(); + I != E; ++I) + Metrics.analyzeBasicBlock(*I); + + // Limit the number of instructions to avoid causing significant code + // 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) { + DEBUG(errs() << "NOT unswitching loop %" + << currentLoop->getHeader()->getName() << ", cost too high: " + << currentLoop->getBlocks().size() << "\n"); + return false; + } } Constant *CondVal; -- 2.34.1