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