Instruction selection via pattern matching on instruction trees using BURG.

llvm-svn: 231

4 files changed, 1097 insertions, 0 deletions

diff --git a/llvm/lib/CodeGen/InstrSelection/InstrForest.cpp b/llvm/lib/CodeGen/InstrSelection/InstrForest.cpp
new file mode 100644
index 00000000000..8ea293129c2
--- /dev/null
+++ b/llvm/lib/CodeGen/InstrSelection/InstrForest.cpp
@@ -0,0 +1,461 @@
+// $Id$
+//---------------------------------------------------------------------------
+// File:
+//	InstrForest.cpp
+// 
+// Purpose:
+//	Convert SSA graph to instruction trees for instruction selection.
+// 
+// Strategy:
+//  The key goal is to group instructions into a single
+//  tree if one or more of them might be potentially combined into a single
+//  complex instruction in the target machine.
+//  Since this grouping is completely machine-independent, we do it as
+//  aggressive as possible to exploit any possible taret instructions.
+//  In particular, we group two instructions O and I if:
+//      (1) Instruction O computes an operand used by instruction I,
+//  and (2) O and I are part of the same basic block,
+//  and (3) O has only a single use, viz., I.
+// 
+// History:
+//	6/28/01	 -  Vikram Adve  -  Created
+// 
+//---------------------------------------------------------------------------
+
+
+//************************** System Include Files **************************/
+
+#include <assert.h>
+#include <iostream.h>
+#include <bool.h>
+#include <string>
+
+//*************************** User Include Files ***************************/
+
+#include "llvm/Type.h"
+#include "llvm/Module.h"
+#include "llvm/Method.h"
+#include "llvm/Instruction.h"
+#include "llvm/iTerminators.h"
+#include "llvm/iMemory.h"
+#include "llvm/ConstPoolVals.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Bytecode/Reader.h"
+#include "llvm/Bytecode/Writer.h"
+#include "llvm/Tools/CommandLine.h"
+#include "llvm/LLC/CompileContext.h"
+#include "llvm/Codegen/MachineInstr.h"
+#include "llvm/Codegen/InstrForest.h"
+
+//************************ Class Implementations **************************/
+
+
+//------------------------------------------------------------------------ 
+// class InstrTreeNode
+//------------------------------------------------------------------------ 
+
+
+InstrTreeNode::InstrTreeNode(InstrTreeNodeType nodeType,
+			     Value* _val)
+  : treeNodeType(nodeType),
+    val(_val)
+{
+  basicNode.leftChild = NULL;
+  basicNode.rightChild = NULL;
+  basicNode.parent = NULL;
+  basicNode.opLabel = InvalidOp;
+  basicNode.treeNodePtr = this;
+}
+
+InstrTreeNode::~InstrTreeNode()
+{}
+
+
+void
+InstrTreeNode::dump(int dumpChildren,
+		    int indent) const
+{
+  this->dumpNode(indent);
+  
+  if (dumpChildren)
+    {
+      if (leftChild())
+	leftChild()->dump(dumpChildren, indent+1);
+      if (rightChild())
+	rightChild()->dump(dumpChildren, indent+1);
+    }
+}
+
+
+InstructionNode::InstructionNode(Instruction* _instr)
+  : InstrTreeNode(NTInstructionNode, _instr)
+{
+  OpLabel opLabel = _instr->getOpcode();
+
+  // Distinguish special cases of some instructions such as Ret and Br
+  // 
+  if (opLabel == Instruction::Ret && ((ReturnInst*) _instr)->getReturnValue())
+    {
+      opLabel = RetValueOp;		 // ret(value) operation
+    }
+  else if (opLabel == Instruction::Br && ! ((BranchInst*) _instr)->isUnconditional())
+    {
+      opLabel = BrCondOp;		// br(cond) operation
+    }
+  else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT)
+    {
+      opLabel = SetCCOp;		// common label for all SetCC ops
+    }
+  else if (opLabel == Instruction::Alloca && _instr->getNumOperands() > 0)
+    {
+      opLabel = AllocaN;		 // Alloca(ptr, N) operation
+    }
+  else if ((opLabel == Instruction::Load ||
+	    opLabel == Instruction::GetElementPtr)
+	   && ((MemAccessInst*)_instr)->getFirstOffsetIdx() > 0)
+    {
+      opLabel = opLabel + 100;		 // load/getElem with index vector
+    }
+  else if (opLabel == Instruction::Cast)
+    {
+      const Type* instrValueType = _instr->getType();
+      switch(instrValueType->getPrimitiveID())
+	{
+	case Type::BoolTyID:	opLabel = ToBoolTy;  break;
+	case Type::UByteTyID:	opLabel = ToUByteTy; break;
+	case Type::SByteTyID:	opLabel = ToSByteTy; break;
+	case Type::UShortTyID:	opLabel = ToUShortTy; break;
+	case Type::ShortTyID:	opLabel = ToShortTy; break;
+	case Type::UIntTyID:	opLabel = ToUIntTy; break;
+	case Type::IntTyID:	opLabel = ToIntTy; break;
+	case Type::ULongTyID:	opLabel = ToULongTy; break;
+	case Type::LongTyID:	opLabel = ToLongTy; break;
+	case Type::FloatTyID:	opLabel = ToFloatTy; break;
+	case Type::DoubleTyID:	opLabel = ToDoubleTy; break;
+	default:
+	  if (instrValueType->isArrayType())
+	    opLabel = ToArrayTy;
+	  else if (instrValueType->isPointerType())
+	    opLabel = ToPointerTy;
+	  else
+	    ; // Just use `Cast' opcode otherwise. It's probably ignored.
+	  break;
+	}
+    }
+  
+  basicNode.opLabel = opLabel;
+}
+
+void
+InstructionNode::reverseBinaryArgumentOrder()
+{
+  assert(getInstruction()->isBinaryOp());
+  
+  // switch arguments for the instruction
+  ((BinaryOperator*) getInstruction())->swapOperands();
+  
+  // switch arguments for this tree node itself
+  BasicTreeNode* leftCopy = basicNode.leftChild;
+  basicNode.leftChild = basicNode.rightChild;
+  basicNode.rightChild = leftCopy;
+}
+
+void
+InstructionNode::dumpNode(int indent) const
+{
+  for (int i=0; i < indent; i++)
+    cout << "    ";
+  
+  cout << getInstruction()->getOpcodeName();
+  
+  const vector<MachineInstr*>& mvec = getInstruction()->getMachineInstrVec();
+  if (mvec.size() > 0)
+    cout << "\tMachine Instructions:  ";
+  for (unsigned int i=0; i < mvec.size(); i++)
+    {
+      mvec[i]->dump(0);
+      if (i < mvec.size() - 1)
+	cout << ";  ";
+    }
+  
+  cout << endl;
+}
+
+
+VRegListNode::VRegListNode()
+  : InstrTreeNode(NTVRegListNode, NULL)
+{
+  basicNode.opLabel = VRegListOp;
+}
+
+void
+VRegListNode::dumpNode(int indent) const
+{
+  for (int i=0; i < indent; i++)
+    cout << "    ";
+  
+  cout << "List" << endl;
+}
+
+
+VRegNode::VRegNode(Value* _val)
+  : InstrTreeNode(NTVRegNode, _val)
+{
+  basicNode.opLabel = VRegNodeOp;
+}
+
+void
+VRegNode::dumpNode(int indent) const
+{
+  for (int i=0; i < indent; i++)
+    cout << "    ";
+  
+  cout << "VReg " << getValue() << "\t(type "
+       << (int) getValue()->getValueType() << ")" << endl;
+}
+
+
+ConstantNode::ConstantNode(ConstPoolVal* constVal)
+  : InstrTreeNode(NTConstNode, constVal)
+{
+  basicNode.opLabel = ConstantNodeOp;
+}
+
+void
+ConstantNode::dumpNode(int indent) const
+{
+  for (int i=0; i < indent; i++)
+    cout << "    ";
+  
+  cout << "Constant " << getValue() << "\t(type "
+       << (int) getValue()->getValueType() << ")" << endl;
+}
+
+
+LabelNode::LabelNode(BasicBlock* _bblock)
+  : InstrTreeNode(NTLabelNode, _bblock)
+{
+  basicNode.opLabel = LabelNodeOp;
+}
+
+void
+LabelNode::dumpNode(int indent) const
+{
+  for (int i=0; i < indent; i++)
+    cout << "    ";
+  
+  cout << "Label " << getValue() << endl;
+}
+
+//------------------------------------------------------------------------
+// class InstrForest
+// 
+// A forest of instruction trees, usually for a single method.
+//------------------------------------------------------------------------ 
+
+void
+InstrForest::buildTreesForMethod(Method *method)
+{
+  for (Method::inst_iterator instrIter = method->inst_begin();
+       instrIter != method->inst_end();
+       ++instrIter)
+    {
+      Instruction *instr = *instrIter;
+      if (! instr->isPHINode())
+	(void) this->buildTreeForInstruction(instr);
+    } 
+}
+
+
+void
+InstrForest::dump() const
+{
+  for (hash_set<InstructionNode*, ptrHashFunc >::const_iterator
+	 treeRootIter = treeRoots.begin();
+       treeRootIter != treeRoots.end();
+       ++treeRootIter)
+    {
+      (*treeRootIter)->dump(/*dumpChildren*/ 1, /*indent*/ 0);
+    }
+}
+
+inline void
+InstrForest::noteTreeNodeForInstr(Instruction* instr,
+				  InstructionNode* treeNode)
+{
+  assert(treeNode->getNodeType() == InstrTreeNode::NTInstructionNode);
+  (*this)[instr] = treeNode;
+  treeRoots.insert(treeNode);		// mark node as root of a new tree
+}
+
+
+inline void
+InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child)
+{
+  parent->basicNode.leftChild = & child->basicNode;
+  child->basicNode.parent = & parent->basicNode;
+  if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
+    treeRoots.erase((InstructionNode*) child);	// no longer a tree root
+}
+
+
+inline void
+InstrForest::setRightChild(InstrTreeNode* parent, InstrTreeNode* child)
+{
+  parent->basicNode.rightChild = & child->basicNode;
+  child->basicNode.parent = & parent->basicNode;
+  if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
+    treeRoots.erase((InstructionNode*) child);	// no longer a tree root
+}
+
+
+InstructionNode*
+InstrForest::buildTreeForInstruction(Instruction* instr)
+{
+  InstructionNode* treeNode = this->getTreeNodeForInstr(instr);
+  if (treeNode != NULL)
+    {// treeNode has already been constructed for this instruction
+      assert(treeNode->getInstruction() == instr);
+      return treeNode;
+    }
+  
+  // Otherwise, create a new tree node for this instruction.
+  // 
+  treeNode = new InstructionNode(instr);
+  this->noteTreeNodeForInstr(instr, treeNode);
+  
+  // If the instruction has more than 2 instruction operands,
+  // then we will not add any children.  This assumes that instructions
+  // like 'call' that have more than 2 instruction operands do not
+  // ever get combined with the instructions that compute the operands. 
+  // Note that we only count operands of type instruction and not other
+  // values such as branch labels for a branch or switch instruction.
+  //
+  // To do this efficiently, we'll walk all operands, build treeNodes
+  // for all instruction operands and save them in an array, and then
+  // insert children at the end if there are not more than 2.
+  // As a performance optimization, allocate a child array only
+  // if a fixed array is too small.
+  // 
+  int numChildren = 0;
+  const unsigned int MAX_CHILD = 8;
+  static InstrTreeNode* fixedChildArray[MAX_CHILD];
+  InstrTreeNode** childArray =
+    (instr->getNumOperands() > MAX_CHILD)
+    ? new (InstrTreeNode*)[instr->getNumOperands()]
+    : fixedChildArray;
+  
+  //
+  // Walk the operands of the instruction
+  // 
+  for (Instruction::op_iterator opIter = instr->op_begin();
+       opIter != instr->op_end();
+       ++opIter)
+    {
+      Value* operand = *opIter;
+      
+      // Check if the operand is a data value, not an branch label, type,
+      // method or module.  If the operand is an address type (i.e., label
+      // or method) that is used in an non-branching operation, e.g., `add'.
+      // that should be considered a data value.
+      
+      // Check latter condition here just to simplify the next IF.
+      bool includeAddressOperand =
+	((operand->getValueType() == Value::BasicBlockVal
+	  || operand->getValueType() == Value::MethodVal)
+	 && ! instr->isTerminator());
+	 
+      if (/* (*opIter) != NULL
+	     &&*/ includeAddressOperand
+		  || operand->getValueType() == Value::InstructionVal
+		  ||  operand->getValueType() == Value::ConstantVal
+		  ||  operand->getValueType() == Value::MethodArgumentVal)
+	{// This operand is a data value
+	  
+	  // An instruction that computes the incoming value is added as a
+	  // child of the current instruction if:
+	  //   the value has only a single use
+	  //   AND both instructions are in the same basic block
+	  //   AND the instruction is not a PHI
+	  // 
+	  // (Note that if the value has only a single use (viz., `instr'),
+	  //  the def of the value can be safely moved just before instr
+	  //  and therefore it is safe to combine these two instructions.)
+	  // 
+	  // In all other cases, the virtual register holding the value
+	  // is used directly, i.e., made a child of the instruction node.
+	  // 
+	  InstrTreeNode* opTreeNode;
+	  if (operand->getValueType() == Value::InstructionVal
+	      && operand->use_size() == 1
+	      && ((Instruction*)operand)->getParent() == instr->getParent()
+	      && ! ((Instruction*)operand)->isPHINode())
+	    {
+	      // Recursively create a treeNode for it.
+	      opTreeNode =this->buildTreeForInstruction((Instruction*)operand);
+	    }
+	  else if (operand->getValueType() == Value::ConstantVal)
+	    {
+	      // Create a leaf node for a constant
+	      opTreeNode = new ConstantNode((ConstPoolVal*) operand);
+	    }
+	  else
+	    {
+	      // Create a leaf node for the virtual register
+	      opTreeNode = new VRegNode(operand);
+	    }
+	  
+	  childArray[numChildren] = opTreeNode;
+	  numChildren++;
+	}
+    }
+  
+  //-------------------------------------------------------------------- 
+  // Add any selected operands as children in the tree.
+  // Certain instructions can have more than 2 in some instances (viz.,
+  // a CALL or a memory access -- LOAD, STORE, and GetElemPtr -- to an
+  // array or struct). Make the operands of every such instruction into
+  // a right-leaning binary tree with the operand nodes at the leaves
+  // and VRegList nodes as internal nodes.
+  //-------------------------------------------------------------------- 
+  
+  InstrTreeNode* parent = treeNode;		// new VRegListNode();
+  int n;
+  
+  if (numChildren > 2)
+    {
+      unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
+      assert(instrOpcode == Instruction::Call ||
+	     instrOpcode == Instruction::Load ||
+	     instrOpcode == Instruction::Store ||
+	     instrOpcode == Instruction::GetElementPtr);
+    }
+  
+  // Insert the first child as a direct child
+  if (numChildren >= 1)
+    this->setLeftChild(parent, childArray[0]);
+  
+  // Create a list node for children 2 .. N-1, if any
+  for (n = numChildren-1; n >= 2; n--)
+    { // We have more than two children
+      InstrTreeNode* listNode = new VRegListNode();
+      this->setRightChild(parent, listNode);
+      this->setLeftChild(listNode, childArray[numChildren - n]);
+      parent = listNode;
+    }
+  
+  // Now insert the last remaining child (if any).
+  if (numChildren >= 2)
+    {
+      assert(n == 1);
+      this->setRightChild(parent, childArray[numChildren - 1]);
+    }
+  
+  if (childArray != fixedChildArray)
+    {
+      delete[] childArray; 
+    }
+  
+  return treeNode;
+}
+
diff --git a/llvm/lib/CodeGen/InstrSelection/InstrSelection.cpp b/llvm/lib/CodeGen/InstrSelection/InstrSelection.cpp
new file mode 100644
index 00000000000..0d7dc7e898e
--- /dev/null
+++ b/llvm/lib/CodeGen/InstrSelection/InstrSelection.cpp
@@ -0,0 +1,279 @@
+// $Id$ -*-c++-*-
+//***************************************************************************
+// File:
+//	InstrSelection.h
+// 
+// Purpose:
+//	
+// History:
+//	7/02/01	 -  Vikram Adve  -  Created
+//***************************************************************************
+
+
+//************************** System Include Files **************************/
+
+#include <assert.h>
+#include <stdio.h>
+#include <iostream.h>
+#include <bool.h>
+#include <string>
+
+//*************************** User Include Files ***************************/
+
+#include "llvm/Method.h"
+#include "llvm/BasicBlock.h"
+#include "llvm/Type.h"
+#include "llvm/iMemory.h"
+#include "llvm/Instruction.h"
+#include "llvm/LLC/CompileContext.h"
+#include "llvm/Codegen/InstrForest.h"
+#include "llvm/Codegen/MachineInstr.h"
+#include "llvm/Codegen/InstrSelection.h"
+
+
+//************************* Forward Declarations ***************************/
+
+static bool SelectInstructionsForTree	(BasicTreeNode* treeRoot,
+					 int goalnt,
+					 CompileContext& ccontext);
+
+
+//******************* Externally Visible Functions *************************/
+
+
+//---------------------------------------------------------------------------
+// Entry point for instruction selection using BURG.
+// Returns true if instruction selection failed, false otherwise.
+//---------------------------------------------------------------------------
+
+bool
+SelectInstructionsForMethod(Method* method,
+			    CompileContext& ccontext)
+{
+  bool failed = false;
+  
+  InstrForest instrForest;
+  instrForest.buildTreesForMethod(method);
+      
+  const hash_set<InstructionNode*, ptrHashFunc>&
+    treeRoots = instrForest.getRootSet();
+  
+  //
+  // Invoke BURG instruction selection for each tree
+  // 
+  for (hash_set<InstructionNode*, ptrHashFunc >::const_iterator
+	 treeRootIter = treeRoots.begin();
+       treeRootIter != treeRoots.end();
+       ++treeRootIter)
+    {
+      BasicTreeNode* basicNode = (*treeRootIter)->getBasicNode();
+      
+      // Invoke BURM to label each tree node with a state
+      (void) burm_label(basicNode);
+      
+      if (ccontext.getOptions().IntOptionValue(DEBUG_INSTR_SELECT_OPT)
+	  >= DEBUG_BURG_TREES)
+	{
+	  printcover(basicNode, 1, 0);
+	  printf("\nCover cost == %d\n\n", treecost(basicNode, 1, 0));
+	  printMatches(basicNode);
+	}
+      
+      // Then recursively walk the tree to select instructions
+      if (SelectInstructionsForTree(basicNode, /*goalnt*/1, ccontext))
+	{
+	  failed = true;
+	  break;
+	}
+    }
+  
+  if (!failed)
+    {
+      if ( ccontext.getOptions().IntOptionValue(DEBUG_INSTR_SELECT_OPT)
+	   >= DEBUG_INSTR_TREES)
+	{
+	  cout << "\n\n*** Instruction trees for method "
+	       << (method->hasName()? method->getName() : "")
+	       << endl << endl;
+	  instrForest.dump();
+	}
+      
+      if (ccontext.getOptions().IntOptionValue(DEBUG_INSTR_SELECT_OPT) > 0)
+	PrintMachineInstructions(method, ccontext);	
+    }
+  
+  return false;
+}
+
+
+//---------------------------------------------------------------------------
+// Function: FoldGetElemChain
+// 
+// Purpose:
+//   Fold a chain of GetElementPtr instructions into an equivalent
+//   (Pointer, IndexVector) pair.  Returns the pointer Value, and
+//   stores the resulting IndexVector in argument chainIdxVec.
+//---------------------------------------------------------------------------
+
+Value*
+FoldGetElemChain(const InstructionNode* getElemInstrNode,
+		 vector<ConstPoolVal*>& chainIdxVec)
+{
+  MemAccessInst* getElemInst = (MemAccessInst*)
+    getElemInstrNode->getInstruction();
+  
+  // Initialize return values from the incoming instruction
+  Value* ptrVal = getElemInst->getPtrOperand();
+  chainIdxVec = getElemInst->getIndexVec(); // copies index vector values
+  
+  // Now chase the chain of getElementInstr instructions, if any
+  InstrTreeNode* ptrChild = getElemInstrNode->leftChild();
+  while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
+	 ptrChild->getOpLabel() == GetElemPtrIdx)
+    {
+      // Child is a GetElemPtr instruction
+      getElemInst = (MemAccessInst*)
+	((InstructionNode*) ptrChild)->getInstruction();
+      const vector<ConstPoolVal*>& idxVec = getElemInst->getIndexVec();
+      
+      // Get the pointer value out of ptrChild and *prepend* its index vector
+      ptrVal = getElemInst->getPtrOperand();
+      chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end());
+      
+      ptrChild = ptrChild->leftChild();
+    }
+  
+  return ptrVal;
+}
+
+
+void
+PrintMachineInstructions(Method* method,
+			 CompileContext& ccontext)
+{
+  cout << "\n" << method->getReturnType()
+       << " \"" << method->getName() << "\"" << endl;
+  
+  for (Method::const_iterator bbIter = method->begin();
+       bbIter != method->end();
+       ++bbIter)
+    {
+      BasicBlock* bb = *bbIter;
+      cout << "\n"
+	   << (bb->hasName()? bb->getName() : "Label")
+	   << " (" << bb << ")" << ":"
+	   << endl;
+      
+      for (BasicBlock::const_iterator instrIter = bb->begin();
+	   instrIter != bb->end();
+	   ++instrIter)
+	{
+	  Instruction *instr = *instrIter;
+	  const MachineCodeForVMInstr& minstrVec = instr->getMachineInstrVec();
+	  for (unsigned i=0, N=minstrVec.size(); i < N; i++)
+	    cout << "\t" << *minstrVec[i] << endl;
+	}
+    } 
+}
+
+//*********************** Private Functions *****************************/
+
+
+//---------------------------------------------------------------------------
+// Function SelectInstructionsForTree 
+// 
+// Recursively walk the tree to select instructions.
+// Do this top-down so that child instructions can exploit decisions
+// made at the child instructions.
+// 
+// E.g., if br(setle(reg,const)) decides the constant is 0 and uses
+// a branch-on-integer-register instruction, then the setle node
+// can use that information to avoid generating the SUBcc instruction.
+//
+// Note that this cannot be done bottom-up because setle must do this
+// only if it is a child of the branch (otherwise, the result of setle
+// may be used by multiple instructions).
+//---------------------------------------------------------------------------
+
+bool
+SelectInstructionsForTree(BasicTreeNode* treeRoot,
+			  int goalnt,
+			  CompileContext& ccontext)
+{
+  // Use a static vector to avoid allocating a new one per VM instruction
+  static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR];
+  
+  // Get the rule that matches this node.
+  // 
+  int ruleForNode = burm_rule(treeRoot->state, goalnt);
+  
+  if (ruleForNode == 0)
+    {
+      cerr << "Could not match instruction tree for instr selection" << endl;
+      return true;
+    }
+  
+  // Get this rule's non-terminals and the corresponding child nodes (if any)
+  // 
+  short *nts = burm_nts[ruleForNode];
+  
+  
+  // First, select instructions for the current node and rule.
+  // (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*) MainTreeNode(treeRoot);
+      assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
+      
+      unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, ccontext,
+					 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
+
+      BasicTreeNode* 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 = MainTreeNode(kids[i])->getNodeType();
+	  if (nodeType == InstrTreeNode::NTVRegListNode ||
+	      nodeType == InstrTreeNode::NTInstructionNode)
+	    {
+	      bool failed= SelectInstructionsForTree(kids[i], nts[i],ccontext);
+	      if (failed)
+		return true;			// failure
+	    }
+	}
+    }
+  
+  return false;				// success
+}
+
diff --git a/llvm/lib/CodeGen/InstrSelection/Makefile b/llvm/lib/CodeGen/InstrSelection/Makefile
new file mode 100644
index 00000000000..985ddaf4bf9
--- /dev/null
+++ b/llvm/lib/CodeGen/InstrSelection/Makefile
@@ -0,0 +1,13 @@
+LEVEL = ../../..
+
+DIRS  = 
+
+LIBRARYNAME = select
+
+## List source files in link order
+Source  = \
+	  InstrSelection.o \
+	  MachineInstr.o \
+	  InstrForest.o
+
+include $(LEVEL)/Makefile.common
diff --git a/llvm/lib/CodeGen/MachineInstr.cpp b/llvm/lib/CodeGen/MachineInstr.cpp
new file mode 100644
index 00000000000..1b6f25ae77f
--- /dev/null
+++ b/llvm/lib/CodeGen/MachineInstr.cpp
@@ -0,0 +1,344 @@
+// $Id$
+//***************************************************************************
+// File:
+//	MachineInstr.cpp
+// 
+// Purpose:
+//	
+// 
+// Strategy:
+// 
+// History:
+//	7/2/01	 -  Vikram Adve  -  Created
+//**************************************************************************/
+
+
+//************************** System Include Files **************************/
+
+#include <strstream.h>
+#include <string>
+#include <vector>
+
+//*************************** User Include Files ***************************/
+
+#include "llvm/Type.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/ConstPoolVals.h"
+#include "llvm/Value.h"
+#include "llvm/Instruction.h"
+#include "llvm/Codegen/InstrForest.h"
+#include "llvm/Codegen/MachineInstr.h"
+
+//************************ Class Implementations **************************/
+
+
+bool
+MachineInstrInfo::constantFitsInImmedField(int64_t intValue) const
+{
+  // First, check if opCode has an immed field.
+  bool isSignExtended;
+  uint64_t maxImmedValue = this->maxImmedConstant(isSignExtended);
+  if (maxImmedValue != 0)
+    {
+      // Now check if the constant fits
+      if (intValue <= (int64_t) maxImmedValue &&
+	  intValue >= -((int64_t) maxImmedValue+1))
+	return true;
+    }
+  
+  return false;
+}
+
+MachineInstr::MachineInstr(MachineOpCode _opCode,
+			   OpCodeMask    _opCodeMask)
+  : opCode(_opCode),
+    opCodeMask(_opCodeMask),
+    operands(TargetMachineInstrInfo[_opCode].numOperands)
+{
+}
+
+MachineInstr::~MachineInstr()
+{
+}
+
+void
+MachineInstr::SetMachineOperand(unsigned int i,
+				MachineOperand::MachineOperandType operandType,
+				Value* _val)
+{
+  assert(i < TargetMachineInstrInfo[opCode].numOperands);
+  operands[i].Initialize(operandType, _val);
+}
+
+void
+MachineInstr::SetMachineOperand(unsigned int i,
+				MachineOperand::MachineOperandType operandType,
+				int64_t intValue)
+{
+  assert(i < TargetMachineInstrInfo[opCode].numOperands);
+  operands[i].InitializeConst(operandType, intValue);
+}
+
+void
+MachineInstr::SetMachineOperand(unsigned int i,
+				unsigned int regNum)
+{
+  assert(i < TargetMachineInstrInfo[opCode].numOperands);
+  operands[i].InitializeReg(regNum);
+}
+
+void
+MachineInstr::dump(unsigned int indent)
+{
+  for (unsigned i=0; i < indent; i++)
+    cout << "    ";
+  
+  cout << *this;
+}
+
+ostream&
+operator<< (ostream& os, const MachineInstr& minstr)
+{
+  os << TargetMachineInstrInfo[minstr.opCode].opCodeString;
+  
+  for (unsigned i=0, N=minstr.getNumOperands(); i < N; i++)
+    os << "\t" << minstr.getOperand(i);
+  
+  return os;
+}
+
+ostream&
+operator<< (ostream& os, const MachineOperand& mop)
+{
+  strstream regInfo;
+  if (mop.machineOperandType == MachineOperand::MO_Register)
+    {
+      if (mop.vregType == MachineOperand::MO_VirtualReg)
+	regInfo << "(val " << mop.value << ")" << ends;
+      else
+	regInfo << "("       << mop.regNum << ")" << ends;
+    }
+  else if (mop.machineOperandType == MachineOperand::MO_CCRegister)
+    regInfo << "(val " << mop.value << ")" << ends;
+  
+  switch(mop.machineOperandType)
+    {
+    case MachineOperand::MO_Register:
+      os << "%reg" << regInfo.str();
+      free(regInfo.str());
+      break;
+      
+    case MachineOperand::MO_CCRegister:
+      os << "%ccreg" << regInfo.str();
+      free(regInfo.str());
+      break;
+
+    case MachineOperand::MO_SignExtendedImmed:
+      os << mop.immedVal;
+      break;
+
+    case MachineOperand::MO_UnextendedImmed:
+      os << mop.immedVal;
+      break;
+
+    case MachineOperand::MO_PCRelativeDisp:
+      os << "%disp(label " << mop.value << ")";
+      break;
+
+    default:
+      assert(0 && "Unrecognized operand type");
+      break;
+    }
+
+  return os;
+}
+
+
+//---------------------------------------------------------------------------
+// Target-independent utility routines for creating machine instructions
+//---------------------------------------------------------------------------
+
+
+//------------------------------------------------------------------------ 
+// Function Set2OperandsFromInstr
+// Function Set3OperandsFromInstr
+// 
+// For the common case of 2- and 3-operand arithmetic/logical instructions,
+// set the m/c instr. operands directly from the VM instruction's operands.
+// Check whether the first or second operand is 0 and can use a dedicated "0" register.
+// Check whether the second operand should use an immediate field or register.
+// (First and third operands are never immediates for such instructions.)
+// 
+// Arguments:
+// canDiscardResult: Specifies that the result operand can be discarded
+//		     by using the dedicated "0"
+// 
+// op1position, op2position and resultPosition: Specify in which position
+//		     in the machine instruction the 3 operands (arg1, arg2
+//		     and result) should go.
+// 
+// RETURN VALUE: unsigned int flags, where
+//	flags & 0x01	=> operand 1 is constant and needs a register
+//	flags & 0x02	=> operand 2 is constant and needs a register
+//------------------------------------------------------------------------ 
+
+void
+Set2OperandsFromInstr(MachineInstr* minstr,
+		      InstructionNode* vmInstrNode,
+		      const TargetMachine& targetMachine,
+		      bool canDiscardResult,
+		      int op1Position,
+		      int resultPosition)
+{
+  Set3OperandsFromInstr(minstr, vmInstrNode, targetMachine,
+			canDiscardResult, op1Position,
+			/*op2Position*/ -1, resultPosition);
+}
+
+
+unsigned
+Set3OperandsFromInstrJUNK(MachineInstr* minstr,
+		      InstructionNode* vmInstrNode,
+		      const TargetMachine& targetMachine,
+		      bool canDiscardResult,
+		      int op1Position,
+		      int op2Position,
+		      int resultPosition)
+{
+  assert(op1Position >= 0);
+  assert(resultPosition >= 0);
+  
+  unsigned returnFlags = 0x0;
+  
+  // Check if operand 1 is 0 and if so, try to use the register that gives 0, if any.
+  Value* op1Value = vmInstrNode->leftChild()->getValue();
+  bool isValidConstant;
+  int64_t intValue = GetConstantValueAsSignedInt(op1Value, isValidConstant);
+  if (isValidConstant && intValue == 0 && targetMachine.zeroRegNum >= 0)
+    minstr->SetMachineOperand(op1Position, /*regNum*/ targetMachine.zeroRegNum);
+  else
+    {
+      if (op1Value->getValueType() == Value::ConstantVal)
+	{// value is constant and must be loaded from constant pool
+	  returnFlags = returnFlags | (1 << op1Position);
+	}
+      minstr->SetMachineOperand(op1Position, MachineOperand::MO_Register,
+					     op1Value);
+    }
+  
+  // Check if operand 2 (if any) fits in the immediate field of the instruction,
+  // of if it is 0 and can use a dedicated machine register
+  if (op2Position >= 0)
+    {
+      Value* op2Value = vmInstrNode->rightChild()->getValue();
+      int64_t immedValue;
+      MachineOperand::VirtualRegisterType vregType;
+      unsigned int machineRegNum;
+      
+      MachineOperand::MachineOperandType
+	op2type = ChooseRegOrImmed(op2Value, minstr->getOpCode(),targetMachine,
+				   /*canUseImmed*/ true,
+				   vregType, machineRegNum, immedValue);
+      
+      if (op2type == MachineOperand::MO_Register)
+	{
+	  if (vregType == MachineOperand::MO_MachineReg)
+	    minstr->SetMachineOperand(op2Position, machineRegNum);
+	  else
+	    {
+	      if (op2Value->getValueType() == Value::ConstantVal)
+		{// value is constant and must be loaded from constant pool
+		  returnFlags = returnFlags | (1 << op2Position);
+		}
+	      minstr->SetMachineOperand(op2Position, op2type, op2Value);
+	    }
+	}
+      else
+	minstr->SetMachineOperand(op2Position, op2type, immedValue);
+    }
+  
+  // If operand 3 (result) can be discarded, use a dead register if one exists
+  if (canDiscardResult && targetMachine.zeroRegNum >= 0)
+    minstr->SetMachineOperand(resultPosition, targetMachine.zeroRegNum);
+  else
+    minstr->SetMachineOperand(resultPosition, MachineOperand::MO_Register,
+					      vmInstrNode->getValue());
+
+  return returnFlags;
+}
+
+
+void
+Set3OperandsFromInstr(MachineInstr* minstr,
+		      InstructionNode* vmInstrNode,
+		      const TargetMachine& targetMachine,
+		      bool canDiscardResult,
+		      int op1Position,
+		      int op2Position,
+		      int resultPosition)
+{
+  assert(op1Position >= 0);
+  assert(resultPosition >= 0);
+  
+  // operand 1
+  minstr->SetMachineOperand(op1Position, MachineOperand::MO_Register,
+			    vmInstrNode->leftChild()->getValue());   
+  
+  // operand 2 (if any)
+  if (op2Position >= 0)
+    minstr->SetMachineOperand(op2Position, MachineOperand::MO_Register,
+			      vmInstrNode->rightChild()->getValue());   
+  
+  // result operand: if it can be discarded, use a dead register if one exists
+  if (canDiscardResult && targetMachine.zeroRegNum >= 0)
+    minstr->SetMachineOperand(resultPosition, targetMachine.zeroRegNum);
+  else
+    minstr->SetMachineOperand(resultPosition, MachineOperand::MO_Register,
+					      vmInstrNode->getValue());
+}
+
+
+MachineOperand::MachineOperandType
+ChooseRegOrImmed(Value* val,
+		 MachineOpCode opCode,
+		 const TargetMachine& targetMachine,
+		 bool canUseImmed,
+		 MachineOperand::VirtualRegisterType& getVRegType,
+		 unsigned int& getMachineRegNum,
+		 int64_t& getImmedValue)
+{
+  MachineOperand::MachineOperandType opType = MachineOperand::MO_Register;
+  getVRegType = MachineOperand::MO_VirtualReg;
+  getMachineRegNum = 0;
+  getImmedValue = 0;
+  
+  // Check for the common case first: argument is not constant
+  // 
+  if (val->getValueType() != Value::ConstantVal)
+    return opType;
+  
+  // Now get the constant value and check if it fits in the IMMED field.
+  // Take advantage of the fact that the max unsigned value will rarely
+  // fit into any IMMED field and ignore that case (i.e., cast smaller
+  // unsigned constants to signed).
+  // 
+  bool isValidConstant;
+  int64_t intValue = GetConstantValueAsSignedInt(val, isValidConstant);
+  
+  if (isValidConstant)
+    {
+      if (intValue == 0 && targetMachine.zeroRegNum >= 0)
+	{
+	  getVRegType = MachineOperand::MO_MachineReg;
+	  getMachineRegNum = targetMachine.zeroRegNum;
+	}
+      else if (canUseImmed &&
+	       targetMachine.machineInstrInfo[opCode].constantFitsInImmedField(intValue))
+	{
+	  opType = MachineOperand::MO_SignExtendedImmed;
+	  getImmedValue = intValue;
+	}
+    }
+  
+  return opType;
+}