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 @@ -20,17 +20,23 @@ #include "llvm/IR/PassManager.h" #include "llvm/Transforms/InstCombine/InstCombineWorklist.h" +#include + namespace llvm { class InstCombinePass : public PassInfoMixin { InstCombineWorklist Worklist; bool ExpensiveCombines; + unsigned MaxIterations; public: static StringRef name() { return "InstCombinePass"; } explicit InstCombinePass(bool ExpensiveCombines = true) - : ExpensiveCombines(ExpensiveCombines) {} + : ExpensiveCombines(ExpensiveCombines), MaxIterations(UINT_MAX) {} + + explicit InstCombinePass(bool ExpensiveCombines, unsigned MaxIterations) + : ExpensiveCombines(ExpensiveCombines), MaxIterations(MaxIterations) {} PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM); }; @@ -42,11 +48,13 @@ 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); + InstructionCombiningPass(bool ExpensiveCombines, unsigned MaxIterations); void getAnalysisUsage(AnalysisUsage &AU) const override; bool runOnFunction(Function &F) override; @@ -65,6 +73,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 @@ -130,6 +130,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(UINT_MAX)); + static cl::opt MaxArraySize("instcombine-maxarray-size", cl::init(1024), cl::desc("Maximum array size considered when doing a combine")); @@ -3538,10 +3543,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 +3566,16 @@ 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"); + break; + } + LLVM_DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on " << F.getName() << "\n"); @@ -3574,9 +3587,11 @@ if (!IC.run()) break; + + MadeIRChange = true; } - return MadeIRChange || Iteration > 1; + return MadeIRChange; } PreservedAnalyses InstCombinePass::run(Function &F, @@ -3596,8 +3611,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 +3662,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 +3708,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,33 @@ +; 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: [[COND1:%.*]] = icmp sgt i32 %X, -32768 +; ONE: [[TMP:%.*]] = and i1 [[COND0]], [[COND1]] +; ONE-NEXT: ret i1 [[TMP]] + +; FIXPOINT-LABEL: @v0_select_of_consts( +; FIXPOINT: [[TMP:%.*]] = icmp ult i32 [[XOFF:%.*]], 65535 +; FIXPOINT-NEXT: ret i1 [[TMP]] + + %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 +}