2 //***************************************************************************
9 // 7/02/01 - Vikram Adve - Created
10 //***************************************************************************
13 //*************************** User Include Files ***************************/
15 #include "llvm/CodeGen/InstrSelection.h"
16 #include "llvm/Method.h"
17 #include "llvm/BasicBlock.h"
18 #include "llvm/Type.h"
19 #include "llvm/iMemory.h"
20 #include "llvm/Instruction.h"
21 #include "llvm/LLC/CompileContext.h"
22 #include "llvm/CodeGen/MachineInstr.h"
25 //************************* Forward Declarations ***************************/
27 static bool SelectInstructionsForTree(BasicTreeNode* treeRoot, int goalnt,
28 CompileContext& ccontext);
31 //******************* Externally Visible Functions *************************/
34 //---------------------------------------------------------------------------
35 // Entry point for instruction selection using BURG.
36 // Returns true if instruction selection failed, false otherwise.
37 //---------------------------------------------------------------------------
39 bool SelectInstructionsForMethod(Method* method, CompileContext& ccontext,
43 InstrForest instrForest;
44 instrForest.buildTreesForMethod(method);
46 const hash_set<InstructionNode*, ptrHashFunc>&
47 treeRoots = instrForest.getRootSet();
50 // Invoke BURG instruction selection for each tree
52 for (hash_set<InstructionNode*, ptrHashFunc >::const_iterator
53 treeRootIter = treeRoots.begin();
54 treeRootIter != treeRoots.end();
57 BasicTreeNode* basicNode = (*treeRootIter)->getBasicNode();
59 // Invoke BURM to label each tree node with a state
60 (void) burm_label(basicNode);
62 if (DebugLevel >= DEBUG_BURG_TREES)
64 printcover(basicNode, 1, 0);
65 cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
66 printMatches(basicNode);
69 // Then recursively walk the tree to select instructions
70 if (SelectInstructionsForTree(basicNode, /*goalnt*/1, ccontext))
79 if (DebugLevel >= DEBUG_INSTR_TREES)
81 cout << "\n\n*** Instruction trees for method "
82 << (method->hasName()? method->getName() : "")
87 if (DebugLevel >= DEBUG_TREES_NONE)
88 PrintMachineInstructions(method);
95 //---------------------------------------------------------------------------
96 // Function: FoldGetElemChain
99 // Fold a chain of GetElementPtr instructions into an equivalent
100 // (Pointer, IndexVector) pair. Returns the pointer Value, and
101 // stores the resulting IndexVector in argument chainIdxVec.
102 //---------------------------------------------------------------------------
105 FoldGetElemChain(const InstructionNode* getElemInstrNode,
106 vector<ConstPoolVal*>& chainIdxVec)
108 MemAccessInst* getElemInst = (MemAccessInst*)
109 getElemInstrNode->getInstruction();
111 // Initialize return values from the incoming instruction
112 Value* ptrVal = getElemInst->getPtrOperand();
113 chainIdxVec = getElemInst->getIndexVec(); // copies index vector values
115 // Now chase the chain of getElementInstr instructions, if any
116 InstrTreeNode* ptrChild = getElemInstrNode->leftChild();
117 while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
118 ptrChild->getOpLabel() == GetElemPtrIdx)
120 // Child is a GetElemPtr instruction
121 getElemInst = (MemAccessInst*)
122 ((InstructionNode*) ptrChild)->getInstruction();
123 const vector<ConstPoolVal*>& idxVec = getElemInst->getIndexVec();
125 // Get the pointer value out of ptrChild and *prepend* its index vector
126 ptrVal = getElemInst->getPtrOperand();
127 chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end());
129 ptrChild = ptrChild->leftChild();
136 void PrintMachineInstructions(Method* method) {
137 cout << "\n" << method->getReturnType()
138 << " \"" << method->getName() << "\"" << endl;
140 for (Method::const_iterator bbIter = method->begin();
141 bbIter != method->end();
144 BasicBlock* bb = *bbIter;
146 << (bb->hasName()? bb->getName() : "Label")
147 << " (" << bb << ")" << ":"
150 for (BasicBlock::const_iterator instrIter = bb->begin();
151 instrIter != bb->end();
154 Instruction *instr = *instrIter;
155 const MachineCodeForVMInstr& minstrVec = instr->getMachineInstrVec();
156 for (unsigned i=0, N=minstrVec.size(); i < N; i++)
157 cout << "\t" << *minstrVec[i] << endl;
162 //*********************** Private Functions *****************************/
165 //---------------------------------------------------------------------------
166 // Function SelectInstructionsForTree
168 // Recursively walk the tree to select instructions.
169 // Do this top-down so that child instructions can exploit decisions
170 // made at the child instructions.
172 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
173 // a branch-on-integer-register instruction, then the setle node
174 // can use that information to avoid generating the SUBcc instruction.
176 // Note that this cannot be done bottom-up because setle must do this
177 // only if it is a child of the branch (otherwise, the result of setle
178 // may be used by multiple instructions).
179 //---------------------------------------------------------------------------
182 SelectInstructionsForTree(BasicTreeNode* treeRoot,
184 CompileContext& ccontext)
186 // Use a static vector to avoid allocating a new one per VM instruction
187 static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR];
189 // Get the rule that matches this node.
191 int ruleForNode = burm_rule(treeRoot->state, goalnt);
193 if (ruleForNode == 0)
195 cerr << "Could not match instruction tree for instr selection" << endl;
199 // Get this rule's non-terminals and the corresponding child nodes (if any)
201 short *nts = burm_nts[ruleForNode];
204 // First, select instructions for the current node and rule.
205 // (If this is a list node, not an instruction, then skip this step).
206 // This function is specific to the target architecture.
208 if (treeRoot->opLabel != VRegListOp)
210 InstructionNode* instrNode = (InstructionNode*) MainTreeNode(treeRoot);
211 assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
213 unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, ccontext,
215 assert(N <= MAX_INSTR_PER_VMINSTR);
216 for (unsigned i=0; i < N; i++)
218 assert(minstrVec[i] != NULL);
219 instrNode->getInstruction()->addMachineInstruction(minstrVec[i]);
223 // Then, recursively compile the child nodes, if any.
226 { // i.e., there is at least one kid
228 BasicTreeNode* kids[2];
229 int currentRule = ruleForNode;
230 burm_kids(treeRoot, currentRule, kids);
232 // First skip over any chain rules so that we don't visit
233 // the current node again.
235 while (ThisIsAChainRule(currentRule))
237 currentRule = burm_rule(treeRoot->state, nts[0]);
238 nts = burm_nts[currentRule];
239 burm_kids(treeRoot, currentRule, kids);
242 // Now we have the first non-chain rule so we have found
243 // the actual child nodes. Recursively compile them.
245 for (int i = 0; nts[i]; i++)
248 InstrTreeNode::InstrTreeNodeType
249 nodeType = MainTreeNode(kids[i])->getNodeType();
250 if (nodeType == InstrTreeNode::NTVRegListNode ||
251 nodeType == InstrTreeNode::NTInstructionNode)
253 bool failed= SelectInstructionsForTree(kids[i], nts[i],ccontext);
255 return true; // failure
260 return false; // success