Transforms/Utils/InstructionWorklist.h

0001 //=== InstructionWorklist.h - Worklist for InstCombine & others -*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_TRANSFORMS_UTILS_INSTRUCTIONWORKLIST_H
0010 #define LLVM_TRANSFORMS_UTILS_INSTRUCTIONWORKLIST_H
0011
0012 #include "llvm/ADT/DenseMap.h"
0013 #include "llvm/ADT/STLExtras.h"
0014 #include "llvm/ADT/SetVector.h"
0015 #include "llvm/ADT/SmallVector.h"
0016 #include "llvm/IR/Instruction.h"
0017 #include "llvm/Support/Compiler.h"
0018 #include "llvm/Support/Debug.h"
0019 #include "llvm/Support/raw_ostream.h"
0020
0021 namespace llvm {
0022
0023 /// InstructionWorklist - This is the worklist management logic for
0024 /// InstCombine and other simplification passes.
0025 class InstructionWorklist {
0026   SmallVector<Instruction *, 256> Worklist;
0027   DenseMap<Instruction *, unsigned> WorklistMap;
0028   /// These instructions will be added in reverse order after the current
0029   /// combine has finished. This means that these instructions will be visited
0030   /// in the order they have been added.
0031   SmallSetVector<Instruction *, 16> Deferred;
0032
0033 public:
0034   InstructionWorklist() = default;
0035
0036   InstructionWorklist(InstructionWorklist &&) = default;
0037   InstructionWorklist &operator=(InstructionWorklist &&) = default;
0038
0039   bool isEmpty() const { return Worklist.empty() && Deferred.empty(); }
0040
0041   /// Add instruction to the worklist.
0042   /// Instructions will be visited in the order they are added.
0043   /// You likely want to use this method.
0044   void add(Instruction *I) {
0045     if (Deferred.insert(I))
0046       LLVM_DEBUG(dbgs() << "ADD DEFERRED: " << *I << '\n');
0047   }
0048
0049   /// Add value to the worklist if it is an instruction.
0050   /// Instructions will be visited in the order they are added.
0051   void addValue(Value *V) {
0052     if (Instruction *I = dyn_cast<Instruction>(V))
0053       add(I);
0054   }
0055
0056   /// Push the instruction onto the worklist stack.
0057   /// Instructions that have been added first will be visited last.
0058   void push(Instruction *I) {
0059     assert(I);
0060     assert(I->getParent() && "Instruction not inserted yet?");
0061
0062     if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
0063       LLVM_DEBUG(dbgs() << "ADD: " << *I << '\n');
0064       Worklist.push_back(I);
0065     }
0066   }
0067
0068   void pushValue(Value *V) {
0069     if (Instruction *I = dyn_cast<Instruction>(V))
0070       push(I);
0071   }
0072
0073   Instruction *popDeferred() {
0074     if (Deferred.empty())
0075       return nullptr;
0076     return Deferred.pop_back_val();
0077   }
0078
0079   void reserve(size_t Size) {
0080     Worklist.reserve(Size + 16);
0081     WorklistMap.reserve(Size);
0082   }
0083
0084   /// Remove I from the worklist if it exists.
0085   void remove(Instruction *I) {
0086     DenseMap<Instruction *, unsigned>::iterator It = WorklistMap.find(I);
0087     if (It != WorklistMap.end()) {
0088       // Don't bother moving everything down, just null out the slot.
0089       Worklist[It->second] = nullptr;
0090       WorklistMap.erase(It);
0091     }
0092
0093     Deferred.remove(I);
0094   }
0095
0096   Instruction *removeOne() {
0097     if (Worklist.empty())
0098       return nullptr;
0099     Instruction *I = Worklist.pop_back_val();
0100     WorklistMap.erase(I);
0101     return I;
0102   }
0103
0104   /// When an instruction is simplified, add all users of the instruction
0105   /// to the work lists because they might get more simplified now.
0106   void pushUsersToWorkList(Instruction &I) {
0107     for (User *U : I.users())
0108       push(cast<Instruction>(U));
0109   }
0110
0111   /// Should be called *after* decrementing the use-count on V.
0112   void handleUseCountDecrement(Value *V) {
0113     if (auto *I = dyn_cast<Instruction>(V)) {
0114       add(I);
0115       // Many folds have one-use limitations. If there's only one use left,
0116       // revisit that use.
0117       if (I->hasOneUse())
0118         add(cast<Instruction>(*I->user_begin()));
0119     }
0120   }
0121
0122   /// Check that the worklist is empty and nuke the backing store for the map.
0123   void zap() {
0124     assert(WorklistMap.empty() && "Worklist empty, but map not?");
0125     assert(Deferred.empty() && "Deferred instructions left over");
0126
0127     // Do an explicit clear, this shrinks the map if needed.
0128     WorklistMap.clear();
0129   }
0130 };
0131
0132 } // end namespace llvm.
0133
0134 #endif