DAGISelMatcherGen.cpp revision e609a513f3c072bba28412c681465332a2822d9a
1//===- DAGISelMatcherGen.cpp - Matcher generator --------------------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9 10#include "DAGISelMatcher.h" 11#include "CodeGenDAGPatterns.h" 12#include "Record.h" 13#include "llvm/ADT/StringMap.h" 14using namespace llvm; 15 16namespace { 17 class MatcherGen { 18 const PatternToMatch &Pattern; 19 const CodeGenDAGPatterns &CGP; 20 21 /// PatWithNoTypes - This is a clone of Pattern.getSrcPattern() that starts 22 /// out with all of the types removed. This allows us to insert type checks 23 /// as we scan the tree. 24 TreePatternNode *PatWithNoTypes; 25 26 /// VariableMap - A map from variable names ('$dst') to the recorded operand 27 /// number that they were captured as. These are biased by 1 to make 28 /// insertion easier. 29 StringMap<unsigned> VariableMap; 30 unsigned NextRecordedOperandNo; 31 32 MatcherNodeWithChild *Matcher; 33 MatcherNodeWithChild *CurPredicate; 34 public: 35 MatcherGen(const PatternToMatch &pattern, const CodeGenDAGPatterns &cgp); 36 37 ~MatcherGen() { 38 delete PatWithNoTypes; 39 } 40 41 void EmitMatcherCode(); 42 43 MatcherNodeWithChild *GetMatcher() const { return Matcher; } 44 MatcherNodeWithChild *GetCurPredicate() const { return CurPredicate; } 45 private: 46 void AddMatcherNode(MatcherNodeWithChild *NewNode); 47 void InferPossibleTypes(); 48 void EmitMatchCode(const TreePatternNode *N, TreePatternNode *NodeNoTypes); 49 void EmitLeafMatchCode(const TreePatternNode *N); 50 void EmitOperatorMatchCode(const TreePatternNode *N, 51 TreePatternNode *NodeNoTypes); 52 }; 53 54} // end anon namespace. 55 56MatcherGen::MatcherGen(const PatternToMatch &pattern, 57 const CodeGenDAGPatterns &cgp) 58: Pattern(pattern), CGP(cgp), NextRecordedOperandNo(0), 59 Matcher(0), CurPredicate(0) { 60 // We need to produce the matcher tree for the patterns source pattern. To do 61 // this we need to match the structure as well as the types. To do the type 62 // matching, we want to figure out the fewest number of type checks we need to 63 // emit. For example, if there is only one integer type supported by a 64 // target, there should be no type comparisons at all for integer patterns! 65 // 66 // To figure out the fewest number of type checks needed, clone the pattern, 67 // remove the types, then perform type inference on the pattern as a whole. 68 // If there are unresolved types, emit an explicit check for those types, 69 // apply the type to the tree, then rerun type inference. Iterate until all 70 // types are resolved. 71 // 72 PatWithNoTypes = Pattern.getSrcPattern()->clone(); 73 PatWithNoTypes->RemoveAllTypes(); 74 75 // If there are types that are manifestly known, infer them. 76 InferPossibleTypes(); 77} 78 79/// InferPossibleTypes - As we emit the pattern, we end up generating type 80/// checks and applying them to the 'PatWithNoTypes' tree. As we do this, we 81/// want to propagate implied types as far throughout the tree as possible so 82/// that we avoid doing redundant type checks. This does the type propagation. 83void MatcherGen::InferPossibleTypes() { 84 // TP - Get *SOME* tree pattern, we don't care which. It is only used for 85 // diagnostics, which we know are impossible at this point. 86 TreePattern &TP = *CGP.pf_begin()->second; 87 88 try { 89 bool MadeChange = true; 90 while (MadeChange) 91 MadeChange = PatWithNoTypes->ApplyTypeConstraints(TP, 92 true/*Ignore reg constraints*/); 93 } catch (...) { 94 errs() << "Type constraint application shouldn't fail!"; 95 abort(); 96 } 97} 98 99 100/// AddMatcherNode - Add a matcher node to the current graph we're building. 101void MatcherGen::AddMatcherNode(MatcherNodeWithChild *NewNode) { 102 if (CurPredicate != 0) 103 CurPredicate->setChild(NewNode); 104 else 105 Matcher = NewNode; 106 CurPredicate = NewNode; 107} 108 109 110 111/// EmitLeafMatchCode - Generate matching code for leaf nodes. 112void MatcherGen::EmitLeafMatchCode(const TreePatternNode *N) { 113 assert(N->isLeaf() && "Not a leaf?"); 114 // Direct match against an integer constant. 115 if (IntInit *II = dynamic_cast<IntInit*>(N->getLeafValue())) 116 return AddMatcherNode(new CheckIntegerMatcherNode(II->getValue())); 117 118 DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue()); 119 if (DI == 0) { 120 errs() << "Unknown leaf kind: " << *DI << "\n"; 121 abort(); 122 } 123 124 Record *LeafRec = DI->getDef(); 125 if (// Handle register references. Nothing to do here, they always match. 126 LeafRec->isSubClassOf("RegisterClass") || 127 LeafRec->isSubClassOf("PointerLikeRegClass") || 128 LeafRec->isSubClassOf("Register") || 129 // Place holder for SRCVALUE nodes. Nothing to do here. 130 LeafRec->getName() == "srcvalue") 131 return; 132 133 if (LeafRec->isSubClassOf("ValueType")) 134 return AddMatcherNode(new CheckValueTypeMatcherNode(LeafRec->getName())); 135 136 if (LeafRec->isSubClassOf("CondCode")) 137 return AddMatcherNode(new CheckCondCodeMatcherNode(LeafRec->getName())); 138 139 if (LeafRec->isSubClassOf("ComplexPattern")) { 140 // We can't model ComplexPattern uses that don't have their name taken yet. 141 // The OPC_CheckComplexPattern operation implicitly records the results. 142 if (N->getName().empty()) { 143 errs() << "We expect complex pattern uses to have names: " << *N << "\n"; 144 exit(1); 145 } 146 147 // Handle complex pattern. 148 const ComplexPattern &CP = CGP.getComplexPattern(LeafRec); 149 return AddMatcherNode(new CheckComplexPatMatcherNode(CP)); 150 } 151 152 errs() << "Unknown leaf kind: " << *N << "\n"; 153 abort(); 154} 155 156void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, 157 TreePatternNode *NodeNoTypes) { 158 assert(!N->isLeaf() && "Not an operator?"); 159 const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator()); 160 161 // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is 162 // a constant without a predicate fn that has more that one bit set, handle 163 // this as a special case. This is usually for targets that have special 164 // handling of certain large constants (e.g. alpha with it's 8/16/32-bit 165 // handling stuff). Using these instructions is often far more efficient 166 // than materializing the constant. Unfortunately, both the instcombiner 167 // and the dag combiner can often infer that bits are dead, and thus drop 168 // them from the mask in the dag. For example, it might turn 'AND X, 255' 169 // into 'AND X, 254' if it knows the low bit is set. Emit code that checks 170 // to handle this. 171 if ((N->getOperator()->getName() == "and" || 172 N->getOperator()->getName() == "or") && 173 N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty()) { 174 if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) { 175 if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. 176 if (N->getOperator()->getName() == "and") 177 AddMatcherNode(new CheckAndImmMatcherNode(II->getValue())); 178 else 179 AddMatcherNode(new CheckOrImmMatcherNode(II->getValue())); 180 181 // Match the LHS of the AND as appropriate. 182 AddMatcherNode(new MoveChildMatcherNode(0)); 183 EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0)); 184 AddMatcherNode(new MoveParentMatcherNode()); 185 return; 186 } 187 } 188 } 189 190 // Check that the current opcode lines up. 191 AddMatcherNode(new CheckOpcodeMatcherNode(CInfo.getEnumName())); 192 193 // If this node has a chain, then the chain is operand #0 is the SDNode, and 194 // the child numbers of the node are all offset by one. 195 unsigned OpNo = 0; 196 if (N->NodeHasProperty(SDNPHasChain, CGP)) { 197 OpNo = 1; 198 199 // If this node is not the root and the subtree underneath it produces a 200 // chain, then the result of matching the node is also produce a chain. 201 // Beyond that, this means that we're also folding (at least) the root node 202 // into the node that produce the chain (for example, matching 203 // "(add reg, (load ptr))" as a add_with_memory on X86). This is 204 // problematic, if the 'reg' node also uses the load (say, its chain). 205 // Graphically: 206 // 207 // [LD] 208 // ^ ^ 209 // | \ DAG's like cheese. 210 // / | 211 // / [YY] 212 // | ^ 213 // [XX]--/ 214 // 215 // It would be invalid to fold XX and LD. In this case, folding the two 216 // nodes together would induce a cycle in the DAG, making it a 'cyclic DAG' 217 // To prevent this, we emit a dynamic check for legality before allowing 218 // this to be folded. 219 // 220 const TreePatternNode *Root = Pattern.getSrcPattern(); 221 if (N != Root) { // Not the root of the pattern. 222 // If there is a node between the root and this node, then we definitely 223 // need to emit the check. 224 bool NeedCheck = !Root->hasChild(N); 225 226 // If it *is* an immediate child of the root, we can still need a check if 227 // the root SDNode has multiple inputs. For us, this means that it is an 228 // intrinsic, has multiple operands, or has other inputs like chain or 229 // flag). 230 if (!NeedCheck) { 231 const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root->getOperator()); 232 NeedCheck = 233 Root->getOperator() == CGP.get_intrinsic_void_sdnode() || 234 Root->getOperator() == CGP.get_intrinsic_w_chain_sdnode() || 235 Root->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() || 236 PInfo.getNumOperands() > 1 || 237 PInfo.hasProperty(SDNPHasChain) || 238 PInfo.hasProperty(SDNPInFlag) || 239 PInfo.hasProperty(SDNPOptInFlag); 240 } 241 242 if (NeedCheck) 243 AddMatcherNode(new CheckFoldableChainNodeMatcherNode()); 244 } 245 } 246 247 // FIXME: Need to generate IsChainCompatible checks. 248 249 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { 250 // Get the code suitable for matching this child. Move to the child, check 251 // it then move back to the parent. 252 AddMatcherNode(new MoveChildMatcherNode(i)); 253 EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i)); 254 AddMatcherNode(new MoveParentMatcherNode()); 255 } 256} 257 258 259void MatcherGen::EmitMatchCode(const TreePatternNode *N, 260 TreePatternNode *NodeNoTypes) { 261 // If N and NodeNoTypes don't agree on a type, then this is a case where we 262 // need to do a type check. Emit the check, apply the tyep to NodeNoTypes and 263 // reinfer any correlated types. 264 if (NodeNoTypes->getExtTypes() != N->getExtTypes()) { 265 AddMatcherNode(new CheckTypeMatcherNode(N->getTypeNum(0))); 266 NodeNoTypes->setTypes(N->getExtTypes()); 267 InferPossibleTypes(); 268 } 269 270 271 // If this node has a name associated with it, capture it in VariableMap. If 272 // we already saw this in the pattern, emit code to verify dagness. 273 if (!N->getName().empty()) { 274 unsigned &VarMapEntry = VariableMap[N->getName()]; 275 if (VarMapEntry == 0) { 276 VarMapEntry = NextRecordedOperandNo+1; 277 278 unsigned NumRecorded; 279 280 // If this is a complex pattern, the match operation for it will 281 // implicitly record all of the outputs of it (which may be more than 282 // one). 283 if (const ComplexPattern *AM = N->getComplexPatternInfo(CGP)) { 284 // Record the right number of operands. 285 NumRecorded = AM->getNumOperands()-1; 286 287 if (AM->hasProperty(SDNPHasChain)) 288 NumRecorded += 2; // Input and output chains. 289 } else { 290 // If it is a normal named node, we must emit a 'Record' opcode. 291 AddMatcherNode(new RecordMatcherNode()); 292 NumRecorded = 1; 293 } 294 NextRecordedOperandNo += NumRecorded; 295 296 } else { 297 // If we get here, this is a second reference to a specific name. Since 298 // we already have checked that the first reference is valid, we don't 299 // have to recursively match it, just check that it's the same as the 300 // previously named thing. 301 AddMatcherNode(new CheckSameMatcherNode(VarMapEntry-1)); 302 return; 303 } 304 } 305 306 // If there are node predicates for this node, generate their checks. 307 for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) 308 AddMatcherNode(new CheckPredicateMatcherNode(N->getPredicateFns()[i])); 309 310 if (N->isLeaf()) 311 EmitLeafMatchCode(N); 312 else 313 EmitOperatorMatchCode(N, NodeNoTypes); 314} 315 316void MatcherGen::EmitMatcherCode() { 317 // If the pattern has a predicate on it (e.g. only enabled when a subtarget 318 // feature is around, do the check). 319 if (!Pattern.getPredicateCheck().empty()) 320 AddMatcherNode(new 321 CheckPatternPredicateMatcherNode(Pattern.getPredicateCheck())); 322 323 // Emit the matcher for the pattern structure and types. 324 EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes); 325} 326 327 328MatcherNode *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern, 329 const CodeGenDAGPatterns &CGP) { 330 MatcherGen Gen(Pattern, CGP); 331 332 // Generate the code for the matcher. 333 Gen.EmitMatcherCode(); 334 335 // If the match succeeds, then we generate Pattern. 336 EmitNodeMatcherNode *Result = new EmitNodeMatcherNode(Pattern); 337 338 // Link it into the pattern. 339 if (MatcherNodeWithChild *Pred = Gen.GetCurPredicate()) { 340 Pred->setChild(Result); 341 return Gen.GetMatcher(); 342 } 343 344 // Unconditional match. 345 return Result; 346} 347 348 349 350