1 //===- DAGISelMatcherOpt.cpp - Optimize a DAG Matcher ---------------------===// 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 // This file implements the DAG Matcher optimizer. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #include "DAGISelMatcher.h" 15 #include "CodeGenDAGPatterns.h" 16 #include "llvm/ADT/DenseSet.h" 17 #include "llvm/ADT/StringSet.h" 18 #include "llvm/Support/Debug.h" 19 #include "llvm/Support/raw_ostream.h" 20 using namespace llvm; 21 22 #define DEBUG_TYPE "isel-opt" 23 24 /// ContractNodes - Turn multiple matcher node patterns like 'MoveChild+Record' 25 /// into single compound nodes like RecordChild. 26 static void ContractNodes(std::unique_ptr<Matcher> &MatcherPtr, 27 const CodeGenDAGPatterns &CGP) { 28 // If we reached the end of the chain, we're done. 29 Matcher *N = MatcherPtr.get(); 30 if (!N) return; 31 32 // If we have a scope node, walk down all of the children. 33 if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { 34 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 35 std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 36 ContractNodes(Child, CGP); 37 Scope->resetChild(i, Child.release()); 38 } 39 return; 40 } 41 42 // If we found a movechild node with a node that comes in a 'foochild' form, 43 // transform it. 44 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) { 45 Matcher *New = nullptr; 46 if (RecordMatcher *RM = dyn_cast<RecordMatcher>(MC->getNext())) 47 if (MC->getChildNo() < 8) // Only have RecordChild0...7 48 New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor(), 49 RM->getResultNo()); 50 51 if (CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(MC->getNext())) 52 if (MC->getChildNo() < 8 && // Only have CheckChildType0...7 53 CT->getResNo() == 0) // CheckChildType checks res #0 54 New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); 55 56 if (CheckSameMatcher *CS = dyn_cast<CheckSameMatcher>(MC->getNext())) 57 if (MC->getChildNo() < 4) // Only have CheckChildSame0...3 58 New = new CheckChildSameMatcher(MC->getChildNo(), CS->getMatchNumber()); 59 60 if (CheckIntegerMatcher *CS = dyn_cast<CheckIntegerMatcher>(MC->getNext())) 61 if (MC->getChildNo() < 5) // Only have CheckChildInteger0...4 62 New = new CheckChildIntegerMatcher(MC->getChildNo(), CS->getValue()); 63 64 if (New) { 65 // Insert the new node. 66 New->setNext(MatcherPtr.release()); 67 MatcherPtr.reset(New); 68 // Remove the old one. 69 MC->setNext(MC->getNext()->takeNext()); 70 return ContractNodes(MatcherPtr, CGP); 71 } 72 } 73 74 // Zap movechild -> moveparent. 75 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) 76 if (MoveParentMatcher *MP = 77 dyn_cast<MoveParentMatcher>(MC->getNext())) { 78 MatcherPtr.reset(MP->takeNext()); 79 return ContractNodes(MatcherPtr, CGP); 80 } 81 82 // Turn EmitNode->MarkFlagResults->CompleteMatch into 83 // MarkFlagResults->EmitNode->CompleteMatch when we can to encourage 84 // MorphNodeTo formation. This is safe because MarkFlagResults never refers 85 // to the root of the pattern. 86 if (isa<EmitNodeMatcher>(N) && isa<MarkGlueResultsMatcher>(N->getNext()) && 87 isa<CompleteMatchMatcher>(N->getNext()->getNext())) { 88 // Unlink the two nodes from the list. 89 Matcher *EmitNode = MatcherPtr.release(); 90 Matcher *MFR = EmitNode->takeNext(); 91 Matcher *Tail = MFR->takeNext(); 92 93 // Relink them. 94 MatcherPtr.reset(MFR); 95 MFR->setNext(EmitNode); 96 EmitNode->setNext(Tail); 97 return ContractNodes(MatcherPtr, CGP); 98 } 99 100 // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. 101 if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) 102 if (CompleteMatchMatcher *CM = 103 dyn_cast<CompleteMatchMatcher>(EN->getNext())) { 104 // We can only use MorphNodeTo if the result values match up. 105 unsigned RootResultFirst = EN->getFirstResultSlot(); 106 bool ResultsMatch = true; 107 for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) 108 if (CM->getResult(i) != RootResultFirst+i) 109 ResultsMatch = false; 110 111 // If the selected node defines a subset of the glue/chain results, we 112 // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the 113 // matched pattern has a chain but the root node doesn't. 114 const PatternToMatch &Pattern = CM->getPattern(); 115 116 if (!EN->hasChain() && 117 Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) 118 ResultsMatch = false; 119 120 // If the matched node has glue and the output root doesn't, we can't 121 // use MorphNodeTo. 122 // 123 // NOTE: Strictly speaking, we don't have to check for glue here 124 // because the code in the pattern generator doesn't handle it right. We 125 // do it anyway for thoroughness. 126 if (!EN->hasOutFlag() && 127 Pattern.getSrcPattern()->NodeHasProperty(SDNPOutGlue, CGP)) 128 ResultsMatch = false; 129 130 131 // If the root result node defines more results than the source root node 132 // *and* has a chain or glue input, then we can't match it because it 133 // would end up replacing the extra result with the chain/glue. 134 #if 0 135 if ((EN->hasGlue() || EN->hasChain()) && 136 EN->getNumNonChainGlueVTs() > ... need to get no results reliably ...) 137 ResultMatch = false; 138 #endif 139 140 if (ResultsMatch) { 141 const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList(); 142 const SmallVectorImpl<unsigned> &Operands = EN->getOperandList(); 143 MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(), 144 VTs, Operands, 145 EN->hasChain(), EN->hasInFlag(), 146 EN->hasOutFlag(), 147 EN->hasMemRefs(), 148 EN->getNumFixedArityOperands(), 149 Pattern)); 150 return; 151 } 152 153 // FIXME2: Kill off all the SelectionDAG::SelectNodeTo and getMachineNode 154 // variants. 155 } 156 157 ContractNodes(N->getNextPtr(), CGP); 158 159 160 // If we have a CheckType/CheckChildType/Record node followed by a 161 // CheckOpcode, invert the two nodes. We prefer to do structural checks 162 // before type checks, as this opens opportunities for factoring on targets 163 // like X86 where many operations are valid on multiple types. 164 if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || 165 isa<RecordMatcher>(N)) && 166 isa<CheckOpcodeMatcher>(N->getNext())) { 167 // Unlink the two nodes from the list. 168 Matcher *CheckType = MatcherPtr.release(); 169 Matcher *CheckOpcode = CheckType->takeNext(); 170 Matcher *Tail = CheckOpcode->takeNext(); 171 172 // Relink them. 173 MatcherPtr.reset(CheckOpcode); 174 CheckOpcode->setNext(CheckType); 175 CheckType->setNext(Tail); 176 return ContractNodes(MatcherPtr, CGP); 177 } 178 } 179 180 /// SinkPatternPredicates - Pattern predicates can be checked at any level of 181 /// the matching tree. The generator dumps them at the top level of the pattern 182 /// though, which prevents factoring from being able to see past them. This 183 /// optimization sinks them as far down into the pattern as possible. 184 /// 185 /// Conceptually, we'd like to sink these predicates all the way to the last 186 /// matcher predicate in the series. However, it turns out that some 187 /// ComplexPatterns have side effects on the graph, so we really don't want to 188 /// run a the complex pattern if the pattern predicate will fail. For this 189 /// reason, we refuse to sink the pattern predicate past a ComplexPattern. 190 /// 191 static void SinkPatternPredicates(std::unique_ptr<Matcher> &MatcherPtr) { 192 // Recursively scan for a PatternPredicate. 193 // If we reached the end of the chain, we're done. 194 Matcher *N = MatcherPtr.get(); 195 if (!N) return; 196 197 // Walk down all members of a scope node. 198 if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { 199 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 200 std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 201 SinkPatternPredicates(Child); 202 Scope->resetChild(i, Child.release()); 203 } 204 return; 205 } 206 207 // If this node isn't a CheckPatternPredicateMatcher we keep scanning until 208 // we find one. 209 CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N); 210 if (!CPPM) 211 return SinkPatternPredicates(N->getNextPtr()); 212 213 // Ok, we found one, lets try to sink it. Check if we can sink it past the 214 // next node in the chain. If not, we won't be able to change anything and 215 // might as well bail. 216 if (!CPPM->getNext()->isSafeToReorderWithPatternPredicate()) 217 return; 218 219 // Okay, we know we can sink it past at least one node. Unlink it from the 220 // chain and scan for the new insertion point. 221 MatcherPtr.release(); // Don't delete CPPM. 222 MatcherPtr.reset(CPPM->takeNext()); 223 224 N = MatcherPtr.get(); 225 while (N->getNext()->isSafeToReorderWithPatternPredicate()) 226 N = N->getNext(); 227 228 // At this point, we want to insert CPPM after N. 229 CPPM->setNext(N->takeNext()); 230 N->setNext(CPPM); 231 } 232 233 /// FindNodeWithKind - Scan a series of matchers looking for a matcher with a 234 /// specified kind. Return null if we didn't find one otherwise return the 235 /// matcher. 236 static Matcher *FindNodeWithKind(Matcher *M, Matcher::KindTy Kind) { 237 for (; M; M = M->getNext()) 238 if (M->getKind() == Kind) 239 return M; 240 return nullptr; 241 } 242 243 244 /// FactorNodes - Turn matches like this: 245 /// Scope 246 /// OPC_CheckType i32 247 /// ABC 248 /// OPC_CheckType i32 249 /// XYZ 250 /// into: 251 /// OPC_CheckType i32 252 /// Scope 253 /// ABC 254 /// XYZ 255 /// 256 static void FactorNodes(std::unique_ptr<Matcher> &MatcherPtr) { 257 // If we reached the end of the chain, we're done. 258 Matcher *N = MatcherPtr.get(); 259 if (!N) return; 260 261 // If this is not a push node, just scan for one. 262 ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N); 263 if (!Scope) 264 return FactorNodes(N->getNextPtr()); 265 266 // Okay, pull together the children of the scope node into a vector so we can 267 // inspect it more easily. While we're at it, bucket them up by the hash 268 // code of their first predicate. 269 SmallVector<Matcher*, 32> OptionsToMatch; 270 271 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 272 // Factor the subexpression. 273 std::unique_ptr<Matcher> Child(Scope->takeChild(i)); 274 FactorNodes(Child); 275 276 if (Matcher *N = Child.release()) 277 OptionsToMatch.push_back(N); 278 } 279 280 SmallVector<Matcher*, 32> NewOptionsToMatch; 281 282 // Loop over options to match, merging neighboring patterns with identical 283 // starting nodes into a shared matcher. 284 for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { 285 // Find the set of matchers that start with this node. 286 Matcher *Optn = OptionsToMatch[OptionIdx++]; 287 288 if (OptionIdx == e) { 289 NewOptionsToMatch.push_back(Optn); 290 continue; 291 } 292 293 // See if the next option starts with the same matcher. If the two 294 // neighbors *do* start with the same matcher, we can factor the matcher out 295 // of at least these two patterns. See what the maximal set we can merge 296 // together is. 297 SmallVector<Matcher*, 8> EqualMatchers; 298 EqualMatchers.push_back(Optn); 299 300 // Factor all of the known-equal matchers after this one into the same 301 // group. 302 while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn)) 303 EqualMatchers.push_back(OptionsToMatch[OptionIdx++]); 304 305 // If we found a non-equal matcher, see if it is contradictory with the 306 // current node. If so, we know that the ordering relation between the 307 // current sets of nodes and this node don't matter. Look past it to see if 308 // we can merge anything else into this matching group. 309 unsigned Scan = OptionIdx; 310 while (1) { 311 // If we ran out of stuff to scan, we're done. 312 if (Scan == e) break; 313 314 Matcher *ScanMatcher = OptionsToMatch[Scan]; 315 316 // If we found an entry that matches out matcher, merge it into the set to 317 // handle. 318 if (Optn->isEqual(ScanMatcher)) { 319 // If is equal after all, add the option to EqualMatchers and remove it 320 // from OptionsToMatch. 321 EqualMatchers.push_back(ScanMatcher); 322 OptionsToMatch.erase(OptionsToMatch.begin()+Scan); 323 --e; 324 continue; 325 } 326 327 // If the option we're checking for contradicts the start of the list, 328 // skip over it. 329 if (Optn->isContradictory(ScanMatcher)) { 330 ++Scan; 331 continue; 332 } 333 334 // If we're scanning for a simple node, see if it occurs later in the 335 // sequence. If so, and if we can move it up, it might be contradictory 336 // or the same as what we're looking for. If so, reorder it. 337 if (Optn->isSimplePredicateOrRecordNode()) { 338 Matcher *M2 = FindNodeWithKind(ScanMatcher, Optn->getKind()); 339 if (M2 && M2 != ScanMatcher && 340 M2->canMoveBefore(ScanMatcher) && 341 (M2->isEqual(Optn) || M2->isContradictory(Optn))) { 342 Matcher *MatcherWithoutM2 = ScanMatcher->unlinkNode(M2); 343 M2->setNext(MatcherWithoutM2); 344 OptionsToMatch[Scan] = M2; 345 continue; 346 } 347 } 348 349 // Otherwise, we don't know how to handle this entry, we have to bail. 350 break; 351 } 352 353 if (Scan != e && 354 // Don't print it's obvious nothing extra could be merged anyway. 355 Scan+1 != e) { 356 DEBUG(errs() << "Couldn't merge this:\n"; 357 Optn->print(errs(), 4); 358 errs() << "into this:\n"; 359 OptionsToMatch[Scan]->print(errs(), 4); 360 if (Scan+1 != e) 361 OptionsToMatch[Scan+1]->printOne(errs()); 362 if (Scan+2 < e) 363 OptionsToMatch[Scan+2]->printOne(errs()); 364 errs() << "\n"); 365 } 366 367 // If we only found one option starting with this matcher, no factoring is 368 // possible. 369 if (EqualMatchers.size() == 1) { 370 NewOptionsToMatch.push_back(EqualMatchers[0]); 371 continue; 372 } 373 374 // Factor these checks by pulling the first node off each entry and 375 // discarding it. Take the first one off the first entry to reuse. 376 Matcher *Shared = Optn; 377 Optn = Optn->takeNext(); 378 EqualMatchers[0] = Optn; 379 380 // Remove and delete the first node from the other matchers we're factoring. 381 for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { 382 Matcher *Tmp = EqualMatchers[i]->takeNext(); 383 delete EqualMatchers[i]; 384 EqualMatchers[i] = Tmp; 385 } 386 387 Shared->setNext(new ScopeMatcher(EqualMatchers)); 388 389 // Recursively factor the newly created node. 390 FactorNodes(Shared->getNextPtr()); 391 392 NewOptionsToMatch.push_back(Shared); 393 } 394 395 // If we're down to a single pattern to match, then we don't need this scope 396 // anymore. 397 if (NewOptionsToMatch.size() == 1) { 398 MatcherPtr.reset(NewOptionsToMatch[0]); 399 return; 400 } 401 402 if (NewOptionsToMatch.empty()) { 403 MatcherPtr.reset(nullptr); 404 return; 405 } 406 407 // If our factoring failed (didn't achieve anything) see if we can simplify in 408 // other ways. 409 410 // Check to see if all of the leading entries are now opcode checks. If so, 411 // we can convert this Scope to be a OpcodeSwitch instead. 412 bool AllOpcodeChecks = true, AllTypeChecks = true; 413 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 414 // Check to see if this breaks a series of CheckOpcodeMatchers. 415 if (AllOpcodeChecks && 416 !isa<CheckOpcodeMatcher>(NewOptionsToMatch[i])) { 417 #if 0 418 if (i > 3) { 419 errs() << "FAILING OPC #" << i << "\n"; 420 NewOptionsToMatch[i]->dump(); 421 } 422 #endif 423 AllOpcodeChecks = false; 424 } 425 426 // Check to see if this breaks a series of CheckTypeMatcher's. 427 if (AllTypeChecks) { 428 CheckTypeMatcher *CTM = 429 cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], 430 Matcher::CheckType)); 431 if (!CTM || 432 // iPTR checks could alias any other case without us knowing, don't 433 // bother with them. 434 CTM->getType() == MVT::iPTR || 435 // SwitchType only works for result #0. 436 CTM->getResNo() != 0 || 437 // If the CheckType isn't at the start of the list, see if we can move 438 // it there. 439 !CTM->canMoveBefore(NewOptionsToMatch[i])) { 440 #if 0 441 if (i > 3 && AllTypeChecks) { 442 errs() << "FAILING TYPE #" << i << "\n"; 443 NewOptionsToMatch[i]->dump(); 444 } 445 #endif 446 AllTypeChecks = false; 447 } 448 } 449 } 450 451 // If all the options are CheckOpcode's, we can form the SwitchOpcode, woot. 452 if (AllOpcodeChecks) { 453 StringSet<> Opcodes; 454 SmallVector<std::pair<const SDNodeInfo*, Matcher*>, 8> Cases; 455 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 456 CheckOpcodeMatcher *COM = cast<CheckOpcodeMatcher>(NewOptionsToMatch[i]); 457 assert(Opcodes.insert(COM->getOpcode().getEnumName()) && 458 "Duplicate opcodes not factored?"); 459 Cases.push_back(std::make_pair(&COM->getOpcode(), COM->getNext())); 460 } 461 462 MatcherPtr.reset(new SwitchOpcodeMatcher(Cases)); 463 return; 464 } 465 466 // If all the options are CheckType's, we can form the SwitchType, woot. 467 if (AllTypeChecks) { 468 DenseMap<unsigned, unsigned> TypeEntry; 469 SmallVector<std::pair<MVT::SimpleValueType, Matcher*>, 8> Cases; 470 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) { 471 CheckTypeMatcher *CTM = 472 cast_or_null<CheckTypeMatcher>(FindNodeWithKind(NewOptionsToMatch[i], 473 Matcher::CheckType)); 474 Matcher *MatcherWithoutCTM = NewOptionsToMatch[i]->unlinkNode(CTM); 475 MVT::SimpleValueType CTMTy = CTM->getType(); 476 delete CTM; 477 478 unsigned &Entry = TypeEntry[CTMTy]; 479 if (Entry != 0) { 480 // If we have unfactored duplicate types, then we should factor them. 481 Matcher *PrevMatcher = Cases[Entry-1].second; 482 if (ScopeMatcher *SM = dyn_cast<ScopeMatcher>(PrevMatcher)) { 483 SM->setNumChildren(SM->getNumChildren()+1); 484 SM->resetChild(SM->getNumChildren()-1, MatcherWithoutCTM); 485 continue; 486 } 487 488 Matcher *Entries[2] = { PrevMatcher, MatcherWithoutCTM }; 489 Cases[Entry-1].second = new ScopeMatcher(Entries); 490 continue; 491 } 492 493 Entry = Cases.size()+1; 494 Cases.push_back(std::make_pair(CTMTy, MatcherWithoutCTM)); 495 } 496 497 if (Cases.size() != 1) { 498 MatcherPtr.reset(new SwitchTypeMatcher(Cases)); 499 } else { 500 // If we factored and ended up with one case, create it now. 501 MatcherPtr.reset(new CheckTypeMatcher(Cases[0].first, 0)); 502 MatcherPtr->setNext(Cases[0].second); 503 } 504 return; 505 } 506 507 508 // Reassemble the Scope node with the adjusted children. 509 Scope->setNumChildren(NewOptionsToMatch.size()); 510 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) 511 Scope->resetChild(i, NewOptionsToMatch[i]); 512 } 513 514 Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher, 515 const CodeGenDAGPatterns &CGP) { 516 std::unique_ptr<Matcher> MatcherPtr(TheMatcher); 517 ContractNodes(MatcherPtr, CGP); 518 SinkPatternPredicates(MatcherPtr); 519 FactorNodes(MatcherPtr); 520 return MatcherPtr.release(); 521 } 522