LLVM API Documentation

PhyRegAlloc.cpp

Go to the documentation of this file.
00001 //===-- PhyRegAlloc.cpp ---------------------------------------------------===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file was developed by the LLVM research group and is distributed under
00006 // the University of Illinois Open Source License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 //
00010 // Traditional graph-coloring global register allocator currently used
00011 // by the SPARC back-end.
00012 //
00013 // NOTE: This register allocator has some special support
00014 // for the Reoptimizer, such as not saving some registers on calls to
00015 // the first-level instrumentation function.
00016 //
00017 // NOTE 2: This register allocator can save its state in a global
00018 // variable in the module it's working on. This feature is not
00019 // thread-safe; if you have doubts, leave it turned off.
00020 //
00021 //===----------------------------------------------------------------------===//
00022 
00023 #include "AllocInfo.h"
00024 #include "IGNode.h"
00025 #include "PhyRegAlloc.h"
00026 #include "RegAllocCommon.h"
00027 #include "RegClass.h"
00028 #include "../LiveVar/FunctionLiveVarInfo.h"
00029 #include "../MachineCodeForInstruction.h"
00030 #include "../MachineFunctionInfo.h"
00031 #include "../SparcV9InstrInfo.h"
00032 #include "../SparcV9TmpInstr.h"
00033 #include "llvm/Constants.h"
00034 #include "llvm/DerivedTypes.h"
00035 #include "llvm/Instructions.h"
00036 #include "llvm/Module.h"
00037 #include "llvm/Type.h"
00038 #include "llvm/Analysis/LoopInfo.h"
00039 #include "llvm/CodeGen/MachineFunction.h"
00040 #include "llvm/CodeGen/MachineInstr.h"
00041 #include "llvm/CodeGen/MachineInstrBuilder.h"
00042 #include "../MachineInstrAnnot.h"
00043 #include "llvm/CodeGen/Passes.h"
00044 #include "llvm/Support/InstIterator.h"
00045 #include "llvm/Target/TargetInstrInfo.h"
00046 #include "llvm/Support/CommandLine.h"
00047 #include "llvm/ADT/SetOperations.h"
00048 #include "llvm/ADT/STLExtras.h"
00049 #include "llvm/ADT/Statistic.h"
00050 #include <cmath>
00051 #include <iostream>
00052 
00053 namespace llvm {
00054  Statistic<> RASpills("regalloc-spills", "Number of registers spilled");
00055 
00056 RegAllocDebugLevel_t DEBUG_RA;
00057 
00058 static cl::opt<RegAllocDebugLevel_t, true>
00059 DRA_opt("dregalloc", cl::Hidden, cl::location(DEBUG_RA),
00060         cl::desc("enable register allocation debugging information"),
00061         cl::values(
00062   clEnumValN(RA_DEBUG_None   ,     "n", "disable debug output"),
00063   clEnumValN(RA_DEBUG_Results,     "y", "debug output for allocation results"),
00064   clEnumValN(RA_DEBUG_Coloring,    "c", "debug output for graph coloring step"),
00065   clEnumValN(RA_DEBUG_Interference,"ig","debug output for interference graphs"),
00066   clEnumValN(RA_DEBUG_LiveRanges , "lr","debug output for live ranges"),
00067   clEnumValN(RA_DEBUG_Verbose,     "v", "extra debug output"),
00068                    clEnumValEnd));
00069 
00070 /// The reoptimizer wants to be able to grovel through the register
00071 /// allocator's state after it has done its job. This is a hack.
00072 ///
00073 PhyRegAlloc::SavedStateMapTy ExportedFnAllocState;
00074 bool SaveRegAllocState = false;
00075 bool SaveStateToModule = true;
00076 static cl::opt<bool, true>
00077 SaveRegAllocStateOpt("save-ra-state", cl::Hidden,
00078                   cl::location (SaveRegAllocState),
00079                   cl::init(false),
00080                   cl::desc("write reg. allocator state into module"));
00081 
00082 FunctionPass *getRegisterAllocator(TargetMachine &T) {
00083   return new PhyRegAlloc (T);
00084 }
00085 
00086 void PhyRegAlloc::getAnalysisUsage(AnalysisUsage &AU) const {
00087   AU.addRequired<LoopInfo> ();
00088   AU.addRequired<FunctionLiveVarInfo> ();
00089 }
00090 
00091 
00092 /// Initialize interference graphs (one in each reg class) and IGNodeLists
00093 /// (one in each IG). The actual nodes will be pushed later.
00094 ///
00095 void PhyRegAlloc::createIGNodeListsAndIGs() {
00096   if (DEBUG_RA >= RA_DEBUG_LiveRanges) std::cerr << "Creating LR lists ...\n";
00097 
00098   LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap()->begin();
00099   LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap()->end();
00100 
00101   for (; HMI != HMIEnd ; ++HMI ) {
00102     if (HMI->first) {
00103       V9LiveRange *L = HMI->second;   // get the V9LiveRange
00104       if (!L) {
00105         if (DEBUG_RA && !isa<ConstantIntegral> (HMI->first))
00106           std::cerr << "\n**** ?!?WARNING: NULL LIVE RANGE FOUND FOR: "
00107                << RAV(HMI->first) << "****\n";
00108         continue;
00109       }
00110 
00111       // if the Value * is not null, and LR is not yet written to the IGNodeList
00112       if (!(L->getUserIGNode())  ) {
00113         RegClass *const RC =           // RegClass of first value in the LR
00114           RegClassList[ L->getRegClassID() ];
00115         RC->addLRToIG(L);              // add this LR to an IG
00116       }
00117     }
00118   }
00119 
00120   // init RegClassList
00121   for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
00122     RegClassList[rc]->createInterferenceGraph();
00123 
00124   if (DEBUG_RA >= RA_DEBUG_LiveRanges) std::cerr << "LRLists Created!\n";
00125 }
00126 
00127 
00128 /// Add all interferences for a given instruction.  Interference occurs only
00129 /// if the LR of Def (Inst or Arg) is of the same reg class as that of live
00130 /// var. The live var passed to this function is the LVset AFTER the
00131 /// instruction.
00132 ///
00133 void PhyRegAlloc::addInterference(const Value *Def, const ValueSet *LVSet,
00134                                   bool isCallInst) {
00135   ValueSet::const_iterator LIt = LVSet->begin();
00136 
00137   // get the live range of instruction
00138   const V9LiveRange *const LROfDef = LRI->getLiveRangeForValue( Def );
00139 
00140   IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
00141   assert( IGNodeOfDef );
00142 
00143   RegClass *const RCOfDef = LROfDef->getRegClass();
00144 
00145   // for each live var in live variable set
00146   for ( ; LIt != LVSet->end(); ++LIt) {
00147 
00148     if (DEBUG_RA >= RA_DEBUG_Verbose)
00149       std::cerr << "< Def=" << RAV(Def) << ", Lvar=" << RAV(*LIt) << "> ";
00150 
00151     //  get the live range corresponding to live var
00152     V9LiveRange *LROfVar = LRI->getLiveRangeForValue(*LIt);
00153 
00154     // LROfVar can be null if it is a const since a const
00155     // doesn't have a dominating def - see Assumptions above
00156     if (LROfVar)
00157       if (LROfDef != LROfVar)                  // do not set interf for same LR
00158         if (RCOfDef == LROfVar->getRegClass()) // 2 reg classes are the same
00159           RCOfDef->setInterference( LROfDef, LROfVar);
00160   }
00161 }
00162 
00163 
00164 /// For a call instruction, this method sets the CallInterference flag in
00165 /// the LR of each variable live in the Live Variable Set live after the
00166 /// call instruction (except the return value of the call instruction - since
00167 /// the return value does not interfere with that call itself).
00168 ///
00169 void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst,
00170                                        const ValueSet *LVSetAft) {
00171   if (DEBUG_RA >= RA_DEBUG_Interference)
00172     std::cerr << "\n For call inst: " << *MInst;
00173 
00174   // for each live var in live variable set after machine inst
00175   for (ValueSet::const_iterator LIt = LVSetAft->begin(), LEnd = LVSetAft->end();
00176        LIt != LEnd; ++LIt) {
00177 
00178     //  get the live range corresponding to live var
00179     V9LiveRange *const LR = LRI->getLiveRangeForValue(*LIt);
00180 
00181     // LR can be null if it is a const since a const
00182     // doesn't have a dominating def - see Assumptions above
00183     if (LR) {
00184       if (DEBUG_RA >= RA_DEBUG_Interference)
00185         std::cerr << "\n\tLR after Call: " << *LR << "\n";
00186       LR->setCallInterference();
00187       if (DEBUG_RA >= RA_DEBUG_Interference)
00188             std::cerr << "\n  ++After adding call interference for LR: " << *LR << "\n";
00189     }
00190   }
00191 
00192   // Now find the LR of the return value of the call
00193   // We do this because, we look at the LV set *after* the instruction
00194   // to determine, which LRs must be saved across calls. The return value
00195   // of the call is live in this set - but it does not interfere with call
00196   // (i.e., we can allocate a volatile register to the return value)
00197   CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst);
00198 
00199   if (const Value *RetVal = argDesc->getReturnValue()) {
00200     V9LiveRange *RetValLR = LRI->getLiveRangeForValue( RetVal );
00201     assert( RetValLR && "No LR for RetValue of call");
00202     RetValLR->clearCallInterference();
00203   }
00204 
00205   // If the CALL is an indirect call, find the LR of the function pointer.
00206   // That has a call interference because it conflicts with outgoing args.
00207   if (const Value *AddrVal = argDesc->getIndirectFuncPtr()) {
00208     V9LiveRange *AddrValLR = LRI->getLiveRangeForValue( AddrVal );
00209     // LR can be null if the function pointer is a constant.
00210     if (AddrValLR)
00211       AddrValLR->setCallInterference();
00212   }
00213 }
00214 
00215 
00216 /// Create interferences in the IG of each RegClass, and calculate the spill
00217 /// cost of each Live Range (it is done in this method to save another pass
00218 /// over the code).
00219 ///
00220 void PhyRegAlloc::buildInterferenceGraphs() {
00221   if (DEBUG_RA >= RA_DEBUG_Interference)
00222     std::cerr << "Creating interference graphs ...\n";
00223 
00224   unsigned BBLoopDepthCost;
00225   for (MachineFunction::iterator BBI = MF->begin(), BBE = MF->end();
00226        BBI != BBE; ++BBI) {
00227     const MachineBasicBlock &MBB = *BBI;
00228     const BasicBlock *BB = MBB.getBasicBlock();
00229 
00230     // find the 10^(loop_depth) of this BB
00231     BBLoopDepthCost = (unsigned)pow(10.0, LoopDepthCalc->getLoopDepth(BB));
00232 
00233     // get the iterator for machine instructions
00234     MachineBasicBlock::const_iterator MII = MBB.begin();
00235 
00236     // iterate over all the machine instructions in BB
00237     for ( ; MII != MBB.end(); ++MII) {
00238       const MachineInstr *MInst = MII;
00239 
00240       // get the LV set after the instruction
00241       const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BB);
00242       bool isCallInst = TM.getInstrInfo()->isCall(MInst->getOpcode());
00243 
00244       if (isCallInst) {
00245         // set the isCallInterference flag of each live range which extends
00246         // across this call instruction. This information is used by graph
00247         // coloring algorithm to avoid allocating volatile colors to live ranges
00248         // that span across calls (since they have to be saved/restored)
00249         setCallInterferences(MInst, &LVSetAI);
00250       }
00251 
00252       // iterate over all MI operands to find defs
00253       for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
00254              OpE = MInst->end(); OpI != OpE; ++OpI) {
00255         if (OpI.isDef()) // create a new LR since def
00256           addInterference(*OpI, &LVSetAI, isCallInst);
00257 
00258         // Calculate the spill cost of each live range
00259         V9LiveRange *LR = LRI->getLiveRangeForValue(*OpI);
00260         if (LR) LR->addSpillCost(BBLoopDepthCost);
00261       }
00262       // Also add interference for any implicit definitions in a machine
00263       // instr (currently, only calls have this).
00264       unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
00265       for (unsigned z=0; z < NumOfImpRefs; z++)
00266         if (MInst->getImplicitOp(z).isDef())
00267           addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst );
00268     } // for all machine instructions in BB
00269   } // for all BBs in function
00270 
00271   // add interferences for function arguments. Since there are no explicit
00272   // defs in the function for args, we have to add them manually
00273   addInterferencesForArgs();
00274 
00275   if (DEBUG_RA >= RA_DEBUG_Interference)
00276     std::cerr << "Interference graphs calculated!\n";
00277 }
00278 
00279 
00280 /// Mark all operands of the given MachineInstr as interfering with one
00281 /// another.
00282 ///
00283 void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {
00284   bool setInterf = false;
00285 
00286   // iterate over MI operands to find defs
00287   for (MachineInstr::const_val_op_iterator It1 = MInst->begin(),
00288          ItE = MInst->end(); It1 != ItE; ++It1) {
00289     const V9LiveRange *LROfOp1 = LRI->getLiveRangeForValue(*It1);
00290     assert((LROfOp1 || It1.isDef()) && "No LR for Def in PSEUDO insruction");
00291 
00292     MachineInstr::const_val_op_iterator It2 = It1;
00293     for (++It2; It2 != ItE; ++It2) {
00294       const V9LiveRange *LROfOp2 = LRI->getLiveRangeForValue(*It2);
00295 
00296       if (LROfOp2) {
00297         RegClass *RCOfOp1 = LROfOp1->getRegClass();
00298         RegClass *RCOfOp2 = LROfOp2->getRegClass();
00299 
00300         if (RCOfOp1 == RCOfOp2 ){
00301           RCOfOp1->setInterference( LROfOp1, LROfOp2 );
00302           setInterf = true;
00303         }
00304       } // if Op2 has a LR
00305     } // for all other defs in machine instr
00306   } // for all operands in an instruction
00307 
00308   if (!setInterf && MInst->getNumOperands() > 2) {
00309     std::cerr << "\nInterf not set for any operand in pseudo instr:\n";
00310     std::cerr << *MInst;
00311     assert(0 && "Interf not set for pseudo instr with > 2 operands" );
00312   }
00313 }
00314 
00315 
00316 /// Add interferences for incoming arguments to a function.
00317 ///
00318 void PhyRegAlloc::addInterferencesForArgs() {
00319   // get the InSet of root BB
00320   const ValueSet &InSet = LVI->getInSetOfBB(&Fn->front());
00321 
00322   for (Function::const_arg_iterator AI = Fn->arg_begin(); AI != Fn->arg_end(); ++AI) {
00323     // add interferences between args and LVars at start
00324     addInterference(AI, &InSet, false);
00325 
00326     if (DEBUG_RA >= RA_DEBUG_Interference)
00327       std::cerr << " - %% adding interference for argument " << RAV(AI) << "\n";
00328   }
00329 }
00330 
00331 
00332 /// The following are utility functions used solely by updateMachineCode and
00333 /// the functions that it calls. They should probably be folded back into
00334 /// updateMachineCode at some point.
00335 ///
00336 
00337 // used by: updateMachineCode (1 time), PrependInstructions (1 time)
00338 inline void InsertBefore(MachineInstr* newMI, MachineBasicBlock& MBB,
00339                          MachineBasicBlock::iterator& MII) {
00340   MII = MBB.insert(MII, newMI);
00341   ++MII;
00342 }
00343 
00344 // used by: AppendInstructions (1 time)
00345 inline void InsertAfter(MachineInstr* newMI, MachineBasicBlock& MBB,
00346                         MachineBasicBlock::iterator& MII) {
00347   ++MII;    // insert before the next instruction
00348   MII = MBB.insert(MII, newMI);
00349 }
00350 
00351 // used by: updateMachineCode (2 times)
00352 inline void PrependInstructions(std::vector<MachineInstr *> &IBef,
00353                                 MachineBasicBlock& MBB,
00354                                 MachineBasicBlock::iterator& MII,
00355                                 const std::string& msg) {
00356   if (!IBef.empty()) {
00357       MachineInstr* OrigMI = MII;
00358       std::vector<MachineInstr *>::iterator AdIt;
00359       for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt) {
00360           if (DEBUG_RA) {
00361             if (OrigMI) std::cerr << "For MInst:\n  " << *OrigMI;
00362             std::cerr << msg << "PREPENDed instr:\n  " << **AdIt << "\n";
00363           }
00364           InsertBefore(*AdIt, MBB, MII);
00365         }
00366     }
00367 }
00368 
00369 // used by: updateMachineCode (1 time)
00370 inline void AppendInstructions(std::vector<MachineInstr *> &IAft,
00371                                MachineBasicBlock& MBB,
00372                                MachineBasicBlock::iterator& MII,
00373                                const std::string& msg) {
00374   if (!IAft.empty()) {
00375       MachineInstr* OrigMI = MII;
00376       std::vector<MachineInstr *>::iterator AdIt;
00377       for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt ) {
00378           if (DEBUG_RA) {
00379             if (OrigMI) std::cerr << "For MInst:\n  " << *OrigMI;
00380             std::cerr << msg << "APPENDed instr:\n  "  << **AdIt << "\n";
00381           }
00382           InsertAfter(*AdIt, MBB, MII);
00383         }
00384     }
00385 }
00386 
00387 /// Set the registers for operands in the given MachineInstr, if a register was
00388 /// successfully allocated.  Return true if any of its operands has been marked
00389 /// for spill.
00390 ///
00391 bool PhyRegAlloc::markAllocatedRegs(MachineInstr* MInst)
00392 {
00393   bool instrNeedsSpills = false;
00394 
00395   // First, set the registers for operands in the machine instruction
00396   // if a register was successfully allocated.  Do this first because we
00397   // will need to know which registers are already used by this instr'n.
00398   for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
00399       MachineOperand& Op = MInst->getOperand(OpNum);
00400       if (Op.getType() ==  MachineOperand::MO_VirtualRegister ||
00401           Op.getType() ==  MachineOperand::MO_CCRegister) {
00402           const Value *const Val =  Op.getVRegValue();
00403           if (const V9LiveRange* LR = LRI->getLiveRangeForValue(Val)) {
00404             // Remember if any operand needs spilling
00405             instrNeedsSpills |= LR->isMarkedForSpill();
00406 
00407             // An operand may have a color whether or not it needs spilling
00408             if (LR->hasColor())
00409               MInst->SetRegForOperand(OpNum,
00410                           MRI.getUnifiedRegNum(LR->getRegClassID(),
00411                                                LR->getColor()));
00412           }
00413         }
00414     } // for each operand
00415 
00416   return instrNeedsSpills;
00417 }
00418 
00419 /// Mark allocated registers (using markAllocatedRegs()) on the instruction
00420 /// that MII points to. Then, if it's a call instruction, insert caller-saving
00421 /// code before and after it. Finally, insert spill code before and after it,
00422 /// using insertCode4SpilledLR().
00423 ///
00424 void PhyRegAlloc::updateInstruction(MachineBasicBlock::iterator& MII,
00425                                     MachineBasicBlock &MBB) {
00426   MachineInstr* MInst = MII;
00427   unsigned Opcode = MInst->getOpcode();
00428 
00429   // Reset tmp stack positions so they can be reused for each machine instr.
00430   MF->getInfo<SparcV9FunctionInfo>()->popAllTempValues();
00431 
00432   // Mark the operands for which regs have been allocated.
00433   bool instrNeedsSpills = markAllocatedRegs(MII);
00434 
00435 #ifndef NDEBUG
00436   // Mark that the operands have been updated.  Later,
00437   // setRelRegsUsedByThisInst() is called to find registers used by each
00438   // MachineInst, and it should not be used for an instruction until
00439   // this is done.  This flag just serves as a sanity check.
00440   OperandsColoredMap[MInst] = true;
00441 #endif
00442 
00443   // Now insert caller-saving code before/after the call.
00444   // Do this before inserting spill code since some registers must be
00445   // used by save/restore and spill code should not use those registers.
00446   if (TM.getInstrInfo()->isCall(Opcode)) {
00447     AddedInstrns &AI = AddedInstrMap[MInst];
00448     insertCallerSavingCode(AI.InstrnsBefore, AI.InstrnsAfter, MInst,
00449                            MBB.getBasicBlock());
00450   }
00451 
00452   // Now insert spill code for remaining operands not allocated to
00453   // registers.  This must be done even for call return instructions
00454   // since those are not handled by the special code above.
00455   if (instrNeedsSpills)
00456     for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
00457         MachineOperand& Op = MInst->getOperand(OpNum);
00458         if (Op.getType() ==  MachineOperand::MO_VirtualRegister ||
00459             Op.getType() ==  MachineOperand::MO_CCRegister) {
00460             const Value* Val = Op.getVRegValue();
00461             if (const V9LiveRange *LR = LRI->getLiveRangeForValue(Val))
00462               if (LR->isMarkedForSpill())
00463                 insertCode4SpilledLR(LR, MII, MBB, OpNum);
00464           }
00465       } // for each operand
00466 }
00467 
00468 /// Iterate over all the MachineBasicBlocks in the current function and set
00469 /// the allocated registers for each instruction (using updateInstruction()),
00470 /// after register allocation is complete. Then move code out of delay slots.
00471 ///
00472 void PhyRegAlloc::updateMachineCode()
00473 {
00474   // Insert any instructions needed at method entry
00475   MachineBasicBlock::iterator MII = MF->front().begin();
00476   PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MF->front(), MII,
00477                       "At function entry: \n");
00478   assert(AddedInstrAtEntry.InstrnsAfter.empty() &&
00479          "InstrsAfter should be unnecessary since we are just inserting at "
00480          "the function entry point here.");
00481 
00482   for (MachineFunction::iterator BBI = MF->begin(), BBE = MF->end();
00483        BBI != BBE; ++BBI) {
00484     MachineBasicBlock &MBB = *BBI;
00485 
00486     // Iterate over all machine instructions in BB and mark operands with
00487     // their assigned registers or insert spill code, as appropriate.
00488     // Also, fix operands of call/return instructions.
00489     for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII)
00490       if (MII->getOpcode() != V9::PHI)
00491         updateInstruction(MII, MBB);
00492 
00493     // Now, move code out of delay slots of branches and returns if needed.
00494     // (Also, move "after" code from calls to the last delay slot instruction.)
00495     // Moving code out of delay slots is needed in 2 situations:
00496     // (1) If this is a branch and it needs instructions inserted after it,
00497     //     move any existing instructions out of the delay slot so that the
00498     //     instructions can go into the delay slot.  This only supports the
00499     //     case that #instrsAfter <= #delay slots.
00500     //
00501     // (2) If any instruction in the delay slot needs
00502     //     instructions inserted, move it out of the delay slot and before the
00503     //     branch because putting code before or after it would be VERY BAD!
00504     //
00505     // If the annul bit of the branch is set, neither of these is legal!
00506     // If so, we need to handle spill differently but annulling is not yet used.
00507     for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII)
00508       if (unsigned delaySlots =
00509           TM.getInstrInfo()->getNumDelaySlots(MII->getOpcode())) {
00510           MachineBasicBlock::iterator DelaySlotMI = next(MII);
00511           assert(DelaySlotMI != MBB.end() && "no instruction for delay slot");
00512 
00513           // Check the 2 conditions above:
00514           // (1) Does a branch need instructions added after it?
00515           // (2) O/w does delay slot instr. need instrns before or after?
00516           bool isBranch = (TM.getInstrInfo()->isBranch(MII->getOpcode()) ||
00517                            TM.getInstrInfo()->isReturn(MII->getOpcode()));
00518           bool cond1 = (isBranch &&
00519                         AddedInstrMap.count(MII) &&
00520                         AddedInstrMap[MII].InstrnsAfter.size() > 0);
00521           bool cond2 = (AddedInstrMap.count(DelaySlotMI) &&
00522                         (AddedInstrMap[DelaySlotMI].InstrnsBefore.size() > 0 ||
00523                          AddedInstrMap[DelaySlotMI].InstrnsAfter.size()  > 0));
00524 
00525           if (cond1 || cond2) {
00526               assert(delaySlots==1 &&
00527                      "InsertBefore does not yet handle >1 delay slots!");
00528 
00529               if (DEBUG_RA) {
00530                 std::cerr << "\nRegAlloc: Moved instr. with added code: "
00531                      << *DelaySlotMI
00532                      << "           out of delay slots of instr: " << *MII;
00533               }
00534 
00535               // move instruction before branch
00536               MBB.insert(MII, MBB.remove(DelaySlotMI++));
00537 
00538               // On cond1 we are done (we already moved the
00539               // instruction out of the delay slot). On cond2 we need
00540               // to insert a nop in place of the moved instruction
00541               if (cond2) {
00542                 MBB.insert(MII, BuildMI(V9::NOP, 1));
00543               }
00544             }
00545           else {
00546             // For non-branch instr with delay slots (probably a call), move
00547             // InstrAfter to the instr. in the last delay slot.
00548             MachineBasicBlock::iterator tmp = next(MII, delaySlots);
00549             move2DelayedInstr(MII, tmp);
00550           }
00551       }
00552 
00553     // Finally iterate over all instructions in BB and insert before/after
00554     for (MachineBasicBlock::iterator MII=MBB.begin(); MII != MBB.end(); ++MII) {
00555       MachineInstr *MInst = MII;
00556 
00557       // do not process Phis
00558       if (MInst->getOpcode() == V9::PHI)
00559         continue;
00560 
00561       // if there are any added instructions...
00562       if (AddedInstrMap.count(MInst)) {
00563         AddedInstrns &CallAI = AddedInstrMap[MInst];
00564 
00565 #ifndef NDEBUG
00566         bool isBranch = (TM.getInstrInfo()->isBranch(MInst->getOpcode()) ||
00567                          TM.getInstrInfo()->isReturn(MInst->getOpcode()));
00568         assert((!isBranch ||
00569                 AddedInstrMap[MInst].InstrnsAfter.size() <=
00570                 TM.getInstrInfo()->getNumDelaySlots(MInst->getOpcode())) &&
00571                "Cannot put more than #delaySlots instrns after "
00572                "branch or return! Need to handle temps differently.");
00573 #endif
00574 
00575 #ifndef NDEBUG
00576         // Temporary sanity checking code to detect whether the same machine
00577         // instruction is ever inserted twice before/after a call.
00578         // I suspect this is happening but am not sure. --Vikram, 7/1/03.
00579         std::set<const MachineInstr*> instrsSeen;
00580         for (int i = 0, N = CallAI.InstrnsBefore.size(); i < N; ++i) {
00581           assert(instrsSeen.count(CallAI.InstrnsBefore[i]) == 0 &&
00582                  "Duplicate machine instruction in InstrnsBefore!");
00583           instrsSeen.insert(CallAI.InstrnsBefore[i]);
00584         }
00585         for (int i = 0, N = CallAI.InstrnsAfter.size(); i < N; ++i) {
00586           assert(instrsSeen.count(CallAI.InstrnsAfter[i]) == 0 &&
00587                  "Duplicate machine instruction in InstrnsBefore/After!");
00588           instrsSeen.insert(CallAI.InstrnsAfter[i]);
00589         }
00590 #endif
00591 
00592         // Now add the instructions before/after this MI.
00593         // We do this here to ensure that spill for an instruction is inserted
00594         // as close as possible to an instruction (see above insertCode4Spill)
00595         if (! CallAI.InstrnsBefore.empty())
00596           PrependInstructions(CallAI.InstrnsBefore, MBB, MII,"");
00597 
00598         if (! CallAI.InstrnsAfter.empty())
00599           AppendInstructions(CallAI.InstrnsAfter, MBB, MII,"");
00600 
00601       } // if there are any added instructions
00602     } // for each machine instruction
00603   }
00604 }
00605 
00606 
00607 /// Insert spill code for AN operand whose LR was spilled.  May be called
00608 /// repeatedly for a single MachineInstr if it has many spilled operands. On
00609 /// each call, it finds a register which is not live at that instruction and
00610 /// also which is not used by other spilled operands of the same
00611 /// instruction. Then it uses this register temporarily to accommodate the
00612 /// spilled value.
00613 ///
00614 void PhyRegAlloc::insertCode4SpilledLR(const V9LiveRange *LR,
00615                                        MachineBasicBlock::iterator& MII,
00616                                        MachineBasicBlock &MBB,
00617                                        const unsigned OpNum) {
00618   MachineInstr *MInst = MII;
00619   const BasicBlock *BB = MBB.getBasicBlock();
00620 
00621   assert((! TM.getInstrInfo()->isCall(MInst->getOpcode()) || OpNum == 0) &&
00622          "Outgoing arg of a call must be handled elsewhere (func arg ok)");
00623   assert(! TM.getInstrInfo()->isReturn(MInst->getOpcode()) &&
00624          "Return value of a ret must be handled elsewhere");
00625 
00626   MachineOperand& Op = MInst->getOperand(OpNum);
00627   bool isDef =  Op.isDef();
00628   bool isUse = Op.isUse();
00629   unsigned RegType = MRI.getRegTypeForLR(LR);
00630   int SpillOff = LR->getSpillOffFromFP();
00631   RegClass *RC = LR->getRegClass();
00632 
00633   // Get the live-variable set to find registers free before this instr.
00634   const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);
00635 
00636 #ifndef NDEBUG
00637   // If this instr. is in the delay slot of a branch or return, we need to
00638   // include all live variables before that branch or return -- we don't want to
00639   // trample those!  Verify that the set is included in the LV set before MInst.
00640   if (MII != MBB.begin()) {
00641     MachineBasicBlock::iterator PredMI = prior(MII);
00642     if (unsigned DS = TM.getInstrInfo()->getNumDelaySlots(PredMI->getOpcode()))
00643       assert(set_difference(LVI->getLiveVarSetBeforeMInst(PredMI), LVSetBef)
00644              .empty() && "Live-var set before branch should be included in "
00645              "live-var set of each delay slot instruction!");
00646   }
00647 #endif
00648 
00649   MF->getInfo<SparcV9FunctionInfo>()->pushTempValue(MRI.getSpilledRegSize(RegType));
00650 
00651   std::vector<MachineInstr*> MIBef, MIAft;
00652   std::vector<MachineInstr*> AdIMid;
00653 
00654   // Choose a register to hold the spilled value, if one was not preallocated.
00655   // This may insert code before and after MInst to free up the value.  If so,
00656   // this code should be first/last in the spill sequence before/after MInst.
00657   int TmpRegU=(LR->hasColor()
00658                ? MRI.getUnifiedRegNum(LR->getRegClassID(),LR->getColor())
00659                : getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef,MIAft));
00660 
00661   // Set the operand first so that it this register does not get used
00662   // as a scratch register for later calls to getUsableUniRegAtMI below
00663   MInst->SetRegForOperand(OpNum, TmpRegU);
00664 
00665   // get the added instructions for this instruction
00666   AddedInstrns &AI = AddedInstrMap[MInst];
00667 
00668   // We may need a scratch register to copy the spilled value to/from memory.
00669   // This may itself have to insert code to free up a scratch register.
00670   // Any such code should go before (after) the spill code for a load (store).
00671   // The scratch reg is not marked as used because it is only used
00672   // for the copy and not used across MInst.
00673   int scratchRegType = -1;
00674   int scratchReg = -1;
00675   if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) {
00676       scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
00677                                        MInst, MIBef, MIAft);
00678       assert(scratchReg != MRI.getInvalidRegNum());
00679     }
00680 
00681   if (isUse) {
00682     // for a USE, we have to load the value of LR from stack to a TmpReg
00683     // and use the TmpReg as one operand of instruction
00684 
00685     // actual loading instruction(s)
00686     MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU,
00687                     RegType, scratchReg);
00688 
00689     // the actual load should be after the instructions to free up TmpRegU
00690     MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end());
00691     AdIMid.clear();
00692   }
00693 
00694   if (isDef) {   // if this is a Def
00695     // for a DEF, we have to store the value produced by this instruction
00696     // on the stack position allocated for this LR
00697 
00698     // actual storing instruction(s)
00699     MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff,
00700                     RegType, scratchReg);
00701 
00702     MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end());
00703   }  // if !DEF
00704 
00705   // Finally, insert the entire spill code sequences before/after MInst
00706   AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end());
00707   AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end());
00708   ++RASpills;
00709 
00710   if (DEBUG_RA) {
00711     std::cerr << "\nFor Inst:\n  " << *MInst;
00712     std::cerr << "SPILLED LR# " << LR->getUserIGNode()->getIndex();
00713     std::cerr << "; added Instructions:";
00714     for_each(MIBef.begin(), MIBef.end(), std::mem_fun(&MachineInstr::dump));
00715     for_each(MIAft.begin(), MIAft.end(), std::mem_fun(&MachineInstr::dump));
00716   }
00717 }
00718 
00719 
00720 /// Insert caller saving/restoring instructions before/after a call machine
00721 /// instruction (before or after any other instructions that were inserted for
00722 /// the call).
00723 ///
00724 void
00725 PhyRegAlloc::insertCallerSavingCode(std::vector<MachineInstr*> &instrnsBefore,
00726                                     std::vector<MachineInstr*> &instrnsAfter,
00727                                     MachineInstr *CallMI,
00728                                     const BasicBlock *BB) {
00729   assert(TM.getInstrInfo()->isCall(CallMI->getOpcode()));
00730 
00731   // hash set to record which registers were saved/restored
00732   hash_set<unsigned> PushedRegSet;
00733 
00734   CallArgsDescriptor* argDesc = CallArgsDescriptor::get(CallMI);
00735 
00736   // if the call is to a instrumentation function, do not insert save and
00737   // restore instructions the instrumentation function takes care of save
00738   // restore for volatile regs.
00739   //
00740   // FIXME: this should be made general, not specific to the reoptimizer!
00741   const Function *Callee = argDesc->getCallInst()->getCalledFunction();
00742   bool isLLVMFirstTrigger = Callee && Callee->getName() == "llvm_first_trigger";
00743 
00744   // Now check if the call has a return value (using argDesc) and if so,
00745   // find the LR of the TmpInstruction representing the return value register.
00746   // (using the last or second-last *implicit operand* of the call MI).
00747   // Insert it to to the PushedRegSet since we must not save that register
00748   // and restore it after the call.
00749   // We do this because, we look at the LV set *after* the instruction
00750   // to determine, which LRs must be saved across calls. The return value
00751   // of the call is live in this set - but we must not save/restore it.
00752   if (const Value *origRetVal = argDesc->getReturnValue()) {
00753     unsigned retValRefNum = (CallMI->getNumImplicitRefs() -
00754                              (argDesc->getIndirectFuncPtr()? 1 : 2));
00755     const TmpInstruction* tmpRetVal =
00756       cast<TmpInstruction>(CallMI->getImplicitRef(retValRefNum));
00757     assert(tmpRetVal->getOperand(0) == origRetVal &&
00758            tmpRetVal->getType() == origRetVal->getType() &&
00759            "Wrong implicit ref?");
00760     V9LiveRange *RetValLR = LRI->getLiveRangeForValue(tmpRetVal);
00761     assert(RetValLR && "No LR for RetValue of call");
00762 
00763     if (! RetValLR->isMarkedForSpill())
00764       PushedRegSet.insert(MRI.getUnifiedRegNum(RetValLR->getRegClassID(),
00765                                                RetValLR->getColor()));
00766   }
00767 
00768   const ValueSet &LVSetAft =  LVI->getLiveVarSetAfterMInst(CallMI, BB);
00769   ValueSet::const_iterator LIt = LVSetAft.begin();
00770 
00771   // for each live var in live variable set after machine inst
00772   for( ; LIt != LVSetAft.end(); ++LIt) {
00773     // get the live range corresponding to live var
00774     V9LiveRange *const LR = LRI->getLiveRangeForValue(*LIt);
00775 
00776     // LR can be null if it is a const since a const
00777     // doesn't have a dominating def - see Assumptions above
00778     if (LR) {
00779       if (! LR->isMarkedForSpill()) {
00780         assert(LR->hasColor() && "LR is neither spilled nor colored?");
00781         unsigned RCID = LR->getRegClassID();
00782         unsigned Color = LR->getColor();
00783 
00784         if (MRI.isRegVolatile(RCID, Color) ) {
00785           // if this is a call to the first-level reoptimizer
00786           // instrumentation entry point, and the register is not
00787           // modified by call, don't save and restore it.
00788           if (isLLVMFirstTrigger && !MRI.modifiedByCall(RCID, Color))
00789             continue;
00790 
00791           // if the value is in both LV sets (i.e., live before and after
00792           // the call machine instruction)
00793           unsigned Reg = MRI.getUnifiedRegNum(RCID, Color);
00794 
00795           // if we haven't already pushed this register...
00796           if( PushedRegSet.find(Reg) == PushedRegSet.end() ) {
00797             unsigned RegType = MRI.getRegTypeForLR(LR);
00798 
00799             // Now get two instructions - to push on stack and pop from stack
00800             // and add them to InstrnsBefore and InstrnsAfter of the
00801             // call instruction
00802             int StackOff =
00803               MF->getInfo<SparcV9FunctionInfo>()->pushTempValue(MRI.getSpilledRegSize(RegType));
00804 
00805             //---- Insert code for pushing the reg on stack ----------
00806 
00807             std::vector<MachineInstr*> AdIBef, AdIAft;
00808 
00809             // We may need a scratch register to copy the saved value
00810             // to/from memory.  This may itself have to insert code to
00811             // free up a scratch register.  Any such code should go before
00812             // the save code.  The scratch register, if any, is by default
00813             // temporary and not "used" by the instruction unless the
00814             // copy code itself decides to keep the value in the scratch reg.
00815             int scratchRegType = -1;
00816             int scratchReg = -1;
00817             if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
00818               { // Find a register not live in the LVSet before CallMI
00819                 const ValueSet &LVSetBef =
00820                   LVI->getLiveVarSetBeforeMInst(CallMI, BB);
00821                 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
00822                                                  CallMI, AdIBef, AdIAft);
00823                 assert(scratchReg != MRI.getInvalidRegNum());
00824               }
00825 
00826             if (AdIBef.size() > 0)
00827               instrnsBefore.insert(instrnsBefore.end(),
00828                                    AdIBef.begin(), AdIBef.end());
00829 
00830             MRI.cpReg2MemMI(instrnsBefore, Reg, MRI.getFramePointer(),
00831                             StackOff, RegType, scratchReg);
00832 
00833             if (AdIAft.size() > 0)
00834               instrnsBefore.insert(instrnsBefore.end(),
00835                                    AdIAft.begin(), AdIAft.end());
00836 
00837             //---- Insert code for popping the reg from the stack ----------
00838             AdIBef.clear();
00839             AdIAft.clear();
00840 
00841             // We may need a scratch register to copy the saved value
00842             // from memory.  This may itself have to insert code to
00843             // free up a scratch register.  Any such code should go
00844             // after the save code.  As above, scratch is not marked "used".
00845             scratchRegType = -1;
00846             scratchReg = -1;
00847             if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
00848               { // Find a register not live in the LVSet after CallMI
00849                 scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetAft,
00850                                                  CallMI, AdIBef, AdIAft);
00851                 assert(scratchReg != MRI.getInvalidRegNum());
00852               }
00853 
00854             if (AdIBef.size() > 0)
00855               instrnsAfter.insert(instrnsAfter.end(),
00856                                   AdIBef.begin(), AdIBef.end());
00857 
00858             MRI.cpMem2RegMI(instrnsAfter, MRI.getFramePointer(), StackOff,
00859                             Reg, RegType, scratchReg);
00860 
00861             if (AdIAft.size() > 0)
00862               instrnsAfter.insert(instrnsAfter.end(),
00863                                   AdIAft.begin(), AdIAft.end());
00864 
00865             PushedRegSet.insert(Reg);
00866 
00867             if(DEBUG_RA) {
00868               std::cerr << "\nFor call inst:" << *CallMI;
00869               std::cerr << " -inserted caller saving instrs: Before:\n\t ";
00870               for_each(instrnsBefore.begin(), instrnsBefore.end(),
00871                        std::mem_fun(&MachineInstr::dump));
00872               std::cerr << " -and After:\n\t ";
00873               for_each(instrnsAfter.begin(), instrnsAfter.end(),
00874                        std::mem_fun(&MachineInstr::dump));
00875             }
00876           } // if not already pushed
00877         } // if LR has a volatile color
00878       } // if LR has color
00879     } // if there is a LR for Var
00880   } // for each value in the LV set after instruction
00881 }
00882 
00883 
00884 /// Returns the unified register number of a temporary register to be used
00885 /// BEFORE MInst. If no register is available, it will pick one and modify
00886 /// MIBef and MIAft to contain instructions used to free up this returned
00887 /// register.
00888 ///
00889 int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
00890                                      const ValueSet *LVSetBef,
00891                                      MachineInstr *MInst,
00892                                      std::vector<MachineInstr*>& MIBef,
00893                                      std::vector<MachineInstr*>& MIAft) {
00894   RegClass* RC = getRegClassByID(MRI.getRegClassIDOfRegType(RegType));
00895 
00896   int RegU = getUnusedUniRegAtMI(RC, RegType, MInst, LVSetBef);
00897 
00898   if (RegU == -1) {
00899     // we couldn't find an unused register. Generate code to free up a reg by
00900     // saving it on stack and restoring after the instruction
00901 
00902     int TmpOff = MF->getInfo<SparcV9FunctionInfo>()->pushTempValue(MRI.getSpilledRegSize(RegType));
00903 
00904     RegU = getUniRegNotUsedByThisInst(RC, RegType, MInst);
00905 
00906     // Check if we need a scratch register to copy this register to memory.
00907     int scratchRegType = -1;
00908     if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType)) {
00909         int scratchReg = getUsableUniRegAtMI(scratchRegType, LVSetBef,
00910                                              MInst, MIBef, MIAft);
00911         assert(scratchReg != MRI.getInvalidRegNum());
00912 
00913         // We may as well hold the value in the scratch register instead
00914         // of copying it to memory and back.  But we have to mark the
00915         // register as used by this instruction, so it does not get used
00916         // as a scratch reg. by another operand or anyone else.
00917         ScratchRegsUsed.insert(std::make_pair(MInst, scratchReg));
00918         MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType);
00919         MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType);
00920     } else { // the register can be copied directly to/from memory so do it.
00921         MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType);
00922         MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType);
00923     }
00924   }
00925 
00926   return RegU;
00927 }
00928 
00929 
00930 /// Returns the register-class register number of a new unused register that
00931 /// can be used to accommodate a temporary value.  May be called repeatedly
00932 /// for a single MachineInstr.  On each call, it finds a register which is not
00933 /// live at that instruction and which is not used by any spilled operands of
00934 /// that instruction.
00935 ///
00936 int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC, const int RegType,
00937                                      const MachineInstr *MInst,
00938                                      const ValueSet* LVSetBef) {
00939   RC->clearColorsUsed();     // Reset array
00940 
00941   if (LVSetBef == NULL) {
00942       LVSetBef = &LVI->getLiveVarSetBeforeMInst(MInst);
00943       assert(LVSetBef != NULL && "Unable to get live-var set before MInst?");
00944   }
00945 
00946   ValueSet::const_iterator LIt = LVSetBef->begin();
00947 
00948   // for each live var in live variable set after machine inst
00949   for ( ; LIt != LVSetBef->end(); ++LIt) {
00950     // Get the live range corresponding to live var, and its RegClass
00951     V9LiveRange *const LRofLV = LRI->getLiveRangeForValue(*LIt );
00952 
00953     // LR can be null if it is a const since a const
00954     // doesn't have a dominating def - see Assumptions above
00955     if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor())
00956       RC->markColorsUsed(LRofLV->getColor(),
00957                          MRI.getRegTypeForLR(LRofLV), RegType);
00958   }
00959 
00960   // It is possible that one operand of this MInst was already spilled
00961   // and it received some register temporarily. If that's the case,
00962   // it is recorded in machine operand. We must skip such registers.
00963   setRelRegsUsedByThisInst(RC, RegType, MInst);
00964 
00965   int unusedReg = RC->getUnusedColor(RegType);   // find first unused color
00966   if (unusedReg >= 0)
00967     return MRI.getUnifiedRegNum(RC->getID(), unusedReg);
00968 
00969   return -1;
00970 }
00971 
00972 
00973 /// Return the unified register number of a register in class RC which is not
00974 /// used by any operands of MInst.
00975 ///
00976 int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC,
00977                                             const int RegType,
00978                                             const MachineInstr *MInst) {
00979   RC->clearColorsUsed();
00980 
00981   setRelRegsUsedByThisInst(RC, RegType, MInst);
00982 
00983   // find the first unused color
00984   int unusedReg = RC->getUnusedColor(RegType);
00985   assert(unusedReg >= 0 &&
00986          "FATAL: No free register could be found in reg class!!");
00987 
00988   return MRI.getUnifiedRegNum(RC->getID(), unusedReg);
00989 }
00990 
00991 
00992 /// Modify the IsColorUsedArr of register class RC, by setting the bits
00993 /// corresponding to register RegNo. This is a helper method of
00994 /// setRelRegsUsedByThisInst().
00995 ///
00996 static void markRegisterUsed(int RegNo, RegClass *RC, int RegType,
00997                              const SparcV9RegInfo &TRI) {
00998   unsigned classId = 0;
00999   int classRegNum = TRI.getClassRegNum(RegNo, classId);
01000   if (RC->getID() == classId)
01001     RC->markColorsUsed(classRegNum, RegType, RegType);
01002 }
01003 
01004 void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC, int RegType,
01005                                            const MachineInstr *MI) {
01006   assert(OperandsColoredMap[MI] == true &&
01007          "Illegal to call setRelRegsUsedByThisInst() until colored operands "
01008          "are marked for an instruction.");
01009 
01010   // Add the registers already marked as used by the instruction. Both
01011   // explicit and implicit operands are set.
01012   for (unsigned i = 0, e = MI->getNumOperands(); i != e; ++i)
01013     if (MI->getOperand(i).hasAllocatedReg())
01014       markRegisterUsed(MI->getOperand(i).getReg(), RC, RegType,MRI);
01015 
01016   for (unsigned i = 0, e = MI->getNumImplicitRefs(); i != e; ++i)
01017     if (MI->getImplicitOp(i).hasAllocatedReg())
01018       markRegisterUsed(MI->getImplicitOp(i).getReg(), RC, RegType,MRI);
01019 
01020   // Add all of the scratch registers that are used to save values across the
01021   // instruction (e.g., for saving state register values).
01022   std::pair<ScratchRegsUsedTy::iterator, ScratchRegsUsedTy::iterator>
01023     IR = ScratchRegsUsed.equal_range(MI);
01024   for (ScratchRegsUsedTy::iterator I = IR.first; I != IR.second; ++I)
01025     markRegisterUsed(I->second, RC, RegType, MRI);
01026 
01027   // If there are implicit references, mark their allocated regs as well
01028   for (unsigned z=0; z < MI->getNumImplicitRefs(); z++)
01029     if (const V9LiveRange*
01030         LRofImpRef = LRI->getLiveRangeForValue(MI->getImplicitRef(z)))
01031       if (LRofImpRef->hasColor())
01032         // this implicit reference is in a LR that received a color
01033         RC->markColorsUsed(LRofImpRef->getColor(),
01034                            MRI.getRegTypeForLR(LRofImpRef), RegType);
01035 }
01036 
01037 
01038 /// If there are delay slots for an instruction, the instructions added after
01039 /// it must really go after the delayed instruction(s).  So, we Move the
01040 /// InstrAfter of that instruction to the corresponding delayed instruction
01041 /// using the following method.
01042 ///
01043 void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
01044                                     const MachineInstr *DelayedMI)
01045 {
01046   // "added after" instructions of the original instr
01047   std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter;
01048 
01049   if (DEBUG_RA && OrigAft.size() > 0) {
01050     std::cerr << "\nRegAlloc: Moved InstrnsAfter for: " << *OrigMI;
01051     std::cerr << "         to last delay slot instrn: " << *DelayedMI;
01052   }
01053 
01054   // "added after" instructions of the delayed instr
01055   std::vector<MachineInstr *> &DelayedAft=AddedInstrMap[DelayedMI].InstrnsAfter;
01056 
01057   // go thru all the "added after instructions" of the original instruction
01058   // and append them to the "added after instructions" of the delayed
01059   // instructions
01060   DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());
01061 
01062   // empty the "added after instructions" of the original instruction
01063   OrigAft.clear();
01064 }
01065 
01066 
01067 void PhyRegAlloc::colorIncomingArgs()
01068 {
01069   MRI.colorMethodArgs(Fn, *LRI, AddedInstrAtEntry.InstrnsBefore,
01070                       AddedInstrAtEntry.InstrnsAfter);
01071 }
01072 
01073 
01074 /// Determine whether the suggested color of each live range is really usable,
01075 /// and then call its setSuggestedColorUsable() method to record the answer. A
01076 /// suggested color is NOT usable when the suggested color is volatile AND
01077 /// when there are call interferences.
01078 ///
01079 void PhyRegAlloc::markUnusableSugColors()
01080 {
01081   LiveRangeMapType::const_iterator HMI = (LRI->getLiveRangeMap())->begin();
01082   LiveRangeMapType::const_iterator HMIEnd = (LRI->getLiveRangeMap())->end();
01083 
01084   for (; HMI != HMIEnd ; ++HMI ) {
01085     if (HMI->first) {
01086       V9LiveRange *L = HMI->second;      // get the V9LiveRange
01087       if (L && L->hasSuggestedColor ())
01088         L->setSuggestedColorUsable
01089           (!(MRI.isRegVolatile (L->getRegClassID (), L->getSuggestedColor ())
01090              && L->isCallInterference ()));
01091     }
01092   } // for all LR's in hash map
01093 }
01094 
01095 
01096 /// For each live range that is spilled, allocates a new spill position on the
01097 /// stack, and set the stack offsets of the live range that will be spilled to
01098 /// that position. This must be called just after coloring the LRs.
01099 ///
01100 void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
01101   if (DEBUG_RA) std::cerr << "\nSetting LR stack offsets for spills...\n";
01102 
01103   LiveRangeMapType::const_iterator HMI    = LRI->getLiveRangeMap()->begin();
01104   LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap()->end();
01105 
01106   for ( ; HMI != HMIEnd ; ++HMI) {
01107     if (HMI->first && HMI->second) {
01108       V9LiveRange *L = HMI->second;       // get the V9LiveRange
01109       if (L->isMarkedForSpill()) {      // NOTE: allocating size of long Type **
01110         int stackOffset = MF->getInfo<SparcV9FunctionInfo>()->allocateSpilledValue(Type::LongTy);
01111         L->setSpillOffFromFP(stackOffset);
01112         if (DEBUG_RA)
01113           std::cerr << "  LR# " << L->getUserIGNode()->getIndex()
01114                << ": stack-offset = " << stackOffset << "\n";
01115       }
01116     }
01117   } // for all LR's in hash map
01118 }
01119 
01120 
01121 void PhyRegAlloc::saveStateForValue (std::vector<AllocInfo> &state,
01122                                      const Value *V, int Insn, int Opnd) {
01123   LiveRangeMapType::const_iterator HMI = LRI->getLiveRangeMap ()->find (V);
01124   LiveRangeMapType::const_iterator HMIEnd = LRI->getLiveRangeMap ()->end ();
01125   AllocInfo::AllocStateTy AllocState = AllocInfo::NotAllocated;
01126   int Placement = -1;
01127   if ((HMI != HMIEnd) && HMI->second) {
01128     V9LiveRange *L = HMI->second;
01129     assert ((L->hasColor () || L->isMarkedForSpill ())
01130             && "Live range exists but not colored or spilled");
01131     if (L->hasColor ()) {
01132       AllocState = AllocInfo::Allocated;
01133       Placement = MRI.getUnifiedRegNum (L->getRegClassID (),
01134                                         L->getColor ());
01135     } else if (L->isMarkedForSpill ()) {
01136       AllocState = AllocInfo::Spilled;
01137       assert (L->hasSpillOffset ()
01138               && "Live range marked for spill but has no spill offset");
01139       Placement = L->getSpillOffFromFP ();
01140     }
01141   }
01142   state.push_back (AllocInfo (Insn, Opnd, AllocState, Placement));
01143 }
01144 
01145 
01146 /// Save the global register allocation decisions made by the register
01147 /// allocator so that they can be accessed later (sort of like "poor man's
01148 /// debug info").
01149 ///
01150 void PhyRegAlloc::saveState () {
01151   std::vector<AllocInfo> &state = FnAllocState[Fn];
01152   unsigned ArgNum = 0;
01153   // Arguments encoded as instruction # -1
01154   for (Function::const_arg_iterator i=Fn->arg_begin (), e=Fn->arg_end (); i != e; ++i) {
01155     const Argument *Arg = &*i;
01156     saveStateForValue (state, Arg, -1, ArgNum);
01157     ++ArgNum;
01158   }
01159   unsigned InstCount = 0;
01160   // Instructions themselves encoded as operand # -1
01161   for (const_inst_iterator II=inst_begin (Fn), IE=inst_end (Fn); II!=IE; ++II){
01162     const Instruction *Inst = &*II;
01163     saveStateForValue (state, Inst, InstCount, -1);
01164     if (isa<PHINode> (Inst)) {
01165      MachineCodeForInstruction &MCforPN = MachineCodeForInstruction::get(Inst);
01166      // Last instr should be the copy...figure out what reg it is reading from
01167      if (Value *PhiCpRes = MCforPN.back()->getOperand(0).getVRegValueOrNull()){
01168       if (DEBUG_RA)
01169        std::cerr << "Found Phi copy result: " << PhiCpRes->getName()
01170          << " in: " << *MCforPN.back() << "\n";
01171       saveStateForValue (state, PhiCpRes, InstCount, -2);
01172      }
01173     }
01174     ++InstCount;
01175   }
01176 }
01177 
01178 
01179 bool PhyRegAlloc::doFinalization (Module &M) {
01180   if (SaveRegAllocState) finishSavingState (M);
01181   return false;
01182 }
01183 
01184 
01185 /// Finish the job of saveState(), by collapsing FnAllocState into an LLVM
01186 /// Constant and stuffing it inside the Module.
01187 ///
01188 /// FIXME: There should be other, better ways of storing the saved
01189 /// state; this one is cumbersome and does not work well with the JIT.
01190 ///
01191 void PhyRegAlloc::finishSavingState (Module &M) {
01192   if (DEBUG_RA)
01193     std::cerr << "---- Saving reg. alloc state; SaveStateToModule = "
01194               << SaveStateToModule << " ----\n";
01195 
01196   // If saving state into the module, just copy new elements to the
01197   // correct global.
01198   if (!SaveStateToModule) {
01199     ExportedFnAllocState = FnAllocState;
01200     // FIXME: should ONLY copy new elements in FnAllocState
01201     return;
01202   }
01203 
01204   // Convert FnAllocState to a single Constant array and add it
01205   // to the Module.
01206   ArrayType *AT = ArrayType::get (AllocInfo::getConstantType (), 0);
01207   std::vector<const Type *> TV;
01208   TV.push_back (Type::UIntTy);
01209   TV.push_back (AT);
01210   PointerType *PT = PointerType::get (StructType::get (TV));
01211 
01212   std::vector<Constant *> allstate;
01213   for (Module::iterator I = M.begin (), E = M.end (); I != E; ++I) {
01214     Function *F = I;
01215     if (F->isExternal ()) continue;
01216     if (FnAllocState.find (F) == FnAllocState.end ()) {
01217       allstate.push_back (ConstantPointerNull::get (PT));
01218     } else {
01219       std::vector<AllocInfo> &state = FnAllocState[F];
01220 
01221       // Convert state into an LLVM ConstantArray, and put it in a
01222       // ConstantStruct (named S) along with its size.
01223       std::vector<Constant *> stateConstants;
01224       for (unsigned i = 0, s = state.size (); i != s; ++i)
01225         stateConstants.push_back (state[i].toConstant ());
01226       unsigned Size = stateConstants.size ();
01227       ArrayType *AT = ArrayType::get (AllocInfo::getConstantType (), Size);
01228       std::vector<const Type *> TV;
01229       TV.push_back (Type::UIntTy);
01230       TV.push_back (AT);
01231       StructType *ST = StructType::get (TV);
01232       std::vector<Constant *> CV;
01233       CV.push_back (ConstantUInt::get (Type::UIntTy, Size));
01234       CV.push_back (ConstantArray::get (AT, stateConstants));
01235       Constant *S = ConstantStruct::get (ST, CV);
01236 
01237       GlobalVariable *GV =
01238         new GlobalVariable (ST, true,
01239                             GlobalValue::InternalLinkage, S,
01240                             F->getName () + ".regAllocState", &M);
01241 
01242       // Have: { uint, [Size x { uint, int, uint, int }] } *
01243       // Cast it to: { uint, [0 x { uint, int, uint, int }] } *
01244       Constant *CE = ConstantExpr::getCast (GV, PT);
01245       allstate.push_back (CE);
01246     }
01247   }
01248 
01249   unsigned Size = allstate.size ();
01250   // Final structure type is:
01251   // { uint, [Size x { uint, [0 x { uint, int, uint, int }] } *] }
01252   std::vector<const Type *> TV2;
01253   TV2.push_back (Type::UIntTy);
01254   ArrayType *AT2 = ArrayType::get (PT, Size);
01255   TV2.push_back (AT2);
01256   StructType *ST2 = StructType::get (TV2);
01257   std::vector<Constant *> CV2;
01258   CV2.push_back (ConstantUInt::get (Type::UIntTy, Size));
01259   CV2.push_back (ConstantArray::get (AT2, allstate));
01260   new GlobalVariable (ST2, true, GlobalValue::ExternalLinkage,
01261                       ConstantStruct::get (ST2, CV2), "_llvm_regAllocState",
01262                       &M);
01263 }
01264 
01265 
01266 /// Allocate registers for the machine code previously generated for F using
01267 /// the graph-coloring algorithm.
01268 ///
01269 bool PhyRegAlloc::runOnFunction (Function &F) {
01270   if (DEBUG_RA)
01271     std::cerr << "\n********* Function "<< F.getName () << " ***********\n";
01272 
01273   Fn = &F;
01274   MF = &MachineFunction::get (Fn);
01275   LVI = &getAnalysis<FunctionLiveVarInfo> ();
01276   LRI = new LiveRangeInfo (Fn, TM, RegClassList);
01277   LoopDepthCalc = &getAnalysis<LoopInfo> ();
01278 
01279   // Create each RegClass for the target machine and add it to the
01280   // RegClassList.  This must be done before calling constructLiveRanges().
01281   for (unsigned rc = 0; rc != NumOfRegClasses; ++rc)
01282     RegClassList.push_back (new RegClass (Fn, TM.getRegInfo(),
01283                                           MRI.getMachineRegClass(rc)));
01284 
01285   LRI->constructLiveRanges();            // create LR info
01286   if (DEBUG_RA >= RA_DEBUG_LiveRanges)
01287     LRI->printLiveRanges();
01288 
01289   createIGNodeListsAndIGs();            // create IGNode list and IGs
01290 
01291   buildInterferenceGraphs();            // build IGs in all reg classes
01292 
01293   if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
01294     // print all LRs in all reg classes
01295     for ( unsigned rc=0; rc < NumOfRegClasses  ; rc++)
01296       RegClassList[rc]->printIGNodeList();
01297 
01298     // print IGs in all register classes
01299     for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)
01300       RegClassList[rc]->printIG();
01301   }
01302 
01303   LRI->coalesceLRs();                    // coalesce all live ranges
01304 
01305   if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
01306     // print all LRs in all reg classes
01307     for (unsigned rc=0; rc < NumOfRegClasses; rc++)
01308       RegClassList[rc]->printIGNodeList();
01309 
01310     // print IGs in all register classes
01311     for (unsigned rc=0; rc < NumOfRegClasses; rc++)
01312       RegClassList[rc]->printIG();
01313   }
01314 
01315   // mark un-usable suggested color before graph coloring algorithm.
01316   // When this is done, the graph coloring algo will not reserve
01317   // suggested color unnecessarily - they can be used by another LR
01318   markUnusableSugColors();
01319 
01320   // color all register classes using the graph coloring algo
01321   for (unsigned rc=0; rc < NumOfRegClasses ; rc++)
01322     RegClassList[rc]->colorAllRegs();
01323 
01324   // After graph coloring, if some LRs did not receive a color (i.e, spilled)
01325   // a position for such spilled LRs
01326   allocateStackSpace4SpilledLRs();
01327 
01328   // Reset the temp. area on the stack before use by the first instruction.
01329   // This will also happen after updating each instruction.
01330   MF->getInfo<SparcV9FunctionInfo>()->popAllTempValues();
01331 
01332   // color incoming args - if the correct color was not received
01333   // insert code to copy to the correct register
01334   colorIncomingArgs();
01335 
01336   // Save register allocation state for this function in a Constant.
01337   if (SaveRegAllocState)
01338     saveState();
01339 
01340   // Now update the machine code with register names and add any additional
01341   // code inserted by the register allocator to the instruction stream.
01342   updateMachineCode();
01343 
01344   if (SaveRegAllocState && !SaveStateToModule)
01345     finishSavingState (const_cast<Module&> (*Fn->getParent ()));
01346 
01347   if (DEBUG_RA) {
01348     std::cerr << "\n**** Machine Code After Register Allocation:\n\n";
01349     MF->dump();
01350   }
01351 
01352   // Tear down temporary data structures
01353   for (unsigned rc = 0; rc < NumOfRegClasses; ++rc)
01354     delete RegClassList[rc];
01355   RegClassList.clear ();
01356   AddedInstrMap.clear ();
01357   OperandsColoredMap.clear ();
01358   ScratchRegsUsed.clear ();
01359   AddedInstrAtEntry.clear ();
01360   delete LRI;
01361 
01362   if (DEBUG_RA) std::cerr << "\nRegister allocation complete!\n";
01363   return false;     // Function was not modified
01364 }
01365 
01366 } // End llvm namespace