2 //***************************************************************************
9 // 7/02/01 - Vikram Adve - Created
10 //***************************************************************************
13 #include "llvm/CodeGen/InstrSelection.h"
14 #include "llvm/Method.h"
15 #include "llvm/BasicBlock.h"
16 #include "llvm/Type.h"
17 #include "llvm/iMemory.h"
18 #include "llvm/Instruction.h"
19 #include "llvm/LLC/CompileContext.h"
20 #include "llvm/CodeGen/MachineInstr.h"
21 #include "llvm/Tools/CommandLine.h"
29 // Enable Debug Options to be specified on the command line
30 cl::Enum<enum DebugLev> DebugLevel("debug_select", cl::NoFlags, // cl::Hidden
31 "enable instruction selection debugging information",
32 clEnumVal(NoDebugInfo , "disable debug output"),
33 clEnumVal(DebugInstTrees, "print instruction trees"),
34 clEnumVal(DebugBurgTrees, "print burg trees"), 0);
36 //************************* Forward Declarations ***************************/
38 static bool SelectInstructionsForTree(BasicTreeNode* treeRoot, int goalnt,
39 CompileContext& ccontext);
42 //******************* Externally Visible Functions *************************/
45 //---------------------------------------------------------------------------
46 // Entry point for instruction selection using BURG.
47 // Returns true if instruction selection failed, false otherwise.
48 //---------------------------------------------------------------------------
50 bool SelectInstructionsForMethod(Method* method, CompileContext& ccontext) {
53 InstrForest instrForest;
54 instrForest.buildTreesForMethod(method);
56 const hash_set<InstructionNode*, ptrHashFunc>&
57 treeRoots = instrForest.getRootSet();
60 // Invoke BURG instruction selection for each tree
62 for (hash_set<InstructionNode*, ptrHashFunc >::const_iterator
63 treeRootIter = treeRoots.begin();
64 treeRootIter != treeRoots.end();
67 BasicTreeNode* basicNode = (*treeRootIter)->getBasicNode();
69 // Invoke BURM to label each tree node with a state
70 (void) burm_label(basicNode);
72 if (DebugLevel.getValue() >= DebugBurgTrees)
74 printcover(basicNode, 1, 0);
75 cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
76 printMatches(basicNode);
79 // Then recursively walk the tree to select instructions
80 if (SelectInstructionsForTree(basicNode, /*goalnt*/1, ccontext))
89 if (DebugLevel.getValue() >= DebugInstTrees)
91 cout << "\n\n*** Instruction trees for method "
92 << (method->hasName()? method->getName() : "")
97 if (DebugLevel.getValue() > NoDebugInfo)
98 PrintMachineInstructions(method);
105 //---------------------------------------------------------------------------
106 // Function: FoldGetElemChain
109 // Fold a chain of GetElementPtr instructions into an equivalent
110 // (Pointer, IndexVector) pair. Returns the pointer Value, and
111 // stores the resulting IndexVector in argument chainIdxVec.
112 //---------------------------------------------------------------------------
115 FoldGetElemChain(const InstructionNode* getElemInstrNode,
116 vector<ConstPoolVal*>& chainIdxVec)
118 MemAccessInst* getElemInst = (MemAccessInst*)
119 getElemInstrNode->getInstruction();
121 // Initialize return values from the incoming instruction
122 Value* ptrVal = getElemInst->getPtrOperand();
123 chainIdxVec = getElemInst->getIndexVec(); // copies index vector values
125 // Now chase the chain of getElementInstr instructions, if any
126 InstrTreeNode* ptrChild = getElemInstrNode->leftChild();
127 while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
128 ptrChild->getOpLabel() == GetElemPtrIdx)
130 // Child is a GetElemPtr instruction
131 getElemInst = (MemAccessInst*)
132 ((InstructionNode*) ptrChild)->getInstruction();
133 const vector<ConstPoolVal*>& idxVec = getElemInst->getIndexVec();
135 // Get the pointer value out of ptrChild and *prepend* its index vector
136 ptrVal = getElemInst->getPtrOperand();
137 chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end());
139 ptrChild = ptrChild->leftChild();
146 void PrintMachineInstructions(Method* method) {
147 cout << "\n" << method->getReturnType()
148 << " \"" << method->getName() << "\"" << endl;
150 for (Method::const_iterator bbIter = method->begin();
151 bbIter != method->end();
154 BasicBlock* bb = *bbIter;
156 << (bb->hasName()? bb->getName() : "Label")
157 << " (" << bb << ")" << ":"
160 for (BasicBlock::const_iterator instrIter = bb->begin();
161 instrIter != bb->end();
164 Instruction *instr = *instrIter;
165 const MachineCodeForVMInstr& minstrVec = instr->getMachineInstrVec();
166 for (unsigned i=0, N=minstrVec.size(); i < N; i++)
167 cout << "\t" << *minstrVec[i] << endl;
172 //*********************** Private Functions *****************************/
175 //---------------------------------------------------------------------------
176 // Function SelectInstructionsForTree
178 // Recursively walk the tree to select instructions.
179 // Do this top-down so that child instructions can exploit decisions
180 // made at the child instructions.
182 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
183 // a branch-on-integer-register instruction, then the setle node
184 // can use that information to avoid generating the SUBcc instruction.
186 // Note that this cannot be done bottom-up because setle must do this
187 // only if it is a child of the branch (otherwise, the result of setle
188 // may be used by multiple instructions).
189 //---------------------------------------------------------------------------
192 SelectInstructionsForTree(BasicTreeNode* treeRoot,
194 CompileContext& ccontext)
196 // Use a static vector to avoid allocating a new one per VM instruction
197 static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR];
199 // Get the rule that matches this node.
201 int ruleForNode = burm_rule(treeRoot->state, goalnt);
203 if (ruleForNode == 0)
205 cerr << "Could not match instruction tree for instr selection" << endl;
209 // Get this rule's non-terminals and the corresponding child nodes (if any)
211 short *nts = burm_nts[ruleForNode];
214 // First, select instructions for the current node and rule.
215 // (If this is a list node, not an instruction, then skip this step).
216 // This function is specific to the target architecture.
218 if (treeRoot->opLabel != VRegListOp)
220 InstructionNode* instrNode = (InstructionNode*) MainTreeNode(treeRoot);
221 assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
223 unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, ccontext,
225 assert(N <= MAX_INSTR_PER_VMINSTR);
226 for (unsigned i=0; i < N; i++)
228 assert(minstrVec[i] != NULL);
229 instrNode->getInstruction()->addMachineInstruction(minstrVec[i]);
233 // Then, recursively compile the child nodes, if any.
236 { // i.e., there is at least one kid
238 BasicTreeNode* kids[2];
239 int currentRule = ruleForNode;
240 burm_kids(treeRoot, currentRule, kids);
242 // First skip over any chain rules so that we don't visit
243 // the current node again.
245 while (ThisIsAChainRule(currentRule))
247 currentRule = burm_rule(treeRoot->state, nts[0]);
248 nts = burm_nts[currentRule];
249 burm_kids(treeRoot, currentRule, kids);
252 // Now we have the first non-chain rule so we have found
253 // the actual child nodes. Recursively compile them.
255 for (int i = 0; nts[i]; i++)
258 InstrTreeNode::InstrTreeNodeType
259 nodeType = MainTreeNode(kids[i])->getNodeType();
260 if (nodeType == InstrTreeNode::NTVRegListNode ||
261 nodeType == InstrTreeNode::NTInstructionNode)
263 bool failed= SelectInstructionsForTree(kids[i], nts[i],ccontext);
265 return true; // failure
270 return false; // success