LLVM API Documentation

LazyLiveness.h

Go to the documentation of this file.
00001 //===- LazyLiveness.h - Lazy, CFG-invariant liveness information ----------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // This pass implements a lazy liveness analysis as per "Fast Liveness Checking
00011 // for SSA-form Programs," by Boissinot, et al.
00012 //
00013 //===----------------------------------------------------------------------===//
00014 
00015 #ifndef LLVM_CODEGEN_LAZYLIVENESS_H
00016 #define LLVM_CODEGEN_LAZYLIVENESS_H
00017 
00018 #include "llvm/CodeGen/MachineFunctionPass.h"
00019 #include "llvm/CodeGen/MachineDominators.h"
00020 #include "llvm/ADT/DenseMap.h"
00021 #include "llvm/ADT/DenseSet.h"
00022 #include "llvm/ADT/SparseBitVector.h"
00023 #include <vector>
00024 
00025 namespace llvm {
00026 
00027 class MachineRegisterInfo;
00028 
00029 class LazyLiveness : public MachineFunctionPass {
00030 public:
00031   static char ID; // Pass identification, replacement for typeid
00032   LazyLiveness() : MachineFunctionPass(&ID) { }
00033   
00034   void getAnalysisUsage(AnalysisUsage &AU) const {
00035     AU.setPreservesAll();
00036     AU.addRequired<MachineDominatorTree>();
00037     MachineFunctionPass::getAnalysisUsage(AU);
00038   }
00039   
00040   bool runOnMachineFunction(MachineFunction &mf);
00041 
00042   bool vregLiveIntoMBB(unsigned vreg, MachineBasicBlock* MBB);
00043   
00044 private:
00045   void computeBackedgeChain(MachineFunction& mf, MachineBasicBlock* MBB);
00046   
00047   typedef std::pair<MachineBasicBlock*, MachineBasicBlock*> edge_t;
00048   
00049   MachineRegisterInfo* MRI;
00050   
00051   DenseMap<MachineBasicBlock*, unsigned> preorder;
00052   std::vector<MachineBasicBlock*> rev_preorder;
00053   DenseMap<MachineBasicBlock*, SparseBitVector<128> > rv;
00054   DenseMap<MachineBasicBlock*, SparseBitVector<128> > tv;
00055   DenseSet<edge_t> backedges;
00056   SparseBitVector<128> backedge_source;
00057   SparseBitVector<128> backedge_target;
00058   SparseBitVector<128> calculated;
00059 };
00060 
00061 }
00062 
00063 #endif
00064