[InstCombine] Move InstCombineWorklist to Utils to allow reuse (NFC).

[fhahn]

Summary

InstCombine's worklist can be re-used by other passes like
VectorCombine. Move it to llvm/Transform/Utils and rename it to
InstructionWorklist.

[fhahn]

In D110171#3012460, @lebedev.ri wrote:

Nice!
I'm not sure it is a good idea to just reuse part of another pass like that.
Perhaps InstCombineWorklist should be extracted+promoted to being more reusable?

Yeah, it should probably be moved. I put up D110181 to move it to Utils and rename it to InstructionWorklist.

[fhahn]

In D110181#3012805, @fhahn wrote:

In D110171#3012460, @lebedev.ri wrote:

Nice!
I'm not sure it is a good idea to just reuse part of another pass like that.
Perhaps InstCombineWorklist should be extracted+promoted to being more reusable?

Yeah, it should probably be moved. I put up D110181 to move it to Utils and rename it to InstructionWorklist.

The comment ended up on the wrong review, should be at D110171

[lebedev.ri]

Now this i like!
LGTM, but please wait for @spatel.

[lebedev.ri]

i think you want to apply some more s/instcombine/instructionworklist/ to the diff

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

16–17

These need updating

llvm/include/llvm/Transforms/Utils/InstructionWorklist.h

21

Update

[fhahn]

Fix include guard, remove DEBUG_TYPE from header, move it to before the individual includes.

[fhahn]

llvm/include/llvm/Transforms/Utils/InstructionWorklist.h

21

I removed it here and moved the user includes after the DEBUG_TYPE definitions at the include site. Not sure if there's a better way to customize the DEBUG_TYPE string here.

[spatel]

Thanks! We should have done this long ago. :)
See inline for a couple of minor points, but LGTM too.

llvm/include/llvm/Transforms/Utils/InstructionWorklist.h

21

Do we really need for the caller's DEBUG_TYPE to be set, or can we just define that here as "instruction-utils" or something like that? That's what it looks like in BasicBlockUtils.cpp (so might have to split this into a header and source file pair?).

35

Is it necessary to have that prefix? That part is just noise to me when I'm scrolling through instcombine debug spew. No tests should be depending on matching that...

[fhahn]

Remove DbgPrefix.

[fhahn]

llvm/include/llvm/Transforms/Utils/InstructionWorklist.h

21

I think we could just use a different DEBUG_TYPE here, but then we would miss update messages from the worklist with -debug-only=instcombine. Not sure if that's preferable?

35

I removed the prefix part for now.

[lebedev.ri]

llvm/include/llvm/Transforms/Utils/InstructionWorklist.h

21

I think the current patch as-is is fine.

[fhahn]

Hmm, it looks like this broke the build with explicit modules ( -DLLVM_ENABLE_MODULES=On). I'm currently checking to see what the options are for unbreaking the build.

[fhahn]

In D110181#3014750, @fhahn wrote:

Hmm, it looks like this broke the build with explicit modules ( -DLLVM_ENABLE_MODULES=On). I'm currently checking to see what the options are for unbreaking the build.

@teemperor fixed the issue in a5e1c746b870d79142419a07a8aecc471eacfed1, thanks!

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

 //===- InstCombine.h - InstCombine pass -------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 /// \file
 ///
 /// This file provides the primary interface to the instcombine pass. This pass
 /// is suitable for use in the new pass manager. For a pass that works with the
 /// legacy pass manager, use \c createInstructionCombiningPass().
 ///
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINE_H
 #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINE_H
 
 #include "llvm/IR/Function.h"
 #include "llvm/IR/PassManager.h"
