Instruction selection via pattern matching on instruction trees using BURG.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@231 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 344 insertions, 0 deletions

diff --git a/lib/CodeGen/MachineInstr.cpp b/lib/CodeGen/MachineInstr.cpp
new file mode 100644
index 0000000..1b6f25a
--- /dev/null
+++ b/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;
+}