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 #ifndef NDEBUG 32 bool Finalized = true; 33 #endif 34 35 public: 36 GISelWorkList() : WorklistMap(N) {} 37 38 bool empty() const { return WorklistMap.empty(); } 39 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. 50 void deferred_insert(MachineInstr *I) { 51 Worklist.push_back(I); 52 #ifndef NDEBUG 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. 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 #ifndef NDEBUG 69 Finalized = true; 70 #endif 71 } 72 73 /// Add the specified instruction to the worklist if it isn't already in it. 74 void insert(MachineInstr *I) { 75 assert(Finalized && "GISelWorkList used without finalizing"); 76 if (WorklistMap.try_emplace(I, Worklist.size()).second) 77 Worklist.push_back(I); 78 } 79 80 /// Remove I from the worklist if it exists. 81 void remove(const MachineInstr *I) { 82 assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty"); 83 auto It = WorklistMap.find(I); 84 if (It == WorklistMap.end()) 85 return; // Not in worklist. 86 87 // Don't bother moving everything down, just null out the slot. 88 Worklist[It->second] = nullptr; 89 90 WorklistMap.erase(It); 91 } 92 93 void clear() { 94 Worklist.clear(); 95 WorklistMap.clear(); 96 } 97 98 MachineInstr *pop_back_val() { 99 assert(Finalized && "GISelWorkList used without finalizing"); 100 MachineInstr *I; 101 do { 102 I = Worklist.pop_back_val(); 103 } while(!I); 104 assert(I && "Pop back on empty worklist"); 105 WorklistMap.erase(I); 106 return I; 107 } 108 }; 109 110 } // end namespace llvm. 111 112 #endif 113