CodeGen/GlobalISel/GISelWorkList.h

0001 //===- GISelWorkList.h - Worklist for GISel passes ----*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_CODEGEN_GLOBALISEL_GISELWORKLIST_H
0010 #define LLVM_CODEGEN_GLOBALISEL_GISELWORKLIST_H
0011
0012 #include "llvm/ADT/DenseMap.h"
0013 #include "llvm/ADT/SmallVector.h"
0014
0015 namespace llvm {
0016
0017 class MachineInstr;
0018
0019 // Worklist which mostly works similar to InstCombineWorkList, but on
0020 // MachineInstrs. The main difference with something like a SetVector is that
0021 // erasing an element doesn't move all elements over one place - instead just
0022 // nulls out the element of the vector.
0023 //
0024 // FIXME: Does it make sense to factor out common code with the
0025 // instcombinerWorkList?
0026 template<unsigned N>
0027 class GISelWorkList {
0028   SmallVector<MachineInstr *, N> Worklist;
0029   DenseMap<MachineInstr *, unsigned> WorklistMap;
0030
0031 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
0032   bool Finalized = true;
0033 #endif
0034
0035 public:
0036   GISelWorkList() : WorklistMap(N) {}
0037
0038   bool empty() const { return WorklistMap.empty(); }
0039
0040   unsigned size() const { return WorklistMap.size(); }
0041
0042   // Since we don't know ahead of time how many instructions we're going to add
0043   // to the worklist, and migrating densemap's elements is quite expensive
0044   // everytime we resize, only insert to the smallvector (typically during the
0045   // initial phase of populating lists). Before the worklist can be used,
0046   // finalize should be called. Also assert with NDEBUG if list is ever used
0047   // without finalizing. Note that unlike insert, we won't check for duplicates
0048   // - so the ideal place to use this is during the initial prepopulating phase
0049   // of most passes.
0050   void deferred_insert(MachineInstr *I) {
0051     Worklist.push_back(I);
0052 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
0053     Finalized = false;
0054 #endif
0055   }
0056
0057   // This should only be called when using deferred_insert.
0058   // This asserts that the WorklistMap is empty, and then
0059   // inserts all the elements in the Worklist into the map.
0060   // It also asserts if there are any duplicate elements found.
0061   void finalize() {
0062     assert(WorklistMap.empty() && "Expecting empty worklistmap");
0063     if (Worklist.size() > N)
0064       WorklistMap.reserve(Worklist.size());
0065     for (unsigned i = 0; i < Worklist.size(); ++i)
0066       if (!WorklistMap.try_emplace(Worklist[i], i).second)
0067         llvm_unreachable("Duplicate elements in the list");
0068 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
0069     Finalized = true;
0070 #endif
0071   }
0072
0073   /// Add the specified instruction to the worklist if it isn't already in it.
0074   void insert(MachineInstr *I) {
0075 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
0076     assert(Finalized && "GISelWorkList used without finalizing");
0077 #endif
0078     if (WorklistMap.try_emplace(I, Worklist.size()).second)
0079       Worklist.push_back(I);
0080   }
0081
0082   /// Remove I from the worklist if it exists.
0083   void remove(const MachineInstr *I) {
0084 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
0085     assert(Finalized && "GISelWorkList used without finalizing");
0086 #endif
0087     auto It = WorklistMap.find(I);
0088     if (It == WorklistMap.end())
0089       return; // Not in worklist.
0090
0091     // Don't bother moving everything down, just null out the slot.
0092     Worklist[It->second] = nullptr;
0093
0094     WorklistMap.erase(It);
0095   }
0096
0097   void clear() {
0098     Worklist.clear();
0099     WorklistMap.clear();
0100   }
0101
0102   MachineInstr *pop_back_val() {
0103 #if LLVM_ENABLE_ABI_BREAKING_CHECKS
0104     assert(Finalized && "GISelWorkList used without finalizing");
0105 #endif
0106     MachineInstr *I;
0107     do {
0108       I = Worklist.pop_back_val();
0109     } while(!I);
0110     assert(I && "Pop back on empty worklist");
0111     WorklistMap.erase(I);
0112     return I;
0113   }
0114 };
0115
0116 } // end namespace llvm.
0117
0118 #endif