DAGISelMatcherGen.cpp revision e39650a805425ffdbd79692c7d1bad80f7332dae
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 // Handle complex pattern. 141 const ComplexPattern &CP = CGP.getComplexPattern(LeafRec); 142 return AddMatcherNode(new CheckComplexPatMatcherNode(CP)); 143 } 144 145 errs() << "Unknown leaf kind: " << *N << "\n"; 146 abort(); 147} 148 149void MatcherGen::EmitOperatorMatchCode(const TreePatternNode *N, 150 TreePatternNode *NodeNoTypes) { 151 assert(!N->isLeaf() && "Not an operator?"); 152 const SDNodeInfo &CInfo = CGP.getSDNodeInfo(N->getOperator()); 153 154 // If this is an 'and R, 1234' where the operation is AND/OR and the RHS is 155 // a constant without a predicate fn that has more that one bit set, handle 156 // this as a special case. This is usually for targets that have special 157 // handling of certain large constants (e.g. alpha with it's 8/16/32-bit 158 // handling stuff). Using these instructions is often far more efficient 159 // than materializing the constant. Unfortunately, both the instcombiner 160 // and the dag combiner can often infer that bits are dead, and thus drop 161 // them from the mask in the dag. For example, it might turn 'AND X, 255' 162 // into 'AND X, 254' if it knows the low bit is set. Emit code that checks 163 // to handle this. 164 if ((N->getOperator()->getName() == "and" || 165 N->getOperator()->getName() == "or") && 166 N->getChild(1)->isLeaf() && N->getChild(1)->getPredicateFns().empty()) { 167 if (IntInit *II = dynamic_cast<IntInit*>(N->getChild(1)->getLeafValue())) { 168 if (!isPowerOf2_32(II->getValue())) { // Don't bother with single bits. 169 if (N->getOperator()->getName() == "and") 170 AddMatcherNode(new CheckAndImmMatcherNode(II->getValue())); 171 else 172 AddMatcherNode(new CheckOrImmMatcherNode(II->getValue())); 173 174 // Match the LHS of the AND as appropriate. 175 AddMatcherNode(new MoveChildMatcherNode(0)); 176 EmitMatchCode(N->getChild(0), NodeNoTypes->getChild(0)); 177 AddMatcherNode(new MoveParentMatcherNode()); 178 return; 179 } 180 } 181 } 182 183 // Check that the current opcode lines up. 184 AddMatcherNode(new CheckOpcodeMatcherNode(CInfo.getEnumName())); 185 186 // If this node has a chain, then the chain is operand #0 is the SDNode, and 187 // the child numbers of the node are all offset by one. 188 unsigned OpNo = 0; 189 if (N->NodeHasProperty(SDNPHasChain, CGP)) 190 OpNo = 1; 191 192 // If this node is not the root and the subtree underneath it produces a 193 // chain, then the result of matching the node is also produce a chain. 194 // Beyond that, this means that we're also folding (at least) the root node 195 // into the node that produce the chain (for example, matching 196 // "(add reg, (load ptr))" as a add_with_memory on X86). This is problematic, 197 // if the 'reg' node also uses the load (say, its chain). Graphically: 198 // 199 // [LD] 200 // ^ ^ 201 // | \ DAG's like cheese. 202 // / | 203 // / [YY] 204 // | ^ 205 // [XX]--/ 206 // 207 // It would be invalid to fold XX and LD. In this case, folding the two 208 // nodes together would induce a cycle in the DAG, making it a cyclic DAG (!). 209 // To prevent this, we emit a dynamic check for legality before allowing this 210 // to be folded. 211 // 212 const TreePatternNode *Root = Pattern.getSrcPattern(); 213 if (N != Root && // Not the root of the pattern. 214 N->TreeHasProperty(SDNPHasChain, CGP)) { // Has a chain somewhere in tree. 215 216 AddMatcherNode(new CheckProfitableToFoldMatcherNode()); 217 218 // If this non-root node produces a chain, we may need to emit a validity 219 // check. 220 if (OpNo != 0) { 221 // If there is a node between the root and this node, then we definitely 222 // need to emit the check. 223 bool NeedCheck = !Root->hasChild(N); 224 225 // If it *is* an immediate child of the root, we can still need a check if 226 // the root SDNode has multiple inputs. For us, this means that it is an 227 // intrinsic, has multiple operands, or has other inputs like chain or 228 // flag). 229 if (!NeedCheck) { 230 const SDNodeInfo &PInfo = CGP.getSDNodeInfo(Root->getOperator()); 231 NeedCheck = 232 Root->getOperator() == CGP.get_intrinsic_void_sdnode() || 233 Root->getOperator() == CGP.get_intrinsic_w_chain_sdnode() || 234 Root->getOperator() == CGP.get_intrinsic_wo_chain_sdnode() || 235 PInfo.getNumOperands() > 1 || 236 PInfo.hasProperty(SDNPHasChain) || 237 PInfo.hasProperty(SDNPInFlag) || 238 PInfo.hasProperty(SDNPOptInFlag); 239 } 240 241 if (NeedCheck) 242 AddMatcherNode(new CheckLegalToFoldMatcherNode()); 243 } 244 } 245 246 // FIXME: Handle EmittedUseCheck & Flags & .hasOneUse() 247 248 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i, ++OpNo) { 249 // Get the code suitable for matching this child. Move to the child, check 250 // it then move back to the parent. 251 AddMatcherNode(new MoveChildMatcherNode(i)); 252 EmitMatchCode(N->getChild(i), NodeNoTypes->getChild(i)); 253 AddMatcherNode(new MoveParentMatcherNode()); 254 } 255} 256 257 258void MatcherGen::EmitMatchCode(const TreePatternNode *N, 259 TreePatternNode *NodeNoTypes) { 260 // If N and NodeNoTypes don't agree on a type, then this is a case where we 261 // need to do a type check. Emit the check, apply the tyep to NodeNoTypes and 262 // reinfer any correlated types. 263 if (NodeNoTypes->getExtTypes() != N->getExtTypes()) { 264 AddMatcherNode(new CheckTypeMatcherNode(N->getTypeNum(0))); 265 NodeNoTypes->setTypes(N->getExtTypes()); 266 InferPossibleTypes(); 267 } 268 269 270 // If this node has a name associated with it, capture it in VariableMap. If 271 // we already saw this in the pattern, emit code to verify dagness. 272 if (!N->getName().empty()) { 273 unsigned &VarMapEntry = VariableMap[N->getName()]; 274 if (VarMapEntry == 0) { 275 VarMapEntry = ++NextRecordedOperandNo; 276 AddMatcherNode(new RecordMatcherNode()); 277 } else { 278 // If we get here, this is a second reference to a specific name. Since 279 // we already have checked that the first reference is valid, we don't 280 // have to recursively match it, just check that it's the same as the 281 // previously named thing. 282 AddMatcherNode(new CheckSameMatcherNode(VarMapEntry-1)); 283 return; 284 } 285 } 286 287 // If there are node predicates for this node, generate their checks. 288 for (unsigned i = 0, e = N->getPredicateFns().size(); i != e; ++i) 289 AddMatcherNode(new CheckPredicateMatcherNode(N->getPredicateFns()[i])); 290 291 if (N->isLeaf()) 292 EmitLeafMatchCode(N); 293 else 294 EmitOperatorMatchCode(N, NodeNoTypes); 295} 296 297void MatcherGen::EmitMatcherCode() { 298 // If the pattern has a predicate on it (e.g. only enabled when a subtarget 299 // feature is around, do the check). 300 if (!Pattern.getPredicateCheck().empty()) 301 AddMatcherNode(new 302 CheckPatternPredicateMatcherNode(Pattern.getPredicateCheck())); 303 304 // Emit the matcher for the pattern structure and types. 305 EmitMatchCode(Pattern.getSrcPattern(), PatWithNoTypes); 306} 307 308 309MatcherNode *llvm::ConvertPatternToMatcher(const PatternToMatch &Pattern, 310 const CodeGenDAGPatterns &CGP) { 311 MatcherGen Gen(Pattern, CGP); 312 313 // Generate the code for the matcher. 314 Gen.EmitMatcherCode(); 315 316 // If the match succeeds, then we generate Pattern. 317 EmitNodeMatcherNode *Result = new EmitNodeMatcherNode(Pattern); 318 319 // Link it into the pattern. 320 if (MatcherNodeWithChild *Pred = Gen.GetCurPredicate()) { 321 Pred->setChild(Result); 322 return Gen.GetMatcher(); 323 } 324 325 // Unconditional match. 326 return Result; 327} 328 329 330 331