DAGISelMatcher.cpp revision fbadcd0826c2e69ed21c2d535310ba958acb4359
1//===- DAGISelMatcher.cpp - Representation of DAG pattern 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#include "DAGISelMatcher.h" 11#include "CodeGenDAGPatterns.h" 12#include "CodeGenTarget.h" 13#include "Record.h" 14#include "llvm/Support/raw_ostream.h" 15#include "llvm/ADT/StringExtras.h" 16using namespace llvm; 17 18void Matcher::dump() const { 19 print(errs(), 0); 20} 21 22void Matcher::print(raw_ostream &OS, unsigned indent) const { 23 printImpl(OS, indent); 24 if (Next) 25 return Next->print(OS, indent); 26} 27 28void Matcher::printOne(raw_ostream &OS) const { 29 printImpl(OS, 0); 30} 31 32/// unlinkNode - Unlink the specified node from this chain. If Other == this, 33/// we unlink the next pointer and return it. Otherwise we unlink Other from 34/// the list and return this. 35Matcher *Matcher::unlinkNode(Matcher *Other) { 36 if (this == Other) 37 return takeNext(); 38 39 // Scan until we find the predecessor of Other. 40 Matcher *Cur = this; 41 for (; Cur && Cur->getNext() != Other; Cur = Cur->getNext()) 42 /*empty*/; 43 44 if (Cur == 0) return 0; 45 Cur->takeNext(); 46 Cur->setNext(Other->takeNext()); 47 return this; 48} 49 50/// canMoveBefore - Return true if this matcher is the same as Other, or if 51/// we can move this matcher past all of the nodes in-between Other and this 52/// node. Other must be equal to or before this. 53bool Matcher::canMoveBefore(const Matcher *Other) const { 54 for (;; Other = Other->getNext()) { 55 assert(Other && "Other didn't come before 'this'?"); 56 if (this == Other) return true; 57 58 // We have to be able to move this node across the Other node. 59 if (!canMoveBeforeNode(Other)) 60 return false; 61 } 62} 63 64/// canMoveBefore - Return true if it is safe to move the current matcher 65/// across the specified one. 66bool Matcher::canMoveBeforeNode(const Matcher *Other) const { 67 // We can move simple predicates before record nodes. 68 if (isSimplePredicateNode()) 69 return Other->isSimplePredicateOrRecordNode(); 70 71 // We can move record nodes across simple predicates. 72 if (isSimplePredicateOrRecordNode()) 73 return isSimplePredicateNode(); 74 75 // We can't move record nodes across each other etc. 76 return false; 77} 78 79 80ScopeMatcher::~ScopeMatcher() { 81 for (unsigned i = 0, e = Children.size(); i != e; ++i) 82 delete Children[i]; 83} 84 85 86// printImpl methods. 87 88void ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 89 OS.indent(indent) << "Scope\n"; 90 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 91 if (getChild(i) == 0) 92 OS.indent(indent+1) << "NULL POINTER\n"; 93 else 94 getChild(i)->print(OS, indent+2); 95 } 96} 97 98void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 99 OS.indent(indent) << "Record\n"; 100} 101 102void RecordChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 103 OS.indent(indent) << "RecordChild: " << ChildNo << '\n'; 104} 105 106void RecordMemRefMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 107 OS.indent(indent) << "RecordMemRef\n"; 108} 109 110void CaptureFlagInputMatcher::printImpl(raw_ostream &OS, unsigned indent) const{ 111 OS.indent(indent) << "CaptureFlagInput\n"; 112} 113 114void MoveChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 115 OS.indent(indent) << "MoveChild " << ChildNo << '\n'; 116} 117 118void MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 119 OS.indent(indent) << "MoveParent\n"; 120} 121 122void CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 123 OS.indent(indent) << "CheckSame " << MatchNumber << '\n'; 124} 125 126void CheckPatternPredicateMatcher:: 127printImpl(raw_ostream &OS, unsigned indent) const { 128 OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n'; 129} 130 131void CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 132 OS.indent(indent) << "CheckPredicate " << PredName << '\n'; 133} 134 135void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 136 OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n'; 137} 138 139void SwitchOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 140 OS.indent(indent) << "SwitchOpcode: {\n"; 141 for (unsigned i = 0, e = Cases.size(); i != e; ++i) { 142 OS.indent(indent) << "case " << Cases[i].first->getEnumName() << ":\n"; 143 Cases[i].second->print(OS, indent+2); 144 } 145 OS.indent(indent) << "}\n"; 146} 147 148 149void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 150 OS.indent(indent) << "CheckType " << getEnumName(Type) << ", ResNo=" 151 << ResNo << '\n'; 152} 153 154void SwitchTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 155 OS.indent(indent) << "SwitchType: {\n"; 156 for (unsigned i = 0, e = Cases.size(); i != e; ++i) { 157 OS.indent(indent) << "case " << getEnumName(Cases[i].first) << ":\n"; 158 Cases[i].second->print(OS, indent+2); 159 } 160 OS.indent(indent) << "}\n"; 161} 162 163void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 164 OS.indent(indent) << "CheckChildType " << ChildNo << " " 165 << getEnumName(Type) << '\n'; 166} 167 168 169void CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 170 OS.indent(indent) << "CheckInteger " << Value << '\n'; 171} 172 173void CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 174 OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n'; 175} 176 177void CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 178 OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n'; 179} 180 181void CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 182 OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n'; 183} 184 185void CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 186 OS.indent(indent) << "CheckAndImm " << Value << '\n'; 187} 188 189void CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 190 OS.indent(indent) << "CheckOrImm " << Value << '\n'; 191} 192 193void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS, 194 unsigned indent) const { 195 OS.indent(indent) << "CheckFoldableChainNode\n"; 196} 197 198void EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 199 OS.indent(indent) << "EmitInteger " << Val << " VT=" << VT << '\n'; 200} 201 202void EmitStringIntegerMatcher:: 203printImpl(raw_ostream &OS, unsigned indent) const { 204 OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << VT << '\n'; 205} 206 207void EmitRegisterMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 208 OS.indent(indent) << "EmitRegister "; 209 if (Reg) 210 OS << Reg->getName(); 211 else 212 OS << "zero_reg"; 213 OS << " VT=" << VT << '\n'; 214} 215 216void EmitConvertToTargetMatcher:: 217printImpl(raw_ostream &OS, unsigned indent) const { 218 OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n'; 219} 220 221void EmitMergeInputChainsMatcher:: 222printImpl(raw_ostream &OS, unsigned indent) const { 223 OS.indent(indent) << "EmitMergeInputChains <todo: args>\n"; 224} 225 226void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 227 OS.indent(indent) << "EmitCopyToReg <todo: args>\n"; 228} 229 230void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 231 OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName() 232 << " Slot=" << Slot << '\n'; 233} 234 235 236void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const { 237 OS.indent(indent); 238 OS << (isa<MorphNodeToMatcher>(this) ? "MorphNodeTo: " : "EmitNode: ") 239 << OpcodeName << ": <todo flags> "; 240 241 for (unsigned i = 0, e = VTs.size(); i != e; ++i) 242 OS << ' ' << getEnumName(VTs[i]); 243 OS << '('; 244 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 245 OS << Operands[i] << ' '; 246 OS << ")\n"; 247} 248 249void MarkFlagResultsMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 250 OS.indent(indent) << "MarkFlagResults <todo: args>\n"; 251} 252 253void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 254 OS.indent(indent) << "CompleteMatch <todo args>\n"; 255 OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n"; 256 OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n"; 257} 258 259// getHashImpl Implementation. 260 261unsigned CheckPatternPredicateMatcher::getHashImpl() const { 262 return HashString(Predicate); 263} 264 265unsigned CheckPredicateMatcher::getHashImpl() const { 266 return HashString(PredName); 267} 268 269unsigned CheckOpcodeMatcher::getHashImpl() const { 270 return HashString(Opcode.getEnumName()); 271} 272 273unsigned CheckCondCodeMatcher::getHashImpl() const { 274 return HashString(CondCodeName); 275} 276 277unsigned CheckValueTypeMatcher::getHashImpl() const { 278 return HashString(TypeName); 279} 280 281unsigned EmitStringIntegerMatcher::getHashImpl() const { 282 return HashString(Val) ^ VT; 283} 284 285template<typename It> 286static unsigned HashUnsigneds(It I, It E) { 287 unsigned Result = 0; 288 for (; I != E; ++I) 289 Result = (Result<<3) ^ *I; 290 return Result; 291} 292 293unsigned EmitMergeInputChainsMatcher::getHashImpl() const { 294 return HashUnsigneds(ChainNodes.begin(), ChainNodes.end()); 295} 296 297bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const { 298 // Note: pointer equality isn't enough here, we have to check the enum names 299 // to ensure that the nodes are for the same opcode. 300 return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() == 301 Opcode.getEnumName(); 302} 303 304 305bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const { 306 const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m); 307 return M->OpcodeName == OpcodeName && M->VTs == VTs && 308 M->Operands == Operands && M->HasChain == HasChain && 309 M->HasInFlag == HasInFlag && M->HasOutFlag == HasOutFlag && 310 M->HasMemRefs == HasMemRefs && 311 M->NumFixedArityOperands == NumFixedArityOperands; 312} 313 314unsigned EmitNodeMatcherCommon::getHashImpl() const { 315 return (HashString(OpcodeName) << 4) | Operands.size(); 316} 317 318 319unsigned MarkFlagResultsMatcher::getHashImpl() const { 320 return HashUnsigneds(FlagResultNodes.begin(), FlagResultNodes.end()); 321} 322 323unsigned CompleteMatchMatcher::getHashImpl() const { 324 return HashUnsigneds(Results.begin(), Results.end()) ^ 325 ((unsigned)(intptr_t)&Pattern << 8); 326} 327 328// isContradictoryImpl Implementations. 329 330static bool TypesAreContradictory(MVT::SimpleValueType T1, 331 MVT::SimpleValueType T2) { 332 // If the two types are the same, then they are the same, so they don't 333 // contradict. 334 if (T1 == T2) return false; 335 336 // If either type is about iPtr, then they don't conflict unless the other 337 // one is not a scalar integer type. 338 if (T1 == MVT::iPTR) 339 return !MVT(T2).isInteger() || MVT(T2).isVector(); 340 341 if (T2 == MVT::iPTR) 342 return !MVT(T1).isInteger() || MVT(T1).isVector(); 343 344 // Otherwise, they are two different non-iPTR types, they conflict. 345 return true; 346} 347 348bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const { 349 if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) { 350 // One node can't have two different opcodes! 351 // Note: pointer equality isn't enough here, we have to check the enum names 352 // to ensure that the nodes are for the same opcode. 353 return COM->getOpcode().getEnumName() != getOpcode().getEnumName(); 354 } 355 356 // If the node has a known type, and if the type we're checking for is 357 // different, then we know they contradict. For example, a check for 358 // ISD::STORE will never be true at the same time a check for Type i32 is. 359 if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) { 360 // If checking for a result the opcode doesn't have, it can't match. 361 if (CT->getResNo() >= getOpcode().getNumResults()) 362 return true; 363 364 MVT::SimpleValueType NodeType = getOpcode().getKnownType(CT->getResNo()); 365 if (NodeType != MVT::Other) 366 return TypesAreContradictory(NodeType, CT->getType()); 367 } 368 369 return false; 370} 371 372bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const { 373 if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) 374 return TypesAreContradictory(getType(), CT->getType()); 375 return false; 376} 377 378bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const { 379 if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) { 380 // If the two checks are about different nodes, we don't know if they 381 // conflict! 382 if (CC->getChildNo() != getChildNo()) 383 return false; 384 385 return TypesAreContradictory(getType(), CC->getType()); 386 } 387 return false; 388} 389 390bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const { 391 if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M)) 392 return CIM->getValue() != getValue(); 393 return false; 394} 395 396bool CheckValueTypeMatcher::isContradictoryImpl(const Matcher *M) const { 397 if (const CheckValueTypeMatcher *CVT = dyn_cast<CheckValueTypeMatcher>(M)) 398 return CVT->getTypeName() != getTypeName(); 399 return false; 400} 401 402