[InstCombine] Improve infinite loop detection

[kuhar]

Summary

This patch limits the default number of iterations performed by InstCombine. It also exposes a new option that allows to specify how many iterations is considered getting stuck in an infinite loop.

Based on experiments performed on real-world C++ programs, InstCombine seems to perform at most ~8-20 iterations, so treating 1000 iterations as an infinite loop seems like a safe choice. See D71145 for details.

The two limits can be specified via command line options.

[spatel]

LGTM

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

125–126

I'm guessing that the general understanding that ideally these should become 2 in the end.
Now, that might never happen, but that should be the trend.
So far no one seems to have come up with any cases where 1000 limit is reached.
Can we periodically ~halve them, starting now?

[mdchen]

@kuhar @lebedev.ri I'm lucky to have a test case which requires exactly 1001 times iteration thus aborts. And would it be better just break out rather than report a fatal error?

Test case(only stucks in our customized pipeline, paste it here in case it helps):

int a, g;
union b {
  long c;
} f;
long d, h;
short *e;
static short j();
void k() {
  union b i;
  j(0, i);
}
short j(int l, union b m) {
  d = 0;
  for (; d <= 24; d = d + 2)
    if (m.c) {
      h = 0;
      for (; h < 59; h++) {
        *e = l > g ^ f.c;
        g = a < 0 ?: a;
      }
    }
}
int main() {}

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 constexpr unsigned InstCombineDefaultMaxIterations = 1000;
+static constexpr unsigned InstCombineDefaultInfiniteLoopThreshold = 1000;
 
 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> InfiniteLoopDetectionThreshold(
+    "instcombine-infinite-loop-threshold",
+    cl::desc("Number of instruction combining iterations considered an "
+             "infinite loop"),
+    cl::init(InstCombineDefaultInfiniteLoopThreshold), cl::Hidden);
+
 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 combineInstructionsOverFunction(
   bool MadeIRChange = false;
   if (ShouldLowerDbgDeclare)
     MadeIRChange = LowerDbgDeclare(F);
 
   // Iterate while there is work to do.
   unsigned Iteration = 0;
   while (true) {
     ++Iteration;
+
+    if (Iteration > InfiniteLoopDetectionThreshold) {
+      report_fatal_error(
+          "Instruction Combining seems stuck in an infinite loop after " +
+          Twine(InfiniteLoopDetectionThreshold) + " iterations.");
+    }
+
     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);
 

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
+; RUN: not opt < %s -instcombine -S --instcombine-infinite-loop-threshold=3 2>&1 | FileCheck %s --check-prefix=LOOP
 
 ; 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

 ; 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]]
 
+; LOOP: LLVM ERROR: Instruction Combining seems stuck in an infinite loop after 3 iterations.
+
   %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
 }