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) return nullptr; 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 SwitchOpcodeMatcher::~SwitchOpcodeMatcher() { 88 for (unsigned i = 0, e = Cases.size(); i != e; ++i) 89 delete Cases[i].second; 90 } 91 92 SwitchTypeMatcher::~SwitchTypeMatcher() { 93 for (unsigned i = 0, e = Cases.size(); i != e; ++i) 94 delete Cases[i].second; 95 } 96 97 CheckPredicateMatcher::CheckPredicateMatcher(const TreePredicateFn &pred) 98 : Matcher(CheckPredicate), Pred(pred.getOrigPatFragRecord()) {} 99 100 TreePredicateFn CheckPredicateMatcher::getPredicate() const { 101 return TreePredicateFn(Pred); 102 } 103 104 105 106 // printImpl methods. 107 108 void ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 109 OS.indent(indent) << "Scope\n"; 110 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 111 if (!getChild(i)) 112 OS.indent(indent+1) << "NULL POINTER\n"; 113 else 114 getChild(i)->print(OS, indent+2); 115 } 116 } 117 118 void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 119 OS.indent(indent) << "Record\n"; 120 } 121 122 void RecordChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 123 OS.indent(indent) << "RecordChild: " << ChildNo << '\n'; 124 } 125 126 void RecordMemRefMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 127 OS.indent(indent) << "RecordMemRef\n"; 128 } 129 130 void CaptureGlueInputMatcher::printImpl(raw_ostream &OS, unsigned indent) const{ 131 OS.indent(indent) << "CaptureGlueInput\n"; 132 } 133 134 void MoveChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 135 OS.indent(indent) << "MoveChild " << ChildNo << '\n'; 136 } 137 138 void MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 139 OS.indent(indent) << "MoveParent\n"; 140 } 141 142 void CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 143 OS.indent(indent) << "CheckSame " << MatchNumber << '\n'; 144 } 145 146 void CheckChildSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 147 OS.indent(indent) << "CheckChild" << ChildNo << "Same\n"; 148 } 149 150 void CheckPatternPredicateMatcher:: 151 printImpl(raw_ostream &OS, unsigned indent) const { 152 OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n'; 153 } 154 155 void CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 156 OS.indent(indent) << "CheckPredicate " << getPredicate().getFnName() << '\n'; 157 } 158 159 void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 160 OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n'; 161 } 162 163 void SwitchOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 164 OS.indent(indent) << "SwitchOpcode: {\n"; 165 for (unsigned i = 0, e = Cases.size(); i != e; ++i) { 166 OS.indent(indent) << "case " << Cases[i].first->getEnumName() << ":\n"; 167 Cases[i].second->print(OS, indent+2); 168 } 169 OS.indent(indent) << "}\n"; 170 } 171 172 173 void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 174 OS.indent(indent) << "CheckType " << getEnumName(Type) << ", ResNo=" 175 << ResNo << '\n'; 176 } 177 178 void SwitchTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 179 OS.indent(indent) << "SwitchType: {\n"; 180 for (unsigned i = 0, e = Cases.size(); i != e; ++i) { 181 OS.indent(indent) << "case " << getEnumName(Cases[i].first) << ":\n"; 182 Cases[i].second->print(OS, indent+2); 183 } 184 OS.indent(indent) << "}\n"; 185 } 186 187 void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 188 OS.indent(indent) << "CheckChildType " << ChildNo << " " 189 << getEnumName(Type) << '\n'; 190 } 191 192 193 void CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 194 OS.indent(indent) << "CheckInteger " << Value << '\n'; 195 } 196 197 void CheckChildIntegerMatcher::printImpl(raw_ostream &OS, 198 unsigned indent) const { 199 OS.indent(indent) << "CheckChildInteger " << ChildNo << " " << Value << '\n'; 200 } 201 202 void CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 203 OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n'; 204 } 205 206 void CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 207 OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n'; 208 } 209 210 void CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 211 OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n'; 212 } 213 214 void CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 215 OS.indent(indent) << "CheckAndImm " << Value << '\n'; 216 } 217 218 void CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 219 OS.indent(indent) << "CheckOrImm " << Value << '\n'; 220 } 221 222 void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS, 223 unsigned indent) const { 224 OS.indent(indent) << "CheckFoldableChainNode\n"; 225 } 226 227 void EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 228 OS.indent(indent) << "EmitInteger " << Val << " VT=" << getEnumName(VT) 229 << '\n'; 230 } 231 232 void EmitStringIntegerMatcher:: 233 printImpl(raw_ostream &OS, unsigned indent) const { 234 OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << getEnumName(VT) 235 << '\n'; 236 } 237 238 void EmitRegisterMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 239 OS.indent(indent) << "EmitRegister "; 240 if (Reg) 241 OS << Reg->getName(); 242 else 243 OS << "zero_reg"; 244 OS << " VT=" << getEnumName(VT) << '\n'; 245 } 246 247 void EmitConvertToTargetMatcher:: 248 printImpl(raw_ostream &OS, unsigned indent) const { 249 OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n'; 250 } 251 252 void EmitMergeInputChainsMatcher:: 253 printImpl(raw_ostream &OS, unsigned indent) const { 254 OS.indent(indent) << "EmitMergeInputChains <todo: args>\n"; 255 } 256 257 void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 258 OS.indent(indent) << "EmitCopyToReg <todo: args>\n"; 259 } 260 261 void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 262 OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName() 263 << " Slot=" << Slot << '\n'; 264 } 265 266 267 void EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const { 268 OS.indent(indent); 269 OS << (isa<MorphNodeToMatcher>(this) ? "MorphNodeTo: " : "EmitNode: ") 270 << OpcodeName << ": <todo flags> "; 271 272 for (unsigned i = 0, e = VTs.size(); i != e; ++i) 273 OS << ' ' << getEnumName(VTs[i]); 274 OS << '('; 275 for (unsigned i = 0, e = Operands.size(); i != e; ++i) 276 OS << Operands[i] << ' '; 277 OS << ")\n"; 278 } 279 280 void CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 281 OS.indent(indent) << "CompleteMatch <todo args>\n"; 282 OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n"; 283 OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n"; 284 } 285 286 bool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const { 287 // Note: pointer equality isn't enough here, we have to check the enum names 288 // to ensure that the nodes are for the same opcode. 289 return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() == 290 Opcode.getEnumName(); 291 } 292 293 bool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const { 294 const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m); 295 return M->OpcodeName == OpcodeName && M->VTs == VTs && 296 M->Operands == Operands && M->HasChain == HasChain && 297 M->HasInGlue == HasInGlue && M->HasOutGlue == HasOutGlue && 298 M->HasMemRefs == HasMemRefs && 299 M->NumFixedArityOperands == NumFixedArityOperands; 300 } 301 302 void EmitNodeMatcher::anchor() { } 303 304 void MorphNodeToMatcher::anchor() { } 305 306 // isContradictoryImpl Implementations. 307 308 static bool TypesAreContradictory(MVT::SimpleValueType T1, 309 MVT::SimpleValueType T2) { 310 // If the two types are the same, then they are the same, so they don't 311 // contradict. 312 if (T1 == T2) return false; 313 314 // If either type is about iPtr, then they don't conflict unless the other 315 // one is not a scalar integer type. 316 if (T1 == MVT::iPTR) 317 return !MVT(T2).isInteger() || MVT(T2).isVector(); 318 319 if (T2 == MVT::iPTR) 320 return !MVT(T1).isInteger() || MVT(T1).isVector(); 321 322 // Otherwise, they are two different non-iPTR types, they conflict. 323 return true; 324 } 325 326 bool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const { 327 if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) { 328 // One node can't have two different opcodes! 329 // Note: pointer equality isn't enough here, we have to check the enum names 330 // to ensure that the nodes are for the same opcode. 331 return COM->getOpcode().getEnumName() != getOpcode().getEnumName(); 332 } 333 334 // If the node has a known type, and if the type we're checking for is 335 // different, then we know they contradict. For example, a check for 336 // ISD::STORE will never be true at the same time a check for Type i32 is. 337 if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) { 338 // If checking for a result the opcode doesn't have, it can't match. 339 if (CT->getResNo() >= getOpcode().getNumResults()) 340 return true; 341 342 MVT::SimpleValueType NodeType = getOpcode().getKnownType(CT->getResNo()); 343 if (NodeType != MVT::Other) 344 return TypesAreContradictory(NodeType, CT->getType()); 345 } 346 347 return false; 348 } 349 350 bool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const { 351 if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) 352 return TypesAreContradictory(getType(), CT->getType()); 353 return false; 354 } 355 356 bool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const { 357 if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) { 358 // If the two checks are about different nodes, we don't know if they 359 // conflict! 360 if (CC->getChildNo() != getChildNo()) 361 return false; 362 363 return TypesAreContradictory(getType(), CC->getType()); 364 } 365 return false; 366 } 367 368 bool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const { 369 if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M)) 370 return CIM->getValue() != getValue(); 371 return false; 372 } 373 374 bool CheckChildIntegerMatcher::isContradictoryImpl(const Matcher *M) const { 375 if (const CheckChildIntegerMatcher *CCIM = dyn_cast<CheckChildIntegerMatcher>(M)) { 376 // If the two checks are about different nodes, we don't know if they 377 // conflict! 378 if (CCIM->getChildNo() != getChildNo()) 379 return false; 380 381 return CCIM->getValue() != getValue(); 382 } 383 return false; 384 } 385 386 bool CheckValueTypeMatcher::isContradictoryImpl(const Matcher *M) const { 387 if (const CheckValueTypeMatcher *CVT = dyn_cast<CheckValueTypeMatcher>(M)) 388 return CVT->getTypeName() != getTypeName(); 389 return false; 390 } 391 392
