lib/CodeGen/RegAlloc/PhyRegAlloc.cpp

//===-- PhyRegAlloc.cpp ---------------------------------------------------===//
// 
//  Register allocation for LLVM.
// 
//===----------------------------------------------------------------------===//

#include "llvm/CodeGen/RegisterAllocation.h"
#include "RegAllocCommon.h"
#include "RegClass.h"
#include "llvm/CodeGen/IGNode.h"
#include "llvm/CodeGen/PhyRegAlloc.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineInstrAnnot.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionInfo.h"
#include "llvm/CodeGen/FunctionLiveVarInfo.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetFrameInfo.h"
#include "llvm/Target/TargetInstrInfo.h"
#include "llvm/Target/TargetRegInfo.h"
#include "llvm/Function.h"
#include "llvm/Type.h"
#include "llvm/iOther.h"
#include "Support/STLExtras.h"
#include "Support/CommandLine.h"
#include <math.h>
using std::cerr;
using std::vector;

RegAllocDebugLevel_t DEBUG_RA;

static cl::opt<RegAllocDebugLevel_t, true>
DRA_opt("dregalloc", cl::Hidden, cl::location(DEBUG_RA),
        cl::desc("enable register allocation debugging information"),
        cl::values(
  clEnumValN(RA_DEBUG_None   ,     "n", "disable debug output"),
  clEnumValN(RA_DEBUG_Results,     "y", "debug output for allocation results"),
  clEnumValN(RA_DEBUG_Coloring,    "c", "debug output for graph coloring step"),
  clEnumValN(RA_DEBUG_Interference,"ig","debug output for interference graphs"),
  clEnumValN(RA_DEBUG_LiveRanges , "lr","debug output for live ranges"),
  clEnumValN(RA_DEBUG_Verbose,     "v", "extra debug output"),
                   0));

//----------------------------------------------------------------------------
// RegisterAllocation pass front end...
//----------------------------------------------------------------------------
namespace {
  class RegisterAllocator : public FunctionPass {
    TargetMachine &Target;
  public:
    inline RegisterAllocator(TargetMachine &T) : Target(T) {}

    const char *getPassName() const { return "Register Allocation"; }
    
    bool runOnFunction(Function &F) {
      if (DEBUG_RA)
        cerr << "\n********* Function "<< F.getName() << " ***********\n";
      
      PhyRegAlloc PRA(&F, Target, &getAnalysis<FunctionLiveVarInfo>(),
                      &getAnalysis<LoopInfo>());
      PRA.allocateRegisters();
      
      if (DEBUG_RA) cerr << "\nRegister allocation complete!\n";
      return false;
    }

    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
      AU.addRequired<LoopInfo>();
      AU.addRequired<FunctionLiveVarInfo>();
    }
  };
}

Pass *getRegisterAllocator(TargetMachine &T) {
  return new RegisterAllocator(T);
}

//----------------------------------------------------------------------------
// Constructor: Init local composite objects and create register classes.
//----------------------------------------------------------------------------
PhyRegAlloc::PhyRegAlloc(Function *F, const TargetMachine& tm, 
			 FunctionLiveVarInfo *Lvi, LoopInfo *LDC) 
  :  TM(tm), Fn(F), MF(MachineFunction::get(F)), LVI(Lvi),
     LRI(F, tm, RegClassList), MRI(tm.getRegInfo()),
     NumOfRegClasses(MRI.getNumOfRegClasses()), LoopDepthCalc(LDC) {

  // create each RegisterClass and put in RegClassList
  //
  for (unsigned rc=0; rc != NumOfRegClasses; rc++)  
    RegClassList.push_back(new RegClass(F, &tm.getRegInfo(),
                                        MRI.getMachineRegClass(rc)));
}


//----------------------------------------------------------------------------
// Destructor: Deletes register classes
//----------------------------------------------------------------------------
PhyRegAlloc::~PhyRegAlloc() { 
  for ( unsigned rc=0; rc < NumOfRegClasses; rc++)
    delete RegClassList[rc];

  AddedInstrMap.clear();
} 

//----------------------------------------------------------------------------
// This method initally creates interference graphs (one in each reg class)
// and IGNodeList (one in each IG). The actual nodes will be pushed later. 
//----------------------------------------------------------------------------
void PhyRegAlloc::createIGNodeListsAndIGs() {
  if (DEBUG_RA >= RA_DEBUG_LiveRanges) cerr << "Creating LR lists ...\n";

  // hash map iterator
  LiveRangeMapType::const_iterator HMI = LRI.getLiveRangeMap()->begin();   

  // hash map end
  LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();   

  for (; HMI != HMIEnd ; ++HMI ) {
    if (HMI->first) { 
      LiveRange *L = HMI->second;   // get the LiveRange
      if (!L) { 
        if (DEBUG_RA)
          cerr << "\n**** ?!?WARNING: NULL LIVE RANGE FOUND FOR: "
               << RAV(HMI->first) << "****\n";
        continue;
      }

      // if the Value * is not null, and LR is not yet written to the IGNodeList
      if (!(L->getUserIGNode())  ) {  
        RegClass *const RC =           // RegClass of first value in the LR
          RegClassList[ L->getRegClass()->getID() ];
        RC->addLRToIG(L);              // add this LR to an IG
      }
    }
  }
    
  // init RegClassList
  for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)  
    RegClassList[rc]->createInterferenceGraph();

  if (DEBUG_RA >= RA_DEBUG_LiveRanges) cerr << "LRLists Created!\n";
}


//----------------------------------------------------------------------------
// This method will add all interferences at for a given instruction.
// Interence occurs only if the LR of Def (Inst or Arg) is of the same reg 
// class as that of live var. The live var passed to this function is the 
// LVset AFTER the instruction
//----------------------------------------------------------------------------

