1 //===- GISelWorkList.h - Worklist for GISel passes ----*- 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_CODEGEN_GLOBALISEL_GISELWORKLIST_H 10 #define LLVM_CODEGEN_GLOBALISEL_GISELWORKLIST_H 11 12 #include "llvm/ADT/DenseMap.h" 13 #include "llvm/ADT/SmallVector.h" 14 15 namespace llvm { 16 17 class MachineInstr; 18 19 // Worklist which mostly works similar to InstCombineWorkList, but on 20 // MachineInstrs. The main difference with something like a SetVector is that 21 // erasing an element doesn't move all elements over one place - instead just 22 // nulls out the element of the vector. 23 // 24 // FIXME: Does it make sense to factor out common code with the 25 // instcombinerWorkList? 26 template<unsigned N> 27 class GISelWorkList { 28 SmallVector<MachineInstr *, N> Worklist; 29 DenseMap<MachineInstr *, unsigned> WorklistMap; 30 31 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 32 bool Finalized = true; 33 #endif 34 35 public: GISelWorkList()36 GISelWorkList() : WorklistMap(N) {} 37 empty()38 bool empty() const { return WorklistMap.empty(); } 39 size()40 unsigned size() const { return WorklistMap.size(); } 41 42 // Since we don't know ahead of time how many instructions we're going to add 43 // to the worklist, and migrating densemap's elements is quite expensive 44 // everytime we resize, only insert to the smallvector (typically during the 45 // initial phase of populating lists). Before the worklist can be used, 46 // finalize should be called. Also assert with NDEBUG if list is ever used 47 // without finalizing. Note that unlike insert, we won't check for duplicates 48 // - so the ideal place to use this is during the initial prepopulating phase 49 // of most passes. deferred_insert(MachineInstr * I)50 void deferred_insert(MachineInstr *I) { 51 Worklist.push_back(I); 52 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 53 Finalized = false; 54 #endif 55 } 56 57 // This should only be called when using deferred_insert. 58 // This asserts that the WorklistMap is empty, and then 59 // inserts all the elements in the Worklist into the map. 60 // It also asserts if there are any duplicate elements found. finalize()61 void finalize() { 62 assert(WorklistMap.empty() && "Expecting empty worklistmap"); 63 if (Worklist.size() > N) 64 WorklistMap.reserve(Worklist.size()); 65 for (unsigned i = 0; i < Worklist.size(); ++i) 66 if (!WorklistMap.try_emplace(Worklist[i], i).second) 67 llvm_unreachable("Duplicate elements in the list"); 68 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 69 Finalized = true; 70 #endif 71 } 72 73 /// Add the specified instruction to the worklist if it isn't already in it. insert(MachineInstr * I)74 void insert(MachineInstr *I) { 75 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 76 assert(Finalized && "GISelWorkList used without finalizing"); 77 #endif 78 if (WorklistMap.try_emplace(I, Worklist.size()).second) 79 Worklist.push_back(I); 80 } 81 82 /// Remove I from the worklist if it exists. remove(const MachineInstr * I)83 void remove(const MachineInstr *I) { 84 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 85 assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty"); 86 #endif 87 auto It = WorklistMap.find(I); 88 if (It == WorklistMap.end()) 89 return; // Not in worklist. 90 91 // Don't bother moving everything down, just null out the slot. 92 Worklist[It->second] = nullptr; 93 94 WorklistMap.erase(It); 95 } 96 clear()97 void clear() { 98 Worklist.clear(); 99 WorklistMap.clear(); 100 } 101 pop_back_val()102 MachineInstr *pop_back_val() { 103 #if LLVM_ENABLE_ABI_BREAKING_CHECKS 104 assert(Finalized && "GISelWorkList used without finalizing"); 105 #endif 106 MachineInstr *I; 107 do { 108 I = Worklist.pop_back_val(); 109 } while(!I); 110 assert(I && "Pop back on empty worklist"); 111 WorklistMap.erase(I); 112 return I; 113 } 114 }; 115 116 } // end namespace llvm. 117 118 #endif 119