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