include/llvm/CodeGen/GlobalISel/GISelWorkList.h

   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