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