2 files changed, 182 insertions, 166 deletions

diff --git a/llvm/lib/CodeGen/InstrSelection/InstrSelection.cpp b/llvm/lib/CodeGen/InstrSelection/InstrSelection.cpp
index 7153b3cdd12..339ba6474cc 100644
--- a/llvm/lib/CodeGen/InstrSelection/InstrSelection.cpp
+++ b/llvm/lib/CodeGen/InstrSelection/InstrSelection.cpp
@@ -4,6 +4,10 @@
 //	InstrSelection.cpp
 // 
 // Purpose:
+//	Machine-independent driver file for instruction selection.
+//	This file constructs a forest of BURG instruction trees and then
+//      use the BURG-generated tree grammar (BURM) to find the optimal
+//      instruction sequences for a given machine.
 //	
 // History:
 //	7/02/01	 -  Vikram Adve  -  Created
@@ -35,7 +39,7 @@ cl::Enum<enum SelectDebugLevel_t> SelectDebugLevel("dselect", cl::NoFlags,
    "enable instruction selection debugging information",
    clEnumValN(Select_NoDebugInfo,      "n", "disable debug output"),
    clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
-   clEnumValN(Select_DebugInstTrees,   "i", "print instruction selection debug info"),
+   clEnumValN(Select_DebugInstTrees,   "i", "print debugging info for instruction selection "),
    clEnumValN(Select_DebugBurgTrees,   "b", "print burg trees"), 0);
 
 
