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 #define DEBUG_TYPE "instcombine" 14 #include "llvm/ADT/DenseMap.h" 15 #include "llvm/ADT/SmallVector.h" 16 #include "llvm/IR/Instruction.h" 17 #include "llvm/Support/Compiler.h" 18 #include "llvm/Support/Debug.h" 19 #include "llvm/Support/raw_ostream.h" 20 21 namespace llvm { 22 23 /// InstCombineWorklist - This is the worklist management logic for 24 /// InstCombine. 25 class LLVM_LIBRARY_VISIBILITY InstCombineWorklist { 26 SmallVector<Instruction*, 256> Worklist; 27 DenseMap<Instruction*, unsigned> WorklistMap; 28 29 void operator=(const InstCombineWorklist&RHS) LLVM_DELETED_FUNCTION; 30 InstCombineWorklist(const InstCombineWorklist&) LLVM_DELETED_FUNCTION; 31 public: 32 InstCombineWorklist() {} 33 34 bool isEmpty() const { return Worklist.empty(); } 35 36 /// Add - Add the specified instruction to the worklist if it isn't already 37 /// in it. 38 void Add(Instruction *I) { 39 if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) { 40 DEBUG(errs() << "IC: ADD: " << *I << '\n'); 41 Worklist.push_back(I); 42 } 43 } 44 45 void AddValue(Value *V) { 46 if (Instruction *I = dyn_cast<Instruction>(V)) 47 Add(I); 48 } 49 50 /// AddInitialGroup - Add the specified batch of stuff in reverse order. 51 /// which should only be done when the worklist is empty and when the group 52 /// has no duplicates. 53 void AddInitialGroup(Instruction *const *List, unsigned NumEntries) { 54 assert(Worklist.empty() && "Worklist must be empty to add initial group"); 55 Worklist.reserve(NumEntries+16); 56 WorklistMap.resize(NumEntries); 57 DEBUG(errs() << "IC: ADDING: " << NumEntries << " instrs to worklist\n"); 58 for (unsigned Idx = 0; NumEntries; --NumEntries) { 59 Instruction *I = List[NumEntries-1]; 60 WorklistMap.insert(std::make_pair(I, Idx++)); 61 Worklist.push_back(I); 62 } 63 } 64 65 // Remove - remove I from the worklist if it exists. 66 void Remove(Instruction *I) { 67 DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(I); 68 if (It == WorklistMap.end()) return; // Not in worklist. 69 70 // Don't bother moving everything down, just null out the slot. 71 Worklist[It->second] = 0; 72 73 WorklistMap.erase(It); 74 } 75 76 Instruction *RemoveOne() { 77 Instruction *I = Worklist.back(); 78 Worklist.pop_back(); 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 (Value::use_iterator UI = I.use_begin(), UE = I.use_end(); 89 UI != UE; ++UI) 90 Add(cast<Instruction>(*UI)); 91 } 92 93 94 /// Zap - check that the worklist is empty and nuke the backing store for 95 /// the map if it is large. 96 void Zap() { 97 assert(WorklistMap.empty() && "Worklist empty, but map not?"); 98 99 // Do an explicit clear, this shrinks the map if needed. 100 WorklistMap.clear(); 101 } 102 }; 103 104 } // end namespace llvm. 105 106 #endif 107
