[InstCombine] Insert instructions before adding them to worklist

[kuhar]

Summary

This patch adds instructions to the InstCombine worklist after they are properly inserted. This way we don't get <badref>s printed when logging added instructions.
It also adds a check in Worklist::Add that ensures that all added instructions have parents.

Simple test case that illustrates the difference when run with --debug-only=instcombine:

define i32 @test35(i32 %a, i32 %b) {
  %1 = or i32 %a, 1135
  %2 = or i32 %1, %b
  ret i32 %2
}

Before this patch:

INSTCOMBINE ITERATION #1 on test35
IC: ADDING: 3 instrs to worklist
IC: Visiting:   %1 = or i32 %a, 1135
IC: Visiting:   %2 = or i32 %1, %b
IC: ADD:   %2 = or i32 %a, %b
IC: Old =   %3 = or i32 %1, %b
    New =   <badref> = or i32 %2, 1135
IC: ADD:   <badref> = or i32 %2, 1135
...

With this patch:

INSTCOMBINE ITERATION #1 on test35
IC: ADDING: 3 instrs to worklist
IC: Visiting:   %1 = or i32 %a, 1135
IC: Visiting:   %2 = or i32 %1, %b
IC: ADD:   %2 = or i32 %a, %b
IC: Old =   %3 = or i32 %1, %b
    New =   <badref> = or i32 %2, 1135
IC: ADD:   %3 = or i32 %2, 1135
...

[davide]

This looks fine, I wonder whether it's worth testing [how easy it's to test, that is]

[spatel]

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

3347

Remove the print of 'New' here?
I think we always produce redundant debug output for the Result instruction, so we still get something like this with <badref>:

IC: Old =   %t2 = insertelement <4 x float> %t1, float 2.000000e+00, i32 2
    New =   <badref> = shufflevector <4 x float> %b, <4 x float> <float undef, float 1.000000e+00, float 2.000000e+00, float undef>, <4 x i32> <i32 0, i32 5, i32 6, i32 3>
IC: ADD:   %t2 = shufflevector <4 x float> %b, <4 x float> <float undef, float 1.000000e+00, float 2.000000e+00, float undef>, <4 x i32> <i32 0, i32 5, i32 6, i32 3>

[kuhar]

This looks fine, I wonder whether it's worth testing [how easy it's to test, that is]

I'd rather not create that rely on debug messages. As an alternative, we could add an assertion in Worklist::Add checking if the added instruction has a parent. What do you think?

[lebedev.ri]

I'm not convinced this is an improvement overall.

As a concrete point: we will no longer print the 'new' if said 'new' isn't a new instruction;
as in, printing of new will now depend on the fact that it will be added into worklist,
which won't be the case if we returned preexisting instruction.

[spatel]

In D71093#1772839, @lebedev.ri wrote:

I'm not convinced this is an improvement overall.

As a concrete point: we will no longer print the 'new' if said 'new' isn't a new instruction;
as in, printing of new will now depend on the fact that it will be added into worklist,
which won't be the case if we returned preexisting instruction.

If we return the existing instruction, don't we always fall down to the else at line 3372 and print it there?

[lebedev.ri]

In D71093#1773021, @spatel wrote:

In D71093#1772839, @lebedev.ri wrote:

I'm not convinced this is an improvement overall.

As a concrete point: we will no longer print the 'new' if said 'new' isn't a new instruction;
as in, printing of new will now depend on the fact that it will be added into worklist,
which won't be the case if we returned preexisting instruction.

If we return the existing instruction, don't we always fall down to the else at line 3372 and print it there?

No, because we only get there if we return *the same* instruction we just visited.
I'm talking about the case like:

%x = mul i8 %y, 42
%t0 = sub i8 0, %x
%t1 = sub i8 0, %t0

visit %t1
... returned %x
%x != %t1

[spatel]

In D71093#1773043, @lebedev.ri wrote:

In D71093#1773021, @spatel wrote:

In D71093#1772839, @lebedev.ri wrote:

I'm not convinced this is an improvement overall.

As a concrete point: we will no longer print the 'new' if said 'new' isn't a new instruction;
as in, printing of new will now depend on the fact that it will be added into worklist,
which won't be the case if we returned preexisting instruction.

If we return the existing instruction, don't we always fall down to the else at line 3372 and print it there?