void PhyRegAlloc::addInterference(const Value *Def, 
				  const ValueSet *LVSet,
				  bool isCallInst) {

  ValueSet::const_iterator LIt = LVSet->begin();

  // get the live range of instruction
  //
  const LiveRange *const LROfDef = LRI.getLiveRangeForValue( Def );   

  IGNode *const IGNodeOfDef = LROfDef->getUserIGNode();
  assert( IGNodeOfDef );

  RegClass *const RCOfDef = LROfDef->getRegClass(); 

  // for each live var in live variable set
  //
  for ( ; LIt != LVSet->end(); ++LIt) {

    if (DEBUG_RA >= RA_DEBUG_Verbose)
      cerr << "< Def=" << RAV(Def) << ", Lvar=" << RAV(*LIt) << "> ";

    //  get the live range corresponding to live var
    // 
    LiveRange *LROfVar = LRI.getLiveRangeForValue(*LIt);

    // LROfVar can be null if it is a const since a const 
    // doesn't have a dominating def - see Assumptions above
    //
    if (LROfVar)
      if (LROfDef != LROfVar)                  // do not set interf for same LR
        if (RCOfDef == LROfVar->getRegClass()) // 2 reg classes are the same
          RCOfDef->setInterference( LROfDef, LROfVar);  
  }
}



//----------------------------------------------------------------------------
// For a call instruction, this method sets the CallInterference flag in 
// the LR of each variable live int the Live Variable Set live after the
// call instruction (except the return value of the call instruction - since
// the return value does not interfere with that call itself).
//----------------------------------------------------------------------------

void PhyRegAlloc::setCallInterferences(const MachineInstr *MInst, 
				       const ValueSet *LVSetAft) {

  if (DEBUG_RA >= RA_DEBUG_Interference)
    cerr << "\n For call inst: " << *MInst;

  // for each live var in live variable set after machine inst
  //
  for (ValueSet::const_iterator LIt = LVSetAft->begin(), LEnd = LVSetAft->end();
       LIt != LEnd; ++LIt) {

    //  get the live range corresponding to live var
    //
    LiveRange *const LR = LRI.getLiveRangeForValue(*LIt ); 

    // LR can be null if it is a const since a const 
    // doesn't have a dominating def - see Assumptions above
    //
    if (LR ) {  
      if (DEBUG_RA >= RA_DEBUG_Interference) {
        cerr << "\n\tLR after Call: ";
        printSet(*LR);
      }
      LR->setCallInterference();
      if (DEBUG_RA >= RA_DEBUG_Interference) {
	cerr << "\n  ++After adding call interference for LR: " ;
	printSet(*LR);
      }
    }

  }

  // Now find the LR of the return value of the call
  // We do this because, we look at the LV set *after* the instruction
  // to determine, which LRs must be saved across calls. The return value
  // of the call is live in this set - but it does not interfere with call
  // (i.e., we can allocate a volatile register to the return value)
  //
  CallArgsDescriptor* argDesc = CallArgsDescriptor::get(MInst);
  
  if (const Value *RetVal = argDesc->getReturnValue()) {
    LiveRange *RetValLR = LRI.getLiveRangeForValue( RetVal );
    assert( RetValLR && "No LR for RetValue of call");
    RetValLR->clearCallInterference();
  }

  // If the CALL is an indirect call, find the LR of the function pointer.
  // That has a call interference because it conflicts with outgoing args.
  if (const Value *AddrVal = argDesc->getIndirectFuncPtr()) {
    LiveRange *AddrValLR = LRI.getLiveRangeForValue( AddrVal );
    assert( AddrValLR && "No LR for indirect addr val of call");
    AddrValLR->setCallInterference();
  }

}




//----------------------------------------------------------------------------
// This method will walk thru code and create interferences in the IG of
// each RegClass. Also, this method calculates the spill cost of each
// Live Range (it is done in this method to save another pass over the code).
//----------------------------------------------------------------------------
void PhyRegAlloc::buildInterferenceGraphs()
{

  if (DEBUG_RA >= RA_DEBUG_Interference)
    cerr << "Creating interference graphs ...\n";

  unsigned BBLoopDepthCost;
  for (MachineFunction::iterator BBI = MF.begin(), BBE = MF.end();
       BBI != BBE; ++BBI) {
    const MachineBasicBlock &MBB = *BBI;
    const BasicBlock *BB = MBB.getBasicBlock();

    // find the 10^(loop_depth) of this BB 
    //
    BBLoopDepthCost = (unsigned)pow(10.0, LoopDepthCalc->getLoopDepth(BB));

    // get the iterator for machine instructions
    //
    MachineBasicBlock::const_iterator MII = MBB.begin();

    // iterate over all the machine instructions in BB
    //
    for ( ; MII != MBB.end(); ++MII) {
      const MachineInstr *MInst = *MII;

      // get the LV set after the instruction
      //
      const ValueSet &LVSetAI = LVI->getLiveVarSetAfterMInst(MInst, BB);
      bool isCallInst = TM.getInstrInfo().isCall(MInst->getOpCode());

      if (isCallInst ) {
	// set the isCallInterference flag of each live range wich extends
	// accross this call instruction. This information is used by graph
	// coloring algo to avoid allocating volatile colors to live ranges
	// that span across calls (since they have to be saved/restored)
	//
	setCallInterferences(MInst, &LVSetAI);
      }

      // iterate over all MI operands to find defs
      //
      for (MachineInstr::const_val_op_iterator OpI = MInst->begin(),
             OpE = MInst->end(); OpI != OpE; ++OpI) {
       	if (OpI.isDefOnly() || OpI.isDefAndUse()) // create a new LR since def
	  addInterference(*OpI, &LVSetAI, isCallInst);

	// Calculate the spill cost of each live range
	//
	LiveRange *LR = LRI.getLiveRangeForValue(*OpI);
	if (LR) LR->addSpillCost(BBLoopDepthCost);
      } 


      // if there are multiple defs in this instruction e.g. in SETX
      //   
      if (TM.getInstrInfo().isPseudoInstr(MInst->getOpCode()))
      	addInterf4PseudoInstr(MInst);


      // Also add interference for any implicit definitions in a machine
      // instr (currently, only calls have this).
      //
      unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
      for (unsigned z=0; z < NumOfImpRefs; z++) 
        if (MInst->getImplicitOp(z).opIsDefOnly() ||
	    MInst->getImplicitOp(z).opIsDefAndUse())
	  addInterference( MInst->getImplicitRef(z), &LVSetAI, isCallInst );

    } // for all machine instructions in BB
  } // for all BBs in function


  // add interferences for function arguments. Since there are no explict 
  // defs in the function for args, we have to add them manually
  //  
  addInterferencesForArgs();          

  if (DEBUG_RA >= RA_DEBUG_Interference)
    cerr << "Interference graphs calculated!\n";
}



