2 //---------------------------------------------------------------------------
7 // Convert SSA graph to instruction trees for instruction selection.
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.
21 // 6/28/01 - Vikram Adve - Created
23 //---------------------------------------------------------------------------
26 //************************** System Include Files **************************/
33 //*************************** User Include Files ***************************/
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"
50 //************************ Class Implementations **************************/
53 //------------------------------------------------------------------------
54 // class InstrTreeNode
55 //------------------------------------------------------------------------
58 InstrTreeNode::InstrTreeNode(InstrTreeNodeType nodeType,
60 : treeNodeType(nodeType),
63 basicNode.leftChild = NULL;
64 basicNode.rightChild = NULL;
65 basicNode.parent = NULL;
66 basicNode.opLabel = InvalidOp;
67 basicNode.treeNodePtr = this;
70 InstrTreeNode::~InstrTreeNode()
75 InstrTreeNode::dump(int dumpChildren,
78 this->dumpNode(indent);
83 leftChild()->dump(dumpChildren, indent+1);
85 rightChild()->dump(dumpChildren, indent+1);
90 InstructionNode::InstructionNode(Instruction* _instr)
91 : InstrTreeNode(NTInstructionNode, _instr)
93 OpLabel opLabel = _instr->getOpcode();
95 // Distinguish special cases of some instructions such as Ret and Br
97 if (opLabel == Instruction::Ret && ((ReturnInst*) _instr)->getReturnValue())
99 opLabel = RetValueOp; // ret(value) operation
101 else if (opLabel == Instruction::Br && ! ((BranchInst*) _instr)->isUnconditional())
103 opLabel = BrCondOp; // br(cond) operation
105 else if (opLabel >= Instruction::SetEQ && opLabel <= Instruction::SetGT)
107 opLabel = SetCCOp; // common label for all SetCC ops
109 else if (opLabel == Instruction::Alloca && _instr->getNumOperands() > 0)
111 opLabel = AllocaN; // Alloca(ptr, N) operation
113 else if ((opLabel == Instruction::Load ||
114 opLabel == Instruction::GetElementPtr)
115 && ((MemAccessInst*)_instr)->getFirstOffsetIdx() > 0)
117 opLabel = opLabel + 100; // load/getElem with index vector
119 else if (opLabel == Instruction::Cast)
121 const Type* instrValueType = _instr->getType();
122 switch(instrValueType->getPrimitiveID())
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;
136 if (instrValueType->isArrayType())
138 else if (instrValueType->isPointerType())
139 opLabel = ToPointerTy;
141 ; // Just use `Cast' opcode otherwise. It's probably ignored.
146 basicNode.opLabel = opLabel;
150 InstructionNode::reverseBinaryArgumentOrder()
152 assert(getInstruction()->isBinaryOp());
154 // switch arguments for the instruction
155 ((BinaryOperator*) getInstruction())->swapOperands();
157 // switch arguments for this tree node itself
158 BasicTreeNode* leftCopy = basicNode.leftChild;
159 basicNode.leftChild = basicNode.rightChild;
160 basicNode.rightChild = leftCopy;
164 InstructionNode::dumpNode(int indent) const
166 for (int i=0; i < indent; i++)
169 cout << getInstruction()->getOpcodeName();
171 const vector<MachineInstr*>& mvec = getInstruction()->getMachineInstrVec();
173 cout << "\tMachine Instructions: ";
174 for (unsigned int i=0; i < mvec.size(); i++)
177 if (i < mvec.size() - 1)
185 VRegListNode::VRegListNode()
186 : InstrTreeNode(NTVRegListNode, NULL)
188 basicNode.opLabel = VRegListOp;
192 VRegListNode::dumpNode(int indent) const
194 for (int i=0; i < indent; i++)
197 cout << "List" << endl;
201 VRegNode::VRegNode(Value* _val)
202 : InstrTreeNode(NTVRegNode, _val)
204 basicNode.opLabel = VRegNodeOp;
208 VRegNode::dumpNode(int indent) const
210 for (int i=0; i < indent; i++)
213 cout << "VReg " << getValue() << "\t(type "
214 << (int) getValue()->getValueType() << ")" << endl;
218 ConstantNode::ConstantNode(ConstPoolVal* constVal)
219 : InstrTreeNode(NTConstNode, constVal)
221 basicNode.opLabel = ConstantNodeOp;
225 ConstantNode::dumpNode(int indent) const
227 for (int i=0; i < indent; i++)
230 cout << "Constant " << getValue() << "\t(type "
231 << (int) getValue()->getValueType() << ")" << endl;
235 LabelNode::LabelNode(BasicBlock* _bblock)
236 : InstrTreeNode(NTLabelNode, _bblock)
238 basicNode.opLabel = LabelNodeOp;
242 LabelNode::dumpNode(int indent) const
244 for (int i=0; i < indent; i++)
247 cout << "Label " << getValue() << endl;
250 //------------------------------------------------------------------------
253 // A forest of instruction trees, usually for a single method.
254 //------------------------------------------------------------------------
257 InstrForest::buildTreesForMethod(Method *method)
259 for (Method::inst_iterator instrIter = method->inst_begin();
260 instrIter != method->inst_end();
263 Instruction *instr = *instrIter;
264 if (! instr->isPHINode())
265 (void) this->buildTreeForInstruction(instr);
271 InstrForest::dump() const
273 for (hash_set<InstructionNode*, ptrHashFunc >::const_iterator
274 treeRootIter = treeRoots.begin();
275 treeRootIter != treeRoots.end();
278 (*treeRootIter)->dump(/*dumpChildren*/ 1, /*indent*/ 0);
283 InstrForest::noteTreeNodeForInstr(Instruction* instr,
284 InstructionNode* treeNode)
286 assert(treeNode->getNodeType() == InstrTreeNode::NTInstructionNode);
287 (*this)[instr] = treeNode;
288 treeRoots.insert(treeNode); // mark node as root of a new tree
293 InstrForest::setLeftChild(InstrTreeNode* parent, InstrTreeNode* child)
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
303 InstrForest::setRightChild(InstrTreeNode* parent, InstrTreeNode* child)
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
313 InstrForest::buildTreeForInstruction(Instruction* instr)
315 InstructionNode* treeNode = this->getTreeNodeForInstr(instr);
316 if (treeNode != NULL)
317 {// treeNode has already been constructed for this instruction
318 assert(treeNode->getInstruction() == instr);
322 // Otherwise, create a new tree node for this instruction.
324 treeNode = new InstructionNode(instr);
325 this->noteTreeNodeForInstr(instr, treeNode);
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.
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.
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()]
349 // Walk the operands of the instruction
351 for (Instruction::op_iterator opIter = instr->op_begin();
352 opIter != instr->op_end();
355 Value* operand = *opIter;
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.
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());
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
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
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.)
385 // In all other cases, the virtual register holding the value
386 // is used directly, i.e., made a child of the instruction node.
388 InstrTreeNode* opTreeNode;
389 if (operand->getValueType() == Value::InstructionVal
390 && operand->use_size() == 1
391 && ((Instruction*)operand)->getParent() == instr->getParent()
392 && ! ((Instruction*)operand)->isPHINode())
394 // Recursively create a treeNode for it.
395 opTreeNode =this->buildTreeForInstruction((Instruction*)operand);
397 else if (operand->getValueType() == Value::ConstantVal)
399 // Create a leaf node for a constant
400 opTreeNode = new ConstantNode((ConstPoolVal*) operand);
404 // Create a leaf node for the virtual register
405 opTreeNode = new VRegNode(operand);
408 childArray[numChildren] = opTreeNode;
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 //--------------------------------------------------------------------
422 InstrTreeNode* parent = treeNode; // new VRegListNode();
427 unsigned instrOpcode = treeNode->getInstruction()->getOpcode();
428 assert(instrOpcode == Instruction::Call ||
429 instrOpcode == Instruction::Load ||
430 instrOpcode == Instruction::Store ||
431 instrOpcode == Instruction::GetElementPtr);
434 // Insert the first child as a direct child
435 if (numChildren >= 1)
436 this->setLeftChild(parent, childArray[0]);
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]);
447 // Now insert the last remaining child (if any).
448 if (numChildren >= 2)
451 this->setRightChild(parent, childArray[numChildren - 1]);
454 if (childArray != fixedChildArray)