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