-#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
+#include "llvm/Transforms/Utils/InstructionWorklist.h"
 
 namespace llvm {
 
 class InstCombinePass : public PassInfoMixin<InstCombinePass> {
-  InstCombineWorklist Worklist;
+  InstructionWorklist Worklist;
   const unsigned MaxIterations;
 
 public:
   explicit InstCombinePass();
   explicit InstCombinePass(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;
+  InstructionWorklist Worklist;
   const unsigned MaxIterations;
 
 public:
   static char ID; // Pass identification, replacement for typeid
 
   explicit InstructionCombiningPass();
   explicit InstructionCombiningPass(unsigned MaxIterations);
 

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

 
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetFolder.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
-#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
+#include "llvm/Transforms/Utils/InstructionWorklist.h"
 #include <cassert>
 
 #define DEBUG_TYPE "instcombine"
 
 namespace llvm {
 
 class AAResults;
 class AssumptionCache;
public:
 
   /// An IRBuilder that automatically inserts new instructions into the
   /// worklist.
   using BuilderTy = IRBuilder<TargetFolder, IRBuilderCallbackInserter>;
   BuilderTy &Builder;
 
 protected:
   /// A worklist of the instructions that need to be simplified.
-  InstCombineWorklist &Worklist;
+  InstructionWorklist &Worklist;
 
   // Mode in which we are running the combiner.
   const bool MinimizeSize;
 
   AAResults *AA;
 
   // Required analyses.
   AssumptionCache &AC;
   TargetLibraryInfo &TLI;
   DominatorTree &DT;
   const DataLayout &DL;
   const SimplifyQuery SQ;
   OptimizationRemarkEmitter &ORE;
   BlockFrequencyInfo *BFI;
   ProfileSummaryInfo *PSI;
 
   // Optional analyses. When non-null, these can both be used to do better
   // combining and will be updated to reflect any changes.
   LoopInfo *LI;
 
   bool MadeIRChange = false;
 
 public:
-  InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder,
+  InstCombiner(InstructionWorklist &Worklist, BuilderTy &Builder,
                bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
                TargetLibraryInfo &TLI, TargetTransformInfo &TTI,
                DominatorTree &DT, OptimizationRemarkEmitter &ORE,
                BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
                const DataLayout &DL, LoopInfo *LI)
       : TTI(TTI), Builder(Builder), Worklist(Worklist),
         MinimizeSize(MinimizeSize), AA(AA), AC(AC), TLI(TLI), DT(DT), DL(DL),
         SQ(DL, &TLI, &DT, &AC), ORE(ORE), BFI(BFI), PSI(PSI), LI(LI) {}

llvm/include/llvm/Transforms/Utils/InstructionWorklist.h

-//===- InstCombineWorklist.h - Worklist for InstCombine pass ----*- C++ -*-===//
+//=== InstructionWorklist.h - Worklist for InstCombine & others -*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H
 #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "instcombine"
 
 namespace llvm {
 
-/// InstCombineWorklist - This is the worklist management logic for
-/// InstCombine.
-class InstCombineWorklist {
+/// InstructionWorklist - This is the worklist management logic for
+/// InstCombine and other simplification passes.
+class InstructionWorklist {
   SmallVector<Instruction *, 256> Worklist;
   DenseMap<Instruction *, unsigned> WorklistMap;
   /// These instructions will be added in reverse order after the current
   /// combine has finished. This means that these instructions will be visited
   /// in the order they have been added.
   SmallSetVector<Instruction *, 16> Deferred;
 
+  const char *DbgPrefix = "IC";
+
 public:
-  InstCombineWorklist() = default;
+  InstructionWorklist() = default;
 
-  InstCombineWorklist(InstCombineWorklist &&) = default;
-  InstCombineWorklist &operator=(InstCombineWorklist &&) = default;
+  InstructionWorklist(InstructionWorklist &&) = default;
+  InstructionWorklist &operator=(InstructionWorklist &&) = default;
 
   bool isEmpty() const { return Worklist.empty() && Deferred.empty(); }
 
   /// Add instruction to the worklist.
   /// Instructions will be visited in the order they are added.
   /// You likely want to use this method.
   void add(Instruction *I) {
     if (Deferred.insert(I))
-      LLVM_DEBUG(dbgs() << "IC: ADD DEFERRED: " << *I << '\n');
+      LLVM_DEBUG(dbgs() << DbgPrefix << ": ADD DEFERRED: " << *I << '\n');
   }
 
   /// Add value to the worklist if it is an instruction.
   /// Instructions will be visited in the order they are added.
   void addValue(Value *V) {
     if (Instruction *I = dyn_cast<Instruction>(V))
       add(I);
   }
 
   /// Push the instruction onto the worklist stack.
   /// Instructions that have been added first will be visited last.
   void push(Instruction *I) {
     assert(I);
     assert(I->getParent() && "Instruction not inserted yet?");
 
     if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
-      LLVM_DEBUG(dbgs() << "IC: ADD: " << *I << '\n');
+      LLVM_DEBUG(dbgs() << ": ADD: " << *I << '\n');
       Worklist.push_back(I);
     }
   }
 
   void pushValue(Value *V) {
     if (Instruction *I = dyn_cast<Instruction>(V))
       push(I);
   }
 
   Instruction *popDeferred() {
     if (Deferred.empty())
       return nullptr;
     return Deferred.pop_back_val();
   }
 
   void reserve(size_t Size) {
     Worklist.reserve(Size + 16);
     WorklistMap.reserve(Size);
   }
 
   /// Remove I from the worklist if it exists.
   void remove(Instruction *I) {
-    DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(I);
+    DenseMap<Instruction *, unsigned>::iterator It = WorklistMap.find(I);
     if (It != WorklistMap.end()) {
       // Don't bother moving everything down, just null out the slot.
       Worklist[It->second] = nullptr;
       WorklistMap.erase(It);
     }
 
     Deferred.remove(I);
   }
 
   Instruction *removeOne() {
     if (Worklist.empty())
       return nullptr;
     Instruction *I = Worklist.pop_back_val();
     WorklistMap.erase(I);
     return I;
   }
 
   /// When an instruction is simplified, add all users of the instruction
   /// to the work lists because they might get more simplified now.
   void pushUsersToWorkList(Instruction &I) {
     for (User *U : I.users())
       push(cast<Instruction>(U));
   }
 
-
   /// Check that the worklist is empty and nuke the backing store for the map.
   void zap() {
     assert(WorklistMap.empty() && "Worklist empty, but map not?");
     assert(Deferred.empty() && "Deferred instructions left over");
 
     // Do an explicit clear, this shrinks the map if needed.
     WorklistMap.clear();
   }
 };
 
 } // end namespace llvm.
 
 #undef DEBUG_TYPE
 
 #endif

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

 #include "llvm/Support/Casting.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Support/raw_ostream.h"
-#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
 #include "llvm/Transforms/InstCombine/InstCombiner.h"
 #include "llvm/Transforms/Utils/AssumeBundleBuilder.h"
+#include "llvm/Transforms/Utils/InstructionWorklist.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include "llvm/Transforms/Utils/SimplifyLibCalls.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <cstring>
 #include <utility>
 #include <vector>

llvm/lib/Transforms/InstCombine/InstCombineInternal.h

 #include "llvm/Analysis/TargetFolder.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/InstVisitor.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/KnownBits.h"
-#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
 #include "llvm/Transforms/InstCombine/InstCombiner.h"
+#include "llvm/Transforms/Utils/InstructionWorklist.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <cassert>
 
 #define DEBUG_TYPE "instcombine"
 
 using namespace llvm::PatternMatch;
 
 // As a default, let's assume that we want to be aggressive,

 class ProfileSummaryInfo;
 class TargetLibraryInfo;
 class User;
 
 class LLVM_LIBRARY_VISIBILITY InstCombinerImpl final
     : public InstCombiner,
       public InstVisitor<InstCombinerImpl, Instruction *> {
 public:
-  InstCombinerImpl(InstCombineWorklist &Worklist, BuilderTy &Builder,
+  InstCombinerImpl(InstructionWorklist &Worklist, BuilderTy &Builder,
                    bool MinimizeSize, AAResults *AA, AssumptionCache &AC,
                    TargetLibraryInfo &TLI, TargetTransformInfo &TTI,
                    DominatorTree &DT, OptimizationRemarkEmitter &ORE,
                    BlockFrequencyInfo *BFI, ProfileSummaryInfo *PSI,
                    const DataLayout &DL, LoopInfo *LI)
       : InstCombiner(Worklist, Builder, MinimizeSize, AA, AC, TLI, TTI, DT, ORE,
                      BFI, PSI, DL, LI) {}
 

llvm/lib/Transforms/InstCombine/InstCombineMulDivRem.cpp

 #include "llvm/IR/Intrinsics.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
-#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
 #include "llvm/Transforms/InstCombine/InstCombiner.h"
 #include "llvm/Transforms/Utils/BuildLibCalls.h"
+#include "llvm/Transforms/Utils/InstructionWorklist.h"
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <utility>
 
 using namespace llvm;
 using namespace PatternMatch;
 

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
-#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
 #include "llvm/Transforms/InstCombine/InstCombiner.h"
+#include "llvm/Transforms/Utils/InstructionWorklist.h"
 #include <cassert>
 #include <utility>
 
 using namespace llvm;
 using namespace PatternMatch;
 
 #define DEBUG_TYPE "instcombine"
 

llvm/lib/Transforms/InstCombine/InstCombineVectorOps.cpp

 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/Operator.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/IR/Type.h"
 #include "llvm/IR/User.h"
 #include "llvm/IR/Value.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
-#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
 #include "llvm/Transforms/InstCombine/InstCombiner.h"
+#include "llvm/Transforms/Utils/InstructionWorklist.h"
 #include <cassert>
 #include <cstdint>
 #include <iterator>
 #include <utility>
 
 using namespace llvm;
 using namespace PatternMatch;
 

llvm/lib/Transforms/InstCombine/InstructionCombining.cpp

 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Compiler.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/DebugCounter.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/KnownBits.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/InstCombine/InstCombine.h"
-#include "llvm/Transforms/InstCombine/InstCombineWorklist.h"
+#include "llvm/Transforms/Utils/InstructionWorklist.h"
 #include "llvm/Transforms/Utils/Local.h"
 #include <algorithm>
 #include <cassert>
 #include <cstdint>
 #include <memory>
 #include <string>
 #include <utility>
 

 ///
 /// This has a couple of tricks to make the code faster and more powerful.  In
 /// particular, we constant fold and DCE instructions as we go, to avoid adding
 /// them to the worklist (this significantly speeds up instcombine on code where
 /// many instructions are dead or constant).  Additionally, if we find a branch
 /// whose condition is a known constant, we only visit the reachable successors.
 static bool prepareICWorklistFromFunction(Function &F, const DataLayout &DL,
                                           const TargetLibraryInfo *TLI,
-                                          InstCombineWorklist &ICWorklist) {
+                                          InstructionWorklist &ICWorklist) {
   bool MadeIRChange = false;
   SmallPtrSet<BasicBlock *, 32> Visited;
   SmallVector<BasicBlock*, 256> Worklist;
   Worklist.push_back(&F.front());
 
-  SmallVector<Instruction*, 128> InstrsForInstCombineWorklist;
+  SmallVector<Instruction *, 128> InstrsForInstructionWorklist;
   DenseMap<Constant *, Constant *> FoldedConstants;
   AliasScopeTracker SeenAliasScopes;
 
   do {
     BasicBlock *BB = Worklist.pop_back_val();
 
     // We have now visited this block!  If we've already been here, ignore it.
     if (!Visited.insert(BB).second)
for (Instruction &Inst : llvm::make_early_inc_range(*BB)) {
           MadeIRChange = true;
         }
       }
 
       // Skip processing debug and pseudo intrinsics in InstCombine. Processing
       // these call instructions consumes non-trivial amount of time and
       // provides no value for the optimization.
       if (!Inst.isDebugOrPseudoInst()) {
-        InstrsForInstCombineWorklist.push_back(&Inst);
+        InstrsForInstructionWorklist.push_back(&Inst);
         SeenAliasScopes.analyse(&Inst);
       }
     }
 
     // Recursively visit successors.  If this is a branch or switch on a
     // constant, only visit the reachable successor.
     Instruction *TI = BB->getTerminator();
     if (BranchInst *BI = dyn_cast<BranchInst>(TI)) {
for (BasicBlock &BB : F) {
     NumDeadInst += NumDeadInstInBB;
   }
 
   // Once we've found all of the instructions to add to instcombine's worklist,
   // add them in reverse order.  This way instcombine will visit from the top
   // of the function down.  This jives well with the way that it adds all uses
   // of instructions to the worklist after doing a transformation, thus avoiding
   // some N^2 behavior in pathological cases.
-  ICWorklist.reserve(InstrsForInstCombineWorklist.size());
-  for (Instruction *Inst : reverse(InstrsForInstCombineWorklist)) {
+  ICWorklist.reserve(InstrsForInstructionWorklist.size());
+  for (Instruction *Inst : reverse(InstrsForInstructionWorklist)) {
     // DCE instruction if trivially dead. As we iterate in reverse program
     // order here, we will clean up whole chains of dead instructions.
     if (isInstructionTriviallyDead(Inst, TLI) ||
         SeenAliasScopes.isNoAliasScopeDeclDead(Inst)) {
       ++NumDeadInst;
       LLVM_DEBUG(dbgs() << "IC: DCE: " << *Inst << '\n');
       salvageDebugInfo(*Inst);
       Inst->eraseFromParent();
       MadeIRChange = true;
       continue;
     }
 
     ICWorklist.push(Inst);
   }
 
   return MadeIRChange;
 }
 
 static bool combineInstructionsOverFunction(
-    Function &F, InstCombineWorklist &Worklist, AliasAnalysis *AA,
+    Function &F, InstructionWorklist &Worklist, AliasAnalysis *AA,
     AssumptionCache &AC, TargetLibraryInfo &TLI, TargetTransformInfo &TTI,
     DominatorTree &DT, OptimizationRemarkEmitter &ORE, BlockFrequencyInfo *BFI,
     ProfileSummaryInfo *PSI, unsigned MaxIterations, LoopInfo *LI) {
   auto &DL = F.getParent()->getDataLayout();
   MaxIterations = std::min(MaxIterations, LimitMaxIterations.getValue());
 
   /// Builder - This is an IRBuilder that automatically inserts new
   /// instructions into the worklist when they are created.