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" 16using namespace llvm; 17 18void Matcher::anchor() { } 19 20void Matcher::dump() const { 21 print(errs(), 0); 22} 23 24void Matcher::print(raw_ostream &OS, unsigned indent) const { 25 printImpl(OS, indent); 26 if (Next) 27 return Next->print(OS, indent); 28} 29 30void 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. 37Matcher *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. 55bool 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. 68bool 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 82ScopeMatcher::~ScopeMatcher() { 83 for (unsigned i = 0, e = Children.size(); i != e; ++i) 84 delete Children[i]; 85} 86 87 88CheckPredicateMatcher::CheckPredicateMatcher(const TreePredicateFn &pred) 89 : Matcher(CheckPredicate), Pred(pred.getOrigPatFragRecord()) {} 90 91TreePredicateFn CheckPredicateMatcher::getPredicate() const { 92 return TreePredicateFn(Pred); 93} 94 95 96 97// printImpl methods. 98 99void 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 109void RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 110 OS.indent(indent) << "Record\n"; 111} 112 113void RecordChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 114 OS.indent(indent) << "RecordChild: " << ChildNo << '\n'; 115} 116 117void RecordMemRefMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 118 OS.indent(indent) << "RecordMemRef\n"; 119} 120 121void CaptureGlueInputMatcher::printImpl(raw_ostream &OS, unsigned indent) const{ 122 OS.indent(indent) << "CaptureGlueInput\n"; 123} 124 125void MoveChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 126 OS.indent(indent) << "MoveChild " << ChildNo << '\n'; 127} 128 129void MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 130 OS.indent(indent) << "MoveParent\n"; 131} 132 133void CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 134 OS.indent(indent) << "CheckSame " << MatchNumber << '\n'; 135} 136 137void CheckChildSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 138 OS.indent(indent) << "CheckChild" << ChildNo << "Same\n"; 139} 140 141void CheckPatternPredicateMatcher:: 142printImpl(raw_ostream &OS, unsigned indent) const { 143 OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n'; 144} 145 146void CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 147 OS.indent(indent) << "CheckPredicate " << getPredicate().getFnName() << '\n'; 148} 149 150void CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 151 OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n'; 152} 153 154void 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 164void CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 165 OS.indent(indent) << "CheckType " << getEnumName(Type) << ", ResNo=" 166 << ResNo << '\n'; 167} 168 169void 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 178void CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 179 OS.indent(indent) << "CheckChildType " << ChildNo << " " 180 << getEnumName(Type) << '\n'; 181} 182 183 184void CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 185 OS.indent(indent) << "CheckInteger " << Value << '\n'; 186} 187 188void CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 189 OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n'; 190} 191 192void CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 193 OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n'; 194} 195 196void CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 197 OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n'; 198} 199 200void CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 201 OS.indent(indent) << "CheckAndImm " << Value << '\n'; 202} 203 204void CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 205 OS.indent(indent) << "CheckOrImm " << Value << '\n'; 206} 207 208void CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS, 209 unsigned indent) const { 210 OS.indent(indent) << "CheckFoldableChainNode\n"; 211} 212 213void EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 214 OS.indent(indent) << "EmitInteger " << Val << " VT=" << VT << '\n'; 215} 216 217void EmitStringIntegerMatcher:: 218printImpl(raw_ostream &OS, unsigned indent) const { 219 OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << VT << '\n'; 220} 221 222void 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 231void EmitConvertToTargetMatcher:: 232printImpl(raw_ostream &OS, unsigned indent) const { 233 OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n'; 234} 235 236void EmitMergeInputChainsMatcher:: 237printImpl(raw_ostream &OS, unsigned indent) const { 238 OS.indent(indent) << "EmitMergeInputChains <todo: args>\n"; 239} 240 241void EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 242 OS.indent(indent) << "EmitCopyToReg <todo: args>\n"; 243} 244 245void EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 246 OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName() 247 << " Slot=" << Slot << '\n'; 248} 249 250 251void 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 264void MarkGlueResultsMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 265 OS.indent(indent) << "MarkGlueResults <todo: args>\n"; 266} 267 268void 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 276unsigned CheckPatternPredicateMatcher::getHashImpl() const { 277 return HashString(Predicate); 278} 279 280unsigned CheckPredicateMatcher::getHashImpl() const { 281 return HashString(getPredicate().getFnName()); 282} 283 284unsigned CheckOpcodeMatcher::getHashImpl() const { 285 return HashString(Opcode.getEnumName()); 286} 287 288unsigned CheckCondCodeMatcher::getHashImpl() const { 289 return HashString(CondCodeName); 290} 291 292unsigned CheckValueTypeMatcher::getHashImpl() const { 293 return HashString(TypeName); 294} 295 296unsigned EmitStringIntegerMatcher::getHashImpl() const { 297 return HashString(Val) ^ VT; 298} 299 300template<typename It> 301static 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 308unsigned EmitMergeInputChainsMatcher::getHashImpl() const { 309 return HashUnsigneds(ChainNodes.begin(), ChainNodes.end()); 310} 311 312bool 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 319bool 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 328unsigned EmitNodeMatcherCommon::getHashImpl() const { 329 return (HashString(OpcodeName) << 4) | Operands.size(); 330} 331 332 333void EmitNodeMatcher::anchor() { } 334 335void MorphNodeToMatcher::anchor() { } 336 337unsigned MarkGlueResultsMatcher::getHashImpl() const { 338 return HashUnsigneds(GlueResultNodes.begin(), GlueResultNodes.end()); 339} 340 341unsigned CompleteMatchMatcher::getHashImpl() const { 342 return HashUnsigneds(Results.begin(), Results.end()) ^ 343 ((unsigned)(intptr_t)&Pattern << 8); 344} 345 346// isContradictoryImpl Implementations. 347 348static 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 366bool 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 390bool 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 396bool 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 408bool 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 414bool 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