2 //***************************************************************************
9 // 7/02/01 - Vikram Adve - Created
10 //**************************************************************************/
13 //************************** System Include Files ***************************/
16 //*************************** User Include Files ***************************/
18 #include "llvm/CodeGen/InstrSelection.h"
19 #include "llvm/Support/CommandLine.h"
20 #include "llvm/Type.h"
21 #include "llvm/iMemory.h"
22 #include "llvm/Instruction.h"
23 #include "llvm/BasicBlock.h"
24 #include "llvm/Method.h"
25 #include "llvm/CodeGen/MachineInstr.h"
28 //************************* Forward Declarations ***************************/
30 static bool SelectInstructionsForTree(BasicTreeNode* treeRoot,
32 TargetMachine &Target);
35 //************************* Internal Data Types *****************************/
37 enum SelectDebugLevel_t {
39 Select_PrintMachineCode,
40 Select_DebugInstTrees,
41 Select_DebugBurgTrees,
44 // Enable Debug Options to be specified on the command line
45 cl::Enum<enum SelectDebugLevel_t> SelectDebugLevel("dselect", cl::NoFlags, // cl::Hidden
46 "enable instruction selection debugging information",
47 clEnumValN(Select_NoDebugInfo, "n", "disable debug output"),
48 clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
49 clEnumValN(Select_DebugInstTrees, "i", "print instr. selection debugging info"),
50 clEnumValN(Select_DebugBurgTrees, "b", "print burg trees"), 0);
53 //************************** External Functions ****************************/
56 //---------------------------------------------------------------------------
57 // Entry point for instruction selection using BURG.
58 // Returns true if instruction selection failed, false otherwise.
59 //---------------------------------------------------------------------------
62 SelectInstructionsForMethod(Method* method,
63 TargetMachine &Target)
68 // Build the instruction trees to be given as inputs to BURG.
70 InstrForest instrForest;
71 instrForest.buildTreesForMethod(method);
73 if (SelectDebugLevel >= Select_DebugInstTrees)
75 cout << "\n\n*** Instruction trees for method "
76 << (method->hasName()? method->getName() : "")
82 // Invoke BURG instruction selection for each tree
84 const hash_set<InstructionNode*> &treeRoots = instrForest.getRootSet();
85 for (hash_set<InstructionNode*>::const_iterator
86 treeRootIter = treeRoots.begin();
87 treeRootIter != treeRoots.end();
90 BasicTreeNode* basicNode = (*treeRootIter)->getBasicNode();
92 // Invoke BURM to label each tree node with a state
93 (void) burm_label(basicNode);
95 if (SelectDebugLevel >= Select_DebugBurgTrees)
97 printcover(basicNode, 1, 0);
98 cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
99 printMatches(basicNode);
102 // Then recursively walk the tree to select instructions
103 if (SelectInstructionsForTree(basicNode, /*goalnt*/1, Target))
111 // Record instructions in the vector for each basic block
113 for (Method::iterator BI = method->begin(); BI != method->end(); ++BI)
115 MachineCodeForBasicBlock& bbMvec = (*BI)->getMachineInstrVec();
116 for (BasicBlock::iterator II = (*BI)->begin(); II != (*BI)->end(); ++II)
118 MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
119 for (unsigned i=0; i < mvec.size(); i++)
120 bbMvec.push_back(mvec[i]);
124 if (SelectDebugLevel >= Select_PrintMachineCode)
126 cout << endl << "*** Machine instructions after INSTRUCTION SELECTION" << endl;
127 PrintMachineInstructions(method);
134 //---------------------------------------------------------------------------
135 // Function: FoldGetElemChain
138 // Fold a chain of GetElementPtr instructions into an equivalent
139 // (Pointer, IndexVector) pair. Returns the pointer Value, and
140 // stores the resulting IndexVector in argument chainIdxVec.
141 //---------------------------------------------------------------------------
144 FoldGetElemChain(const InstructionNode* getElemInstrNode,
145 vector<ConstPoolVal*>& chainIdxVec)
147 MemAccessInst* getElemInst = (MemAccessInst*)
148 getElemInstrNode->getInstruction();
150 // Initialize return values from the incoming instruction
151 Value* ptrVal = getElemInst->getPtrOperand();
152 chainIdxVec = getElemInst->getIndexVec(); // copies index vector values
154 // Now chase the chain of getElementInstr instructions, if any
155 InstrTreeNode* ptrChild = getElemInstrNode->leftChild();
156 while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
157 ptrChild->getOpLabel() == GetElemPtrIdx)
159 // Child is a GetElemPtr instruction
160 getElemInst = (MemAccessInst*)
161 ((InstructionNode*) ptrChild)->getInstruction();
162 const vector<ConstPoolVal*>& idxVec = getElemInst->getIndexVec();
164 // Get the pointer value out of ptrChild and *prepend* its index vector
165 ptrVal = getElemInst->getPtrOperand();
166 chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end());
168 ptrChild = ptrChild->leftChild();
175 //*********************** Private Functions *****************************/
178 //---------------------------------------------------------------------------
179 // Function SelectInstructionsForTree
181 // Recursively walk the tree to select instructions.
182 // Do this top-down so that child instructions can exploit decisions
183 // made at the child instructions.
185 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
186 // a branch-on-integer-register instruction, then the setle node
187 // can use that information to avoid generating the SUBcc instruction.
189 // Note that this cannot be done bottom-up because setle must do this
190 // only if it is a child of the branch (otherwise, the result of setle
191 // may be used by multiple instructions).
192 //---------------------------------------------------------------------------
195 SelectInstructionsForTree(BasicTreeNode* treeRoot,
197 TargetMachine &Target)
199 // Use a static vector to avoid allocating a new one per VM instruction
200 static MachineInstr* minstrVec[MAX_INSTR_PER_VMINSTR];
202 // Get the rule that matches this node.
204 int ruleForNode = burm_rule(treeRoot->state, goalnt);
206 if (ruleForNode == 0)
208 cerr << "Could not match instruction tree for instr selection" << endl;
212 // Get this rule's non-terminals and the corresponding child nodes (if any)
214 short *nts = burm_nts[ruleForNode];
217 // First, select instructions for the current node and rule.
218 // (If this is a list node, not an instruction, then skip this step).
219 // This function is specific to the target architecture.
221 if (treeRoot->opLabel != VRegListOp)
223 InstructionNode* instrNode = (InstructionNode*)treeRoot->treeNodePtr;
224 assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
226 unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, Target,
228 assert(N <= MAX_INSTR_PER_VMINSTR);
229 for (unsigned i=0; i < N; i++)
231 assert(minstrVec[i] != NULL);
232 instrNode->getInstruction()->addMachineInstruction(minstrVec[i]);
236 // Then, recursively compile the child nodes, if any.
239 { // i.e., there is at least one kid
241 BasicTreeNode* kids[2];
242 int currentRule = ruleForNode;
243 burm_kids(treeRoot, currentRule, kids);
245 // First skip over any chain rules so that we don't visit
246 // the current node again.
248 while (ThisIsAChainRule(currentRule))
250 currentRule = burm_rule(treeRoot->state, nts[0]);
251 nts = burm_nts[currentRule];
252 burm_kids(treeRoot, currentRule, kids);
255 // Now we have the first non-chain rule so we have found
256 // the actual child nodes. Recursively compile them.
258 for (int i = 0; nts[i]; i++)
261 InstrTreeNode::InstrTreeNodeType
262 nodeType = kids[i]->treeNodePtr->getNodeType();
263 if (nodeType == InstrTreeNode::NTVRegListNode ||
264 nodeType == InstrTreeNode::NTInstructionNode)
266 if (SelectInstructionsForTree(kids[i], nts[i], Target))
267 return true; // failure
272 return false; // success