//--------------------------------------------------------------------------
// Pseudo instructions will be exapnded to multiple instructions by the
// assembler. Consequently, all the opernds must get distinct registers.
// Therefore, we mark all operands of a pseudo instruction as they interfere
// with one another.
//--------------------------------------------------------------------------
void PhyRegAlloc::addInterf4PseudoInstr(const MachineInstr *MInst) {

  bool setInterf = false;

  // iterate over  MI operands to find defs
  //
  for (MachineInstr::const_val_op_iterator It1 = MInst->begin(),
         ItE = MInst->end(); It1 != ItE; ++It1) {
    const LiveRange *LROfOp1 = LRI.getLiveRangeForValue(*It1); 
    assert((LROfOp1 || !It1.isUseOnly())&& "No LR for Def in PSEUDO insruction");

    MachineInstr::const_val_op_iterator It2 = It1;
    for (++It2; It2 != ItE; ++It2) {
      const LiveRange *LROfOp2 = LRI.getLiveRangeForValue(*It2); 

      if (LROfOp2) {
	RegClass *RCOfOp1 = LROfOp1->getRegClass(); 
	RegClass *RCOfOp2 = LROfOp2->getRegClass(); 
 
	if (RCOfOp1 == RCOfOp2 ){ 
	  RCOfOp1->setInterference( LROfOp1, LROfOp2 );  
	  setInterf = true;
	}
      } // if Op2 has a LR
    } // for all other defs in machine instr
  } // for all operands in an instruction

  if (!setInterf && MInst->getNumOperands() > 2) {
    cerr << "\nInterf not set for any operand in pseudo instr:\n";
    cerr << *MInst;
    assert(0 && "Interf not set for pseudo instr with > 2 operands" );
  }
} 



//----------------------------------------------------------------------------
// This method will add interferences for incoming arguments to a function.
//----------------------------------------------------------------------------

void PhyRegAlloc::addInterferencesForArgs() {
  // get the InSet of root BB
  const ValueSet &InSet = LVI->getInSetOfBB(&Fn->front());  

  for (Function::const_aiterator AI = Fn->abegin(); AI != Fn->aend(); ++AI) {
    // add interferences between args and LVars at start 
    addInterference(AI, &InSet, false);
    
    if (DEBUG_RA >= RA_DEBUG_Interference)
      cerr << " - %% adding interference for  argument " << RAV(AI) << "\n";
  }
}


//----------------------------------------------------------------------------
// This method is called after register allocation is complete to set the
// allocated reisters in the machine code. This code will add register numbers
// to MachineOperands that contain a Value. Also it calls target specific
// methods to produce caller saving instructions. At the end, it adds all
// additional instructions produced by the register allocator to the 
// instruction stream. 
//----------------------------------------------------------------------------

//-----------------------------
// Utility functions used below
//-----------------------------
inline void
InsertBefore(MachineInstr* newMI,
             MachineBasicBlock& MBB,
             MachineBasicBlock::iterator& MII)
{
  MII = MBB.insert(MII, newMI);
  ++MII;
}

inline void
InsertAfter(MachineInstr* newMI,
            MachineBasicBlock& MBB,
            MachineBasicBlock::iterator& MII)
{
  ++MII;    // insert before the next instruction
  MII = MBB.insert(MII, newMI);
}

inline void
DeleteInstruction(MachineBasicBlock& MBB,
                  MachineBasicBlock::iterator& MII)
{
  MII = MBB.erase(MII);
}

inline void
SubstituteInPlace(MachineInstr* newMI,
                  MachineBasicBlock& MBB,
                  MachineBasicBlock::iterator MII)
{
  *MII = newMI;
}

inline void
PrependInstructions(vector<MachineInstr *> &IBef,
                    MachineBasicBlock& MBB,
                    MachineBasicBlock::iterator& MII,
                    const std::string& msg)
{
  if (!IBef.empty())
    {
      MachineInstr* OrigMI = *MII;
      std::vector<MachineInstr *>::iterator AdIt; 
      for (AdIt = IBef.begin(); AdIt != IBef.end() ; ++AdIt)
        {
          if (DEBUG_RA) {
            if (OrigMI) cerr << "For MInst:\n  " << *OrigMI;
            cerr << msg << "PREPENDed instr:\n  " << **AdIt << "\n";
          }
          InsertBefore(*AdIt, MBB, MII);
        }
    }
}

inline void
AppendInstructions(std::vector<MachineInstr *> &IAft,
                   MachineBasicBlock& MBB,
                   MachineBasicBlock::iterator& MII,
                   const std::string& msg)
{
  if (!IAft.empty())
    {
      MachineInstr* OrigMI = *MII;
      std::vector<MachineInstr *>::iterator AdIt; 
      for ( AdIt = IAft.begin(); AdIt != IAft.end() ; ++AdIt )
        {
          if (DEBUG_RA) {
            if (OrigMI) cerr << "For MInst:\n  " << *OrigMI;
            cerr << msg << "APPENDed instr:\n  "  << **AdIt << "\n";
          }
          InsertAfter(*AdIt, MBB, MII);
        }
    }
}

