1 //===- InstCombineWorklist.h - Worklist for InstCombine pass ----*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #ifndef LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H 10 #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H 11 12 #include "llvm/ADT/DenseMap.h" 13 #include "llvm/ADT/STLExtras.h" 14 #include "llvm/ADT/SmallVector.h" 15 #include "llvm/IR/Instruction.h" 16 #include "llvm/Support/Compiler.h" 17 #include "llvm/Support/Debug.h" 18 #include "llvm/Support/raw_ostream.h" 19 20 #define DEBUG_TYPE "instcombine" 21 22 namespace llvm { 23 24 /// InstCombineWorklist - This is the worklist management logic for 25 /// InstCombine. 26 class InstCombineWorklist { 27 SmallVector<Instruction *, 256> Worklist; 28 DenseMap<Instruction *, unsigned> WorklistMap; 29 30 public: 31 InstCombineWorklist() = default; 32 33 InstCombineWorklist(InstCombineWorklist &&) = default; 34 InstCombineWorklist &operator=(InstCombineWorklist &&) = default; 35 isEmpty()36 bool isEmpty() const { return Worklist.empty(); } 37 38 /// Add - Add the specified instruction to the worklist if it isn't already 39 /// in it. Add(Instruction * I)40 void Add(Instruction *I) { 41 assert(I); 42 assert(I->getParent() && "Instruction not inserted yet?"); 43 44 if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) { 45 LLVM_DEBUG(dbgs() << "IC: ADD: " << *I << '\n'); 46 Worklist.push_back(I); 47 } 48 } 49 AddValue(Value * V)50 void AddValue(Value *V) { 51 if (Instruction *I = dyn_cast<Instruction>(V)) 52 Add(I); 53 } 54 55 /// AddInitialGroup - Add the specified batch of stuff in reverse order. 56 /// which should only be done when the worklist is empty and when the group 57 /// has no duplicates. AddInitialGroup(ArrayRef<Instruction * > List)58 void AddInitialGroup(ArrayRef<Instruction *> List) { 59 assert(Worklist.empty() && "Worklist must be empty to add initial group"); 60 Worklist.reserve(List.size()+16); 61 WorklistMap.reserve(List.size()); 62 LLVM_DEBUG(dbgs() << "IC: ADDING: " << List.size() 63 << " instrs to worklist\n"); 64 unsigned Idx = 0; 65 for (Instruction *I : reverse(List)) { 66 WorklistMap.insert(std::make_pair(I, Idx++)); 67 Worklist.push_back(I); 68 } 69 } 70 71 // Remove - remove I from the worklist if it exists. Remove(Instruction * I)72 void Remove(Instruction *I) { 73 DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(I); 74 if (It == WorklistMap.end()) return; // Not in worklist. 75 76 // Don't bother moving everything down, just null out the slot. 77 Worklist[It->second] = nullptr; 78 79 WorklistMap.erase(It); 80 } 81 RemoveOne()82 Instruction *RemoveOne() { 83 Instruction *I = Worklist.pop_back_val(); 84 WorklistMap.erase(I); 85 return I; 86 } 87 88 /// AddUsersToWorkList - When an instruction is simplified, add all users of 89 /// the instruction to the work lists because they might get more simplified 90 /// now. 91 /// AddUsersToWorkList(Instruction & I)92 void AddUsersToWorkList(Instruction &I) { 93 for (User *U : I.users()) 94 Add(cast<Instruction>(U)); 95 } 96 97 98 /// Zap - check that the worklist is empty and nuke the backing store for 99 /// the map if it is large. Zap()100 void Zap() { 101 assert(WorklistMap.empty() && "Worklist empty, but map not?"); 102 103 // Do an explicit clear, this shrinks the map if needed. 104 WorklistMap.clear(); 105 } 106 }; 107 108 } // end namespace llvm. 109 110 #undef DEBUG_TYPE 111 112 #endif 113