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