void PhyRegAlloc::updateInstruction(MachineInstr* MInst, BasicBlock* BB)
{
  unsigned Opcode = MInst->getOpCode();
  
  // Reset tmp stack positions so they can be reused for each machine instr.
  MF.getInfo()->popAllTempValues();  
      
  // First, set the registers for operands in the machine instruction
  // if a register was successfully allocated.  Do this first because we
  // will need to know which registers are already used by this instr'n.
  // 
  for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
    {
      MachineOperand& Op = MInst->getOperand(OpNum);
      if (Op.getType() ==  MachineOperand::MO_VirtualRegister || 
          Op.getType() ==  MachineOperand::MO_CCRegister)
        {
          const Value *const Val =  Op.getVRegValue();
          if (const LiveRange* LR = LRI.getLiveRangeForValue(Val))
            if (LR->hasColor())
              MInst->SetRegForOperand(OpNum,
                          MRI.getUnifiedRegNum(LR->getRegClass()->getID(),
                                               LR->getColor()));
        }
    } // for each operand
  
  // Mark that the operands have been updated.  setRelRegsUsedByThisInst()
  // is called to find registers used by each MachineInst, and it should not
  // be used for an instruction until this is done.  This flag just serves
  // as a sanity check.
  OperandsColoredMap[MInst] = true;

  // Now insert caller-saving code before/after the call.
  // Do this before inserting spill code since some registers must be
  // used by save/restore and spill code should not use those registers.
  //
  if (TM.getInstrInfo().isCall(Opcode)) {
    AddedInstrns &AI = AddedInstrMap[MInst];
    MRI.insertCallerSavingCode(AI.InstrnsBefore, AI.InstrnsAfter,
                               MInst, BB, *this);
  }

  // Now insert spill code for remaining operands not allocated to
  // registers.  This must be done even for call return instructions
  // since those are not handled by the special code above.
  for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum)
    {
      MachineOperand& Op = MInst->getOperand(OpNum);
      if (Op.getType() ==  MachineOperand::MO_VirtualRegister || 
          Op.getType() ==  MachineOperand::MO_CCRegister)
        {
          const Value* Val = Op.getVRegValue();
          if (const LiveRange *LR = LRI.getLiveRangeForValue(Val))
            if (LR->isMarkedForSpill())
              insertCode4SpilledLR(LR, MInst, BB, OpNum);
        }
    } // for each operand
}

void PhyRegAlloc::updateMachineCode()
{
  // Insert any instructions needed at method entry
  MachineBasicBlock::iterator MII = MF.front().begin();
  PrependInstructions(AddedInstrAtEntry.InstrnsBefore, MF.front(), MII,
                      "At function entry: \n");
  assert(AddedInstrAtEntry.InstrnsAfter.empty() &&
         "InstrsAfter should be unnecessary since we are just inserting at "
         "the function entry point here.");
  
  for (MachineFunction::iterator BBI = MF.begin(), BBE = MF.end();
       BBI != BBE; ++BBI) {

    MachineBasicBlock &MBB = *BBI;

    // Iterate over all machine instructions in BB and mark operands with
    // their assigned registers or insert spill code, as appropriate. 
    // Also, fix operands of call/return instructions.
    // 
    for (MachineBasicBlock::iterator MII = MBB.begin(); MII != MBB.end(); ++MII)
      if (!TM.getInstrInfo().isDummyPhiInstr((*MII)->getOpCode()))// ignore Phis
        updateInstruction(*MII, MBB.getBasicBlock());

    // Now, move code out of delay slots of branches and returns if needed.
    // (Also, move "after" code from calls to the last delay slot instruction.)
    // Moving code out of delay slots is needed in 2 situations:
    // (1) If this is a branch and it needs instructions inserted after it,
    //     move any existing instructions out of the delay slot so that the
    //     instructions can go into the delay slot.  This only supports the
    //     case that #instrsAfter <= #delay slots.
    // 
    // (2) If any instruction in the delay slot needs
    //     instructions inserted, move it out of the delay slot and before the
    //     branch because putting code before or after it would be VERY BAD!
    // 
    // If the annul bit of the branch is set, neither of these is legal!
    // If so, we need to handle spill differently but annulling is not yet used.
    //
    for (MachineBasicBlock::iterator MII = MBB.begin();
         MII != MBB.end(); ++MII)
      if (unsigned delaySlots =
          TM.getInstrInfo().getNumDelaySlots((*MII)->getOpCode()))
        { 
          assert(delaySlots==1 && "Not handling multiple delay slots!");

          MachineInstr *MInst = *MII; 
          MachineInstr *MDelayInst = *(MII+1); 

          // Check the 2 conditions above:
          // (1) Does a branch need instructions added after it?
          // (2) O/w does delay slot instr. need instrns before or after?
          bool isBranch = (TM.getInstrInfo().isBranch((*MII)->getOpCode()) ||
                           TM.getInstrInfo().isReturn((*MII)->getOpCode()));
          bool cond1 = isBranch && AddedInstrMap[MInst].InstrnsAfter.size() > 0;
          bool cond2 = (AddedInstrMap.count(MDelayInst) ||
                        AddedInstrMap[MDelayInst].InstrnsAfter.size() > 0);

          if (cond1 || cond2)
            {
              // Move delay slot instrn before the preceding branch.
              // InsertBefore() modifies MII to point to the branch again.
              assert(((*MII)->getOpCodeFlags() & AnnulFlag) == 0 &&
                     "FIXME: Annul bit must be turned off here!");
              InsertBefore(MDelayInst, MBB, MII);

              // In case (1), delete it and don't replace with anything!
              // Otherwise (i.e., case (2) only) replace it with a NOP.
              if (cond1) {
                assert(AddedInstrMap[MInst].InstrnsAfter.size() <= delaySlots &&
                       "Cannot put more than #delaySlots spill instrns after "
                       "branch or return! Need to handle spill differently.");
                DeleteInstruction(MBB, MII); // MII now points to next inst.
              }
              else {
                MachineInstr* nopI =BuildMI(TM.getInstrInfo().getNOPOpCode(),1);
                SubstituteInPlace(nopI, MBB, MII+1); // replace with NOP
              }
            }

          // If this is not a branch or return (probably a call),
          // the Instrnsafter, if any, must really go after the last
          // delay slot.  Move the InstrAfter to the instr. in that slot.
          // We must do this after the previous code because the instructions
          // in delay slots may get moved out by that code.
          // 
          if (!isBranch)
            move2DelayedInstr(MInst,  *(MII+delaySlots));
        }

    // Finally iterate over all instructions in BB and insert before/after
    // 
    for (MachineBasicBlock::iterator MII=MBB.begin(); MII != MBB.end(); ++MII) {
      MachineInstr *MInst = *MII; 

      // do not process Phis
      if (TM.getInstrInfo().isDummyPhiInstr(MInst->getOpCode()))
	continue;

      // if there are any added instructions...
      if (AddedInstrMap.count(MInst)) {
        AddedInstrns &CallAI = AddedInstrMap[MInst];

#ifndef NDEBUG
        // Temporary sanity checking code to detect whether the same machine
        // instruction is ever inserted twice before/after a call.
        // I suspect this is happening but am not sure. --Vikram, 7/1/03.
        // 
        std::set<const MachineInstr*> instrsSeen;
        for (int i = 0, N = CallAI.InstrnsBefore.size(); i < N; ++i) {
          assert(instrsSeen.count(CallAI.InstrnsBefore[i]) == 0 &&
                 "Duplicate machine instruction in InstrnsBefore!");
          instrsSeen.insert(CallAI.InstrnsBefore[i]);
        } 
        for (int i = 0, N = CallAI.InstrnsAfter.size(); i < N; ++i) {
          assert(instrsSeen.count(CallAI.InstrnsAfter[i]) == 0 &&
                 "Duplicate machine instruction in InstrnsBefore/After!");
          instrsSeen.insert(CallAI.InstrnsAfter[i]);
        } 
#endif

        // Now add the instructions before/after this MI.
        // We do this here to ensure that spill for an instruction is inserted
        // as close as possible to an instruction (see above insertCode4Spill)
        //      
        if (! CallAI.InstrnsBefore.empty())
          PrependInstructions(CallAI.InstrnsBefore, MBB, MII,"");
        
        if (! CallAI.InstrnsAfter.empty())
          AppendInstructions(CallAI.InstrnsAfter, MBB, MII,"");

      } // if there are any added instructions

    } // for each machine instruction
  }
}



