DAGISelMatcher.cpp revision 218893
1187063Srwatson//===- DAGISelMatcher.cpp - Representation of DAG pattern matcher ---------===// 2187063Srwatson// 3187063Srwatson// The LLVM Compiler Infrastructure 4187063Srwatson// 5187063Srwatson// This file is distributed under the University of Illinois Open Source 6187063Srwatson// License. See LICENSE.TXT for details. 7187063Srwatson// 8187063Srwatson//===----------------------------------------------------------------------===// 9187063Srwatson 10187063Srwatson#include "DAGISelMatcher.h" 11187063Srwatson#include "CodeGenDAGPatterns.h" 12187063Srwatson#include "CodeGenTarget.h" 13187063Srwatson#include "Record.h" 14187063Srwatson#include "llvm/Support/raw_ostream.h" 15187063Srwatson#include "llvm/ADT/StringExtras.h" 16187063Srwatsonusing namespace llvm; 17187063Srwatson 18187063Srwatsonvoid Matcher::dump() const { 19187063Srwatson print(errs(), 0); 20187063Srwatson} 21187063Srwatson 22187063Srwatsonvoid Matcher::print(raw_ostream &OS, unsigned indent) const { 23187063Srwatson printImpl(OS, indent); 24187063Srwatson if (Next) 25187063Srwatson return Next->print(OS, indent); 26187063Srwatson} 27187063Srwatson 28187063Srwatsonvoid Matcher::printOne(raw_ostream &OS) const { 29187063Srwatson printImpl(OS, 0); 30187063Srwatson} 31187063Srwatson 32187063Srwatson/// unlinkNode - Unlink the specified node from this chain. If Other == this, 33187063Srwatson/// we unlink the next pointer and return it. Otherwise we unlink Other from 34187063Srwatson/// the list and return this. 35187063SrwatsonMatcher *Matcher::unlinkNode(Matcher *Other) { 36187063Srwatson if (this == Other) 37187063Srwatson return takeNext(); 38187063Srwatson 39187063Srwatson // Scan until we find the predecessor of Other. 40187063Srwatson Matcher *Cur = this; 41187063Srwatson for (; Cur && Cur->getNext() != Other; Cur = Cur->getNext()) 42187063Srwatson /*empty*/; 43187063Srwatson 44187063Srwatson if (Cur == 0) return 0; 45187063Srwatson Cur->takeNext(); 46187063Srwatson Cur->setNext(Other->takeNext()); 47187063Srwatson return this; 48187063Srwatson} 49187063Srwatson 50187063Srwatson/// canMoveBefore - Return true if this matcher is the same as Other, or if 51187063Srwatson/// we can move this matcher past all of the nodes in-between Other and this 52187063Srwatson/// node. Other must be equal to or before this. 53187063Srwatsonbool Matcher::canMoveBefore(const Matcher *Other) const { 54187063Srwatson for (;; Other = Other->getNext()) { 55187063Srwatson assert(Other && "Other didn't come before 'this'?"); 56187063Srwatson if (this == Other) return true; 57187063Srwatson 58187063Srwatson // We have to be able to move this node across the Other node. 59187063Srwatson if (!canMoveBeforeNode(Other)) 60187063Srwatson return false; 61187063Srwatson } 62187063Srwatson} 63187063Srwatson 64187063Srwatson/// canMoveBefore - Return true if it is safe to move the current matcher 65187063Srwatson/// across the specified one. 66187063Srwatsonbool Matcher::canMoveBeforeNode(const Matcher *Other) const { 67187063Srwatson // We can move simple predicates before record nodes. 68187063Srwatson if (isSimplePredicateNode()) 69187063Srwatson return Other->isSimplePredicateOrRecordNode(); 70187063Srwatson 71187063Srwatson // We can move record nodes across simple predicates. 72187063Srwatson if (isSimplePredicateOrRecordNode()) 73187063Srwatson return isSimplePredicateNode(); 74187063Srwatson 75187063Srwatson // We can't move record nodes across each other etc. 76187063Srwatson return false; 77187063Srwatson} 78187063Srwatson 79187063Srwatson 80187063SrwatsonScopeMatcher::~ScopeMatcher() { 81187063Srwatson for (unsigned i = 0, e = Children.size(); i != e; ++i) 82187063Srwatson delete Children[i]; 83187063Srwatson} 84187063Srwatson 85187063Srwatson 86187063Srwatson// printImpl methods. 87187063Srwatson 88187063Srwatsonvoid ScopeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 89187063Srwatson OS.indent(indent) << "Scope\n"; 90187063Srwatson for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 91187063Srwatson if (getChild(i) == 0) 92187063Srwatson OS.indent(indent+1) << "NULL POINTER\n"; 93187063Srwatson else 94187063Srwatson getChild(i)->print(OS, indent+2); 95187063Srwatson } 96187063Srwatson} 97187063Srwatson 98187063Srwatsonvoid RecordMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 99187063Srwatson OS.indent(indent) << "Record\n"; 100187063Srwatson} 101187063Srwatson 102187063Srwatsonvoid RecordChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 103187063Srwatson OS.indent(indent) << "RecordChild: " << ChildNo << '\n'; 104187063Srwatson} 105187063Srwatson 106187063Srwatsonvoid RecordMemRefMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 107187063Srwatson OS.indent(indent) << "RecordMemRef\n"; 108187063Srwatson} 109187063Srwatson 110187063Srwatsonvoid CaptureGlueInputMatcher::printImpl(raw_ostream &OS, unsigned indent) const{ 111187063Srwatson OS.indent(indent) << "CaptureGlueInput\n"; 112187063Srwatson} 113187063Srwatson 114187063Srwatsonvoid MoveChildMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 115187063Srwatson OS.indent(indent) << "MoveChild " << ChildNo << '\n'; 116187063Srwatson} 117187063Srwatson 118187063Srwatsonvoid MoveParentMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 119187063Srwatson OS.indent(indent) << "MoveParent\n"; 120187063Srwatson} 121187063Srwatson 122187063Srwatsonvoid CheckSameMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 123187063Srwatson OS.indent(indent) << "CheckSame " << MatchNumber << '\n'; 124187063Srwatson} 125187063Srwatson 126187063Srwatsonvoid CheckPatternPredicateMatcher:: 127187063SrwatsonprintImpl(raw_ostream &OS, unsigned indent) const { 128187063Srwatson OS.indent(indent) << "CheckPatternPredicate " << Predicate << '\n'; 129187063Srwatson} 130187063Srwatson 131187063Srwatsonvoid CheckPredicateMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 132187063Srwatson OS.indent(indent) << "CheckPredicate " << PredName << '\n'; 133187063Srwatson} 134187063Srwatson 135187063Srwatsonvoid CheckOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 136187063Srwatson OS.indent(indent) << "CheckOpcode " << Opcode.getEnumName() << '\n'; 137187063Srwatson} 138187063Srwatson 139187063Srwatsonvoid SwitchOpcodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 140187063Srwatson OS.indent(indent) << "SwitchOpcode: {\n"; 141187063Srwatson for (unsigned i = 0, e = Cases.size(); i != e; ++i) { 142187063Srwatson OS.indent(indent) << "case " << Cases[i].first->getEnumName() << ":\n"; 143187063Srwatson Cases[i].second->print(OS, indent+2); 144187063Srwatson } 145187063Srwatson OS.indent(indent) << "}\n"; 146187063Srwatson} 147187063Srwatson 148187063Srwatson 149187063Srwatsonvoid CheckTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 150187063Srwatson OS.indent(indent) << "CheckType " << getEnumName(Type) << ", ResNo=" 151187063Srwatson << ResNo << '\n'; 152187063Srwatson} 153187063Srwatson 154187063Srwatsonvoid SwitchTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 155187063Srwatson OS.indent(indent) << "SwitchType: {\n"; 156187063Srwatson for (unsigned i = 0, e = Cases.size(); i != e; ++i) { 157187063Srwatson OS.indent(indent) << "case " << getEnumName(Cases[i].first) << ":\n"; 158187063Srwatson Cases[i].second->print(OS, indent+2); 159187063Srwatson } 160187063Srwatson OS.indent(indent) << "}\n"; 161187063Srwatson} 162187063Srwatson 163187063Srwatsonvoid CheckChildTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 164187063Srwatson OS.indent(indent) << "CheckChildType " << ChildNo << " " 165187063Srwatson << getEnumName(Type) << '\n'; 166187063Srwatson} 167187063Srwatson 168187063Srwatson 169187063Srwatsonvoid CheckIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 170187063Srwatson OS.indent(indent) << "CheckInteger " << Value << '\n'; 171187063Srwatson} 172187063Srwatson 173187063Srwatsonvoid CheckCondCodeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 174187063Srwatson OS.indent(indent) << "CheckCondCode ISD::" << CondCodeName << '\n'; 175187063Srwatson} 176187063Srwatson 177187063Srwatsonvoid CheckValueTypeMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 178187063Srwatson OS.indent(indent) << "CheckValueType MVT::" << TypeName << '\n'; 179187063Srwatson} 180187063Srwatson 181187063Srwatsonvoid CheckComplexPatMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 182187063Srwatson OS.indent(indent) << "CheckComplexPat " << Pattern.getSelectFunc() << '\n'; 183187063Srwatson} 184187063Srwatson 185187063Srwatsonvoid CheckAndImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 186187063Srwatson OS.indent(indent) << "CheckAndImm " << Value << '\n'; 187187063Srwatson} 188187063Srwatson 189187063Srwatsonvoid CheckOrImmMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 190187063Srwatson OS.indent(indent) << "CheckOrImm " << Value << '\n'; 191187063Srwatson} 192187063Srwatson 193187063Srwatsonvoid CheckFoldableChainNodeMatcher::printImpl(raw_ostream &OS, 194187063Srwatson unsigned indent) const { 195187063Srwatson OS.indent(indent) << "CheckFoldableChainNode\n"; 196187063Srwatson} 197187063Srwatson 198187063Srwatsonvoid EmitIntegerMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 199187063Srwatson OS.indent(indent) << "EmitInteger " << Val << " VT=" << VT << '\n'; 200187063Srwatson} 201187063Srwatson 202187063Srwatsonvoid EmitStringIntegerMatcher:: 203187063SrwatsonprintImpl(raw_ostream &OS, unsigned indent) const { 204187063Srwatson OS.indent(indent) << "EmitStringInteger " << Val << " VT=" << VT << '\n'; 205187063Srwatson} 206187063Srwatson 207187063Srwatsonvoid EmitRegisterMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 208187063Srwatson OS.indent(indent) << "EmitRegister "; 209187063Srwatson if (Reg) 210187063Srwatson OS << Reg->getName(); 211187063Srwatson else 212187063Srwatson OS << "zero_reg"; 213187063Srwatson OS << " VT=" << VT << '\n'; 214187063Srwatson} 215187063Srwatson 216187063Srwatsonvoid EmitConvertToTargetMatcher:: 217187063SrwatsonprintImpl(raw_ostream &OS, unsigned indent) const { 218187063Srwatson OS.indent(indent) << "EmitConvertToTarget " << Slot << '\n'; 219187063Srwatson} 220187063Srwatson 221187063Srwatsonvoid EmitMergeInputChainsMatcher:: 222187063SrwatsonprintImpl(raw_ostream &OS, unsigned indent) const { 223187063Srwatson OS.indent(indent) << "EmitMergeInputChains <todo: args>\n"; 224187063Srwatson} 225187063Srwatson 226187063Srwatsonvoid EmitCopyToRegMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 227187063Srwatson OS.indent(indent) << "EmitCopyToReg <todo: args>\n"; 228187063Srwatson} 229187063Srwatson 230187063Srwatsonvoid EmitNodeXFormMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 231187063Srwatson OS.indent(indent) << "EmitNodeXForm " << NodeXForm->getName() 232187063Srwatson << " Slot=" << Slot << '\n'; 233187063Srwatson} 234187063Srwatson 235187063Srwatson 236187063Srwatsonvoid EmitNodeMatcherCommon::printImpl(raw_ostream &OS, unsigned indent) const { 237187063Srwatson OS.indent(indent); 238187063Srwatson OS << (isa<MorphNodeToMatcher>(this) ? "MorphNodeTo: " : "EmitNode: ") 239187063Srwatson << OpcodeName << ": <todo flags> "; 240187063Srwatson 241187063Srwatson for (unsigned i = 0, e = VTs.size(); i != e; ++i) 242187063Srwatson OS << ' ' << getEnumName(VTs[i]); 243187063Srwatson OS << '('; 244187063Srwatson for (unsigned i = 0, e = Operands.size(); i != e; ++i) 245187063Srwatson OS << Operands[i] << ' '; 246187063Srwatson OS << ")\n"; 247187063Srwatson} 248187063Srwatson 249187063Srwatsonvoid MarkGlueResultsMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 250187063Srwatson OS.indent(indent) << "MarkGlueResults <todo: args>\n"; 251187063Srwatson} 252187063Srwatson 253187063Srwatsonvoid CompleteMatchMatcher::printImpl(raw_ostream &OS, unsigned indent) const { 254187063Srwatson OS.indent(indent) << "CompleteMatch <todo args>\n"; 255187063Srwatson OS.indent(indent) << "Src = " << *Pattern.getSrcPattern() << "\n"; 256187063Srwatson OS.indent(indent) << "Dst = " << *Pattern.getDstPattern() << "\n"; 257187063Srwatson} 258187063Srwatson 259187063Srwatson// getHashImpl Implementation. 260187063Srwatson 261187063Srwatsonunsigned CheckPatternPredicateMatcher::getHashImpl() const { 262187063Srwatson return HashString(Predicate); 263187063Srwatson} 264187063Srwatson 265187063Srwatsonunsigned CheckPredicateMatcher::getHashImpl() const { 266187063Srwatson return HashString(PredName); 267187063Srwatson} 268187063Srwatson 269187063Srwatsonunsigned CheckOpcodeMatcher::getHashImpl() const { 270187063Srwatson return HashString(Opcode.getEnumName()); 271187063Srwatson} 272187063Srwatson 273187063Srwatsonunsigned CheckCondCodeMatcher::getHashImpl() const { 274187063Srwatson return HashString(CondCodeName); 275187063Srwatson} 276187063Srwatson 277187063Srwatsonunsigned CheckValueTypeMatcher::getHashImpl() const { 278187063Srwatson return HashString(TypeName); 279187063Srwatson} 280187063Srwatson 281187063Srwatsonunsigned EmitStringIntegerMatcher::getHashImpl() const { 282187063Srwatson return HashString(Val) ^ VT; 283187063Srwatson} 284187063Srwatson 285187063Srwatsontemplate<typename It> 286187063Srwatsonstatic unsigned HashUnsigneds(It I, It E) { 287187063Srwatson unsigned Result = 0; 288187063Srwatson for (; I != E; ++I) 289187063Srwatson Result = (Result<<3) ^ *I; 290187063Srwatson return Result; 291187063Srwatson} 292187063Srwatson 293187063Srwatsonunsigned EmitMergeInputChainsMatcher::getHashImpl() const { 294187063Srwatson return HashUnsigneds(ChainNodes.begin(), ChainNodes.end()); 295187063Srwatson} 296187063Srwatson 297187063Srwatsonbool CheckOpcodeMatcher::isEqualImpl(const Matcher *M) const { 298187063Srwatson // Note: pointer equality isn't enough here, we have to check the enum names 299187063Srwatson // to ensure that the nodes are for the same opcode. 300187063Srwatson return cast<CheckOpcodeMatcher>(M)->Opcode.getEnumName() == 301187063Srwatson Opcode.getEnumName(); 302187063Srwatson} 303187063Srwatson 304187063Srwatson 305187063Srwatsonbool EmitNodeMatcherCommon::isEqualImpl(const Matcher *m) const { 306187063Srwatson const EmitNodeMatcherCommon *M = cast<EmitNodeMatcherCommon>(m); 307187063Srwatson return M->OpcodeName == OpcodeName && M->VTs == VTs && 308187063Srwatson M->Operands == Operands && M->HasChain == HasChain && 309187063Srwatson M->HasInGlue == HasInGlue && M->HasOutGlue == HasOutGlue && 310187063Srwatson M->HasMemRefs == HasMemRefs && 311187063Srwatson M->NumFixedArityOperands == NumFixedArityOperands; 312187063Srwatson} 313187063Srwatson 314187063Srwatsonunsigned EmitNodeMatcherCommon::getHashImpl() const { 315187063Srwatson return (HashString(OpcodeName) << 4) | Operands.size(); 316187063Srwatson} 317187063Srwatson 318187063Srwatson 319187063Srwatsonunsigned MarkGlueResultsMatcher::getHashImpl() const { 320187063Srwatson return HashUnsigneds(GlueResultNodes.begin(), GlueResultNodes.end()); 321187063Srwatson} 322187063Srwatson 323187063Srwatsonunsigned CompleteMatchMatcher::getHashImpl() const { 324187063Srwatson return HashUnsigneds(Results.begin(), Results.end()) ^ 325187063Srwatson ((unsigned)(intptr_t)&Pattern << 8); 326187063Srwatson} 327187063Srwatson 328187063Srwatson// isContradictoryImpl Implementations. 329187063Srwatson 330187063Srwatsonstatic bool TypesAreContradictory(MVT::SimpleValueType T1, 331187063Srwatson MVT::SimpleValueType T2) { 332187063Srwatson // If the two types are the same, then they are the same, so they don't 333187063Srwatson // contradict. 334187063Srwatson if (T1 == T2) return false; 335187063Srwatson 336187063Srwatson // If either type is about iPtr, then they don't conflict unless the other 337187063Srwatson // one is not a scalar integer type. 338187063Srwatson if (T1 == MVT::iPTR) 339187063Srwatson return !MVT(T2).isInteger() || MVT(T2).isVector(); 340187063Srwatson 341187063Srwatson if (T2 == MVT::iPTR) 342187063Srwatson return !MVT(T1).isInteger() || MVT(T1).isVector(); 343187063Srwatson 344187063Srwatson // Otherwise, they are two different non-iPTR types, they conflict. 345187063Srwatson return true; 346187063Srwatson} 347187063Srwatson 348187063Srwatsonbool CheckOpcodeMatcher::isContradictoryImpl(const Matcher *M) const { 349187063Srwatson if (const CheckOpcodeMatcher *COM = dyn_cast<CheckOpcodeMatcher>(M)) { 350187063Srwatson // One node can't have two different opcodes! 351187063Srwatson // Note: pointer equality isn't enough here, we have to check the enum names 352187063Srwatson // to ensure that the nodes are for the same opcode. 353187063Srwatson return COM->getOpcode().getEnumName() != getOpcode().getEnumName(); 354187063Srwatson } 355187063Srwatson 356187063Srwatson // If the node has a known type, and if the type we're checking for is 357187063Srwatson // different, then we know they contradict. For example, a check for 358187063Srwatson // ISD::STORE will never be true at the same time a check for Type i32 is. 359187063Srwatson if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) { 360187063Srwatson // If checking for a result the opcode doesn't have, it can't match. 361187063Srwatson if (CT->getResNo() >= getOpcode().getNumResults()) 362187063Srwatson return true; 363187063Srwatson 364187063Srwatson MVT::SimpleValueType NodeType = getOpcode().getKnownType(CT->getResNo()); 365187063Srwatson if (NodeType != MVT::Other) 366187063Srwatson return TypesAreContradictory(NodeType, CT->getType()); 367187063Srwatson } 368187063Srwatson 369187063Srwatson return false; 370187063Srwatson} 371187063Srwatson 372187063Srwatsonbool CheckTypeMatcher::isContradictoryImpl(const Matcher *M) const { 373187063Srwatson if (const CheckTypeMatcher *CT = dyn_cast<CheckTypeMatcher>(M)) 374187063Srwatson return TypesAreContradictory(getType(), CT->getType()); 375187063Srwatson return false; 376187063Srwatson} 377187063Srwatson 378187063Srwatsonbool CheckChildTypeMatcher::isContradictoryImpl(const Matcher *M) const { 379187063Srwatson if (const CheckChildTypeMatcher *CC = dyn_cast<CheckChildTypeMatcher>(M)) { 380187063Srwatson // If the two checks are about different nodes, we don't know if they 381187063Srwatson // conflict! 382187063Srwatson if (CC->getChildNo() != getChildNo()) 383187063Srwatson return false; 384187063Srwatson 385187063Srwatson return TypesAreContradictory(getType(), CC->getType()); 386187063Srwatson } 387187063Srwatson return false; 388187063Srwatson} 389187063Srwatson 390187063Srwatsonbool CheckIntegerMatcher::isContradictoryImpl(const Matcher *M) const { 391187063Srwatson if (const CheckIntegerMatcher *CIM = dyn_cast<CheckIntegerMatcher>(M)) 392187063Srwatson return CIM->getValue() != getValue(); 393187063Srwatson return false; 394187063Srwatson} 395187063Srwatson 396187063Srwatsonbool CheckValueTypeMatcher::isContradictoryImpl(const Matcher *M) const { 397187063Srwatson if (const CheckValueTypeMatcher *CVT = dyn_cast<CheckValueTypeMatcher>(M)) 398187063Srwatson return CVT->getTypeName() != getTypeName(); 399187063Srwatson return false; 400187063Srwatson} 401187063Srwatson 402187063Srwatson