LLVM API Documentation
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