//----------------------------------------------------------------------------
// This method inserts spill code for AN operand whose LR was spilled.
// This method may be called several times for a single machine instruction
// if it contains many spilled operands. Each time it is called, it finds
// a register which is not live at that instruction and also which is not
// used by other spilled operands of the same instruction. Then it uses
// this register temporarily to accomodate the spilled value.
//----------------------------------------------------------------------------

void PhyRegAlloc::insertCode4SpilledLR(const LiveRange *LR, 
				       MachineInstr *MInst,
				       const BasicBlock *BB,
				       const unsigned OpNum) {

  assert((! TM.getInstrInfo().isCall(MInst->getOpCode()) || OpNum == 0) &&
         "Outgoing arg of a call must be handled elsewhere (func arg ok)");
  assert(! TM.getInstrInfo().isReturn(MInst->getOpCode()) &&
	 "Return value of a ret must be handled elsewhere");

  MachineOperand& Op = MInst->getOperand(OpNum);
  bool isDef =  Op.opIsDefOnly();
  bool isDefAndUse = Op.opIsDefAndUse();
  unsigned RegType = MRI.getRegTypeForLR(LR);
  int SpillOff = LR->getSpillOffFromFP();
  RegClass *RC = LR->getRegClass();
  const ValueSet &LVSetBef = LVI->getLiveVarSetBeforeMInst(MInst, BB);

  MF.getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType) );
  
  vector<MachineInstr*> MIBef, MIAft;
  vector<MachineInstr*> AdIMid;
  
  // Choose a register to hold the spilled value, if one was not preallocated.
  // This may insert code before and after MInst to free up the value.  If so,
  // this code should be first/last in the spill sequence before/after MInst.
  int TmpRegU=(LR->hasColor()
               ? MRI.getUnifiedRegNum(LR->getRegClass()->getID(),LR->getColor())
               : getUsableUniRegAtMI(RegType, &LVSetBef, MInst, MIBef,MIAft));
  
  // Set the operand first so that it this register does not get used
  // as a scratch register for later calls to getUsableUniRegAtMI below
  MInst->SetRegForOperand(OpNum, TmpRegU);
  
  // get the added instructions for this instruction
  AddedInstrns &AI = AddedInstrMap[MInst];

  // We may need a scratch register to copy the spilled value to/from memory.
  // This may itself have to insert code to free up a scratch register.  
  // Any such code should go before (after) the spill code for a load (store).
  // The scratch reg is not marked as used because it is only used
  // for the copy and not used across MInst.
  int scratchRegType = -1;
  int scratchReg = -1;
  if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
    {
      scratchReg = getUsableUniRegAtMI(scratchRegType, &LVSetBef,
                                       MInst, MIBef, MIAft);
      assert(scratchReg != MRI.getInvalidRegNum());
    }
  
  if (!isDef || isDefAndUse) {
    // for a USE, we have to load the value of LR from stack to a TmpReg
    // and use the TmpReg as one operand of instruction
    
    // actual loading instruction(s)
    MRI.cpMem2RegMI(AdIMid, MRI.getFramePointer(), SpillOff, TmpRegU, RegType,
                    scratchReg);
    
    // the actual load should be after the instructions to free up TmpRegU
    MIBef.insert(MIBef.end(), AdIMid.begin(), AdIMid.end());
    AdIMid.clear();
  }
  
  if (isDef || isDefAndUse) {   // if this is a Def
    // for a DEF, we have to store the value produced by this instruction
    // on the stack position allocated for this LR
    
    // actual storing instruction(s)
    MRI.cpReg2MemMI(AdIMid, TmpRegU, MRI.getFramePointer(), SpillOff, RegType,
                    scratchReg);
    
    MIAft.insert(MIAft.begin(), AdIMid.begin(), AdIMid.end());
  }  // if !DEF
  
  // Finally, insert the entire spill code sequences before/after MInst
  AI.InstrnsBefore.insert(AI.InstrnsBefore.end(), MIBef.begin(), MIBef.end());
  AI.InstrnsAfter.insert(AI.InstrnsAfter.begin(), MIAft.begin(), MIAft.end());
  
  if (DEBUG_RA) {
    cerr << "\nFor Inst:\n  " << *MInst;
    cerr << "SPILLED LR# " << LR->getUserIGNode()->getIndex();
    cerr << "; added Instructions:";
    for_each(MIBef.begin(), MIBef.end(), std::mem_fun(&MachineInstr::dump));
    for_each(MIAft.begin(), MIAft.end(), std::mem_fun(&MachineInstr::dump));
  }
}


