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/CodeGen/MachineInstr.h"
20 #include "llvm/Support/CommandLine.h"
29 // Enable Debug Options to be specified on the command line
30 cl::Enum<enum DebugLev> DebugLevel("dselect", cl::NoFlags, // cl::Hidden
31 "enable instruction selection debugging information",
32 clEnumValN(NoDebugInfo, "n", "disable debug output"),
33 clEnumValN(PrintInstTrees, "y", "print generated instruction trees"),
34 clEnumValN(DebugInstTrees, "i", "print instr. selection debugging info"),
35 clEnumValN(DebugBurgTrees, "b", "print burg trees"), 0);
37 //************************* Forward Declarations ***************************/
39 static bool SelectInstructionsForTree(BasicTreeNode* treeRoot, int goalnt,
40 TargetMachine &Target);
43 //******************* Externally Visible Functions *************************/
46 //---------------------------------------------------------------------------
47 // Entry point for instruction selection using BURG.
48 // Returns true if instruction selection failed, false otherwise.
49 //---------------------------------------------------------------------------
51 bool SelectInstructionsForMethod(Method* method, TargetMachine &Target) {
54 InstrForest instrForest;
55 instrForest.buildTreesForMethod(method);
57 const hash_set<InstructionNode*> &treeRoots = instrForest.getRootSet();
60 // Invoke BURG instruction selection for each tree
62 for (hash_set<InstructionNode*>::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 >= 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, Target))
89 if (DebugLevel >= DebugInstTrees)
91 cout << "\n\n*** Instruction trees for method "
92 << (method->hasName()? method->getName() : "")
97 if (DebugLevel >= PrintInstTrees)
98 PrintMachineInstructions(method);
102 // Record instructions in the vector for each basic block
104 for (Method::iterator BI = method->begin(); BI != method->end(); ++BI)
106 MachineCodeForBasicBlock& bbMvec = (*BI)->getMachineInstrVec();
107 for (BasicBlock::iterator II = (*BI)->begin(); II != (*BI)->end(); ++II)
109 MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
110 for (unsigned i=0; i < mvec.size(); i++)
111 bbMvec.push_back(mvec[i]);
119 //---------------------------------------------------------------------------
120 // Function: FoldGetElemChain
123 // Fold a chain of GetElementPtr instructions into an equivalent
124 // (Pointer, IndexVector) pair. Returns the pointer Value, and
125 // stores the resulting IndexVector in argument chainIdxVec.
126 //---------------------------------------------------------------------------
129 FoldGetElemChain(const InstructionNode* getElemInstrNode,
130 vector<ConstPoolVal*>& chainIdxVec)
132 MemAccessInst* getElemInst = (MemAccessInst*)
133 getElemInstrNode->getInstruction();
135 // Initialize return values from the incoming instruction
136 Value* ptrVal = getElemInst->getPtrOperand();
137 chainIdxVec = getElemInst->getIndexVec(); // copies index vector values
139 // Now chase the chain of getElementInstr instructions, if any
140 InstrTreeNode* ptrChild = getElemInstrNode->leftChild();
141 while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
142 ptrChild->getOpLabel() == GetElemPtrIdx)
144 // Child is a GetElemPtr instruction
145 getElemInst = (MemAccessInst*)
146 ((InstructionNode*) ptrChild)->getInstruction();
147 const vector<ConstPoolVal*>& idxVec = getElemInst->getIndexVec();
149 // Get the pointer value out of ptrChild and *prepend* its index vector
150 ptrVal = getElemInst->getPtrOperand();
151 chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end());
153 ptrChild = ptrChild->leftChild();
160 void PrintMachineInstructions(Method* method) {
161 cout << "\n" << method->getReturnType()
162 << " \"" << method->getName() << "\"" << endl;
164 for (Method::const_iterator bbIter = method->begin();
165 bbIter != method->end();
168 BasicBlock* bb = *bbIter;
170 << (bb->hasName()? bb->getName() : "Label")
171 << " (" << bb << ")" << ":"
174 for (BasicBlock::const_iterator instrIter = bb->begin();
175 instrIter != bb->end();
178 Instruction *instr = *instrIter;
179 const MachineCodeForVMInstr& minstrVec = instr->getMachineInstrVec();
180 for (unsigned i=0, N=minstrVec.size(); i < N; i++)
181 cout << "\t" << *minstrVec[i] << endl;
186 //*********************** Private Functions *****************************/
189 //---------------------------------------------------------------------------
190 // Function SelectInstructionsForTree
192 // Recursively walk the tree to select instructions.
193 // Do this top-down so that child instructions can exploit decisions
194 // made at the child instructions.
196 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
197 // a branch-on-integer-register instruction, then the setle node
198 // can use that information to avoid generating the SUBcc instruction.
200 // Note that this cannot be done bottom-up because setle must do this
201 // only if it is a child of the branch (otherwise, the result of setle
202 // may be used by multiple instructions).
203 //---------------------------------------------------------------------------
206 SelectInstructionsForTree(BasicTreeNode* treeRoot,
208 TargetMachine &Target)
210 // Use a static vector to avoid allocating a new one per VM instruction
211 static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR];
213 // Get the rule that matches this node.
215 int ruleForNode = burm_rule(treeRoot->state, goalnt);
217 if (ruleForNode == 0)
219 cerr << "Could not match instruction tree for instr selection" << endl;
223 // Get this rule's non-terminals and the corresponding child nodes (if any)
225 short *nts = burm_nts[ruleForNode];
228 // First, select instructions for the current node and rule.
229 // (If this is a list node, not an instruction, then skip this step).
230 // This function is specific to the target architecture.
232 if (treeRoot->opLabel != VRegListOp)
234 InstructionNode* instrNode = (InstructionNode*) MainTreeNode(treeRoot);
235 assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
237 unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, Target,
239 assert(N <= MAX_INSTR_PER_VMINSTR);
240 for (unsigned i=0; i < N; i++)
242 assert(minstrVec[i] != NULL);
243 instrNode->getInstruction()->addMachineInstruction(minstrVec[i]);
247 // Then, recursively compile the child nodes, if any.
250 { // i.e., there is at least one kid
252 BasicTreeNode* kids[2];
253 int currentRule = ruleForNode;
254 burm_kids(treeRoot, currentRule, kids);
256 // First skip over any chain rules so that we don't visit
257 // the current node again.
259 while (ThisIsAChainRule(currentRule))
261 currentRule = burm_rule(treeRoot->state, nts[0]);
262 nts = burm_nts[currentRule];
263 burm_kids(treeRoot, currentRule, kids);
266 // Now we have the first non-chain rule so we have found
267 // the actual child nodes. Recursively compile them.
269 for (int i = 0; nts[i]; i++)
272 InstrTreeNode::InstrTreeNodeType
273 nodeType = MainTreeNode(kids[i])->getNodeType();
274 if (nodeType == InstrTreeNode::NTVRegListNode ||
275 nodeType == InstrTreeNode::NTInstructionNode)
277 if (SelectInstructionsForTree(kids[i], nts[i], Target))
278 return true; // failure
283 return false; // success