1326938Sdim//===- GISelWorkList.h - Worklist for GISel passes ----*- C++ -*-===// 2326938Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6326938Sdim// 7326938Sdim//===----------------------------------------------------------------------===// 8326938Sdim 9326938Sdim#ifndef LLVM_GISEL_WORKLIST_H 10326938Sdim#define LLVM_GISEL_WORKLIST_H 11326938Sdim 12326938Sdim#include "llvm/ADT/DenseMap.h" 13326938Sdim#include "llvm/ADT/SmallVector.h" 14344779Sdim#include "llvm/CodeGen/MachineBasicBlock.h" 15344779Sdim#include "llvm/CodeGen/MachineInstr.h" 16326938Sdim#include "llvm/Support/Debug.h" 17326938Sdim 18326938Sdimnamespace llvm { 19326938Sdim 20326938Sdimclass MachineInstr; 21344779Sdimclass MachineFunction; 22326938Sdim 23344779Sdim// Worklist which mostly works similar to InstCombineWorkList, but on 24344779Sdim// MachineInstrs. The main difference with something like a SetVector is that 25344779Sdim// erasing an element doesn't move all elements over one place - instead just 26344779Sdim// nulls out the element of the vector. 27344779Sdim// 28344779Sdim// FIXME: Does it make sense to factor out common code with the 29344779Sdim// instcombinerWorkList? 30326938Sdimtemplate<unsigned N> 31326938Sdimclass GISelWorkList { 32344779Sdim SmallVector<MachineInstr *, N> Worklist; 33344779Sdim DenseMap<MachineInstr *, unsigned> WorklistMap; 34326938Sdim 35353358Sdim#ifndef NDEBUG 36353358Sdim bool Finalized = true; 37353358Sdim#endif 38353358Sdim 39326938Sdimpublic: 40353358Sdim GISelWorkList() : WorklistMap(N) {} 41326938Sdim 42326938Sdim bool empty() const { return WorklistMap.empty(); } 43326938Sdim 44326938Sdim unsigned size() const { return WorklistMap.size(); } 45326938Sdim 46353358Sdim // Since we don't know ahead of time how many instructions we're going to add 47353358Sdim // to the worklist, and migrating densemap's elements is quite expensive 48353358Sdim // everytime we resize, only insert to the smallvector (typically during the 49353358Sdim // initial phase of populating lists). Before the worklist can be used, 50353358Sdim // finalize should be called. Also assert with NDEBUG if list is ever used 51353358Sdim // without finalizing. Note that unlike insert, we won't check for duplicates 52353358Sdim // - so the ideal place to use this is during the initial prepopulating phase 53353358Sdim // of most passes. 54353358Sdim void deferred_insert(MachineInstr *I) { 55353358Sdim Worklist.push_back(I); 56353358Sdim#ifndef NDEBUG 57353358Sdim Finalized = false; 58353358Sdim#endif 59353358Sdim } 60353358Sdim 61353358Sdim // This should only be called when using deferred_insert. 62353358Sdim // This asserts that the WorklistMap is empty, and then 63353358Sdim // inserts all the elements in the Worklist into the map. 64353358Sdim // It also asserts if there are any duplicate elements found. 65353358Sdim void finalize() { 66353358Sdim assert(WorklistMap.empty() && "Expecting empty worklistmap"); 67353358Sdim if (Worklist.size() > N) 68353358Sdim WorklistMap.reserve(Worklist.size()); 69353358Sdim for (unsigned i = 0; i < Worklist.size(); ++i) 70353358Sdim if (!WorklistMap.try_emplace(Worklist[i], i).second) 71353358Sdim llvm_unreachable("Duplicate elements in the list"); 72353358Sdim#ifndef NDEBUG 73353358Sdim Finalized = true; 74353358Sdim#endif 75353358Sdim } 76353358Sdim 77344779Sdim /// Add the specified instruction to the worklist if it isn't already in it. 78326938Sdim void insert(MachineInstr *I) { 79353358Sdim assert(Finalized && "GISelWorkList used without finalizing"); 80344779Sdim if (WorklistMap.try_emplace(I, Worklist.size()).second) 81326938Sdim Worklist.push_back(I); 82326938Sdim } 83326938Sdim 84344779Sdim /// Remove I from the worklist if it exists. 85344779Sdim void remove(const MachineInstr *I) { 86353358Sdim assert((Finalized || WorklistMap.empty()) && "Neither finalized nor empty"); 87326938Sdim auto It = WorklistMap.find(I); 88353358Sdim if (It == WorklistMap.end()) 89353358Sdim return; // Not in worklist. 90326938Sdim 91326938Sdim // Don't bother moving everything down, just null out the slot. 92326938Sdim Worklist[It->second] = nullptr; 93326938Sdim 94326938Sdim WorklistMap.erase(It); 95326938Sdim } 96326938Sdim 97344779Sdim void clear() { 98344779Sdim Worklist.clear(); 99344779Sdim WorklistMap.clear(); 100344779Sdim } 101344779Sdim 102326938Sdim MachineInstr *pop_back_val() { 103353358Sdim assert(Finalized && "GISelWorkList used without finalizing"); 104326938Sdim MachineInstr *I; 105326938Sdim do { 106326938Sdim I = Worklist.pop_back_val(); 107326938Sdim } while(!I); 108326938Sdim assert(I && "Pop back on empty worklist"); 109326938Sdim WorklistMap.erase(I); 110326938Sdim return I; 111326938Sdim } 112326938Sdim}; 113326938Sdim 114326938Sdim} // end namespace llvm. 115326938Sdim 116326938Sdim#endif 117