DAGISelMatcherOpt.cpp revision e9eeda878beb8d36507a69a2be2fe08fcc968fef
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/DenseMap.h" 18#include "llvm/Support/Debug.h" 19#include "llvm/Support/raw_ostream.h" 20#include <vector> 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 New = new RecordChildMatcher(MC->getChildNo(), RM->getWhatFor()); 47 48 if (CheckTypeMatcher *CT= dyn_cast<CheckTypeMatcher>(MC->getNext())) 49 New = new CheckChildTypeMatcher(MC->getChildNo(), CT->getType()); 50 51 if (New) { 52 // Insert the new node. 53 New->setNext(MatcherPtr.take()); 54 MatcherPtr.reset(New); 55 // Remove the old one. 56 MC->setNext(MC->getNext()->takeNext()); 57 return ContractNodes(MatcherPtr, CGP); 58 } 59 } 60 61 // Zap movechild -> moveparent. 62 if (MoveChildMatcher *MC = dyn_cast<MoveChildMatcher>(N)) 63 if (MoveParentMatcher *MP = 64 dyn_cast<MoveParentMatcher>(MC->getNext())) { 65 MatcherPtr.reset(MP->takeNext()); 66 return ContractNodes(MatcherPtr, CGP); 67 } 68 69 // FIXME: Handle OPC_MarkFlagResults. 70 71 // Turn EmitNode->CompleteMatch into MorphNodeTo if we can. 72 if (EmitNodeMatcher *EN = dyn_cast<EmitNodeMatcher>(N)) 73 if (CompleteMatchMatcher *CM = 74 dyn_cast<CompleteMatchMatcher>(EN->getNext())) { 75 // We can only use MorphNodeTo if the result values match up. 76 unsigned RootResultFirst = EN->getFirstResultSlot(); 77 bool ResultsMatch = true; 78 for (unsigned i = 0, e = CM->getNumResults(); i != e; ++i) 79 if (CM->getResult(i) != RootResultFirst+i) 80 ResultsMatch = false; 81 82 // If the selected node defines a subset of the flag/chain results, we 83 // can't use MorphNodeTo. For example, we can't use MorphNodeTo if the 84 // matched pattern has a chain but the root node doesn't. 85 const PatternToMatch &Pattern = CM->getPattern(); 86 87 if (!EN->hasChain() && 88 Pattern.getSrcPattern()->NodeHasProperty(SDNPHasChain, CGP)) 89 ResultsMatch = false; 90 91 // If the matched node has a flag and the output root doesn't, we can't 92 // use MorphNodeTo. 93 // 94 // NOTE: Strictly speaking, we don't have to check for the flag here 95 // because the code in the pattern generator doesn't handle it right. We 96 // do it anyway for thoroughness. 97 if (!EN->hasOutFlag() && 98 Pattern.getSrcPattern()->NodeHasProperty(SDNPOutFlag, CGP)) 99 ResultsMatch = false; 100 101 102 // If the root result node defines more results than the source root node 103 // *and* has a chain or flag input, then we can't match it because it 104 // would end up replacing the extra result with the chain/flag. 105#if 0 106 if ((EN->hasFlag() || EN->hasChain()) && 107 EN->getNumNonChainFlagVTs() > ... need to get no results reliably ...) 108 ResultMatch = false; 109#endif 110 111 if (ResultsMatch) { 112 const SmallVectorImpl<MVT::SimpleValueType> &VTs = EN->getVTList(); 113 const SmallVectorImpl<unsigned> &Operands = EN->getOperandList(); 114 MatcherPtr.reset(new MorphNodeToMatcher(EN->getOpcodeName(), 115 VTs.data(), VTs.size(), 116 Operands.data(),Operands.size(), 117 EN->hasChain(), EN->hasInFlag(), 118 EN->hasOutFlag(), 119 EN->hasMemRefs(), 120 EN->getNumFixedArityOperands(), 121 Pattern)); 122 return; 123 } 124 125 // FIXME2: Kill off all the SelectionDAG::MorphNodeTo and getMachineNode 126 // variants. 127 } 128 129 ContractNodes(N->getNextPtr(), CGP); 130 131 132 // If we have a CheckType/CheckChildType/Record node followed by a 133 // CheckOpcode, invert the two nodes. We prefer to do structural checks 134 // before type checks, as this opens opportunities for factoring on targets 135 // like X86 where many operations are valid on multiple types. 136 if ((isa<CheckTypeMatcher>(N) || isa<CheckChildTypeMatcher>(N) || 137 isa<RecordMatcher>(N)) && 138 isa<CheckOpcodeMatcher>(N->getNext())) { 139 // Unlink the two nodes from the list. 140 Matcher *CheckType = MatcherPtr.take(); 141 Matcher *CheckOpcode = CheckType->takeNext(); 142 Matcher *Tail = CheckOpcode->takeNext(); 143 144 // Relink them. 145 MatcherPtr.reset(CheckOpcode); 146 CheckOpcode->setNext(CheckType); 147 CheckType->setNext(Tail); 148 return ContractNodes(MatcherPtr, CGP); 149 } 150} 151 152/// SinkPatternPredicates - Pattern predicates can be checked at any level of 153/// the matching tree. The generator dumps them at the top level of the pattern 154/// though, which prevents factoring from being able to see past them. This 155/// optimization sinks them as far down into the pattern as possible. 156/// 157/// Conceptually, we'd like to sink these predicates all the way to the last 158/// matcher predicate in the series. However, it turns out that some 159/// ComplexPatterns have side effects on the graph, so we really don't want to 160/// run a the complex pattern if the pattern predicate will fail. For this 161/// reason, we refuse to sink the pattern predicate past a ComplexPattern. 162/// 163static void SinkPatternPredicates(OwningPtr<Matcher> &MatcherPtr) { 164 // Recursively scan for a PatternPredicate. 165 // If we reached the end of the chain, we're done. 166 Matcher *N = MatcherPtr.get(); 167 if (N == 0) return; 168 169 // Walk down all members of a scope node. 170 if (ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N)) { 171 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 172 OwningPtr<Matcher> Child(Scope->takeChild(i)); 173 SinkPatternPredicates(Child); 174 Scope->resetChild(i, Child.take()); 175 } 176 return; 177 } 178 179 // If this node isn't a CheckPatternPredicateMatcher we keep scanning until 180 // we find one. 181 CheckPatternPredicateMatcher *CPPM =dyn_cast<CheckPatternPredicateMatcher>(N); 182 if (CPPM == 0) 183 return SinkPatternPredicates(N->getNextPtr()); 184 185 // Ok, we found one, lets try to sink it. Check if we can sink it past the 186 // next node in the chain. If not, we won't be able to change anything and 187 // might as well bail. 188 if (!CPPM->getNext()->isSafeToReorderWithPatternPredicate()) 189 return; 190 191 // Okay, we know we can sink it past at least one node. Unlink it from the 192 // chain and scan for the new insertion point. 193 MatcherPtr.take(); // Don't delete CPPM. 194 MatcherPtr.reset(CPPM->takeNext()); 195 196 N = MatcherPtr.get(); 197 while (N->getNext()->isSafeToReorderWithPatternPredicate()) 198 N = N->getNext(); 199 200 // At this point, we want to insert CPPM after N. 201 CPPM->setNext(N->takeNext()); 202 N->setNext(CPPM); 203} 204 205/// FactorNodes - Turn matches like this: 206/// Scope 207/// OPC_CheckType i32 208/// ABC 209/// OPC_CheckType i32 210/// XYZ 211/// into: 212/// OPC_CheckType i32 213/// Scope 214/// ABC 215/// XYZ 216/// 217static void FactorNodes(OwningPtr<Matcher> &MatcherPtr) { 218 // If we reached the end of the chain, we're done. 219 Matcher *N = MatcherPtr.get(); 220 if (N == 0) return; 221 222 // If this is not a push node, just scan for one. 223 ScopeMatcher *Scope = dyn_cast<ScopeMatcher>(N); 224 if (Scope == 0) 225 return FactorNodes(N->getNextPtr()); 226 227 // Okay, pull together the children of the scope node into a vector so we can 228 // inspect it more easily. While we're at it, bucket them up by the hash 229 // code of their first predicate. 230 SmallVector<Matcher*, 32> OptionsToMatch; 231 232 for (unsigned i = 0, e = Scope->getNumChildren(); i != e; ++i) { 233 // Factor the subexpression. 234 OwningPtr<Matcher> Child(Scope->takeChild(i)); 235 FactorNodes(Child); 236 237 if (Matcher *N = Child.take()) 238 OptionsToMatch.push_back(N); 239 } 240 241 SmallVector<Matcher*, 32> NewOptionsToMatch; 242 243 // Loop over options to match, merging neighboring patterns with identical 244 // starting nodes into a shared matcher. 245 for (unsigned OptionIdx = 0, e = OptionsToMatch.size(); OptionIdx != e;) { 246 // Find the set of matchers that start with this node. 247 Matcher *Optn = OptionsToMatch[OptionIdx++]; 248 249 if (OptionIdx == e) { 250 NewOptionsToMatch.push_back(Optn); 251 continue; 252 } 253 254 // See if the next option starts with the same matcher. If the two 255 // neighbors *do* start with the same matcher, we can factor the matcher out 256 // of at least these two patterns. See what the maximal set we can merge 257 // together is. 258 SmallVector<Matcher*, 8> EqualMatchers; 259 EqualMatchers.push_back(Optn); 260 261 // Factor all of the known-equal matchers after this one into the same 262 // group. 263 while (OptionIdx != e && OptionsToMatch[OptionIdx]->isEqual(Optn)) 264 EqualMatchers.push_back(OptionsToMatch[OptionIdx++]); 265 266 // If we found a non-equal matcher, see if it is contradictory with the 267 // current node. If so, we know that the ordering relation between the 268 // current sets of nodes and this node don't matter. Look past it to see if 269 // we can merge anything else into this matching group. 270 unsigned Scan = OptionIdx; 271 while (1) { 272 while (Scan != e && Optn->isContradictory(OptionsToMatch[Scan])) 273 ++Scan; 274 275 // Ok, we found something that isn't known to be contradictory. If it is 276 // equal, we can merge it into the set of nodes to factor, if not, we have 277 // to cease factoring. 278 if (Scan == e || !Optn->isEqual(OptionsToMatch[Scan])) break; 279 280 // If is equal after all, add the option to EqualMatchers and remove it 281 // from OptionsToMatch. 282 EqualMatchers.push_back(OptionsToMatch[Scan]); 283 OptionsToMatch.erase(OptionsToMatch.begin()+Scan); 284 --e; 285 } 286 287 if (Scan != e && 288 // Don't print it's obvious nothing extra could be merged anyway. 289 Scan+1 != e) { 290 DEBUG(errs() << "Couldn't merge this:\n"; 291 Optn->print(errs(), 4); 292 errs() << "into this:\n"; 293 OptionsToMatch[Scan]->print(errs(), 4); 294 if (Scan+1 != e) 295 OptionsToMatch[Scan+1]->printOne(errs()); 296 if (Scan+2 < e) 297 OptionsToMatch[Scan+2]->printOne(errs()); 298 errs() << "\n"); 299 } 300 301 // If we only found one option starting with this matcher, no factoring is 302 // possible. 303 if (EqualMatchers.size() == 1) { 304 NewOptionsToMatch.push_back(EqualMatchers[0]); 305 continue; 306 } 307 308 // Factor these checks by pulling the first node off each entry and 309 // discarding it. Take the first one off the first entry to reuse. 310 Matcher *Shared = Optn; 311 Optn = Optn->takeNext(); 312 EqualMatchers[0] = Optn; 313 314 // Remove and delete the first node from the other matchers we're factoring. 315 for (unsigned i = 1, e = EqualMatchers.size(); i != e; ++i) { 316 Matcher *Tmp = EqualMatchers[i]->takeNext(); 317 delete EqualMatchers[i]; 318 EqualMatchers[i] = Tmp; 319 } 320 321 Shared->setNext(new ScopeMatcher(&EqualMatchers[0], EqualMatchers.size())); 322 323 // Recursively factor the newly created node. 324 FactorNodes(Shared->getNextPtr()); 325 326 NewOptionsToMatch.push_back(Shared); 327 } 328 329 // Reassemble a new Scope node. 330 assert(!NewOptionsToMatch.empty() && "where'd all our children go?"); 331 if (NewOptionsToMatch.empty()) 332 MatcherPtr.reset(0); 333 if (NewOptionsToMatch.size() == 1) 334 MatcherPtr.reset(NewOptionsToMatch[0]); 335 else { 336 Scope->setNumChildren(NewOptionsToMatch.size()); 337 for (unsigned i = 0, e = NewOptionsToMatch.size(); i != e; ++i) 338 Scope->resetChild(i, NewOptionsToMatch[i]); 339 } 340} 341 342Matcher *llvm::OptimizeMatcher(Matcher *TheMatcher, 343 const CodeGenDAGPatterns &CGP) { 344 OwningPtr<Matcher> MatcherPtr(TheMatcher); 345 ContractNodes(MatcherPtr, CGP); 346 SinkPatternPredicates(MatcherPtr); 347 FactorNodes(MatcherPtr); 348 return MatcherPtr.take(); 349} 350