lib/Target/SparcV9/RegAlloc/LiveRangeInfo.cpp

   1 #include "llvm/CodeGen/LiveRangeInfo.h"
   2
   3 LiveRangeInfo::LiveRangeInfo(const Method *const M,
   4                              const TargetMachine& tm,
   5                              vector<RegClass *> &RCL)
   6                              : Meth(M), LiveRangeMap(),
   7                                TM(tm), RegClassList(RCL),
   8                                MRI( tm.getRegInfo()),
   9                                CallRetInstrList()
  10 { }
  11
  12
  13 // union two live ranges into one. The 2nd LR is deleted. Used for coalescing.
  14 // Note: the caller must make sure that L1 and L2 are distinct and both
  15 // LRs don't have suggested colors
  16
  17 void LiveRangeInfo::unionAndUpdateLRs(LiveRange *const L1, LiveRange *L2)
  18 {
  19   assert( L1 != L2);
  20   L1->setUnion( L2 );             // add elements of L2 to L1
  21   ValueSet::iterator L2It;
  22
  23   for( L2It = L2->begin() ; L2It != L2->end(); ++L2It) {
  24
  25     //assert(( L1->getTypeID() == L2->getTypeID()) && "Merge:Different types");
  26
  27     L1->add( *L2It );            // add the var in L2 to L1
  28     LiveRangeMap[ *L2It ] = L1;  // now the elements in L2 should map to L1
  29   }
  30
  31
  32   // Now if LROfDef(L1) has a suggested color, it will remain.
  33   // But, if LROfUse(L2) has a suggested color, the new range
  34   // must have the same color.
  35
  36   if(L2->hasSuggestedColor())
  37     L1->setSuggestedColor( L2->getSuggestedColor() );
  38
  39   delete ( L2 );                 // delete L2 as it is no longer needed
  40 }
  41
  42
  43
  44
  45 void LiveRangeInfo::constructLiveRanges()
  46 {
  47
  48   if( DEBUG_RA)
  49     cout << "Consturcting Live Ranges ..." << endl;
  50
  51   // first find the live ranges for all incoming args of the method since
  52   // those LRs start from the start of the method
  53
  54                                                  // get the argument list
  55   const Method::ArgumentListType& ArgList = Meth->getArgumentList();
  56                                                  // get an iterator to arg list
  57   Method::ArgumentListType::const_iterator ArgIt = ArgList.begin();
  58
  59
  60   for( ; ArgIt != ArgList.end() ; ++ArgIt) {     // for each argument
  61
  62     LiveRange * ArgRange = new LiveRange();      // creates a new LR and
  63     const Value *const Val = (const Value *) *ArgIt;
  64
  65     assert( Val);
  66
  67     ArgRange->add( Val );     // add the arg (def) to it
  68     LiveRangeMap[ Val ] = ArgRange;
  69
  70     // create a temp machine op to find the register class of value
  71     //const MachineOperand Op(MachineOperand::MO_VirtualRegister);
  72
  73     unsigned rcid = MRI.getRegClassIDOfValue( Val );
  74     ArgRange->setRegClass(RegClassList[ rcid ] );
  75
  76
  77     if( DEBUG_RA > 1) {
  78       cout << " adding LiveRange for argument ";
  79       printValue( (const Value *) *ArgIt); cout  << endl;
  80     }
  81   }
  82
  83   // Now suggest hardware registers for these method args
  84   MRI.suggestRegs4MethodArgs(Meth, *this);
  85
  86
  87
  88   // Now find speical LLVM instructions (CALL, RET) and LRs in machine
  89   // instructions.
  90
  91
  92   Method::const_iterator BBI = Meth->begin();    // random iterator for BBs
  93
  94   for( ; BBI != Meth->end(); ++BBI) {            // go thru BBs in random order
  95
  96     // Now find all LRs for machine the instructions. A new LR will be created
  97     // only for defs in the machine instr since, we assume that all Values are
  98     // defined before they are used. However, there can be multiple defs for
  99     // the same Value in machine instructions.
 100
 101     // get the iterator for machine instructions
 102     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 103     MachineCodeForBasicBlock::const_iterator
 104       MInstIterator = MIVec.begin();
 105
 106     // iterate over all the machine instructions in BB
 107     for( ; MInstIterator != MIVec.end(); MInstIterator++) {
 108
 109       const MachineInstr * MInst = *MInstIterator;
 110
 111       // Now if the machine instruction has special operands that must be
 112       // set with a "suggested color", do it here.
 113       // This will be true for call/return instructions
 114
 115
 116       if(  MRI.handleSpecialMInstr(MInst, *this, RegClassList) )
 117         continue;
 118
 119
 120       // iterate over  MI operands to find defs
 121       for( MachineInstr::val_op_const_iterator OpI(MInst);!OpI.done(); ++OpI) {
 122
 123
 124         // delete later from here ************
 125         MachineOperand::MachineOperandType OpTyp =
 126           OpI.getMachineOperand().getOperandType();
 127
 128         if (DEBUG_RA && OpTyp == MachineOperand::MO_CCRegister) {
 129           cout << "\n**CC reg found. Is Def=" << OpI.isDef() << " Val:";
 130           printValue( OpI.getMachineOperand().getVRegValue() );
 131           cout << endl;
 132         }
 133         // ************* to here
 134
 135
 136         // create a new LR iff this operand is a def
 137         if( OpI.isDef() ) {
 138
 139           const Value *const Def = *OpI;
 140
 141
 142           // Only instruction values are accepted for live ranges here
 143
 144           if( Def->getValueType() != Value::InstructionVal ) {
 145             cout << "\n**%%Error: Def is not an instruction val. Def=";
 146             printValue( Def ); cout << endl;
 147             continue;
 148           }
 149
 150
 151           LiveRange *DefRange = LiveRangeMap[Def];
 152
 153           // see LR already there (because of multiple defs)
 154
 155           if( !DefRange) {                  // if it is not in LiveRangeMap
 156
 157             DefRange = new LiveRange();     // creates a new live range and
 158             DefRange->add( Def );           // add the instruction (def) to it
 159             LiveRangeMap[ Def ] = DefRange; // update the map
 160
 161             if( DEBUG_RA > 1) {
 162               cout << "  creating a LR for def: ";
 163               printValue(Def); cout  << endl;
 164             }
 165
 166             // set the register class of the new live range
 167             //assert( RegClassList.size() );
 168             MachineOperand::MachineOperandType OpTy =
 169               OpI.getMachineOperand().getOperandType();
 170
 171             bool isCC = ( OpTy == MachineOperand::MO_CCRegister);
 172             unsigned rcid = MRI.getRegClassIDOfValue(
 173                             OpI.getMachineOperand().getVRegValue(), isCC );
 174
 175
 176             if(isCC && DEBUG_RA) {
 177               cout  << "\a**created a LR for a CC reg:";
 178               printValue( OpI.getMachineOperand().getVRegValue() );
 179             }
 180
 181             DefRange->setRegClass( RegClassList[ rcid ] );
 182
 183           }
 184           else {
 185             DefRange->add( Def );           // add the opearand to def range
 186                                             // update the map - Operand points
 187                                             // to the merged set
 188             LiveRangeMap[ Def ] = DefRange;
 189
 190             if( DEBUG_RA > 1) {
 191               cout << "   added to an existing LR for def: ";
 192               printValue( Def ); cout  << endl;
 193             }
 194           }
 195
 196
 197
 198
 199         } // if isDef()
 200
 201       } // for all opereands in machine instructions
 202
 203     } // for all machine instructions in the BB
 204
 205
 206   } // for all BBs in method
 207
 208   // go thru LLVM instructions in the basic block and suggest colors
 209   // for their args. Also  record all CALL
 210   // instructions and Return instructions in the CallRetInstrList
 211   // This is done because since there are no reverse pointers in machine
 212   // instructions to find the llvm instruction, when we encounter a call
 213   // or a return whose args must be specailly colored (e.g., %o's for args)
 214   // We have to makes sure that all LRs of call/ret args are added before
 215   // doing this. But return value of call will not have a LR.
 216
 217   BBI = Meth->begin();                  // random iterator for BBs
 218
 219   for( ; BBI != Meth->end(); ++BBI) {   // go thru BBs in random order
 220
 221     BasicBlock::const_iterator InstIt = (*BBI)->begin();
 222
 223     for( ; InstIt != (*BBI)->end() ; ++InstIt) {
 224
 225       const Instruction *const CallRetI = *InstIt;
 226       unsigned OpCode =  (CallRetI)->getOpcode();
 227
 228       if( (OpCode == Instruction::Call) ) {
 229         CallRetInstrList.push_back(CallRetI );
 230         MRI.suggestRegs4CallArgs( (CallInst *) CallRetI, *this, RegClassList );
 231       }
 232
 233       else if (OpCode == Instruction::Ret ) {
 234         CallRetInstrList.push_back( CallRetI );
 235         MRI.suggestReg4RetValue( (ReturnInst *) CallRetI, *this);
 236       }
 237
 238
 239     } // for each llvm instr in BB
 240
 241   } // for all BBs in method
 242
 243   if( DEBUG_RA)
 244     cout << "Initial Live Ranges constructed!" << endl;
 245
 246 }
 247
 248
 249
 250 void LiveRangeInfo::coalesceLRs()
 251 {
 252
 253 /* Algorithm:
 254    for each BB in method
 255      for each machine instruction (inst)
 256        for each definition (def) in inst
 257          for each operand (op) of inst that is a use
 258            if the def and op are of the same register class
 259              if the def and op do not interfere //i.e., not simultaneously live
 260                if (degree(LR of def) + degree(LR of op)) <= # avail regs
 261                  if both LRs do not have suggested colors
 262                     merge2IGNodes(def, op) // i.e., merge 2 LRs
 263
 264 */
 265
 266   if( DEBUG_RA)
 267     cout << endl << "Coalscing LRs ..." << endl;
 268
 269   Method::const_iterator BBI = Meth->begin();  // random iterator for BBs
 270
 271   for( ; BBI != Meth->end(); ++BBI) {          // traverse BBs in random order
 272
 273     // get the iterator for machine instructions
 274     const MachineCodeForBasicBlock& MIVec = (*BBI)->getMachineInstrVec();
 275     MachineCodeForBasicBlock::const_iterator
 276       MInstIterator = MIVec.begin();
 277
 278     // iterate over all the machine instructions in BB
 279     for( ; MInstIterator != MIVec.end(); ++MInstIterator) {
 280
 281       const MachineInstr * MInst = *MInstIterator;
 282
 283       if( DEBUG_RA > 1) {
 284         cout << " *Iterating over machine instr ";
 285         MInst->dump();
 286         cout << endl;
 287       }
 288
 289
 290       // iterate over  MI operands to find defs
 291       for(MachineInstr::val_op_const_iterator DefI(MInst);!DefI.done();++DefI){
 292
 293         if( DefI.isDef() ) {            // iff this operand is a def
 294
 295           LiveRange *const LROfDef = getLiveRangeForValue( *DefI );
 296           assert( LROfDef );
 297           RegClass *const RCOfDef = LROfDef->getRegClass();
 298
 299           MachineInstr::val_op_const_iterator UseI(MInst);
 300           for( ; !UseI.done(); ++UseI){ // for all uses
 301
 302             LiveRange *const LROfUse = getLiveRangeForValue( *UseI );
 303
 304             if( ! LROfUse ) {           // if LR of use is not found
 305
 306               //don't warn about labels
 307               if (!((*UseI)->getType())->isLabelType() && DEBUG_RA) {
 308                 cout<<" !! Warning: No LR for use "; printValue(*UseI);
 309                 cout << endl;
 310               }
 311               continue;                 // ignore and continue
 312             }
 313
 314             if( LROfUse == LROfDef)     // nothing to merge if they are same
 315               continue;
 316
 317             RegClass *const RCOfUse = LROfUse->getRegClass();
 318
 319             if( RCOfDef == RCOfUse ) {  // if the reg classes are the same
 320
 321               // if( LROfUse->getTypeID() == LROfDef->getTypeID() ) {
 322
 323               if( ! RCOfDef->getInterference(LROfDef, LROfUse) ) {
 324
 325                 unsigned CombinedDegree =
 326                   LROfDef->getUserIGNode()->getNumOfNeighbors() +
 327                   LROfUse->getUserIGNode()->getNumOfNeighbors();
 328
 329                 if( CombinedDegree <= RCOfDef->getNumOfAvailRegs() ) {
 330
 331                   // if both LRs do not have suggested colors
 332                   if( ! (LROfDef->hasSuggestedColor() &&
 333                          LROfUse->hasSuggestedColor() ) ) {
 334
 335                     RCOfDef->mergeIGNodesOfLRs(LROfDef, LROfUse);
 336                     unionAndUpdateLRs(LROfDef, LROfUse);
 337                   }
 338
 339
 340                 } // if combined degree is less than # of regs
 341
 342               } // if def and use do not interfere
 343
 344             }// if reg classes are the same
 345
 346           } // for all uses
 347
 348         } // if def
 349
 350       } // for all defs
 351
 352     } // for all machine instructions
 353
 354   } // for all BBs
 355
 356   if( DEBUG_RA)
 357     cout << endl << "Coalscing Done!" << endl;
 358
 359 }
 360
 361
 362
 363
 364
 365 /*--------------------------- Debug code for printing ---------------*/
 366
 367
 368 void LiveRangeInfo::printLiveRanges()
 369 {
 370   LiveRangeMapType::iterator HMI = LiveRangeMap.begin();   // hash map iterator
 371   cout << endl << "Printing Live Ranges from Hash Map:" << endl;
 372   for( ; HMI != LiveRangeMap.end() ; HMI ++ ) {
 373     if( (*HMI).first && (*HMI).second ) {
 374       cout <<" "; printValue((*HMI).first);  cout  << "\t: ";
 375       ((*HMI).second)->printSet(); cout << endl;
 376     }
 377   }
 378 }
 379
 380