@@ -45,7 +49,9 @@ cl::Enum<enum SelectDebugLevel_t> SelectDebugLevel("dselect", cl::NoFlags,
 // Returns true if instruction selection failed, false otherwise.
 //---------------------------------------------------------------------------
 
-bool SelectInstructionsForMethod(Method* method, TargetMachine &Target) {
+bool
+SelectInstructionsForMethod(Method* method, TargetMachine &Target)
+{
   bool failed = false;
   
   //
@@ -67,41 +73,47 @@ bool SelectInstructionsForMethod(Method* method, TargetMachine &Target) {
   const hash_set<InstructionNode*> &treeRoots = instrForest.getRootSet();
   for (hash_set<InstructionNode*>::const_iterator
 	 treeRootIter = treeRoots.begin(); treeRootIter != treeRoots.end();
-       ++treeRootIter) {
-    InstrTreeNode* basicNode = *treeRootIter;
+       ++treeRootIter)
+    {
+      InstrTreeNode* basicNode = *treeRootIter;
       
-    // Invoke BURM to label each tree node with a state
-    burm_label(basicNode);
+      // Invoke BURM to label each tree node with a state
+      burm_label(basicNode);
       
-    if (SelectDebugLevel >= Select_DebugBurgTrees) {
-      printcover(basicNode, 1, 0);
-      cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
-      printMatches(basicNode);
-    }
+      if (SelectDebugLevel >= Select_DebugBurgTrees)
+	{
+	  printcover(basicNode, 1, 0);
+	  cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
+	  printMatches(basicNode);
+	}
       
-    // Then recursively walk the tree to select instructions
-    if (SelectInstructionsForTree(basicNode, /*goalnt*/1, Target)) {
-      failed = true;
-      break;
+      // Then recursively walk the tree to select instructions
+      if (SelectInstructionsForTree(basicNode, /*goalnt*/1, Target))
+	{
+	  failed = true;
+	  break;
+	}
     }
-  }
   
   //
   // Record instructions in the vector for each basic block
   // 
-  for (Method::iterator BI = method->begin(); BI != method->end(); ++BI) {
-    MachineCodeForBasicBlock& bbMvec = (*BI)->getMachineInstrVec();
-    for (BasicBlock::iterator II = (*BI)->begin(); II != (*BI)->end(); ++II) {
-      MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
-      for (unsigned i=0; i < mvec.size(); i++)
-	bbMvec.push_back(mvec[i]);
+  for (Method::iterator BI = method->begin(); BI != method->end(); ++BI)
+    {
+      MachineCodeForBasicBlock& bbMvec = (*BI)->getMachineInstrVec();
+      for (BasicBlock::iterator II = (*BI)->begin(); II != (*BI)->end(); ++II)
+	{
+	  MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
+	  for (unsigned i=0; i < mvec.size(); i++)
+	    bbMvec.push_back(mvec[i]);
+	}
     }
-  }
   
-  if (SelectDebugLevel >= Select_PrintMachineCode) {
-    cout << endl << "*** Machine instructions after INSTRUCTION SELECTION" << endl;
-    PrintMachineInstructions(method);
-  }
+  if (SelectDebugLevel >= Select_PrintMachineCode)
+    {
+      cout << endl << "*** Machine instructions after INSTRUCTION SELECTION" << endl;
+      PrintMachineInstructions(method);
+    }
   
   return false;
 }
@@ -167,8 +179,10 @@ FoldGetElemChain(const InstructionNode* getElemInstrNode,
 // may be used by multiple instructions).
 //---------------------------------------------------------------------------
 
-bool SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
-			       TargetMachine &Target) {
+bool
+SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
+			  TargetMachine &Target)
+{
   // Use a static vector to avoid allocating a new one per VM instruction
   static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR];
   
@@ -176,10 +190,12 @@ bool SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
   // 
   int ruleForNode = burm_rule(treeRoot->state, goalnt);
   
-  if (ruleForNode == 0) {
-    cerr << "Could not match instruction tree for instr selection" << endl;
-    return true;
-  }
+  if (ruleForNode == 0)
+    {
+      cerr << "Could not match instruction tree for instr selection" << endl;
+      assert(0);
+      return true;
+    }
   
   // Get this rule's non-terminals and the corresponding child nodes (if any)
   // 
@@ -190,48 +206,54 @@ bool SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
   // (If this is a list node, not an instruction, then skip this step).
   // This function is specific to the target architecture.
   // 
-  if (treeRoot->opLabel != VRegListOp) {
-    InstructionNode* instrNode = (InstructionNode*)treeRoot;
-    assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
+  if (treeRoot->opLabel != VRegListOp)
+    {
+      InstructionNode* instrNode = (InstructionNode*)treeRoot;
+      assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
     
-    unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, Target,
-				       minstrVec);
-    assert(N <= MAX_INSTR_PER_VMINSTR);
-    for (unsigned i=0; i < N; i++) {
-      assert(minstrVec[i] != NULL);
-      instrNode->getInstruction()->addMachineInstruction(minstrVec[i]);
+      unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, Target,
+					 minstrVec);
+      assert(N <= MAX_INSTR_PER_VMINSTR);
+      for (unsigned i=0; i < N; i++)
+	{
+	  assert(minstrVec[i] != NULL);
+	  instrNode->getInstruction()->addMachineInstruction(minstrVec[i]);
+	}
     }
-  }
   
   // Then, recursively compile the child nodes, if any.
   // 
-  if (nts[0]) { // i.e., there is at least one kid
-    InstrTreeNode* kids[2];
-    int currentRule = ruleForNode;
-    burm_kids(treeRoot, currentRule, kids);
-    
-    // First skip over any chain rules so that we don't visit
-    // the current node again.
-    // 
-    while (ThisIsAChainRule(currentRule)) {
-      currentRule = burm_rule(treeRoot->state, nts[0]);
-      nts = burm_nts[currentRule];
+  if (nts[0])
+    { // i.e., there is at least one kid
+      InstrTreeNode* kids[2];
+      int currentRule = ruleForNode;
       burm_kids(treeRoot, currentRule, kids);
-    }
+    
+      // First skip over any chain rules so that we don't visit
+      // the current node again.
+      // 
+      while (ThisIsAChainRule(currentRule))
+	{
+	  currentRule = burm_rule(treeRoot->state, nts[0]);
+	  nts = burm_nts[currentRule];
+	  burm_kids(treeRoot, currentRule, kids);
+	}
       
-    // Now we have the first non-chain rule so we have found
-    // the actual child nodes.  Recursively compile them.
-    // 
-    for (int i = 0; nts[i]; i++) {
-      assert(i < 2);
-      InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
-      if (nodeType == InstrTreeNode::NTVRegListNode ||
-	  nodeType == InstrTreeNode::NTInstructionNode) {
-	if (SelectInstructionsForTree(kids[i], nts[i], Target))
-	  return true;			// failure
-      }
+      // Now we have the first non-chain rule so we have found
+      // the actual child nodes.  Recursively compile them.
+      // 
+      for (int i = 0; nts[i]; i++)
+	{
+	  assert(i < 2);
+	  InstrTreeNode::InstrTreeNodeType nodeType = kids[i]->getNodeType();
+	  if (nodeType == InstrTreeNode::NTVRegListNode ||
+	      nodeType == InstrTreeNode::NTInstructionNode)
+	    {
+	      if (SelectInstructionsForTree(kids[i], nts[i], Target))
+		return true;			// failure
+	    }
+	}
     }
-  }
   
   return false;				// success
 }
diff --git a/llvm/lib/CodeGen/MachineInstr.cpp b/llvm/lib/CodeGen/MachineInstr.cpp
index bbe2144f237..1db2d48fc9e 100644
--- a/llvm/lib/CodeGen/MachineInstr.cpp
+++ b/llvm/lib/CodeGen/MachineInstr.cpp
@@ -14,6 +14,7 @@
 
 
 #include "llvm/CodeGen/MachineInstr.h"
+#include "llvm/Target/MachineRegInfo.h"
 #include "llvm/Method.h"
 #include "llvm/ConstPoolVals.h"
 #include "llvm/Instruction.h"
@@ -49,7 +50,7 @@ MachineInstr::SetMachineOperand(unsigned int i,
   assert(i < operands.size());
   operands[i].Initialize(operandType, _val);
   operands[i].isDef = isdef ||
-		      TargetInstrDescriptors[opCode].resultPos == (int) i;
+    TargetInstrDescriptors[opCode].resultPos == (int) i;
 }
 
 void
@@ -60,7 +61,7 @@ MachineInstr::SetMachineOperand(unsigned int i,
   assert(i < operands.size());
   operands[i].InitializeConst(operandType, intValue);
   operands[i].isDef = isdef ||
-		      TargetInstrDescriptors[opCode].resultPos == (int) i;
+    TargetInstrDescriptors[opCode].resultPos == (int) i;
 }
 
 void
@@ -70,7 +71,7 @@ MachineInstr::SetMachineOperand(unsigned int i,
   assert(i < operands.size());
   operands[i].InitializeReg(regNum);
   operands[i].isDef = isdef ||
-		      TargetInstrDescriptors[opCode].resultPos == (int) i;
+    TargetInstrDescriptors[opCode].resultPos == (int) i;
 }
 
 void
@@ -104,39 +105,45 @@ operator<< (ostream& os, const MachineInstr& minstr)
   return os;
 }
 
-static inline ostream &OutputOperand(ostream &os, const MachineOperand &mop) {
-  switch (mop.getOperandType()) {
-  case MachineOperand::MO_CCRegister:
-  case MachineOperand::MO_VirtualRegister:
-    return os << "(val " << mop.getVRegValue() << ")";
-  case MachineOperand::MO_MachineRegister:
-    return os << "("     << mop.getMachineRegNum() << ")";
-  default:
-    assert(0 && "Unknown operand type");
-    return os;
-  }
+static inline ostream&
+OutputOperand(ostream &os, const MachineOperand &mop)
+{
+  switch (mop.getOperandType())
+    {
+    case MachineOperand::MO_CCRegister:
+    case MachineOperand::MO_VirtualRegister:
+      return os << "(val " << mop.getVRegValue() << ")";
+    case MachineOperand::MO_MachineRegister:
+      return os << "("     << mop.getMachineRegNum() << ")";
+    default:
+      assert(0 && "Unknown operand type");
+      return os;
+    }
 }
 
 
-ostream &operator<<(ostream &os, const MachineOperand &mop) {
-  switch(mop.opType) {
-  case MachineOperand::MO_VirtualRegister:
-  case MachineOperand::MO_MachineRegister:
-    os << "%reg";
-    return OutputOperand(os, mop);
-  case MachineOperand::MO_CCRegister:
-    os << "%ccreg";
-    return OutputOperand(os, mop);
-  case MachineOperand::MO_SignExtendedImmed:
-    return os << mop.immedVal;
-  case MachineOperand::MO_UnextendedImmed:
-    return os << mop.immedVal;
-  case MachineOperand::MO_PCRelativeDisp:
-    return os << "%disp(label " << mop.getVRegValue() << ")";
-  default:
-    assert(0 && "Unrecognized operand type");
-    break;
-  }
+ostream&
+operator<<(ostream &os, const MachineOperand &mop)
+{
+  switch(mop.opType)
+    {
+    case MachineOperand::MO_VirtualRegister:
+    case MachineOperand::MO_MachineRegister:
+      os << "%reg";
+      return OutputOperand(os, mop);
+    case MachineOperand::MO_CCRegister:
+      os << "%ccreg";
+      return OutputOperand(os, mop);
+    case MachineOperand::MO_SignExtendedImmed:
+      return os << mop.immedVal;
+    case MachineOperand::MO_UnextendedImmed:
+      return os << mop.immedVal;
+    case MachineOperand::MO_PCRelativeDisp:
+      return os << "%disp(label " << mop.getVRegValue() << ")";
+    default:
+      assert(0 && "Unrecognized operand type");
+      break;
+    }
   
   return os;
 }
@@ -188,12 +195,12 @@ Set2OperandsFromInstr(MachineInstr* minstr,
 #ifdef REVERT_TO_EXPLICIT_CONSTANT_CHECKS
 unsigned
 Set3OperandsFromInstrJUNK(MachineInstr* minstr,
-		      InstructionNode* vmInstrNode,
-		      const TargetMachine& target,
-		      bool canDiscardResult,
-		      int op1Position,
-		      int op2Position,
-		      int resultPosition)
+			  InstructionNode* vmInstrNode,
+			  const TargetMachine& target,
+			  bool canDiscardResult,
+			  int op1Position,
+			  int op2Position,
+			  int resultPosition)
 {
   assert(op1Position >= 0);
   assert(resultPosition >= 0);
@@ -208,10 +215,11 @@ Set3OperandsFromInstrJUNK(MachineInstr* minstr,
     minstr->SetMachineOperand(op1Position, /*regNum*/ target.zeroRegNum);
   else
     {
-      if (op1Value->isConstant()) {
-	// value is constant and must be loaded from constant pool
-	returnFlags = returnFlags | (1 << op1Position);
-      }
+      if (op1Value->isConstant())
+	{
+	  // value is constant and must be loaded from constant pool
+	  returnFlags = returnFlags | (1 << op1Position);
+	}
       minstr->SetMachineOperand(op1Position, MachineOperand::MO_VirtualRegister,
 				op1Value);
     }
@@ -233,10 +241,11 @@ Set3OperandsFromInstrJUNK(MachineInstr* minstr,
 	minstr->SetMachineOperand(op2Position, machineRegNum);
       else if (op2type == MachineOperand::MO_VirtualRegister)
 	{
-	  if (op2Value->isConstant()) {
-	    // value is constant and must be loaded from constant pool
-	    returnFlags = returnFlags | (1 << op2Position);
-	  }
+	  if (op2Value->isConstant())
+	    {
+	      // value is constant and must be loaded from constant pool
+	      returnFlags = returnFlags | (1 << op2Position);
+	    }
 	  minstr->SetMachineOperand(op2Position, op2type, op2Value);
 	}
       else
@@ -279,10 +288,12 @@ Set3OperandsFromInstr(MachineInstr* minstr,
 			      vmInstrNode->rightChild()->getValue());   
   
   // result operand: if it can be discarded, use a dead register if one exists
-  if (canDiscardResult && target.zeroRegNum >= 0)
-    minstr->SetMachineOperand(resultPosition, target.zeroRegNum);
+  if (canDiscardResult && target.getRegInfo().getZeroRegNum() >= 0)
+    minstr->SetMachineOperand(resultPosition,
+			      target.getRegInfo().getZeroRegNum());
   else
-    minstr->SetMachineOperand(resultPosition, MachineOperand::MO_VirtualRegister, vmInstrNode->getValue());
+    minstr->SetMachineOperand(resultPosition,
+			      MachineOperand::MO_VirtualRegister, vmInstrNode->getValue());
 }
 
 
@@ -304,16 +315,18 @@ ChooseRegOrImmed(Value* val,
   ConstPoolVal *CPV = val->castConstant();
   if (!CPV) return opType;
 
-  if (CPV->getType() == Type::BoolTy) {
-    ConstPoolBool *CPB = (ConstPoolBool*)CPV;
-    if (!CPB->getValue() && target.zeroRegNum >= 0) {
-      getMachineRegNum = target.zeroRegNum;
-      return MachineOperand::MO_MachineRegister;
-    }
+  if (CPV->getType() == Type::BoolTy)
+    {
+      ConstPoolBool *CPB = (ConstPoolBool*)CPV;
+      if (!CPB->getValue() && target.getRegInfo().getZeroRegNum() >= 0)
+	{
+	  getMachineRegNum = target.getRegInfo().getZeroRegNum();
+	  return MachineOperand::MO_MachineRegister;
+	}
 
-    getImmedValue = 1;
-    return MachineOperand::MO_SignExtendedImmed;
-  }
+      getImmedValue = 1;
+      return MachineOperand::MO_SignExtendedImmed;
+    }
   
   if (!CPV->getType()->isIntegral()) return opType;
 
@@ -323,22 +336,28 @@ ChooseRegOrImmed(Value* val,
   // unsigned constants to signed).
   // 
   int64_t intValue;
-  if (CPV->getType()->isSigned()) {
-    intValue = ((ConstPoolSInt*)CPV)->getValue();
-  } else {
-    uint64_t V = ((ConstPoolUInt*)CPV)->getValue();
-    if (V >= INT64_MAX) return opType;
-    intValue = (int64_t)V;
-  }
+  if (CPV->getType()->isSigned())
+    {
+      intValue = ((ConstPoolSInt*)CPV)->getValue();
+    }
+  else
+    {
+      uint64_t V = ((ConstPoolUInt*)CPV)->getValue();
+      if (V >= INT64_MAX) return opType;
+      intValue = (int64_t)V;
+    }
 
-  if (intValue == 0 && target.zeroRegNum >= 0){
-    opType = MachineOperand::MO_MachineRegister;
-    getMachineRegNum = target.zeroRegNum;
-  } else if (canUseImmed &&
-	     target.getInstrInfo().constantFitsInImmedField(opCode, intValue)) {
-    opType = MachineOperand::MO_SignExtendedImmed;
-    getImmedValue = intValue;
-  }
+  if (intValue == 0 && target.getRegInfo().getZeroRegNum() >= 0)
+    {
+      opType = MachineOperand::MO_MachineRegister;
+      getMachineRegNum = target.getRegInfo().getZeroRegNum();
+    }
+  else if (canUseImmed &&
+	   target.getInstrInfo().constantFitsInImmedField(opCode, intValue))
+    {
+      opType = MachineOperand::MO_SignExtendedImmed;
+      getImmedValue = intValue;
+    }
   
   return opType;
 }
@@ -365,28 +384,3 @@ PrintMachineInstructions(const Method *const method)
   cout << endl << "End method \"" << method->getName() << "\""
        << endl << endl;
 }
-
-#if 0
-
-void PrintMachineInstructions(Method * method)
-
-{
-  cout << "\n" << method->getReturnType()
-       << " \"" << method->getName() << "\"" << endl;
-  
-  for (Method::const_iterator BI = method->begin(); BI != method->end(); ++BI)
-    {
-      const BasicBlock* bb = *BI;
-      cout << "\n"
-	   << (bb->hasName()? bb->getName() : "Label")
-	   << " (" << bb << ")" << ":"
-	   << endl;
-      
-      const MachineCodeForBasicBlock& mvec = bb->getMachineInstrVec();
-      for (unsigned i=0; i < mvec.size(); i++)
-	cout << "\t" << *mvec[i] << endl;
-    } 
-  cout << endl << "End method \"" << method->getName() << "\""
-       << endl << endl;
-}
-#endif