[InstCombine] Allow to limit the max number of iterations

[kuhar]

Summary

This patch teaches InstCombine to accept a new parameter: maximum number of iterations over functions.

InstCombine tries to simplify instructions by iterating over the whole function until the function stops changing. As a consequence, the last iteration before reaching a fixpoint visits all instructions in the worklist and never performs any rewrites.

Bounding the number of iterations can have 2 benefits:

• In case the users of the pass can make a good guess about the number of required iterations, we can save the time normally spent on the last iteration that doesn't change anything.
• When the wants to use InstCombine as a cleanup pass, it may be enough to run just a few iterations and stop even before reaching a fixpoint. This can be also useful for implementing a lightweight pass pipeline (think -O1).

This patch does not change the behavior of opt or Clang -- limiting the number of iterations is entirely opt-in.

[spatel]

I like this idea. In addition to the stated uses, it can be used to improve debugging of what used to be infinite loops (see D71164 as a current example).
I think you're right that this doesn't change current behavior because:

++Iteration;
if (Iteration > MaxIterations) {

...will silently overflow because we initialized the max to UINT_MAX. So an infinite loop will still be an infinite loop. But what if we instead initialize that to some lower constant (1000?) and then assert that we haven't hit LimitMaxIterations?

llvm/test/Transforms/InstCombine/limit-max-iterations.ll

2

This looks like you used utils/update_test_checks.py, but then made some manual edits? Was the script output not good in some way? If not, I prefer to leave the auto-generated output as-is for easier updating in the future.

[xbolva00]

I like this technical solution more than "AggresiveInstCombine" concept (-O3 only).

Like you suggested, with -O2/-O1 we should use smaller number of iterations.

[lebedev.ri]

I just want to note that in general this doesn't limit the amount of folding,
we still process the entire worklist; we have to re-process entire worklist
because we are clearly inconsistent with how we fill said worklist.

[kuhar]

Thanks for the suggestions.

I changed the default bound to 1000 and regenerated the filecheck directives with the update_test_checks script.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

125

I think it should be

static constexpr unsigned InstCombineDefaultMaxIterations = std::numeric_limits<unsigned>::max - 1;

if the goal is to catch infinite loops while avoiding unintentional capping of iteration limit.

[kuhar]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

125

UINT_MAX is about 4*10^9. I don't think we will ever reach that number of iterations on any reasonable-sized input bitcode.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

125

Yes, that is kind-of the point, i'm not confident we won't reach 1000 in normal situations.

[kuhar]

I ran some experiments to see how many iterations of InstCombine are necessary on real-world C++ applications. I paste the results below.
The numbers were collected by running InstCombine in a Full-LTO-like scenario: first I compiled all the code with -O3 with *optimizations disabled*, then I linked it together (using gllvm), and gave it to opt with -O3.

Name	Bitcode size [MB]	Max Iterations	Total InstCombine Executions	Total Iterations	Average Iterations Per Execution
sqlite3.bc	3	5	12685	17907	1.41
wasm-dis.bc	25	4	295002	361302	1.22
wasm-metadce.bc	25	4	299757	367117	1.22
wasm-reduce.bc	25	4	298667	365802	1.22
wasm-as.bc	25	4	296061	362598	1.22
wasm-emscripten-finalize.bc	25	4	296670	363328	1.22
wasm-ctor-eval.bc	25	4	298052	365195	1.23
wasm-shell.bc	25	4	299701	367329	1.23
wasm-opt.bc	26	4	310991	381525	1.23
wasm2js.bc	26	4	310483	380472	1.23
asm2wasm.bc	26	4	310153	380159	1.23
llvm-dis.bc	20	6	225957	290632	1.29
llvm-as.bc	44	8	478734	619940	1.29
rippled.bc	427	20	1130242	1444180	1.28
opt.bc	184	8	1640664	2147381	1.31
lld.bc	210	8	1902236	2479378	1.30
clang-9.bc	397	8	3505308	4503068	1.28

The maximum number of iterations required was 20, while check-llvm seems to require 4. This is in-line with what I see in the GPU code I'm working on.
Based on this data, I think that 1000 should be a safe limit that can actually detect infinite loops in finite time.
@lebedev.ri

That being said, it'd be interesting to hand-craft an IR generator that forces instcombine to run arbitrary many iteration before reaching a fixpoint. Do you have an idea for a code pattern that will force such a behavior?

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

125

See my full answer below.

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

125

If we want to be safer, we could set the limit to UINT_MAX in this patch, then make a follow-up that just changes that single constant value.

Based on the data so far, either way seems ok to me.

[kuhar]

Change the default iteration limit to UINT_MAX - 1.

[kuhar]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

125

Sounds good to me. Making the bound tighter can be a follow-up patch.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3579–3580

If i'm reading this right this will not allow passing instcombine-max-iterations bigger than the default
(i.e. it will assert when the default default is reached)

[kuhar]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3579–3580

Yes, that's the intention. Do you suggest an alternative behavior here?

[kuhar]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3685

Forgot to update the constant here. Will fix in the next revision.

[nlopes]

LGTM. The table you provided was very interesting to see, thanks!

[craig.topper]

In my experience extra iterations are often caused by bad worklist management when updating nodes sometimes. For example https://reviews.llvm.org/D50990 was supposed to fix one case of that, but I never got around to finding the original test where I observed the issue. If that patch still applies does it have any effect on any of the extra iterations in the table?

[kuhar]

In D71145#1779870, @craig.topper wrote:

In my experience extra iterations are often caused by bad worklist management when updating nodes sometimes. For example https://reviews.llvm.org/D50990 was supposed to fix one case of that, but I never got around to finding the original test where I observed the issue. If that patch still applies does it have any effect on any of the extra iterations in the table?

Sure, below is a new table generated with your patch applied. I can only see a very small difference.

Name	Bitcode size [MB]	Max Iterations	Total InstCombine Executions	Total Iterations	Average Iterations Per Execution
sqlite3.bc	3	5	12685	17889	1.41
wasm-dis.bc	25	4	295002	361294	1.22
wasm-shell.bc	25	4	299701	367321	1.23
wasm-emscripten-finalize.bc	25	4	296670	363320	1.22
wasm-as.bc	25	4	296061	362590	1.22
wasm-reduce.bc	25	4	298667	365794	1.22
wasm-ctor-eval.bc	25	4	298052	365187	1.23
wasm-metadce.bc	25	4	299757	367109	1.22
wasm-opt.bc	26	4	310991	381517	1.23
wasm2js.bc	26	4	310483	380464	1.23
llvm-dis.bc	20	6	225957	290550	1.29
asm2wasm.bc	26	4	310153	380151	1.23
llvm-as.bc	44	8	478734	619785	1.29
rippled.bc	427	20	1130242	1443942	1.28
opt.bc	184	8	1640664	2146832	1.31
lld.bc	210	8	1902236	2478772	1.3
clang-9.bc	397	8	3505308	4502159	1.28

[kuhar]

@lebedev.ri @spatel @craig.topper
Do you have any other feedback or questions/concerns about the patch?

[lebedev.ri]

In D71145#1787997, @kuhar wrote:

@lebedev.ri @spatel @craig.topper
Do you have any other feedback or questions/concerns about the patch?

I'm not sure what problem this solves, and how successfully, so i can't review this.

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3685

This is marked as 'Done' but UINT_MAX should be changed to InstCombineDefaultMaxIterations?

[kuhar]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3685

Yes. I have it fixed locally like you mentioned.

[spatel]

LGTM

[nikic]

I think it may be worthwhile to separate the limits for "stop after N iterations" and "assert after N iterations". In particular what I have in mind is that we can use -instcombine-max-iterations=2 in tests to ensure that correct worklist management allows everything to be folded in a single iteration (with the second establishing the fixed point). However, for this purpose -instcombine-max-iterations would actually need to assert. Possibly there's room for two separate options?

[kuhar]

In D71145#1788369, @nikic wrote:

I think it may be worthwhile to separate the limits for "stop after N iterations" and "assert after N iterations". In particular what I have in mind is that we can use -instcombine-max-iterations=2 in tests to ensure that correct worklist management allows everything to be folded in a single iteration (with the second establishing the fixed point). However, for this purpose -instcombine-max-iterations would actually need to assert. Possibly there's room for two separate options?

This sounds reasonable, but I think it would be better to consider this, together with making the default max lower, as a separate patch. What do you think?

[nikic]

In D71145#1788379, @kuhar wrote:

In D71145#1788369, @nikic wrote:

I think it may be worthwhile to separate the limits for "stop after N iterations" and "assert after N iterations". In particular what I have in mind is that we can use -instcombine-max-iterations=2 in tests to ensure that correct worklist management allows everything to be folded in a single iteration (with the second establishing the fixed point). However, for this purpose -instcombine-max-iterations would actually need to assert. Possibly there's room for two separate options?

This sounds reasonable, but I think it would be better to consider this, together with making the default max lower, as a separate patch. What do you think?

Yeah, sounds good.

[kuhar]

Replace UINT_MAX with InstCombineDefaultMaxIterations

llvm/include/llvm/Transforms/InstCombine/InstCombine.h

 #include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
 
 namespace llvm {
 
 class InstCombinePass : public PassInfoMixin<InstCombinePass> {
   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);
 };
 
 /// The legacy pass manager's instcombine pass.
 ///
 /// This is a basic whole-function wrapper around the instcombine utility. It
 /// will try to combine all instructions in the function.
 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;
 };
 
 //===----------------------------------------------------------------------===//
 //
 // InstructionCombining - Combine instructions to form fewer, simple
 // instructions. This pass does not modify the CFG, and has a tendency to make
 // instructions dead, so a subsequent DCE pass is useful.
 //
 // This pass combines things like:
 //    %Y = add int 1, %X
 //    %Z = add int 1, %Y
 // into:
 //    %Z = add int 2, %X
 //
 FunctionPass *createInstructionCombiningPass(bool ExpensiveCombines = true);
