1 //===- GISelWorkList.h - Worklist for GISel passes ----*- 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 LLVM_GISEL_WORKLIST_H 11 #define LLVM_GISEL_WORKLIST_H 12 13 #include "llvm/ADT/DenseMap.h" 14 #include "llvm/ADT/SmallVector.h" 15 #include "llvm/Support/Debug.h" 16 17 namespace llvm { 18 19 class MachineInstr; 20 21 // Worklist which mostly works similar to InstCombineWorkList, but on MachineInstrs. 22 // The main difference with something like a SetVector is that erasing an element doesn't 23 // move all elements over one place - instead just nulls out the element of the vector. 24 // FIXME: Does it make sense to factor out common code with the instcombinerWorkList? 25 template<unsigned N> 26 class GISelWorkList { 27 SmallVector<MachineInstr*, N> Worklist; 28 DenseMap<MachineInstr*, unsigned> WorklistMap; 29 30 public: 31 GISelWorkList() = default; 32 empty()33 bool empty() const { return WorklistMap.empty(); } 34 size()35 unsigned size() const { return WorklistMap.size(); } 36 37 /// Add - Add the specified instruction to the worklist if it isn't already 38 /// in it. insert(MachineInstr * I)39 void insert(MachineInstr *I) { 40 if (WorklistMap.try_emplace(I, Worklist.size()).second) { 41 Worklist.push_back(I); 42 } 43 } 44 45 /// Remove - remove I from the worklist if it exists. remove(MachineInstr * I)46 void remove(MachineInstr *I) { 47 auto It = WorklistMap.find(I); 48 if (It == WorklistMap.end()) return; // Not in worklist. 49 50 // Don't bother moving everything down, just null out the slot. 51 Worklist[It->second] = nullptr; 52 53 WorklistMap.erase(It); 54 } 55 pop_back_val()56 MachineInstr *pop_back_val() { 57 MachineInstr *I; 58 do { 59 I = Worklist.pop_back_val(); 60 } while(!I); 61 assert(I && "Pop back on empty worklist"); 62 WorklistMap.erase(I); 63 return I; 64 } 65 }; 66 67 } // end namespace llvm. 68 69 #endif 70