InstCombineWorklist.h revision 360784
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 22namespace llvm { 23 24/// InstCombineWorklist - This is the worklist management logic for 25/// InstCombine. 26class InstCombineWorklist { 27 SmallVector<Instruction *, 256> Worklist; 28 DenseMap<Instruction *, unsigned> WorklistMap; 29 30public: 31 InstCombineWorklist() = default; 32 33 InstCombineWorklist(InstCombineWorklist &&) = default; 34 InstCombineWorklist &operator=(InstCombineWorklist &&) = default; 35 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. 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 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. 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. 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 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 /// 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. 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