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     MachineFunctionPass::getAnalysisUsage(AU);
  38   }
  39
  40   bool runOnMachineFunction(MachineFunction &mf);
  41
  42   bool vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB);
  43
  44 private:
  45   void computeBackedgeChain(MachineFunction& mf, MachineBasicBlock* MBB);
  46
  47   typedef std::pair<MachineBasicBlock*, MachineBasicBlock*> edge_t;
  48
  49   MachineRegisterInfo* MRI;
  50
  51   DenseMap<MachineBasicBlock*, unsigned> preorder;
  52   std::vector<MachineBasicBlock*> rev_preorder;
  53   DenseMap<MachineBasicBlock*, SparseBitVector<128> > rv;
  54   DenseMap<MachineBasicBlock*, SparseBitVector<128> > tv;
  55   DenseSet<edge_t> backedges;
  56   SparseBitVector<128> backedge_source;
  57   SparseBitVector<128> backedge_target;
  58   SparseBitVector<128> calculated;
  59 };
  60
  61 }
  62
  63 #endif
  64