include/llvm/Transforms/InstCombine/InstCombineWorklist.h

   1 //===- InstCombineWorklist.h - Worklist for InstCombine pass ----*- 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_INSTCOMBINE_INSTCOMBINEWORKLIST_H
  10 #define LLVM_TRANSFORMS_INSTCOMBINE_INSTCOMBINEWORKLIST_H
  11
  12 #include "llvm/ADT/DenseMap.h"
  13 #include "llvm/ADT/STLExtras.h"
  14 #include "llvm/ADT/SmallVector.h"
  15 #include "llvm/IR/Instruction.h"
  16 #include "llvm/Support/Compiler.h"
  17 #include "llvm/Support/Debug.h"
  18 #include "llvm/Support/raw_ostream.h"
  19
  20 #define DEBUG_TYPE "instcombine"
  21
  22 namespace llvm {
  23
  24 /// InstCombineWorklist - This is the worklist management logic for
  25 /// InstCombine.
  26 class InstCombineWorklist {
  27   SmallVector<Instruction*, 256> Worklist;
  28   DenseMap<Instruction*, unsigned> WorklistMap;
  29
  30 public:
  31   InstCombineWorklist() = default;
  32
  33   InstCombineWorklist(InstCombineWorklist &&) = default;
  34   InstCombineWorklist &operator=(InstCombineWorklist &&) = default;
  35
  36   bool isEmpty() const { return Worklist.empty(); }
  37
  38   /// Add - Add the specified instruction to the worklist if it isn't already
  39   /// in it.
  40   void Add(Instruction *I) {
  41     if (WorklistMap.insert(std::make_pair(I, Worklist.size())).second) {
  42       LLVM_DEBUG(dbgs() << "IC: ADD: " << *I << '\n');
  43       Worklist.push_back(I);
  44     }
  45   }
  46
  47   void AddValue(Value *V) {
  48     if (Instruction *I = dyn_cast<Instruction>(V))
  49       Add(I);
  50   }
  51
  52   /// AddInitialGroup - Add the specified batch of stuff in reverse order.
  53   /// which should only be done when the worklist is empty and when the group
  54   /// has no duplicates.
  55   void AddInitialGroup(ArrayRef<Instruction *> List) {
  56     assert(Worklist.empty() && "Worklist must be empty to add initial group");
  57     Worklist.reserve(List.size()+16);
  58     WorklistMap.reserve(List.size());
  59     LLVM_DEBUG(dbgs() << "IC: ADDING: " << List.size()
  60                       << " instrs to worklist\n");
  61     unsigned Idx = 0;
  62     for (Instruction *I : reverse(List)) {
  63       WorklistMap.insert(std::make_pair(I, Idx++));
  64       Worklist.push_back(I);
  65     }
  66   }
  67
  68   // Remove - remove I from the worklist if it exists.
  69   void Remove(Instruction *I) {
  70     DenseMap<Instruction*, unsigned>::iterator It = WorklistMap.find(I);
  71     if (It == WorklistMap.end()) return; // Not in worklist.
  72
  73     // Don't bother moving everything down, just null out the slot.
  74     Worklist[It->second] = nullptr;
  75
  76     WorklistMap.erase(It);
  77   }
  78
  79   Instruction *RemoveOne() {
  80     Instruction *I = Worklist.pop_back_val();
  81     WorklistMap.erase(I);
  82     return I;
  83   }
  84
  85   /// AddUsersToWorkList - When an instruction is simplified, add all users of
  86   /// the instruction to the work lists because they might get more simplified
  87   /// now.
  88   ///
  89   void AddUsersToWorkList(Instruction &I) {
  90     for (User *U : I.users())
  91       Add(cast<Instruction>(U));
  92   }
  93
  94
  95   /// Zap - check that the worklist is empty and nuke the backing store for
  96   /// the map if it is large.
  97   void Zap() {
  98     assert(WorklistMap.empty() && "Worklist empty, but map not?");
  99
 100     // Do an explicit clear, this shrinks the map if needed.
 101     WorklistMap.clear();
 102   }
 103 };
 104
 105 } // end namespace llvm.
 106
 107 #undef DEBUG_TYPE
 108
 109 #endif