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