diff --git a/llvm/include/llvm/Transforms/InstCombine/InstCombine.h b/llvm/include/llvm/Transforms/InstCombine/InstCombine.h --- a/llvm/include/llvm/Transforms/InstCombine/InstCombine.h +++ b/llvm/include/llvm/Transforms/InstCombine/InstCombine.h @@ -24,13 +24,14 @@ class InstCombinePass : public PassInfoMixin { InstCombineWorklist Worklist; - bool ExpensiveCombines; + const bool ExpensiveCombines; + const unsigned MaxIterations; public: static StringRef name() { return "InstCombinePass"; } - explicit InstCombinePass(bool ExpensiveCombines = true) - : ExpensiveCombines(ExpensiveCombines) {} + explicit InstCombinePass(bool ExpensiveCombines = true); + explicit InstCombinePass(bool ExpensiveCombines, unsigned MaxIterations); PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; @@ -42,11 +43,14 @@ class InstructionCombiningPass : public FunctionPass { InstCombineWorklist Worklist; const bool ExpensiveCombines; + const unsigned MaxIterations; public: static char ID; // Pass identification, replacement for typeid - InstructionCombiningPass(bool ExpensiveCombines = true); + explicit InstructionCombiningPass(bool ExpensiveCombines = true); + explicit InstructionCombiningPass(bool ExpensiveCombines, + unsigned MaxIterations); void getAnalysisUsage(AnalysisUsage &AU) const override; bool runOnFunction(Function &F) override; @@ -65,6 +69,8 @@ // %Z = add int 2, %X // FunctionPass *createInstructionCombiningPass(bool ExpensiveCombines = true); +FunctionPass *createInstructionCombiningPass(bool ExpensiveCombines, + unsigned MaxIterations); } #endif diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp --- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -122,6 +122,8 @@ DEBUG_COUNTER(VisitCounter, "instcombine-visit", "Controls which instructions are visited"); +static constexpr unsigned InstCombineDefaultMaxIterations = 1000; + static cl::opt EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"), cl::init(true)); @@ -130,6 +132,11 @@ EnableExpensiveCombines("expensive-combines", cl::desc("Enable expensive instruction combines")); +static cl::opt LimitMaxIterations( + "instcombine-max-iterations", + cl::desc("Limit the maximum number of instruction combining iterations"), + cl::init(InstCombineDefaultMaxIterations)); + static cl::opt MaxArraySize("instcombine-maxarray-size", cl::init(1024), cl::desc("Maximum array size considered when doing a combine")); @@ -3538,10 +3545,11 @@ Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA, AssumptionCache &AC, TargetLibraryInfo &TLI, DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI, - ProfileSummaryInfo *PSI, bool ExpensiveCombines = true, - LoopInfo *LI = nullptr) { + ProfileSummaryInfo *PSI, bool ExpensiveCombines, unsigned MaxIterations, + LoopInfo *LI) { auto &DL = F.getParent()->getDataLayout(); ExpensiveCombines |= EnableExpensiveCombines; + MaxIterations = std::min(MaxIterations, LimitMaxIterations.getValue()); /// Builder - This is an IRBuilder that automatically inserts new /// instructions into the worklist when they are created. @@ -3560,9 +3568,19 @@ MadeIRChange = LowerDbgDeclare(F); // Iterate while there is work to do. - int Iteration = 0; + unsigned Iteration = 0; while (true) { ++Iteration; + if (Iteration > MaxIterations) { + LLVM_DEBUG(dbgs() << "\n\n[IC] Iteration limit #" << MaxIterations + << " on " << F.getName() + << " reached; stopping before reaching a fixpoint\n"); + LLVM_DEBUG(dbgs().flush()); + assert(Iteration <= InstCombineDefaultMaxIterations && + "InstCombine stuck in an infinite loop?"); + break; + } + LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on " << F.getName() << "\n"); @@ -3574,11 +3592,19 @@ if (!IC.run()) break; + + MadeIRChange = true; } - return MadeIRChange || Iteration > 1; + return MadeIRChange; } +InstCombinePass::InstCombinePass(bool ExpensiveCombines) + : ExpensiveCombines(ExpensiveCombines), MaxIterations(LimitMaxIterations) {} + +InstCombinePass::InstCombinePass(bool ExpensiveCombines, unsigned MaxIterations) + : ExpensiveCombines(ExpensiveCombines), MaxIterations(MaxIterations) {} + PreservedAnalyses InstCombinePass::run(Function &F, FunctionAnalysisManager &AM) { auto &AC = AM.getResult(F); @@ -3596,8 +3622,9 @@ auto *BFI = (PSI && PSI->hasProfileSummary()) ? &AM.getResult(F) : nullptr; - if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, - BFI, PSI, ExpensiveCombines, LI)) + if (!combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, BFI, + PSI, ExpensiveCombines, MaxIterations, + LI)) // No changes, all analyses are preserved. return PreservedAnalyses::all(); @@ -3646,14 +3673,23 @@ &getAnalysis().getBFI() : nullptr; - return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, - BFI, PSI, ExpensiveCombines, LI); + return combineInstructionsOverFunction(F, Worklist, AA, AC, TLI, DT, ORE, BFI, + PSI, ExpensiveCombines, MaxIterations, + LI); } char InstructionCombiningPass::ID = 0; InstructionCombiningPass::InstructionCombiningPass(bool ExpensiveCombines) - : FunctionPass(ID), ExpensiveCombines(ExpensiveCombines) { + : FunctionPass(ID), ExpensiveCombines(ExpensiveCombines), + MaxIterations(UINT_MAX) { + initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry()); +} + +InstructionCombiningPass::InstructionCombiningPass(bool ExpensiveCombines, + unsigned MaxIterations) + : FunctionPass(ID), ExpensiveCombines(ExpensiveCombines), + MaxIterations(MaxIterations) { initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry()); } @@ -3683,6 +3719,11 @@ return new InstructionCombiningPass(ExpensiveCombines); } +FunctionPass *llvm::createInstructionCombiningPass(bool ExpensiveCombines, + unsigned MaxIterations) { + return new InstructionCombiningPass(ExpensiveCombines, MaxIterations); +} + void LLVMAddInstructionCombiningPass(LLVMPassManagerRef PM) { unwrap(PM)->add(createInstructionCombiningPass()); } diff --git a/llvm/test/Transforms/InstCombine/limit-max-iterations.ll b/llvm/test/Transforms/InstCombine/limit-max-iterations.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/InstCombine/limit-max-iterations.ll @@ -0,0 +1,41 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -instcombine --instcombine-max-iterations=0 -S | FileCheck %s --check-prefix=ZERO +; RUN: opt < %s -instcombine --instcombine-max-iterations=1 -S | FileCheck %s --check-prefix=ONE +; RUN: opt < %s -instcombine -S | FileCheck %s --check-prefix=FIXPOINT + +; Based on xor-of-icmps-with-extra-uses.ll. This requires multiple iterations of +; InstCombine to reach a fixpoint. + +define i1 @v0_select_of_consts(i32 %X, i32* %selected) { +; ZERO-LABEL: @v0_select_of_consts( +; ZERO-NEXT: [[COND0:%.*]] = icmp sgt i32 [[X:%.*]], 32767 +; ZERO-NEXT: [[COND1:%.*]] = icmp sgt i32 [[X]], -32768 +; ZERO-NEXT: [[SELECT:%.*]] = select i1 [[COND0]], i32 32767, i32 -32768 +; ZERO-NEXT: store i32 [[SELECT]], i32* [[SELECTED:%.*]] +; ZERO-NEXT: [[RES:%.*]] = xor i1 [[COND0]], [[COND1]] +; ZERO-NEXT: ret i1 [[RES]] + +; ONE-LABEL: @v0_select_of_consts( +; ONE-NEXT: [[COND0:%.*]] = icmp sle i32 [[X:%.*]], 32767 +; ONE-NEXT: [[COND0_NOT:%.*]] = xor i1 [[COND0]], true +; ONE-NEXT: [[COND1:%.*]] = icmp sgt i32 [[X]], -32768 +; ONE-NEXT: [[SELECT:%.*]] = select i1 [[COND0_NOT]], i32 32767, i32 -32768 +; ONE-NEXT: store i32 [[SELECT]], i32* [[SELECTED:%.*]], align 4 +; ONE-NEXT: [[TMP1:%.*]] = and i1 [[COND0]], [[COND1]] +; ONE-NEXT: ret i1 [[TMP1]] + +; FIXPOINT-LABEL: @v0_select_of_consts( +; FIXPOINT-NEXT: [[COND0_INV:%.*]] = icmp sgt i32 [[X:%.*]], 32767 +; FIXPOINT-NEXT: [[SELECT:%.*]] = select i1 [[COND0_INV]], i32 32767, i32 -32768 +; FIXPOINT-NEXT: store i32 [[SELECT]], i32* [[SELECTED:%.*]], align 4 +; FIXPOINT-NEXT: [[X_OFF:%.*]] = add i32 [[X]], 32767 +; FIXPOINT-NEXT: [[TMP1:%.*]] = icmp ult i32 [[X_OFF]], 65535 +; FIXPOINT-NEXT: ret i1 [[TMP1]] + + %cond0 = icmp sgt i32 %X, 32767 + %cond1 = icmp sgt i32 %X, -32768 + %select = select i1 %cond0, i32 32767, i32 -32768 + store i32 %select, i32* %selected + %res = xor i1 %cond0, %cond1 + ret i1 %res +}