Subversion Repositories QNX 8.QNX8 LLVM/Clang compiler suite

Rev

Blame | Last modification | View Log | Download | RSS feed

  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
  124.