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