+FunctionPass *createInstructionCombiningPass(bool ExpensiveCombines,
+                                             unsigned MaxIterations);
 }
 
 #endif

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 STATISTIC(NumDeadInst , "Number of dead inst eliminated");
 STATISTIC(NumSunkInst , "Number of instructions sunk");
 STATISTIC(NumExpand,    "Number of expansions");
 STATISTIC(NumFactor   , "Number of factorizations");
 STATISTIC(NumReassoc  , "Number of reassociations");
 DEBUG_COUNTER(VisitCounter, "instcombine-visit",
               "Controls which instructions are visited");
 
+static constexpr unsigned InstCombineDefaultMaxIterations = UINT_MAX - 1;
+
 static cl::opt<bool>
 EnableCodeSinking("instcombine-code-sinking", cl::desc("Enable code sinking"),
                                               cl::init(true));
 
 static cl::opt<bool>
 EnableExpensiveCombines("expensive-combines",
                         cl::desc("Enable expensive instruction combines"));
 
+static cl::opt<unsigned> LimitMaxIterations(
+    "instcombine-max-iterations",
+    cl::desc("Limit the maximum number of instruction combining iterations"),
+    cl::init(InstCombineDefaultMaxIterations));
+
 static cl::opt<unsigned>
 MaxArraySize("instcombine-maxarray-size", cl::init(1024),
              cl::desc("Maximum array size considered when doing a combine"));
 
 // FIXME: Remove this flag when it is no longer necessary to convert
 // llvm.dbg.declare to avoid inaccurate debug info. Setting this to false
 // increases variable availability at the cost of accuracy. Variables that
 // cannot be promoted by mem2reg or SROA will be described as living in memory
