Index: lib/Transforms/Scalar/SimpleLoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/SimpleLoopUnswitch.cpp +++ lib/Transforms/Scalar/SimpleLoopUnswitch.cpp @@ -71,13 +71,18 @@ static cl::opt UnswitchThreshold("unswitch-threshold", cl::init(50), cl::Hidden, cl::desc("The cost threshold for unswitching a loop.")); + +static cl::opt EnableUnswitchCostMultiplier( + "enable-unswitch-cost-multiplier", cl::init(true), cl::Hidden, + cl::desc("Enable unswitch cost multiplier that prohibits exponential " + "explosion in nontrivial unswitch.")); static cl::opt UnswitchSiblingsToplevelDiv( "unswitch-siblings-toplevel-div", cl::init(2), cl::Hidden, - cl::desc("toplevel siblings divisor for cost multiplier")); + cl::desc("Toplevel siblings divisor for cost multiplier.")); static cl::opt UnswitchCandidatesBottomCap( "unswitch-candidates-bottom-cap", cl::init(8), cl::Hidden, - cl::desc("amount of unswitch candidates that are ignored when calculating " - "cost multiplier")); + cl::desc("Amount of unswitch candidates that are ignored when calculating " + "cost multiplier.")); static cl::opt UnswitchGuards( "simple-loop-unswitch-guards", cl::init(true), cl::Hidden, cl::desc("If enabled, simple loop unswitching will also consider " @@ -2266,6 +2271,59 @@ return CheckBI; } +/// Cost multiplier is a way to limit potentially exponential behavior +/// of loop-unswitch. Cost is multipied in proportion of 2^number of unswitch +/// candidates available. Also accounting for the number of "sibling" loops with +/// the idea to account for previous unswitches that already happened on this +/// cluster of loops. Formula is kept intentionally simple since it is designed +/// to limit the worst case behavior. It is not an attempt to provide a detailed +/// heuristic size prediction. +static int calculateUnswitchCostMultiplier( + Instruction &TI, Loop &L, LoopInfo &LI, + ArrayRef>> + UnswitchCandidates) { + + if (!EnableUnswitchCostMultiplier) + return 1; + + // Violated guards always exit the loop, thus they can never cause exponential behavior. + // TODO: Catch more cases when branch exits the loop. + if (isGuard(&TI)) + return 1; + + auto *ParentL = L.getParentLoop(); + int SiblingsCount = (ParentL ? ParentL->getSubLoopsVector().size() + : std::distance(LI.begin(), LI.end())); + // Ignore up to the "bottom cap" number of unswitch candidates when + // calculating the power-of-two scaling of the cost. The main idea + // with this cap is to allow a small number of unswitches to happen + // and rely more on siblings multiplier (see below) when the number + // of candidates is small. + unsigned CandidatesPower = std::max( + (int)UnswitchCandidates.size() - (int)UnswitchCandidatesBottomCap, 0); + + // Allowing top-level loops to spread a bit more than nested ones. + int SiblingsMultiplier = + std::max((ParentL ? SiblingsCount + : SiblingsCount / (int)UnswitchSiblingsToplevelDiv), + 1); + // Compute the cost multiplier in a way that won't overflow by saturating + // at an upper bound. + int CostMultiplier; + if (CandidatesPower > Log2_32(UnswitchThreshold) || + SiblingsMultiplier > UnswitchThreshold) + CostMultiplier = UnswitchThreshold; + else + CostMultiplier = std::min(SiblingsMultiplier * (1 << CandidatesPower), + (int)UnswitchThreshold); + + LLVM_DEBUG(dbgs() << " Computed multiplier " << CostMultiplier + << " (siblings " << SiblingsMultiplier << " * candidates " + << (1 << CandidatesPower) << ")" + << " for unswitch candidate: " << TI << "\n"); + return CostMultiplier; +} + static bool unswitchBestCondition(Loop &L, DominatorTree &DT, LoopInfo &LI, AssumptionCache &AC, TargetTransformInfo &TTI, @@ -2479,43 +2537,13 @@ int CandidateCost = ComputeUnswitchedCost( TI, /*FullUnswitch*/ !BI || (Invariants.size() == 1 && Invariants[0] == BI->getCondition())); - // Now we try to limit potentially exponential behavior of loop-unswitch - // by multiplying the cost in proportion of 2^number of unswitch candidates - // available. Also accounting for the number of "sibling" loops with the - // idea to account for previous unswitches that already happened on this - // cluster of loops. Formula is kept intentionally simple since it a cap for - // worst cases and not an attempt to make exact size predictions. - int CostMultiplier = 1; - if (!isGuard(&TI)) { - auto *ParentL = L.getParentLoop(); - int SiblingsCount = (ParentL ? ParentL->getSubLoopsVector().size() - : std::distance(LI.begin(), LI.end())); - // Applying a "bottom cap" to allow a certain amount of unswitch - // candidates before going into prohibitive power-of-two. - unsigned CandidatesPower = std::max( - int(UnswitchCandidates.size() - (int)UnswitchCandidatesBottomCap), 0); - - // Allowing top-level loops to spread a bit more than nested ones. - int SiblingsMultiplier = - std::max((ParentL ? SiblingsCount - : SiblingsCount / (int)UnswitchSiblingsToplevelDiv), - 1); - // Handle possible overflow. UnswitchThreshold is a good upper boundary - // since multiplying by it will definitely move cost over the threshold. - if (CandidatesPower > Log2_32(UnswitchThreshold) || - SiblingsMultiplier > UnswitchThreshold) - CostMultiplier = UnswitchThreshold; - else - CostMultiplier = std::min(SiblingsMultiplier * (1 << CandidatesPower), - (int)UnswitchThreshold); - - LLVM_DEBUG(dbgs() << " Computed multiplier " << CostMultiplier - << "(siblings " << SiblingsMultiplier - << " * candidates " << (1 << CandidatesPower) << ")" - << " for unswitch candidate: " << TI << "\n"); - } - - CandidateCost *= std::max(CostMultiplier, 1); + // Calculate cost multiplier which is a tool to limit potentially + // exponential behavior of loop-unswitch. + int CostMultiplier = + calculateUnswitchCostMultiplier(TI, L, LI, UnswitchCandidates); + assert((CostMultiplier > 0 && CostMultiplier <= UnswitchThreshold) && + "cost multiplier needs to be in the range of 0..UnswitchThreshold"); + CandidateCost *= CostMultiplier; LLVM_DEBUG(dbgs() << " Computed cost of " << CandidateCost << "(multiplier: " << CostMultiplier << ")" << " for unswitch candidate: " << TI << "\n"); Index: test/Transforms/SimpleLoopUnswitch/exponential-nontrivial-unswitch-nested.ll =================================================================== --- /dev/null +++ test/Transforms/SimpleLoopUnswitch/exponential-nontrivial-unswitch-nested.ll @@ -0,0 +1,93 @@ +; +; There should be just a single copy of each loop - and thus 3 volatile store - +; when strictest mutiplier candidates formula (cap == 0) is enforced: + +; RUN: opt < %s -enable-nontrivial-unswitch -enable-unswitch-cost-multiplier=true \ +; RUN: -unswitch-candidates-bottom-cap=0 -unswitch-siblings-toplevel-div=1 \ +; RUN: -passes=unswitch -S | grep volatile | count 3 +; +; RUN: opt < %s -enable-nontrivial-unswitch -enable-unswitch-cost-multiplier=true \ +; RUN: -unswitch-candidates-bottom-cap=0 -unswitch-siblings-toplevel-div=16 \ +; RUN: -passes=unswitch -S | grep volatile | count 3 +; +; Get +; 2^(num conds) * (depth) == 2^5 * 3 == 96 +; loop when cost multiplier is disabled: +; +; RUN: opt < %s -enable-nontrivial-unswitch -enable-unswitch-cost-multiplier=false \ +; RUN: -passes=unswitch -S | grep volatile | count 96 + +declare void @bar() + +define void @loop_nested3_conds5(i32* %addr, i1 %c1, i1 %c2, i1 %c3, i1 %c4, i1 %c5) { +entry: + %addr1 = getelementptr i32, i32* %addr, i64 0 + %addr2 = getelementptr i32, i32* %addr, i64 1 + %addr3 = getelementptr i32, i32* %addr, i64 2 + br label %outer +outer: + %iv1 = phi i32 [0, %entry], [%iv1.next, %outer_latch] + %iv1.next = add i32 %iv1, 1 + ;; skip nontrivial unswitch + call void @bar() + br label %middle +middle: + %iv2 = phi i32 [0, %outer], [%iv2.next, %middle_latch] + %iv2.next = add i32 %iv2, 1 + ;; skip nontrivial unswitch + call void @bar() + br label %loop +loop: + %iv3 = phi i32 [0, %middle], [%iv3.next, %loop_latch] + %iv3.next = add i32 %iv3, 1 + ;; skip nontrivial unswitch + call void @bar() + br i1 %c1, label %loop_next1_left, label %loop_next1_right +loop_next1_left: + br label %loop_next1 +loop_next1_right: + br label %loop_next1 + +loop_next1: + br i1 %c2, label %loop_next2_left, label %loop_next2_right +loop_next2_left: + br label %loop_next2 +loop_next2_right: + br label %loop_next2 + +loop_next2: + br i1 %c3, label %loop_next3_left, label %loop_next3_right +loop_next3_left: + br label %loop_next3 +loop_next3_right: + br label %loop_next3 + +loop_next3: + br i1 %c4, label %loop_next4_left, label %loop_next4_right +loop_next4_left: + br label %loop_next4 +loop_next4_right: + br label %loop_next4 + +loop_next4: + br i1 %c5, label %loop_latch_left, label %loop_latch_right +loop_latch_left: + br label %loop_latch +loop_latch_right: + br label %loop_latch + +loop_latch: + store volatile i32 0, i32* %addr1 + %test_loop = icmp slt i32 %iv3, 50 + br i1 %test_loop, label %loop, label %middle_latch +middle_latch: + store volatile i32 0, i32* %addr2 + %test_middle = icmp slt i32 %iv2, 50 + br i1 %test_middle, label %middle, label %outer_latch +outer_latch: + store volatile i32 0, i32* %addr3 + %test_outer = icmp slt i32 %iv1, 50 + br i1 %test_outer, label %outer, label %exit +exit: + ret void +} Index: test/Transforms/SimpleLoopUnswitch/exponential-nontrivial-unswitch.ll =================================================================== --- /dev/null +++ test/Transforms/SimpleLoopUnswitch/exponential-nontrivial-unswitch.ll @@ -0,0 +1,68 @@ +; +; There should be just a single copy of loop - and thus single volatile store - +; when strictest mutiplier candidates formula (cap == 0) is enforced: +; +; RUN: opt < %s -enable-nontrivial-unswitch -enable-unswitch-cost-multiplier=true \ +; RUN: -unswitch-candidates-bottom-cap=0 -unswitch-siblings-toplevel-div=1 \ +; RUN: -passes=unswitch -S | grep volatile | count 1 +; +; RUN: opt < %s -enable-nontrivial-unswitch -enable-unswitch-cost-multiplier=true \ +; RUN: -unswitch-candidates-bottom-cap=0 -unswitch-siblings-toplevel-div=8 \ +; RUN: -passes=unswitch -S | grep volatile | count 1 +; +; With relaxed candidates multiplier (cap == 8) we should allow some unswitches +; to happen until siblings multiplier starts kicking in: +; +; RUN: opt < %s -enable-nontrivial-unswitch -enable-unswitch-cost-multiplier=true \ +; RUN: -unswitch-candidates-bottom-cap=8 -unswitch-siblings-toplevel-div=1 \ +; RUN: -passes=unswitch -S | grep volatile | count 5 +; +; With relaxed candidates multiplier (cap == 8) and with relaxed siblings +; multiplier for top-level loops (toplevel-div == 8) we should get +; 2^(num conds) == 2^5 == 32 +; copies of the loop: +; +; RUN: opt < %s -enable-nontrivial-unswitch -enable-unswitch-cost-multiplier=true \ +; RUN: -unswitch-candidates-bottom-cap=8 -unswitch-siblings-toplevel-div=8 \ +; RUN: -passes=unswitch -S | grep volatile | count 32 +; +; Similarly get +; 2^(num conds) == 2^5 == 32 +; copies of the loop when cost multiplier is disabled: +; +; RUN: opt < %s -enable-nontrivial-unswitch -enable-unswitch-cost-multiplier=false \ +; RUN: -passes=unswitch -S | grep volatile | count 32 +; + +define void @loop_simple5(i32* %addr, i1 %c1, i1 %c2, i1 %c3, i1 %c4, i1 %c5) { +entry: + br label %loop +loop: + %iv = phi i32 [0, %entry], [%iv.next, %loop_latch] + %iv.next = add i32 %iv, 1 + br i1 %c1, label %loop_next1, label %loop_next1_right +loop_next1_right: + br label %loop_next1 +loop_next1: + br i1 %c2, label %loop_next2, label %loop_next2_right +loop_next2_right: + br label %loop_next2 +loop_next2: + br i1 %c3, label %loop_next3, label %loop_next3_right +loop_next3_right: + br label %loop_next3 +loop_next3: + br i1 %c4, label %loop_next4, label %loop_next4_right +loop_next4_right: + br label %loop_next4 +loop_next4: + br i1 %c5, label %loop_latch, label %loop_latch_right +loop_latch_right: + br label %loop_latch +loop_latch: + store volatile i32 0, i32* %addr + %test_loop = icmp slt i32 %iv, 50 + br i1 %test_loop, label %loop, label %exit +exit: + ret void +}