1//===- InstCombineWorklist.h - Worklist for the InstCombine pass ----------===// 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/Instruction.h" 15#include "llvm/Support/Debug.h" 16#include "llvm/Support/Compiler.h" 17#include "llvm/ADT/SmallVector.h" 18#include "llvm/ADT/DenseMap.h" 19#include "llvm/Support/raw_ostream.h" 20 21namespace llvm { 22 23/// InstCombineWorklist - This is the worklist management logic for 24/// InstCombine. 25class 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; 31public: 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