No, because we only get there if we return *the same* instruction we just visited.
I'm talking about the case like:

%x = mul i8 %y, 42
%t0 = sub i8 0, %x
%t1 = sub i8 0, %t0

visit %t1
... returned %x
%x != %t1

Ah, disregard my suggestion then. Sorry for the noise. I don't have strong feelings about the debug spew, so feel free to proceed with whatever the consensus leads to.

[kuhar]

I added an assertion checking if the instructions added have a parent (block).
Also restored the previous debug message.

For the context, I find this invariant useful for 2 reasons:

• as mentioned, we don't print badrefs
• I'm experimenting with new InstCombine iteration strategies geared towards GPU code and more local rewrites. To know control visitation better, I need to know which basic blocks to re-visit.

[kuhar]

Ping.

Do you have any other feedback? @spatel @lebedev.ri

[spatel]

In D71093#1783629, @kuhar wrote:

Ping.

Do you have any other feedback? @spatel @lebedev.ri

LGTM, but better see if @lebedev.ri concurs.
Do you have a small IR example with before/after output that we can put here in the review? That way there's at least a record of what the improvement looks like.

[kuhar]

In D71093#1783729, @spatel wrote:

Do you have a small IR example with before/after output that we can put here in the review? That way there's at least a record of what the improvement looks like.

Sure, I added one to the description.

[lebedev.ri]

I'm sorry, i'm not following the patch's logic anymore.
First it was about relying on Add() printing ADD: line, and now
all the printing stuff seems to be gone and the patch is adding some
invariants on when the instruction should be inserted into worklist?

Does the current diff still achieve the same initial goal of not printing badref?
How? If not, the description is not longer applicable, and post a new patch instead?

Apologies if i'm horribly misreading the patch?

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

95–96 ↗

