[InstCombine] Fix change flag handling to report all IR changes up to the pass manager or preseved analyses

[craig.topper]

Summary

Currently InstCombine does not report dead code elimination or constant folding during the worklist building up to the pass manager or preserved analysis reporting. With one caveat, constant folding operands does report as a change and forces another iteration of the InstCombine pass. Since the return flag is currently based on iteration count being greater than 1, those modifications would be reported.

This patch adds a change flag to DCE and constant folding in the worklist build. Additionally we no longer treat changes during worklist building as a reason to run another iteration. Now the return value is based on a change flag instead of the iteration count.

[davide]

I assume this is a follow-up from our mailing list discussion. Not sure how feasible it is, but it would be great if you can leverage DebugCounters to maybe write a test. I'll appreciate if you can take a look. Thanks.

[craig.topper]

I can certainly try. What exactly were you envisioning?

[chandlerc]

In D31678#722169, @craig.topper wrote:

I can certainly try. What exactly were you envisioning?

Alternatively or perhaps additionally, can you contrive a test case where we failed to invalidate an analysis but mutated the IR prior to this change? That seems like a good edge case test for the thing that would actually go wrong.

[craig.topper]

@chandlerc do you know of other tests that check this sort of thing or can you give more guidance. I haven't spent a lot of time in the IR optimizers until recently.

[chandlerc]

In D31678#723024, @craig.topper wrote:

@chandlerc do you know of other tests that check this sort of thing or can you give more guidance. I haven't spent a lot of time in the IR optimizers until recently.

The closest is probably test/Transforms/Inline/cgscc-invalidate.ll. It's doing essentially the same thing but for the inliner. Unfortunately, it is much more complicated in some ways due to testing an interprocedural pass. The key is typically:

1. compute some analysis
2. run optimization pass that does mutation
3. run verifier for analysis

If #3 gets a stale analysis it should fail. This means you need a verifier that will detect the old analysis as invalid after the mutation in #2. Then you want to write FileCheck patterns to verify that #2 actually *does* mutate the IR in the interesting way.

[craig.topper]

@chandlerc What analysis has a verifier that is sensitive to which instructions exist? If we delete any BasicBlocks I believe those do get reported up.

[craig.topper]

Err, we never delete basic blocks, we just remove all instructions from them if its unreachable.

lib/Transforms/InstCombine/InstructionCombining.cpp

do {
     for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ) {
       Instruction *Inst = &*BBI++;
 
       // DCE instruction if trivially dead.
       if (isInstructionTriviallyDead(Inst, TLI)) {
         ++NumDeadInst;
         DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n');
         Inst->eraseFromParent();
+        MadeIRChange = true;
         continue;
       }
 
       // ConstantProp instruction if trivially constant.
       if (!Inst->use_empty() &&
           (Inst->getNumOperands() == 0 || isa<Constant>(Inst->getOperand(0))))
         if (Constant *C = ConstantFoldInstruction(Inst, DL, TLI)) {
           DEBUG(dbgs() << "IC: ConstFold to: " << *C << " from: "
                        << *Inst << '\n');
           Inst->replaceAllUsesWith(C);
           ++NumConstProp;
           if (isInstructionTriviallyDead(Inst, TLI))
             Inst->eraseFromParent();
+          MadeIRChange = true;
           continue;
         }
 
       // See if we can constant fold its operands.
       for (Use &U : Inst->operands()) {
         if (!isa<ConstantVector>(U) && !isa<ConstantExpr>(U))
           continue;
 
IRBuilder<TargetFolder, IRBuilderCallbackInserter> Builder(
 
         using namespace llvm::PatternMatch;
         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 DbgDeclaresChanged = LowerDbgDeclare(F);
+  bool MadeIRChange = LowerDbgDeclare(F);
 
   // Iterate while there is work to do.
   int Iteration = 0;
   for (;;) {
     ++Iteration;
     DEBUG(dbgs() << "\n\nINSTCOMBINE ITERATION #" << Iteration << " on "
                  << F.getName() << "\n");
 
-    bool Changed = prepareICWorklistFromFunction(F, DL, &TLI, Worklist);
+    MadeIRChange |= prepareICWorklistFromFunction(F, DL, &TLI, Worklist);
 
     InstCombiner IC(Worklist, &Builder, F.optForMinSize(), ExpensiveCombines,
                     AA, AC, TLI, DT, DL, LI);
     IC.MaxArraySizeForCombine = MaxArraySize;
-    Changed |= IC.run();
 
-    if (!Changed)
+    if (!IC.run())
       break;
+
+    MadeIRChange = true;
   }
 
-  return DbgDeclaresChanged || Iteration > 1;
+  return MadeIRChange;
 }
 
 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);