2 //***************************************************************************
7 // Machine-independent driver file for instruction selection.
8 // This file constructs a forest of BURG instruction trees and then
9 // use the BURG-generated tree grammar (BURM) to find the optimal
10 // instruction sequences for a given machine.
13 // 7/02/01 - Vikram Adve - Created
14 //**************************************************************************/
17 #include "llvm/CodeGen/InstrSelection.h"
18 #include "llvm/CodeGen/MachineInstr.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"
26 static bool SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
27 TargetMachine &Target);
30 enum SelectDebugLevel_t {
32 Select_PrintMachineCode,
33 Select_DebugInstTrees,
34 Select_DebugBurgTrees,
37 // Enable Debug Options to be specified on the command line
38 cl::Enum<enum SelectDebugLevel_t> SelectDebugLevel("dselect", cl::NoFlags,
39 "enable instruction selection debugging information",
40 clEnumValN(Select_NoDebugInfo, "n", "disable debug output"),
41 clEnumValN(Select_PrintMachineCode, "y", "print generated machine code"),
42 clEnumValN(Select_DebugInstTrees, "i", "print debugging info for instruction selection "),
43 clEnumValN(Select_DebugBurgTrees, "b", "print burg trees"), 0);
47 //---------------------------------------------------------------------------
48 // Entry point for instruction selection using BURG.
49 // Returns true if instruction selection failed, false otherwise.
50 //---------------------------------------------------------------------------
53 SelectInstructionsForMethod(Method* method, TargetMachine &Target)
58 // Build the instruction trees to be given as inputs to BURG.
60 InstrForest instrForest(method);
62 if (SelectDebugLevel >= Select_DebugInstTrees)
64 cout << "\n\n*** Instruction trees for method "
65 << (method->hasName()? method->getName() : "")
71 // Invoke BURG instruction selection for each tree
73 const hash_set<InstructionNode*> &treeRoots = instrForest.getRootSet();
74 for (hash_set<InstructionNode*>::const_iterator
75 treeRootIter = treeRoots.begin(); treeRootIter != treeRoots.end();
78 InstrTreeNode* basicNode = *treeRootIter;
80 // Invoke BURM to label each tree node with a state
81 burm_label(basicNode);
83 if (SelectDebugLevel >= Select_DebugBurgTrees)
85 printcover(basicNode, 1, 0);
86 cerr << "\nCover cost == " << treecost(basicNode, 1, 0) << "\n\n";
87 printMatches(basicNode);
90 // Then recursively walk the tree to select instructions
91 if (SelectInstructionsForTree(basicNode, /*goalnt*/1, Target))
99 // Record instructions in the vector for each basic block
101 for (Method::iterator BI = method->begin(); BI != method->end(); ++BI)
103 MachineCodeForBasicBlock& bbMvec = (*BI)->getMachineInstrVec();
104 for (BasicBlock::iterator II = (*BI)->begin(); II != (*BI)->end(); ++II)
106 MachineCodeForVMInstr& mvec = (*II)->getMachineInstrVec();
107 for (unsigned i=0; i < mvec.size(); i++)
108 bbMvec.push_back(mvec[i]);
112 if (SelectDebugLevel >= Select_PrintMachineCode)
114 cout << endl << "*** Machine instructions after INSTRUCTION SELECTION" << endl;
115 PrintMachineInstructions(method);
122 //---------------------------------------------------------------------------
123 // Function: FoldGetElemChain
126 // Fold a chain of GetElementPtr instructions into an equivalent
127 // (Pointer, IndexVector) pair. Returns the pointer Value, and
128 // stores the resulting IndexVector in argument chainIdxVec.
129 //---------------------------------------------------------------------------
132 FoldGetElemChain(const InstructionNode* getElemInstrNode,
133 vector<ConstPoolVal*>& chainIdxVec)
135 MemAccessInst* getElemInst = (MemAccessInst*)
136 getElemInstrNode->getInstruction();
138 // Initialize return values from the incoming instruction
139 Value* ptrVal = getElemInst->getPtrOperand();
140 chainIdxVec = getElemInst->getIndexVec(); // copies index vector values
142 // Now chase the chain of getElementInstr instructions, if any
143 InstrTreeNode* ptrChild = getElemInstrNode->leftChild();
144 while (ptrChild->getOpLabel() == Instruction::GetElementPtr ||
145 ptrChild->getOpLabel() == GetElemPtrIdx)
147 // Child is a GetElemPtr instruction
148 getElemInst = (MemAccessInst*)
149 ((InstructionNode*) ptrChild)->getInstruction();
150 const vector<ConstPoolVal*>& idxVec = getElemInst->getIndexVec();
152 // Get the pointer value out of ptrChild and *prepend* its index vector
153 ptrVal = getElemInst->getPtrOperand();
154 chainIdxVec.insert(chainIdxVec.begin(), idxVec.begin(), idxVec.end());
156 ptrChild = ptrChild->leftChild();
163 //*********************** Private Functions *****************************/
166 //---------------------------------------------------------------------------
167 // Function SelectInstructionsForTree
169 // Recursively walk the tree to select instructions.
170 // Do this top-down so that child instructions can exploit decisions
171 // made at the child instructions.
173 // E.g., if br(setle(reg,const)) decides the constant is 0 and uses
174 // a branch-on-integer-register instruction, then the setle node
175 // can use that information to avoid generating the SUBcc instruction.
177 // Note that this cannot be done bottom-up because setle must do this
178 // only if it is a child of the branch (otherwise, the result of setle
179 // may be used by multiple instructions).
180 //---------------------------------------------------------------------------
183 SelectInstructionsForTree(InstrTreeNode* treeRoot, int goalnt,
184 TargetMachine &Target)
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;
200 // Get this rule's non-terminals and the corresponding child nodes (if any)
202 short *nts = burm_nts[ruleForNode];
205 // First, select instructions for the current node and rule.
206 // (If this is a list node, not an instruction, then skip this step).
207 // This function is specific to the target architecture.
209 if (treeRoot->opLabel != VRegListOp)
211 InstructionNode* instrNode = (InstructionNode*)treeRoot;
212 assert(instrNode->getNodeType() == InstrTreeNode::NTInstructionNode);
214 unsigned N = GetInstructionsByRule(instrNode, ruleForNode, nts, Target,
216 assert(N <= MAX_INSTR_PER_VMINSTR);
217 for (unsigned i=0; i < N; i++)
219 assert(minstrVec[i] != NULL);
220 instrNode->getInstruction()->addMachineInstruction(minstrVec[i]);
224 // Then, recursively compile the child nodes, if any.
227 { // i.e., there is at least one kid
228 InstrTreeNode* 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 nodeType = kids[i]->getNodeType();
249 if (nodeType == InstrTreeNode::NTVRegListNode ||
250 nodeType == InstrTreeNode::NTInstructionNode)
252 if (SelectInstructionsForTree(kids[i], nts[i], Target))
253 return true; // failure
258 return false; // success