include/llvm/CodeGen/LazyLiveness.h

   1 //===- LazyLiveness.h - Lazy, CFG-invariant liveness information ----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This pass implements a lazy liveness analysis as per "Fast Liveness Checking
  11 // for SSA-form Programs," by Boissinot, et al.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #ifndef LLVM_CODEGEN_LAZYLIVENESS_H
  16 #define LLVM_CODEGEN_LAZYLIVENESS_H
  17
  18 #include "llvm/CodeGen/MachineFunctionPass.h"
  19 #include "llvm/CodeGen/MachineDominators.h"
  20 #include "llvm/ADT/DenseMap.h"
  21 #include "llvm/ADT/DenseSet.h"
  22 #include "llvm/ADT/SparseBitVector.h"
  23 #include <vector>
  24
  25 namespace llvm {
  26
  27 class MachineRegisterInfo;
  28
  29 class LazyLiveness : public MachineFunctionPass {
  30 public:
  31   static char ID; // Pass identification, replacement for typeid
  32   LazyLiveness() : MachineFunctionPass(&ID) { }
  33
  34   void getAnalysisUsage(AnalysisUsage &AU) const {
  35     AU.setPreservesAll();
  36     AU.addRequired<MachineDominatorTree>();
  37   }
  38
  39   bool runOnMachineFunction(MachineFunction &mf);
  40
  41   bool vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB);
  42
  43 private:
  44   void computeBackedgeChain(MachineFunction& mf, MachineBasicBlock* MBB);
  45
  46   typedef std::pair<MachineBasicBlock*, MachineBasicBlock*> edge_t;
  47
  48   MachineRegisterInfo* MRI;
  49
  50   DenseMap<MachineBasicBlock*, unsigned> preorder;
  51   std::vector<MachineBasicBlock*> rev_preorder;
  52   DenseMap<MachineBasicBlock*, SparseBitVector<128> > rv;
  53   DenseMap<MachineBasicBlock*, SparseBitVector<128> > tv;
  54   DenseSet<edge_t> backedges;
  55   SparseBitVector<128> backedge_source;
  56   SparseBitVector<128> backedge_target;
  57   SparseBitVector<128> calculated;
  58 };
  59
  60 }
  61
  62 #endif
  63