CodeGenDAGPatterns.cpp revision ee4fa1977dd3a495a8857eef924ee5961db765c6
1b483ea3f0e16760c75045042f25372a50527d30fArun Sharma//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===// 2b483ea3f0e16760c75045042f25372a50527d30fArun Sharma// 3b483ea3f0e16760c75045042f25372a50527d30fArun Sharma// The LLVM Compiler Infrastructure 4d20df8b3183d1f179ffc30a5ceabb9d1375ac0ffArun Sharma// 5d20df8b3183d1f179ffc30a5ceabb9d1375ac0ffArun Sharma// This file is distributed under the University of Illinois Open Source 6b483ea3f0e16760c75045042f25372a50527d30fArun Sharma// License. See LICENSE.TXT for details. 7b483ea3f0e16760c75045042f25372a50527d30fArun Sharma// 8b483ea3f0e16760c75045042f25372a50527d30fArun Sharma//===----------------------------------------------------------------------===// 9b483ea3f0e16760c75045042f25372a50527d30fArun Sharma// 10b483ea3f0e16760c75045042f25372a50527d30fArun Sharma// This file implements the CodeGenDAGPatterns class, which is used to read and 11b483ea3f0e16760c75045042f25372a50527d30fArun Sharma// represent the patterns present in a .td file for instructions. 12b483ea3f0e16760c75045042f25372a50527d30fArun Sharma// 13b483ea3f0e16760c75045042f25372a50527d30fArun Sharma//===----------------------------------------------------------------------===// 14b483ea3f0e16760c75045042f25372a50527d30fArun Sharma 15b483ea3f0e16760c75045042f25372a50527d30fArun Sharma#include "CodeGenDAGPatterns.h" 16b483ea3f0e16760c75045042f25372a50527d30fArun Sharma#include "Record.h" 17b483ea3f0e16760c75045042f25372a50527d30fArun Sharma#include "llvm/ADT/StringExtras.h" 188d5b1aeeffb80515197fd7aeee0b3fbfac904ecdTommi Rantala#include "llvm/Support/Debug.h" 198d5b1aeeffb80515197fd7aeee0b3fbfac904ecdTommi Rantala#include "llvm/Support/Streams.h" 20b483ea3f0e16760c75045042f25372a50527d30fArun Sharma#include <set> 21b483ea3f0e16760c75045042f25372a50527d30fArun Sharma#include <algorithm> 22b483ea3f0e16760c75045042f25372a50527d30fArun Sharmausing namespace llvm; 23b483ea3f0e16760c75045042f25372a50527d30fArun Sharma 24b483ea3f0e16760c75045042f25372a50527d30fArun Sharma//===----------------------------------------------------------------------===// 25b483ea3f0e16760c75045042f25372a50527d30fArun Sharma// Helpers for working with extended types. 26b483ea3f0e16760c75045042f25372a50527d30fArun Sharma 27d20df8b3183d1f179ffc30a5ceabb9d1375ac0ffArun Sharma/// FilterVTs - Filter a list of VT's according to a predicate. 28d20df8b3183d1f179ffc30a5ceabb9d1375ac0ffArun Sharma/// 29d20df8b3183d1f179ffc30a5ceabb9d1375ac0ffArun Sharmatemplate<typename T> 30d20df8b3183d1f179ffc30a5ceabb9d1375ac0ffArun Sharmastatic std::vector<MVT::ValueType> 31d20df8b3183d1f179ffc30a5ceabb9d1375ac0ffArun SharmaFilterVTs(const std::vector<MVT::ValueType> &InVTs, T Filter) { 32d20df8b3183d1f179ffc30a5ceabb9d1375ac0ffArun Sharma std::vector<MVT::ValueType> Result; 33 for (unsigned i = 0, e = InVTs.size(); i != e; ++i) 34 if (Filter(InVTs[i])) 35 Result.push_back(InVTs[i]); 36 return Result; 37} 38 39template<typename T> 40static std::vector<unsigned char> 41FilterEVTs(const std::vector<unsigned char> &InVTs, T Filter) { 42 std::vector<unsigned char> Result; 43 for (unsigned i = 0, e = InVTs.size(); i != e; ++i) 44 if (Filter((MVT::ValueType)InVTs[i])) 45 Result.push_back(InVTs[i]); 46 return Result; 47} 48 49static std::vector<unsigned char> 50ConvertVTs(const std::vector<MVT::ValueType> &InVTs) { 51 std::vector<unsigned char> Result; 52 for (unsigned i = 0, e = InVTs.size(); i != e; ++i) 53 Result.push_back(InVTs[i]); 54 return Result; 55} 56 57static bool LHSIsSubsetOfRHS(const std::vector<unsigned char> &LHS, 58 const std::vector<unsigned char> &RHS) { 59 if (LHS.size() > RHS.size()) return false; 60 for (unsigned i = 0, e = LHS.size(); i != e; ++i) 61 if (std::find(RHS.begin(), RHS.end(), LHS[i]) == RHS.end()) 62 return false; 63 return true; 64} 65 66/// isExtIntegerVT - Return true if the specified extended value type vector 67/// contains isInt or an integer value type. 68namespace llvm { 69namespace MVT { 70bool isExtIntegerInVTs(const std::vector<unsigned char> &EVTs) { 71 assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!"); 72 return EVTs[0] == isInt || !(FilterEVTs(EVTs, isInteger).empty()); 73} 74 75/// isExtFloatingPointVT - Return true if the specified extended value type 76/// vector contains isFP or a FP value type. 77bool isExtFloatingPointInVTs(const std::vector<unsigned char> &EVTs) { 78 assert(!EVTs.empty() && "Cannot check for integer in empty ExtVT list!"); 79 return EVTs[0] == isFP || !(FilterEVTs(EVTs, isFloatingPoint).empty()); 80} 81} // end namespace MVT. 82} // end namespace llvm. 83 84 85/// Dependent variable map for CodeGenDAGPattern variant generation 86typedef std::map<std::string, int> DepVarMap; 87 88/// Const iterator shorthand for DepVarMap 89typedef DepVarMap::const_iterator DepVarMap_citer; 90 91namespace { 92void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) { 93 if (N->isLeaf()) { 94 if (dynamic_cast<DefInit*>(N->getLeafValue()) != NULL) { 95 DepMap[N->getName()]++; 96 } 97 } else { 98 for (size_t i = 0, e = N->getNumChildren(); i != e; ++i) 99 FindDepVarsOf(N->getChild(i), DepMap); 100 } 101} 102 103//! Find dependent variables within child patterns 104/*! 105 */ 106void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) { 107 DepVarMap depcounts; 108 FindDepVarsOf(N, depcounts); 109 for (DepVarMap_citer i = depcounts.begin(); i != depcounts.end(); ++i) { 110 if (i->second > 1) { // std::pair<std::string, int> 111 DepVars.insert(i->first); 112 } 113 } 114} 115 116//! Dump the dependent variable set: 117void DumpDepVars(MultipleUseVarSet &DepVars) { 118 if (DepVars.empty()) { 119 DOUT << "<empty set>"; 120 } else { 121 DOUT << "[ "; 122 for (MultipleUseVarSet::const_iterator i = DepVars.begin(), e = DepVars.end(); 123 i != e; ++i) { 124 DOUT << (*i) << " "; 125 } 126 DOUT << "]"; 127 } 128} 129} 130 131//===----------------------------------------------------------------------===// 132// SDTypeConstraint implementation 133// 134 135SDTypeConstraint::SDTypeConstraint(Record *R) { 136 OperandNo = R->getValueAsInt("OperandNum"); 137 138 if (R->isSubClassOf("SDTCisVT")) { 139 ConstraintType = SDTCisVT; 140 x.SDTCisVT_Info.VT = getValueType(R->getValueAsDef("VT")); 141 } else if (R->isSubClassOf("SDTCisPtrTy")) { 142 ConstraintType = SDTCisPtrTy; 143 } else if (R->isSubClassOf("SDTCisInt")) { 144 ConstraintType = SDTCisInt; 145 } else if (R->isSubClassOf("SDTCisFP")) { 146 ConstraintType = SDTCisFP; 147 } else if (R->isSubClassOf("SDTCisSameAs")) { 148 ConstraintType = SDTCisSameAs; 149 x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum"); 150 } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) { 151 ConstraintType = SDTCisVTSmallerThanOp; 152 x.SDTCisVTSmallerThanOp_Info.OtherOperandNum = 153 R->getValueAsInt("OtherOperandNum"); 154 } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) { 155 ConstraintType = SDTCisOpSmallerThanOp; 156 x.SDTCisOpSmallerThanOp_Info.BigOperandNum = 157 R->getValueAsInt("BigOperandNum"); 158 } else if (R->isSubClassOf("SDTCisIntVectorOfSameSize")) { 159 ConstraintType = SDTCisIntVectorOfSameSize; 160 x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum = 161 R->getValueAsInt("OtherOpNum"); 162 } else if (R->isSubClassOf("SDTCisEltOfVec")) { 163 ConstraintType = SDTCisEltOfVec; 164 x.SDTCisEltOfVec_Info.OtherOperandNum = 165 R->getValueAsInt("OtherOpNum"); 166 } else { 167 cerr << "Unrecognized SDTypeConstraint '" << R->getName() << "'!\n"; 168 exit(1); 169 } 170} 171 172/// getOperandNum - Return the node corresponding to operand #OpNo in tree 173/// N, which has NumResults results. 174TreePatternNode *SDTypeConstraint::getOperandNum(unsigned OpNo, 175 TreePatternNode *N, 176 unsigned NumResults) const { 177 assert(NumResults <= 1 && 178 "We only work with nodes with zero or one result so far!"); 179 180 if (OpNo >= (NumResults + N->getNumChildren())) { 181 cerr << "Invalid operand number " << OpNo << " "; 182 N->dump(); 183 cerr << '\n'; 184 exit(1); 185 } 186 187 if (OpNo < NumResults) 188 return N; // FIXME: need value # 189 else 190 return N->getChild(OpNo-NumResults); 191} 192 193/// ApplyTypeConstraint - Given a node in a pattern, apply this type 194/// constraint to the nodes operands. This returns true if it makes a 195/// change, false otherwise. If a type contradiction is found, throw an 196/// exception. 197bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N, 198 const SDNodeInfo &NodeInfo, 199 TreePattern &TP) const { 200 unsigned NumResults = NodeInfo.getNumResults(); 201 assert(NumResults <= 1 && 202 "We only work with nodes with zero or one result so far!"); 203 204 // Check that the number of operands is sane. Negative operands -> varargs. 205 if (NodeInfo.getNumOperands() >= 0) { 206 if (N->getNumChildren() != (unsigned)NodeInfo.getNumOperands()) 207 TP.error(N->getOperator()->getName() + " node requires exactly " + 208 itostr(NodeInfo.getNumOperands()) + " operands!"); 209 } 210 211 const CodeGenTarget &CGT = TP.getDAGPatterns().getTargetInfo(); 212 213 TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NumResults); 214 215 switch (ConstraintType) { 216 default: assert(0 && "Unknown constraint type!"); 217 case SDTCisVT: 218 // Operand must be a particular type. 219 return NodeToApply->UpdateNodeType(x.SDTCisVT_Info.VT, TP); 220 case SDTCisPtrTy: { 221 // Operand must be same as target pointer type. 222 return NodeToApply->UpdateNodeType(MVT::iPTR, TP); 223 } 224 case SDTCisInt: { 225 // If there is only one integer type supported, this must be it. 226 std::vector<MVT::ValueType> IntVTs = 227 FilterVTs(CGT.getLegalValueTypes(), MVT::isInteger); 228 229 // If we found exactly one supported integer type, apply it. 230 if (IntVTs.size() == 1) 231 return NodeToApply->UpdateNodeType(IntVTs[0], TP); 232 return NodeToApply->UpdateNodeType(MVT::isInt, TP); 233 } 234 case SDTCisFP: { 235 // If there is only one FP type supported, this must be it. 236 std::vector<MVT::ValueType> FPVTs = 237 FilterVTs(CGT.getLegalValueTypes(), MVT::isFloatingPoint); 238 239 // If we found exactly one supported FP type, apply it. 240 if (FPVTs.size() == 1) 241 return NodeToApply->UpdateNodeType(FPVTs[0], TP); 242 return NodeToApply->UpdateNodeType(MVT::isFP, TP); 243 } 244 case SDTCisSameAs: { 245 TreePatternNode *OtherNode = 246 getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NumResults); 247 return NodeToApply->UpdateNodeType(OtherNode->getExtTypes(), TP) | 248 OtherNode->UpdateNodeType(NodeToApply->getExtTypes(), TP); 249 } 250 case SDTCisVTSmallerThanOp: { 251 // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must 252 // have an integer type that is smaller than the VT. 253 if (!NodeToApply->isLeaf() || 254 !dynamic_cast<DefInit*>(NodeToApply->getLeafValue()) || 255 !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef() 256 ->isSubClassOf("ValueType")) 257 TP.error(N->getOperator()->getName() + " expects a VT operand!"); 258 MVT::ValueType VT = 259 getValueType(static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()); 260 if (!MVT::isInteger(VT)) 261 TP.error(N->getOperator()->getName() + " VT operand must be integer!"); 262 263 TreePatternNode *OtherNode = 264 getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N,NumResults); 265 266 // It must be integer. 267 bool MadeChange = false; 268 MadeChange |= OtherNode->UpdateNodeType(MVT::isInt, TP); 269 270 // This code only handles nodes that have one type set. Assert here so 271 // that we can change this if we ever need to deal with multiple value 272 // types at this point. 273 assert(OtherNode->getExtTypes().size() == 1 && "Node has too many types!"); 274 if (OtherNode->hasTypeSet() && OtherNode->getTypeNum(0) <= VT) 275 OtherNode->UpdateNodeType(MVT::Other, TP); // Throw an error. 276 return false; 277 } 278 case SDTCisOpSmallerThanOp: { 279 TreePatternNode *BigOperand = 280 getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NumResults); 281 282 // Both operands must be integer or FP, but we don't care which. 283 bool MadeChange = false; 284 285 // This code does not currently handle nodes which have multiple types, 286 // where some types are integer, and some are fp. Assert that this is not 287 // the case. 288 assert(!(MVT::isExtIntegerInVTs(NodeToApply->getExtTypes()) && 289 MVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) && 290 !(MVT::isExtIntegerInVTs(BigOperand->getExtTypes()) && 291 MVT::isExtFloatingPointInVTs(BigOperand->getExtTypes())) && 292 "SDTCisOpSmallerThanOp does not handle mixed int/fp types!"); 293 if (MVT::isExtIntegerInVTs(NodeToApply->getExtTypes())) 294 MadeChange |= BigOperand->UpdateNodeType(MVT::isInt, TP); 295 else if (MVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) 296 MadeChange |= BigOperand->UpdateNodeType(MVT::isFP, TP); 297 if (MVT::isExtIntegerInVTs(BigOperand->getExtTypes())) 298 MadeChange |= NodeToApply->UpdateNodeType(MVT::isInt, TP); 299 else if (MVT::isExtFloatingPointInVTs(BigOperand->getExtTypes())) 300 MadeChange |= NodeToApply->UpdateNodeType(MVT::isFP, TP); 301 302 std::vector<MVT::ValueType> VTs = CGT.getLegalValueTypes(); 303 304 if (MVT::isExtIntegerInVTs(NodeToApply->getExtTypes())) { 305 VTs = FilterVTs(VTs, MVT::isInteger); 306 } else if (MVT::isExtFloatingPointInVTs(NodeToApply->getExtTypes())) { 307 VTs = FilterVTs(VTs, MVT::isFloatingPoint); 308 } else { 309 VTs.clear(); 310 } 311 312 switch (VTs.size()) { 313 default: // Too many VT's to pick from. 314 case 0: break; // No info yet. 315 case 1: 316 // Only one VT of this flavor. Cannot ever satisify the constraints. 317 return NodeToApply->UpdateNodeType(MVT::Other, TP); // throw 318 case 2: 319 // If we have exactly two possible types, the little operand must be the 320 // small one, the big operand should be the big one. Common with 321 // float/double for example. 322 assert(VTs[0] < VTs[1] && "Should be sorted!"); 323 MadeChange |= NodeToApply->UpdateNodeType(VTs[0], TP); 324 MadeChange |= BigOperand->UpdateNodeType(VTs[1], TP); 325 break; 326 } 327 return MadeChange; 328 } 329 case SDTCisIntVectorOfSameSize: { 330 TreePatternNode *OtherOperand = 331 getOperandNum(x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum, 332 N, NumResults); 333 if (OtherOperand->hasTypeSet()) { 334 if (!MVT::isVector(OtherOperand->getTypeNum(0))) 335 TP.error(N->getOperator()->getName() + " VT operand must be a vector!"); 336 MVT::ValueType IVT = OtherOperand->getTypeNum(0); 337 IVT = MVT::getIntVectorWithNumElements(MVT::getVectorNumElements(IVT)); 338 return NodeToApply->UpdateNodeType(IVT, TP); 339 } 340 return false; 341 } 342 case SDTCisEltOfVec: { 343 TreePatternNode *OtherOperand = 344 getOperandNum(x.SDTCisIntVectorOfSameSize_Info.OtherOperandNum, 345 N, NumResults); 346 if (OtherOperand->hasTypeSet()) { 347 if (!MVT::isVector(OtherOperand->getTypeNum(0))) 348 TP.error(N->getOperator()->getName() + " VT operand must be a vector!"); 349 MVT::ValueType IVT = OtherOperand->getTypeNum(0); 350 IVT = MVT::getVectorElementType(IVT); 351 return NodeToApply->UpdateNodeType(IVT, TP); 352 } 353 return false; 354 } 355 } 356 return false; 357} 358 359//===----------------------------------------------------------------------===// 360// SDNodeInfo implementation 361// 362SDNodeInfo::SDNodeInfo(Record *R) : Def(R) { 363 EnumName = R->getValueAsString("Opcode"); 364 SDClassName = R->getValueAsString("SDClass"); 365 Record *TypeProfile = R->getValueAsDef("TypeProfile"); 366 NumResults = TypeProfile->getValueAsInt("NumResults"); 367 NumOperands = TypeProfile->getValueAsInt("NumOperands"); 368 369 // Parse the properties. 370 Properties = 0; 371 std::vector<Record*> PropList = R->getValueAsListOfDefs("Properties"); 372 for (unsigned i = 0, e = PropList.size(); i != e; ++i) { 373 if (PropList[i]->getName() == "SDNPCommutative") { 374 Properties |= 1 << SDNPCommutative; 375 } else if (PropList[i]->getName() == "SDNPAssociative") { 376 Properties |= 1 << SDNPAssociative; 377 } else if (PropList[i]->getName() == "SDNPHasChain") { 378 Properties |= 1 << SDNPHasChain; 379 } else if (PropList[i]->getName() == "SDNPOutFlag") { 380 Properties |= 1 << SDNPOutFlag; 381 } else if (PropList[i]->getName() == "SDNPInFlag") { 382 Properties |= 1 << SDNPInFlag; 383 } else if (PropList[i]->getName() == "SDNPOptInFlag") { 384 Properties |= 1 << SDNPOptInFlag; 385 } else if (PropList[i]->getName() == "SDNPMayStore") { 386 Properties |= 1 << SDNPMayStore; 387 } else if (PropList[i]->getName() == "SDNPMayLoad") { 388 Properties |= 1 << SDNPMayLoad; 389 } else if (PropList[i]->getName() == "SDNPSideEffect") { 390 Properties |= 1 << SDNPSideEffect; 391 } else { 392 cerr << "Unknown SD Node property '" << PropList[i]->getName() 393 << "' on node '" << R->getName() << "'!\n"; 394 exit(1); 395 } 396 } 397 398 399 // Parse the type constraints. 400 std::vector<Record*> ConstraintList = 401 TypeProfile->getValueAsListOfDefs("Constraints"); 402 TypeConstraints.assign(ConstraintList.begin(), ConstraintList.end()); 403} 404 405//===----------------------------------------------------------------------===// 406// TreePatternNode implementation 407// 408 409TreePatternNode::~TreePatternNode() { 410#if 0 // FIXME: implement refcounted tree nodes! 411 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 412 delete getChild(i); 413#endif 414} 415 416/// UpdateNodeType - Set the node type of N to VT if VT contains 417/// information. If N already contains a conflicting type, then throw an 418/// exception. This returns true if any information was updated. 419/// 420bool TreePatternNode::UpdateNodeType(const std::vector<unsigned char> &ExtVTs, 421 TreePattern &TP) { 422 assert(!ExtVTs.empty() && "Cannot update node type with empty type vector!"); 423 424 if (ExtVTs[0] == MVT::isUnknown || LHSIsSubsetOfRHS(getExtTypes(), ExtVTs)) 425 return false; 426 if (isTypeCompletelyUnknown() || LHSIsSubsetOfRHS(ExtVTs, getExtTypes())) { 427 setTypes(ExtVTs); 428 return true; 429 } 430 431 if (getExtTypeNum(0) == MVT::iPTR) { 432 if (ExtVTs[0] == MVT::iPTR || ExtVTs[0] == MVT::isInt) 433 return false; 434 if (MVT::isExtIntegerInVTs(ExtVTs)) { 435 std::vector<unsigned char> FVTs = FilterEVTs(ExtVTs, MVT::isInteger); 436 if (FVTs.size()) { 437 setTypes(ExtVTs); 438 return true; 439 } 440 } 441 } 442 443 if (ExtVTs[0] == MVT::isInt && MVT::isExtIntegerInVTs(getExtTypes())) { 444 assert(hasTypeSet() && "should be handled above!"); 445 std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger); 446 if (getExtTypes() == FVTs) 447 return false; 448 setTypes(FVTs); 449 return true; 450 } 451 if (ExtVTs[0] == MVT::iPTR && MVT::isExtIntegerInVTs(getExtTypes())) { 452 //assert(hasTypeSet() && "should be handled above!"); 453 std::vector<unsigned char> FVTs = FilterEVTs(getExtTypes(), MVT::isInteger); 454 if (getExtTypes() == FVTs) 455 return false; 456 if (FVTs.size()) { 457 setTypes(FVTs); 458 return true; 459 } 460 } 461 if (ExtVTs[0] == MVT::isFP && MVT::isExtFloatingPointInVTs(getExtTypes())) { 462 assert(hasTypeSet() && "should be handled above!"); 463 std::vector<unsigned char> FVTs = 464 FilterEVTs(getExtTypes(), MVT::isFloatingPoint); 465 if (getExtTypes() == FVTs) 466 return false; 467 setTypes(FVTs); 468 return true; 469 } 470 471 // If we know this is an int or fp type, and we are told it is a specific one, 472 // take the advice. 473 // 474 // Similarly, we should probably set the type here to the intersection of 475 // {isInt|isFP} and ExtVTs 476 if ((getExtTypeNum(0) == MVT::isInt && MVT::isExtIntegerInVTs(ExtVTs)) || 477 (getExtTypeNum(0) == MVT::isFP && MVT::isExtFloatingPointInVTs(ExtVTs))){ 478 setTypes(ExtVTs); 479 return true; 480 } 481 if (getExtTypeNum(0) == MVT::isInt && ExtVTs[0] == MVT::iPTR) { 482 setTypes(ExtVTs); 483 return true; 484 } 485 486 if (isLeaf()) { 487 dump(); 488 cerr << " "; 489 TP.error("Type inference contradiction found in node!"); 490 } else { 491 TP.error("Type inference contradiction found in node " + 492 getOperator()->getName() + "!"); 493 } 494 return true; // unreachable 495} 496 497 498void TreePatternNode::print(std::ostream &OS) const { 499 if (isLeaf()) { 500 OS << *getLeafValue(); 501 } else { 502 OS << "(" << getOperator()->getName(); 503 } 504 505 // FIXME: At some point we should handle printing all the value types for 506 // nodes that are multiply typed. 507 switch (getExtTypeNum(0)) { 508 case MVT::Other: OS << ":Other"; break; 509 case MVT::isInt: OS << ":isInt"; break; 510 case MVT::isFP : OS << ":isFP"; break; 511 case MVT::isUnknown: ; /*OS << ":?";*/ break; 512 case MVT::iPTR: OS << ":iPTR"; break; 513 default: { 514 std::string VTName = llvm::getName(getTypeNum(0)); 515 // Strip off MVT:: prefix if present. 516 if (VTName.substr(0,5) == "MVT::") 517 VTName = VTName.substr(5); 518 OS << ":" << VTName; 519 break; 520 } 521 } 522 523 if (!isLeaf()) { 524 if (getNumChildren() != 0) { 525 OS << " "; 526 getChild(0)->print(OS); 527 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 528 OS << ", "; 529 getChild(i)->print(OS); 530 } 531 } 532 OS << ")"; 533 } 534 535 if (!PredicateFn.empty()) 536 OS << "<<P:" << PredicateFn << ">>"; 537 if (TransformFn) 538 OS << "<<X:" << TransformFn->getName() << ">>"; 539 if (!getName().empty()) 540 OS << ":$" << getName(); 541 542} 543void TreePatternNode::dump() const { 544 print(*cerr.stream()); 545} 546 547/// isIsomorphicTo - Return true if this node is recursively 548/// isomorphic to the specified node. For this comparison, the node's 549/// entire state is considered. The assigned name is ignored, since 550/// nodes with differing names are considered isomorphic. However, if 551/// the assigned name is present in the dependent variable set, then 552/// the assigned name is considered significant and the node is 553/// isomorphic if the names match. 554bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N, 555 const MultipleUseVarSet &DepVars) const { 556 if (N == this) return true; 557 if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() || 558 getPredicateFn() != N->getPredicateFn() || 559 getTransformFn() != N->getTransformFn()) 560 return false; 561 562 if (isLeaf()) { 563 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) { 564 if (DefInit *NDI = dynamic_cast<DefInit*>(N->getLeafValue())) { 565 return ((DI->getDef() == NDI->getDef()) 566 && (DepVars.find(getName()) == DepVars.end() 567 || getName() == N->getName())); 568 } 569 } 570 return getLeafValue() == N->getLeafValue(); 571 } 572 573 if (N->getOperator() != getOperator() || 574 N->getNumChildren() != getNumChildren()) return false; 575 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 576 if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars)) 577 return false; 578 return true; 579} 580 581/// clone - Make a copy of this tree and all of its children. 582/// 583TreePatternNode *TreePatternNode::clone() const { 584 TreePatternNode *New; 585 if (isLeaf()) { 586 New = new TreePatternNode(getLeafValue()); 587 } else { 588 std::vector<TreePatternNode*> CChildren; 589 CChildren.reserve(Children.size()); 590 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 591 CChildren.push_back(getChild(i)->clone()); 592 New = new TreePatternNode(getOperator(), CChildren); 593 } 594 New->setName(getName()); 595 New->setTypes(getExtTypes()); 596 New->setPredicateFn(getPredicateFn()); 597 New->setTransformFn(getTransformFn()); 598 return New; 599} 600 601/// SubstituteFormalArguments - Replace the formal arguments in this tree 602/// with actual values specified by ArgMap. 603void TreePatternNode:: 604SubstituteFormalArguments(std::map<std::string, TreePatternNode*> &ArgMap) { 605 if (isLeaf()) return; 606 607 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) { 608 TreePatternNode *Child = getChild(i); 609 if (Child->isLeaf()) { 610 Init *Val = Child->getLeafValue(); 611 if (dynamic_cast<DefInit*>(Val) && 612 static_cast<DefInit*>(Val)->getDef()->getName() == "node") { 613 // We found a use of a formal argument, replace it with its value. 614 Child = ArgMap[Child->getName()]; 615 assert(Child && "Couldn't find formal argument!"); 616 setChild(i, Child); 617 } 618 } else { 619 getChild(i)->SubstituteFormalArguments(ArgMap); 620 } 621 } 622} 623 624 625/// InlinePatternFragments - If this pattern refers to any pattern 626/// fragments, inline them into place, giving us a pattern without any 627/// PatFrag references. 628TreePatternNode *TreePatternNode::InlinePatternFragments(TreePattern &TP) { 629 if (isLeaf()) return this; // nothing to do. 630 Record *Op = getOperator(); 631 632 if (!Op->isSubClassOf("PatFrag")) { 633 // Just recursively inline children nodes. 634 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 635 setChild(i, getChild(i)->InlinePatternFragments(TP)); 636 return this; 637 } 638 639 // Otherwise, we found a reference to a fragment. First, look up its 640 // TreePattern record. 641 TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op); 642 643 // Verify that we are passing the right number of operands. 644 if (Frag->getNumArgs() != Children.size()) 645 TP.error("'" + Op->getName() + "' fragment requires " + 646 utostr(Frag->getNumArgs()) + " operands!"); 647 648 TreePatternNode *FragTree = Frag->getOnlyTree()->clone(); 649 650 // Resolve formal arguments to their actual value. 651 if (Frag->getNumArgs()) { 652 // Compute the map of formal to actual arguments. 653 std::map<std::string, TreePatternNode*> ArgMap; 654 for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) 655 ArgMap[Frag->getArgName(i)] = getChild(i)->InlinePatternFragments(TP); 656 657 FragTree->SubstituteFormalArguments(ArgMap); 658 } 659 660 FragTree->setName(getName()); 661 FragTree->UpdateNodeType(getExtTypes(), TP); 662 663 // Get a new copy of this fragment to stitch into here. 664 //delete this; // FIXME: implement refcounting! 665 return FragTree; 666} 667 668/// getImplicitType - Check to see if the specified record has an implicit 669/// type which should be applied to it. This infer the type of register 670/// references from the register file information, for example. 671/// 672static std::vector<unsigned char> getImplicitType(Record *R, bool NotRegisters, 673 TreePattern &TP) { 674 // Some common return values 675 std::vector<unsigned char> Unknown(1, MVT::isUnknown); 676 std::vector<unsigned char> Other(1, MVT::Other); 677 678 // Check to see if this is a register or a register class... 679 if (R->isSubClassOf("RegisterClass")) { 680 if (NotRegisters) 681 return Unknown; 682 const CodeGenRegisterClass &RC = 683 TP.getDAGPatterns().getTargetInfo().getRegisterClass(R); 684 return ConvertVTs(RC.getValueTypes()); 685 } else if (R->isSubClassOf("PatFrag")) { 686 // Pattern fragment types will be resolved when they are inlined. 687 return Unknown; 688 } else if (R->isSubClassOf("Register")) { 689 if (NotRegisters) 690 return Unknown; 691 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo(); 692 return T.getRegisterVTs(R); 693 } else if (R->isSubClassOf("ValueType") || R->isSubClassOf("CondCode")) { 694 // Using a VTSDNode or CondCodeSDNode. 695 return Other; 696 } else if (R->isSubClassOf("ComplexPattern")) { 697 if (NotRegisters) 698 return Unknown; 699 std::vector<unsigned char> 700 ComplexPat(1, TP.getDAGPatterns().getComplexPattern(R).getValueType()); 701 return ComplexPat; 702 } else if (R->getName() == "ptr_rc") { 703 Other[0] = MVT::iPTR; 704 return Other; 705 } else if (R->getName() == "node" || R->getName() == "srcvalue" || 706 R->getName() == "zero_reg") { 707 // Placeholder. 708 return Unknown; 709 } 710 711 TP.error("Unknown node flavor used in pattern: " + R->getName()); 712 return Other; 713} 714 715 716/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the 717/// CodeGenIntrinsic information for it, otherwise return a null pointer. 718const CodeGenIntrinsic *TreePatternNode:: 719getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const { 720 if (getOperator() != CDP.get_intrinsic_void_sdnode() && 721 getOperator() != CDP.get_intrinsic_w_chain_sdnode() && 722 getOperator() != CDP.get_intrinsic_wo_chain_sdnode()) 723 return 0; 724 725 unsigned IID = 726 dynamic_cast<IntInit*>(getChild(0)->getLeafValue())->getValue(); 727 return &CDP.getIntrinsicInfo(IID); 728} 729 730 731/// ApplyTypeConstraints - Apply all of the type constraints relevent to 732/// this node and its children in the tree. This returns true if it makes a 733/// change, false otherwise. If a type contradiction is found, throw an 734/// exception. 735bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) { 736 CodeGenDAGPatterns &CDP = TP.getDAGPatterns(); 737 if (isLeaf()) { 738 if (DefInit *DI = dynamic_cast<DefInit*>(getLeafValue())) { 739 // If it's a regclass or something else known, include the type. 740 return UpdateNodeType(getImplicitType(DI->getDef(), NotRegisters, TP),TP); 741 } else if (IntInit *II = dynamic_cast<IntInit*>(getLeafValue())) { 742 // Int inits are always integers. :) 743 bool MadeChange = UpdateNodeType(MVT::isInt, TP); 744 745 if (hasTypeSet()) { 746 // At some point, it may make sense for this tree pattern to have 747 // multiple types. Assert here that it does not, so we revisit this 748 // code when appropriate. 749 assert(getExtTypes().size() >= 1 && "TreePattern doesn't have a type!"); 750 MVT::ValueType VT = getTypeNum(0); 751 for (unsigned i = 1, e = getExtTypes().size(); i != e; ++i) 752 assert(getTypeNum(i) == VT && "TreePattern has too many types!"); 753 754 VT = getTypeNum(0); 755 if (VT != MVT::iPTR) { 756 unsigned Size = MVT::getSizeInBits(VT); 757 // Make sure that the value is representable for this type. 758 if (Size < 32) { 759 int Val = (II->getValue() << (32-Size)) >> (32-Size); 760 if (Val != II->getValue()) { 761 // If sign-extended doesn't fit, does it fit as unsigned? 762 unsigned ValueMask = unsigned(MVT::getIntVTBitMask(VT)); 763 unsigned UnsignedVal = unsigned(II->getValue()); 764 765 if ((ValueMask & UnsignedVal) != UnsignedVal) { 766 TP.error("Integer value '" + itostr(II->getValue())+ 767 "' is out of range for type '" + 768 getEnumName(getTypeNum(0)) + "'!"); 769 } 770 } 771 } 772 } 773 } 774 775 return MadeChange; 776 } 777 return false; 778 } 779 780 // special handling for set, which isn't really an SDNode. 781 if (getOperator()->getName() == "set") { 782 assert (getNumChildren() >= 2 && "Missing RHS of a set?"); 783 unsigned NC = getNumChildren(); 784 bool MadeChange = false; 785 for (unsigned i = 0; i < NC-1; ++i) { 786 MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 787 MadeChange |= getChild(NC-1)->ApplyTypeConstraints(TP, NotRegisters); 788 789 // Types of operands must match. 790 MadeChange |= getChild(i)->UpdateNodeType(getChild(NC-1)->getExtTypes(), 791 TP); 792 MadeChange |= getChild(NC-1)->UpdateNodeType(getChild(i)->getExtTypes(), 793 TP); 794 MadeChange |= UpdateNodeType(MVT::isVoid, TP); 795 } 796 return MadeChange; 797 } else if (getOperator()->getName() == "implicit" || 798 getOperator()->getName() == "parallel") { 799 bool MadeChange = false; 800 for (unsigned i = 0; i < getNumChildren(); ++i) 801 MadeChange = getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 802 MadeChange |= UpdateNodeType(MVT::isVoid, TP); 803 return MadeChange; 804 } else if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) { 805 bool MadeChange = false; 806 807 // Apply the result type to the node. 808 MadeChange = UpdateNodeType(Int->ArgVTs[0], TP); 809 810 if (getNumChildren() != Int->ArgVTs.size()) 811 TP.error("Intrinsic '" + Int->Name + "' expects " + 812 utostr(Int->ArgVTs.size()-1) + " operands, not " + 813 utostr(getNumChildren()-1) + " operands!"); 814 815 // Apply type info to the intrinsic ID. 816 MadeChange |= getChild(0)->UpdateNodeType(MVT::iPTR, TP); 817 818 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) { 819 MVT::ValueType OpVT = Int->ArgVTs[i]; 820 MadeChange |= getChild(i)->UpdateNodeType(OpVT, TP); 821 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 822 } 823 return MadeChange; 824 } else if (getOperator()->isSubClassOf("SDNode")) { 825 const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator()); 826 827 bool MadeChange = NI.ApplyTypeConstraints(this, TP); 828 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 829 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters); 830 // Branch, etc. do not produce results and top-level forms in instr pattern 831 // must have void types. 832 if (NI.getNumResults() == 0) 833 MadeChange |= UpdateNodeType(MVT::isVoid, TP); 834 835 // If this is a vector_shuffle operation, apply types to the build_vector 836 // operation. The types of the integers don't matter, but this ensures they 837 // won't get checked. 838 if (getOperator()->getName() == "vector_shuffle" && 839 getChild(2)->getOperator()->getName() == "build_vector") { 840 TreePatternNode *BV = getChild(2); 841 const std::vector<MVT::ValueType> &LegalVTs 842 = CDP.getTargetInfo().getLegalValueTypes(); 843 MVT::ValueType LegalIntVT = MVT::Other; 844 for (unsigned i = 0, e = LegalVTs.size(); i != e; ++i) 845 if (MVT::isInteger(LegalVTs[i]) && !MVT::isVector(LegalVTs[i])) { 846 LegalIntVT = LegalVTs[i]; 847 break; 848 } 849 assert(LegalIntVT != MVT::Other && "No legal integer VT?"); 850 851 for (unsigned i = 0, e = BV->getNumChildren(); i != e; ++i) 852 MadeChange |= BV->getChild(i)->UpdateNodeType(LegalIntVT, TP); 853 } 854 return MadeChange; 855 } else if (getOperator()->isSubClassOf("Instruction")) { 856 const DAGInstruction &Inst = CDP.getInstruction(getOperator()); 857 bool MadeChange = false; 858 unsigned NumResults = Inst.getNumResults(); 859 860 assert(NumResults <= 1 && 861 "Only supports zero or one result instrs!"); 862 863 CodeGenInstruction &InstInfo = 864 CDP.getTargetInfo().getInstruction(getOperator()->getName()); 865 // Apply the result type to the node 866 if (NumResults == 0 || InstInfo.NumDefs == 0) { 867 MadeChange = UpdateNodeType(MVT::isVoid, TP); 868 } else { 869 Record *ResultNode = Inst.getResult(0); 870 871 if (ResultNode->getName() == "ptr_rc") { 872 std::vector<unsigned char> VT; 873 VT.push_back(MVT::iPTR); 874 MadeChange = UpdateNodeType(VT, TP); 875 } else if (ResultNode->getName() == "unknown") { 876 std::vector<unsigned char> VT; 877 VT.push_back(MVT::isUnknown); 878 MadeChange = UpdateNodeType(VT, TP); 879 } else { 880 assert(ResultNode->isSubClassOf("RegisterClass") && 881 "Operands should be register classes!"); 882 883 const CodeGenRegisterClass &RC = 884 CDP.getTargetInfo().getRegisterClass(ResultNode); 885 MadeChange = UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP); 886 } 887 } 888 889 unsigned ChildNo = 0; 890 for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) { 891 Record *OperandNode = Inst.getOperand(i); 892 893 // If the instruction expects a predicate or optional def operand, we 894 // codegen this by setting the operand to it's default value if it has a 895 // non-empty DefaultOps field. 896 if ((OperandNode->isSubClassOf("PredicateOperand") || 897 OperandNode->isSubClassOf("OptionalDefOperand")) && 898 !CDP.getDefaultOperand(OperandNode).DefaultOps.empty()) 899 continue; 900 901 // Verify that we didn't run out of provided operands. 902 if (ChildNo >= getNumChildren()) 903 TP.error("Instruction '" + getOperator()->getName() + 904 "' expects more operands than were provided."); 905 906 MVT::ValueType VT; 907 TreePatternNode *Child = getChild(ChildNo++); 908 if (OperandNode->isSubClassOf("RegisterClass")) { 909 const CodeGenRegisterClass &RC = 910 CDP.getTargetInfo().getRegisterClass(OperandNode); 911 MadeChange |= Child->UpdateNodeType(ConvertVTs(RC.getValueTypes()), TP); 912 } else if (OperandNode->isSubClassOf("Operand")) { 913 VT = getValueType(OperandNode->getValueAsDef("Type")); 914 MadeChange |= Child->UpdateNodeType(VT, TP); 915 } else if (OperandNode->getName() == "ptr_rc") { 916 MadeChange |= Child->UpdateNodeType(MVT::iPTR, TP); 917 } else if (OperandNode->getName() == "unknown") { 918 MadeChange |= Child->UpdateNodeType(MVT::isUnknown, TP); 919 } else { 920 assert(0 && "Unknown operand type!"); 921 abort(); 922 } 923 MadeChange |= Child->ApplyTypeConstraints(TP, NotRegisters); 924 } 925 926 if (ChildNo != getNumChildren()) 927 TP.error("Instruction '" + getOperator()->getName() + 928 "' was provided too many operands!"); 929 930 return MadeChange; 931 } else { 932 assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"); 933 934 // Node transforms always take one operand. 935 if (getNumChildren() != 1) 936 TP.error("Node transform '" + getOperator()->getName() + 937 "' requires one operand!"); 938 939 // If either the output or input of the xform does not have exact 940 // type info. We assume they must be the same. Otherwise, it is perfectly 941 // legal to transform from one type to a completely different type. 942 if (!hasTypeSet() || !getChild(0)->hasTypeSet()) { 943 bool MadeChange = UpdateNodeType(getChild(0)->getExtTypes(), TP); 944 MadeChange |= getChild(0)->UpdateNodeType(getExtTypes(), TP); 945 return MadeChange; 946 } 947 return false; 948 } 949} 950 951/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the 952/// RHS of a commutative operation, not the on LHS. 953static bool OnlyOnRHSOfCommutative(TreePatternNode *N) { 954 if (!N->isLeaf() && N->getOperator()->getName() == "imm") 955 return true; 956 if (N->isLeaf() && dynamic_cast<IntInit*>(N->getLeafValue())) 957 return true; 958 return false; 959} 960 961 962/// canPatternMatch - If it is impossible for this pattern to match on this 963/// target, fill in Reason and return false. Otherwise, return true. This is 964/// used as a santity check for .td files (to prevent people from writing stuff 965/// that can never possibly work), and to prevent the pattern permuter from 966/// generating stuff that is useless. 967bool TreePatternNode::canPatternMatch(std::string &Reason, 968 const CodeGenDAGPatterns &CDP) { 969 if (isLeaf()) return true; 970 971 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) 972 if (!getChild(i)->canPatternMatch(Reason, CDP)) 973 return false; 974 975 // If this is an intrinsic, handle cases that would make it not match. For 976 // example, if an operand is required to be an immediate. 977 if (getOperator()->isSubClassOf("Intrinsic")) { 978 // TODO: 979 return true; 980 } 981 982 // If this node is a commutative operator, check that the LHS isn't an 983 // immediate. 984 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator()); 985 if (NodeInfo.hasProperty(SDNPCommutative)) { 986 // Scan all of the operands of the node and make sure that only the last one 987 // is a constant node, unless the RHS also is. 988 if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) { 989 for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) 990 if (OnlyOnRHSOfCommutative(getChild(i))) { 991 Reason="Immediate value must be on the RHS of commutative operators!"; 992 return false; 993 } 994 } 995 } 996 997 return true; 998} 999 1000//===----------------------------------------------------------------------===// 1001// TreePattern implementation 1002// 1003 1004TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput, 1005 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1006 isInputPattern = isInput; 1007 for (unsigned i = 0, e = RawPat->getSize(); i != e; ++i) 1008 Trees.push_back(ParseTreePattern((DagInit*)RawPat->getElement(i))); 1009} 1010 1011TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput, 1012 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1013 isInputPattern = isInput; 1014 Trees.push_back(ParseTreePattern(Pat)); 1015} 1016 1017TreePattern::TreePattern(Record *TheRec, TreePatternNode *Pat, bool isInput, 1018 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp){ 1019 isInputPattern = isInput; 1020 Trees.push_back(Pat); 1021} 1022 1023 1024 1025void TreePattern::error(const std::string &Msg) const { 1026 dump(); 1027 throw "In " + TheRecord->getName() + ": " + Msg; 1028} 1029 1030TreePatternNode *TreePattern::ParseTreePattern(DagInit *Dag) { 1031 DefInit *OpDef = dynamic_cast<DefInit*>(Dag->getOperator()); 1032 if (!OpDef) error("Pattern has unexpected operator type!"); 1033 Record *Operator = OpDef->getDef(); 1034 1035 if (Operator->isSubClassOf("ValueType")) { 1036 // If the operator is a ValueType, then this must be "type cast" of a leaf 1037 // node. 1038 if (Dag->getNumArgs() != 1) 1039 error("Type cast only takes one operand!"); 1040 1041 Init *Arg = Dag->getArg(0); 1042 TreePatternNode *New; 1043 if (DefInit *DI = dynamic_cast<DefInit*>(Arg)) { 1044 Record *R = DI->getDef(); 1045 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { 1046 Dag->setArg(0, new DagInit(DI, 1047 std::vector<std::pair<Init*, std::string> >())); 1048 return ParseTreePattern(Dag); 1049 } 1050 New = new TreePatternNode(DI); 1051 } else if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) { 1052 New = ParseTreePattern(DI); 1053 } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) { 1054 New = new TreePatternNode(II); 1055 if (!Dag->getArgName(0).empty()) 1056 error("Constant int argument should not have a name!"); 1057 } else if (BitsInit *BI = dynamic_cast<BitsInit*>(Arg)) { 1058 // Turn this into an IntInit. 1059 Init *II = BI->convertInitializerTo(new IntRecTy()); 1060 if (II == 0 || !dynamic_cast<IntInit*>(II)) 1061 error("Bits value must be constants!"); 1062 1063 New = new TreePatternNode(dynamic_cast<IntInit*>(II)); 1064 if (!Dag->getArgName(0).empty()) 1065 error("Constant int argument should not have a name!"); 1066 } else { 1067 Arg->dump(); 1068 error("Unknown leaf value for tree pattern!"); 1069 return 0; 1070 } 1071 1072 // Apply the type cast. 1073 New->UpdateNodeType(getValueType(Operator), *this); 1074 New->setName(Dag->getArgName(0)); 1075 return New; 1076 } 1077 1078 // Verify that this is something that makes sense for an operator. 1079 if (!Operator->isSubClassOf("PatFrag") && !Operator->isSubClassOf("SDNode") && 1080 !Operator->isSubClassOf("Instruction") && 1081 !Operator->isSubClassOf("SDNodeXForm") && 1082 !Operator->isSubClassOf("Intrinsic") && 1083 Operator->getName() != "set" && 1084 Operator->getName() != "implicit" && 1085 Operator->getName() != "parallel") 1086 error("Unrecognized node '" + Operator->getName() + "'!"); 1087 1088 // Check to see if this is something that is illegal in an input pattern. 1089 if (isInputPattern && (Operator->isSubClassOf("Instruction") || 1090 Operator->isSubClassOf("SDNodeXForm"))) 1091 error("Cannot use '" + Operator->getName() + "' in an input pattern!"); 1092 1093 std::vector<TreePatternNode*> Children; 1094 1095 for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i) { 1096 Init *Arg = Dag->getArg(i); 1097 if (DagInit *DI = dynamic_cast<DagInit*>(Arg)) { 1098 Children.push_back(ParseTreePattern(DI)); 1099 if (Children.back()->getName().empty()) 1100 Children.back()->setName(Dag->getArgName(i)); 1101 } else if (DefInit *DefI = dynamic_cast<DefInit*>(Arg)) { 1102 Record *R = DefI->getDef(); 1103 // Direct reference to a leaf DagNode or PatFrag? Turn it into a 1104 // TreePatternNode if its own. 1105 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrag")) { 1106 Dag->setArg(i, new DagInit(DefI, 1107 std::vector<std::pair<Init*, std::string> >())); 1108 --i; // Revisit this node... 1109 } else { 1110 TreePatternNode *Node = new TreePatternNode(DefI); 1111 Node->setName(Dag->getArgName(i)); 1112 Children.push_back(Node); 1113 1114 // Input argument? 1115 if (R->getName() == "node") { 1116 if (Dag->getArgName(i).empty()) 1117 error("'node' argument requires a name to match with operand list"); 1118 Args.push_back(Dag->getArgName(i)); 1119 } 1120 } 1121 } else if (IntInit *II = dynamic_cast<IntInit*>(Arg)) { 1122 TreePatternNode *Node = new TreePatternNode(II); 1123 if (!Dag->getArgName(i).empty()) 1124 error("Constant int argument should not have a name!"); 1125 Children.push_back(Node); 1126 } else if (BitsInit *BI = dynamic_cast<BitsInit*>(Arg)) { 1127 // Turn this into an IntInit. 1128 Init *II = BI->convertInitializerTo(new IntRecTy()); 1129 if (II == 0 || !dynamic_cast<IntInit*>(II)) 1130 error("Bits value must be constants!"); 1131 1132 TreePatternNode *Node = new TreePatternNode(dynamic_cast<IntInit*>(II)); 1133 if (!Dag->getArgName(i).empty()) 1134 error("Constant int argument should not have a name!"); 1135 Children.push_back(Node); 1136 } else { 1137 cerr << '"'; 1138 Arg->dump(); 1139 cerr << "\": "; 1140 error("Unknown leaf value for tree pattern!"); 1141 } 1142 } 1143 1144 // If the operator is an intrinsic, then this is just syntactic sugar for for 1145 // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and 1146 // convert the intrinsic name to a number. 1147 if (Operator->isSubClassOf("Intrinsic")) { 1148 const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator); 1149 unsigned IID = getDAGPatterns().getIntrinsicID(Operator)+1; 1150 1151 // If this intrinsic returns void, it must have side-effects and thus a 1152 // chain. 1153 if (Int.ArgVTs[0] == MVT::isVoid) { 1154 Operator = getDAGPatterns().get_intrinsic_void_sdnode(); 1155 } else if (Int.ModRef != CodeGenIntrinsic::NoMem) { 1156 // Has side-effects, requires chain. 1157 Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode(); 1158 } else { 1159 // Otherwise, no chain. 1160 Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode(); 1161 } 1162 1163 TreePatternNode *IIDNode = new TreePatternNode(new IntInit(IID)); 1164 Children.insert(Children.begin(), IIDNode); 1165 } 1166 1167 return new TreePatternNode(Operator, Children); 1168} 1169 1170/// InferAllTypes - Infer/propagate as many types throughout the expression 1171/// patterns as possible. Return true if all types are infered, false 1172/// otherwise. Throw an exception if a type contradiction is found. 1173bool TreePattern::InferAllTypes() { 1174 bool MadeChange = true; 1175 while (MadeChange) { 1176 MadeChange = false; 1177 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1178 MadeChange |= Trees[i]->ApplyTypeConstraints(*this, false); 1179 } 1180 1181 bool HasUnresolvedTypes = false; 1182 for (unsigned i = 0, e = Trees.size(); i != e; ++i) 1183 HasUnresolvedTypes |= Trees[i]->ContainsUnresolvedType(); 1184 return !HasUnresolvedTypes; 1185} 1186 1187void TreePattern::print(std::ostream &OS) const { 1188 OS << getRecord()->getName(); 1189 if (!Args.empty()) { 1190 OS << "(" << Args[0]; 1191 for (unsigned i = 1, e = Args.size(); i != e; ++i) 1192 OS << ", " << Args[i]; 1193 OS << ")"; 1194 } 1195 OS << ": "; 1196 1197 if (Trees.size() > 1) 1198 OS << "[\n"; 1199 for (unsigned i = 0, e = Trees.size(); i != e; ++i) { 1200 OS << "\t"; 1201 Trees[i]->print(OS); 1202 OS << "\n"; 1203 } 1204 1205 if (Trees.size() > 1) 1206 OS << "]\n"; 1207} 1208 1209void TreePattern::dump() const { print(*cerr.stream()); } 1210 1211//===----------------------------------------------------------------------===// 1212// CodeGenDAGPatterns implementation 1213// 1214 1215// FIXME: REMOVE OSTREAM ARGUMENT 1216CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R) : Records(R) { 1217 Intrinsics = LoadIntrinsics(Records); 1218 ParseNodeInfo(); 1219 ParseNodeTransforms(); 1220 ParseComplexPatterns(); 1221 ParsePatternFragments(); 1222 ParseDefaultOperands(); 1223 ParseInstructions(); 1224 ParsePatterns(); 1225 1226 // Generate variants. For example, commutative patterns can match 1227 // multiple ways. Add them to PatternsToMatch as well. 1228 GenerateVariants(); 1229 1230 // Infer instruction flags. For example, we can detect loads, 1231 // stores, and side effects in many cases by examining an 1232 // instruction's pattern. 1233 InferInstructionFlags(); 1234} 1235 1236CodeGenDAGPatterns::~CodeGenDAGPatterns() { 1237 for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(), 1238 E = PatternFragments.end(); I != E; ++I) 1239 delete I->second; 1240} 1241 1242 1243Record *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const { 1244 Record *N = Records.getDef(Name); 1245 if (!N || !N->isSubClassOf("SDNode")) { 1246 cerr << "Error getting SDNode '" << Name << "'!\n"; 1247 exit(1); 1248 } 1249 return N; 1250} 1251 1252// Parse all of the SDNode definitions for the target, populating SDNodes. 1253void CodeGenDAGPatterns::ParseNodeInfo() { 1254 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode"); 1255 while (!Nodes.empty()) { 1256 SDNodes.insert(std::make_pair(Nodes.back(), Nodes.back())); 1257 Nodes.pop_back(); 1258 } 1259 1260 // Get the buildin intrinsic nodes. 1261 intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void"); 1262 intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain"); 1263 intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain"); 1264} 1265 1266/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms 1267/// map, and emit them to the file as functions. 1268void CodeGenDAGPatterns::ParseNodeTransforms() { 1269 std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm"); 1270 while (!Xforms.empty()) { 1271 Record *XFormNode = Xforms.back(); 1272 Record *SDNode = XFormNode->getValueAsDef("Opcode"); 1273 std::string Code = XFormNode->getValueAsCode("XFormFunction"); 1274 SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code))); 1275 1276 Xforms.pop_back(); 1277 } 1278} 1279 1280void CodeGenDAGPatterns::ParseComplexPatterns() { 1281 std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern"); 1282 while (!AMs.empty()) { 1283 ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back())); 1284 AMs.pop_back(); 1285 } 1286} 1287 1288 1289/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td 1290/// file, building up the PatternFragments map. After we've collected them all, 1291/// inline fragments together as necessary, so that there are no references left 1292/// inside a pattern fragment to a pattern fragment. 1293/// 1294void CodeGenDAGPatterns::ParsePatternFragments() { 1295 std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrag"); 1296 1297 // First step, parse all of the fragments. 1298 for (unsigned i = 0, e = Fragments.size(); i != e; ++i) { 1299 DagInit *Tree = Fragments[i]->getValueAsDag("Fragment"); 1300 TreePattern *P = new TreePattern(Fragments[i], Tree, true, *this); 1301 PatternFragments[Fragments[i]] = P; 1302 1303 // Validate the argument list, converting it to set, to discard duplicates. 1304 std::vector<std::string> &Args = P->getArgList(); 1305 std::set<std::string> OperandsSet(Args.begin(), Args.end()); 1306 1307 if (OperandsSet.count("")) 1308 P->error("Cannot have unnamed 'node' values in pattern fragment!"); 1309 1310 // Parse the operands list. 1311 DagInit *OpsList = Fragments[i]->getValueAsDag("Operands"); 1312 DefInit *OpsOp = dynamic_cast<DefInit*>(OpsList->getOperator()); 1313 // Special cases: ops == outs == ins. Different names are used to 1314 // improve readibility. 1315 if (!OpsOp || 1316 (OpsOp->getDef()->getName() != "ops" && 1317 OpsOp->getDef()->getName() != "outs" && 1318 OpsOp->getDef()->getName() != "ins")) 1319 P->error("Operands list should start with '(ops ... '!"); 1320 1321 // Copy over the arguments. 1322 Args.clear(); 1323 for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) { 1324 if (!dynamic_cast<DefInit*>(OpsList->getArg(j)) || 1325 static_cast<DefInit*>(OpsList->getArg(j))-> 1326 getDef()->getName() != "node") 1327 P->error("Operands list should all be 'node' values."); 1328 if (OpsList->getArgName(j).empty()) 1329 P->error("Operands list should have names for each operand!"); 1330 if (!OperandsSet.count(OpsList->getArgName(j))) 1331 P->error("'" + OpsList->getArgName(j) + 1332 "' does not occur in pattern or was multiply specified!"); 1333 OperandsSet.erase(OpsList->getArgName(j)); 1334 Args.push_back(OpsList->getArgName(j)); 1335 } 1336 1337 if (!OperandsSet.empty()) 1338 P->error("Operands list does not contain an entry for operand '" + 1339 *OperandsSet.begin() + "'!"); 1340 1341 // If there is a code init for this fragment, keep track of the fact that 1342 // this fragment uses it. 1343 std::string Code = Fragments[i]->getValueAsCode("Predicate"); 1344 if (!Code.empty()) 1345 P->getOnlyTree()->setPredicateFn("Predicate_"+Fragments[i]->getName()); 1346 1347 // If there is a node transformation corresponding to this, keep track of 1348 // it. 1349 Record *Transform = Fragments[i]->getValueAsDef("OperandTransform"); 1350 if (!getSDNodeTransform(Transform).second.empty()) // not noop xform? 1351 P->getOnlyTree()->setTransformFn(Transform); 1352 } 1353 1354 // Now that we've parsed all of the tree fragments, do a closure on them so 1355 // that there are not references to PatFrags left inside of them. 1356 for (std::map<Record*, TreePattern*>::iterator I = PatternFragments.begin(), 1357 E = PatternFragments.end(); I != E; ++I) { 1358 TreePattern *ThePat = I->second; 1359 ThePat->InlinePatternFragments(); 1360 1361 // Infer as many types as possible. Don't worry about it if we don't infer 1362 // all of them, some may depend on the inputs of the pattern. 1363 try { 1364 ThePat->InferAllTypes(); 1365 } catch (...) { 1366 // If this pattern fragment is not supported by this target (no types can 1367 // satisfy its constraints), just ignore it. If the bogus pattern is 1368 // actually used by instructions, the type consistency error will be 1369 // reported there. 1370 } 1371 1372 // If debugging, print out the pattern fragment result. 1373 DEBUG(ThePat->dump()); 1374 } 1375} 1376 1377void CodeGenDAGPatterns::ParseDefaultOperands() { 1378 std::vector<Record*> DefaultOps[2]; 1379 DefaultOps[0] = Records.getAllDerivedDefinitions("PredicateOperand"); 1380 DefaultOps[1] = Records.getAllDerivedDefinitions("OptionalDefOperand"); 1381 1382 // Find some SDNode. 1383 assert(!SDNodes.empty() && "No SDNodes parsed?"); 1384 Init *SomeSDNode = new DefInit(SDNodes.begin()->first); 1385 1386 for (unsigned iter = 0; iter != 2; ++iter) { 1387 for (unsigned i = 0, e = DefaultOps[iter].size(); i != e; ++i) { 1388 DagInit *DefaultInfo = DefaultOps[iter][i]->getValueAsDag("DefaultOps"); 1389 1390 // Clone the DefaultInfo dag node, changing the operator from 'ops' to 1391 // SomeSDnode so that we can parse this. 1392 std::vector<std::pair<Init*, std::string> > Ops; 1393 for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op) 1394 Ops.push_back(std::make_pair(DefaultInfo->getArg(op), 1395 DefaultInfo->getArgName(op))); 1396 DagInit *DI = new DagInit(SomeSDNode, Ops); 1397 1398 // Create a TreePattern to parse this. 1399 TreePattern P(DefaultOps[iter][i], DI, false, *this); 1400 assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!"); 1401 1402 // Copy the operands over into a DAGDefaultOperand. 1403 DAGDefaultOperand DefaultOpInfo; 1404 1405 TreePatternNode *T = P.getTree(0); 1406 for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) { 1407 TreePatternNode *TPN = T->getChild(op); 1408 while (TPN->ApplyTypeConstraints(P, false)) 1409 /* Resolve all types */; 1410 1411 if (TPN->ContainsUnresolvedType()) { 1412 if (iter == 0) 1413 throw "Value #" + utostr(i) + " of PredicateOperand '" + 1414 DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!"; 1415 else 1416 throw "Value #" + utostr(i) + " of OptionalDefOperand '" + 1417 DefaultOps[iter][i]->getName() + "' doesn't have a concrete type!"; 1418 } 1419 DefaultOpInfo.DefaultOps.push_back(TPN); 1420 } 1421 1422 // Insert it into the DefaultOperands map so we can find it later. 1423 DefaultOperands[DefaultOps[iter][i]] = DefaultOpInfo; 1424 } 1425 } 1426} 1427 1428/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an 1429/// instruction input. Return true if this is a real use. 1430static bool HandleUse(TreePattern *I, TreePatternNode *Pat, 1431 std::map<std::string, TreePatternNode*> &InstInputs, 1432 std::vector<Record*> &InstImpInputs) { 1433 // No name -> not interesting. 1434 if (Pat->getName().empty()) { 1435 if (Pat->isLeaf()) { 1436 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 1437 if (DI && DI->getDef()->isSubClassOf("RegisterClass")) 1438 I->error("Input " + DI->getDef()->getName() + " must be named!"); 1439 else if (DI && DI->getDef()->isSubClassOf("Register")) 1440 InstImpInputs.push_back(DI->getDef()); 1441 ; 1442 } 1443 return false; 1444 } 1445 1446 Record *Rec; 1447 if (Pat->isLeaf()) { 1448 DefInit *DI = dynamic_cast<DefInit*>(Pat->getLeafValue()); 1449 if (!DI) I->error("Input $" + Pat->getName() + " must be an identifier!"); 1450 Rec = DI->getDef(); 1451 } else { 1452 assert(Pat->getNumChildren() == 0 && "can't be a use with children!"); 1453 Rec = Pat->getOperator(); 1454 } 1455 1456 // SRCVALUE nodes are ignored. 1457 if (Rec->getName() == "srcvalue") 1458 return false; 1459 1460 TreePatternNode *&Slot = InstInputs[Pat->getName()]; 1461 if (!Slot) { 1462 Slot = Pat; 1463 } else { 1464 Record *SlotRec; 1465 if (Slot->isLeaf()) { 1466 SlotRec = dynamic_cast<DefInit*>(Slot->getLeafValue())->getDef(); 1467 } else { 1468 assert(Slot->getNumChildren() == 0 && "can't be a use with children!"); 1469 SlotRec = Slot->getOperator(); 1470 } 1471 1472 // Ensure that the inputs agree if we've already seen this input. 1473 if (Rec != SlotRec) 1474 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 1475 if (Slot->getExtTypes() != Pat->getExtTypes()) 1476 I->error("All $" + Pat->getName() + " inputs must agree with each other"); 1477 } 1478 return true; 1479} 1480 1481/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is 1482/// part of "I", the instruction), computing the set of inputs and outputs of 1483/// the pattern. Report errors if we see anything naughty. 1484void CodeGenDAGPatterns:: 1485FindPatternInputsAndOutputs(TreePattern *I, TreePatternNode *Pat, 1486 std::map<std::string, TreePatternNode*> &InstInputs, 1487 std::map<std::string, TreePatternNode*>&InstResults, 1488 std::vector<Record*> &InstImpInputs, 1489 std::vector<Record*> &InstImpResults) { 1490 if (Pat->isLeaf()) { 1491 bool isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); 1492 if (!isUse && Pat->getTransformFn()) 1493 I->error("Cannot specify a transform function for a non-input value!"); 1494 return; 1495 } else if (Pat->getOperator()->getName() == "implicit") { 1496 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 1497 TreePatternNode *Dest = Pat->getChild(i); 1498 if (!Dest->isLeaf()) 1499 I->error("implicitly defined value should be a register!"); 1500 1501 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue()); 1502 if (!Val || !Val->getDef()->isSubClassOf("Register")) 1503 I->error("implicitly defined value should be a register!"); 1504 InstImpResults.push_back(Val->getDef()); 1505 } 1506 return; 1507 } else if (Pat->getOperator()->getName() != "set") { 1508 // If this is not a set, verify that the children nodes are not void typed, 1509 // and recurse. 1510 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) { 1511 if (Pat->getChild(i)->getExtTypeNum(0) == MVT::isVoid) 1512 I->error("Cannot have void nodes inside of patterns!"); 1513 FindPatternInputsAndOutputs(I, Pat->getChild(i), InstInputs, InstResults, 1514 InstImpInputs, InstImpResults); 1515 } 1516 1517 // If this is a non-leaf node with no children, treat it basically as if 1518 // it were a leaf. This handles nodes like (imm). 1519 bool isUse = false; 1520 if (Pat->getNumChildren() == 0) 1521 isUse = HandleUse(I, Pat, InstInputs, InstImpInputs); 1522 1523 if (!isUse && Pat->getTransformFn()) 1524 I->error("Cannot specify a transform function for a non-input value!"); 1525 return; 1526 } 1527 1528 // Otherwise, this is a set, validate and collect instruction results. 1529 if (Pat->getNumChildren() == 0) 1530 I->error("set requires operands!"); 1531 1532 if (Pat->getTransformFn()) 1533 I->error("Cannot specify a transform function on a set node!"); 1534 1535 // Check the set destinations. 1536 unsigned NumDests = Pat->getNumChildren()-1; 1537 for (unsigned i = 0; i != NumDests; ++i) { 1538 TreePatternNode *Dest = Pat->getChild(i); 1539 if (!Dest->isLeaf()) 1540 I->error("set destination should be a register!"); 1541 1542 DefInit *Val = dynamic_cast<DefInit*>(Dest->getLeafValue()); 1543 if (!Val) 1544 I->error("set destination should be a register!"); 1545 1546 if (Val->getDef()->isSubClassOf("RegisterClass") || 1547 Val->getDef()->getName() == "ptr_rc") { 1548 if (Dest->getName().empty()) 1549 I->error("set destination must have a name!"); 1550 if (InstResults.count(Dest->getName())) 1551 I->error("cannot set '" + Dest->getName() +"' multiple times"); 1552 InstResults[Dest->getName()] = Dest; 1553 } else if (Val->getDef()->isSubClassOf("Register")) { 1554 InstImpResults.push_back(Val->getDef()); 1555 } else { 1556 I->error("set destination should be a register!"); 1557 } 1558 } 1559 1560 // Verify and collect info from the computation. 1561 FindPatternInputsAndOutputs(I, Pat->getChild(NumDests), 1562 InstInputs, InstResults, 1563 InstImpInputs, InstImpResults); 1564} 1565 1566//===----------------------------------------------------------------------===// 1567// Instruction Analysis 1568//===----------------------------------------------------------------------===// 1569 1570class InstAnalyzer { 1571 const CodeGenDAGPatterns &CDP; 1572 bool &mayStore; 1573 bool &mayLoad; 1574 bool &HasSideEffects; 1575public: 1576 InstAnalyzer(const CodeGenDAGPatterns &cdp, 1577 bool &maystore, bool &mayload, bool &hse) 1578 : CDP(cdp), mayStore(maystore), mayLoad(mayload), HasSideEffects(hse){ 1579 } 1580 1581 /// Analyze - Analyze the specified instruction, returning true if the 1582 /// instruction had a pattern. 1583 bool Analyze(Record *InstRecord) { 1584 const TreePattern *Pattern = CDP.getInstruction(InstRecord).getPattern(); 1585 if (Pattern == 0) { 1586 HasSideEffects = 1; 1587 return false; // No pattern. 1588 } 1589 1590 // FIXME: Assume only the first tree is the pattern. The others are clobber 1591 // nodes. 1592 AnalyzeNode(Pattern->getTree(0)); 1593 return true; 1594 } 1595 1596private: 1597 void AnalyzeNode(const TreePatternNode *N) { 1598 if (N->isLeaf()) { 1599 if (DefInit *DI = dynamic_cast<DefInit*>(N->getLeafValue())) { 1600 Record *LeafRec = DI->getDef(); 1601 // Handle ComplexPattern leaves. 1602 if (LeafRec->isSubClassOf("ComplexPattern")) { 1603 const ComplexPattern &CP = CDP.getComplexPattern(LeafRec); 1604 if (CP.hasProperty(SDNPMayStore)) mayStore = true; 1605 if (CP.hasProperty(SDNPMayLoad)) mayLoad = true; 1606 if (CP.hasProperty(SDNPSideEffect)) HasSideEffects = true; 1607 } 1608 } 1609 return; 1610 } 1611 1612 // Analyze children. 1613 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 1614 AnalyzeNode(N->getChild(i)); 1615 1616 // Ignore set nodes, which are not SDNodes. 1617 if (N->getOperator()->getName() == "set") 1618 return; 1619 1620 // Get information about the SDNode for the operator. 1621 const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator()); 1622 1623 // Notice properties of the node. 1624 if (OpInfo.hasProperty(SDNPMayStore)) mayStore = true; 1625 if (OpInfo.hasProperty(SDNPMayLoad)) mayLoad = true; 1626 if (OpInfo.hasProperty(SDNPSideEffect)) HasSideEffects = true; 1627 1628 if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) { 1629 // If this is an intrinsic, analyze it. 1630 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadArgMem) 1631 mayLoad = true;// These may load memory. 1632 1633 if (IntInfo->ModRef >= CodeGenIntrinsic::WriteArgMem) 1634 mayStore = true;// Intrinsics that can write to memory are 'mayStore'. 1635 1636 if (IntInfo->ModRef >= CodeGenIntrinsic::WriteMem) 1637 // WriteMem intrinsics can have other strange effects. 1638 HasSideEffects = true; 1639 } 1640 } 1641 1642}; 1643 1644static void InferFromPattern(const CodeGenInstruction &Inst, 1645 bool &MayStore, bool &MayLoad, 1646 bool &HasSideEffects, 1647 const CodeGenDAGPatterns &CDP) { 1648 MayStore = MayLoad = HasSideEffects = false; 1649 1650 bool HadPattern = 1651 InstAnalyzer(CDP, MayStore, MayLoad, HasSideEffects).Analyze(Inst.TheDef); 1652 1653 // InstAnalyzer only correctly analyzes mayStore/mayLoad so far. 1654 if (Inst.mayStore) { // If the .td file explicitly sets mayStore, use it. 1655 // If we decided that this is a store from the pattern, then the .td file 1656 // entry is redundant. 1657 if (MayStore) 1658 fprintf(stderr, 1659 "Warning: mayStore flag explicitly set on instruction '%s'" 1660 " but flag already inferred from pattern.\n", 1661 Inst.TheDef->getName().c_str()); 1662 MayStore = true; 1663 } 1664 1665 if (Inst.mayLoad) { // If the .td file explicitly sets mayLoad, use it. 1666 // If we decided that this is a load from the pattern, then the .td file 1667 // entry is redundant. 1668 if (MayLoad) 1669 fprintf(stderr, 1670 "Warning: mayLoad flag explicitly set on instruction '%s'" 1671 " but flag already inferred from pattern.\n", 1672 Inst.TheDef->getName().c_str()); 1673 MayLoad = true; 1674 } 1675 1676 if (Inst.neverHasSideEffects) { 1677 if (HadPattern) 1678 fprintf(stderr, "Warning: neverHasSideEffects set on instruction '%s' " 1679 "which already has a pattern\n", Inst.TheDef->getName().c_str()); 1680 HasSideEffects = false; 1681 } 1682 1683 if (Inst.hasSideEffects) { 1684 if (HasSideEffects) 1685 fprintf(stderr, "Warning: hasSideEffects set on instruction '%s' " 1686 "which already inferred this.\n", Inst.TheDef->getName().c_str()); 1687 HasSideEffects = true; 1688 } 1689} 1690 1691/// ParseInstructions - Parse all of the instructions, inlining and resolving 1692/// any fragments involved. This populates the Instructions list with fully 1693/// resolved instructions. 1694void CodeGenDAGPatterns::ParseInstructions() { 1695 std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction"); 1696 1697 for (unsigned i = 0, e = Instrs.size(); i != e; ++i) { 1698 ListInit *LI = 0; 1699 1700 if (dynamic_cast<ListInit*>(Instrs[i]->getValueInit("Pattern"))) 1701 LI = Instrs[i]->getValueAsListInit("Pattern"); 1702 1703 // If there is no pattern, only collect minimal information about the 1704 // instruction for its operand list. We have to assume that there is one 1705 // result, as we have no detailed info. 1706 if (!LI || LI->getSize() == 0) { 1707 std::vector<Record*> Results; 1708 std::vector<Record*> Operands; 1709 1710 CodeGenInstruction &InstInfo =Target.getInstruction(Instrs[i]->getName()); 1711 1712 if (InstInfo.OperandList.size() != 0) { 1713 if (InstInfo.NumDefs == 0) { 1714 // These produce no results 1715 for (unsigned j = 0, e = InstInfo.OperandList.size(); j < e; ++j) 1716 Operands.push_back(InstInfo.OperandList[j].Rec); 1717 } else { 1718 // Assume the first operand is the result. 1719 Results.push_back(InstInfo.OperandList[0].Rec); 1720 1721 // The rest are inputs. 1722 for (unsigned j = 1, e = InstInfo.OperandList.size(); j < e; ++j) 1723 Operands.push_back(InstInfo.OperandList[j].Rec); 1724 } 1725 } 1726 1727 // Create and insert the instruction. 1728 std::vector<Record*> ImpResults; 1729 std::vector<Record*> ImpOperands; 1730 Instructions.insert(std::make_pair(Instrs[i], 1731 DAGInstruction(0, Results, Operands, ImpResults, 1732 ImpOperands))); 1733 continue; // no pattern. 1734 } 1735 1736 // Parse the instruction. 1737 TreePattern *I = new TreePattern(Instrs[i], LI, true, *this); 1738 // Inline pattern fragments into it. 1739 I->InlinePatternFragments(); 1740 1741 // Infer as many types as possible. If we cannot infer all of them, we can 1742 // never do anything with this instruction pattern: report it to the user. 1743 if (!I->InferAllTypes()) 1744 I->error("Could not infer all types in pattern!"); 1745 1746 // InstInputs - Keep track of all of the inputs of the instruction, along 1747 // with the record they are declared as. 1748 std::map<std::string, TreePatternNode*> InstInputs; 1749 1750 // InstResults - Keep track of all the virtual registers that are 'set' 1751 // in the instruction, including what reg class they are. 1752 std::map<std::string, TreePatternNode*> InstResults; 1753 1754 std::vector<Record*> InstImpInputs; 1755 std::vector<Record*> InstImpResults; 1756 1757 // Verify that the top-level forms in the instruction are of void type, and 1758 // fill in the InstResults map. 1759 for (unsigned j = 0, e = I->getNumTrees(); j != e; ++j) { 1760 TreePatternNode *Pat = I->getTree(j); 1761 if (Pat->getExtTypeNum(0) != MVT::isVoid) 1762 I->error("Top-level forms in instruction pattern should have" 1763 " void types"); 1764 1765 // Find inputs and outputs, and verify the structure of the uses/defs. 1766 FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults, 1767 InstImpInputs, InstImpResults); 1768 } 1769 1770 // Now that we have inputs and outputs of the pattern, inspect the operands 1771 // list for the instruction. This determines the order that operands are 1772 // added to the machine instruction the node corresponds to. 1773 unsigned NumResults = InstResults.size(); 1774 1775 // Parse the operands list from the (ops) list, validating it. 1776 assert(I->getArgList().empty() && "Args list should still be empty here!"); 1777 CodeGenInstruction &CGI = Target.getInstruction(Instrs[i]->getName()); 1778 1779 // Check that all of the results occur first in the list. 1780 std::vector<Record*> Results; 1781 TreePatternNode *Res0Node = NULL; 1782 for (unsigned i = 0; i != NumResults; ++i) { 1783 if (i == CGI.OperandList.size()) 1784 I->error("'" + InstResults.begin()->first + 1785 "' set but does not appear in operand list!"); 1786 const std::string &OpName = CGI.OperandList[i].Name; 1787 1788 // Check that it exists in InstResults. 1789 TreePatternNode *RNode = InstResults[OpName]; 1790 if (RNode == 0) 1791 I->error("Operand $" + OpName + " does not exist in operand list!"); 1792 1793 if (i == 0) 1794 Res0Node = RNode; 1795 Record *R = dynamic_cast<DefInit*>(RNode->getLeafValue())->getDef(); 1796 if (R == 0) 1797 I->error("Operand $" + OpName + " should be a set destination: all " 1798 "outputs must occur before inputs in operand list!"); 1799 1800 if (CGI.OperandList[i].Rec != R) 1801 I->error("Operand $" + OpName + " class mismatch!"); 1802 1803 // Remember the return type. 1804 Results.push_back(CGI.OperandList[i].Rec); 1805 1806 // Okay, this one checks out. 1807 InstResults.erase(OpName); 1808 } 1809 1810 // Loop over the inputs next. Make a copy of InstInputs so we can destroy 1811 // the copy while we're checking the inputs. 1812 std::map<std::string, TreePatternNode*> InstInputsCheck(InstInputs); 1813 1814 std::vector<TreePatternNode*> ResultNodeOperands; 1815 std::vector<Record*> Operands; 1816 for (unsigned i = NumResults, e = CGI.OperandList.size(); i != e; ++i) { 1817 CodeGenInstruction::OperandInfo &Op = CGI.OperandList[i]; 1818 const std::string &OpName = Op.Name; 1819 if (OpName.empty()) 1820 I->error("Operand #" + utostr(i) + " in operands list has no name!"); 1821 1822 if (!InstInputsCheck.count(OpName)) { 1823 // If this is an predicate operand or optional def operand with an 1824 // DefaultOps set filled in, we can ignore this. When we codegen it, 1825 // we will do so as always executed. 1826 if (Op.Rec->isSubClassOf("PredicateOperand") || 1827 Op.Rec->isSubClassOf("OptionalDefOperand")) { 1828 // Does it have a non-empty DefaultOps field? If so, ignore this 1829 // operand. 1830 if (!getDefaultOperand(Op.Rec).DefaultOps.empty()) 1831 continue; 1832 } 1833 I->error("Operand $" + OpName + 1834 " does not appear in the instruction pattern"); 1835 } 1836 TreePatternNode *InVal = InstInputsCheck[OpName]; 1837 InstInputsCheck.erase(OpName); // It occurred, remove from map. 1838 1839 if (InVal->isLeaf() && 1840 dynamic_cast<DefInit*>(InVal->getLeafValue())) { 1841 Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef(); 1842 if (Op.Rec != InRec && !InRec->isSubClassOf("ComplexPattern")) 1843 I->error("Operand $" + OpName + "'s register class disagrees" 1844 " between the operand and pattern"); 1845 } 1846 Operands.push_back(Op.Rec); 1847 1848 // Construct the result for the dest-pattern operand list. 1849 TreePatternNode *OpNode = InVal->clone(); 1850 1851 // No predicate is useful on the result. 1852 OpNode->setPredicateFn(""); 1853 1854 // Promote the xform function to be an explicit node if set. 1855 if (Record *Xform = OpNode->getTransformFn()) { 1856 OpNode->setTransformFn(0); 1857 std::vector<TreePatternNode*> Children; 1858 Children.push_back(OpNode); 1859 OpNode = new TreePatternNode(Xform, Children); 1860 } 1861 1862 ResultNodeOperands.push_back(OpNode); 1863 } 1864 1865 if (!InstInputsCheck.empty()) 1866 I->error("Input operand $" + InstInputsCheck.begin()->first + 1867 " occurs in pattern but not in operands list!"); 1868 1869 TreePatternNode *ResultPattern = 1870 new TreePatternNode(I->getRecord(), ResultNodeOperands); 1871 // Copy fully inferred output node type to instruction result pattern. 1872 if (NumResults > 0) 1873 ResultPattern->setTypes(Res0Node->getExtTypes()); 1874 1875 // Create and insert the instruction. 1876 // FIXME: InstImpResults and InstImpInputs should not be part of 1877 // DAGInstruction. 1878 DAGInstruction TheInst(I, Results, Operands, InstImpResults, InstImpInputs); 1879 Instructions.insert(std::make_pair(I->getRecord(), TheInst)); 1880 1881 // Use a temporary tree pattern to infer all types and make sure that the 1882 // constructed result is correct. This depends on the instruction already 1883 // being inserted into the Instructions map. 1884 TreePattern Temp(I->getRecord(), ResultPattern, false, *this); 1885 Temp.InferAllTypes(); 1886 1887 DAGInstruction &TheInsertedInst = Instructions.find(I->getRecord())->second; 1888 TheInsertedInst.setResultPattern(Temp.getOnlyTree()); 1889 1890 DEBUG(I->dump()); 1891 } 1892 1893 // If we can, convert the instructions to be patterns that are matched! 1894 for (std::map<Record*, DAGInstruction>::iterator II = Instructions.begin(), 1895 E = Instructions.end(); II != E; ++II) { 1896 DAGInstruction &TheInst = II->second; 1897 const TreePattern *I = TheInst.getPattern(); 1898 if (I == 0) continue; // No pattern. 1899 1900 // FIXME: Assume only the first tree is the pattern. The others are clobber 1901 // nodes. 1902 TreePatternNode *Pattern = I->getTree(0); 1903 TreePatternNode *SrcPattern; 1904 if (Pattern->getOperator()->getName() == "set") { 1905 SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone(); 1906 } else{ 1907 // Not a set (store or something?) 1908 SrcPattern = Pattern; 1909 } 1910 1911 std::string Reason; 1912 if (!SrcPattern->canPatternMatch(Reason, *this)) 1913 I->error("Instruction can never match: " + Reason); 1914 1915 Record *Instr = II->first; 1916 TreePatternNode *DstPattern = TheInst.getResultPattern(); 1917 PatternsToMatch. 1918 push_back(PatternToMatch(Instr->getValueAsListInit("Predicates"), 1919 SrcPattern, DstPattern, TheInst.getImpResults(), 1920 Instr->getValueAsInt("AddedComplexity"))); 1921 } 1922} 1923 1924 1925void CodeGenDAGPatterns::InferInstructionFlags() { 1926 std::map<std::string, CodeGenInstruction> &InstrDescs = 1927 Target.getInstructions(); 1928 for (std::map<std::string, CodeGenInstruction>::iterator 1929 II = InstrDescs.begin(), E = InstrDescs.end(); II != E; ++II) { 1930 CodeGenInstruction &InstInfo = II->second; 1931 // Determine properties of the instruction from its pattern. 1932 bool MayStore, MayLoad, HasSideEffects; 1933 InferFromPattern(InstInfo, MayStore, MayLoad, HasSideEffects, *this); 1934 InstInfo.mayStore = MayStore; 1935 InstInfo.mayLoad = MayLoad; 1936 InstInfo.hasSideEffects = HasSideEffects; 1937 } 1938} 1939 1940void CodeGenDAGPatterns::ParsePatterns() { 1941 std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern"); 1942 1943 for (unsigned i = 0, e = Patterns.size(); i != e; ++i) { 1944 DagInit *Tree = Patterns[i]->getValueAsDag("PatternToMatch"); 1945 DefInit *OpDef = dynamic_cast<DefInit*>(Tree->getOperator()); 1946 Record *Operator = OpDef->getDef(); 1947 TreePattern *Pattern; 1948 if (Operator->getName() != "parallel") 1949 Pattern = new TreePattern(Patterns[i], Tree, true, *this); 1950 else { 1951 std::vector<Init*> Values; 1952 for (unsigned j = 0, ee = Tree->getNumArgs(); j != ee; ++j) 1953 Values.push_back(Tree->getArg(j)); 1954 ListInit *LI = new ListInit(Values); 1955 Pattern = new TreePattern(Patterns[i], LI, true, *this); 1956 } 1957 1958 // Inline pattern fragments into it. 1959 Pattern->InlinePatternFragments(); 1960 1961 ListInit *LI = Patterns[i]->getValueAsListInit("ResultInstrs"); 1962 if (LI->getSize() == 0) continue; // no pattern. 1963 1964 // Parse the instruction. 1965 TreePattern *Result = new TreePattern(Patterns[i], LI, false, *this); 1966 1967 // Inline pattern fragments into it. 1968 Result->InlinePatternFragments(); 1969 1970 if (Result->getNumTrees() != 1) 1971 Result->error("Cannot handle instructions producing instructions " 1972 "with temporaries yet!"); 1973 1974 bool IterateInference; 1975 bool InferredAllPatternTypes, InferredAllResultTypes; 1976 do { 1977 // Infer as many types as possible. If we cannot infer all of them, we 1978 // can never do anything with this pattern: report it to the user. 1979 InferredAllPatternTypes = Pattern->InferAllTypes(); 1980 1981 // Infer as many types as possible. If we cannot infer all of them, we 1982 // can never do anything with this pattern: report it to the user. 1983 InferredAllResultTypes = Result->InferAllTypes(); 1984 1985 // Apply the type of the result to the source pattern. This helps us 1986 // resolve cases where the input type is known to be a pointer type (which 1987 // is considered resolved), but the result knows it needs to be 32- or 1988 // 64-bits. Infer the other way for good measure. 1989 IterateInference = Pattern->getTree(0)-> 1990 UpdateNodeType(Result->getTree(0)->getExtTypes(), *Result); 1991 IterateInference |= Result->getTree(0)-> 1992 UpdateNodeType(Pattern->getTree(0)->getExtTypes(), *Result); 1993 } while (IterateInference); 1994 1995 // Verify that we inferred enough types that we can do something with the 1996 // pattern and result. If these fire the user has to add type casts. 1997 if (!InferredAllPatternTypes) 1998 Pattern->error("Could not infer all types in pattern!"); 1999 if (!InferredAllResultTypes) 2000 Result->error("Could not infer all types in pattern result!"); 2001 2002 // Validate that the input pattern is correct. 2003 std::map<std::string, TreePatternNode*> InstInputs; 2004 std::map<std::string, TreePatternNode*> InstResults; 2005 std::vector<Record*> InstImpInputs; 2006 std::vector<Record*> InstImpResults; 2007 for (unsigned j = 0, ee = Pattern->getNumTrees(); j != ee; ++j) 2008 FindPatternInputsAndOutputs(Pattern, Pattern->getTree(j), 2009 InstInputs, InstResults, 2010 InstImpInputs, InstImpResults); 2011 2012 // Promote the xform function to be an explicit node if set. 2013 TreePatternNode *DstPattern = Result->getOnlyTree(); 2014 std::vector<TreePatternNode*> ResultNodeOperands; 2015 for (unsigned ii = 0, ee = DstPattern->getNumChildren(); ii != ee; ++ii) { 2016 TreePatternNode *OpNode = DstPattern->getChild(ii); 2017 if (Record *Xform = OpNode->getTransformFn()) { 2018 OpNode->setTransformFn(0); 2019 std::vector<TreePatternNode*> Children; 2020 Children.push_back(OpNode); 2021 OpNode = new TreePatternNode(Xform, Children); 2022 } 2023 ResultNodeOperands.push_back(OpNode); 2024 } 2025 DstPattern = Result->getOnlyTree(); 2026 if (!DstPattern->isLeaf()) 2027 DstPattern = new TreePatternNode(DstPattern->getOperator(), 2028 ResultNodeOperands); 2029 DstPattern->setTypes(Result->getOnlyTree()->getExtTypes()); 2030 TreePattern Temp(Result->getRecord(), DstPattern, false, *this); 2031 Temp.InferAllTypes(); 2032 2033 std::string Reason; 2034 if (!Pattern->getTree(0)->canPatternMatch(Reason, *this)) 2035 Pattern->error("Pattern can never match: " + Reason); 2036 2037 PatternsToMatch. 2038 push_back(PatternToMatch(Patterns[i]->getValueAsListInit("Predicates"), 2039 Pattern->getTree(0), 2040 Temp.getOnlyTree(), InstImpResults, 2041 Patterns[i]->getValueAsInt("AddedComplexity"))); 2042 } 2043} 2044 2045/// CombineChildVariants - Given a bunch of permutations of each child of the 2046/// 'operator' node, put them together in all possible ways. 2047static void CombineChildVariants(TreePatternNode *Orig, 2048 const std::vector<std::vector<TreePatternNode*> > &ChildVariants, 2049 std::vector<TreePatternNode*> &OutVariants, 2050 CodeGenDAGPatterns &CDP, 2051 const MultipleUseVarSet &DepVars) { 2052 // Make sure that each operand has at least one variant to choose from. 2053 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 2054 if (ChildVariants[i].empty()) 2055 return; 2056 2057 // The end result is an all-pairs construction of the resultant pattern. 2058 std::vector<unsigned> Idxs; 2059 Idxs.resize(ChildVariants.size()); 2060 bool NotDone; 2061 do { 2062#ifndef NDEBUG 2063 if (DebugFlag && !Idxs.empty()) { 2064 cerr << Orig->getOperator()->getName() << ": Idxs = [ "; 2065 for (unsigned i = 0; i < Idxs.size(); ++i) { 2066 cerr << Idxs[i] << " "; 2067 } 2068 cerr << "]\n"; 2069 } 2070#endif 2071 // Create the variant and add it to the output list. 2072 std::vector<TreePatternNode*> NewChildren; 2073 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i) 2074 NewChildren.push_back(ChildVariants[i][Idxs[i]]); 2075 TreePatternNode *R = new TreePatternNode(Orig->getOperator(), NewChildren); 2076 2077 // Copy over properties. 2078 R->setName(Orig->getName()); 2079 R->setPredicateFn(Orig->getPredicateFn()); 2080 R->setTransformFn(Orig->getTransformFn()); 2081 R->setTypes(Orig->getExtTypes()); 2082 2083 // If this pattern cannot match, do not include it as a variant. 2084 std::string ErrString; 2085 if (!R->canPatternMatch(ErrString, CDP)) { 2086 delete R; 2087 } else { 2088 bool AlreadyExists = false; 2089 2090 // Scan to see if this pattern has already been emitted. We can get 2091 // duplication due to things like commuting: 2092 // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a) 2093 // which are the same pattern. Ignore the dups. 2094 for (unsigned i = 0, e = OutVariants.size(); i != e; ++i) 2095 if (R->isIsomorphicTo(OutVariants[i], DepVars)) { 2096 AlreadyExists = true; 2097 break; 2098 } 2099 2100 if (AlreadyExists) 2101 delete R; 2102 else 2103 OutVariants.push_back(R); 2104 } 2105 2106 // Increment indices to the next permutation by incrementing the 2107 // indicies from last index backward, e.g., generate the sequence 2108 // [0, 0], [0, 1], [1, 0], [1, 1]. 2109 int IdxsIdx; 2110 for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) { 2111 if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size()) 2112 Idxs[IdxsIdx] = 0; 2113 else 2114 break; 2115 } 2116 NotDone = (IdxsIdx >= 0); 2117 } while (NotDone); 2118} 2119 2120/// CombineChildVariants - A helper function for binary operators. 2121/// 2122static void CombineChildVariants(TreePatternNode *Orig, 2123 const std::vector<TreePatternNode*> &LHS, 2124 const std::vector<TreePatternNode*> &RHS, 2125 std::vector<TreePatternNode*> &OutVariants, 2126 CodeGenDAGPatterns &CDP, 2127 const MultipleUseVarSet &DepVars) { 2128 std::vector<std::vector<TreePatternNode*> > ChildVariants; 2129 ChildVariants.push_back(LHS); 2130 ChildVariants.push_back(RHS); 2131 CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars); 2132} 2133 2134 2135static void GatherChildrenOfAssociativeOpcode(TreePatternNode *N, 2136 std::vector<TreePatternNode *> &Children) { 2137 assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"); 2138 Record *Operator = N->getOperator(); 2139 2140 // Only permit raw nodes. 2141 if (!N->getName().empty() || !N->getPredicateFn().empty() || 2142 N->getTransformFn()) { 2143 Children.push_back(N); 2144 return; 2145 } 2146 2147 if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator) 2148 Children.push_back(N->getChild(0)); 2149 else 2150 GatherChildrenOfAssociativeOpcode(N->getChild(0), Children); 2151 2152 if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator) 2153 Children.push_back(N->getChild(1)); 2154 else 2155 GatherChildrenOfAssociativeOpcode(N->getChild(1), Children); 2156} 2157 2158/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of 2159/// the (potentially recursive) pattern by using algebraic laws. 2160/// 2161static void GenerateVariantsOf(TreePatternNode *N, 2162 std::vector<TreePatternNode*> &OutVariants, 2163 CodeGenDAGPatterns &CDP, 2164 const MultipleUseVarSet &DepVars) { 2165 // We cannot permute leaves. 2166 if (N->isLeaf()) { 2167 OutVariants.push_back(N); 2168 return; 2169 } 2170 2171 // Look up interesting info about the node. 2172 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator()); 2173 2174 // If this node is associative, reassociate. 2175 if (NodeInfo.hasProperty(SDNPAssociative)) { 2176 // Reassociate by pulling together all of the linked operators 2177 std::vector<TreePatternNode*> MaximalChildren; 2178 GatherChildrenOfAssociativeOpcode(N, MaximalChildren); 2179 2180 // Only handle child sizes of 3. Otherwise we'll end up trying too many 2181 // permutations. 2182 if (MaximalChildren.size() == 3) { 2183 // Find the variants of all of our maximal children. 2184 std::vector<TreePatternNode*> AVariants, BVariants, CVariants; 2185 GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars); 2186 GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars); 2187 GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars); 2188 2189 // There are only two ways we can permute the tree: 2190 // (A op B) op C and A op (B op C) 2191 // Within these forms, we can also permute A/B/C. 2192 2193 // Generate legal pair permutations of A/B/C. 2194 std::vector<TreePatternNode*> ABVariants; 2195 std::vector<TreePatternNode*> BAVariants; 2196 std::vector<TreePatternNode*> ACVariants; 2197 std::vector<TreePatternNode*> CAVariants; 2198 std::vector<TreePatternNode*> BCVariants; 2199 std::vector<TreePatternNode*> CBVariants; 2200 CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars); 2201 CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars); 2202 CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars); 2203 CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars); 2204 CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars); 2205 CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars); 2206 2207 // Combine those into the result: (x op x) op x 2208 CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars); 2209 CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars); 2210 CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars); 2211 CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars); 2212 CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars); 2213 CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars); 2214 2215 // Combine those into the result: x op (x op x) 2216 CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars); 2217 CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars); 2218 CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars); 2219 CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars); 2220 CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars); 2221 CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars); 2222 return; 2223 } 2224 } 2225 2226 // Compute permutations of all children. 2227 std::vector<std::vector<TreePatternNode*> > ChildVariants; 2228 ChildVariants.resize(N->getNumChildren()); 2229 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) 2230 GenerateVariantsOf(N->getChild(i), ChildVariants[i], CDP, DepVars); 2231 2232 // Build all permutations based on how the children were formed. 2233 CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars); 2234 2235 // If this node is commutative, consider the commuted order. 2236 if (NodeInfo.hasProperty(SDNPCommutative)) { 2237 assert(N->getNumChildren()==2 &&"Commutative but doesn't have 2 children!"); 2238 // Don't count children which are actually register references. 2239 unsigned NC = 0; 2240 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) { 2241 TreePatternNode *Child = N->getChild(i); 2242 if (Child->isLeaf()) 2243 if (DefInit *DI = dynamic_cast<DefInit*>(Child->getLeafValue())) { 2244 Record *RR = DI->getDef(); 2245 if (RR->isSubClassOf("Register")) 2246 continue; 2247 } 2248 NC++; 2249 } 2250 // Consider the commuted order. 2251 if (NC == 2) 2252 CombineChildVariants(N, ChildVariants[1], ChildVariants[0], 2253 OutVariants, CDP, DepVars); 2254 } 2255} 2256 2257 2258// GenerateVariants - Generate variants. For example, commutative patterns can 2259// match multiple ways. Add them to PatternsToMatch as well. 2260void CodeGenDAGPatterns::GenerateVariants() { 2261 DOUT << "Generating instruction variants.\n"; 2262 2263 // Loop over all of the patterns we've collected, checking to see if we can 2264 // generate variants of the instruction, through the exploitation of 2265 // identities. This permits the target to provide agressive matching without 2266 // the .td file having to contain tons of variants of instructions. 2267 // 2268 // Note that this loop adds new patterns to the PatternsToMatch list, but we 2269 // intentionally do not reconsider these. Any variants of added patterns have 2270 // already been added. 2271 // 2272 for (unsigned i = 0, e = PatternsToMatch.size(); i != e; ++i) { 2273 MultipleUseVarSet DepVars; 2274 std::vector<TreePatternNode*> Variants; 2275 FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars); 2276 DOUT << "Dependent/multiply used variables: "; 2277 DEBUG(DumpDepVars(DepVars)); 2278 DOUT << "\n"; 2279 GenerateVariantsOf(PatternsToMatch[i].getSrcPattern(), Variants, *this, DepVars); 2280 2281 assert(!Variants.empty() && "Must create at least original variant!"); 2282 Variants.erase(Variants.begin()); // Remove the original pattern. 2283 2284 if (Variants.empty()) // No variants for this pattern. 2285 continue; 2286 2287 DOUT << "FOUND VARIANTS OF: "; 2288 DEBUG(PatternsToMatch[i].getSrcPattern()->dump()); 2289 DOUT << "\n"; 2290 2291 for (unsigned v = 0, e = Variants.size(); v != e; ++v) { 2292 TreePatternNode *Variant = Variants[v]; 2293 2294 DOUT << " VAR#" << v << ": "; 2295 DEBUG(Variant->dump()); 2296 DOUT << "\n"; 2297 2298 // Scan to see if an instruction or explicit pattern already matches this. 2299 bool AlreadyExists = false; 2300 for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) { 2301 // Check to see if this variant already exists. 2302 if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(), DepVars)) { 2303 DOUT << " *** ALREADY EXISTS, ignoring variant.\n"; 2304 AlreadyExists = true; 2305 break; 2306 } 2307 } 2308 // If we already have it, ignore the variant. 2309 if (AlreadyExists) continue; 2310 2311 // Otherwise, add it to the list of patterns we have. 2312 PatternsToMatch. 2313 push_back(PatternToMatch(PatternsToMatch[i].getPredicates(), 2314 Variant, PatternsToMatch[i].getDstPattern(), 2315 PatternsToMatch[i].getDstRegs(), 2316 PatternsToMatch[i].getAddedComplexity())); 2317 } 2318 2319 DOUT << "\n"; 2320 } 2321} 2322 2323