1 //===- InstCombineWorklist.h - Worklist for InstCombine pass ----*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef INSTCOMBINE_WORKLIST_H 11 #define INSTCOMBINE_WORKLIST_H 12 13 #include "llvm/ADT/DenseMap.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 LLVM_LIBRARY_VISIBILITY InstCombineWorklist { 27 SmallVector<Instruction*, 256> Worklist; 28 DenseMap<Instruction*, unsigned> WorklistMap; 29 30 void operator=(const InstCombineWorklist&RHS) LLVM_DELETED_FUNCTION; 31 InstCombineWorklist(const InstCombineWorklist&) LLVM_DELETED_FUNCTION; 32 public: 33 InstCombineWorklist() {} 34 35 bool isEmpty() const { return Worklist.empty(); } 36 37 /// Add - Add the specified instruction to the worklist if it isn't already 38 /// in it. 39 void Add(Instruction *I) { 40 if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) { 41 DEBUG(dbgs() << "IC: ADD: " << *I << '\n'); 42 Worklist.push_back(I); 43 } 44 } 45 46 void AddValue(Value *V) { 47 if (Instruction *I = dyn_cast<Instruction>(V)) 48 Add(I); 49 } 50 51 /// AddInitialGroup - Add the specified batch of stuff in reverse order. 52 /// which should only be done when the worklist is empty and when the group 53 /// has no duplicates. 54 void AddInitialGroup(Instruction *const *List, unsigned NumEntries) { 55 assert(Worklist.empty() && "Worklist must be empty to add initial group"); 56 Worklist.reserve(NumEntries+16); 57 WorklistMap.resize(NumEntries); 58 DEBUG(dbgs() << "IC: ADDING: " << NumEntries << " instrs to worklist\n"); 59 for (unsigned Idx = 0; NumEntries; --NumEntries) { 60 Instruction *I = List[NumEntries-1]; 61 WorklistMap.insert(std::make_pair(I, Idx++)); 62 Worklist.push_back(I); 63 } 64 } 65 66 // Remove - remove I from the worklist if it exists. 67 void Remove(Instruction *I) { 68 DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(I); 69 if (It == WorklistMap.end()) return; // Not in worklist. 70 71 // Don't bother moving everything down, just null out the slot. 72 Worklist[It->second] = nullptr; 73 74 WorklistMap.erase(It); 75 } 76 77 Instruction *RemoveOne() { 78 Instruction *I = Worklist.pop_back_val(); 79 WorklistMap.erase(I); 80 return I; 81 } 82 83 /// AddUsersToWorkList - When an instruction is simplified, add all users of 84 /// the instruction to the work lists because they might get more simplified 85 /// now. 86 /// 87 void AddUsersToWorkList(Instruction &I) { 88 for (User *U : I.users()) 89 Add(cast<Instruction>(U)); 90 } 91 92 93 /// Zap - check that the worklist is empty and nuke the backing store for 94 /// the map if it is large. 95 void Zap() { 96 assert(WorklistMap.empty() && "Worklist empty, but map not?"); 97 98 // Do an explicit clear, this shrinks the map if needed. 99 WorklistMap.clear(); 100 } 101 }; 102 103 } // end namespace llvm. 104 105 #undef DEBUG_TYPE 106 107 #endif 108