//----------------------------------------------------------------------------
// We can use the following method to get a temporary register to be used
// BEFORE any given machine instruction. If there is a register available,
// this method will simply return that register and set MIBef = MIAft = NULL.
// Otherwise, it will return a register and MIAft and MIBef will contain
// two instructions used to free up this returned register.
// Returned register number is the UNIFIED register number
//----------------------------------------------------------------------------

int PhyRegAlloc::getUsableUniRegAtMI(const int RegType,
                                     const ValueSet *LVSetBef,
                                     MachineInstr *MInst, 
                                     std::vector<MachineInstr*>& MIBef,
                                     std::vector<MachineInstr*>& MIAft) {
  
  RegClass* RC = getRegClassByID(MRI.getRegClassIDOfRegType(RegType));
  
  int RegU =  getUnusedUniRegAtMI(RC, RegType, MInst, LVSetBef);
  
  if (RegU == -1) {
    // we couldn't find an unused register. Generate code to free up a reg by
    // saving it on stack and restoring after the instruction
    
    int TmpOff = MF.getInfo()->pushTempValue(MRI.getSpilledRegSize(RegType));
    
    RegU = getUniRegNotUsedByThisInst(RC, RegType, MInst);
    
    // Check if we need a scratch register to copy this register to memory.
    int scratchRegType = -1;
    if (MRI.regTypeNeedsScratchReg(RegType, scratchRegType))
      {
        int scratchReg = getUsableUniRegAtMI(scratchRegType, LVSetBef,
                                             MInst, MIBef, MIAft);
        assert(scratchReg != MRI.getInvalidRegNum());
        
        // We may as well hold the value in the scratch register instead
        // of copying it to memory and back.  But we have to mark the
        // register as used by this instruction, so it does not get used
        // as a scratch reg. by another operand or anyone else.
        MInst->insertUsedReg(scratchReg); 
        MRI.cpReg2RegMI(MIBef, RegU, scratchReg, RegType);
        MRI.cpReg2RegMI(MIAft, scratchReg, RegU, RegType);
      }
    else
      { // the register can be copied directly to/from memory so do it.
        MRI.cpReg2MemMI(MIBef, RegU, MRI.getFramePointer(), TmpOff, RegType);
        MRI.cpMem2RegMI(MIAft, MRI.getFramePointer(), TmpOff, RegU, RegType);
      }
  }
  
  return RegU;
}

//----------------------------------------------------------------------------
// This method is called to get a new unused register that can be used to
// accomodate a spilled value. 
// This method may be called several times for a single machine instruction
// if it contains many spilled operands. Each time it is called, it finds
// a register which is not live at that instruction and also which is not
// used by other spilled operands of the same instruction.
// Return register number is relative to the register class. NOT
// unified number
//----------------------------------------------------------------------------

int PhyRegAlloc::getUnusedUniRegAtMI(RegClass *RC, 
                                     const int RegType,
                                     const MachineInstr *MInst, 
                                     const ValueSet *LVSetBef) {
  
  RC->clearColorsUsed();     // Reset array
  
  ValueSet::const_iterator LIt = LVSetBef->begin();

  // for each live var in live variable set after machine inst
  for ( ; LIt != LVSetBef->end(); ++LIt) {

   //  get the live range corresponding to live var, and its RegClass
    LiveRange *const LRofLV = LRI.getLiveRangeForValue(*LIt );    

    // LR can be null if it is a const since a const 
    // doesn't have a dominating def - see Assumptions above
    if (LRofLV && LRofLV->getRegClass() == RC && LRofLV->hasColor())
      RC->markColorsUsed(LRofLV->getColor(),
                         MRI.getRegTypeForLR(LRofLV), RegType);
  }

  // It is possible that one operand of this MInst was already spilled
  // and it received some register temporarily. If that's the case,
  // it is recorded in machine operand. We must skip such registers.
  // 
  setRelRegsUsedByThisInst(RC, RegType, MInst);

  int unusedReg = RC->getUnusedColor(RegType);   // find first unused color
  if (unusedReg >= 0)
    return MRI.getUnifiedRegNum(RC->getID(), unusedReg);

  return -1;
}