(On Diff #232605)

The described behavior sounds like a bug to me.
More importantly, it's not related to the printing changes?

[kuhar]

In D71093#1783809, @lebedev.ri wrote:

I'm sorry, i'm not following the patch's logic anymore.
First it was about relying on Add() printing ADD: line, and now
all the printing stuff seems to be gone and the patch is adding some
invariants on when the instruction should be inserted into worklist?

Since the beginning, the patch was about ensuring that the instructions added to the worklist are properly inserted. One manifestation of instructions not being correctly inserted that was easy to observe was debug ADD lines with <badrefs> being printed.
One confusing thing that happened was that I followed a suggestion of reducing the amount of debug output printed and removing the line containing NEW that directly preceded ADD. But this change is no more and the amount of the debug output is the same.

Does the current diff still achieve the same initial goal of not printing badref?

Yes.

How? If not, the description is not longer applicable, and post a new patch instead?

By ensuring that instructions are inserted. I moved adding instructions later in one place in InstCombine that solves the issue.
In addition, the patch asserts that all inserted instructions have a parent (block). This is stronger than making debug logs pretty, but serves the same goal of ensuring instructions are properly inserted.

Apologies if i'm horribly misreading the patch?

I think having many iterations made is a bit messy. I also may have simplified the original description of the patch, and though that explaining the change in terms of printing will make it simpler to understand. I apologize and will try to make future patches like this be described more directly.

[kuhar]

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

95–96 ↗

(On Diff #232605)

The users that I refer to here are new instructions that are being constructed; InstCombine inserts them in subsequent calls to Add(). This happens in a few places and it's not obvious to me make it more straight-forward.
With the changes to the worklist here, everything works like before and the order of iteration is exactly the same.

Let me know if you want me to dig up some concrete examples for this behavior here.

[lebedev.ri]

In D71093#1783911, @kuhar wrote:

In D71093#1783809, @lebedev.ri wrote:

...

Okay.
Thank you for detailed responses.

I'm mainly confused because, as per the patch's description:

IC: Old = %3 = or i32 %1, %b

New =   <badref> = or i32 %2, 1135

But i think now the patch as it is now is okay,
if @spatel accepted i will not block this any further.

[nikic]

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

95–96 ↗

(On Diff #232605)

I'd appreciate an example for this. I can see how it can happen in principle, but not really why we'd write the code that way in practice.

[kuhar]

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

95–96 ↗

(On Diff #232605)

Consider the test llvm/test/Transforms/InstCombine/zext-or-icmp.ll, function zext_or_icmp_icmp:

define i8 @zext_or_icmp_icmp(i8 %a, i8 %b) {
  %mask = and i8 %a, 1
  %toBool1 = icmp eq i8 %mask, 0
  %toBool2 = icmp eq i8 %b, 0
  %bothCond = or i1 %toBool1, %toBool2
  %zext = zext i1 %bothCond to i8
  ret i8 %zext
}

Instcombine starts like this:

INSTCOMBINE ITERATION #1 on zext_or_icmp_icmp
IC: ADDING: 6 instrs to worklist
IC: Visiting:   %mask = and i8 %a, 1
IC: Visiting:   %toBool1 = icmp eq i8 %mask, 0
IC: Visiting:   %toBool2 = icmp eq i8 %b, 0
IC: Visiting:   %bothCond = or i1 %toBool1, %toBool2
IC: Visiting:   %zext = zext i1 %bothCond to i8
IC: ADD:   %toBool11 = zext i1 %toBool1 to i8
IC: ADD:   %toBool22 = zext i1 %toBool2 to i8
IC: ADD:   %1 = xor i8 %mask, 1

Instcombine wants to replace all uses of %toBool11 = zext i1 %toBool1 to i8 with %1 = xor i8 %mask, 1. One of the uses is <badref> = or i8 %toBool11, %toBool22:

IC: Replacing   %toBool11 = zext i1 %toBool1 to i8
    with   %1 = xor i8 %mask, 1
IC: Old =   %zext = zext i1 %bothCond to i8
    New =   <badref> = or i8 %1, %toBool22
IC: ADD:   %zext = or i8 %1, %toBool22

The way I understand the issue is that one of the uses is the instructions that currently being simplified. This instruction will be added to the worklist anyway once the simplification is finished.

[nikic]

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

95–96 ↗

(On Diff #232605)

Thanks for the example. This transform seems to be a pretty special case that manually runs other InstCombine transforms to prevent an infinite loop.

Assuming that this is the only case (at least I didn't get anything else running InstCombine tests), possibly we might just want to adjust the transform to insert the instruction earlier? Something along these lines:

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
index 5112fb1a6c3..70a7b9bfbba 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineCasts.cpp
@@ -1189,7 +1189,8 @@ Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
       // zext (or icmp, icmp) -> or (zext icmp), (zext icmp)
       Value *LCast = Builder.CreateZExt(LHS, CI.getType(), LHS->getName());
       Value *RCast = Builder.CreateZExt(RHS, CI.getType(), RHS->getName());
-      BinaryOperator *Or = BinaryOperator::Create(Instruction::Or, LCast, RCast);
+      Value *Or = Builder.CreateOr(LCast, RCast);
+      Builder.SetInsertPoint(cast<Instruction>(Or));
 
       // Perform the elimination.
       if (auto *LZExt = dyn_cast<ZExtInst>(LCast))
@@ -1197,7 +1198,7 @@ Instruction *InstCombiner::visitZExt(ZExtInst &CI) {
       if (auto *RZExt = dyn_cast<ZExtInst>(RCast))
         transformZExtICmp(RHS, *RZExt);
 
-      return Or;
+      return replaceInstUsesWith(CI, Or);
     }
   }

I feel like doing this might be better than carving out an exception in the worklist management itself.

[kuhar]

Fix instruction insertion in InstCombineCasts for zext-or-icmp.

[kuhar]

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

95–96 ↗

(On Diff #232605)

You approach seems to like a better way than silently skipping some uses.

I ran the in-source test suite and compiled a few large projects with -O3 to make sure it works.

[kuhar]

This comment was removed by kuhar.

[nikic]

LGTM

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

     // Now that we have an instruction, try combining it to simplify it.
     Builder.SetInsertPoint(I);
     Builder.SetCurrentDebugLocation(I->getDebugLoc());
 
 #ifndef NDEBUG
     std::string OrigI;
 #endif
     LLVM_DEBUG(raw_string_ostream SS(OrigI); I->print(SS); OrigI = SS.str(););
     LLVM_DEBUG(dbgs() << "IC: Visiting: " << OrigI << '\n');
 
     if (Instruction *Result = visit(*I)) {
       ++NumCombined;
       // Should we replace the old instruction with a new one?
       if (Result != I) {
         LLVM_DEBUG(dbgs() << "IC: Old = " << *I << '\n'
                           << "    New = " << *Result << '\n');
 

 
   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>();

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