Vikram S. Adve | 39c94e1 | 2002-09-14 23:05:33 +0000 | [diff] [blame] | 1 | //===-- LiveRangeInfo.cpp -------------------------------------------------===// |
| 2 | // |
John Criswell | b576c94 | 2003-10-20 19:43:21 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| 4 | // |
| 5 | // This file was developed by the LLVM research group and is distributed under |
| 6 | // the University of Illinois Open Source License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | // |
Vikram S. Adve | 39c94e1 | 2002-09-14 23:05:33 +0000 | [diff] [blame] | 10 | // Live range construction for coloring-based register allocation for LLVM. |
| 11 | // |
| 12 | //===----------------------------------------------------------------------===// |
| 13 | |
Misha Brukman | 0d82a54 | 2003-10-23 18:03:50 +0000 | [diff] [blame] | 14 | #include "IGNode.h" |
Chris Lattner | 893f954 | 2003-09-01 20:12:17 +0000 | [diff] [blame] | 15 | #include "LiveRangeInfo.h" |
Chris Lattner | 4309e73 | 2003-01-15 19:57:07 +0000 | [diff] [blame] | 16 | #include "RegAllocCommon.h" |
Chris Lattner | 9d4ed15 | 2003-01-15 21:14:01 +0000 | [diff] [blame] | 17 | #include "RegClass.h" |
Misha Brukman | 0d82a54 | 2003-10-23 18:03:50 +0000 | [diff] [blame] | 18 | #include "llvm/Function.h" |
Chris Lattner | 0a8ed94 | 2002-02-04 05:56:09 +0000 | [diff] [blame] | 19 | #include "llvm/CodeGen/MachineInstr.h" |
Chris Lattner | f726e77 | 2002-10-28 19:22:04 +0000 | [diff] [blame] | 20 | #include "llvm/CodeGen/MachineFunction.h" |
Chris Lattner | 0a8ed94 | 2002-02-04 05:56:09 +0000 | [diff] [blame] | 21 | #include "llvm/Target/TargetMachine.h" |
Chris Lattner | 3501fea | 2003-01-14 22:00:31 +0000 | [diff] [blame] | 22 | #include "llvm/Target/TargetInstrInfo.h" |
Brian Gaeke | 3b2e5e6 | 2004-04-23 18:15:47 +0000 | [diff] [blame] | 23 | #include "../SparcV9RegInfo.h" |
Reid Spencer | 551ccae | 2004-09-01 22:55:40 +0000 | [diff] [blame] | 24 | #include "llvm/ADT/SetOperations.h" |
Reid Spencer | 954da37 | 2004-07-04 12:19:56 +0000 | [diff] [blame] | 25 | #include <iostream> |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 26 | |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 27 | namespace llvm { |
| 28 | |
Chris Lattner | 9d4ed15 | 2003-01-15 21:14:01 +0000 | [diff] [blame] | 29 | unsigned LiveRange::getRegClassID() const { return getRegClass()->getID(); } |
| 30 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 31 | LiveRangeInfo::LiveRangeInfo(const Function *F, const TargetMachine &tm, |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 32 | std::vector<RegClass *> &RCL) |
Chris Lattner | d029cd2 | 2004-06-02 05:55:25 +0000 | [diff] [blame] | 33 | : Meth(F), TM(tm), RegClassList(RCL), MRI(*tm.getRegInfo()) { } |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 34 | |
| 35 | |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 36 | LiveRangeInfo::~LiveRangeInfo() { |
Chris Lattner | 2f898d2 | 2002-02-05 06:02:59 +0000 | [diff] [blame] | 37 | for (LiveRangeMapType::iterator MI = LiveRangeMap.begin(); |
| 38 | MI != LiveRangeMap.end(); ++MI) { |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 39 | |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 40 | if (MI->first && MI->second) { |
| 41 | LiveRange *LR = MI->second; |
| 42 | |
| 43 | // we need to be careful in deleting LiveRanges in LiveRangeMap |
| 44 | // since two/more Values in the live range map can point to the same |
| 45 | // live range. We have to make the other entries NULL when we delete |
| 46 | // a live range. |
| 47 | |
Chris Lattner | cb6b4bd | 2002-10-29 16:51:05 +0000 | [diff] [blame] | 48 | for (LiveRange::iterator LI = LR->begin(); LI != LR->end(); ++LI) |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 49 | LiveRangeMap[*LI] = 0; |
| 50 | |
| 51 | delete LR; |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 52 | } |
| 53 | } |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 54 | } |
| 55 | |
| 56 | |
| 57 | //--------------------------------------------------------------------------- |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 58 | // union two live ranges into one. The 2nd LR is deleted. Used for coalescing. |
Ruchira Sasanka | a5ab964 | 2001-09-30 23:11:59 +0000 | [diff] [blame] | 59 | // Note: the caller must make sure that L1 and L2 are distinct and both |
| 60 | // LRs don't have suggested colors |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 61 | //--------------------------------------------------------------------------- |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 62 | |
Chris Lattner | 296b773 | 2002-02-05 02:52:05 +0000 | [diff] [blame] | 63 | void LiveRangeInfo::unionAndUpdateLRs(LiveRange *L1, LiveRange *L2) { |
| 64 | assert(L1 != L2 && (!L1->hasSuggestedColor() || !L2->hasSuggestedColor())); |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 65 | assert(! (L1->hasColor() && L2->hasColor()) || |
| 66 | L1->getColor() == L2->getColor()); |
| 67 | |
Brian Gaeke | db7c40d | 2004-07-29 06:43:08 +0000 | [diff] [blame] | 68 | L2->insert (L1->begin(), L1->end()); // add elements of L2 to L1 |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 69 | |
Brian Gaeke | db7c40d | 2004-07-29 06:43:08 +0000 | [diff] [blame] | 70 | for(LiveRange::iterator L2It = L2->begin(); L2It != L2->end(); ++L2It) { |
Chris Lattner | 30adeb6 | 2002-02-04 16:36:59 +0000 | [diff] [blame] | 71 | L1->insert(*L2It); // add the var in L2 to L1 |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 72 | LiveRangeMap[*L2It] = L1; // now the elements in L2 should map |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 73 | //to L1 |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 74 | } |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 75 | |
| 76 | // set call interference for L1 from L2 |
Chris Lattner | 296b773 | 2002-02-05 02:52:05 +0000 | [diff] [blame] | 77 | if (L2->isCallInterference()) |
Ruchira Sasanka | 958faf3 | 2001-10-19 17:21:03 +0000 | [diff] [blame] | 78 | L1->setCallInterference(); |
| 79 | |
Chris Lattner | 296b773 | 2002-02-05 02:52:05 +0000 | [diff] [blame] | 80 | // add the spill costs |
| 81 | L1->addSpillCost(L2->getSpillCost()); |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 82 | |
| 83 | // If L2 has a color, give L1 that color. Note that L1 may have had the same |
| 84 | // color or none, but would not have a different color as asserted above. |
| 85 | if (L2->hasColor()) |
| 86 | L1->setColor(L2->getColor()); |
| 87 | |
| 88 | // Similarly, if LROfUse(L2) has a suggested color, the new range |
| 89 | // must have the same color. |
| 90 | if (L2->hasSuggestedColor()) |
| 91 | L1->setSuggestedColor(L2->getSuggestedColor()); |
Chris Lattner | 296b773 | 2002-02-05 02:52:05 +0000 | [diff] [blame] | 92 | |
Chris Lattner | 697954c | 2002-01-20 22:54:45 +0000 | [diff] [blame] | 93 | delete L2; // delete L2 as it is no longer needed |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 94 | } |
| 95 | |
| 96 | |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 97 | //--------------------------------------------------------------------------- |
| 98 | // Method for creating a single live range for a definition. |
| 99 | // The definition must be represented by a virtual register (a Value). |
| 100 | // Note: this function does *not* check that no live range exists for def. |
| 101 | //--------------------------------------------------------------------------- |
| 102 | |
| 103 | LiveRange* |
| 104 | LiveRangeInfo::createNewLiveRange(const Value* Def, bool isCC /* = false*/) |
| 105 | { |
| 106 | LiveRange* DefRange = new LiveRange(); // Create a new live range, |
| 107 | DefRange->insert(Def); // add Def to it, |
| 108 | LiveRangeMap[Def] = DefRange; // and update the map. |
| 109 | |
| 110 | // set the register class of the new live range |
Chris Lattner | 9d4ed15 | 2003-01-15 21:14:01 +0000 | [diff] [blame] | 111 | DefRange->setRegClass(RegClassList[MRI.getRegClassIDOfType(Def->getType(), |
| 112 | isCC)]); |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 113 | |
| 114 | if (DEBUG_RA >= RA_DEBUG_LiveRanges) { |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 115 | std::cerr << " Creating a LR for def "; |
| 116 | if (isCC) std::cerr << " (CC Register!)"; |
| 117 | std::cerr << " : " << RAV(Def) << "\n"; |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 118 | } |
| 119 | return DefRange; |
| 120 | } |
| 121 | |
| 122 | |
| 123 | LiveRange* |
| 124 | LiveRangeInfo::createOrAddToLiveRange(const Value* Def, bool isCC /* = false*/) |
| 125 | { |
| 126 | LiveRange *DefRange = LiveRangeMap[Def]; |
| 127 | |
| 128 | // check if the LR is already there (because of multiple defs) |
| 129 | if (!DefRange) { |
Chris Lattner | 133f079 | 2002-10-28 04:45:29 +0000 | [diff] [blame] | 130 | DefRange = createNewLiveRange(Def, isCC); |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 131 | } else { // live range already exists |
| 132 | DefRange->insert(Def); // add the operand to the range |
| 133 | LiveRangeMap[Def] = DefRange; // make operand point to merged set |
| 134 | if (DEBUG_RA >= RA_DEBUG_LiveRanges) |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 135 | std::cerr << " Added to existing LR for def: " << RAV(Def) << "\n"; |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 136 | } |
| 137 | return DefRange; |
| 138 | } |
| 139 | |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 140 | |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 141 | //--------------------------------------------------------------------------- |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 142 | // Method for constructing all live ranges in a function. It creates live |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 143 | // ranges for all values defined in the instruction stream. Also, it |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 144 | // creates live ranges for all incoming arguments of the function. |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 145 | //--------------------------------------------------------------------------- |
Chris Lattner | 2f898d2 | 2002-02-05 06:02:59 +0000 | [diff] [blame] | 146 | void LiveRangeInfo::constructLiveRanges() { |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 147 | |
Vikram S. Adve | 39c94e1 | 2002-09-14 23:05:33 +0000 | [diff] [blame] | 148 | if (DEBUG_RA >= RA_DEBUG_LiveRanges) |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 149 | std::cerr << "Constructing Live Ranges ...\n"; |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 150 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 151 | // first find the live ranges for all incoming args of the function since |
| 152 | // those LRs start from the start of the function |
Chris Lattner | e4d5c44 | 2005-03-15 04:54:21 +0000 | [diff] [blame^] | 153 | for (Function::const_arg_iterator AI = Meth->arg_begin(); AI != Meth->arg_end(); ++AI) |
Chris Lattner | 133f079 | 2002-10-28 04:45:29 +0000 | [diff] [blame] | 154 | createNewLiveRange(AI, /*isCC*/ false); |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 155 | |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 156 | // Now suggest hardware registers for these function args |
Ruchira Sasanka | a5ab964 | 2001-09-30 23:11:59 +0000 | [diff] [blame] | 157 | MRI.suggestRegs4MethodArgs(Meth, *this); |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 158 | |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 159 | // Now create LRs for machine instructions. A new LR will be created |
| 160 | // only for defs in the machine instr since, we assume that all Values are |
| 161 | // defined before they are used. However, there can be multiple defs for |
| 162 | // the same Value in machine instructions. |
| 163 | // |
| 164 | // Also, find CALL and RETURN instructions, which need extra work. |
Chris Lattner | 2f898d2 | 2002-02-05 06:02:59 +0000 | [diff] [blame] | 165 | // |
Chris Lattner | f726e77 | 2002-10-28 19:22:04 +0000 | [diff] [blame] | 166 | MachineFunction &MF = MachineFunction::get(Meth); |
| 167 | for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) { |
| 168 | MachineBasicBlock &MBB = *BBI; |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 169 | |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 170 | // iterate over all the machine instructions in BB |
Chris Lattner | f726e77 | 2002-10-28 19:22:04 +0000 | [diff] [blame] | 171 | for(MachineBasicBlock::iterator MInstIterator = MBB.begin(); |
| 172 | MInstIterator != MBB.end(); ++MInstIterator) { |
Alkis Evlogimenos | c0b9dc5 | 2004-02-12 02:27:10 +0000 | [diff] [blame] | 173 | MachineInstr *MInst = MInstIterator; |
Ruchira Sasanka | a5ab964 | 2001-09-30 23:11:59 +0000 | [diff] [blame] | 174 | |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 175 | // If the machine instruction is a call/return instruction, add it to |
| 176 | // CallRetInstrList for processing its args, ret value, and ret addr. |
| 177 | // |
Chris Lattner | d029cd2 | 2004-06-02 05:55:25 +0000 | [diff] [blame] | 178 | if(TM.getInstrInfo()->isReturn(MInst->getOpcode()) || |
| 179 | TM.getInstrInfo()->isCall(MInst->getOpcode())) |
Chris Lattner | 133f079 | 2002-10-28 04:45:29 +0000 | [diff] [blame] | 180 | CallRetInstrList.push_back(MInst); |
Ruchira Sasanka | a90e770 | 2001-10-15 16:26:38 +0000 | [diff] [blame] | 181 | |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 182 | // iterate over explicit MI operands and create a new LR |
| 183 | // for each operand that is defined by the instruction |
Vikram S. Adve | c9a0ca5 | 2002-07-08 23:07:26 +0000 | [diff] [blame] | 184 | for (MachineInstr::val_op_iterator OpI = MInst->begin(), |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 185 | OpE = MInst->end(); OpI != OpE; ++OpI) |
Alkis Evlogimenos | 4d7af65 | 2003-12-14 13:24:17 +0000 | [diff] [blame] | 186 | if (OpI.isDef()) { |
Chris Lattner | 30adeb6 | 2002-02-04 16:36:59 +0000 | [diff] [blame] | 187 | const Value *Def = *OpI; |
Chris Lattner | 133f079 | 2002-10-28 04:45:29 +0000 | [diff] [blame] | 188 | bool isCC = (OpI.getMachineOperand().getType() |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 189 | == MachineOperand::MO_CCRegister); |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 190 | LiveRange* LR = createOrAddToLiveRange(Def, isCC); |
| 191 | |
| 192 | // If the operand has a pre-assigned register, |
| 193 | // set it directly in the LiveRange |
| 194 | if (OpI.getMachineOperand().hasAllocatedReg()) { |
| 195 | unsigned getClassId; |
Alkis Evlogimenos | be766c7 | 2004-02-13 21:01:20 +0000 | [diff] [blame] | 196 | LR->setColor(MRI.getClassRegNum(OpI.getMachineOperand().getReg(), |
| 197 | getClassId)); |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 198 | } |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 199 | } |
Ruchira Sasanka | a5ab964 | 2001-09-30 23:11:59 +0000 | [diff] [blame] | 200 | |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 201 | // iterate over implicit MI operands and create a new LR |
| 202 | // for each operand that is defined by the instruction |
| 203 | for (unsigned i = 0; i < MInst->getNumImplicitRefs(); ++i) |
Alkis Evlogimenos | 4d7af65 | 2003-12-14 13:24:17 +0000 | [diff] [blame] | 204 | if (MInst->getImplicitOp(i).isDef()) { |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 205 | const Value *Def = MInst->getImplicitRef(i); |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 206 | LiveRange* LR = createOrAddToLiveRange(Def, /*isCC*/ false); |
| 207 | |
| 208 | // If the implicit operand has a pre-assigned register, |
| 209 | // set it directly in the LiveRange |
| 210 | if (MInst->getImplicitOp(i).hasAllocatedReg()) { |
| 211 | unsigned getClassId; |
| 212 | LR->setColor(MRI.getClassRegNum( |
Alkis Evlogimenos | be766c7 | 2004-02-13 21:01:20 +0000 | [diff] [blame] | 213 | MInst->getImplicitOp(i).getReg(), |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 214 | getClassId)); |
| 215 | } |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 216 | } |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 217 | |
| 218 | } // for all machine instructions in the BB |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 219 | } // for all BBs in function |
Ruchira Sasanka | a5ab964 | 2001-09-30 23:11:59 +0000 | [diff] [blame] | 220 | |
Ruchira Sasanka | a90e770 | 2001-10-15 16:26:38 +0000 | [diff] [blame] | 221 | // Now we have to suggest clors for call and return arg live ranges. |
| 222 | // Also, if there are implicit defs (e.g., retun value of a call inst) |
| 223 | // they must be added to the live range list |
Vikram S. Adve | 9d67cd1 | 2002-09-28 17:05:22 +0000 | [diff] [blame] | 224 | // |
Ruchira Sasanka | a90e770 | 2001-10-15 16:26:38 +0000 | [diff] [blame] | 225 | suggestRegs4CallRets(); |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 226 | |
Vikram S. Adve | 39c94e1 | 2002-09-14 23:05:33 +0000 | [diff] [blame] | 227 | if( DEBUG_RA >= RA_DEBUG_LiveRanges) |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 228 | std::cerr << "Initial Live Ranges constructed!\n"; |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 229 | } |
| 230 | |
| 231 | |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 232 | //--------------------------------------------------------------------------- |
| 233 | // If some live ranges must be colored with specific hardware registers |
| 234 | // (e.g., for outgoing call args), suggesting of colors for such live |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 235 | // ranges is done using target specific function. Those functions are called |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 236 | // from this function. The target specific methods must: |
| 237 | // 1) suggest colors for call and return args. |
| 238 | // 2) create new LRs for implicit defs in machine instructions |
| 239 | //--------------------------------------------------------------------------- |
Chris Lattner | 88da77c | 2002-10-29 17:03:19 +0000 | [diff] [blame] | 240 | void LiveRangeInfo::suggestRegs4CallRets() { |
| 241 | std::vector<MachineInstr*>::iterator It = CallRetInstrList.begin(); |
| 242 | for( ; It != CallRetInstrList.end(); ++It) { |
Vikram S. Adve | c9a0ca5 | 2002-07-08 23:07:26 +0000 | [diff] [blame] | 243 | MachineInstr *MInst = *It; |
Brian Gaeke | 12c1d2c | 2004-02-11 20:47:34 +0000 | [diff] [blame] | 244 | MachineOpCode OpCode = MInst->getOpcode(); |
Ruchira Sasanka | a90e770 | 2001-10-15 16:26:38 +0000 | [diff] [blame] | 245 | |
Chris Lattner | d029cd2 | 2004-06-02 05:55:25 +0000 | [diff] [blame] | 246 | if (TM.getInstrInfo()->isReturn(OpCode)) |
Chris Lattner | 88da77c | 2002-10-29 17:03:19 +0000 | [diff] [blame] | 247 | MRI.suggestReg4RetValue(MInst, *this); |
Chris Lattner | d029cd2 | 2004-06-02 05:55:25 +0000 | [diff] [blame] | 248 | else if (TM.getInstrInfo()->isCall(OpCode)) |
Chris Lattner | 88da77c | 2002-10-29 17:03:19 +0000 | [diff] [blame] | 249 | MRI.suggestRegs4CallArgs(MInst, *this); |
Ruchira Sasanka | a90e770 | 2001-10-15 16:26:38 +0000 | [diff] [blame] | 250 | else |
Chris Lattner | 88da77c | 2002-10-29 17:03:19 +0000 | [diff] [blame] | 251 | assert( 0 && "Non call/ret instr in CallRetInstrList" ); |
Ruchira Sasanka | a90e770 | 2001-10-15 16:26:38 +0000 | [diff] [blame] | 252 | } |
Ruchira Sasanka | a90e770 | 2001-10-15 16:26:38 +0000 | [diff] [blame] | 253 | } |
| 254 | |
| 255 | |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 256 | //-------------------------------------------------------------------------- |
| 257 | // The following method coalesces live ranges when possible. This method |
| 258 | // must be called after the interference graph has been constructed. |
Ruchira Sasanka | a90e770 | 2001-10-15 16:26:38 +0000 | [diff] [blame] | 259 | |
| 260 | |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 261 | /* Algorithm: |
Chris Lattner | 2fbfdcf | 2002-04-07 20:49:59 +0000 | [diff] [blame] | 262 | for each BB in function |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 263 | for each machine instruction (inst) |
| 264 | for each definition (def) in inst |
| 265 | for each operand (op) of inst that is a use |
Ruchira Sasanka | efaf9be | 2001-11-10 00:20:24 +0000 | [diff] [blame] | 266 | if the def and op are of the same register type |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 267 | if the def and op do not interfere //i.e., not simultaneously live |
| 268 | if (degree(LR of def) + degree(LR of op)) <= # avail regs |
Ruchira Sasanka | a5ab964 | 2001-09-30 23:11:59 +0000 | [diff] [blame] | 269 | if both LRs do not have suggested colors |
| 270 | merge2IGNodes(def, op) // i.e., merge 2 LRs |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 271 | |
| 272 | */ |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 273 | //--------------------------------------------------------------------------- |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 274 | |
| 275 | |
| 276 | // Checks if live range LR interferes with any node assigned or suggested to |
| 277 | // be assigned the specified color |
| 278 | // |
Misha Brukman | 0d82a54 | 2003-10-23 18:03:50 +0000 | [diff] [blame] | 279 | inline bool InterferesWithColor(const LiveRange& LR, unsigned color) { |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 280 | IGNode* lrNode = LR.getUserIGNode(); |
| 281 | for (unsigned n=0, NN = lrNode->getNumOfNeighbors(); n < NN; n++) { |
| 282 | LiveRange *neighLR = lrNode->getAdjIGNode(n)->getParentLR(); |
| 283 | if (neighLR->hasColor() && neighLR->getColor() == color) |
| 284 | return true; |
| 285 | if (neighLR->hasSuggestedColor() && neighLR->getSuggestedColor() == color) |
| 286 | return true; |
| 287 | } |
| 288 | return false; |
| 289 | } |
| 290 | |
| 291 | // Cannot coalesce if any of the following is true: |
| 292 | // (1) Both LRs have suggested colors (should be "different suggested colors"?) |
| 293 | // (2) Both LR1 and LR2 have colors and the colors are different |
| 294 | // (but if the colors are the same, it is definitely safe to coalesce) |
| 295 | // (3) LR1 has color and LR2 interferes with any LR that has the same color |
| 296 | // (4) LR2 has color and LR1 interferes with any LR that has the same color |
| 297 | // |
| 298 | inline bool InterfsPreventCoalescing(const LiveRange& LROfDef, |
Misha Brukman | 0d82a54 | 2003-10-23 18:03:50 +0000 | [diff] [blame] | 299 | const LiveRange& LROfUse) { |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 300 | // (4) if they have different suggested colors, cannot coalesce |
| 301 | if (LROfDef.hasSuggestedColor() && LROfUse.hasSuggestedColor()) |
| 302 | return true; |
| 303 | |
| 304 | // if neither has a color, nothing more to do. |
| 305 | if (! LROfDef.hasColor() && ! LROfUse.hasColor()) |
| 306 | return false; |
| 307 | |
| 308 | // (2, 3) if L1 has color... |
| 309 | if (LROfDef.hasColor()) { |
| 310 | if (LROfUse.hasColor()) |
| 311 | return (LROfUse.getColor() != LROfDef.getColor()); |
| 312 | return InterferesWithColor(LROfUse, LROfDef.getColor()); |
| 313 | } |
| 314 | |
| 315 | // (4) else only LROfUse has a color: check if that could interfere |
| 316 | return InterferesWithColor(LROfDef, LROfUse.getColor()); |
| 317 | } |
| 318 | |
| 319 | |
Ruchira Sasanka | 4f3eb22 | 2002-01-07 19:19:18 +0000 | [diff] [blame] | 320 | void LiveRangeInfo::coalesceLRs() |
| 321 | { |
Vikram S. Adve | 39c94e1 | 2002-09-14 23:05:33 +0000 | [diff] [blame] | 322 | if(DEBUG_RA >= RA_DEBUG_LiveRanges) |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 323 | std::cerr << "\nCoalescing LRs ...\n"; |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 324 | |
Chris Lattner | f726e77 | 2002-10-28 19:22:04 +0000 | [diff] [blame] | 325 | MachineFunction &MF = MachineFunction::get(Meth); |
| 326 | for (MachineFunction::iterator BBI = MF.begin(); BBI != MF.end(); ++BBI) { |
| 327 | MachineBasicBlock &MBB = *BBI; |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 328 | |
| 329 | // iterate over all the machine instructions in BB |
Chris Lattner | f726e77 | 2002-10-28 19:22:04 +0000 | [diff] [blame] | 330 | for(MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII){ |
Alkis Evlogimenos | c0b9dc5 | 2004-02-12 02:27:10 +0000 | [diff] [blame] | 331 | const MachineInstr *MI = MII; |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 332 | |
Vikram S. Adve | 39c94e1 | 2002-09-14 23:05:33 +0000 | [diff] [blame] | 333 | if( DEBUG_RA >= RA_DEBUG_LiveRanges) { |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 334 | std::cerr << " *Iterating over machine instr "; |
Chris Lattner | f726e77 | 2002-10-28 19:22:04 +0000 | [diff] [blame] | 335 | MI->dump(); |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 336 | std::cerr << "\n"; |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 337 | } |
| 338 | |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 339 | // iterate over MI operands to find defs |
Chris Lattner | f726e77 | 2002-10-28 19:22:04 +0000 | [diff] [blame] | 340 | for(MachineInstr::const_val_op_iterator DefI = MI->begin(), |
| 341 | DefE = MI->end(); DefI != DefE; ++DefI) { |
Alkis Evlogimenos | 4d7af65 | 2003-12-14 13:24:17 +0000 | [diff] [blame] | 342 | if (DefI.isDef()) { // this operand is modified |
Chris Lattner | 2f898d2 | 2002-02-05 06:02:59 +0000 | [diff] [blame] | 343 | LiveRange *LROfDef = getLiveRangeForValue( *DefI ); |
| 344 | RegClass *RCOfDef = LROfDef->getRegClass(); |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 345 | |
Chris Lattner | f726e77 | 2002-10-28 19:22:04 +0000 | [diff] [blame] | 346 | MachineInstr::const_val_op_iterator UseI = MI->begin(), |
| 347 | UseE = MI->end(); |
| 348 | for( ; UseI != UseE; ++UseI) { // for all uses |
Chris Lattner | 2f898d2 | 2002-02-05 06:02:59 +0000 | [diff] [blame] | 349 | LiveRange *LROfUse = getLiveRangeForValue( *UseI ); |
| 350 | if (!LROfUse) { // if LR of use is not found |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 351 | //don't warn about labels |
Vikram S. Adve | 39c94e1 | 2002-09-14 23:05:33 +0000 | [diff] [blame] | 352 | if (!isa<BasicBlock>(*UseI) && DEBUG_RA >= RA_DEBUG_LiveRanges) |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 353 | std::cerr << " !! Warning: No LR for use " << RAV(*UseI)<< "\n"; |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 354 | continue; // ignore and continue |
| 355 | } |
| 356 | |
Chris Lattner | 2f898d2 | 2002-02-05 06:02:59 +0000 | [diff] [blame] | 357 | if (LROfUse == LROfDef) // nothing to merge if they are same |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 358 | continue; |
| 359 | |
Vikram S. Adve | bc001b2 | 2003-07-25 21:06:09 +0000 | [diff] [blame] | 360 | if (MRI.getRegTypeForLR(LROfDef) == |
| 361 | MRI.getRegTypeForLR(LROfUse)) { |
Ruchira Sasanka | efaf9be | 2001-11-10 00:20:24 +0000 | [diff] [blame] | 362 | // If the two RegTypes are the same |
Chris Lattner | 3773094 | 2002-02-05 03:52:29 +0000 | [diff] [blame] | 363 | if (!RCOfDef->getInterference(LROfDef, LROfUse) ) { |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 364 | |
| 365 | unsigned CombinedDegree = |
| 366 | LROfDef->getUserIGNode()->getNumOfNeighbors() + |
| 367 | LROfUse->getUserIGNode()->getNumOfNeighbors(); |
| 368 | |
Vikram S. Adve | 32f81a3 | 2002-09-20 00:45:47 +0000 | [diff] [blame] | 369 | if (CombinedDegree > RCOfDef->getNumOfAvailRegs()) { |
| 370 | // get more precise estimate of combined degree |
| 371 | CombinedDegree = LROfDef->getUserIGNode()-> |
| 372 | getCombinedDegree(LROfUse->getUserIGNode()); |
| 373 | } |
| 374 | |
Chris Lattner | 3773094 | 2002-02-05 03:52:29 +0000 | [diff] [blame] | 375 | if (CombinedDegree <= RCOfDef->getNumOfAvailRegs()) { |
Vikram S. Adve | d0d06ad | 2003-05-31 07:32:01 +0000 | [diff] [blame] | 376 | // if both LRs do not have different pre-assigned colors |
| 377 | // and both LRs do not have suggested colors |
| 378 | if (! InterfsPreventCoalescing(*LROfDef, *LROfUse)) { |
Ruchira Sasanka | a5ab964 | 2001-09-30 23:11:59 +0000 | [diff] [blame] | 379 | RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse); |
| 380 | unionAndUpdateLRs(LROfDef, LROfUse); |
| 381 | } |
| 382 | |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 383 | } // if combined degree is less than # of regs |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 384 | } // if def and use do not interfere |
Ruchira Sasanka | d33238b | 2001-10-12 17:48:18 +0000 | [diff] [blame] | 385 | }// if reg classes are the same |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 386 | } // for all uses |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 387 | } // if def |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 388 | } // for all defs |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 389 | } // for all machine instructions |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 390 | } // for all BBs |
| 391 | |
Vikram S. Adve | 39c94e1 | 2002-09-14 23:05:33 +0000 | [diff] [blame] | 392 | if (DEBUG_RA >= RA_DEBUG_LiveRanges) |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 393 | std::cerr << "\nCoalescing Done!\n"; |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 394 | } |
| 395 | |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 396 | /*--------------------------- Debug code for printing ---------------*/ |
| 397 | |
| 398 | |
Chris Lattner | 0665a5f | 2002-02-05 01:43:49 +0000 | [diff] [blame] | 399 | void LiveRangeInfo::printLiveRanges() { |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 400 | LiveRangeMapType::iterator HMI = LiveRangeMap.begin(); // hash map iterator |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 401 | std::cerr << "\nPrinting Live Ranges from Hash Map:\n"; |
Chris Lattner | 0665a5f | 2002-02-05 01:43:49 +0000 | [diff] [blame] | 402 | for( ; HMI != LiveRangeMap.end(); ++HMI) { |
| 403 | if (HMI->first && HMI->second) { |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 404 | std::cerr << " Value* " << RAV(HMI->first) << "\t: "; |
Vikram S. Adve | 32f81a3 | 2002-09-20 00:45:47 +0000 | [diff] [blame] | 405 | if (IGNode* igNode = HMI->second->getUserIGNode()) |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 406 | std::cerr << "LR# " << igNode->getIndex(); |
Vikram S. Adve | 32f81a3 | 2002-09-20 00:45:47 +0000 | [diff] [blame] | 407 | else |
Chris Lattner | c083dcc | 2003-09-01 20:05:47 +0000 | [diff] [blame] | 408 | std::cerr << "LR# " << "<no-IGNode>"; |
Brian Gaeke | db7c40d | 2004-07-29 06:43:08 +0000 | [diff] [blame] | 409 | std::cerr << "\t:Values = " << *HMI->second << "\n"; |
Ruchira Sasanka | 8e60479 | 2001-09-14 21:18:34 +0000 | [diff] [blame] | 410 | } |
| 411 | } |
| 412 | } |
Brian Gaeke | d0fde30 | 2003-11-11 22:41:34 +0000 | [diff] [blame] | 413 | |
| 414 | } // End llvm namespace |