//----------------------------------------------------------------------------
// Get any other register in a register class, other than what is used
// by operands of a machine instruction. Returns the unified reg number.
//----------------------------------------------------------------------------
int PhyRegAlloc::getUniRegNotUsedByThisInst(RegClass *RC, 
                                            const int RegType,
                                            const MachineInstr *MInst) {
  RC->clearColorsUsed();

  setRelRegsUsedByThisInst(RC, RegType, MInst);

  // find the first unused color
  int unusedReg = RC->getUnusedColor(RegType);
  assert(unusedReg >= 0 &&
         "FATAL: No free register could be found in reg class!!");

  return MRI.getUnifiedRegNum(RC->getID(), unusedReg);
}


//----------------------------------------------------------------------------
// This method modifies the IsColorUsedArr of the register class passed to it.
// It sets the bits corresponding to the registers used by this machine
// instructions. Both explicit and implicit operands are set.
//----------------------------------------------------------------------------

void PhyRegAlloc::setRelRegsUsedByThisInst(RegClass *RC, 
                                           const int RegType,
                                           const MachineInstr *MInst )
{
  assert(OperandsColoredMap[MInst] == true &&
         "Illegal to call setRelRegsUsedByThisInst() until colored operands "
         "are marked for an instruction.");

  // Add the registers already marked as used by the instruction. 
  // This should include any scratch registers that are used to save
  // values across the instruction (e.g., for saving state register values).
  const std::set<int> &regsUsed = MInst->getRegsUsed();
  for (std::set<int>::iterator I=regsUsed.begin(),E=regsUsed.end(); I != E; ++I)
    {
      int i = *I;
      unsigned classId = 0;
      int classRegNum = MRI.getClassRegNum(i, classId);
      if (RC->getID() == classId)
        RC->markColorsUsed(classRegNum, RegType, RegType);
    }

  // If there are implicit references, mark their allocated regs as well
  // 
  for (unsigned z=0; z < MInst->getNumImplicitRefs(); z++)
    if (const LiveRange*
        LRofImpRef = LRI.getLiveRangeForValue(MInst->getImplicitRef(z)))    
      if (LRofImpRef->hasColor())
        // this implicit reference is in a LR that received a color
        RC->markColorsUsed(LRofImpRef->getColor(),
                           MRI.getRegTypeForLR(LRofImpRef), RegType);
}


//----------------------------------------------------------------------------
// If there are delay slots for an instruction, the instructions
// added after it must really go after the delayed instruction(s).
// So, we move the InstrAfter of that instruction to the 
// corresponding delayed instruction using the following method.
//----------------------------------------------------------------------------

void PhyRegAlloc::move2DelayedInstr(const MachineInstr *OrigMI,
                                    const MachineInstr *DelayedMI)
{
  // "added after" instructions of the original instr
  std::vector<MachineInstr *> &OrigAft = AddedInstrMap[OrigMI].InstrnsAfter;

  // "added after" instructions of the delayed instr
  std::vector<MachineInstr *> &DelayedAft =AddedInstrMap[DelayedMI].InstrnsAfter;

  // go thru all the "added after instructions" of the original instruction
  // and append them to the "added after instructions" of the delayed
  // instructions
  DelayedAft.insert(DelayedAft.end(), OrigAft.begin(), OrigAft.end());

  // empty the "added after instructions" of the original instruction
  OrigAft.clear();
}

//----------------------------------------------------------------------------
// This method prints the code with registers after register allocation is
// complete.
//----------------------------------------------------------------------------
void PhyRegAlloc::printMachineCode()
{

  cerr << "\n;************** Function " << Fn->getName()
       << " *****************\n";

  for (MachineFunction::iterator BBI = MF.begin(), BBE = MF.end();
       BBI != BBE; ++BBI) {
    cerr << "\n"; printLabel(BBI->getBasicBlock()); cerr << ": ";

    // get the iterator for machine instructions
    MachineBasicBlock& MBB = *BBI;
    MachineBasicBlock::iterator MII = MBB.begin();

    // iterate over all the machine instructions in BB
    for ( ; MII != MBB.end(); ++MII) {  
      MachineInstr *MInst = *MII; 

      cerr << "\n\t";
      cerr << TM.getInstrInfo().getName(MInst->getOpCode());

      for (unsigned OpNum=0; OpNum < MInst->getNumOperands(); ++OpNum) {
	MachineOperand& Op = MInst->getOperand(OpNum);

	if (Op.getType() ==  MachineOperand::MO_VirtualRegister || 
	    Op.getType() ==  MachineOperand::MO_CCRegister /*|| 
	    Op.getType() ==  MachineOperand::MO_PCRelativeDisp*/ ) {

	  const Value *const Val = Op.getVRegValue () ;
	  // ****this code is temporary till NULL Values are fixed
	  if (! Val ) {
	    cerr << "\t<*NULL*>";
	    continue;
	  }

	  // if a label or a constant
	  if (isa<BasicBlock>(Val)) {
	    cerr << "\t"; printLabel(	Op.getVRegValue	() );
	  } else {
	    // else it must be a register value
	    const int RegNum = Op.getAllocatedRegNum();

	    cerr << "\t" << "%" << MRI.getUnifiedRegName( RegNum );
	    if (Val->hasName() )
	      cerr << "(" << Val->getName() << ")";
	    else 
	      cerr << "(" << Val << ")";

	    if (Op.opIsDefOnly() || Op.opIsDefAndUse())
	      cerr << "*";

	    const LiveRange *LROfVal = LRI.getLiveRangeForValue(Val);
	    if (LROfVal )
	      if (LROfVal->hasSpillOffset() )
		cerr << "$";
	  }

	} 
	else if (Op.getType() ==  MachineOperand::MO_MachineRegister) {
	  cerr << "\t" << "%" << MRI.getUnifiedRegName(Op.getMachineRegNum());
	}

	else 
	  cerr << "\t" << Op;      // use dump field
      }

    

      unsigned NumOfImpRefs =  MInst->getNumImplicitRefs();
      if (NumOfImpRefs > 0) {
	cerr << "\tImplicit:";

	for (unsigned z=0; z < NumOfImpRefs; z++)
	  cerr << RAV(MInst->getImplicitRef(z)) << "\t";
      }

    } // for all machine instructions

    cerr << "\n";

  } // for all BBs

  cerr << "\n";
}