static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL,
 
   return MadeIRChange;
 }
 
 static bool combineInstructionsOverFunction(
     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.
   IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder(
       F.getContext(), TargetFolder(DL),
       IRBuilderCallbackInserter([&Worklist, &AC](Instruction *I) {
         Worklist.Add(I);
         if (match(I, m_Intrinsic<Intrinsic::assume>()))
           AC.registerAssumption(cast<CallInst>(I));
       }));
 
   // Lower dbg.declare intrinsics otherwise their value may be clobbered
   // by instcombiner.
   bool MadeIRChange = false;
   if (ShouldLowerDbgDeclare)
     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");
 
     MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist);
 
     InstCombiner IC(Worklist, Builder, F.hasMinSize(), ExpensiveCombines, AA,
                     AC, TLI, DT, ORE, BFI, PSI, DL, LI);
     IC.MaxArraySizeForCombine = MaxArraySize;
 
     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<AssumptionAnalysis>(F);
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
   auto &ORE = AM.getResult<OptimizationRemarkEmitterAnalysis>(F);
 
   auto *LI = AM.getCachedResult<LoopAnalysis>(F);
 
   auto *AA = &AM.getResult<AAManager>(F);
   const ModuleAnalysisManager &MAM =
       AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
   ProfileSummaryInfo *PSI =
       MAM.getCachedResult<ProfileSummaryAnalysis>(*F.getParent());
   auto *BFI = (PSI && PSI->hasProfileSummary()) ?
       &AM.getResult<BlockFrequencyAnalysis>(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();
 
   // Mark all the analyses that instcombine updates as preserved.
   PreservedAnalyses PA;
   PA.preserveSet<CFGAnalyses>();
   PA.preserve<AAManager>();
   PA.preserve<BasicAA>();
bool InstructionCombiningPass::runOnFunction(Function &F) {
   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
   ProfileSummaryInfo *PSI =
       &getAnalysis<ProfileSummaryInfoWrapperPass>().getPSI();
   BlockFrequencyInfo *BFI =
       (PSI && PSI->hasProfileSummary()) ?
       &getAnalysis<LazyBlockFrequencyInfoPass>().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(InstCombineDefaultMaxIterations) {
+  initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry());
+}
+
+InstructionCombiningPass::InstructionCombiningPass(bool ExpensiveCombines,
+                                                   unsigned MaxIterations)
+    : FunctionPass(ID), ExpensiveCombines(ExpensiveCombines),
+      MaxIterations(MaxIterations) {
   initializeInstructionCombiningPassPass(*PassRegistry::getPassRegistry());
 }
 
 INITIALIZE_PASS_BEGIN(InstructionCombiningPass, "instcombine",
                       "Combine redundant instructions", false, false)
 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)

 void LLVMInitializeInstCombine(LLVMPassRegistryRef R) {
   initializeInstructionCombiningPassPass(*unwrap(R));
 }
 
 FunctionPass *llvm::createInstructionCombiningPass(bool ExpensiveCombines) {
   return new InstructionCombiningPass(ExpensiveCombines);
 }
 
+FunctionPass *llvm::createInstructionCombiningPass(bool ExpensiveCombines,
+                                                   unsigned MaxIterations) {
+  return new InstructionCombiningPass(ExpensiveCombines, MaxIterations);
+}
+
 void LLVMAddInstructionCombiningPass(LLVMPassManagerRef PM) {
   unwrap(PM)->add(createInstructionCombiningPass());
 }

llvm/test/Transforms/InstCombine/limit-max-iterations.ll

+; 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
+}