Introduce DebugCounter into ConstProp pass

[zhizhouy]

Summary

This patch introduces DebugCounter into ConstProp pass at per-transformation level.

It will provide an option to skip first n or stop after n transformations for the whole ConstProp pass.

This will make debug easier for the pass, also providing chance to do transformation level bisecting.

[george.burgess.iv]

lib/Transforms/Scalar/ConstantProp.cpp

82 ↗

(On Diff #158349)

Looks like we make no attempt to traverse this function in a stable order (we're relying on the iteration order of a std::set<Instruction *>, and pointers don't have a guaranteed relative order from execution to execution), so I don't think this'll do what we want?

[zhizhouy]

Use a vector to ensure worklist iterated in stable order.

[george.burgess.iv]

lib/Transforms/Scalar/ConstantProp.cpp

73 ↗

(On Diff #158440)

Can we also change this to a SmallPtrSet, please?

74 ↗

(On Diff #158440)

Please also add "We use two containers rather than a SetVector, since remove is linear-time, and we don't care enough to remove from Vec"

77 ↗

(On Diff #158440)

This should always be true.

87 ↗

(On Diff #158440)

nit: Probably redundant comment, given the comment above

88 ↗

(On Diff #158440)

We can't do a range for loop here: they expand to (roughly; I'm too lazy to bring up the standard, and the differences don't matter here :) )

for (auto Begin = WorkListVec.begin(), End = WorkListVec.end(); Begin != End; ++Begin) {
  Instruction *I = *Begin;
  {
    // Loop body
  }
}

This is problematic, since WorkListVec.push_back() invalidates iterators, but we're still using the now-invalid iterators.

Please either make this use indices, or a while (!vec.empty()) { auto *i = vec.pop_back_val(); }-like thing

100 ↗

(On Diff #158440)

nit: I think it's preferred to use !set.count(x) instead of set.find(x) == set.end()

We could probably simplify this whole thing to set.insert(cast<Instruction>(U)).second, though (if insertion failed, it already existed)

[zhizhouy]

Comments fixed.

[george.burgess.iv]

lib/Transforms/Scalar/ConstantProp.cpp

88 ↗

(On Diff #158440)

I think there was a misunderstanding here. Please use an index instead of an iterator. The loop should look like

for (unsigned I = 0; I < WorkListVec.size(); ++I) {
  ...
}

[zhizhouy]

Sorry for misunderstanding, comments fixed.

[zhizhouy]

ping for reviewing... thanks!

[fhahn]

IIUC by always adding to the end of WorkListVec, we could end up using substantial more memory, depending on the input program. In practice it shouldn't be too bad, as I think an upper bound for the times an instruction is added to WorkListVec is the number of operands (it will only get added if one of its operands gets constant folded, and once an operand is constant folded, it won't get folded again). And usually most instructions have a small number of operands.

However, I think we might be able to construct programs where WorkListVec uses O(n*n) memory (where n is the number of instructions): say we have n/2 instructions where Inst_x can be constant folded after Inst_(x-1) got constant folded. The other n/2 instructions are PHI nodes with with all other n/2 instructions as incoming values. Now we process them in the most suboptimal order: first all the phi nodes, then Inst_(n/2).... Inst_0. We manage to constant fold Inst_0 and add n/2 phi nodes and Inst_1 to WorkListVec. We again process all phi nodes, constant fold Inst_1 and add all phi nodes and Inst_2. We continue doing until all n/2 non-phi instructions are constant folded and each time we add n/2 nodes to WorkListVec.

Not sure if it is worth it (as this is a legacy pass and not used any more AFAIK), but I think we could use 2 worklists to keep the memory usage linear, with keeping the same iteration order:

while (!WorkList.empty()) {
   SmallVector<Instruction*, 16> NewWorkListVec;
   for (auto *I : WorkListVec) {
     ......
         NewWorkListVec.push_back(U);
     .....
   }
   WorkListVec = std::move(NewWorkListVec);
}

lib/Transforms/Scalar/ConstantProp.cpp

109 ↗

(On Diff #158623)

already erase at line 90?

[zhizhouy]

Using another vector to deal with newly added instructions. Thanks!

[fhahn]

LGTM thanks! It would be great if you could also add a simple test case.

[fhahn]

Do you need someone to commit this?

[zhizhouy]

Thanks for the heads up. Sorry for the delay, I will commit it soon.

llvm/trunk/lib/Transforms/Scalar/ConstantProp.cpp

 //   * Converts instructions like "add int 1, 2" into 3
 //
 // Notice that:
 //   * This pass has a habit of making definitions be dead.  It is a good idea
 //     to run a DIE pass sometime after running this pass.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/ADT/SmallPtrSet.h"
+#include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstantFolding.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
-#include "llvm/Transforms/Utils/Local.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/Pass.h"
+#include "llvm/Support/DebugCounter.h"
 #include "llvm/Transforms/Scalar.h"
-#include <set>
+#include "llvm/Transforms/Utils/Local.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "constprop"
 
 STATISTIC(NumInstKilled, "Number of instructions killed");
+DEBUG_COUNTER(CPCounter, "constprop-transform",
+              "Controls which instructions are killed");
 
 namespace {
   struct ConstantPropagation : public FunctionPass {
     static char ID; // Pass identification, replacement for typeid
     ConstantPropagation() : FunctionPass(ID) {
       initializeConstantPropagationPass(*PassRegistry::getPassRegistry());
     }
 
FunctionPass *llvm::createConstantPropagationPass() {
   return new ConstantPropagation();
 }
 
 bool ConstantPropagation::runOnFunction(Function &F) {
   if (skipFunction(F))
     return false;
 
   // Initialize the worklist to all of the instructions ready to process...
-  std::set<Instruction*> WorkList;
-  for (Instruction &I: instructions(&F))
+  SmallPtrSet<Instruction *, 16> WorkList;
+  // The SmallVector of WorkList ensures that we do iteration at stable order.
+  // We use two containers rather than one SetVector, since remove is
+  // linear-time, and we don't care enough to remove from Vec.
+  SmallVector<Instruction *, 16> WorkListVec;
+  for (Instruction &I : instructions(&F)) {
     WorkList.insert(&I);
+    WorkListVec.push_back(&I);
+  }
 
   bool Changed = false;
   const DataLayout &DL = F.getParent()->getDataLayout();
   TargetLibraryInfo *TLI =
       &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
 
   while (!WorkList.empty()) {
-    Instruction *I = *WorkList.begin();
-    WorkList.erase(WorkList.begin());    // Get an element from the worklist...
+    SmallVector<Instruction*, 16> NewWorkListVec;
+    for (auto *I : WorkListVec) {
+      WorkList.erase(I); // Remove element from the worklist...
 
-    if (!I->use_empty())                 // Don't muck with dead instructions...
+      if (!I->use_empty()) // Don't muck with dead instructions...
         if (Constant *C = ConstantFoldInstruction(I, DL, TLI)) {
+          if (!DebugCounter::shouldExecute(CPCounter))
+            continue;
+
           // Add all of the users of this instruction to the worklist, they might
           // be constant propagatable now...
-        for (User *U : I->users())
-          WorkList.insert(cast<Instruction>(U));
+          for (User *U : I->users()) {
+            // If user not in the set, then add it to the vector.
+            if (WorkList.insert(cast<Instruction>(U)).second)
+              NewWorkListVec.push_back(cast<Instruction>(U));
+          }
 
           // Replace all of the uses of a variable with uses of the constant.
           I->replaceAllUsesWith(C);
 
-        // Remove the dead instruction.
-        WorkList.erase(I);
           if (isInstructionTriviallyDead(I, TLI)) {
             I->eraseFromParent();
             ++NumInstKilled;
           }
 
           // We made a change to the function...
           Changed = true;
         }
     }
+    WorkListVec = std::move(NewWorkListVec);
+  }
   return Changed;
 }