//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
void PhyRegAlloc::colorIncomingArgs()
{
  MRI.colorMethodArgs(Fn, LRI, &AddedInstrAtEntry);
}


//----------------------------------------------------------------------------
// Used to generate a label for a basic block
//----------------------------------------------------------------------------
void PhyRegAlloc::printLabel(const Value *Val) {
  if (Val->hasName())
    cerr  << Val->getName();
  else
    cerr << "Label" << Val;
}


//----------------------------------------------------------------------------
// This method calls setSugColorUsable method of each live range. This
// will determine whether the suggested color of LR is  really usable.
// A suggested color is not usable when the suggested color is volatile
// AND when there are call interferences
//----------------------------------------------------------------------------

void PhyRegAlloc::markUnusableSugColors()
{
  // hash map iterator
  LiveRangeMapType::const_iterator HMI = (LRI.getLiveRangeMap())->begin();   
  LiveRangeMapType::const_iterator HMIEnd = (LRI.getLiveRangeMap())->end();   

    for (; HMI != HMIEnd ; ++HMI ) {
      if (HMI->first) { 
	LiveRange *L = HMI->second;      // get the LiveRange
	if (L) { 
	  if (L->hasSuggestedColor()) {
	    int RCID = L->getRegClass()->getID();
	    if (MRI.isRegVolatile( RCID,  L->getSuggestedColor()) &&
		L->isCallInterference() )
	      L->setSuggestedColorUsable( false );
	    else
	      L->setSuggestedColorUsable( true );
	  }
	} // if L->hasSuggestedColor()
      }
    } // for all LR's in hash map
}



//----------------------------------------------------------------------------
// The following method will set the stack offsets of the live ranges that
// are decided to be spillled. This must be called just after coloring the
// LRs using the graph coloring algo. For each live range that is spilled,
// this method allocate a new spill position on the stack.
//----------------------------------------------------------------------------

void PhyRegAlloc::allocateStackSpace4SpilledLRs() {
  if (DEBUG_RA) cerr << "\nSetting LR stack offsets for spills...\n";

  LiveRangeMapType::const_iterator HMI    = LRI.getLiveRangeMap()->begin();   
  LiveRangeMapType::const_iterator HMIEnd = LRI.getLiveRangeMap()->end();   

  for ( ; HMI != HMIEnd ; ++HMI) {
    if (HMI->first && HMI->second) {
      LiveRange *L = HMI->second;       // get the LiveRange
      if (L->isMarkedForSpill()) {      // NOTE: allocating size of long Type **
        int stackOffset = MF.getInfo()->allocateSpilledValue(Type::LongTy);
        L->setSpillOffFromFP(stackOffset);
        if (DEBUG_RA)
          cerr << "  LR# " << L->getUserIGNode()->getIndex()
               << ": stack-offset = " << stackOffset << "\n";
      }
    }
  } // for all LR's in hash map
}



//----------------------------------------------------------------------------
// The entry pont to Register Allocation
//----------------------------------------------------------------------------

void PhyRegAlloc::allocateRegisters()
{

  // make sure that we put all register classes into the RegClassList 
  // before we call constructLiveRanges (now done in the constructor of 
  // PhyRegAlloc class).
  //
  LRI.constructLiveRanges();            // create LR info

  if (DEBUG_RA >= RA_DEBUG_LiveRanges)
    LRI.printLiveRanges();
  
  createIGNodeListsAndIGs();            // create IGNode list and IGs

  buildInterferenceGraphs();            // build IGs in all reg classes
  
  
  if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
    // print all LRs in all reg classes
    for ( unsigned rc=0; rc < NumOfRegClasses  ; rc++)  
      RegClassList[rc]->printIGNodeList(); 
    
    // print IGs in all register classes
    for ( unsigned rc=0; rc < NumOfRegClasses ; rc++)  
      RegClassList[rc]->printIG();       
  }

  LRI.coalesceLRs();                    // coalesce all live ranges

  if (DEBUG_RA >= RA_DEBUG_LiveRanges) {
    // print all LRs in all reg classes
    for (unsigned rc=0; rc < NumOfRegClasses; rc++)
      RegClassList[rc]->printIGNodeList();
    
    // print IGs in all register classes
    for (unsigned rc=0; rc < NumOfRegClasses; rc++)
      RegClassList[rc]->printIG();
  }


  // mark un-usable suggested color before graph coloring algorithm.
  // When this is done, the graph coloring algo will not reserve
  // suggested color unnecessarily - they can be used by another LR
  //
  markUnusableSugColors(); 

  // color all register classes using the graph coloring algo
  for (unsigned rc=0; rc < NumOfRegClasses ; rc++)  
    RegClassList[rc]->colorAllRegs();    

  // Atter graph coloring, if some LRs did not receive a color (i.e, spilled)
  // a poistion for such spilled LRs
  //
  allocateStackSpace4SpilledLRs();

  // Reset the temp. area on the stack before use by the first instruction.
  // This will also happen after updating each instruction.
  MF.getInfo()->popAllTempValues();

  // color incoming args - if the correct color was not received
  // insert code to copy to the correct register
  //
  colorIncomingArgs();

  // Now update the machine code with register names and add any 
  // additional code inserted by the register allocator to the instruction
  // stream
  //
  updateMachineCode(); 

  if (DEBUG_RA) {
    cerr << "\n**** Machine Code After Register Allocation:\n\n";
    MF.dump();
  }
}