lib/CodeGen/InstrSelection/InstrForest.cpp

   1 // $Id$
   2 //---------------------------------------------------------------------------
   3 // File:
   4 //      InstrForest.cpp
   5 //
   6 // Purpose:
   7 //      Convert SSA graph to instruction trees for instruction selection.
   8 //
   9 // Strategy:
  10 //  The key goal is to group instructions into a single
  11 //  tree if one or more of them might be potentially combined into a single
  12 //  complex instruction in the target machine.
  13 //  Since this grouping is completely machine-independent, we do it as
  14 //  aggressive as possible to exploit any possible taret instructions.
  15 //  In particular, we group two instructions O and I if:
  16 //      (1) Instruction O computes an operand used by instruction I,
  17 //  and (2) O and I are part of the same basic block,
  18 //  and (3) O has only a single use, viz., I.
  19 //
  20 // History:
  21 //      6/28/01  -  Vikram Adve  -  Created
  22 //
  23 //---------------------------------------------------------------------------
  24
  25
  26 //************************** System Include Files **************************/
  27
  28 #include <assert.h>
  29 #include <iostream.h>
  30 #include <bool.h>
  31 #include <string>
  32
  33 //*************************** User Include Files ***************************/
  34
  35 #include "llvm/Type.h"
  36 #include "llvm/Module.h"
  37 #include "llvm/Method.h"
  38 #include "llvm/Instruction.h"
  39 #include "llvm/iTerminators.h"
  40 #include "llvm/iMemory.h"
  41 #include "llvm/ConstPoolVals.h"
  42 #include "llvm/BasicBlock.h"
  43 #include "llvm/Bytecode/Reader.h"
  44 #include "llvm/Bytecode/Writer.h"
  45 #include "llvm/Tools/CommandLine.h"
  46 #include "llvm/LLC/CompileContext.h"
  47 #include "llvm/Codegen/MachineInstr.h"
  48 #include "llvm/Codegen/InstrForest.h"
  49
  50 //************************ Class Implementations **************************/
  51
  52
  53 //------------------------------------------------------------------------
  54 // class InstrTreeNode
  55 //------------------------------------------------------------------------
  56
  57
  58 InstrTreeNode::InstrTreeNode(InstrTreeNodeType nodeType,
  59                              Value* _val)
  60   : treeNodeType(nodeType),
  61     val(_val)
  62 {
  63   basicNode.leftChild = NULL;
  64   basicNode.rightChild = NULL;
  65   basicNode.parent = NULL;
  66   basicNode.opLabel = InvalidOp;
  67   basicNode.treeNodePtr = this;
  68 }
  69
  70 InstrTreeNode::~InstrTreeNode()
  71 {}
  72
  73
  74 void
  75 InstrTreeNode::dump(int dumpChildren,
  76                     int indent) const
  77 {
  78   this->dumpNode(indent);
  79
  80   if (dumpChildren)
  81     {
  82       if (leftChild())
  83         leftChild()->dump(dumpChildren, indent+1);
  84       if (rightChild())
  85         rightChild()->dump(dumpChildren, indent+1);
  86     }
  87 }
  88
  89
  90 InstructionNode::InstructionNode(Instruction* _instr)
  91   : InstrTreeNode(NTInstructionNode, _instr)
  92 {
  93   OpLabel opLabel = _instr->getOpcode();
  94
  95   // Distinguish special cases of some instructions such as Ret and Br
  96   //
  97   if (opLabel == Instruction::Ret && ((ReturnInst*) _instr)->getReturnValue())
  98     {
  99       opLabel = RetValueOp;              // ret(value) operation
 100     }
 101   else if (opLabel == Instruction::Br && ! ((BranchInst*) _instr)->isUnconditional())
 102     {
 103       opLabel = BrCondOp;               // br(cond) operation
 104     }
 105   else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT)
 106     {
 107       opLabel = SetCCOp;                // common label for all SetCC ops
 108     }
 109   else if (opLabel == Instruction::Alloca && _instr->getNumOperands() > 0)
 110     {
 111       opLabel = AllocaN;                 // Alloca(ptr, N) operation
 112     }
 113   else if ((opLabel == Instruction::Load ||
 114             opLabel == Instruction::GetElementPtr)
 115            && ((MemAccessInst*)_instr)->getFirstOffsetIdx() > 0)
 116     {
 117       opLabel = opLabel + 100;           // load/getElem with index vector
 118     }
 119   else if (opLabel == Instruction::Cast)
 120     {
 121       const Type* instrValueType = _instr->getType();
 122       switch(instrValueType->getPrimitiveID())
 123         {
 124         case Type::BoolTyID:    opLabel = ToBoolTy;  break;
 125         case Type::UByteTyID:   opLabel = ToUByteTy; break;
 126         case Type::SByteTyID:   opLabel = ToSByteTy; break;
 127         case Type::UShortTyID:  opLabel = ToUShortTy; break;
 128         case Type::ShortTyID:   opLabel = ToShortTy; break;
 129         case Type::UIntTyID:    opLabel = ToUIntTy; break;
 130         case Type::IntTyID:     opLabel = ToIntTy; break;
 131         case Type::ULongTyID:   opLabel = ToULongTy; break;
 132         case Type::LongTyID:    opLabel = ToLongTy; break;
 133         case Type::FloatTyID:   opLabel = ToFloatTy; break;
 134         case Type::DoubleTyID:  opLabel = ToDoubleTy; break;
 135         default:
 136           if (instrValueType->isArrayType())
 137             opLabel = ToArrayTy;
 138           else if (instrValueType->isPointerType())
 139             opLabel = ToPointerTy;
 140           else
 141             ; // Just use `Cast' opcode otherwise. It's probably ignored.
 142           break;
 143         }
 144     }
 145
 146   basicNode.opLabel = opLabel;
 147 }
 148
 149 void
 150 InstructionNode::reverseBinaryArgumentOrder()
 151 {
 152   assert(getInstruction()->isBinaryOp());
 153
 154   // switch arguments for the instruction
 155   ((BinaryOperator*) getInstruction())->swapOperands();
 156
 157   // switch arguments for this tree node itself
 158   BasicTreeNode* leftCopy = basicNode.leftChild;
 159   basicNode.leftChild = basicNode.rightChild;
 160   basicNode.rightChild = leftCopy;
 161 }
 162
 163 void
 164 InstructionNode::dumpNode(int indent) const
 165 {
 166   for (int i=0; i < indent; i++)
 167     cout << "    ";
 168
 169   cout << getInstruction()->getOpcodeName();
 170
 171   const vector<MachineInstr*>& mvec = getInstruction()->getMachineInstrVec();
 172   if (mvec.size() > 0)
 173     cout << "\tMachine Instructions:  ";
 174   for (unsigned int i=0; i < mvec.size(); i++)
 175     {
 176       mvec[i]->dump(0);
 177       if (i < mvec.size() - 1)
 178         cout << ";  ";
 179     }
 180
 181   cout << endl;
 182 }
 183
 184
 185 VRegListNode::VRegListNode()
 186   : InstrTreeNode(NTVRegListNode, NULL)
 187 {
 188   basicNode.opLabel = VRegListOp;
 189 }
 190
 191 void
 192 VRegListNode::dumpNode(int indent) const
 193 {
 194   for (int i=0; i < indent; i++)
 195     cout << "    ";
 196
 197   cout << "List" << endl;
 198 }
 199
 200
 201 VRegNode::VRegNode(Value* _val)
 202   : InstrTreeNode(NTVRegNode, _val)
 203 {
 204   basicNode.opLabel = VRegNodeOp;
 205 }
 206
 207 void
 208 VRegNode::dumpNode(int indent) const
 209 {
 210   for (int i=0; i < indent; i++)
 211     cout << "    ";
 212
 213   cout << "VReg " << getValue() << "\t(type "
 214        << (int) getValue()->getValueType() << ")" << endl;
 215 }
 216
 217
 218 ConstantNode::ConstantNode(ConstPoolVal* constVal)
 219   : InstrTreeNode(NTConstNode, constVal)
 220 {
 221   basicNode.opLabel = ConstantNodeOp;
 222 }
 223
 224 void
 225 ConstantNode::dumpNode(int indent) const
 226 {
 227   for (int i=0; i < indent; i++)
 228     cout << "    ";
 229
 230   cout << "Constant " << getValue() << "\t(type "
 231        << (int) getValue()->getValueType() << ")" << endl;
 232 }
 233
 234
 235 LabelNode::LabelNode(BasicBlock* _bblock)
 236   : InstrTreeNode(NTLabelNode, _bblock)
 237 {
 238   basicNode.opLabel = LabelNodeOp;
 239 }
 240
 241 void
 242 LabelNode::dumpNode(int indent) const
 243 {
 244   for (int i=0; i < indent; i++)
 245     cout << "    ";
 246
 247   cout << "Label " << getValue() << endl;
 248 }
 249
 250 //------------------------------------------------------------------------
 251 // class InstrForest
 252 //
 253 // A forest of instruction trees, usually for a single method.
 254 //------------------------------------------------------------------------
 255
 256 void
 257 InstrForest::buildTreesForMethod(Method *method)
 258 {
 259   for (Method::inst_iterator instrIter = method->inst_begin();
 260        instrIter != method->inst_end();
 261        ++instrIter)
 262     {
 263       Instruction *instr = *instrIter;
 264       if (! instr->isPHINode())
 265         (void) this->buildTreeForInstruction(instr);
 266     }
 267 }
 268
 269
 270 void
 271 InstrForest::dump() const
 272 {
 273   for (hash_set<InstructionNode*, ptrHashFunc >::const_iterator
 274          treeRootIter = treeRoots.begin();
 275        treeRootIter != treeRoots.end();
 276        ++treeRootIter)
 277     {
 278       (*treeRootIter)->dump(/*dumpChildren*/ 1, /*indent*/ 0);
 279     }
 280 }
 281
 282 inline void
 283 InstrForest::noteTreeNodeForInstr(Instruction* instr,
 284                                   InstructionNode* treeNode)
 285 {
 286   assert(treeNode->getNodeType() == InstrTreeNode::NTInstructionNode);
 287   (*this)[instr] = treeNode;
 288   treeRoots.insert(treeNode);           // mark node as root of a new tree
 289 }
 290
 291
 292 inline void
 293 InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child)
 294 {
 295   parent->basicNode.leftChild = & child->basicNode;
 296   child->basicNode.parent = & parent->basicNode;
 297   if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
 298     treeRoots.erase((InstructionNode*) child);  // no longer a tree root
 299 }
 300
 301
 302 inline void
 303 InstrForest::setRightChild(InstrTreeNode* parent, InstrTreeNode* child)
 304 {
 305   parent->basicNode.rightChild = & child->basicNode;
 306   child->basicNode.parent = & parent->basicNode;
 307   if (child->getNodeType() == InstrTreeNode::NTInstructionNode)
 308     treeRoots.erase((InstructionNode*) child);  // no longer a tree root
 309 }
 310
 311
 312 InstructionNode*
 313 InstrForest::buildTreeForInstruction(Instruction* instr)
 314 {
 315   InstructionNode* treeNode = this->getTreeNodeForInstr(instr);
 316   if (treeNode != NULL)
 317     {// treeNode has already been constructed for this instruction
 318       assert(treeNode->getInstruction() == instr);
 319       return treeNode;
 320     }
 321
 322   // Otherwise, create a new tree node for this instruction.
 323   //
 324   treeNode = new InstructionNode(instr);
 325   this->noteTreeNodeForInstr(instr, treeNode);
 326
 327   // If the instruction has more than 2 instruction operands,
 328   // then we will not add any children.  This assumes that instructions
 329   // like 'call' that have more than 2 instruction operands do not
 330   // ever get combined with the instructions that compute the operands.
 331   // Note that we only count operands of type instruction and not other
 332   // values such as branch labels for a branch or switch instruction.
 333   //
 334   // To do this efficiently, we'll walk all operands, build treeNodes
 335   // for all instruction operands and save them in an array, and then
 336   // insert children at the end if there are not more than 2.
 337   // As a performance optimization, allocate a child array only
 338   // if a fixed array is too small.
 339   //
 340   int numChildren = 0;
 341   const unsigned int MAX_CHILD = 8;
 342   static InstrTreeNode* fixedChildArray[MAX_CHILD];
 343   InstrTreeNode** childArray =
 344     (instr->getNumOperands() > MAX_CHILD)
 345     ? new (InstrTreeNode*)[instr->getNumOperands()]
 346     : fixedChildArray;
 347
 348   //
 349   // Walk the operands of the instruction
 350   //
 351   for (Instruction::op_iterator opIter = instr->op_begin();
 352        opIter != instr->op_end();
 353        ++opIter)
 354     {
 355       Value* operand = *opIter;
 356
 357       // Check if the operand is a data value, not an branch label, type,
 358       // method or module.  If the operand is an address type (i.e., label
 359       // or method) that is used in an non-branching operation, e.g., `add'.
 360       // that should be considered a data value.
 361
 362       // Check latter condition here just to simplify the next IF.
 363       bool includeAddressOperand =
 364         ((operand->getValueType() == Value::BasicBlockVal
 365           || operand->getValueType() == Value::MethodVal)
 366          && ! instr->isTerminator());
 367
 368       if (/* (*opIter) != NULL
 369              &&*/ includeAddressOperand
 370                   || operand->getValueType() == Value::InstructionVal
 371                   ||  operand->getValueType() == Value::ConstantVal
 372                   ||  operand->getValueType() == Value::MethodArgumentVal)
 373         {// This operand is a data value
 374
 375           // An instruction that computes the incoming value is added as a
 376           // child of the current instruction if:
 377           //   the value has only a single use
 378           //   AND both instructions are in the same basic block
 379           //   AND the instruction is not a PHI
 380           //
 381           // (Note that if the value has only a single use (viz., `instr'),
 382           //  the def of the value can be safely moved just before instr
 383           //  and therefore it is safe to combine these two instructions.)
 384           //
 385           // In all other cases, the virtual register holding the value
 386           // is used directly, i.e., made a child of the instruction node.
 387           //
 388           InstrTreeNode* opTreeNode;
 389           if (operand->getValueType() == Value::InstructionVal
 390               && operand->use_size() == 1
 391               && ((Instruction*)operand)->getParent() == instr->getParent()
 392               && ! ((Instruction*)operand)->isPHINode())
 393             {
 394               // Recursively create a treeNode for it.
 395               opTreeNode =this->buildTreeForInstruction((Instruction*)operand);
 396             }
 397           else if (operand->getValueType() == Value::ConstantVal)
 398             {
 399               // Create a leaf node for a constant
 400               opTreeNode = new ConstantNode((ConstPoolVal*) operand);
 401             }
 402           else
 403             {
 404               // Create a leaf node for the virtual register
 405               opTreeNode = new VRegNode(operand);
 406             }
 407
 408           childArray[numChildren] = opTreeNode;
 409           numChildren++;
 410         }
 411     }
 412
 413   //--------------------------------------------------------------------
 414   // Add any selected operands as children in the tree.
 415   // Certain instructions can have more than 2 in some instances (viz.,
 416   // a CALL or a memory access -- LOAD, STORE, and GetElemPtr -- to an
 417   // array or struct). Make the operands of every such instruction into
 418   // a right-leaning binary tree with the operand nodes at the leaves
 419   // and VRegList nodes as internal nodes.
 420   //--------------------------------------------------------------------
 421
 422   InstrTreeNode* parent = treeNode;             // new VRegListNode();
 423   int n;
 424
 425   if (numChildren > 2)
 426     {
 427       unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
 428       assert(instrOpcode == Instruction::Call ||
 429              instrOpcode == Instruction::Load ||
 430              instrOpcode == Instruction::Store ||
 431              instrOpcode == Instruction::GetElementPtr);
 432     }
 433
 434   // Insert the first child as a direct child
 435   if (numChildren >= 1)
 436     this->setLeftChild(parent, childArray[0]);
 437
 438   // Create a list node for children 2 .. N-1, if any
 439   for (n = numChildren-1; n >= 2; n--)
 440     { // We have more than two children
 441       InstrTreeNode* listNode = new VRegListNode();
 442       this->setRightChild(parent, listNode);
 443       this->setLeftChild(listNode, childArray[numChildren - n]);
 444       parent = listNode;
 445     }
 446
 447   // Now insert the last remaining child (if any).
 448   if (numChildren >= 2)
 449     {
 450       assert(n == 1);
 451       this->setRightChild(parent, childArray[numChildren - 1]);
 452     }
 453
 454   if (childArray != fixedChildArray)
 455     {
 456       delete[] childArray;
 457     }
 458
 459   return treeNode;
 460 }
 461