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