include/llvm/CodeGen/FunctionLiveVarInfo.h

   1 /* Title:   FunctionLiveVarInfo.h             -*- C++ -*-
   2    Author:  Ruchira Sasanka
   3    Date:    Jun 30, 01
   4    Purpose:
   5
   6    This is the interface for live variable info of a function that is required
   7    by any other part of the compiler
   8
   9    It must be called like:
  10
  11        FunctionLiveVarInfo FLVI(Function *);  // initializes data structures
  12        FLVI.analyze();                     // do the actural live variable anal
  13
  14  After the analysis, getInSetOfBB or getOutSetofBB can be called to get
  15  live var info of a BB.
  16
  17  The live var set before an instruction can be obtained in 2 ways:
  18
  19  1. Use the method getLiveVarSetAfterInst(Instruction *) to get the LV Info
  20     just after an instruction. (also exists getLiveVarSetBeforeInst(..))
  21
  22     This function caluclates the LV info for a BB only once and caches that
  23     info. If the cache does not contain the LV info of the instruction, it
  24     calculates the LV info for the whole BB and caches them.
  25
  26     Getting liveVar info this way uses more memory since, LV info should be
  27     cached. However, if you need LV info of nearly all the instructions of a
  28     BB, this is the best and simplest interfrace.
  29
  30
  31  2. Use the OutSet and applyTranferFuncForInst(const Instruction *const Inst)
  32     declared in LiveVarSet and  traverse the instructions of a basic block in
  33     reverse (using const_reverse_iterator in the BB class).
  34
  35     This is the most memory efficient method if you need LV info for
  36     only several instructions in a BasicBlock. An example is given below:
  37
  38
  39     LiveVarSet LVSet;  // this will be the set used to traverse through each BB
  40
  41     // Initialize LVSet so that it is the same as OutSet of the BB
  42     LVSet.setUnion( LVI->getOutSetOfBB( *BBI ) );
  43
  44     BasicBlock::InstListType::const_reverse_iterator
  45       InstIterator = InstListInBB.rbegin(); // get the rev iter for inst in BB
  46
  47       // iterate over all the instructions in BB in reverse
  48     for( ; InstIterator != InstListInBB.rend(); InstIterator++) {
  49
  50       //...... all  code here which uses LVSet ........
  51
  52       LVSet.applyTranferFuncForInst(*InstIterator);
  53
  54       // Now LVSet contains live vars ABOVE the current instrution
  55     }
  56
  57     See buildInterferenceGraph() for the above example.
  58 */
  59
  60
  61 #ifndef FUNCTION_LIVE_VAR_INFO_H
  62 #define FUNCTION_LIVE_VAR_INFO_H
  63
  64 #include "Support/hash_map"
  65 #include "llvm/Pass.h"
  66 #include "llvm/CodeGen/ValueSet.h"
  67
  68 class BBLiveVar;
  69 class MachineInstr;
  70
  71 class FunctionLiveVarInfo : public FunctionPass {
  72   // Machine Instr to LiveVarSet Map for providing LVset BEFORE each inst
  73   // These sets are owned by this map and will be freed in releaseMemory().
  74   hash_map<const MachineInstr *, ValueSet *> MInst2LVSetBI;
  75
  76   // Machine Instr to LiveVarSet Map for providing LVset AFTER each inst.
  77   // These sets are just pointers to sets in MInst2LVSetBI or BBLiveVar.
  78   hash_map<const MachineInstr *, ValueSet *> MInst2LVSetAI;
  79
  80   // Stored Function that the data is computed with respect to
  81   const Function *M;
  82
  83   // --------- private methods -----------------------------------------
  84
  85   // constructs BBLiveVars and init Def and In sets
  86   void constructBBs(const Function *F);
  87
  88   // do one backward pass over the CFG
  89   bool doSingleBackwardPass(const Function *F, unsigned int iter);
  90
  91   // calculates live var sets for instructions in a BB
  92   void calcLiveVarSetsForBB(const BasicBlock *BB);
  93
  94 public:
  95   // --------- Implement the FunctionPass interface ----------------------
  96
  97   // runOnFunction - Perform analysis, update internal data structures.
  98   virtual bool runOnFunction(Function &F);
  99
 100   // releaseMemory - After LiveVariable analysis has been used, forget!
 101   virtual void releaseMemory();
 102
 103   // getAnalysisUsage - Provide self!
 104   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 105     AU.setPreservesAll();
 106   }
 107
 108   // --------- Functions to access analysis results -------------------
 109
 110   // get OutSet of a BB
 111   const ValueSet &getOutSetOfBB(const BasicBlock *BB) const;
 112         ValueSet &getOutSetOfBB(const BasicBlock *BB)      ;
 113
 114   // get InSet of a BB
 115   const ValueSet &getInSetOfBB(const BasicBlock *BB) const;
 116         ValueSet &getInSetOfBB(const BasicBlock *BB)      ;
 117
 118   // gets the Live var set BEFORE an instruction.
 119   // if BB is specified and the live var set has not yet been computed,
 120   // it will be computed on demand.
 121   const ValueSet &getLiveVarSetBeforeMInst(const MachineInstr *MI,
 122                                            const BasicBlock *BB = 0);
 123
 124   // gets the Live var set AFTER an instruction
 125   // if BB is specified and the live var set has not yet been computed,
 126   // it will be computed on demand.
 127   const ValueSet &getLiveVarSetAfterMInst(const MachineInstr *MI,
 128                                           const BasicBlock *BB = 0);
 129 };
 130
 131 #endif