Details | Last modification | View Log | RSS feed
| Rev | Author | Line No. | Line |
|---|---|---|---|
| 14 | pmbaty | 1 | //=== InstructionWorklist.h - Worklist for InstCombine & others -*- 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_TRANSFORMS_UTILS_INSTRUCTIONWORKLIST_H |
||
| 10 | #define LLVM_TRANSFORMS_UTILS_INSTRUCTIONWORKLIST_H |
||
| 11 | |||
| 12 | #include "llvm/ADT/DenseMap.h" |
||
| 13 | #include "llvm/ADT/STLExtras.h" |
||
| 14 | #include "llvm/ADT/SetVector.h" |
||
| 15 | #include "llvm/ADT/SmallVector.h" |
||
| 16 | #include "llvm/IR/Instruction.h" |
||
| 17 | #include "llvm/Support/Compiler.h" |
||
| 18 | #include "llvm/Support/Debug.h" |
||
| 19 | #include "llvm/Support/raw_ostream.h" |
||
| 20 | |||
| 21 | namespace llvm { |
||
| 22 | |||
| 23 | /// InstructionWorklist - This is the worklist management logic for |
||
| 24 | /// InstCombine and other simplification passes. |
||
| 25 | class InstructionWorklist { |
||
| 26 | SmallVector<Instruction *, 256> Worklist; |
||
| 27 | DenseMap<Instruction *, unsigned> WorklistMap; |
||
| 28 | /// These instructions will be added in reverse order after the current |
||
| 29 | /// combine has finished. This means that these instructions will be visited |
||
| 30 | /// in the order they have been added. |
||
| 31 | SmallSetVector<Instruction *, 16> Deferred; |
||
| 32 | |||
| 33 | public: |
||
| 34 | InstructionWorklist() = default; |
||
| 35 | |||
| 36 | InstructionWorklist(InstructionWorklist &&) = default; |
||
| 37 | InstructionWorklist &operator=(InstructionWorklist &&) = default; |
||
| 38 | |||
| 39 | bool isEmpty() const { return Worklist.empty() && Deferred.empty(); } |
||
| 40 | |||
| 41 | /// Add instruction to the worklist. |
||
| 42 | /// Instructions will be visited in the order they are added. |
||
| 43 | /// You likely want to use this method. |
||
| 44 | void add(Instruction *I) { |
||
| 45 | if (Deferred.insert(I)) |
||
| 46 | LLVM_DEBUG(dbgs() << "ADD DEFERRED: " << *I << '\n'); |
||
| 47 | } |
||
| 48 | |||
| 49 | /// Add value to the worklist if it is an instruction. |
||
| 50 | /// Instructions will be visited in the order they are added. |
||
| 51 | void addValue(Value *V) { |
||
| 52 | if (Instruction *I = dyn_cast<Instruction>(V)) |
||
| 53 | add(I); |
||
| 54 | } |
||
| 55 | |||
| 56 | /// Push the instruction onto the worklist stack. |
||
| 57 | /// Instructions that have been added first will be visited last. |
||
| 58 | void push(Instruction *I) { |
||
| 59 | assert(I); |
||
| 60 | assert(I->getParent() && "Instruction not inserted yet?"); |
||
| 61 | |||
| 62 | if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) { |
||
| 63 | LLVM_DEBUG(dbgs() << "ADD: " << *I << '\n'); |
||
| 64 | Worklist.push_back(I); |
||
| 65 | } |
||
| 66 | } |
||
| 67 | |||
| 68 | void pushValue(Value *V) { |
||
| 69 | if (Instruction *I = dyn_cast<Instruction>(V)) |
||
| 70 | push(I); |
||
| 71 | } |
||
| 72 | |||
| 73 | Instruction *popDeferred() { |
||
| 74 | if (Deferred.empty()) |
||
| 75 | return nullptr; |
||
| 76 | return Deferred.pop_back_val(); |
||
| 77 | } |
||
| 78 | |||
| 79 | void reserve(size_t Size) { |
||
| 80 | Worklist.reserve(Size + 16); |
||
| 81 | WorklistMap.reserve(Size); |
||
| 82 | } |
||
| 83 | |||
| 84 | /// Remove I from the worklist if it exists. |
||
| 85 | void remove(Instruction *I) { |
||
| 86 | DenseMap<Instruction *, unsigned>::iterator It = WorklistMap.find(I); |
||
| 87 | if (It != WorklistMap.end()) { |
||
| 88 | // Don't bother moving everything down, just null out the slot. |
||
| 89 | Worklist[It->second] = nullptr; |
||
| 90 | WorklistMap.erase(It); |
||
| 91 | } |
||
| 92 | |||
| 93 | Deferred.remove(I); |
||
| 94 | } |
||
| 95 | |||
| 96 | Instruction *removeOne() { |
||
| 97 | if (Worklist.empty()) |
||
| 98 | return nullptr; |
||
| 99 | Instruction *I = Worklist.pop_back_val(); |
||
| 100 | WorklistMap.erase(I); |
||
| 101 | return I; |
||
| 102 | } |
||
| 103 | |||
| 104 | /// When an instruction is simplified, add all users of the instruction |
||
| 105 | /// to the work lists because they might get more simplified now. |
||
| 106 | void pushUsersToWorkList(Instruction &I) { |
||
| 107 | for (User *U : I.users()) |
||
| 108 | push(cast<Instruction>(U)); |
||
| 109 | } |
||
| 110 | |||
| 111 | /// Check that the worklist is empty and nuke the backing store for the map. |
||
| 112 | void zap() { |
||
| 113 | assert(WorklistMap.empty() && "Worklist empty, but map not?"); |
||
| 114 | assert(Deferred.empty() && "Deferred instructions left over"); |
||
| 115 | |||
| 116 | // Do an explicit clear, this shrinks the map if needed. |
||
| 117 | WorklistMap.clear(); |
||
| 118 | } |
||
| 119 | }; |
||
| 120 | |||
| 121 | } // end namespace llvm. |
||
| 122 | |||
| 123 | #endif |