Chris Lattner | 4e8c487 | 2002-03-23 22:51:58 +0000 | [diff] [blame] | 1 | //===-- LiveRangeInfo.h - Track all LiveRanges for a Function ----*- C++ -*-==// |
Chris Lattner | b0da8b2 | 2002-02-04 05:52:08 +0000 | [diff] [blame] | 2 | // |
| 3 | // This file contains the class LiveRangeInfo which constructs and keeps |
| 4 | // the LiveRangMap which contains all the live ranges used in a method. |
| 5 | // |
| 6 | // Assumptions: |
| 7 | // |
| 8 | // All variables (llvm Values) are defined before they are used. However, a |
| 9 | // constant may not be defined in the machine instruction stream if it can be |
| 10 | // used as an immediate value within a machine instruction. However, register |
| 11 | // allocation does not have to worry about immediate constants since they |
| 12 | // do not require registers. |
| 13 | // |
| 14 | // Since an llvm Value has a list of uses associated, it is sufficient to |
| 15 | // record only the defs in a Live Range. |
| 16 | // |
| 17 | //===----------------------------------------------------------------------===// |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 18 | |
| 19 | #ifndef LIVE_RANGE_INFO_H |
| 20 | #define LIVE_RANGE_INFO_H |
| 21 | |
Chris Lattner | de1d729 | 2003-01-14 22:56:37 +0000 | [diff] [blame] | 22 | #include "llvm/CodeGen/ValueSet.h" |
Chris Lattner | 981e585 | 2003-07-26 23:00:29 +0000 | [diff] [blame] | 23 | #include "Support/hash_map" |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 24 | |
Chris Lattner | b0da8b2 | 2002-02-04 05:52:08 +0000 | [diff] [blame] | 25 | class LiveRange; |
| 26 | class MachineInstr; |
Chris Lattner | b0da8b2 | 2002-02-04 05:52:08 +0000 | [diff] [blame] | 27 | class RegClass; |
Chris Lattner | f9781b5 | 2002-12-29 03:13:05 +0000 | [diff] [blame] | 28 | class TargetRegInfo; |
Chris Lattner | b0da8b2 | 2002-02-04 05:52:08 +0000 | [diff] [blame] | 29 | class TargetMachine; |
| 30 | class Value; |
Chris Lattner | 4e8c487 | 2002-03-23 22:51:58 +0000 | [diff] [blame] | 31 | class Function; |
Chris Lattner | b0da8b2 | 2002-02-04 05:52:08 +0000 | [diff] [blame] | 32 | class Instruction; |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 33 | |
Chris Lattner | e583333 | 2002-07-24 21:21:33 +0000 | [diff] [blame] | 34 | typedef hash_map<const Value*, LiveRange*> LiveRangeMapType; |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 35 | |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 36 | //---------------------------------------------------------------------------- |
| 37 | // Class LiveRangeInfo |
| 38 | // |
| 39 | // Constructs and keeps the LiveRangMap which contains all the live |
| 40 | // ranges used in a method. Also contain methods to coalesce live ranges. |
| 41 | //---------------------------------------------------------------------------- |
| 42 | |
Chris Lattner | b0da8b2 | 2002-02-04 05:52:08 +0000 | [diff] [blame] | 43 | class LiveRangeInfo { |
Chris Lattner | 4e8c487 | 2002-03-23 22:51:58 +0000 | [diff] [blame] | 44 | const Function *const Meth; // Func for which live range info is held |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 45 | LiveRangeMapType LiveRangeMap; // A map from Value * to LiveRange * to |
| 46 | // record all live ranges in a method |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 47 | // created by constructLiveRanges |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 48 | |
Ruchira Sasanka | f60342a | 2001-09-15 00:33:26 +0000 | [diff] [blame] | 49 | const TargetMachine& TM; // target machine description |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 50 | |
Chris Lattner | 7f74a56 | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 51 | std::vector<RegClass *> & RegClassList;// vector containing register classess |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 52 | |
Chris Lattner | f9781b5 | 2002-12-29 03:13:05 +0000 | [diff] [blame] | 53 | const TargetRegInfo& MRI; // machine reg info |
Ruchira Sasanka | f60342a | 2001-09-15 00:33:26 +0000 | [diff] [blame] | 54 | |
Chris Lattner | 6d6d87f | 2002-10-29 17:03:19 +0000 | [diff] [blame] | 55 | std::vector<MachineInstr*> CallRetInstrList; // a list of all call/ret instrs |
Ruchira Sasanka | f60342a | 2001-09-15 00:33:26 +0000 | [diff] [blame] | 56 | |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 57 | |
| 58 | //------------ Private methods (see LiveRangeInfo.cpp for description)------- |
| 59 | |
Vikram S. Adve | 9011903 | 2002-09-28 17:05:43 +0000 | [diff] [blame] | 60 | LiveRange* createNewLiveRange (const Value* Def, |
| 61 | bool isCC = false); |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 62 | |
Vikram S. Adve | 9011903 | 2002-09-28 17:05:43 +0000 | [diff] [blame] | 63 | LiveRange* createOrAddToLiveRange (const Value* Def, |
| 64 | bool isCC = false); |
| 65 | |
| 66 | void unionAndUpdateLRs (LiveRange *L1, |
| 67 | LiveRange *L2); |
| 68 | |
| 69 | void addInterference (const Instruction *Inst, |
| 70 | const ValueSet *LVSet); |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 71 | |
Vikram S. Adve | 9011903 | 2002-09-28 17:05:43 +0000 | [diff] [blame] | 72 | void suggestRegs4CallRets (); |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 73 | |
Vikram S. Adve | 9011903 | 2002-09-28 17:05:43 +0000 | [diff] [blame] | 74 | const Function *getMethod () const { return Meth; } |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 75 | |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 76 | public: |
| 77 | |
Chris Lattner | 4e8c487 | 2002-03-23 22:51:58 +0000 | [diff] [blame] | 78 | LiveRangeInfo(const Function *F, |
Ruchira Sasanka | f60342a | 2001-09-15 00:33:26 +0000 | [diff] [blame] | 79 | const TargetMachine& tm, |
Chris Lattner | 7f74a56 | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 80 | std::vector<RegClass *> & RCList); |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 81 | |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 82 | |
| 83 | // Destructor to destroy all LiveRanges in the LiveRange Map |
| 84 | ~LiveRangeInfo(); |
| 85 | |
| 86 | // Main entry point for live range construction |
| 87 | // |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 88 | void constructLiveRanges(); |
Ruchira Sasanka | 560b0ad | 2001-09-30 23:19:57 +0000 | [diff] [blame] | 89 | |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 90 | // return the common live range map for this method |
| 91 | // |
Chris Lattner | 6d6d87f | 2002-10-29 17:03:19 +0000 | [diff] [blame] | 92 | inline const LiveRangeMapType *getLiveRangeMap() const |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 93 | { return &LiveRangeMap; } |
| 94 | |
Vikram S. Adve | e2ef34a | 2003-07-29 19:38:22 +0000 | [diff] [blame] | 95 | // Method used to get the live range containing a Value. |
| 96 | // This may return NULL if no live range exists for a Value (eg, some consts) |
| 97 | inline LiveRange *getLiveRangeForValue(const Value *Val) { |
| 98 | return LiveRangeMap[Val]; |
| 99 | } |
| 100 | inline const LiveRange *getLiveRangeForValue(const Value *Val) const { |
| 101 | LiveRangeMapType::const_iterator I = LiveRangeMap.find(Val); |
| 102 | return I->second; |
| 103 | } |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 104 | |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 105 | // Method for coalescing live ranges. Called only after interference info |
| 106 | // is calculated. |
| 107 | // |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 108 | void coalesceLRs(); |
| 109 | |
Ruchira Sasanka | f20079d | 2002-01-07 19:16:26 +0000 | [diff] [blame] | 110 | // debugging method to print the live ranges |
| 111 | // |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 112 | void printLiveRanges(); |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 113 | }; |
| 114 | |
Ruchira Sasanka | e5d0fb8 | 2001-09-08 14:10:34 +0000 | [diff] [blame] | 115 | #endif |