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