Bug Summary

File:utils/TableGen/CodeGenDAGPatterns.cpp
Warning:line 3324, column 32
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -triple x86_64-pc-linux-gnu -analyze -disable-free -disable-llvm-verifier -discard-value-names -main-file-name CodeGenDAGPatterns.cpp -analyzer-store=region -analyzer-opt-analyze-nested-blocks -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mthread-model posix -mframe-pointer=none -fmath-errno -masm-verbose -mconstructor-aliases -munwind-tables -fuse-init-array -target-cpu x86-64 -dwarf-column-info -debugger-tuning=gdb -ffunction-sections -fdata-sections -resource-dir /usr/lib/llvm-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/utils/TableGen -I /build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen -I /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/include -I /build/llvm-toolchain-snapshot-10~svn374877/include -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/x86_64-linux-gnu/c++/6.3.0 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/6.3.0/../../../../include/c++/6.3.0/backward -internal-isystem /usr/local/include -internal-isystem /usr/lib/llvm-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~svn374877/build-llvm/utils/TableGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~svn374877=. -ferror-limit 19 -fmessage-length 0 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -o /tmp/scan-build-2019-10-15-233810-7101-1 -x c++ /build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp

/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp

1//===- CodeGenDAGPatterns.cpp - Read DAG patterns from .td file -----------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file implements the CodeGenDAGPatterns class, which is used to read and
10// represent the patterns present in a .td file for instructions.
11//
12//===----------------------------------------------------------------------===//
13
14#include "CodeGenDAGPatterns.h"
15#include "llvm/ADT/BitVector.h"
16#include "llvm/ADT/DenseSet.h"
17#include "llvm/ADT/MapVector.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallSet.h"
20#include "llvm/ADT/SmallString.h"
21#include "llvm/ADT/StringExtras.h"
22#include "llvm/ADT/StringMap.h"
23#include "llvm/ADT/Twine.h"
24#include "llvm/Support/Debug.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/TableGen/Error.h"
27#include "llvm/TableGen/Record.h"
28#include <algorithm>
29#include <cstdio>
30#include <iterator>
31#include <set>
32using namespace llvm;
33
34#define DEBUG_TYPE"dag-patterns" "dag-patterns"
35
36static inline bool isIntegerOrPtr(MVT VT) {
37 return VT.isInteger() || VT == MVT::iPTR;
38}
39static inline bool isFloatingPoint(MVT VT) {
40 return VT.isFloatingPoint();
41}
42static inline bool isVector(MVT VT) {
43 return VT.isVector();
44}
45static inline bool isScalar(MVT VT) {
46 return !VT.isVector();
47}
48
49template <typename Predicate>
50static bool berase_if(MachineValueTypeSet &S, Predicate P) {
51 bool Erased = false;
52 // It is ok to iterate over MachineValueTypeSet and remove elements from it
53 // at the same time.
54 for (MVT T : S) {
55 if (!P(T))
56 continue;
57 Erased = true;
58 S.erase(T);
59 }
60 return Erased;
61}
62
63// --- TypeSetByHwMode
64
65// This is a parameterized type-set class. For each mode there is a list
66// of types that are currently possible for a given tree node. Type
67// inference will apply to each mode separately.
68
69TypeSetByHwMode::TypeSetByHwMode(ArrayRef<ValueTypeByHwMode> VTList) {
70 for (const ValueTypeByHwMode &VVT : VTList) {
71 insert(VVT);
72 AddrSpaces.push_back(VVT.PtrAddrSpace);
73 }
74}
75
76bool TypeSetByHwMode::isValueTypeByHwMode(bool AllowEmpty) const {
77 for (const auto &I : *this) {
78 if (I.second.size() > 1)
79 return false;
80 if (!AllowEmpty && I.second.empty())
81 return false;
82 }
83 return true;
84}
85
86ValueTypeByHwMode TypeSetByHwMode::getValueTypeByHwMode() const {
87 assert(isValueTypeByHwMode(true) &&((isValueTypeByHwMode(true) && "The type set has multiple types for at least one HW mode"
) ? static_cast<void> (0) : __assert_fail ("isValueTypeByHwMode(true) && \"The type set has multiple types for at least one HW mode\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 88, __PRETTY_FUNCTION__))
88 "The type set has multiple types for at least one HW mode")((isValueTypeByHwMode(true) && "The type set has multiple types for at least one HW mode"
) ? static_cast<void> (0) : __assert_fail ("isValueTypeByHwMode(true) && \"The type set has multiple types for at least one HW mode\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 88, __PRETTY_FUNCTION__))
;
89 ValueTypeByHwMode VVT;
90 auto ASI = AddrSpaces.begin();
91
92 for (const auto &I : *this) {
93 MVT T = I.second.empty() ? MVT::Other : *I.second.begin();
94 VVT.getOrCreateTypeForMode(I.first, T);
95 if (ASI != AddrSpaces.end())
96 VVT.PtrAddrSpace = *ASI++;
97 }
98 return VVT;
99}
100
101bool TypeSetByHwMode::isPossible() const {
102 for (const auto &I : *this)
103 if (!I.second.empty())
104 return true;
105 return false;
106}
107
108bool TypeSetByHwMode::insert(const ValueTypeByHwMode &VVT) {
109 bool Changed = false;
110 bool ContainsDefault = false;
111 MVT DT = MVT::Other;
112
113 SmallDenseSet<unsigned, 4> Modes;
114 for (const auto &P : VVT) {
115 unsigned M = P.first;
116 Modes.insert(M);
117 // Make sure there exists a set for each specific mode from VVT.
118 Changed |= getOrCreate(M).insert(P.second).second;
119 // Cache VVT's default mode.
120 if (DefaultMode == M) {
121 ContainsDefault = true;
122 DT = P.second;
123 }
124 }
125
126 // If VVT has a default mode, add the corresponding type to all
127 // modes in "this" that do not exist in VVT.
128 if (ContainsDefault)
129 for (auto &I : *this)
130 if (!Modes.count(I.first))
131 Changed |= I.second.insert(DT).second;
132
133 return Changed;
134}
135
136// Constrain the type set to be the intersection with VTS.
137bool TypeSetByHwMode::constrain(const TypeSetByHwMode &VTS) {
138 bool Changed = false;
139 if (hasDefault()) {
140 for (const auto &I : VTS) {
141 unsigned M = I.first;
142 if (M == DefaultMode || hasMode(M))
143 continue;
144 Map.insert({M, Map.at(DefaultMode)});
145 Changed = true;
146 }
147 }
148
149 for (auto &I : *this) {
150 unsigned M = I.first;
151 SetType &S = I.second;
152 if (VTS.hasMode(M) || VTS.hasDefault()) {
153 Changed |= intersect(I.second, VTS.get(M));
154 } else if (!S.empty()) {
155 S.clear();
156 Changed = true;
157 }
158 }
159 return Changed;
160}
161
162template <typename Predicate>
163bool TypeSetByHwMode::constrain(Predicate P) {
164 bool Changed = false;
165 for (auto &I : *this)
166 Changed |= berase_if(I.second, [&P](MVT VT) { return !P(VT); });
167 return Changed;
168}
169
170template <typename Predicate>
171bool TypeSetByHwMode::assign_if(const TypeSetByHwMode &VTS, Predicate P) {
172 assert(empty())((empty()) ? static_cast<void> (0) : __assert_fail ("empty()"
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 172, __PRETTY_FUNCTION__))
;
173 for (const auto &I : VTS) {
174 SetType &S = getOrCreate(I.first);
175 for (auto J : I.second)
176 if (P(J))
177 S.insert(J);
178 }
179 return !empty();
180}
181
182void TypeSetByHwMode::writeToStream(raw_ostream &OS) const {
183 SmallVector<unsigned, 4> Modes;
184 Modes.reserve(Map.size());
185
186 for (const auto &I : *this)
187 Modes.push_back(I.first);
188 if (Modes.empty()) {
189 OS << "{}";
190 return;
191 }
192 array_pod_sort(Modes.begin(), Modes.end());
193
194 OS << '{';
195 for (unsigned M : Modes) {
196 OS << ' ' << getModeName(M) << ':';
197 writeToStream(get(M), OS);
198 }
199 OS << " }";
200}
201
202void TypeSetByHwMode::writeToStream(const SetType &S, raw_ostream &OS) {
203 SmallVector<MVT, 4> Types(S.begin(), S.end());
204 array_pod_sort(Types.begin(), Types.end());
205
206 OS << '[';
207 for (unsigned i = 0, e = Types.size(); i != e; ++i) {
208 OS << ValueTypeByHwMode::getMVTName(Types[i]);
209 if (i != e-1)
210 OS << ' ';
211 }
212 OS << ']';
213}
214
215bool TypeSetByHwMode::operator==(const TypeSetByHwMode &VTS) const {
216 // The isSimple call is much quicker than hasDefault - check this first.
217 bool IsSimple = isSimple();
218 bool VTSIsSimple = VTS.isSimple();
219 if (IsSimple && VTSIsSimple)
220 return *begin() == *VTS.begin();
221
222 // Speedup: We have a default if the set is simple.
223 bool HaveDefault = IsSimple || hasDefault();
224 bool VTSHaveDefault = VTSIsSimple || VTS.hasDefault();
225 if (HaveDefault != VTSHaveDefault)
226 return false;
227
228 SmallDenseSet<unsigned, 4> Modes;
229 for (auto &I : *this)
230 Modes.insert(I.first);
231 for (const auto &I : VTS)
232 Modes.insert(I.first);
233
234 if (HaveDefault) {
235 // Both sets have default mode.
236 for (unsigned M : Modes) {
237 if (get(M) != VTS.get(M))
238 return false;
239 }
240 } else {
241 // Neither set has default mode.
242 for (unsigned M : Modes) {
243 // If there is no default mode, an empty set is equivalent to not having
244 // the corresponding mode.
245 bool NoModeThis = !hasMode(M) || get(M).empty();
246 bool NoModeVTS = !VTS.hasMode(M) || VTS.get(M).empty();
247 if (NoModeThis != NoModeVTS)
248 return false;
249 if (!NoModeThis)
250 if (get(M) != VTS.get(M))
251 return false;
252 }
253 }
254
255 return true;
256}
257
258namespace llvm {
259 raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T) {
260 T.writeToStream(OS);
261 return OS;
262 }
263}
264
265LLVM_DUMP_METHOD__attribute__((noinline)) __attribute__((__used__))
266void TypeSetByHwMode::dump() const {
267 dbgs() << *this << '\n';
268}
269
270bool TypeSetByHwMode::intersect(SetType &Out, const SetType &In) {
271 bool OutP = Out.count(MVT::iPTR), InP = In.count(MVT::iPTR);
272 auto Int = [&In](MVT T) -> bool { return !In.count(T); };
273
274 if (OutP == InP)
275 return berase_if(Out, Int);
276
277 // Compute the intersection of scalars separately to account for only
278 // one set containing iPTR.
279 // The itersection of iPTR with a set of integer scalar types that does not
280 // include iPTR will result in the most specific scalar type:
281 // - iPTR is more specific than any set with two elements or more
282 // - iPTR is less specific than any single integer scalar type.
283 // For example
284 // { iPTR } * { i32 } -> { i32 }
285 // { iPTR } * { i32 i64 } -> { iPTR }
286 // and
287 // { iPTR i32 } * { i32 } -> { i32 }
288 // { iPTR i32 } * { i32 i64 } -> { i32 i64 }
289 // { iPTR i32 } * { i32 i64 i128 } -> { iPTR i32 }
290
291 // Compute the difference between the two sets in such a way that the
292 // iPTR is in the set that is being subtracted. This is to see if there
293 // are any extra scalars in the set without iPTR that are not in the
294 // set containing iPTR. Then the iPTR could be considered a "wildcard"
295 // matching these scalars. If there is only one such scalar, it would
296 // replace the iPTR, if there are more, the iPTR would be retained.
297 SetType Diff;
298 if (InP) {
299 Diff = Out;
300 berase_if(Diff, [&In](MVT T) { return In.count(T); });
301 // Pre-remove these elements and rely only on InP/OutP to determine
302 // whether a change has been made.
303 berase_if(Out, [&Diff](MVT T) { return Diff.count(T); });
304 } else {
305 Diff = In;
306 berase_if(Diff, [&Out](MVT T) { return Out.count(T); });
307 Out.erase(MVT::iPTR);
308 }
309
310 // The actual intersection.
311 bool Changed = berase_if(Out, Int);
312 unsigned NumD = Diff.size();
313 if (NumD == 0)
314 return Changed;
315
316 if (NumD == 1) {
317 Out.insert(*Diff.begin());
318 // This is a change only if Out was the one with iPTR (which is now
319 // being replaced).
320 Changed |= OutP;
321 } else {
322 // Multiple elements from Out are now replaced with iPTR.
323 Out.insert(MVT::iPTR);
324 Changed |= !OutP;
325 }
326 return Changed;
327}
328
329bool TypeSetByHwMode::validate() const {
330#ifndef NDEBUG
331 if (empty())
332 return true;
333 bool AllEmpty = true;
334 for (const auto &I : *this)
335 AllEmpty &= I.second.empty();
336 return !AllEmpty;
337#endif
338 return true;
339}
340
341// --- TypeInfer
342
343bool TypeInfer::MergeInTypeInfo(TypeSetByHwMode &Out,
344 const TypeSetByHwMode &In) {
345 ValidateOnExit _1(Out, *this);
346 In.validate();
347 if (In.empty() || Out == In || TP.hasError())
348 return false;
349 if (Out.empty()) {
350 Out = In;
351 return true;
352 }
353
354 bool Changed = Out.constrain(In);
355 if (Changed && Out.empty())
356 TP.error("Type contradiction");
357
358 return Changed;
359}
360
361bool TypeInfer::forceArbitrary(TypeSetByHwMode &Out) {
362 ValidateOnExit _1(Out, *this);
363 if (TP.hasError())
364 return false;
365 assert(!Out.empty() && "cannot pick from an empty set")((!Out.empty() && "cannot pick from an empty set") ? static_cast
<void> (0) : __assert_fail ("!Out.empty() && \"cannot pick from an empty set\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 365, __PRETTY_FUNCTION__))
;
366
367 bool Changed = false;
368 for (auto &I : Out) {
369 TypeSetByHwMode::SetType &S = I.second;
370 if (S.size() <= 1)
371 continue;
372 MVT T = *S.begin(); // Pick the first element.
373 S.clear();
374 S.insert(T);
375 Changed = true;
376 }
377 return Changed;
378}
379
380bool TypeInfer::EnforceInteger(TypeSetByHwMode &Out) {
381 ValidateOnExit _1(Out, *this);
382 if (TP.hasError())
383 return false;
384 if (!Out.empty())
385 return Out.constrain(isIntegerOrPtr);
386
387 return Out.assign_if(getLegalTypes(), isIntegerOrPtr);
388}
389
390bool TypeInfer::EnforceFloatingPoint(TypeSetByHwMode &Out) {
391 ValidateOnExit _1(Out, *this);
392 if (TP.hasError())
393 return false;
394 if (!Out.empty())
395 return Out.constrain(isFloatingPoint);
396
397 return Out.assign_if(getLegalTypes(), isFloatingPoint);
398}
399
400bool TypeInfer::EnforceScalar(TypeSetByHwMode &Out) {
401 ValidateOnExit _1(Out, *this);
402 if (TP.hasError())
403 return false;
404 if (!Out.empty())
405 return Out.constrain(isScalar);
406
407 return Out.assign_if(getLegalTypes(), isScalar);
408}
409
410bool TypeInfer::EnforceVector(TypeSetByHwMode &Out) {
411 ValidateOnExit _1(Out, *this);
412 if (TP.hasError())
413 return false;
414 if (!Out.empty())
415 return Out.constrain(isVector);
416
417 return Out.assign_if(getLegalTypes(), isVector);
418}
419
420bool TypeInfer::EnforceAny(TypeSetByHwMode &Out) {
421 ValidateOnExit _1(Out, *this);
422 if (TP.hasError() || !Out.empty())
423 return false;
424
425 Out = getLegalTypes();
426 return true;
427}
428
429template <typename Iter, typename Pred, typename Less>
430static Iter min_if(Iter B, Iter E, Pred P, Less L) {
431 if (B == E)
432 return E;
433 Iter Min = E;
434 for (Iter I = B; I != E; ++I) {
435 if (!P(*I))
436 continue;
437 if (Min == E || L(*I, *Min))
438 Min = I;
439 }
440 return Min;
441}
442
443template <typename Iter, typename Pred, typename Less>
444static Iter max_if(Iter B, Iter E, Pred P, Less L) {
445 if (B == E)
446 return E;
447 Iter Max = E;
448 for (Iter I = B; I != E; ++I) {
449 if (!P(*I))
450 continue;
451 if (Max == E || L(*Max, *I))
452 Max = I;
453 }
454 return Max;
455}
456
457/// Make sure that for each type in Small, there exists a larger type in Big.
458bool TypeInfer::EnforceSmallerThan(TypeSetByHwMode &Small,
459 TypeSetByHwMode &Big) {
460 ValidateOnExit _1(Small, *this), _2(Big, *this);
461 if (TP.hasError())
462 return false;
463 bool Changed = false;
464
465 if (Small.empty())
466 Changed |= EnforceAny(Small);
467 if (Big.empty())
468 Changed |= EnforceAny(Big);
469
470 assert(Small.hasDefault() && Big.hasDefault())((Small.hasDefault() && Big.hasDefault()) ? static_cast
<void> (0) : __assert_fail ("Small.hasDefault() && Big.hasDefault()"
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 470, __PRETTY_FUNCTION__))
;
471
472 std::vector<unsigned> Modes = union_modes(Small, Big);
473
474 // 1. Only allow integer or floating point types and make sure that
475 // both sides are both integer or both floating point.
476 // 2. Make sure that either both sides have vector types, or neither
477 // of them does.
478 for (unsigned M : Modes) {
479 TypeSetByHwMode::SetType &S = Small.get(M);
480 TypeSetByHwMode::SetType &B = Big.get(M);
481
482 if (any_of(S, isIntegerOrPtr) && any_of(S, isIntegerOrPtr)) {
483 auto NotInt = [](MVT VT) { return !isIntegerOrPtr(VT); };
484 Changed |= berase_if(S, NotInt) |
485 berase_if(B, NotInt);
486 } else if (any_of(S, isFloatingPoint) && any_of(B, isFloatingPoint)) {
487 auto NotFP = [](MVT VT) { return !isFloatingPoint(VT); };
488 Changed |= berase_if(S, NotFP) |
489 berase_if(B, NotFP);
490 } else if (S.empty() || B.empty()) {
491 Changed = !S.empty() || !B.empty();
492 S.clear();
493 B.clear();
494 } else {
495 TP.error("Incompatible types");
496 return Changed;
497 }
498
499 if (none_of(S, isVector) || none_of(B, isVector)) {
500 Changed |= berase_if(S, isVector) |
501 berase_if(B, isVector);
502 }
503 }
504
505 auto LT = [](MVT A, MVT B) -> bool {
506 return A.getScalarSizeInBits() < B.getScalarSizeInBits() ||
507 (A.getScalarSizeInBits() == B.getScalarSizeInBits() &&
508 A.getSizeInBits() < B.getSizeInBits());
509 };
510 auto LE = [&LT](MVT A, MVT B) -> bool {
511 // This function is used when removing elements: when a vector is compared
512 // to a non-vector, it should return false (to avoid removal).
513 if (A.isVector() != B.isVector())
514 return false;
515
516 return LT(A, B) || (A.getScalarSizeInBits() == B.getScalarSizeInBits() &&
517 A.getSizeInBits() == B.getSizeInBits());
518 };
519
520 for (unsigned M : Modes) {
521 TypeSetByHwMode::SetType &S = Small.get(M);
522 TypeSetByHwMode::SetType &B = Big.get(M);
523 // MinS = min scalar in Small, remove all scalars from Big that are
524 // smaller-or-equal than MinS.
525 auto MinS = min_if(S.begin(), S.end(), isScalar, LT);
526 if (MinS != S.end())
527 Changed |= berase_if(B, std::bind(LE, std::placeholders::_1, *MinS));
528
529 // MaxS = max scalar in Big, remove all scalars from Small that are
530 // larger than MaxS.
531 auto MaxS = max_if(B.begin(), B.end(), isScalar, LT);
532 if (MaxS != B.end())
533 Changed |= berase_if(S, std::bind(LE, *MaxS, std::placeholders::_1));
534
535 // MinV = min vector in Small, remove all vectors from Big that are
536 // smaller-or-equal than MinV.
537 auto MinV = min_if(S.begin(), S.end(), isVector, LT);
538 if (MinV != S.end())
539 Changed |= berase_if(B, std::bind(LE, std::placeholders::_1, *MinV));
540
541 // MaxV = max vector in Big, remove all vectors from Small that are
542 // larger than MaxV.
543 auto MaxV = max_if(B.begin(), B.end(), isVector, LT);
544 if (MaxV != B.end())
545 Changed |= berase_if(S, std::bind(LE, *MaxV, std::placeholders::_1));
546 }
547
548 return Changed;
549}
550
551/// 1. Ensure that for each type T in Vec, T is a vector type, and that
552/// for each type U in Elem, U is a scalar type.
553/// 2. Ensure that for each (scalar) type U in Elem, there exists a (vector)
554/// type T in Vec, such that U is the element type of T.
555bool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,
556 TypeSetByHwMode &Elem) {
557 ValidateOnExit _1(Vec, *this), _2(Elem, *this);
558 if (TP.hasError())
559 return false;
560 bool Changed = false;
561
562 if (Vec.empty())
563 Changed |= EnforceVector(Vec);
564 if (Elem.empty())
565 Changed |= EnforceScalar(Elem);
566
567 for (unsigned M : union_modes(Vec, Elem)) {
568 TypeSetByHwMode::SetType &V = Vec.get(M);
569 TypeSetByHwMode::SetType &E = Elem.get(M);
570
571 Changed |= berase_if(V, isScalar); // Scalar = !vector
572 Changed |= berase_if(E, isVector); // Vector = !scalar
573 assert(!V.empty() && !E.empty())((!V.empty() && !E.empty()) ? static_cast<void>
(0) : __assert_fail ("!V.empty() && !E.empty()", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 573, __PRETTY_FUNCTION__))
;
574
575 SmallSet<MVT,4> VT, ST;
576 // Collect element types from the "vector" set.
577 for (MVT T : V)
578 VT.insert(T.getVectorElementType());
579 // Collect scalar types from the "element" set.
580 for (MVT T : E)
581 ST.insert(T);
582
583 // Remove from V all (vector) types whose element type is not in S.
584 Changed |= berase_if(V, [&ST](MVT T) -> bool {
585 return !ST.count(T.getVectorElementType());
586 });
587 // Remove from E all (scalar) types, for which there is no corresponding
588 // type in V.
589 Changed |= berase_if(E, [&VT](MVT T) -> bool { return !VT.count(T); });
590 }
591
592 return Changed;
593}
594
595bool TypeInfer::EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,
596 const ValueTypeByHwMode &VVT) {
597 TypeSetByHwMode Tmp(VVT);
598 ValidateOnExit _1(Vec, *this), _2(Tmp, *this);
599 return EnforceVectorEltTypeIs(Vec, Tmp);
600}
601
602/// Ensure that for each type T in Sub, T is a vector type, and there
603/// exists a type U in Vec such that U is a vector type with the same
604/// element type as T and at least as many elements as T.
605bool TypeInfer::EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec,
606 TypeSetByHwMode &Sub) {
607 ValidateOnExit _1(Vec, *this), _2(Sub, *this);
608 if (TP.hasError())
609 return false;
610
611 /// Return true if B is a suB-vector of P, i.e. P is a suPer-vector of B.
612 auto IsSubVec = [](MVT B, MVT P) -> bool {
613 if (!B.isVector() || !P.isVector())
614 return false;
615 // Logically a <4 x i32> is a valid subvector of <n x 4 x i32>
616 // but until there are obvious use-cases for this, keep the
617 // types separate.
618 if (B.isScalableVector() != P.isScalableVector())
619 return false;
620 if (B.getVectorElementType() != P.getVectorElementType())
621 return false;
622 return B.getVectorNumElements() < P.getVectorNumElements();
623 };
624
625 /// Return true if S has no element (vector type) that T is a sub-vector of,
626 /// i.e. has the same element type as T and more elements.
627 auto NoSubV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool {
628 for (const auto &I : S)
629 if (IsSubVec(T, I))
630 return false;
631 return true;
632 };
633
634 /// Return true if S has no element (vector type) that T is a super-vector
635 /// of, i.e. has the same element type as T and fewer elements.
636 auto NoSupV = [&IsSubVec](const TypeSetByHwMode::SetType &S, MVT T) -> bool {
637 for (const auto &I : S)
638 if (IsSubVec(I, T))
639 return false;
640 return true;
641 };
642
643 bool Changed = false;
644
645 if (Vec.empty())
646 Changed |= EnforceVector(Vec);
647 if (Sub.empty())
648 Changed |= EnforceVector(Sub);
649
650 for (unsigned M : union_modes(Vec, Sub)) {
651 TypeSetByHwMode::SetType &S = Sub.get(M);
652 TypeSetByHwMode::SetType &V = Vec.get(M);
653
654 Changed |= berase_if(S, isScalar);
655
656 // Erase all types from S that are not sub-vectors of a type in V.
657 Changed |= berase_if(S, std::bind(NoSubV, V, std::placeholders::_1));
658
659 // Erase all types from V that are not super-vectors of a type in S.
660 Changed |= berase_if(V, std::bind(NoSupV, S, std::placeholders::_1));
661 }
662
663 return Changed;
664}
665
666/// 1. Ensure that V has a scalar type iff W has a scalar type.
667/// 2. Ensure that for each vector type T in V, there exists a vector
668/// type U in W, such that T and U have the same number of elements.
669/// 3. Ensure that for each vector type U in W, there exists a vector
670/// type T in V, such that T and U have the same number of elements
671/// (reverse of 2).
672bool TypeInfer::EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W) {
673 ValidateOnExit _1(V, *this), _2(W, *this);
674 if (TP.hasError())
675 return false;
676
677 bool Changed = false;
678 if (V.empty())
679 Changed |= EnforceAny(V);
680 if (W.empty())
681 Changed |= EnforceAny(W);
682
683 // An actual vector type cannot have 0 elements, so we can treat scalars
684 // as zero-length vectors. This way both vectors and scalars can be
685 // processed identically.
686 auto NoLength = [](const SmallSet<unsigned,2> &Lengths, MVT T) -> bool {
687 return !Lengths.count(T.isVector() ? T.getVectorNumElements() : 0);
688 };
689
690 for (unsigned M : union_modes(V, W)) {
691 TypeSetByHwMode::SetType &VS = V.get(M);
692 TypeSetByHwMode::SetType &WS = W.get(M);
693
694 SmallSet<unsigned,2> VN, WN;
695 for (MVT T : VS)
696 VN.insert(T.isVector() ? T.getVectorNumElements() : 0);
697 for (MVT T : WS)
698 WN.insert(T.isVector() ? T.getVectorNumElements() : 0);
699
700 Changed |= berase_if(VS, std::bind(NoLength, WN, std::placeholders::_1));
701 Changed |= berase_if(WS, std::bind(NoLength, VN, std::placeholders::_1));
702 }
703 return Changed;
704}
705
706/// 1. Ensure that for each type T in A, there exists a type U in B,
707/// such that T and U have equal size in bits.
708/// 2. Ensure that for each type U in B, there exists a type T in A
709/// such that T and U have equal size in bits (reverse of 1).
710bool TypeInfer::EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B) {
711 ValidateOnExit _1(A, *this), _2(B, *this);
712 if (TP.hasError())
713 return false;
714 bool Changed = false;
715 if (A.empty())
716 Changed |= EnforceAny(A);
717 if (B.empty())
718 Changed |= EnforceAny(B);
719
720 auto NoSize = [](const SmallSet<unsigned,2> &Sizes, MVT T) -> bool {
721 return !Sizes.count(T.getSizeInBits());
722 };
723
724 for (unsigned M : union_modes(A, B)) {
725 TypeSetByHwMode::SetType &AS = A.get(M);
726 TypeSetByHwMode::SetType &BS = B.get(M);
727 SmallSet<unsigned,2> AN, BN;
728
729 for (MVT T : AS)
730 AN.insert(T.getSizeInBits());
731 for (MVT T : BS)
732 BN.insert(T.getSizeInBits());
733
734 Changed |= berase_if(AS, std::bind(NoSize, BN, std::placeholders::_1));
735 Changed |= berase_if(BS, std::bind(NoSize, AN, std::placeholders::_1));
736 }
737
738 return Changed;
739}
740
741void TypeInfer::expandOverloads(TypeSetByHwMode &VTS) {
742 ValidateOnExit _1(VTS, *this);
743 const TypeSetByHwMode &Legal = getLegalTypes();
744 assert(Legal.isDefaultOnly() && "Default-mode only expected")((Legal.isDefaultOnly() && "Default-mode only expected"
) ? static_cast<void> (0) : __assert_fail ("Legal.isDefaultOnly() && \"Default-mode only expected\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 744, __PRETTY_FUNCTION__))
;
745 const TypeSetByHwMode::SetType &LegalTypes = Legal.get(DefaultMode);
746
747 for (auto &I : VTS)
748 expandOverloads(I.second, LegalTypes);
749}
750
751void TypeInfer::expandOverloads(TypeSetByHwMode::SetType &Out,
752 const TypeSetByHwMode::SetType &Legal) {
753 std::set<MVT> Ovs;
754 for (MVT T : Out) {
755 if (!T.isOverloaded())
756 continue;
757
758 Ovs.insert(T);
759 // MachineValueTypeSet allows iteration and erasing.
760 Out.erase(T);
761 }
762
763 for (MVT Ov : Ovs) {
764 switch (Ov.SimpleTy) {
765 case MVT::iPTRAny:
766 Out.insert(MVT::iPTR);
767 return;
768 case MVT::iAny:
769 for (MVT T : MVT::integer_valuetypes())
770 if (Legal.count(T))
771 Out.insert(T);
772 for (MVT T : MVT::integer_fixedlen_vector_valuetypes())
773 if (Legal.count(T))
774 Out.insert(T);
775 for (MVT T : MVT::integer_scalable_vector_valuetypes())
776 if (Legal.count(T))
777 Out.insert(T);
778 return;
779 case MVT::fAny:
780 for (MVT T : MVT::fp_valuetypes())
781 if (Legal.count(T))
782 Out.insert(T);
783 for (MVT T : MVT::fp_fixedlen_vector_valuetypes())
784 if (Legal.count(T))
785 Out.insert(T);
786 for (MVT T : MVT::fp_scalable_vector_valuetypes())
787 if (Legal.count(T))
788 Out.insert(T);
789 return;
790 case MVT::vAny:
791 for (MVT T : MVT::vector_valuetypes())
792 if (Legal.count(T))
793 Out.insert(T);
794 return;
795 case MVT::Any:
796 for (MVT T : MVT::all_valuetypes())
797 if (Legal.count(T))
798 Out.insert(T);
799 return;
800 default:
801 break;
802 }
803 }
804}
805
806const TypeSetByHwMode &TypeInfer::getLegalTypes() {
807 if (!LegalTypesCached) {
808 TypeSetByHwMode::SetType &LegalTypes = LegalCache.getOrCreate(DefaultMode);
809 // Stuff all types from all modes into the default mode.
810 const TypeSetByHwMode &LTS = TP.getDAGPatterns().getLegalTypes();
811 for (const auto &I : LTS)
812 LegalTypes.insert(I.second);
813 LegalTypesCached = true;
814 }
815 assert(LegalCache.isDefaultOnly() && "Default-mode only expected")((LegalCache.isDefaultOnly() && "Default-mode only expected"
) ? static_cast<void> (0) : __assert_fail ("LegalCache.isDefaultOnly() && \"Default-mode only expected\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 815, __PRETTY_FUNCTION__))
;
816 return LegalCache;
817}
818
819#ifndef NDEBUG
820TypeInfer::ValidateOnExit::~ValidateOnExit() {
821 if (Infer.Validate && !VTS.validate()) {
822 dbgs() << "Type set is empty for each HW mode:\n"
823 "possible type contradiction in the pattern below "
824 "(use -print-records with llvm-tblgen to see all "
825 "expanded records).\n";
826 Infer.TP.dump();
827 llvm_unreachable(nullptr)::llvm::llvm_unreachable_internal(nullptr, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 827)
;
828 }
829}
830#endif
831
832
833//===----------------------------------------------------------------------===//
834// ScopedName Implementation
835//===----------------------------------------------------------------------===//
836
837bool ScopedName::operator==(const ScopedName &o) const {
838 return Scope == o.Scope && Identifier == o.Identifier;
839}
840
841bool ScopedName::operator!=(const ScopedName &o) const {
842 return !(*this == o);
843}
844
845
846//===----------------------------------------------------------------------===//
847// TreePredicateFn Implementation
848//===----------------------------------------------------------------------===//
849
850/// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag.
851TreePredicateFn::TreePredicateFn(TreePattern *N) : PatFragRec(N) {
852 assert((((!hasPredCode() || !hasImmCode()) && ".td file corrupt: can't have a node predicate *and* an imm predicate"
) ? static_cast<void> (0) : __assert_fail ("(!hasPredCode() || !hasImmCode()) && \".td file corrupt: can't have a node predicate *and* an imm predicate\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 854, __PRETTY_FUNCTION__))
853 (!hasPredCode() || !hasImmCode()) &&(((!hasPredCode() || !hasImmCode()) && ".td file corrupt: can't have a node predicate *and* an imm predicate"
) ? static_cast<void> (0) : __assert_fail ("(!hasPredCode() || !hasImmCode()) && \".td file corrupt: can't have a node predicate *and* an imm predicate\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 854, __PRETTY_FUNCTION__))
854 ".td file corrupt: can't have a node predicate *and* an imm predicate")(((!hasPredCode() || !hasImmCode()) && ".td file corrupt: can't have a node predicate *and* an imm predicate"
) ? static_cast<void> (0) : __assert_fail ("(!hasPredCode() || !hasImmCode()) && \".td file corrupt: can't have a node predicate *and* an imm predicate\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 854, __PRETTY_FUNCTION__))
;
855}
856
857bool TreePredicateFn::hasPredCode() const {
858 return isLoad() || isStore() || isAtomic() ||
859 !PatFragRec->getRecord()->getValueAsString("PredicateCode").empty();
860}
861
862std::string TreePredicateFn::getPredCode() const {
863 std::string Code = "";
864
865 if (!isLoad() && !isStore() && !isAtomic()) {
866 Record *MemoryVT = getMemoryVT();
867
868 if (MemoryVT)
869 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
870 "MemoryVT requires IsLoad or IsStore");
871 }
872
873 if (!isLoad() && !isStore()) {
874 if (isUnindexed())
875 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
876 "IsUnindexed requires IsLoad or IsStore");
877
878 Record *ScalarMemoryVT = getScalarMemoryVT();
879
880 if (ScalarMemoryVT)
881 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
882 "ScalarMemoryVT requires IsLoad or IsStore");
883 }
884
885 if (isLoad() + isStore() + isAtomic() > 1)
886 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
887 "IsLoad, IsStore, and IsAtomic are mutually exclusive");
888
889 if (isLoad()) {
890 if (!isUnindexed() && !isNonExtLoad() && !isAnyExtLoad() &&
891 !isSignExtLoad() && !isZeroExtLoad() && getMemoryVT() == nullptr &&
892 getScalarMemoryVT() == nullptr && getAddressSpaces() == nullptr &&
893 getMinAlignment() < 1)
894 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
895 "IsLoad cannot be used by itself");
896 } else {
897 if (isNonExtLoad())
898 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
899 "IsNonExtLoad requires IsLoad");
900 if (isAnyExtLoad())
901 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
902 "IsAnyExtLoad requires IsLoad");
903 if (isSignExtLoad())
904 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
905 "IsSignExtLoad requires IsLoad");
906 if (isZeroExtLoad())
907 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
908 "IsZeroExtLoad requires IsLoad");
909 }
910
911 if (isStore()) {
912 if (!isUnindexed() && !isTruncStore() && !isNonTruncStore() &&
913 getMemoryVT() == nullptr && getScalarMemoryVT() == nullptr &&
914 getAddressSpaces() == nullptr && getMinAlignment() < 1)
915 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
916 "IsStore cannot be used by itself");
917 } else {
918 if (isNonTruncStore())
919 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
920 "IsNonTruncStore requires IsStore");
921 if (isTruncStore())
922 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
923 "IsTruncStore requires IsStore");
924 }
925
926 if (isAtomic()) {
927 if (getMemoryVT() == nullptr && !isAtomicOrderingMonotonic() &&
928 getAddressSpaces() == nullptr &&
929 !isAtomicOrderingAcquire() && !isAtomicOrderingRelease() &&
930 !isAtomicOrderingAcquireRelease() &&
931 !isAtomicOrderingSequentiallyConsistent() &&
932 !isAtomicOrderingAcquireOrStronger() &&
933 !isAtomicOrderingReleaseOrStronger() &&
934 !isAtomicOrderingWeakerThanAcquire() &&
935 !isAtomicOrderingWeakerThanRelease())
936 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
937 "IsAtomic cannot be used by itself");
938 } else {
939 if (isAtomicOrderingMonotonic())
940 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
941 "IsAtomicOrderingMonotonic requires IsAtomic");
942 if (isAtomicOrderingAcquire())
943 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
944 "IsAtomicOrderingAcquire requires IsAtomic");
945 if (isAtomicOrderingRelease())
946 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
947 "IsAtomicOrderingRelease requires IsAtomic");
948 if (isAtomicOrderingAcquireRelease())
949 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
950 "IsAtomicOrderingAcquireRelease requires IsAtomic");
951 if (isAtomicOrderingSequentiallyConsistent())
952 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
953 "IsAtomicOrderingSequentiallyConsistent requires IsAtomic");
954 if (isAtomicOrderingAcquireOrStronger())
955 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
956 "IsAtomicOrderingAcquireOrStronger requires IsAtomic");
957 if (isAtomicOrderingReleaseOrStronger())
958 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
959 "IsAtomicOrderingReleaseOrStronger requires IsAtomic");
960 if (isAtomicOrderingWeakerThanAcquire())
961 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
962 "IsAtomicOrderingWeakerThanAcquire requires IsAtomic");
963 }
964
965 if (isLoad() || isStore() || isAtomic()) {
966 if (ListInit *AddressSpaces = getAddressSpaces()) {
967 Code += "unsigned AddrSpace = cast<MemSDNode>(N)->getAddressSpace();\n"
968 " if (";
969
970 bool First = true;
971 for (Init *Val : AddressSpaces->getValues()) {
972 if (First)
973 First = false;
974 else
975 Code += " && ";
976
977 IntInit *IntVal = dyn_cast<IntInit>(Val);
978 if (!IntVal) {
979 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
980 "AddressSpaces element must be integer");
981 }
982
983 Code += "AddrSpace != " + utostr(IntVal->getValue());
984 }
985
986 Code += ")\nreturn false;\n";
987 }
988
989 int64_t MinAlign = getMinAlignment();
990 if (MinAlign > 0) {
991 Code += "if (cast<MemSDNode>(N)->getAlignment() < ";
992 Code += utostr(MinAlign);
993 Code += ")\nreturn false;\n";
994 }
995
996 Record *MemoryVT = getMemoryVT();
997
998 if (MemoryVT)
999 Code += ("if (cast<MemSDNode>(N)->getMemoryVT() != MVT::" +
1000 MemoryVT->getName() + ") return false;\n")
1001 .str();
1002 }
1003
1004 if (isAtomic() && isAtomicOrderingMonotonic())
1005 Code += "if (cast<AtomicSDNode>(N)->getOrdering() != "
1006 "AtomicOrdering::Monotonic) return false;\n";
1007 if (isAtomic() && isAtomicOrderingAcquire())
1008 Code += "if (cast<AtomicSDNode>(N)->getOrdering() != "
1009 "AtomicOrdering::Acquire) return false;\n";
1010 if (isAtomic() && isAtomicOrderingRelease())
1011 Code += "if (cast<AtomicSDNode>(N)->getOrdering() != "
1012 "AtomicOrdering::Release) return false;\n";
1013 if (isAtomic() && isAtomicOrderingAcquireRelease())
1014 Code += "if (cast<AtomicSDNode>(N)->getOrdering() != "
1015 "AtomicOrdering::AcquireRelease) return false;\n";
1016 if (isAtomic() && isAtomicOrderingSequentiallyConsistent())
1017 Code += "if (cast<AtomicSDNode>(N)->getOrdering() != "
1018 "AtomicOrdering::SequentiallyConsistent) return false;\n";
1019
1020 if (isAtomic() && isAtomicOrderingAcquireOrStronger())
1021 Code += "if (!isAcquireOrStronger(cast<AtomicSDNode>(N)->getOrdering())) "
1022 "return false;\n";
1023 if (isAtomic() && isAtomicOrderingWeakerThanAcquire())
1024 Code += "if (isAcquireOrStronger(cast<AtomicSDNode>(N)->getOrdering())) "
1025 "return false;\n";
1026
1027 if (isAtomic() && isAtomicOrderingReleaseOrStronger())
1028 Code += "if (!isReleaseOrStronger(cast<AtomicSDNode>(N)->getOrdering())) "
1029 "return false;\n";
1030 if (isAtomic() && isAtomicOrderingWeakerThanRelease())
1031 Code += "if (isReleaseOrStronger(cast<AtomicSDNode>(N)->getOrdering())) "
1032 "return false;\n";
1033
1034 if (isLoad() || isStore()) {
1035 StringRef SDNodeName = isLoad() ? "LoadSDNode" : "StoreSDNode";
1036
1037 if (isUnindexed())
1038 Code += ("if (cast<" + SDNodeName +
1039 ">(N)->getAddressingMode() != ISD::UNINDEXED) "
1040 "return false;\n")
1041 .str();
1042
1043 if (isLoad()) {
1044 if ((isNonExtLoad() + isAnyExtLoad() + isSignExtLoad() +
1045 isZeroExtLoad()) > 1)
1046 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
1047 "IsNonExtLoad, IsAnyExtLoad, IsSignExtLoad, and "
1048 "IsZeroExtLoad are mutually exclusive");
1049 if (isNonExtLoad())
1050 Code += "if (cast<LoadSDNode>(N)->getExtensionType() != "
1051 "ISD::NON_EXTLOAD) return false;\n";
1052 if (isAnyExtLoad())
1053 Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::EXTLOAD) "
1054 "return false;\n";
1055 if (isSignExtLoad())
1056 Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::SEXTLOAD) "
1057 "return false;\n";
1058 if (isZeroExtLoad())
1059 Code += "if (cast<LoadSDNode>(N)->getExtensionType() != ISD::ZEXTLOAD) "
1060 "return false;\n";
1061 } else {
1062 if ((isNonTruncStore() + isTruncStore()) > 1)
1063 PrintFatalError(
1064 getOrigPatFragRecord()->getRecord()->getLoc(),
1065 "IsNonTruncStore, and IsTruncStore are mutually exclusive");
1066 if (isNonTruncStore())
1067 Code +=
1068 " if (cast<StoreSDNode>(N)->isTruncatingStore()) return false;\n";
1069 if (isTruncStore())
1070 Code +=
1071 " if (!cast<StoreSDNode>(N)->isTruncatingStore()) return false;\n";
1072 }
1073
1074 Record *ScalarMemoryVT = getScalarMemoryVT();
1075
1076 if (ScalarMemoryVT)
1077 Code += ("if (cast<" + SDNodeName +
1078 ">(N)->getMemoryVT().getScalarType() != MVT::" +
1079 ScalarMemoryVT->getName() + ") return false;\n")
1080 .str();
1081 }
1082
1083 std::string PredicateCode = PatFragRec->getRecord()->getValueAsString("PredicateCode");
1084
1085 Code += PredicateCode;
1086
1087 if (PredicateCode.empty() && !Code.empty())
1088 Code += "return true;\n";
1089
1090 return Code;
1091}
1092
1093bool TreePredicateFn::hasImmCode() const {
1094 return !PatFragRec->getRecord()->getValueAsString("ImmediateCode").empty();
1095}
1096
1097std::string TreePredicateFn::getImmCode() const {
1098 return PatFragRec->getRecord()->getValueAsString("ImmediateCode");
1099}
1100
1101bool TreePredicateFn::immCodeUsesAPInt() const {
1102 return getOrigPatFragRecord()->getRecord()->getValueAsBit("IsAPInt");
1103}
1104
1105bool TreePredicateFn::immCodeUsesAPFloat() const {
1106 bool Unset;
1107 // The return value will be false when IsAPFloat is unset.
1108 return getOrigPatFragRecord()->getRecord()->getValueAsBitOrUnset("IsAPFloat",
1109 Unset);
1110}
1111
1112bool TreePredicateFn::isPredefinedPredicateEqualTo(StringRef Field,
1113 bool Value) const {
1114 bool Unset;
1115 bool Result =
1116 getOrigPatFragRecord()->getRecord()->getValueAsBitOrUnset(Field, Unset);
1117 if (Unset)
1118 return false;
1119 return Result == Value;
1120}
1121bool TreePredicateFn::usesOperands() const {
1122 return isPredefinedPredicateEqualTo("PredicateCodeUsesOperands", true);
1123}
1124bool TreePredicateFn::isLoad() const {
1125 return isPredefinedPredicateEqualTo("IsLoad", true);
1126}
1127bool TreePredicateFn::isStore() const {
1128 return isPredefinedPredicateEqualTo("IsStore", true);
1129}
1130bool TreePredicateFn::isAtomic() const {
1131 return isPredefinedPredicateEqualTo("IsAtomic", true);
1132}
1133bool TreePredicateFn::isUnindexed() const {
1134 return isPredefinedPredicateEqualTo("IsUnindexed", true);
1135}
1136bool TreePredicateFn::isNonExtLoad() const {
1137 return isPredefinedPredicateEqualTo("IsNonExtLoad", true);
1138}
1139bool TreePredicateFn::isAnyExtLoad() const {
1140 return isPredefinedPredicateEqualTo("IsAnyExtLoad", true);
1141}
1142bool TreePredicateFn::isSignExtLoad() const {
1143 return isPredefinedPredicateEqualTo("IsSignExtLoad", true);
1144}
1145bool TreePredicateFn::isZeroExtLoad() const {
1146 return isPredefinedPredicateEqualTo("IsZeroExtLoad", true);
1147}
1148bool TreePredicateFn::isNonTruncStore() const {
1149 return isPredefinedPredicateEqualTo("IsTruncStore", false);
1150}
1151bool TreePredicateFn::isTruncStore() const {
1152 return isPredefinedPredicateEqualTo("IsTruncStore", true);
1153}
1154bool TreePredicateFn::isAtomicOrderingMonotonic() const {
1155 return isPredefinedPredicateEqualTo("IsAtomicOrderingMonotonic", true);
1156}
1157bool TreePredicateFn::isAtomicOrderingAcquire() const {
1158 return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquire", true);
1159}
1160bool TreePredicateFn::isAtomicOrderingRelease() const {
1161 return isPredefinedPredicateEqualTo("IsAtomicOrderingRelease", true);
1162}
1163bool TreePredicateFn::isAtomicOrderingAcquireRelease() const {
1164 return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireRelease", true);
1165}
1166bool TreePredicateFn::isAtomicOrderingSequentiallyConsistent() const {
1167 return isPredefinedPredicateEqualTo("IsAtomicOrderingSequentiallyConsistent",
1168 true);
1169}
1170bool TreePredicateFn::isAtomicOrderingAcquireOrStronger() const {
1171 return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireOrStronger", true);
1172}
1173bool TreePredicateFn::isAtomicOrderingWeakerThanAcquire() const {
1174 return isPredefinedPredicateEqualTo("IsAtomicOrderingAcquireOrStronger", false);
1175}
1176bool TreePredicateFn::isAtomicOrderingReleaseOrStronger() const {
1177 return isPredefinedPredicateEqualTo("IsAtomicOrderingReleaseOrStronger", true);
1178}
1179bool TreePredicateFn::isAtomicOrderingWeakerThanRelease() const {
1180 return isPredefinedPredicateEqualTo("IsAtomicOrderingReleaseOrStronger", false);
1181}
1182Record *TreePredicateFn::getMemoryVT() const {
1183 Record *R = getOrigPatFragRecord()->getRecord();
1184 if (R->isValueUnset("MemoryVT"))
1185 return nullptr;
1186 return R->getValueAsDef("MemoryVT");
1187}
1188
1189ListInit *TreePredicateFn::getAddressSpaces() const {
1190 Record *R = getOrigPatFragRecord()->getRecord();
1191 if (R->isValueUnset("AddressSpaces"))
1192 return nullptr;
1193 return R->getValueAsListInit("AddressSpaces");
1194}
1195
1196int64_t TreePredicateFn::getMinAlignment() const {
1197 Record *R = getOrigPatFragRecord()->getRecord();
1198 if (R->isValueUnset("MinAlignment"))
1199 return 0;
1200 return R->getValueAsInt("MinAlignment");
1201}
1202
1203Record *TreePredicateFn::getScalarMemoryVT() const {
1204 Record *R = getOrigPatFragRecord()->getRecord();
1205 if (R->isValueUnset("ScalarMemoryVT"))
1206 return nullptr;
1207 return R->getValueAsDef("ScalarMemoryVT");
1208}
1209bool TreePredicateFn::hasGISelPredicateCode() const {
1210 return !PatFragRec->getRecord()
1211 ->getValueAsString("GISelPredicateCode")
1212 .empty();
1213}
1214std::string TreePredicateFn::getGISelPredicateCode() const {
1215 return PatFragRec->getRecord()->getValueAsString("GISelPredicateCode");
1216}
1217
1218StringRef TreePredicateFn::getImmType() const {
1219 if (immCodeUsesAPInt())
1220 return "const APInt &";
1221 if (immCodeUsesAPFloat())
1222 return "const APFloat &";
1223 return "int64_t";
1224}
1225
1226StringRef TreePredicateFn::getImmTypeIdentifier() const {
1227 if (immCodeUsesAPInt())
1228 return "APInt";
1229 else if (immCodeUsesAPFloat())
1230 return "APFloat";
1231 return "I64";
1232}
1233
1234/// isAlwaysTrue - Return true if this is a noop predicate.
1235bool TreePredicateFn::isAlwaysTrue() const {
1236 return !hasPredCode() && !hasImmCode();
1237}
1238
1239/// Return the name to use in the generated code to reference this, this is
1240/// "Predicate_foo" if from a pattern fragment "foo".
1241std::string TreePredicateFn::getFnName() const {
1242 return "Predicate_" + PatFragRec->getRecord()->getName().str();
1243}
1244
1245/// getCodeToRunOnSDNode - Return the code for the function body that
1246/// evaluates this predicate. The argument is expected to be in "Node",
1247/// not N. This handles casting and conversion to a concrete node type as
1248/// appropriate.
1249std::string TreePredicateFn::getCodeToRunOnSDNode() const {
1250 // Handle immediate predicates first.
1251 std::string ImmCode = getImmCode();
1252 if (!ImmCode.empty()) {
1253 if (isLoad())
1254 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
1255 "IsLoad cannot be used with ImmLeaf or its subclasses");
1256 if (isStore())
1257 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
1258 "IsStore cannot be used with ImmLeaf or its subclasses");
1259 if (isUnindexed())
1260 PrintFatalError(
1261 getOrigPatFragRecord()->getRecord()->getLoc(),
1262 "IsUnindexed cannot be used with ImmLeaf or its subclasses");
1263 if (isNonExtLoad())
1264 PrintFatalError(
1265 getOrigPatFragRecord()->getRecord()->getLoc(),
1266 "IsNonExtLoad cannot be used with ImmLeaf or its subclasses");
1267 if (isAnyExtLoad())
1268 PrintFatalError(
1269 getOrigPatFragRecord()->getRecord()->getLoc(),
1270 "IsAnyExtLoad cannot be used with ImmLeaf or its subclasses");
1271 if (isSignExtLoad())
1272 PrintFatalError(
1273 getOrigPatFragRecord()->getRecord()->getLoc(),
1274 "IsSignExtLoad cannot be used with ImmLeaf or its subclasses");
1275 if (isZeroExtLoad())
1276 PrintFatalError(
1277 getOrigPatFragRecord()->getRecord()->getLoc(),
1278 "IsZeroExtLoad cannot be used with ImmLeaf or its subclasses");
1279 if (isNonTruncStore())
1280 PrintFatalError(
1281 getOrigPatFragRecord()->getRecord()->getLoc(),
1282 "IsNonTruncStore cannot be used with ImmLeaf or its subclasses");
1283 if (isTruncStore())
1284 PrintFatalError(
1285 getOrigPatFragRecord()->getRecord()->getLoc(),
1286 "IsTruncStore cannot be used with ImmLeaf or its subclasses");
1287 if (getMemoryVT())
1288 PrintFatalError(getOrigPatFragRecord()->getRecord()->getLoc(),
1289 "MemoryVT cannot be used with ImmLeaf or its subclasses");
1290 if (getScalarMemoryVT())
1291 PrintFatalError(
1292 getOrigPatFragRecord()->getRecord()->getLoc(),
1293 "ScalarMemoryVT cannot be used with ImmLeaf or its subclasses");
1294
1295 std::string Result = (" " + getImmType() + " Imm = ").str();
1296 if (immCodeUsesAPFloat())
1297 Result += "cast<ConstantFPSDNode>(Node)->getValueAPF();\n";
1298 else if (immCodeUsesAPInt())
1299 Result += "cast<ConstantSDNode>(Node)->getAPIntValue();\n";
1300 else
1301 Result += "cast<ConstantSDNode>(Node)->getSExtValue();\n";
1302 return Result + ImmCode;
1303 }
1304
1305 // Handle arbitrary node predicates.
1306 assert(hasPredCode() && "Don't have any predicate code!")((hasPredCode() && "Don't have any predicate code!") ?
static_cast<void> (0) : __assert_fail ("hasPredCode() && \"Don't have any predicate code!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1306, __PRETTY_FUNCTION__))
;
1307 StringRef ClassName;
1308 if (PatFragRec->getOnlyTree()->isLeaf())
1309 ClassName = "SDNode";
1310 else {
1311 Record *Op = PatFragRec->getOnlyTree()->getOperator();
1312 ClassName = PatFragRec->getDAGPatterns().getSDNodeInfo(Op).getSDClassName();
1313 }
1314 std::string Result;
1315 if (ClassName == "SDNode")
1316 Result = " SDNode *N = Node;\n";
1317 else
1318 Result = " auto *N = cast<" + ClassName.str() + ">(Node);\n";
1319
1320 return (Twine(Result) + " (void)N;\n" + getPredCode()).str();
1321}
1322
1323//===----------------------------------------------------------------------===//
1324// PatternToMatch implementation
1325//
1326
1327static bool isImmAllOnesAllZerosMatch(const TreePatternNode *P) {
1328 if (!P->isLeaf())
1329 return false;
1330 DefInit *DI = dyn_cast<DefInit>(P->getLeafValue());
1331 if (!DI)
1332 return false;
1333
1334 Record *R = DI->getDef();
1335 return R->getName() == "immAllOnesV" || R->getName() == "immAllZerosV";
1336}
1337
1338/// getPatternSize - Return the 'size' of this pattern. We want to match large
1339/// patterns before small ones. This is used to determine the size of a
1340/// pattern.
1341static unsigned getPatternSize(const TreePatternNode *P,
1342 const CodeGenDAGPatterns &CGP) {
1343 unsigned Size = 3; // The node itself.
1344 // If the root node is a ConstantSDNode, increases its size.
1345 // e.g. (set R32:$dst, 0).
1346 if (P->isLeaf() && isa<IntInit>(P->getLeafValue()))
1347 Size += 2;
1348
1349 if (const ComplexPattern *AM = P->getComplexPatternInfo(CGP)) {
1350 Size += AM->getComplexity();
1351 // We don't want to count any children twice, so return early.
1352 return Size;
1353 }
1354
1355 // If this node has some predicate function that must match, it adds to the
1356 // complexity of this node.
1357 if (!P->getPredicateCalls().empty())
1358 ++Size;
1359
1360 // Count children in the count if they are also nodes.
1361 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i) {
1362 const TreePatternNode *Child = P->getChild(i);
1363 if (!Child->isLeaf() && Child->getNumTypes()) {
1364 const TypeSetByHwMode &T0 = Child->getExtType(0);
1365 // At this point, all variable type sets should be simple, i.e. only
1366 // have a default mode.
1367 if (T0.getMachineValueType() != MVT::Other) {
1368 Size += getPatternSize(Child, CGP);
1369 continue;
1370 }
1371 }
1372 if (Child->isLeaf()) {
1373 if (isa<IntInit>(Child->getLeafValue()))
1374 Size += 5; // Matches a ConstantSDNode (+3) and a specific value (+2).
1375 else if (Child->getComplexPatternInfo(CGP))
1376 Size += getPatternSize(Child, CGP);
1377 else if (isImmAllOnesAllZerosMatch(Child))
1378 Size += 4; // Matches a build_vector(+3) and a predicate (+1).
1379 else if (!Child->getPredicateCalls().empty())
1380 ++Size;
1381 }
1382 }
1383
1384 return Size;
1385}
1386
1387/// Compute the complexity metric for the input pattern. This roughly
1388/// corresponds to the number of nodes that are covered.
1389int PatternToMatch::
1390getPatternComplexity(const CodeGenDAGPatterns &CGP) const {
1391 return getPatternSize(getSrcPattern(), CGP) + getAddedComplexity();
1392}
1393
1394/// getPredicateCheck - Return a single string containing all of this
1395/// pattern's predicates concatenated with "&&" operators.
1396///
1397std::string PatternToMatch::getPredicateCheck() const {
1398 SmallVector<const Predicate*,4> PredList;
1399 for (const Predicate &P : Predicates) {
1400 if (!P.getCondString().empty())
1401 PredList.push_back(&P);
1402 }
1403 llvm::sort(PredList, deref<std::less<>>());
1404
1405 std::string Check;
1406 for (unsigned i = 0, e = PredList.size(); i != e; ++i) {
1407 if (i != 0)
1408 Check += " && ";
1409 Check += '(' + PredList[i]->getCondString() + ')';
1410 }
1411 return Check;
1412}
1413
1414//===----------------------------------------------------------------------===//
1415// SDTypeConstraint implementation
1416//
1417
1418SDTypeConstraint::SDTypeConstraint(Record *R, const CodeGenHwModes &CGH) {
1419 OperandNo = R->getValueAsInt("OperandNum");
1420
1421 if (R->isSubClassOf("SDTCisVT")) {
1422 ConstraintType = SDTCisVT;
1423 VVT = getValueTypeByHwMode(R->getValueAsDef("VT"), CGH);
1424 for (const auto &P : VVT)
1425 if (P.second == MVT::isVoid)
1426 PrintFatalError(R->getLoc(), "Cannot use 'Void' as type to SDTCisVT");
1427 } else if (R->isSubClassOf("SDTCisPtrTy")) {
1428 ConstraintType = SDTCisPtrTy;
1429 } else if (R->isSubClassOf("SDTCisInt")) {
1430 ConstraintType = SDTCisInt;
1431 } else if (R->isSubClassOf("SDTCisFP")) {
1432 ConstraintType = SDTCisFP;
1433 } else if (R->isSubClassOf("SDTCisVec")) {
1434 ConstraintType = SDTCisVec;
1435 } else if (R->isSubClassOf("SDTCisSameAs")) {
1436 ConstraintType = SDTCisSameAs;
1437 x.SDTCisSameAs_Info.OtherOperandNum = R->getValueAsInt("OtherOperandNum");
1438 } else if (R->isSubClassOf("SDTCisVTSmallerThanOp")) {
1439 ConstraintType = SDTCisVTSmallerThanOp;
1440 x.SDTCisVTSmallerThanOp_Info.OtherOperandNum =
1441 R->getValueAsInt("OtherOperandNum");
1442 } else if (R->isSubClassOf("SDTCisOpSmallerThanOp")) {
1443 ConstraintType = SDTCisOpSmallerThanOp;
1444 x.SDTCisOpSmallerThanOp_Info.BigOperandNum =
1445 R->getValueAsInt("BigOperandNum");
1446 } else if (R->isSubClassOf("SDTCisEltOfVec")) {
1447 ConstraintType = SDTCisEltOfVec;
1448 x.SDTCisEltOfVec_Info.OtherOperandNum = R->getValueAsInt("OtherOpNum");
1449 } else if (R->isSubClassOf("SDTCisSubVecOfVec")) {
1450 ConstraintType = SDTCisSubVecOfVec;
1451 x.SDTCisSubVecOfVec_Info.OtherOperandNum =
1452 R->getValueAsInt("OtherOpNum");
1453 } else if (R->isSubClassOf("SDTCVecEltisVT")) {
1454 ConstraintType = SDTCVecEltisVT;
1455 VVT = getValueTypeByHwMode(R->getValueAsDef("VT"), CGH);
1456 for (const auto &P : VVT) {
1457 MVT T = P.second;
1458 if (T.isVector())
1459 PrintFatalError(R->getLoc(),
1460 "Cannot use vector type as SDTCVecEltisVT");
1461 if (!T.isInteger() && !T.isFloatingPoint())
1462 PrintFatalError(R->getLoc(), "Must use integer or floating point type "
1463 "as SDTCVecEltisVT");
1464 }
1465 } else if (R->isSubClassOf("SDTCisSameNumEltsAs")) {
1466 ConstraintType = SDTCisSameNumEltsAs;
1467 x.SDTCisSameNumEltsAs_Info.OtherOperandNum =
1468 R->getValueAsInt("OtherOperandNum");
1469 } else if (R->isSubClassOf("SDTCisSameSizeAs")) {
1470 ConstraintType = SDTCisSameSizeAs;
1471 x.SDTCisSameSizeAs_Info.OtherOperandNum =
1472 R->getValueAsInt("OtherOperandNum");
1473 } else {
1474 PrintFatalError(R->getLoc(),
1475 "Unrecognized SDTypeConstraint '" + R->getName() + "'!\n");
1476 }
1477}
1478
1479/// getOperandNum - Return the node corresponding to operand #OpNo in tree
1480/// N, and the result number in ResNo.
1481static TreePatternNode *getOperandNum(unsigned OpNo, TreePatternNode *N,
1482 const SDNodeInfo &NodeInfo,
1483 unsigned &ResNo) {
1484 unsigned NumResults = NodeInfo.getNumResults();
1485 if (OpNo < NumResults) {
1486 ResNo = OpNo;
1487 return N;
1488 }
1489
1490 OpNo -= NumResults;
1491
1492 if (OpNo >= N->getNumChildren()) {
1493 std::string S;
1494 raw_string_ostream OS(S);
1495 OS << "Invalid operand number in type constraint "
1496 << (OpNo+NumResults) << " ";
1497 N->print(OS);
1498 PrintFatalError(OS.str());
1499 }
1500
1501 return N->getChild(OpNo);
1502}
1503
1504/// ApplyTypeConstraint - Given a node in a pattern, apply this type
1505/// constraint to the nodes operands. This returns true if it makes a
1506/// change, false otherwise. If a type contradiction is found, flag an error.
1507bool SDTypeConstraint::ApplyTypeConstraint(TreePatternNode *N,
1508 const SDNodeInfo &NodeInfo,
1509 TreePattern &TP) const {
1510 if (TP.hasError())
1511 return false;
1512
1513 unsigned ResNo = 0; // The result number being referenced.
1514 TreePatternNode *NodeToApply = getOperandNum(OperandNo, N, NodeInfo, ResNo);
1515 TypeInfer &TI = TP.getInfer();
1516
1517 switch (ConstraintType) {
1518 case SDTCisVT:
1519 // Operand must be a particular type.
1520 return NodeToApply->UpdateNodeType(ResNo, VVT, TP);
1521 case SDTCisPtrTy:
1522 // Operand must be same as target pointer type.
1523 return NodeToApply->UpdateNodeType(ResNo, MVT::iPTR, TP);
1524 case SDTCisInt:
1525 // Require it to be one of the legal integer VTs.
1526 return TI.EnforceInteger(NodeToApply->getExtType(ResNo));
1527 case SDTCisFP:
1528 // Require it to be one of the legal fp VTs.
1529 return TI.EnforceFloatingPoint(NodeToApply->getExtType(ResNo));
1530 case SDTCisVec:
1531 // Require it to be one of the legal vector VTs.
1532 return TI.EnforceVector(NodeToApply->getExtType(ResNo));
1533 case SDTCisSameAs: {
1534 unsigned OResNo = 0;
1535 TreePatternNode *OtherNode =
1536 getOperandNum(x.SDTCisSameAs_Info.OtherOperandNum, N, NodeInfo, OResNo);
1537 return NodeToApply->UpdateNodeType(ResNo, OtherNode->getExtType(OResNo),TP)|
1538 OtherNode->UpdateNodeType(OResNo,NodeToApply->getExtType(ResNo),TP);
1539 }
1540 case SDTCisVTSmallerThanOp: {
1541 // The NodeToApply must be a leaf node that is a VT. OtherOperandNum must
1542 // have an integer type that is smaller than the VT.
1543 if (!NodeToApply->isLeaf() ||
1544 !isa<DefInit>(NodeToApply->getLeafValue()) ||
1545 !static_cast<DefInit*>(NodeToApply->getLeafValue())->getDef()
1546 ->isSubClassOf("ValueType")) {
1547 TP.error(N->getOperator()->getName() + " expects a VT operand!");
1548 return false;
1549 }
1550 DefInit *DI = static_cast<DefInit*>(NodeToApply->getLeafValue());
1551 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
1552 auto VVT = getValueTypeByHwMode(DI->getDef(), T.getHwModes());
1553 TypeSetByHwMode TypeListTmp(VVT);
1554
1555 unsigned OResNo = 0;
1556 TreePatternNode *OtherNode =
1557 getOperandNum(x.SDTCisVTSmallerThanOp_Info.OtherOperandNum, N, NodeInfo,
1558 OResNo);
1559
1560 return TI.EnforceSmallerThan(TypeListTmp, OtherNode->getExtType(OResNo));
1561 }
1562 case SDTCisOpSmallerThanOp: {
1563 unsigned BResNo = 0;
1564 TreePatternNode *BigOperand =
1565 getOperandNum(x.SDTCisOpSmallerThanOp_Info.BigOperandNum, N, NodeInfo,
1566 BResNo);
1567 return TI.EnforceSmallerThan(NodeToApply->getExtType(ResNo),
1568 BigOperand->getExtType(BResNo));
1569 }
1570 case SDTCisEltOfVec: {
1571 unsigned VResNo = 0;
1572 TreePatternNode *VecOperand =
1573 getOperandNum(x.SDTCisEltOfVec_Info.OtherOperandNum, N, NodeInfo,
1574 VResNo);
1575 // Filter vector types out of VecOperand that don't have the right element
1576 // type.
1577 return TI.EnforceVectorEltTypeIs(VecOperand->getExtType(VResNo),
1578 NodeToApply->getExtType(ResNo));
1579 }
1580 case SDTCisSubVecOfVec: {
1581 unsigned VResNo = 0;
1582 TreePatternNode *BigVecOperand =
1583 getOperandNum(x.SDTCisSubVecOfVec_Info.OtherOperandNum, N, NodeInfo,
1584 VResNo);
1585
1586 // Filter vector types out of BigVecOperand that don't have the
1587 // right subvector type.
1588 return TI.EnforceVectorSubVectorTypeIs(BigVecOperand->getExtType(VResNo),
1589 NodeToApply->getExtType(ResNo));
1590 }
1591 case SDTCVecEltisVT: {
1592 return TI.EnforceVectorEltTypeIs(NodeToApply->getExtType(ResNo), VVT);
1593 }
1594 case SDTCisSameNumEltsAs: {
1595 unsigned OResNo = 0;
1596 TreePatternNode *OtherNode =
1597 getOperandNum(x.SDTCisSameNumEltsAs_Info.OtherOperandNum,
1598 N, NodeInfo, OResNo);
1599 return TI.EnforceSameNumElts(OtherNode->getExtType(OResNo),
1600 NodeToApply->getExtType(ResNo));
1601 }
1602 case SDTCisSameSizeAs: {
1603 unsigned OResNo = 0;
1604 TreePatternNode *OtherNode =
1605 getOperandNum(x.SDTCisSameSizeAs_Info.OtherOperandNum,
1606 N, NodeInfo, OResNo);
1607 return TI.EnforceSameSize(OtherNode->getExtType(OResNo),
1608 NodeToApply->getExtType(ResNo));
1609 }
1610 }
1611 llvm_unreachable("Invalid ConstraintType!")::llvm::llvm_unreachable_internal("Invalid ConstraintType!", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1611)
;
1612}
1613
1614// Update the node type to match an instruction operand or result as specified
1615// in the ins or outs lists on the instruction definition. Return true if the
1616// type was actually changed.
1617bool TreePatternNode::UpdateNodeTypeFromInst(unsigned ResNo,
1618 Record *Operand,
1619 TreePattern &TP) {
1620 // The 'unknown' operand indicates that types should be inferred from the
1621 // context.
1622 if (Operand->isSubClassOf("unknown_class"))
1623 return false;
1624
1625 // The Operand class specifies a type directly.
1626 if (Operand->isSubClassOf("Operand")) {
1627 Record *R = Operand->getValueAsDef("Type");
1628 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
1629 return UpdateNodeType(ResNo, getValueTypeByHwMode(R, T.getHwModes()), TP);
1630 }
1631
1632 // PointerLikeRegClass has a type that is determined at runtime.
1633 if (Operand->isSubClassOf("PointerLikeRegClass"))
1634 return UpdateNodeType(ResNo, MVT::iPTR, TP);
1635
1636 // Both RegisterClass and RegisterOperand operands derive their types from a
1637 // register class def.
1638 Record *RC = nullptr;
1639 if (Operand->isSubClassOf("RegisterClass"))
1640 RC = Operand;
1641 else if (Operand->isSubClassOf("RegisterOperand"))
1642 RC = Operand->getValueAsDef("RegClass");
1643
1644 assert(RC && "Unknown operand type")((RC && "Unknown operand type") ? static_cast<void
> (0) : __assert_fail ("RC && \"Unknown operand type\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1644, __PRETTY_FUNCTION__))
;
1645 CodeGenTarget &Tgt = TP.getDAGPatterns().getTargetInfo();
1646 return UpdateNodeType(ResNo, Tgt.getRegisterClass(RC).getValueTypes(), TP);
1647}
1648
1649bool TreePatternNode::ContainsUnresolvedType(TreePattern &TP) const {
1650 for (unsigned i = 0, e = Types.size(); i != e; ++i)
1651 if (!TP.getInfer().isConcrete(Types[i], true))
1652 return true;
1653 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
1654 if (getChild(i)->ContainsUnresolvedType(TP))
1655 return true;
1656 return false;
1657}
1658
1659bool TreePatternNode::hasProperTypeByHwMode() const {
1660 for (const TypeSetByHwMode &S : Types)
1661 if (!S.isDefaultOnly())
1662 return true;
1663 for (const TreePatternNodePtr &C : Children)
1664 if (C->hasProperTypeByHwMode())
1665 return true;
1666 return false;
1667}
1668
1669bool TreePatternNode::hasPossibleType() const {
1670 for (const TypeSetByHwMode &S : Types)
1671 if (!S.isPossible())
1672 return false;
1673 for (const TreePatternNodePtr &C : Children)
1674 if (!C->hasPossibleType())
1675 return false;
1676 return true;
1677}
1678
1679bool TreePatternNode::setDefaultMode(unsigned Mode) {
1680 for (TypeSetByHwMode &S : Types) {
1681 S.makeSimple(Mode);
1682 // Check if the selected mode had a type conflict.
1683 if (S.get(DefaultMode).empty())
1684 return false;
1685 }
1686 for (const TreePatternNodePtr &C : Children)
1687 if (!C->setDefaultMode(Mode))
1688 return false;
1689 return true;
1690}
1691
1692//===----------------------------------------------------------------------===//
1693// SDNodeInfo implementation
1694//
1695SDNodeInfo::SDNodeInfo(Record *R, const CodeGenHwModes &CGH) : Def(R) {
1696 EnumName = R->getValueAsString("Opcode");
1697 SDClassName = R->getValueAsString("SDClass");
1698 Record *TypeProfile = R->getValueAsDef("TypeProfile");
1699 NumResults = TypeProfile->getValueAsInt("NumResults");
1700 NumOperands = TypeProfile->getValueAsInt("NumOperands");
1701
1702 // Parse the properties.
1703 Properties = parseSDPatternOperatorProperties(R);
1704
1705 // Parse the type constraints.
1706 std::vector<Record*> ConstraintList =
1707 TypeProfile->getValueAsListOfDefs("Constraints");
1708 for (Record *R : ConstraintList)
1709 TypeConstraints.emplace_back(R, CGH);
1710}
1711
1712/// getKnownType - If the type constraints on this node imply a fixed type
1713/// (e.g. all stores return void, etc), then return it as an
1714/// MVT::SimpleValueType. Otherwise, return EEVT::Other.
1715MVT::SimpleValueType SDNodeInfo::getKnownType(unsigned ResNo) const {
1716 unsigned NumResults = getNumResults();
1717 assert(NumResults <= 1 &&((NumResults <= 1 && "We only work with nodes with zero or one result so far!"
) ? static_cast<void> (0) : __assert_fail ("NumResults <= 1 && \"We only work with nodes with zero or one result so far!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1718, __PRETTY_FUNCTION__))
1718 "We only work with nodes with zero or one result so far!")((NumResults <= 1 && "We only work with nodes with zero or one result so far!"
) ? static_cast<void> (0) : __assert_fail ("NumResults <= 1 && \"We only work with nodes with zero or one result so far!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1718, __PRETTY_FUNCTION__))
;
1719 assert(ResNo == 0 && "Only handles single result nodes so far")((ResNo == 0 && "Only handles single result nodes so far"
) ? static_cast<void> (0) : __assert_fail ("ResNo == 0 && \"Only handles single result nodes so far\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1719, __PRETTY_FUNCTION__))
;
1720
1721 for (const SDTypeConstraint &Constraint : TypeConstraints) {
1722 // Make sure that this applies to the correct node result.
1723 if (Constraint.OperandNo >= NumResults) // FIXME: need value #
1724 continue;
1725
1726 switch (Constraint.ConstraintType) {
1727 default: break;
1728 case SDTypeConstraint::SDTCisVT:
1729 if (Constraint.VVT.isSimple())
1730 return Constraint.VVT.getSimple().SimpleTy;
1731 break;
1732 case SDTypeConstraint::SDTCisPtrTy:
1733 return MVT::iPTR;
1734 }
1735 }
1736 return MVT::Other;
1737}
1738
1739//===----------------------------------------------------------------------===//
1740// TreePatternNode implementation
1741//
1742
1743static unsigned GetNumNodeResults(Record *Operator, CodeGenDAGPatterns &CDP) {
1744 if (Operator->getName() == "set" ||
1745 Operator->getName() == "implicit")
1746 return 0; // All return nothing.
1747
1748 if (Operator->isSubClassOf("Intrinsic"))
1749 return CDP.getIntrinsic(Operator).IS.RetVTs.size();
1750
1751 if (Operator->isSubClassOf("SDNode"))
1752 return CDP.getSDNodeInfo(Operator).getNumResults();
1753
1754 if (Operator->isSubClassOf("PatFrags")) {
1755 // If we've already parsed this pattern fragment, get it. Otherwise, handle
1756 // the forward reference case where one pattern fragment references another
1757 // before it is processed.
1758 if (TreePattern *PFRec = CDP.getPatternFragmentIfRead(Operator)) {
1759 // The number of results of a fragment with alternative records is the
1760 // maximum number of results across all alternatives.
1761 unsigned NumResults = 0;
1762 for (auto T : PFRec->getTrees())
1763 NumResults = std::max(NumResults, T->getNumTypes());
1764 return NumResults;
1765 }
1766
1767 ListInit *LI = Operator->getValueAsListInit("Fragments");
1768 assert(LI && "Invalid Fragment")((LI && "Invalid Fragment") ? static_cast<void>
(0) : __assert_fail ("LI && \"Invalid Fragment\"", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1768, __PRETTY_FUNCTION__))
;
1769 unsigned NumResults = 0;
1770 for (Init *I : LI->getValues()) {
1771 Record *Op = nullptr;
1772 if (DagInit *Dag = dyn_cast<DagInit>(I))
1773 if (DefInit *DI = dyn_cast<DefInit>(Dag->getOperator()))
1774 Op = DI->getDef();
1775 assert(Op && "Invalid Fragment")((Op && "Invalid Fragment") ? static_cast<void>
(0) : __assert_fail ("Op && \"Invalid Fragment\"", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1775, __PRETTY_FUNCTION__))
;
1776 NumResults = std::max(NumResults, GetNumNodeResults(Op, CDP));
1777 }
1778 return NumResults;
1779 }
1780
1781 if (Operator->isSubClassOf("Instruction")) {
1782 CodeGenInstruction &InstInfo = CDP.getTargetInfo().getInstruction(Operator);
1783
1784 unsigned NumDefsToAdd = InstInfo.Operands.NumDefs;
1785
1786 // Subtract any defaulted outputs.
1787 for (unsigned i = 0; i != InstInfo.Operands.NumDefs; ++i) {
1788 Record *OperandNode = InstInfo.Operands[i].Rec;
1789
1790 if (OperandNode->isSubClassOf("OperandWithDefaultOps") &&
1791 !CDP.getDefaultOperand(OperandNode).DefaultOps.empty())
1792 --NumDefsToAdd;
1793 }
1794
1795 // Add on one implicit def if it has a resolvable type.
1796 if (InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo()) !=MVT::Other)
1797 ++NumDefsToAdd;
1798 return NumDefsToAdd;
1799 }
1800
1801 if (Operator->isSubClassOf("SDNodeXForm"))
1802 return 1; // FIXME: Generalize SDNodeXForm
1803
1804 if (Operator->isSubClassOf("ValueType"))
1805 return 1; // A type-cast of one result.
1806
1807 if (Operator->isSubClassOf("ComplexPattern"))
1808 return 1;
1809
1810 errs() << *Operator;
1811 PrintFatalError("Unhandled node in GetNumNodeResults");
1812}
1813
1814void TreePatternNode::print(raw_ostream &OS) const {
1815 if (isLeaf())
1816 OS << *getLeafValue();
1817 else
1818 OS << '(' << getOperator()->getName();
1819
1820 for (unsigned i = 0, e = Types.size(); i != e; ++i) {
1821 OS << ':';
1822 getExtType(i).writeToStream(OS);
1823 }
1824
1825 if (!isLeaf()) {
1826 if (getNumChildren() != 0) {
1827 OS << " ";
1828 getChild(0)->print(OS);
1829 for (unsigned i = 1, e = getNumChildren(); i != e; ++i) {
1830 OS << ", ";
1831 getChild(i)->print(OS);
1832 }
1833 }
1834 OS << ")";
1835 }
1836
1837 for (const TreePredicateCall &Pred : PredicateCalls) {
1838 OS << "<<P:";
1839 if (Pred.Scope)
1840 OS << Pred.Scope << ":";
1841 OS << Pred.Fn.getFnName() << ">>";
1842 }
1843 if (TransformFn)
1844 OS << "<<X:" << TransformFn->getName() << ">>";
1845 if (!getName().empty())
1846 OS << ":$" << getName();
1847
1848 for (const ScopedName &Name : NamesAsPredicateArg)
1849 OS << ":$pred:" << Name.getScope() << ":" << Name.getIdentifier();
1850}
1851void TreePatternNode::dump() const {
1852 print(errs());
1853}
1854
1855/// isIsomorphicTo - Return true if this node is recursively
1856/// isomorphic to the specified node. For this comparison, the node's
1857/// entire state is considered. The assigned name is ignored, since
1858/// nodes with differing names are considered isomorphic. However, if
1859/// the assigned name is present in the dependent variable set, then
1860/// the assigned name is considered significant and the node is
1861/// isomorphic if the names match.
1862bool TreePatternNode::isIsomorphicTo(const TreePatternNode *N,
1863 const MultipleUseVarSet &DepVars) const {
1864 if (N == this) return true;
1865 if (N->isLeaf() != isLeaf() || getExtTypes() != N->getExtTypes() ||
1866 getPredicateCalls() != N->getPredicateCalls() ||
1867 getTransformFn() != N->getTransformFn())
1868 return false;
1869
1870 if (isLeaf()) {
1871 if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) {
1872 if (DefInit *NDI = dyn_cast<DefInit>(N->getLeafValue())) {
1873 return ((DI->getDef() == NDI->getDef())
1874 && (DepVars.find(getName()) == DepVars.end()
1875 || getName() == N->getName()));
1876 }
1877 }
1878 return getLeafValue() == N->getLeafValue();
1879 }
1880
1881 if (N->getOperator() != getOperator() ||
1882 N->getNumChildren() != getNumChildren()) return false;
1883 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
1884 if (!getChild(i)->isIsomorphicTo(N->getChild(i), DepVars))
1885 return false;
1886 return true;
1887}
1888
1889/// clone - Make a copy of this tree and all of its children.
1890///
1891TreePatternNodePtr TreePatternNode::clone() const {
1892 TreePatternNodePtr New;
1893 if (isLeaf()) {
1894 New = std::make_shared<TreePatternNode>(getLeafValue(), getNumTypes());
1895 } else {
1896 std::vector<TreePatternNodePtr> CChildren;
1897 CChildren.reserve(Children.size());
1898 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
1899 CChildren.push_back(getChild(i)->clone());
1900 New = std::make_shared<TreePatternNode>(getOperator(), std::move(CChildren),
1901 getNumTypes());
1902 }
1903 New->setName(getName());
1904 New->setNamesAsPredicateArg(getNamesAsPredicateArg());
1905 New->Types = Types;
1906 New->setPredicateCalls(getPredicateCalls());
1907 New->setTransformFn(getTransformFn());
1908 return New;
1909}
1910
1911/// RemoveAllTypes - Recursively strip all the types of this tree.
1912void TreePatternNode::RemoveAllTypes() {
1913 // Reset to unknown type.
1914 std::fill(Types.begin(), Types.end(), TypeSetByHwMode());
1915 if (isLeaf()) return;
1916 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
1917 getChild(i)->RemoveAllTypes();
1918}
1919
1920
1921/// SubstituteFormalArguments - Replace the formal arguments in this tree
1922/// with actual values specified by ArgMap.
1923void TreePatternNode::SubstituteFormalArguments(
1924 std::map<std::string, TreePatternNodePtr> &ArgMap) {
1925 if (isLeaf()) return;
1926
1927 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
1928 TreePatternNode *Child = getChild(i);
1929 if (Child->isLeaf()) {
1930 Init *Val = Child->getLeafValue();
1931 // Note that, when substituting into an output pattern, Val might be an
1932 // UnsetInit.
1933 if (isa<UnsetInit>(Val) || (isa<DefInit>(Val) &&
1934 cast<DefInit>(Val)->getDef()->getName() == "node")) {
1935 // We found a use of a formal argument, replace it with its value.
1936 TreePatternNodePtr NewChild = ArgMap[Child->getName()];
1937 assert(NewChild && "Couldn't find formal argument!")((NewChild && "Couldn't find formal argument!") ? static_cast
<void> (0) : __assert_fail ("NewChild && \"Couldn't find formal argument!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1937, __PRETTY_FUNCTION__))
;
1938 assert((Child->getPredicateCalls().empty() ||(((Child->getPredicateCalls().empty() || NewChild->getPredicateCalls
() == Child->getPredicateCalls()) && "Non-empty child predicate clobbered!"
) ? static_cast<void> (0) : __assert_fail ("(Child->getPredicateCalls().empty() || NewChild->getPredicateCalls() == Child->getPredicateCalls()) && \"Non-empty child predicate clobbered!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1940, __PRETTY_FUNCTION__))
1939 NewChild->getPredicateCalls() == Child->getPredicateCalls()) &&(((Child->getPredicateCalls().empty() || NewChild->getPredicateCalls
() == Child->getPredicateCalls()) && "Non-empty child predicate clobbered!"
) ? static_cast<void> (0) : __assert_fail ("(Child->getPredicateCalls().empty() || NewChild->getPredicateCalls() == Child->getPredicateCalls()) && \"Non-empty child predicate clobbered!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1940, __PRETTY_FUNCTION__))
1940 "Non-empty child predicate clobbered!")(((Child->getPredicateCalls().empty() || NewChild->getPredicateCalls
() == Child->getPredicateCalls()) && "Non-empty child predicate clobbered!"
) ? static_cast<void> (0) : __assert_fail ("(Child->getPredicateCalls().empty() || NewChild->getPredicateCalls() == Child->getPredicateCalls()) && \"Non-empty child predicate clobbered!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1940, __PRETTY_FUNCTION__))
;
1941 setChild(i, std::move(NewChild));
1942 }
1943 } else {
1944 getChild(i)->SubstituteFormalArguments(ArgMap);
1945 }
1946 }
1947}
1948
1949
1950/// InlinePatternFragments - If this pattern refers to any pattern
1951/// fragments, return the set of inlined versions (this can be more than
1952/// one if a PatFrags record has multiple alternatives).
1953void TreePatternNode::InlinePatternFragments(
1954 TreePatternNodePtr T, TreePattern &TP,
1955 std::vector<TreePatternNodePtr> &OutAlternatives) {
1956
1957 if (TP.hasError())
1958 return;
1959
1960 if (isLeaf()) {
1961 OutAlternatives.push_back(T); // nothing to do.
1962 return;
1963 }
1964
1965 Record *Op = getOperator();
1966
1967 if (!Op->isSubClassOf("PatFrags")) {
1968 if (getNumChildren() == 0) {
1969 OutAlternatives.push_back(T);
1970 return;
1971 }
1972
1973 // Recursively inline children nodes.
1974 std::vector<std::vector<TreePatternNodePtr> > ChildAlternatives;
1975 ChildAlternatives.resize(getNumChildren());
1976 for (unsigned i = 0, e = getNumChildren(); i != e; ++i) {
1977 TreePatternNodePtr Child = getChildShared(i);
1978 Child->InlinePatternFragments(Child, TP, ChildAlternatives[i]);
1979 // If there are no alternatives for any child, there are no
1980 // alternatives for this expression as whole.
1981 if (ChildAlternatives[i].empty())
1982 return;
1983
1984 for (auto NewChild : ChildAlternatives[i])
1985 assert((Child->getPredicateCalls().empty() ||(((Child->getPredicateCalls().empty() || NewChild->getPredicateCalls
() == Child->getPredicateCalls()) && "Non-empty child predicate clobbered!"
) ? static_cast<void> (0) : __assert_fail ("(Child->getPredicateCalls().empty() || NewChild->getPredicateCalls() == Child->getPredicateCalls()) && \"Non-empty child predicate clobbered!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1987, __PRETTY_FUNCTION__))
1986 NewChild->getPredicateCalls() == Child->getPredicateCalls()) &&(((Child->getPredicateCalls().empty() || NewChild->getPredicateCalls
() == Child->getPredicateCalls()) && "Non-empty child predicate clobbered!"
) ? static_cast<void> (0) : __assert_fail ("(Child->getPredicateCalls().empty() || NewChild->getPredicateCalls() == Child->getPredicateCalls()) && \"Non-empty child predicate clobbered!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1987, __PRETTY_FUNCTION__))
1987 "Non-empty child predicate clobbered!")(((Child->getPredicateCalls().empty() || NewChild->getPredicateCalls
() == Child->getPredicateCalls()) && "Non-empty child predicate clobbered!"
) ? static_cast<void> (0) : __assert_fail ("(Child->getPredicateCalls().empty() || NewChild->getPredicateCalls() == Child->getPredicateCalls()) && \"Non-empty child predicate clobbered!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 1987, __PRETTY_FUNCTION__))
;
1988 }
1989
1990 // The end result is an all-pairs construction of the resultant pattern.
1991 std::vector<unsigned> Idxs;
1992 Idxs.resize(ChildAlternatives.size());
1993 bool NotDone;
1994 do {
1995 // Create the variant and add it to the output list.
1996 std::vector<TreePatternNodePtr> NewChildren;
1997 for (unsigned i = 0, e = ChildAlternatives.size(); i != e; ++i)
1998 NewChildren.push_back(ChildAlternatives[i][Idxs[i]]);
1999 TreePatternNodePtr R = std::make_shared<TreePatternNode>(
2000 getOperator(), std::move(NewChildren), getNumTypes());
2001
2002 // Copy over properties.
2003 R->setName(getName());
2004 R->setNamesAsPredicateArg(getNamesAsPredicateArg());
2005 R->setPredicateCalls(getPredicateCalls());
2006 R->setTransformFn(getTransformFn());
2007 for (unsigned i = 0, e = getNumTypes(); i != e; ++i)
2008 R->setType(i, getExtType(i));
2009 for (unsigned i = 0, e = getNumResults(); i != e; ++i)
2010 R->setResultIndex(i, getResultIndex(i));
2011
2012 // Register alternative.
2013 OutAlternatives.push_back(R);
2014
2015 // Increment indices to the next permutation by incrementing the
2016 // indices from last index backward, e.g., generate the sequence
2017 // [0, 0], [0, 1], [1, 0], [1, 1].
2018 int IdxsIdx;
2019 for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {
2020 if (++Idxs[IdxsIdx] == ChildAlternatives[IdxsIdx].size())
2021 Idxs[IdxsIdx] = 0;
2022 else
2023 break;
2024 }
2025 NotDone = (IdxsIdx >= 0);
2026 } while (NotDone);
2027
2028 return;
2029 }
2030
2031 // Otherwise, we found a reference to a fragment. First, look up its
2032 // TreePattern record.
2033 TreePattern *Frag = TP.getDAGPatterns().getPatternFragment(Op);
2034
2035 // Verify that we are passing the right number of operands.
2036 if (Frag->getNumArgs() != Children.size()) {
2037 TP.error("'" + Op->getName() + "' fragment requires " +
2038 Twine(Frag->getNumArgs()) + " operands!");
2039 return;
2040 }
2041
2042 TreePredicateFn PredFn(Frag);
2043 unsigned Scope = 0;
2044 if (TreePredicateFn(Frag).usesOperands())
2045 Scope = TP.getDAGPatterns().allocateScope();
2046
2047 // Compute the map of formal to actual arguments.
2048 std::map<std::string, TreePatternNodePtr> ArgMap;
2049 for (unsigned i = 0, e = Frag->getNumArgs(); i != e; ++i) {
2050 TreePatternNodePtr Child = getChildShared(i);
2051 if (Scope != 0) {
2052 Child = Child->clone();
2053 Child->addNameAsPredicateArg(ScopedName(Scope, Frag->getArgName(i)));
2054 }
2055 ArgMap[Frag->getArgName(i)] = Child;
2056 }
2057
2058 // Loop over all fragment alternatives.
2059 for (auto Alternative : Frag->getTrees()) {
2060 TreePatternNodePtr FragTree = Alternative->clone();
2061
2062 if (!PredFn.isAlwaysTrue())
2063 FragTree->addPredicateCall(PredFn, Scope);
2064
2065 // Resolve formal arguments to their actual value.
2066 if (Frag->getNumArgs())
2067 FragTree->SubstituteFormalArguments(ArgMap);
2068
2069 // Transfer types. Note that the resolved alternative may have fewer
2070 // (but not more) results than the PatFrags node.
2071 FragTree->setName(getName());
2072 for (unsigned i = 0, e = FragTree->getNumTypes(); i != e; ++i)
2073 FragTree->UpdateNodeType(i, getExtType(i), TP);
2074
2075 // Transfer in the old predicates.
2076 for (const TreePredicateCall &Pred : getPredicateCalls())
2077 FragTree->addPredicateCall(Pred);
2078
2079 // The fragment we inlined could have recursive inlining that is needed. See
2080 // if there are any pattern fragments in it and inline them as needed.
2081 FragTree->InlinePatternFragments(FragTree, TP, OutAlternatives);
2082 }
2083}
2084
2085/// getImplicitType - Check to see if the specified record has an implicit
2086/// type which should be applied to it. This will infer the type of register
2087/// references from the register file information, for example.
2088///
2089/// When Unnamed is set, return the type of a DAG operand with no name, such as
2090/// the F8RC register class argument in:
2091///
2092/// (COPY_TO_REGCLASS GPR:$src, F8RC)
2093///
2094/// When Unnamed is false, return the type of a named DAG operand such as the
2095/// GPR:$src operand above.
2096///
2097static TypeSetByHwMode getImplicitType(Record *R, unsigned ResNo,
2098 bool NotRegisters,
2099 bool Unnamed,
2100 TreePattern &TP) {
2101 CodeGenDAGPatterns &CDP = TP.getDAGPatterns();
2102
2103 // Check to see if this is a register operand.
2104 if (R->isSubClassOf("RegisterOperand")) {
2105 assert(ResNo == 0 && "Regoperand ref only has one result!")((ResNo == 0 && "Regoperand ref only has one result!"
) ? static_cast<void> (0) : __assert_fail ("ResNo == 0 && \"Regoperand ref only has one result!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2105, __PRETTY_FUNCTION__))
;
2106 if (NotRegisters)
2107 return TypeSetByHwMode(); // Unknown.
2108 Record *RegClass = R->getValueAsDef("RegClass");
2109 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
2110 return TypeSetByHwMode(T.getRegisterClass(RegClass).getValueTypes());
2111 }
2112
2113 // Check to see if this is a register or a register class.
2114 if (R->isSubClassOf("RegisterClass")) {
2115 assert(ResNo == 0 && "Regclass ref only has one result!")((ResNo == 0 && "Regclass ref only has one result!") ?
static_cast<void> (0) : __assert_fail ("ResNo == 0 && \"Regclass ref only has one result!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2115, __PRETTY_FUNCTION__))
;
2116 // An unnamed register class represents itself as an i32 immediate, for
2117 // example on a COPY_TO_REGCLASS instruction.
2118 if (Unnamed)
2119 return TypeSetByHwMode(MVT::i32);
2120
2121 // In a named operand, the register class provides the possible set of
2122 // types.
2123 if (NotRegisters)
2124 return TypeSetByHwMode(); // Unknown.
2125 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
2126 return TypeSetByHwMode(T.getRegisterClass(R).getValueTypes());
2127 }
2128
2129 if (R->isSubClassOf("PatFrags")) {
2130 assert(ResNo == 0 && "FIXME: PatFrag with multiple results?")((ResNo == 0 && "FIXME: PatFrag with multiple results?"
) ? static_cast<void> (0) : __assert_fail ("ResNo == 0 && \"FIXME: PatFrag with multiple results?\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2130, __PRETTY_FUNCTION__))
;
2131 // Pattern fragment types will be resolved when they are inlined.
2132 return TypeSetByHwMode(); // Unknown.
2133 }
2134
2135 if (R->isSubClassOf("Register")) {
2136 assert(ResNo == 0 && "Registers only produce one result!")((ResNo == 0 && "Registers only produce one result!")
? static_cast<void> (0) : __assert_fail ("ResNo == 0 && \"Registers only produce one result!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2136, __PRETTY_FUNCTION__))
;
2137 if (NotRegisters)
2138 return TypeSetByHwMode(); // Unknown.
2139 const CodeGenTarget &T = TP.getDAGPatterns().getTargetInfo();
2140 return TypeSetByHwMode(T.getRegisterVTs(R));
2141 }
2142
2143 if (R->isSubClassOf("SubRegIndex")) {
2144 assert(ResNo == 0 && "SubRegisterIndices only produce one result!")((ResNo == 0 && "SubRegisterIndices only produce one result!"
) ? static_cast<void> (0) : __assert_fail ("ResNo == 0 && \"SubRegisterIndices only produce one result!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2144, __PRETTY_FUNCTION__))
;
2145 return TypeSetByHwMode(MVT::i32);
2146 }
2147
2148 if (R->isSubClassOf("ValueType")) {
2149 assert(ResNo == 0 && "This node only has one result!")((ResNo == 0 && "This node only has one result!") ? static_cast
<void> (0) : __assert_fail ("ResNo == 0 && \"This node only has one result!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2149, __PRETTY_FUNCTION__))
;
2150 // An unnamed VTSDNode represents itself as an MVT::Other immediate.
2151 //
2152 // (sext_inreg GPR:$src, i16)
2153 // ~~~
2154 if (Unnamed)
2155 return TypeSetByHwMode(MVT::Other);
2156 // With a name, the ValueType simply provides the type of the named
2157 // variable.
2158 //
2159 // (sext_inreg i32:$src, i16)
2160 // ~~~~~~~~
2161 if (NotRegisters)
2162 return TypeSetByHwMode(); // Unknown.
2163 const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes();
2164 return TypeSetByHwMode(getValueTypeByHwMode(R, CGH));
2165 }
2166
2167 if (R->isSubClassOf("CondCode")) {
2168 assert(ResNo == 0 && "This node only has one result!")((ResNo == 0 && "This node only has one result!") ? static_cast
<void> (0) : __assert_fail ("ResNo == 0 && \"This node only has one result!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2168, __PRETTY_FUNCTION__))
;
2169 // Using a CondCodeSDNode.
2170 return TypeSetByHwMode(MVT::Other);
2171 }
2172
2173 if (R->isSubClassOf("ComplexPattern")) {
2174 assert(ResNo == 0 && "FIXME: ComplexPattern with multiple results?")((ResNo == 0 && "FIXME: ComplexPattern with multiple results?"
) ? static_cast<void> (0) : __assert_fail ("ResNo == 0 && \"FIXME: ComplexPattern with multiple results?\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2174, __PRETTY_FUNCTION__))
;
2175 if (NotRegisters)
2176 return TypeSetByHwMode(); // Unknown.
2177 return TypeSetByHwMode(CDP.getComplexPattern(R).getValueType());
2178 }
2179 if (R->isSubClassOf("PointerLikeRegClass")) {
2180 assert(ResNo == 0 && "Regclass can only have one result!")((ResNo == 0 && "Regclass can only have one result!")
? static_cast<void> (0) : __assert_fail ("ResNo == 0 && \"Regclass can only have one result!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2180, __PRETTY_FUNCTION__))
;
2181 TypeSetByHwMode VTS(MVT::iPTR);
2182 TP.getInfer().expandOverloads(VTS);
2183 return VTS;
2184 }
2185
2186 if (R->getName() == "node" || R->getName() == "srcvalue" ||
2187 R->getName() == "zero_reg" || R->getName() == "immAllOnesV" ||
2188 R->getName() == "immAllZerosV" || R->getName() == "undef_tied_input") {
2189 // Placeholder.
2190 return TypeSetByHwMode(); // Unknown.
2191 }
2192
2193 if (R->isSubClassOf("Operand")) {
2194 const CodeGenHwModes &CGH = CDP.getTargetInfo().getHwModes();
2195 Record *T = R->getValueAsDef("Type");
2196 return TypeSetByHwMode(getValueTypeByHwMode(T, CGH));
2197 }
2198
2199 TP.error("Unknown node flavor used in pattern: " + R->getName());
2200 return TypeSetByHwMode(MVT::Other);
2201}
2202
2203
2204/// getIntrinsicInfo - If this node corresponds to an intrinsic, return the
2205/// CodeGenIntrinsic information for it, otherwise return a null pointer.
2206const CodeGenIntrinsic *TreePatternNode::
2207getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const {
2208 if (getOperator() != CDP.get_intrinsic_void_sdnode() &&
2209 getOperator() != CDP.get_intrinsic_w_chain_sdnode() &&
2210 getOperator() != CDP.get_intrinsic_wo_chain_sdnode())
2211 return nullptr;
2212
2213 unsigned IID = cast<IntInit>(getChild(0)->getLeafValue())->getValue();
2214 return &CDP.getIntrinsicInfo(IID);
2215}
2216
2217/// getComplexPatternInfo - If this node corresponds to a ComplexPattern,
2218/// return the ComplexPattern information, otherwise return null.
2219const ComplexPattern *
2220TreePatternNode::getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const {
2221 Record *Rec;
2222 if (isLeaf()) {
2223 DefInit *DI = dyn_cast<DefInit>(getLeafValue());
2224 if (!DI)
2225 return nullptr;
2226 Rec = DI->getDef();
2227 } else
2228 Rec = getOperator();
2229
2230 if (!Rec->isSubClassOf("ComplexPattern"))
2231 return nullptr;
2232 return &CGP.getComplexPattern(Rec);
2233}
2234
2235unsigned TreePatternNode::getNumMIResults(const CodeGenDAGPatterns &CGP) const {
2236 // A ComplexPattern specifically declares how many results it fills in.
2237 if (const ComplexPattern *CP = getComplexPatternInfo(CGP))
2238 return CP->getNumOperands();
2239
2240 // If MIOperandInfo is specified, that gives the count.
2241 if (isLeaf()) {
2242 DefInit *DI = dyn_cast<DefInit>(getLeafValue());
2243 if (DI && DI->getDef()->isSubClassOf("Operand")) {
2244 DagInit *MIOps = DI->getDef()->getValueAsDag("MIOperandInfo");
2245 if (MIOps->getNumArgs())
2246 return MIOps->getNumArgs();
2247 }
2248 }
2249
2250 // Otherwise there is just one result.
2251 return 1;
2252}
2253
2254/// NodeHasProperty - Return true if this node has the specified property.
2255bool TreePatternNode::NodeHasProperty(SDNP Property,
2256 const CodeGenDAGPatterns &CGP) const {
2257 if (isLeaf()) {
2258 if (const ComplexPattern *CP = getComplexPatternInfo(CGP))
2259 return CP->hasProperty(Property);
2260
2261 return false;
2262 }
2263
2264 if (Property != SDNPHasChain) {
2265 // The chain proprety is already present on the different intrinsic node
2266 // types (intrinsic_w_chain, intrinsic_void), and is not explicitly listed
2267 // on the intrinsic. Anything else is specific to the individual intrinsic.
2268 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CGP))
2269 return Int->hasProperty(Property);
2270 }
2271
2272 if (!Operator->isSubClassOf("SDPatternOperator"))
2273 return false;
2274
2275 return CGP.getSDNodeInfo(Operator).hasProperty(Property);
2276}
2277
2278
2279
2280
2281/// TreeHasProperty - Return true if any node in this tree has the specified
2282/// property.
2283bool TreePatternNode::TreeHasProperty(SDNP Property,
2284 const CodeGenDAGPatterns &CGP) const {
2285 if (NodeHasProperty(Property, CGP))
2286 return true;
2287 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
2288 if (getChild(i)->TreeHasProperty(Property, CGP))
2289 return true;
2290 return false;
2291}
2292
2293/// isCommutativeIntrinsic - Return true if the node corresponds to a
2294/// commutative intrinsic.
2295bool
2296TreePatternNode::isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const {
2297 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP))
2298 return Int->isCommutative;
2299 return false;
2300}
2301
2302static bool isOperandClass(const TreePatternNode *N, StringRef Class) {
2303 if (!N->isLeaf())
2304 return N->getOperator()->isSubClassOf(Class);
2305
2306 DefInit *DI = dyn_cast<DefInit>(N->getLeafValue());
2307 if (DI && DI->getDef()->isSubClassOf(Class))
2308 return true;
2309
2310 return false;
2311}
2312
2313static void emitTooManyOperandsError(TreePattern &TP,
2314 StringRef InstName,
2315 unsigned Expected,
2316 unsigned Actual) {
2317 TP.error("Instruction '" + InstName + "' was provided " + Twine(Actual) +
2318 " operands but expected only " + Twine(Expected) + "!");
2319}
2320
2321static void emitTooFewOperandsError(TreePattern &TP,
2322 StringRef InstName,
2323 unsigned Actual) {
2324 TP.error("Instruction '" + InstName +
2325 "' expects more than the provided " + Twine(Actual) + " operands!");
2326}
2327
2328/// ApplyTypeConstraints - Apply all of the type constraints relevant to
2329/// this node and its children in the tree. This returns true if it makes a
2330/// change, false otherwise. If a type contradiction is found, flag an error.
2331bool TreePatternNode::ApplyTypeConstraints(TreePattern &TP, bool NotRegisters) {
2332 if (TP.hasError())
2333 return false;
2334
2335 CodeGenDAGPatterns &CDP = TP.getDAGPatterns();
2336 if (isLeaf()) {
2337 if (DefInit *DI = dyn_cast<DefInit>(getLeafValue())) {
2338 // If it's a regclass or something else known, include the type.
2339 bool MadeChange = false;
2340 for (unsigned i = 0, e = Types.size(); i != e; ++i)
2341 MadeChange |= UpdateNodeType(i, getImplicitType(DI->getDef(), i,
2342 NotRegisters,
2343 !hasName(), TP), TP);
2344 return MadeChange;
2345 }
2346
2347 if (IntInit *II = dyn_cast<IntInit>(getLeafValue())) {
2348 assert(Types.size() == 1 && "Invalid IntInit")((Types.size() == 1 && "Invalid IntInit") ? static_cast
<void> (0) : __assert_fail ("Types.size() == 1 && \"Invalid IntInit\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2348, __PRETTY_FUNCTION__))
;
2349
2350 // Int inits are always integers. :)
2351 bool MadeChange = TP.getInfer().EnforceInteger(Types[0]);
2352
2353 if (!TP.getInfer().isConcrete(Types[0], false))
2354 return MadeChange;
2355
2356 ValueTypeByHwMode VVT = TP.getInfer().getConcrete(Types[0], false);
2357 for (auto &P : VVT) {
2358 MVT::SimpleValueType VT = P.second.SimpleTy;
2359 if (VT == MVT::iPTR || VT == MVT::iPTRAny)
2360 continue;
2361 unsigned Size = MVT(VT).getSizeInBits();
2362 // Make sure that the value is representable for this type.
2363 if (Size >= 32)
2364 continue;
2365 // Check that the value doesn't use more bits than we have. It must
2366 // either be a sign- or zero-extended equivalent of the original.
2367 int64_t SignBitAndAbove = II->getValue() >> (Size - 1);
2368 if (SignBitAndAbove == -1 || SignBitAndAbove == 0 ||
2369 SignBitAndAbove == 1)
2370 continue;
2371
2372 TP.error("Integer value '" + Twine(II->getValue()) +
2373 "' is out of range for type '" + getEnumName(VT) + "'!");
2374 break;
2375 }
2376 return MadeChange;
2377 }
2378
2379 return false;
2380 }
2381
2382 if (const CodeGenIntrinsic *Int = getIntrinsicInfo(CDP)) {
2383 bool MadeChange = false;
2384
2385 // Apply the result type to the node.
2386 unsigned NumRetVTs = Int->IS.RetVTs.size();
2387 unsigned NumParamVTs = Int->IS.ParamVTs.size();
2388
2389 for (unsigned i = 0, e = NumRetVTs; i != e; ++i)
2390 MadeChange |= UpdateNodeType(i, Int->IS.RetVTs[i], TP);
2391
2392 if (getNumChildren() != NumParamVTs + 1) {
2393 TP.error("Intrinsic '" + Int->Name + "' expects " + Twine(NumParamVTs) +
2394 " operands, not " + Twine(getNumChildren() - 1) + " operands!");
2395 return false;
2396 }
2397
2398 // Apply type info to the intrinsic ID.
2399 MadeChange |= getChild(0)->UpdateNodeType(0, MVT::iPTR, TP);
2400
2401 for (unsigned i = 0, e = getNumChildren()-1; i != e; ++i) {
2402 MadeChange |= getChild(i+1)->ApplyTypeConstraints(TP, NotRegisters);
2403
2404 MVT::SimpleValueType OpVT = Int->IS.ParamVTs[i];
2405 assert(getChild(i+1)->getNumTypes() == 1 && "Unhandled case")((getChild(i+1)->getNumTypes() == 1 && "Unhandled case"
) ? static_cast<void> (0) : __assert_fail ("getChild(i+1)->getNumTypes() == 1 && \"Unhandled case\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2405, __PRETTY_FUNCTION__))
;
2406 MadeChange |= getChild(i+1)->UpdateNodeType(0, OpVT, TP);
2407 }
2408 return MadeChange;
2409 }
2410
2411 if (getOperator()->isSubClassOf("SDNode")) {
2412 const SDNodeInfo &NI = CDP.getSDNodeInfo(getOperator());
2413
2414 // Check that the number of operands is sane. Negative operands -> varargs.
2415 if (NI.getNumOperands() >= 0 &&
2416 getNumChildren() != (unsigned)NI.getNumOperands()) {
2417 TP.error(getOperator()->getName() + " node requires exactly " +
2418 Twine(NI.getNumOperands()) + " operands!");
2419 return false;
2420 }
2421
2422 bool MadeChange = false;
2423 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
2424 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
2425 MadeChange |= NI.ApplyTypeConstraints(this, TP);
2426 return MadeChange;
2427 }
2428
2429 if (getOperator()->isSubClassOf("Instruction")) {
2430 const DAGInstruction &Inst = CDP.getInstruction(getOperator());
2431 CodeGenInstruction &InstInfo =
2432 CDP.getTargetInfo().getInstruction(getOperator());
2433
2434 bool MadeChange = false;
2435
2436 // Apply the result types to the node, these come from the things in the
2437 // (outs) list of the instruction.
2438 unsigned NumResultsToAdd = std::min(InstInfo.Operands.NumDefs,
2439 Inst.getNumResults());
2440 for (unsigned ResNo = 0; ResNo != NumResultsToAdd; ++ResNo)
2441 MadeChange |= UpdateNodeTypeFromInst(ResNo, Inst.getResult(ResNo), TP);
2442
2443 // If the instruction has implicit defs, we apply the first one as a result.
2444 // FIXME: This sucks, it should apply all implicit defs.
2445 if (!InstInfo.ImplicitDefs.empty()) {
2446 unsigned ResNo = NumResultsToAdd;
2447
2448 // FIXME: Generalize to multiple possible types and multiple possible
2449 // ImplicitDefs.
2450 MVT::SimpleValueType VT =
2451 InstInfo.HasOneImplicitDefWithKnownVT(CDP.getTargetInfo());
2452
2453 if (VT != MVT::Other)
2454 MadeChange |= UpdateNodeType(ResNo, VT, TP);
2455 }
2456
2457 // If this is an INSERT_SUBREG, constrain the source and destination VTs to
2458 // be the same.
2459 if (getOperator()->getName() == "INSERT_SUBREG") {
2460 assert(getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled")((getChild(0)->getNumTypes() == 1 && "FIXME: Unhandled"
) ? static_cast<void> (0) : __assert_fail ("getChild(0)->getNumTypes() == 1 && \"FIXME: Unhandled\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2460, __PRETTY_FUNCTION__))
;
2461 MadeChange |= UpdateNodeType(0, getChild(0)->getExtType(0), TP);
2462 MadeChange |= getChild(0)->UpdateNodeType(0, getExtType(0), TP);
2463 } else if (getOperator()->getName() == "REG_SEQUENCE") {
2464 // We need to do extra, custom typechecking for REG_SEQUENCE since it is
2465 // variadic.
2466
2467 unsigned NChild = getNumChildren();
2468 if (NChild < 3) {
2469 TP.error("REG_SEQUENCE requires at least 3 operands!");
2470 return false;
2471 }
2472
2473 if (NChild % 2 == 0) {
2474 TP.error("REG_SEQUENCE requires an odd number of operands!");
2475 return false;
2476 }
2477
2478 if (!isOperandClass(getChild(0), "RegisterClass")) {
2479 TP.error("REG_SEQUENCE requires a RegisterClass for first operand!");
2480 return false;
2481 }
2482
2483 for (unsigned I = 1; I < NChild; I += 2) {
2484 TreePatternNode *SubIdxChild = getChild(I + 1);
2485 if (!isOperandClass(SubIdxChild, "SubRegIndex")) {
2486 TP.error("REG_SEQUENCE requires a SubRegIndex for operand " +
2487 Twine(I + 1) + "!");
2488 return false;
2489 }
2490 }
2491 }
2492
2493 // If one or more operands with a default value appear at the end of the
2494 // formal operand list for an instruction, we allow them to be overridden
2495 // by optional operands provided in the pattern.
2496 //
2497 // But if an operand B without a default appears at any point after an
2498 // operand A with a default, then we don't allow A to be overridden,
2499 // because there would be no way to specify whether the next operand in
2500 // the pattern was intended to override A or skip it.
2501 unsigned NonOverridableOperands = Inst.getNumOperands();
2502 while (NonOverridableOperands > 0 &&
2503 CDP.operandHasDefault(Inst.getOperand(NonOverridableOperands-1)))
2504 --NonOverridableOperands;
2505
2506 unsigned ChildNo = 0;
2507 for (unsigned i = 0, e = Inst.getNumOperands(); i != e; ++i) {
2508 Record *OperandNode = Inst.getOperand(i);
2509
2510 // If the operand has a default value, do we use it? We must use the
2511 // default if we've run out of children of the pattern DAG to consume,
2512 // or if the operand is followed by a non-defaulted one.
2513 if (CDP.operandHasDefault(OperandNode) &&
2514 (i < NonOverridableOperands || ChildNo >= getNumChildren()))
2515 continue;
2516
2517 // If we have run out of child nodes and there _isn't_ a default
2518 // value we can use for the next operand, give an error.
2519 if (ChildNo >= getNumChildren()) {
2520 emitTooFewOperandsError(TP, getOperator()->getName(), getNumChildren());
2521 return false;
2522 }
2523
2524 TreePatternNode *Child = getChild(ChildNo++);
2525 unsigned ChildResNo = 0; // Instructions always use res #0 of their op.
2526
2527 // If the operand has sub-operands, they may be provided by distinct
2528 // child patterns, so attempt to match each sub-operand separately.
2529 if (OperandNode->isSubClassOf("Operand")) {
2530 DagInit *MIOpInfo = OperandNode->getValueAsDag("MIOperandInfo");
2531 if (unsigned NumArgs = MIOpInfo->getNumArgs()) {
2532 // But don't do that if the whole operand is being provided by
2533 // a single ComplexPattern-related Operand.
2534
2535 if (Child->getNumMIResults(CDP) < NumArgs) {
2536 // Match first sub-operand against the child we already have.
2537 Record *SubRec = cast<DefInit>(MIOpInfo->getArg(0))->getDef();
2538 MadeChange |=
2539 Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP);
2540
2541 // And the remaining sub-operands against subsequent children.
2542 for (unsigned Arg = 1; Arg < NumArgs; ++Arg) {
2543 if (ChildNo >= getNumChildren()) {
2544 emitTooFewOperandsError(TP, getOperator()->getName(),
2545 getNumChildren());
2546 return false;
2547 }
2548 Child = getChild(ChildNo++);
2549
2550 SubRec = cast<DefInit>(MIOpInfo->getArg(Arg))->getDef();
2551 MadeChange |=
2552 Child->UpdateNodeTypeFromInst(ChildResNo, SubRec, TP);
2553 }
2554 continue;
2555 }
2556 }
2557 }
2558
2559 // If we didn't match by pieces above, attempt to match the whole
2560 // operand now.
2561 MadeChange |= Child->UpdateNodeTypeFromInst(ChildResNo, OperandNode, TP);
2562 }
2563
2564 if (!InstInfo.Operands.isVariadic && ChildNo != getNumChildren()) {
2565 emitTooManyOperandsError(TP, getOperator()->getName(),
2566 ChildNo, getNumChildren());
2567 return false;
2568 }
2569
2570 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
2571 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
2572 return MadeChange;
2573 }
2574
2575 if (getOperator()->isSubClassOf("ComplexPattern")) {
2576 bool MadeChange = false;
2577
2578 for (unsigned i = 0; i < getNumChildren(); ++i)
2579 MadeChange |= getChild(i)->ApplyTypeConstraints(TP, NotRegisters);
2580
2581 return MadeChange;
2582 }
2583
2584 assert(getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!")((getOperator()->isSubClassOf("SDNodeXForm") && "Unknown node type!"
) ? static_cast<void> (0) : __assert_fail ("getOperator()->isSubClassOf(\"SDNodeXForm\") && \"Unknown node type!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2584, __PRETTY_FUNCTION__))
;
2585
2586 // Node transforms always take one operand.
2587 if (getNumChildren() != 1) {
2588 TP.error("Node transform '" + getOperator()->getName() +
2589 "' requires one operand!");
2590 return false;
2591 }
2592
2593 bool MadeChange = getChild(0)->ApplyTypeConstraints(TP, NotRegisters);
2594 return MadeChange;
2595}
2596
2597/// OnlyOnRHSOfCommutative - Return true if this value is only allowed on the
2598/// RHS of a commutative operation, not the on LHS.
2599static bool OnlyOnRHSOfCommutative(TreePatternNode *N) {
2600 if (!N->isLeaf() && N->getOperator()->getName() == "imm")
2601 return true;
2602 if (N->isLeaf() && isa<IntInit>(N->getLeafValue()))
2603 return true;
2604 return false;
2605}
2606
2607
2608/// canPatternMatch - If it is impossible for this pattern to match on this
2609/// target, fill in Reason and return false. Otherwise, return true. This is
2610/// used as a sanity check for .td files (to prevent people from writing stuff
2611/// that can never possibly work), and to prevent the pattern permuter from
2612/// generating stuff that is useless.
2613bool TreePatternNode::canPatternMatch(std::string &Reason,
2614 const CodeGenDAGPatterns &CDP) {
2615 if (isLeaf()) return true;
2616
2617 for (unsigned i = 0, e = getNumChildren(); i != e; ++i)
2618 if (!getChild(i)->canPatternMatch(Reason, CDP))
2619 return false;
2620
2621 // If this is an intrinsic, handle cases that would make it not match. For
2622 // example, if an operand is required to be an immediate.
2623 if (getOperator()->isSubClassOf("Intrinsic")) {
2624 // TODO:
2625 return true;
2626 }
2627
2628 if (getOperator()->isSubClassOf("ComplexPattern"))
2629 return true;
2630
2631 // If this node is a commutative operator, check that the LHS isn't an
2632 // immediate.
2633 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(getOperator());
2634 bool isCommIntrinsic = isCommutativeIntrinsic(CDP);
2635 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {
2636 // Scan all of the operands of the node and make sure that only the last one
2637 // is a constant node, unless the RHS also is.
2638 if (!OnlyOnRHSOfCommutative(getChild(getNumChildren()-1))) {
2639 unsigned Skip = isCommIntrinsic ? 1 : 0; // First operand is intrinsic id.
2640 for (unsigned i = Skip, e = getNumChildren()-1; i != e; ++i)
2641 if (OnlyOnRHSOfCommutative(getChild(i))) {
2642 Reason="Immediate value must be on the RHS of commutative operators!";
2643 return false;
2644 }
2645 }
2646 }
2647
2648 return true;
2649}
2650
2651//===----------------------------------------------------------------------===//
2652// TreePattern implementation
2653//
2654
2655TreePattern::TreePattern(Record *TheRec, ListInit *RawPat, bool isInput,
2656 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp),
2657 isInputPattern(isInput), HasError(false),
2658 Infer(*this) {
2659 for (Init *I : RawPat->getValues())
2660 Trees.push_back(ParseTreePattern(I, ""));
2661}
2662
2663TreePattern::TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
2664 CodeGenDAGPatterns &cdp) : TheRecord(TheRec), CDP(cdp),
2665 isInputPattern(isInput), HasError(false),
2666 Infer(*this) {
2667 Trees.push_back(ParseTreePattern(Pat, ""));
2668}
2669
2670TreePattern::TreePattern(Record *TheRec, TreePatternNodePtr Pat, bool isInput,
2671 CodeGenDAGPatterns &cdp)
2672 : TheRecord(TheRec), CDP(cdp), isInputPattern(isInput), HasError(false),
2673 Infer(*this) {
2674 Trees.push_back(Pat);
2675}
2676
2677void TreePattern::error(const Twine &Msg) {
2678 if (HasError)
2679 return;
2680 dump();
2681 PrintError(TheRecord->getLoc(), "In " + TheRecord->getName() + ": " + Msg);
2682 HasError = true;
2683}
2684
2685void TreePattern::ComputeNamedNodes() {
2686 for (TreePatternNodePtr &Tree : Trees)
2687 ComputeNamedNodes(Tree.get());
2688}
2689
2690void TreePattern::ComputeNamedNodes(TreePatternNode *N) {
2691 if (!N->getName().empty())
2692 NamedNodes[N->getName()].push_back(N);
2693
2694 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
2695 ComputeNamedNodes(N->getChild(i));
2696}
2697
2698TreePatternNodePtr TreePattern::ParseTreePattern(Init *TheInit,
2699 StringRef OpName) {
2700 if (DefInit *DI = dyn_cast<DefInit>(TheInit)) {
2701 Record *R = DI->getDef();
2702
2703 // Direct reference to a leaf DagNode or PatFrag? Turn it into a
2704 // TreePatternNode of its own. For example:
2705 /// (foo GPR, imm) -> (foo GPR, (imm))
2706 if (R->isSubClassOf("SDNode") || R->isSubClassOf("PatFrags"))
2707 return ParseTreePattern(
2708 DagInit::get(DI, nullptr,
2709 std::vector<std::pair<Init*, StringInit*> >()),
2710 OpName);
2711
2712 // Input argument?
2713 TreePatternNodePtr Res = std::make_shared<TreePatternNode>(DI, 1);
2714 if (R->getName() == "node" && !OpName.empty()) {
2715 if (OpName.empty())
2716 error("'node' argument requires a name to match with operand list");
2717 Args.push_back(OpName);
2718 }
2719
2720 Res->setName(OpName);
2721 return Res;
2722 }
2723
2724 // ?:$name or just $name.
2725 if (isa<UnsetInit>(TheInit)) {
2726 if (OpName.empty())
2727 error("'?' argument requires a name to match with operand list");
2728 TreePatternNodePtr Res = std::make_shared<TreePatternNode>(TheInit, 1);
2729 Args.push_back(OpName);
2730 Res->setName(OpName);
2731 return Res;
2732 }
2733
2734 if (isa<IntInit>(TheInit) || isa<BitInit>(TheInit)) {
2735 if (!OpName.empty())
2736 error("Constant int or bit argument should not have a name!");
2737 if (isa<BitInit>(TheInit))
2738 TheInit = TheInit->convertInitializerTo(IntRecTy::get());
2739 return std::make_shared<TreePatternNode>(TheInit, 1);
2740 }
2741
2742 if (BitsInit *BI = dyn_cast<BitsInit>(TheInit)) {
2743 // Turn this into an IntInit.
2744 Init *II = BI->convertInitializerTo(IntRecTy::get());
2745 if (!II || !isa<IntInit>(II))
2746 error("Bits value must be constants!");
2747 return ParseTreePattern(II, OpName);
2748 }
2749
2750 DagInit *Dag = dyn_cast<DagInit>(TheInit);
2751 if (!Dag) {
2752 TheInit->print(errs());
2753 error("Pattern has unexpected init kind!");
2754 }
2755 DefInit *OpDef = dyn_cast<DefInit>(Dag->getOperator());
2756 if (!OpDef) error("Pattern has unexpected operator type!");
2757 Record *Operator = OpDef->getDef();
2758
2759 if (Operator->isSubClassOf("ValueType")) {
2760 // If the operator is a ValueType, then this must be "type cast" of a leaf
2761 // node.
2762 if (Dag->getNumArgs() != 1)
2763 error("Type cast only takes one operand!");
2764
2765 TreePatternNodePtr New =
2766 ParseTreePattern(Dag->getArg(0), Dag->getArgNameStr(0));
2767
2768 // Apply the type cast.
2769 assert(New->getNumTypes() == 1 && "FIXME: Unhandled")((New->getNumTypes() == 1 && "FIXME: Unhandled") ?
static_cast<void> (0) : __assert_fail ("New->getNumTypes() == 1 && \"FIXME: Unhandled\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2769, __PRETTY_FUNCTION__))
;
2770 const CodeGenHwModes &CGH = getDAGPatterns().getTargetInfo().getHwModes();
2771 New->UpdateNodeType(0, getValueTypeByHwMode(Operator, CGH), *this);
2772
2773 if (!OpName.empty())
2774 error("ValueType cast should not have a name!");
2775 return New;
2776 }
2777
2778 // Verify that this is something that makes sense for an operator.
2779 if (!Operator->isSubClassOf("PatFrags") &&
2780 !Operator->isSubClassOf("SDNode") &&
2781 !Operator->isSubClassOf("Instruction") &&
2782 !Operator->isSubClassOf("SDNodeXForm") &&
2783 !Operator->isSubClassOf("Intrinsic") &&
2784 !Operator->isSubClassOf("ComplexPattern") &&
2785 Operator->getName() != "set" &&
2786 Operator->getName() != "implicit")
2787 error("Unrecognized node '" + Operator->getName() + "'!");
2788
2789 // Check to see if this is something that is illegal in an input pattern.
2790 if (isInputPattern) {
2791 if (Operator->isSubClassOf("Instruction") ||
2792 Operator->isSubClassOf("SDNodeXForm"))
2793 error("Cannot use '" + Operator->getName() + "' in an input pattern!");
2794 } else {
2795 if (Operator->isSubClassOf("Intrinsic"))
2796 error("Cannot use '" + Operator->getName() + "' in an output pattern!");
2797
2798 if (Operator->isSubClassOf("SDNode") &&
2799 Operator->getName() != "imm" &&
2800 Operator->getName() != "timm" &&
2801 Operator->getName() != "fpimm" &&
2802 Operator->getName() != "tglobaltlsaddr" &&
2803 Operator->getName() != "tconstpool" &&
2804 Operator->getName() != "tjumptable" &&
2805 Operator->getName() != "tframeindex" &&
2806 Operator->getName() != "texternalsym" &&
2807 Operator->getName() != "tblockaddress" &&
2808 Operator->getName() != "tglobaladdr" &&
2809 Operator->getName() != "bb" &&
2810 Operator->getName() != "vt" &&
2811 Operator->getName() != "mcsym")
2812 error("Cannot use '" + Operator->getName() + "' in an output pattern!");
2813 }
2814
2815 std::vector<TreePatternNodePtr> Children;
2816
2817 // Parse all the operands.
2818 for (unsigned i = 0, e = Dag->getNumArgs(); i != e; ++i)
2819 Children.push_back(ParseTreePattern(Dag->getArg(i), Dag->getArgNameStr(i)));
2820
2821 // Get the actual number of results before Operator is converted to an intrinsic
2822 // node (which is hard-coded to have either zero or one result).
2823 unsigned NumResults = GetNumNodeResults(Operator, CDP);
2824
2825 // If the operator is an intrinsic, then this is just syntactic sugar for
2826 // (intrinsic_* <number>, ..children..). Pick the right intrinsic node, and
2827 // convert the intrinsic name to a number.
2828 if (Operator->isSubClassOf("Intrinsic")) {
2829 const CodeGenIntrinsic &Int = getDAGPatterns().getIntrinsic(Operator);
2830 unsigned IID = getDAGPatterns().getIntrinsicID(Operator)+1;
2831
2832 // If this intrinsic returns void, it must have side-effects and thus a
2833 // chain.
2834 if (Int.IS.RetVTs.empty())
2835 Operator = getDAGPatterns().get_intrinsic_void_sdnode();
2836 else if (Int.ModRef != CodeGenIntrinsic::NoMem || Int.hasSideEffects)
2837 // Has side-effects, requires chain.
2838 Operator = getDAGPatterns().get_intrinsic_w_chain_sdnode();
2839 else // Otherwise, no chain.
2840 Operator = getDAGPatterns().get_intrinsic_wo_chain_sdnode();
2841
2842 Children.insert(Children.begin(),
2843 std::make_shared<TreePatternNode>(IntInit::get(IID), 1));
2844 }
2845
2846 if (Operator->isSubClassOf("ComplexPattern")) {
2847 for (unsigned i = 0; i < Children.size(); ++i) {
2848 TreePatternNodePtr Child = Children[i];
2849
2850 if (Child->getName().empty())
2851 error("All arguments to a ComplexPattern must be named");
2852
2853 // Check that the ComplexPattern uses are consistent: "(MY_PAT $a, $b)"
2854 // and "(MY_PAT $b, $a)" should not be allowed in the same pattern;
2855 // neither should "(MY_PAT_1 $a, $b)" and "(MY_PAT_2 $a, $b)".
2856 auto OperandId = std::make_pair(Operator, i);
2857 auto PrevOp = ComplexPatternOperands.find(Child->getName());
2858 if (PrevOp != ComplexPatternOperands.end()) {
2859 if (PrevOp->getValue() != OperandId)
2860 error("All ComplexPattern operands must appear consistently: "
2861 "in the same order in just one ComplexPattern instance.");
2862 } else
2863 ComplexPatternOperands[Child->getName()] = OperandId;
2864 }
2865 }
2866
2867 TreePatternNodePtr Result =
2868 std::make_shared<TreePatternNode>(Operator, std::move(Children),
2869 NumResults);
2870 Result->setName(OpName);
2871
2872 if (Dag->getName()) {
2873 assert(Result->getName().empty())((Result->getName().empty()) ? static_cast<void> (0)
: __assert_fail ("Result->getName().empty()", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2873, __PRETTY_FUNCTION__))
;
2874 Result->setName(Dag->getNameStr());
2875 }
2876 return Result;
2877}
2878
2879/// SimplifyTree - See if we can simplify this tree to eliminate something that
2880/// will never match in favor of something obvious that will. This is here
2881/// strictly as a convenience to target authors because it allows them to write
2882/// more type generic things and have useless type casts fold away.
2883///
2884/// This returns true if any change is made.
2885static bool SimplifyTree(TreePatternNodePtr &N) {
2886 if (N->isLeaf())
2887 return false;
2888
2889 // If we have a bitconvert with a resolved type and if the source and
2890 // destination types are the same, then the bitconvert is useless, remove it.
2891 if (N->getOperator()->getName() == "bitconvert" &&
2892 N->getExtType(0).isValueTypeByHwMode(false) &&
2893 N->getExtType(0) == N->getChild(0)->getExtType(0) &&
2894 N->getName().empty()) {
2895 N = N->getChildShared(0);
2896 SimplifyTree(N);
2897 return true;
2898 }
2899
2900 // Walk all children.
2901 bool MadeChange = false;
2902 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
2903 TreePatternNodePtr Child = N->getChildShared(i);
2904 MadeChange |= SimplifyTree(Child);
2905 N->setChild(i, std::move(Child));
2906 }
2907 return MadeChange;
2908}
2909
2910
2911
2912/// InferAllTypes - Infer/propagate as many types throughout the expression
2913/// patterns as possible. Return true if all types are inferred, false
2914/// otherwise. Flags an error if a type contradiction is found.
2915bool TreePattern::
2916InferAllTypes(const StringMap<SmallVector<TreePatternNode*,1> > *InNamedTypes) {
2917 if (NamedNodes.empty())
2918 ComputeNamedNodes();
2919
2920 bool MadeChange = true;
2921 while (MadeChange) {
2922 MadeChange = false;
2923 for (TreePatternNodePtr &Tree : Trees) {
2924 MadeChange |= Tree->ApplyTypeConstraints(*this, false);
2925 MadeChange |= SimplifyTree(Tree);
2926 }
2927
2928 // If there are constraints on our named nodes, apply them.
2929 for (auto &Entry : NamedNodes) {
2930 SmallVectorImpl<TreePatternNode*> &Nodes = Entry.second;
2931
2932 // If we have input named node types, propagate their types to the named
2933 // values here.
2934 if (InNamedTypes) {
2935 if (!InNamedTypes->count(Entry.getKey())) {
2936 error("Node '" + std::string(Entry.getKey()) +
2937 "' in output pattern but not input pattern");
2938 return true;
2939 }
2940
2941 const SmallVectorImpl<TreePatternNode*> &InNodes =
2942 InNamedTypes->find(Entry.getKey())->second;
2943
2944 // The input types should be fully resolved by now.
2945 for (TreePatternNode *Node : Nodes) {
2946 // If this node is a register class, and it is the root of the pattern
2947 // then we're mapping something onto an input register. We allow
2948 // changing the type of the input register in this case. This allows
2949 // us to match things like:
2950 // def : Pat<(v1i64 (bitconvert(v2i32 DPR:$src))), (v1i64 DPR:$src)>;
2951 if (Node == Trees[0].get() && Node->isLeaf()) {
2952 DefInit *DI = dyn_cast<DefInit>(Node->getLeafValue());
2953 if (DI && (DI->getDef()->isSubClassOf("RegisterClass") ||
2954 DI->getDef()->isSubClassOf("RegisterOperand")))
2955 continue;
2956 }
2957
2958 assert(Node->getNumTypes() == 1 &&((Node->getNumTypes() == 1 && InNodes[0]->getNumTypes
() == 1 && "FIXME: cannot name multiple result nodes yet"
) ? static_cast<void> (0) : __assert_fail ("Node->getNumTypes() == 1 && InNodes[0]->getNumTypes() == 1 && \"FIXME: cannot name multiple result nodes yet\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2960, __PRETTY_FUNCTION__))
2959 InNodes[0]->getNumTypes() == 1 &&((Node->getNumTypes() == 1 && InNodes[0]->getNumTypes
() == 1 && "FIXME: cannot name multiple result nodes yet"
) ? static_cast<void> (0) : __assert_fail ("Node->getNumTypes() == 1 && InNodes[0]->getNumTypes() == 1 && \"FIXME: cannot name multiple result nodes yet\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2960, __PRETTY_FUNCTION__))
2960 "FIXME: cannot name multiple result nodes yet")((Node->getNumTypes() == 1 && InNodes[0]->getNumTypes
() == 1 && "FIXME: cannot name multiple result nodes yet"
) ? static_cast<void> (0) : __assert_fail ("Node->getNumTypes() == 1 && InNodes[0]->getNumTypes() == 1 && \"FIXME: cannot name multiple result nodes yet\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2960, __PRETTY_FUNCTION__))
;
2961 MadeChange |= Node->UpdateNodeType(0, InNodes[0]->getExtType(0),
2962 *this);
2963 }
2964 }
2965
2966 // If there are multiple nodes with the same name, they must all have the
2967 // same type.
2968 if (Entry.second.size() > 1) {
2969 for (unsigned i = 0, e = Nodes.size()-1; i != e; ++i) {
2970 TreePatternNode *N1 = Nodes[i], *N2 = Nodes[i+1];
2971 assert(N1->getNumTypes() == 1 && N2->getNumTypes() == 1 &&((N1->getNumTypes() == 1 && N2->getNumTypes() ==
1 && "FIXME: cannot name multiple result nodes yet")
? static_cast<void> (0) : __assert_fail ("N1->getNumTypes() == 1 && N2->getNumTypes() == 1 && \"FIXME: cannot name multiple result nodes yet\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2972, __PRETTY_FUNCTION__))
2972 "FIXME: cannot name multiple result nodes yet")((N1->getNumTypes() == 1 && N2->getNumTypes() ==
1 && "FIXME: cannot name multiple result nodes yet")
? static_cast<void> (0) : __assert_fail ("N1->getNumTypes() == 1 && N2->getNumTypes() == 1 && \"FIXME: cannot name multiple result nodes yet\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 2972, __PRETTY_FUNCTION__))
;
2973
2974 MadeChange |= N1->UpdateNodeType(0, N2->getExtType(0), *this);
2975 MadeChange |= N2->UpdateNodeType(0, N1->getExtType(0), *this);
2976 }
2977 }
2978 }
2979 }
2980
2981 bool HasUnresolvedTypes = false;
2982 for (const TreePatternNodePtr &Tree : Trees)
2983 HasUnresolvedTypes |= Tree->ContainsUnresolvedType(*this);
2984 return !HasUnresolvedTypes;
2985}
2986
2987void TreePattern::print(raw_ostream &OS) const {
2988 OS << getRecord()->getName();
2989 if (!Args.empty()) {
2990 OS << "(" << Args[0];
2991 for (unsigned i = 1, e = Args.size(); i != e; ++i)
2992 OS << ", " << Args[i];
2993 OS << ")";
2994 }
2995 OS << ": ";
2996
2997 if (Trees.size() > 1)
2998 OS << "[\n";
2999 for (const TreePatternNodePtr &Tree : Trees) {
3000 OS << "\t";
3001 Tree->print(OS);
3002 OS << "\n";
3003 }
3004
3005 if (Trees.size() > 1)
3006 OS << "]\n";
3007}
3008
3009void TreePattern::dump() const { print(errs()); }
3010
3011//===----------------------------------------------------------------------===//
3012// CodeGenDAGPatterns implementation
3013//
3014
3015CodeGenDAGPatterns::CodeGenDAGPatterns(RecordKeeper &R,
3016 PatternRewriterFn PatternRewriter)
3017 : Records(R), Target(R), LegalVTS(Target.getLegalValueTypes()),
3018 PatternRewriter(PatternRewriter) {
3019
3020 Intrinsics = CodeGenIntrinsicTable(Records, false);
3021 TgtIntrinsics = CodeGenIntrinsicTable(Records, true);
3022 ParseNodeInfo();
3023 ParseNodeTransforms();
3024 ParseComplexPatterns();
3025 ParsePatternFragments();
3026 ParseDefaultOperands();
3027 ParseInstructions();
3028 ParsePatternFragments(/*OutFrags*/true);
3029 ParsePatterns();
3030
3031 // Break patterns with parameterized types into a series of patterns,
3032 // where each one has a fixed type and is predicated on the conditions
3033 // of the associated HW mode.
3034 ExpandHwModeBasedTypes();
3035
3036 // Generate variants. For example, commutative patterns can match
3037 // multiple ways. Add them to PatternsToMatch as well.
3038 GenerateVariants();
3039
3040 // Infer instruction flags. For example, we can detect loads,
3041 // stores, and side effects in many cases by examining an
3042 // instruction's pattern.
3043 InferInstructionFlags();
3044
3045 // Verify that instruction flags match the patterns.
3046 VerifyInstructionFlags();
3047}
3048
3049Record *CodeGenDAGPatterns::getSDNodeNamed(const std::string &Name) const {
3050 Record *N = Records.getDef(Name);
3051 if (!N || !N->isSubClassOf("SDNode"))
3052 PrintFatalError("Error getting SDNode '" + Name + "'!");
3053
3054 return N;
3055}
3056
3057// Parse all of the SDNode definitions for the target, populating SDNodes.
3058void CodeGenDAGPatterns::ParseNodeInfo() {
3059 std::vector<Record*> Nodes = Records.getAllDerivedDefinitions("SDNode");
3060 const CodeGenHwModes &CGH = getTargetInfo().getHwModes();
3061
3062 while (!Nodes.empty()) {
3063 Record *R = Nodes.back();
3064 SDNodes.insert(std::make_pair(R, SDNodeInfo(R, CGH)));
3065 Nodes.pop_back();
3066 }
3067
3068 // Get the builtin intrinsic nodes.
3069 intrinsic_void_sdnode = getSDNodeNamed("intrinsic_void");
3070 intrinsic_w_chain_sdnode = getSDNodeNamed("intrinsic_w_chain");
3071 intrinsic_wo_chain_sdnode = getSDNodeNamed("intrinsic_wo_chain");
3072}
3073
3074/// ParseNodeTransforms - Parse all SDNodeXForm instances into the SDNodeXForms
3075/// map, and emit them to the file as functions.
3076void CodeGenDAGPatterns::ParseNodeTransforms() {
3077 std::vector<Record*> Xforms = Records.getAllDerivedDefinitions("SDNodeXForm");
3078 while (!Xforms.empty()) {
3079 Record *XFormNode = Xforms.back();
3080 Record *SDNode = XFormNode->getValueAsDef("Opcode");
3081 StringRef Code = XFormNode->getValueAsString("XFormFunction");
3082 SDNodeXForms.insert(std::make_pair(XFormNode, NodeXForm(SDNode, Code)));
3083
3084 Xforms.pop_back();
3085 }
3086}
3087
3088void CodeGenDAGPatterns::ParseComplexPatterns() {
3089 std::vector<Record*> AMs = Records.getAllDerivedDefinitions("ComplexPattern");
3090 while (!AMs.empty()) {
3091 ComplexPatterns.insert(std::make_pair(AMs.back(), AMs.back()));
3092 AMs.pop_back();
3093 }
3094}
3095
3096
3097/// ParsePatternFragments - Parse all of the PatFrag definitions in the .td
3098/// file, building up the PatternFragments map. After we've collected them all,
3099/// inline fragments together as necessary, so that there are no references left
3100/// inside a pattern fragment to a pattern fragment.
3101///
3102void CodeGenDAGPatterns::ParsePatternFragments(bool OutFrags) {
3103 std::vector<Record*> Fragments = Records.getAllDerivedDefinitions("PatFrags");
3104
3105 // First step, parse all of the fragments.
3106 for (Record *Frag : Fragments) {
3107 if (OutFrags != Frag->isSubClassOf("OutPatFrag"))
3108 continue;
3109
3110 ListInit *LI = Frag->getValueAsListInit("Fragments");
3111 TreePattern *P =
3112 (PatternFragments[Frag] = std::make_unique<TreePattern>(
3113 Frag, LI, !Frag->isSubClassOf("OutPatFrag"),
3114 *this)).get();
3115
3116 // Validate the argument list, converting it to set, to discard duplicates.
3117 std::vector<std::string> &Args = P->getArgList();
3118 // Copy the args so we can take StringRefs to them.
3119 auto ArgsCopy = Args;
3120 SmallDenseSet<StringRef, 4> OperandsSet;
3121 OperandsSet.insert(ArgsCopy.begin(), ArgsCopy.end());
3122
3123 if (OperandsSet.count(""))
3124 P->error("Cannot have unnamed 'node' values in pattern fragment!");
3125
3126 // Parse the operands list.
3127 DagInit *OpsList = Frag->getValueAsDag("Operands");
3128 DefInit *OpsOp = dyn_cast<DefInit>(OpsList->getOperator());
3129 // Special cases: ops == outs == ins. Different names are used to
3130 // improve readability.
3131 if (!OpsOp ||
3132 (OpsOp->getDef()->getName() != "ops" &&
3133 OpsOp->getDef()->getName() != "outs" &&
3134 OpsOp->getDef()->getName() != "ins"))
3135 P->error("Operands list should start with '(ops ... '!");
3136
3137 // Copy over the arguments.
3138 Args.clear();
3139 for (unsigned j = 0, e = OpsList->getNumArgs(); j != e; ++j) {
3140 if (!isa<DefInit>(OpsList->getArg(j)) ||
3141 cast<DefInit>(OpsList->getArg(j))->getDef()->getName() != "node")
3142 P->error("Operands list should all be 'node' values.");
3143 if (!OpsList->getArgName(j))
3144 P->error("Operands list should have names for each operand!");
3145 StringRef ArgNameStr = OpsList->getArgNameStr(j);
3146 if (!OperandsSet.count(ArgNameStr))
3147 P->error("'" + ArgNameStr +
3148 "' does not occur in pattern or was multiply specified!");
3149 OperandsSet.erase(ArgNameStr);
3150 Args.push_back(ArgNameStr);
3151 }
3152
3153 if (!OperandsSet.empty())
3154 P->error("Operands list does not contain an entry for operand '" +
3155 *OperandsSet.begin() + "'!");
3156
3157 // If there is a node transformation corresponding to this, keep track of
3158 // it.
3159 Record *Transform = Frag->getValueAsDef("OperandTransform");
3160 if (!getSDNodeTransform(Transform).second.empty()) // not noop xform?
3161 for (auto T : P->getTrees())
3162 T->setTransformFn(Transform);
3163 }
3164
3165 // Now that we've parsed all of the tree fragments, do a closure on them so
3166 // that there are not references to PatFrags left inside of them.
3167 for (Record *Frag : Fragments) {
3168 if (OutFrags != Frag->isSubClassOf("OutPatFrag"))
3169 continue;
3170
3171 TreePattern &ThePat = *PatternFragments[Frag];
3172 ThePat.InlinePatternFragments();
3173
3174 // Infer as many types as possible. Don't worry about it if we don't infer
3175 // all of them, some may depend on the inputs of the pattern. Also, don't
3176 // validate type sets; validation may cause spurious failures e.g. if a
3177 // fragment needs floating-point types but the current target does not have
3178 // any (this is only an error if that fragment is ever used!).
3179 {
3180 TypeInfer::SuppressValidation SV(ThePat.getInfer());
3181 ThePat.InferAllTypes();
3182 ThePat.resetError();
3183 }
3184
3185 // If debugging, print out the pattern fragment result.
3186 LLVM_DEBUG(ThePat.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { ThePat.dump(); } } while (false)
;
3187 }
3188}
3189
3190void CodeGenDAGPatterns::ParseDefaultOperands() {
3191 std::vector<Record*> DefaultOps;
3192 DefaultOps = Records.getAllDerivedDefinitions("OperandWithDefaultOps");
3193
3194 // Find some SDNode.
3195 assert(!SDNodes.empty() && "No SDNodes parsed?")((!SDNodes.empty() && "No SDNodes parsed?") ? static_cast
<void> (0) : __assert_fail ("!SDNodes.empty() && \"No SDNodes parsed?\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 3195, __PRETTY_FUNCTION__))
;
3196 Init *SomeSDNode = DefInit::get(SDNodes.begin()->first);
3197
3198 for (unsigned i = 0, e = DefaultOps.size(); i != e; ++i) {
3199 DagInit *DefaultInfo = DefaultOps[i]->getValueAsDag("DefaultOps");
3200
3201 // Clone the DefaultInfo dag node, changing the operator from 'ops' to
3202 // SomeSDnode so that we can parse this.
3203 std::vector<std::pair<Init*, StringInit*> > Ops;
3204 for (unsigned op = 0, e = DefaultInfo->getNumArgs(); op != e; ++op)
3205 Ops.push_back(std::make_pair(DefaultInfo->getArg(op),
3206 DefaultInfo->getArgName(op)));
3207 DagInit *DI = DagInit::get(SomeSDNode, nullptr, Ops);
3208
3209 // Create a TreePattern to parse this.
3210 TreePattern P(DefaultOps[i], DI, false, *this);
3211 assert(P.getNumTrees() == 1 && "This ctor can only produce one tree!")((P.getNumTrees() == 1 && "This ctor can only produce one tree!"
) ? static_cast<void> (0) : __assert_fail ("P.getNumTrees() == 1 && \"This ctor can only produce one tree!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 3211, __PRETTY_FUNCTION__))
;
3212
3213 // Copy the operands over into a DAGDefaultOperand.
3214 DAGDefaultOperand DefaultOpInfo;
3215
3216 const TreePatternNodePtr &T = P.getTree(0);
3217 for (unsigned op = 0, e = T->getNumChildren(); op != e; ++op) {
3218 TreePatternNodePtr TPN = T->getChildShared(op);
3219 while (TPN->ApplyTypeConstraints(P, false))
3220 /* Resolve all types */;
3221
3222 if (TPN->ContainsUnresolvedType(P)) {
3223 PrintFatalError("Value #" + Twine(i) + " of OperandWithDefaultOps '" +
3224 DefaultOps[i]->getName() +
3225 "' doesn't have a concrete type!");
3226 }
3227 DefaultOpInfo.DefaultOps.push_back(std::move(TPN));
3228 }
3229
3230 // Insert it into the DefaultOperands map so we can find it later.
3231 DefaultOperands[DefaultOps[i]] = DefaultOpInfo;
3232 }
3233}
3234
3235/// HandleUse - Given "Pat" a leaf in the pattern, check to see if it is an
3236/// instruction input. Return true if this is a real use.
3237static bool HandleUse(TreePattern &I, TreePatternNodePtr Pat,
3238 std::map<std::string, TreePatternNodePtr> &InstInputs) {
3239 // No name -> not interesting.
3240 if (Pat->getName().empty()) {
3241 if (Pat->isLeaf()) {
3242 DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue());
3243 if (DI && (DI->getDef()->isSubClassOf("RegisterClass") ||
3244 DI->getDef()->isSubClassOf("RegisterOperand")))
3245 I.error("Input " + DI->getDef()->getName() + " must be named!");
3246 }
3247 return false;
3248 }
3249
3250 Record *Rec;
3251 if (Pat->isLeaf()) {
3252 DefInit *DI = dyn_cast<DefInit>(Pat->getLeafValue());
3253 if (!DI)
3254 I.error("Input $" + Pat->getName() + " must be an identifier!");
3255 Rec = DI->getDef();
3256 } else {
3257 Rec = Pat->getOperator();
3258 }
3259
3260 // SRCVALUE nodes are ignored.
3261 if (Rec->getName() == "srcvalue")
3262 return false;
3263
3264 TreePatternNodePtr &Slot = InstInputs[Pat->getName()];
3265 if (!Slot) {
3266 Slot = Pat;
3267 return true;
3268 }
3269 Record *SlotRec;
3270 if (Slot->isLeaf()) {
3271 SlotRec = cast<DefInit>(Slot->getLeafValue())->getDef();
3272 } else {
3273 assert(Slot->getNumChildren() == 0 && "can't be a use with children!")((Slot->getNumChildren() == 0 && "can't be a use with children!"
) ? static_cast<void> (0) : __assert_fail ("Slot->getNumChildren() == 0 && \"can't be a use with children!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 3273, __PRETTY_FUNCTION__))
;
3274 SlotRec = Slot->getOperator();
3275 }
3276
3277 // Ensure that the inputs agree if we've already seen this input.
3278 if (Rec != SlotRec)
3279 I.error("All $" + Pat->getName() + " inputs must agree with each other");
3280 // Ensure that the types can agree as well.
3281 Slot->UpdateNodeType(0, Pat->getExtType(0), I);
3282 Pat->UpdateNodeType(0, Slot->getExtType(0), I);
3283 if (Slot->getExtTypes() != Pat->getExtTypes())
3284 I.error("All $" + Pat->getName() + " inputs must agree with each other");
3285 return true;
3286}
3287
3288/// FindPatternInputsAndOutputs - Scan the specified TreePatternNode (which is
3289/// part of "I", the instruction), computing the set of inputs and outputs of
3290/// the pattern. Report errors if we see anything naughty.
3291void CodeGenDAGPatterns::FindPatternInputsAndOutputs(
3292 TreePattern &I, TreePatternNodePtr Pat,
3293 std::map<std::string, TreePatternNodePtr> &InstInputs,
3294 MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>>
3295 &InstResults,
3296 std::vector<Record *> &InstImpResults) {
3297
3298 // The instruction pattern still has unresolved fragments. For *named*
3299 // nodes we must resolve those here. This may not result in multiple
3300 // alternatives.
3301 if (!Pat->getName().empty()) {
8
Assuming the condition is false
9
Taking false branch
21
Assuming the condition is false
22
Taking false branch
34
Assuming the condition is false
35
Taking false branch
47
Assuming the condition is false
48
Taking false branch
3302 TreePattern SrcPattern(I.getRecord(), Pat, true, *this);
3303 SrcPattern.InlinePatternFragments();
3304 SrcPattern.InferAllTypes();
3305 Pat = SrcPattern.getOnlyTree();
3306 }
3307
3308 if (Pat->isLeaf()) {
10
Taking false branch
23
Taking false branch
36
Taking false branch
49
Calling 'TreePatternNode::isLeaf'
52
Returning from 'TreePatternNode::isLeaf'
53
Taking false branch
3309 bool isUse = HandleUse(I, Pat, InstInputs);
3310 if (!isUse && Pat->getTransformFn())
3311 I.error("Cannot specify a transform function for a non-input value!");
3312 return;
3313 }
3314
3315 if (Pat->getOperator()->getName() == "implicit") {
11
Assuming the condition is false
12
Taking false branch
24
Assuming the condition is false
25
Taking false branch
37
Assuming the condition is false
38
Taking false branch
54
Assuming the condition is true
55
Taking true branch
3316 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) {
56
Assuming 'i' is not equal to 'e'
57
Loop condition is true. Entering loop body
3317 TreePatternNode *Dest = Pat->getChild(i);
3318 if (!Dest->isLeaf())
58
Taking true branch
3319 I.error("implicitly defined value should be a register!");
3320
3321 DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue());
59
Assuming the object is not a 'DefInit'
60
'Val' initialized to a null pointer value
3322 if (!Val
60.1
'Val' is null
60.1
'Val' is null
|| !Val->getDef()->isSubClassOf("Register"))
61
Taking true branch
3323 I.error("implicitly defined value should be a register!");
3324 InstImpResults.push_back(Val->getDef());
62
Called C++ object pointer is null
3325 }
3326 return;
3327 }
3328
3329 if (Pat->getOperator()->getName() != "set") {
13
Taking false branch
26
Taking false branch
39
Taking false branch
3330 // If this is not a set, verify that the children nodes are not void typed,
3331 // and recurse.
3332 for (unsigned i = 0, e = Pat->getNumChildren(); i != e; ++i) {
3333 if (Pat->getChild(i)->getNumTypes() == 0)
3334 I.error("Cannot have void nodes inside of patterns!");
3335 FindPatternInputsAndOutputs(I, Pat->getChildShared(i), InstInputs,
3336 InstResults, InstImpResults);
3337 }
3338
3339 // If this is a non-leaf node with no children, treat it basically as if
3340 // it were a leaf. This handles nodes like (imm).
3341 bool isUse = HandleUse(I, Pat, InstInputs);
3342
3343 if (!isUse && Pat->getTransformFn())
3344 I.error("Cannot specify a transform function for a non-input value!");
3345 return;
3346 }
3347
3348 // Otherwise, this is a set, validate and collect instruction results.
3349 if (Pat->getNumChildren() == 0)
14
Assuming the condition is false
15
Taking false branch
27
Assuming the condition is false
28
Taking false branch
40
Assuming the condition is false
41
Taking false branch
3350 I.error("set requires operands!");
3351
3352 if (Pat->getTransformFn())
16
Assuming the condition is false
17
Taking false branch
29
Assuming the condition is false
30
Taking false branch
42
Assuming the condition is false
43
Taking false branch
3353 I.error("Cannot specify a transform function on a set node!");
3354
3355 // Check the set destinations.
3356 unsigned NumDests = Pat->getNumChildren()-1;
3357 for (unsigned i = 0; i != NumDests; ++i) {
18
Assuming 'i' is equal to 'NumDests'
19
Loop condition is false. Execution continues on line 3391
31
Assuming 'i' is equal to 'NumDests'
32
Loop condition is false. Execution continues on line 3391
44
Assuming 'i' is equal to 'NumDests'
45
Loop condition is false. Execution continues on line 3391
3358 TreePatternNodePtr Dest = Pat->getChildShared(i);
3359 // For set destinations we also must resolve fragments here.
3360 TreePattern DestPattern(I.getRecord(), Dest, false, *this);
3361 DestPattern.InlinePatternFragments();
3362 DestPattern.InferAllTypes();
3363 Dest = DestPattern.getOnlyTree();
3364
3365 if (!Dest->isLeaf())
3366 I.error("set destination should be a register!");
3367
3368 DefInit *Val = dyn_cast<DefInit>(Dest->getLeafValue());
3369 if (!Val) {
3370 I.error("set destination should be a register!");
3371 continue;
3372 }
3373
3374 if (Val->getDef()->isSubClassOf("RegisterClass") ||
3375 Val->getDef()->isSubClassOf("ValueType") ||
3376 Val->getDef()->isSubClassOf("RegisterOperand") ||
3377 Val->getDef()->isSubClassOf("PointerLikeRegClass")) {
3378 if (Dest->getName().empty())
3379 I.error("set destination must have a name!");
3380 if (InstResults.count(Dest->getName()))
3381 I.error("cannot set '" + Dest->getName() + "' multiple times");
3382 InstResults[Dest->getName()] = Dest;
3383 } else if (Val->getDef()->isSubClassOf("Register")) {
3384 InstImpResults.push_back(Val->getDef());
3385 } else {
3386 I.error("set destination should be a register!");
3387 }
3388 }
3389
3390 // Verify and collect info from the computation.
3391 FindPatternInputsAndOutputs(I, Pat->getChildShared(NumDests), InstInputs,
20
Calling 'CodeGenDAGPatterns::FindPatternInputsAndOutputs'
33
Calling 'CodeGenDAGPatterns::FindPatternInputsAndOutputs'
46
Calling 'CodeGenDAGPatterns::FindPatternInputsAndOutputs'
3392 InstResults, InstImpResults);
3393}
3394
3395//===----------------------------------------------------------------------===//
3396// Instruction Analysis
3397//===----------------------------------------------------------------------===//
3398
3399class InstAnalyzer {
3400 const CodeGenDAGPatterns &CDP;
3401public:
3402 bool hasSideEffects;
3403 bool mayStore;
3404 bool mayLoad;
3405 bool isBitcast;
3406 bool isVariadic;
3407 bool hasChain;
3408
3409 InstAnalyzer(const CodeGenDAGPatterns &cdp)
3410 : CDP(cdp), hasSideEffects(false), mayStore(false), mayLoad(false),
3411 isBitcast(false), isVariadic(false), hasChain(false) {}
3412
3413 void Analyze(const PatternToMatch &Pat) {
3414 const TreePatternNode *N = Pat.getSrcPattern();
3415 AnalyzeNode(N);
3416 // These properties are detected only on the root node.
3417 isBitcast = IsNodeBitcast(N);
3418 }
3419
3420private:
3421 bool IsNodeBitcast(const TreePatternNode *N) const {
3422 if (hasSideEffects || mayLoad || mayStore || isVariadic)
3423 return false;
3424
3425 if (N->isLeaf())
3426 return false;
3427 if (N->getNumChildren() != 1 || !N->getChild(0)->isLeaf())
3428 return false;
3429
3430 const SDNodeInfo &OpInfo = CDP.getSDNodeInfo(N->getOperator());
3431 if (OpInfo.getNumResults() != 1 || OpInfo.getNumOperands() != 1)
3432 return false;
3433 return OpInfo.getEnumName() == "ISD::BITCAST";
3434 }
3435
3436public:
3437 void AnalyzeNode(const TreePatternNode *N) {
3438 if (N->isLeaf()) {
3439 if (DefInit *DI = dyn_cast<DefInit>(N->getLeafValue())) {
3440 Record *LeafRec = DI->getDef();
3441 // Handle ComplexPattern leaves.
3442 if (LeafRec->isSubClassOf("ComplexPattern")) {
3443 const ComplexPattern &CP = CDP.getComplexPattern(LeafRec);
3444 if (CP.hasProperty(SDNPMayStore)) mayStore = true;
3445 if (CP.hasProperty(SDNPMayLoad)) mayLoad = true;
3446 if (CP.hasProperty(SDNPSideEffect)) hasSideEffects = true;
3447 }
3448 }
3449 return;
3450 }
3451
3452 // Analyze children.
3453 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
3454 AnalyzeNode(N->getChild(i));
3455
3456 // Notice properties of the node.
3457 if (N->NodeHasProperty(SDNPMayStore, CDP)) mayStore = true;
3458 if (N->NodeHasProperty(SDNPMayLoad, CDP)) mayLoad = true;
3459 if (N->NodeHasProperty(SDNPSideEffect, CDP)) hasSideEffects = true;
3460 if (N->NodeHasProperty(SDNPVariadic, CDP)) isVariadic = true;
3461 if (N->NodeHasProperty(SDNPHasChain, CDP)) hasChain = true;
3462
3463 if (const CodeGenIntrinsic *IntInfo = N->getIntrinsicInfo(CDP)) {
3464 // If this is an intrinsic, analyze it.
3465 if (IntInfo->ModRef & CodeGenIntrinsic::MR_Ref)
3466 mayLoad = true;// These may load memory.
3467
3468 if (IntInfo->ModRef & CodeGenIntrinsic::MR_Mod)
3469 mayStore = true;// Intrinsics that can write to memory are 'mayStore'.
3470
3471 if (IntInfo->ModRef >= CodeGenIntrinsic::ReadWriteMem ||
3472 IntInfo->hasSideEffects)
3473 // ReadWriteMem intrinsics can have other strange effects.
3474 hasSideEffects = true;
3475 }
3476 }
3477
3478};
3479
3480static bool InferFromPattern(CodeGenInstruction &InstInfo,
3481 const InstAnalyzer &PatInfo,
3482 Record *PatDef) {
3483 bool Error = false;
3484
3485 // Remember where InstInfo got its flags.
3486 if (InstInfo.hasUndefFlags())
3487 InstInfo.InferredFrom = PatDef;
3488
3489 // Check explicitly set flags for consistency.
3490 if (InstInfo.hasSideEffects != PatInfo.hasSideEffects &&
3491 !InstInfo.hasSideEffects_Unset) {
3492 // Allow explicitly setting hasSideEffects = 1 on instructions, even when
3493 // the pattern has no side effects. That could be useful for div/rem
3494 // instructions that may trap.
3495 if (!InstInfo.hasSideEffects) {
3496 Error = true;
3497 PrintError(PatDef->getLoc(), "Pattern doesn't match hasSideEffects = " +
3498 Twine(InstInfo.hasSideEffects));
3499 }
3500 }
3501
3502 if (InstInfo.mayStore != PatInfo.mayStore && !InstInfo.mayStore_Unset) {
3503 Error = true;
3504 PrintError(PatDef->getLoc(), "Pattern doesn't match mayStore = " +
3505 Twine(InstInfo.mayStore));
3506 }
3507
3508 if (InstInfo.mayLoad != PatInfo.mayLoad && !InstInfo.mayLoad_Unset) {
3509 // Allow explicitly setting mayLoad = 1, even when the pattern has no loads.
3510 // Some targets translate immediates to loads.
3511 if (!InstInfo.mayLoad) {
3512 Error = true;
3513 PrintError(PatDef->getLoc(), "Pattern doesn't match mayLoad = " +
3514 Twine(InstInfo.mayLoad));
3515 }
3516 }
3517
3518 // Transfer inferred flags.
3519 InstInfo.hasSideEffects |= PatInfo.hasSideEffects;
3520 InstInfo.mayStore |= PatInfo.mayStore;
3521 InstInfo.mayLoad |= PatInfo.mayLoad;
3522
3523 // These flags are silently added without any verification.
3524 // FIXME: To match historical behavior of TableGen, for now add those flags
3525 // only when we're inferring from the primary instruction pattern.
3526 if (PatDef->isSubClassOf("Instruction")) {
3527 InstInfo.isBitcast |= PatInfo.isBitcast;
3528 InstInfo.hasChain |= PatInfo.hasChain;
3529 InstInfo.hasChain_Inferred = true;
3530 }
3531
3532 // Don't infer isVariadic. This flag means something different on SDNodes and
3533 // instructions. For example, a CALL SDNode is variadic because it has the
3534 // call arguments as operands, but a CALL instruction is not variadic - it
3535 // has argument registers as implicit, not explicit uses.
3536
3537 return Error;
3538}
3539
3540/// hasNullFragReference - Return true if the DAG has any reference to the
3541/// null_frag operator.
3542static bool hasNullFragReference(DagInit *DI) {
3543 DefInit *OpDef = dyn_cast<DefInit>(DI->getOperator());
3544 if (!OpDef) return false;
3545 Record *Operator = OpDef->getDef();
3546
3547 // If this is the null fragment, return true.
3548 if (Operator->getName() == "null_frag") return true;
3549 // If any of the arguments reference the null fragment, return true.
3550 for (unsigned i = 0, e = DI->getNumArgs(); i != e; ++i) {
3551 DagInit *Arg = dyn_cast<DagInit>(DI->getArg(i));
3552 if (Arg && hasNullFragReference(Arg))
3553 return true;
3554 }
3555
3556 return false;
3557}
3558
3559/// hasNullFragReference - Return true if any DAG in the list references
3560/// the null_frag operator.
3561static bool hasNullFragReference(ListInit *LI) {
3562 for (Init *I : LI->getValues()) {
3563 DagInit *DI = dyn_cast<DagInit>(I);
3564 assert(DI && "non-dag in an instruction Pattern list?!")((DI && "non-dag in an instruction Pattern list?!") ?
static_cast<void> (0) : __assert_fail ("DI && \"non-dag in an instruction Pattern list?!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 3564, __PRETTY_FUNCTION__))
;
3565 if (hasNullFragReference(DI))
3566 return true;
3567 }
3568 return false;
3569}
3570
3571/// Get all the instructions in a tree.
3572static void
3573getInstructionsInTree(TreePatternNode *Tree, SmallVectorImpl<Record*> &Instrs) {
3574 if (Tree->isLeaf())
3575 return;
3576 if (Tree->getOperator()->isSubClassOf("Instruction"))
3577 Instrs.push_back(Tree->getOperator());
3578 for (unsigned i = 0, e = Tree->getNumChildren(); i != e; ++i)
3579 getInstructionsInTree(Tree->getChild(i), Instrs);
3580}
3581
3582/// Check the class of a pattern leaf node against the instruction operand it
3583/// represents.
3584static bool checkOperandClass(CGIOperandList::OperandInfo &OI,
3585 Record *Leaf) {
3586 if (OI.Rec == Leaf)
3587 return true;
3588
3589 // Allow direct value types to be used in instruction set patterns.
3590 // The type will be checked later.
3591 if (Leaf->isSubClassOf("ValueType"))
3592 return true;
3593
3594 // Patterns can also be ComplexPattern instances.
3595 if (Leaf->isSubClassOf("ComplexPattern"))
3596 return true;
3597
3598 return false;
3599}
3600
3601void CodeGenDAGPatterns::parseInstructionPattern(
3602 CodeGenInstruction &CGI, ListInit *Pat, DAGInstMap &DAGInsts) {
3603
3604 assert(!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!")((!DAGInsts.count(CGI.TheDef) && "Instruction already parsed!"
) ? static_cast<void> (0) : __assert_fail ("!DAGInsts.count(CGI.TheDef) && \"Instruction already parsed!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 3604, __PRETTY_FUNCTION__))
;
1
Assuming the condition is true
2
'?' condition is true
3605
3606 // Parse the instruction.
3607 TreePattern I(CGI.TheDef, Pat, true, *this);
3608
3609 // InstInputs - Keep track of all of the inputs of the instruction, along
3610 // with the record they are declared as.
3611 std::map<std::string, TreePatternNodePtr> InstInputs;
3612
3613 // InstResults - Keep track of all the virtual registers that are 'set'
3614 // in the instruction, including what reg class they are.
3615 MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>>
3616 InstResults;
3617
3618 std::vector<Record*> InstImpResults;
3619
3620 // Verify that the top-level forms in the instruction are of void type, and
3621 // fill in the InstResults map.
3622 SmallString<32> TypesString;
3623 for (unsigned j = 0, e = I.getNumTrees(); j != e; ++j) {
3
Assuming 'j' is not equal to 'e'
4
Loop condition is true. Entering loop body
3624 TypesString.clear();
3625 TreePatternNodePtr Pat = I.getTree(j);
3626 if (Pat->getNumTypes() != 0) {
5
Assuming the condition is false
6
Taking false branch
3627 raw_svector_ostream OS(TypesString);
3628 for (unsigned k = 0, ke = Pat->getNumTypes(); k != ke; ++k) {
3629 if (k > 0)
3630 OS << ", ";
3631 Pat->getExtType(k).writeToStream(OS);
3632 }
3633 I.error("Top-level forms in instruction pattern should have"
3634 " void types, has types " +
3635 OS.str());
3636 }
3637
3638 // Find inputs and outputs, and verify the structure of the uses/defs.
3639 FindPatternInputsAndOutputs(I, Pat, InstInputs, InstResults,
7
Calling 'CodeGenDAGPatterns::FindPatternInputsAndOutputs'
3640 InstImpResults);
3641 }
3642
3643 // Now that we have inputs and outputs of the pattern, inspect the operands
3644 // list for the instruction. This determines the order that operands are
3645 // added to the machine instruction the node corresponds to.
3646 unsigned NumResults = InstResults.size();
3647
3648 // Parse the operands list from the (ops) list, validating it.
3649 assert(I.getArgList().empty() && "Args list should still be empty here!")((I.getArgList().empty() && "Args list should still be empty here!"
) ? static_cast<void> (0) : __assert_fail ("I.getArgList().empty() && \"Args list should still be empty here!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 3649, __PRETTY_FUNCTION__))
;
3650
3651 // Check that all of the results occur first in the list.
3652 std::vector<Record*> Results;
3653 std::vector<unsigned> ResultIndices;
3654 SmallVector<TreePatternNodePtr, 2> ResNodes;
3655 for (unsigned i = 0; i != NumResults; ++i) {
3656 if (i == CGI.Operands.size()) {
3657 const std::string &OpName =
3658 std::find_if(InstResults.begin(), InstResults.end(),
3659 [](const std::pair<std::string, TreePatternNodePtr> &P) {
3660 return P.second;
3661 })
3662 ->first;
3663
3664 I.error("'" + OpName + "' set but does not appear in operand list!");
3665 }
3666
3667 const std::string &OpName = CGI.Operands[i].Name;
3668
3669 // Check that it exists in InstResults.
3670 auto InstResultIter = InstResults.find(OpName);
3671 if (InstResultIter == InstResults.end() || !InstResultIter->second)
3672 I.error("Operand $" + OpName + " does not exist in operand list!");
3673
3674 TreePatternNodePtr RNode = InstResultIter->second;
3675 Record *R = cast<DefInit>(RNode->getLeafValue())->getDef();
3676 ResNodes.push_back(std::move(RNode));
3677 if (!R)
3678 I.error("Operand $" + OpName + " should be a set destination: all "
3679 "outputs must occur before inputs in operand list!");
3680
3681 if (!checkOperandClass(CGI.Operands[i], R))
3682 I.error("Operand $" + OpName + " class mismatch!");
3683
3684 // Remember the return type.
3685 Results.push_back(CGI.Operands[i].Rec);
3686
3687 // Remember the result index.
3688 ResultIndices.push_back(std::distance(InstResults.begin(), InstResultIter));
3689
3690 // Okay, this one checks out.
3691 InstResultIter->second = nullptr;
3692 }
3693
3694 // Loop over the inputs next.
3695 std::vector<TreePatternNodePtr> ResultNodeOperands;
3696 std::vector<Record*> Operands;
3697 for (unsigned i = NumResults, e = CGI.Operands.size(); i != e; ++i) {
3698 CGIOperandList::OperandInfo &Op = CGI.Operands[i];
3699 const std::string &OpName = Op.Name;
3700 if (OpName.empty())
3701 I.error("Operand #" + Twine(i) + " in operands list has no name!");
3702
3703 if (!InstInputs.count(OpName)) {
3704 // If this is an operand with a DefaultOps set filled in, we can ignore
3705 // this. When we codegen it, we will do so as always executed.
3706 if (Op.Rec->isSubClassOf("OperandWithDefaultOps")) {
3707 // Does it have a non-empty DefaultOps field? If so, ignore this
3708 // operand.
3709 if (!getDefaultOperand(Op.Rec).DefaultOps.empty())
3710 continue;
3711 }
3712 I.error("Operand $" + OpName +
3713 " does not appear in the instruction pattern");
3714 }
3715 TreePatternNodePtr InVal = InstInputs[OpName];
3716 InstInputs.erase(OpName); // It occurred, remove from map.
3717
3718 if (InVal->isLeaf() && isa<DefInit>(InVal->getLeafValue())) {
3719 Record *InRec = static_cast<DefInit*>(InVal->getLeafValue())->getDef();
3720 if (!checkOperandClass(Op, InRec))
3721 I.error("Operand $" + OpName + "'s register class disagrees"
3722 " between the operand and pattern");
3723 }
3724 Operands.push_back(Op.Rec);
3725
3726 // Construct the result for the dest-pattern operand list.
3727 TreePatternNodePtr OpNode = InVal->clone();
3728
3729 // No predicate is useful on the result.
3730 OpNode->clearPredicateCalls();
3731
3732 // Promote the xform function to be an explicit node if set.
3733 if (Record *Xform = OpNode->getTransformFn()) {
3734 OpNode->setTransformFn(nullptr);
3735 std::vector<TreePatternNodePtr> Children;
3736 Children.push_back(OpNode);
3737 OpNode = std::make_shared<TreePatternNode>(Xform, std::move(Children),
3738 OpNode->getNumTypes());
3739 }
3740
3741 ResultNodeOperands.push_back(std::move(OpNode));
3742 }
3743
3744 if (!InstInputs.empty())
3745 I.error("Input operand $" + InstInputs.begin()->first +
3746 " occurs in pattern but not in operands list!");
3747
3748 TreePatternNodePtr ResultPattern = std::make_shared<TreePatternNode>(
3749 I.getRecord(), std::move(ResultNodeOperands),
3750 GetNumNodeResults(I.getRecord(), *this));
3751 // Copy fully inferred output node types to instruction result pattern.
3752 for (unsigned i = 0; i != NumResults; ++i) {
3753 assert(ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled")((ResNodes[i]->getNumTypes() == 1 && "FIXME: Unhandled"
) ? static_cast<void> (0) : __assert_fail ("ResNodes[i]->getNumTypes() == 1 && \"FIXME: Unhandled\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 3753, __PRETTY_FUNCTION__))
;
3754 ResultPattern->setType(i, ResNodes[i]->getExtType(0));
3755 ResultPattern->setResultIndex(i, ResultIndices[i]);
3756 }
3757
3758 // FIXME: Assume only the first tree is the pattern. The others are clobber
3759 // nodes.
3760 TreePatternNodePtr Pattern = I.getTree(0);
3761 TreePatternNodePtr SrcPattern;
3762 if (Pattern->getOperator()->getName() == "set") {
3763 SrcPattern = Pattern->getChild(Pattern->getNumChildren()-1)->clone();
3764 } else{
3765 // Not a set (store or something?)
3766 SrcPattern = Pattern;
3767 }
3768
3769 // Create and insert the instruction.
3770 // FIXME: InstImpResults should not be part of DAGInstruction.
3771 Record *R = I.getRecord();
3772 DAGInsts.emplace(std::piecewise_construct, std::forward_as_tuple(R),
3773 std::forward_as_tuple(Results, Operands, InstImpResults,
3774 SrcPattern, ResultPattern));
3775
3776 LLVM_DEBUG(I.dump())do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { I.dump(); } } while (false)
;
3777}
3778
3779/// ParseInstructions - Parse all of the instructions, inlining and resolving
3780/// any fragments involved. This populates the Instructions list with fully
3781/// resolved instructions.
3782void CodeGenDAGPatterns::ParseInstructions() {
3783 std::vector<Record*> Instrs = Records.getAllDerivedDefinitions("Instruction");
3784
3785 for (Record *Instr : Instrs) {
3786 ListInit *LI = nullptr;
3787
3788 if (isa<ListInit>(Instr->getValueInit("Pattern")))
3789 LI = Instr->getValueAsListInit("Pattern");
3790
3791 // If there is no pattern, only collect minimal information about the
3792 // instruction for its operand list. We have to assume that there is one
3793 // result, as we have no detailed info. A pattern which references the
3794 // null_frag operator is as-if no pattern were specified. Normally this
3795 // is from a multiclass expansion w/ a SDPatternOperator passed in as
3796 // null_frag.
3797 if (!LI || LI->empty() || hasNullFragReference(LI)) {
3798 std::vector<Record*> Results;
3799 std::vector<Record*> Operands;
3800
3801 CodeGenInstruction &InstInfo = Target.getInstruction(Instr);
3802
3803 if (InstInfo.Operands.size() != 0) {
3804 for (unsigned j = 0, e = InstInfo.Operands.NumDefs; j < e; ++j)
3805 Results.push_back(InstInfo.Operands[j].Rec);
3806
3807 // The rest are inputs.
3808 for (unsigned j = InstInfo.Operands.NumDefs,
3809 e = InstInfo.Operands.size(); j < e; ++j)
3810 Operands.push_back(InstInfo.Operands[j].Rec);
3811 }
3812
3813 // Create and insert the instruction.
3814 std::vector<Record*> ImpResults;
3815 Instructions.insert(std::make_pair(Instr,
3816 DAGInstruction(Results, Operands, ImpResults)));
3817 continue; // no pattern.
3818 }
3819
3820 CodeGenInstruction &CGI = Target.getInstruction(Instr);
3821 parseInstructionPattern(CGI, LI, Instructions);
3822 }
3823
3824 // If we can, convert the instructions to be patterns that are matched!
3825 for (auto &Entry : Instructions) {
3826 Record *Instr = Entry.first;
3827 DAGInstruction &TheInst = Entry.second;
3828 TreePatternNodePtr SrcPattern = TheInst.getSrcPattern();
3829 TreePatternNodePtr ResultPattern = TheInst.getResultPattern();
3830
3831 if (SrcPattern && ResultPattern) {
3832 TreePattern Pattern(Instr, SrcPattern, true, *this);
3833 TreePattern Result(Instr, ResultPattern, false, *this);
3834 ParseOnePattern(Instr, Pattern, Result, TheInst.getImpResults());
3835 }
3836 }
3837}
3838
3839typedef std::pair<TreePatternNode *, unsigned> NameRecord;
3840
3841static void FindNames(TreePatternNode *P,
3842 std::map<std::string, NameRecord> &Names,
3843 TreePattern *PatternTop) {
3844 if (!P->getName().empty()) {
3845 NameRecord &Rec = Names[P->getName()];
3846 // If this is the first instance of the name, remember the node.
3847 if (Rec.second++ == 0)
3848 Rec.first = P;
3849 else if (Rec.first->getExtTypes() != P->getExtTypes())
3850 PatternTop->error("repetition of value: $" + P->getName() +
3851 " where different uses have different types!");
3852 }
3853
3854 if (!P->isLeaf()) {
3855 for (unsigned i = 0, e = P->getNumChildren(); i != e; ++i)
3856 FindNames(P->getChild(i), Names, PatternTop);
3857 }
3858}
3859
3860std::vector<Predicate> CodeGenDAGPatterns::makePredList(ListInit *L) {
3861 std::vector<Predicate> Preds;
3862 for (Init *I : L->getValues()) {
3863 if (DefInit *Pred = dyn_cast<DefInit>(I))
3864 Preds.push_back(Pred->getDef());
3865 else
3866 llvm_unreachable("Non-def on the list")::llvm::llvm_unreachable_internal("Non-def on the list", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 3866)
;
3867 }
3868
3869 // Sort so that different orders get canonicalized to the same string.
3870 llvm::sort(Preds);
3871 return Preds;
3872}
3873
3874void CodeGenDAGPatterns::AddPatternToMatch(TreePattern *Pattern,
3875 PatternToMatch &&PTM) {
3876 // Do some sanity checking on the pattern we're about to match.
3877 std::string Reason;
3878 if (!PTM.getSrcPattern()->canPatternMatch(Reason, *this)) {
3879 PrintWarning(Pattern->getRecord()->getLoc(),
3880 Twine("Pattern can never match: ") + Reason);
3881 return;
3882 }
3883
3884 // If the source pattern's root is a complex pattern, that complex pattern
3885 // must specify the nodes it can potentially match.
3886 if (const ComplexPattern *CP =
3887 PTM.getSrcPattern()->getComplexPatternInfo(*this))
3888 if (CP->getRootNodes().empty())
3889 Pattern->error("ComplexPattern at root must specify list of opcodes it"
3890 " could match");
3891
3892
3893 // Find all of the named values in the input and output, ensure they have the
3894 // same type.
3895 std::map<std::string, NameRecord> SrcNames, DstNames;
3896 FindNames(PTM.getSrcPattern(), SrcNames, Pattern);
3897 FindNames(PTM.getDstPattern(), DstNames, Pattern);
3898
3899 // Scan all of the named values in the destination pattern, rejecting them if
3900 // they don't exist in the input pattern.
3901 for (const auto &Entry : DstNames) {
3902 if (SrcNames[Entry.first].first == nullptr)
3903 Pattern->error("Pattern has input without matching name in output: $" +
3904 Entry.first);
3905 }
3906
3907 // Scan all of the named values in the source pattern, rejecting them if the
3908 // name isn't used in the dest, and isn't used to tie two values together.
3909 for (const auto &Entry : SrcNames)
3910 if (DstNames[Entry.first].first == nullptr &&
3911 SrcNames[Entry.first].second == 1)
3912 Pattern->error("Pattern has dead named input: $" + Entry.first);
3913
3914 PatternsToMatch.push_back(PTM);
3915}
3916
3917void CodeGenDAGPatterns::InferInstructionFlags() {
3918 ArrayRef<const CodeGenInstruction*> Instructions =
3919 Target.getInstructionsByEnumValue();
3920
3921 unsigned Errors = 0;
3922
3923 // Try to infer flags from all patterns in PatternToMatch. These include
3924 // both the primary instruction patterns (which always come first) and
3925 // patterns defined outside the instruction.
3926 for (const PatternToMatch &PTM : ptms()) {
3927 // We can only infer from single-instruction patterns, otherwise we won't
3928 // know which instruction should get the flags.
3929 SmallVector<Record*, 8> PatInstrs;
3930 getInstructionsInTree(PTM.getDstPattern(), PatInstrs);
3931 if (PatInstrs.size() != 1)
3932 continue;
3933
3934 // Get the single instruction.
3935 CodeGenInstruction &InstInfo = Target.getInstruction(PatInstrs.front());
3936
3937 // Only infer properties from the first pattern. We'll verify the others.
3938 if (InstInfo.InferredFrom)
3939 continue;
3940
3941 InstAnalyzer PatInfo(*this);
3942 PatInfo.Analyze(PTM);
3943 Errors += InferFromPattern(InstInfo, PatInfo, PTM.getSrcRecord());
3944 }
3945
3946 if (Errors)
3947 PrintFatalError("pattern conflicts");
3948
3949 // If requested by the target, guess any undefined properties.
3950 if (Target.guessInstructionProperties()) {
3951 for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
3952 CodeGenInstruction *InstInfo =
3953 const_cast<CodeGenInstruction *>(Instructions[i]);
3954 if (InstInfo->InferredFrom)
3955 continue;
3956 // The mayLoad and mayStore flags default to false.
3957 // Conservatively assume hasSideEffects if it wasn't explicit.
3958 if (InstInfo->hasSideEffects_Unset)
3959 InstInfo->hasSideEffects = true;
3960 }
3961 return;
3962 }
3963
3964 // Complain about any flags that are still undefined.
3965 for (unsigned i = 0, e = Instructions.size(); i != e; ++i) {
3966 CodeGenInstruction *InstInfo =
3967 const_cast<CodeGenInstruction *>(Instructions[i]);
3968 if (InstInfo->InferredFrom)
3969 continue;
3970 if (InstInfo->hasSideEffects_Unset)
3971 PrintError(InstInfo->TheDef->getLoc(),
3972 "Can't infer hasSideEffects from patterns");
3973 if (InstInfo->mayStore_Unset)
3974 PrintError(InstInfo->TheDef->getLoc(),
3975 "Can't infer mayStore from patterns");
3976 if (InstInfo->mayLoad_Unset)
3977 PrintError(InstInfo->TheDef->getLoc(),
3978 "Can't infer mayLoad from patterns");
3979 }
3980}
3981
3982
3983/// Verify instruction flags against pattern node properties.
3984void CodeGenDAGPatterns::VerifyInstructionFlags() {
3985 unsigned Errors = 0;
3986 for (ptm_iterator I = ptm_begin(), E = ptm_end(); I != E; ++I) {
3987 const PatternToMatch &PTM = *I;
3988 SmallVector<Record*, 8> Instrs;
3989 getInstructionsInTree(PTM.getDstPattern(), Instrs);
3990 if (Instrs.empty())
3991 continue;
3992
3993 // Count the number of instructions with each flag set.
3994 unsigned NumSideEffects = 0;
3995 unsigned NumStores = 0;
3996 unsigned NumLoads = 0;
3997 for (const Record *Instr : Instrs) {
3998 const CodeGenInstruction &InstInfo = Target.getInstruction(Instr);
3999 NumSideEffects += InstInfo.hasSideEffects;
4000 NumStores += InstInfo.mayStore;
4001 NumLoads += InstInfo.mayLoad;
4002 }
4003
4004 // Analyze the source pattern.
4005 InstAnalyzer PatInfo(*this);
4006 PatInfo.Analyze(PTM);
4007
4008 // Collect error messages.
4009 SmallVector<std::string, 4> Msgs;
4010
4011 // Check for missing flags in the output.
4012 // Permit extra flags for now at least.
4013 if (PatInfo.hasSideEffects && !NumSideEffects)
4014 Msgs.push_back("pattern has side effects, but hasSideEffects isn't set");
4015
4016 // Don't verify store flags on instructions with side effects. At least for
4017 // intrinsics, side effects implies mayStore.
4018 if (!PatInfo.hasSideEffects && PatInfo.mayStore && !NumStores)
4019 Msgs.push_back("pattern may store, but mayStore isn't set");
4020
4021 // Similarly, mayStore implies mayLoad on intrinsics.
4022 if (!PatInfo.mayStore && PatInfo.mayLoad && !NumLoads)
4023 Msgs.push_back("pattern may load, but mayLoad isn't set");
4024
4025 // Print error messages.
4026 if (Msgs.empty())
4027 continue;
4028 ++Errors;
4029
4030 for (const std::string &Msg : Msgs)
4031 PrintError(PTM.getSrcRecord()->getLoc(), Twine(Msg) + " on the " +
4032 (Instrs.size() == 1 ?
4033 "instruction" : "output instructions"));
4034 // Provide the location of the relevant instruction definitions.
4035 for (const Record *Instr : Instrs) {
4036 if (Instr != PTM.getSrcRecord())
4037 PrintError(Instr->getLoc(), "defined here");
4038 const CodeGenInstruction &InstInfo = Target.getInstruction(Instr);
4039 if (InstInfo.InferredFrom &&
4040 InstInfo.InferredFrom != InstInfo.TheDef &&
4041 InstInfo.InferredFrom != PTM.getSrcRecord())
4042 PrintError(InstInfo.InferredFrom->getLoc(), "inferred from pattern");
4043 }
4044 }
4045 if (Errors)
4046 PrintFatalError("Errors in DAG patterns");
4047}
4048
4049/// Given a pattern result with an unresolved type, see if we can find one
4050/// instruction with an unresolved result type. Force this result type to an
4051/// arbitrary element if it's possible types to converge results.
4052static bool ForceArbitraryInstResultType(TreePatternNode *N, TreePattern &TP) {
4053 if (N->isLeaf())
4054 return false;
4055
4056 // Analyze children.
4057 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
4058 if (ForceArbitraryInstResultType(N->getChild(i), TP))
4059 return true;
4060
4061 if (!N->getOperator()->isSubClassOf("Instruction"))
4062 return false;
4063
4064 // If this type is already concrete or completely unknown we can't do
4065 // anything.
4066 TypeInfer &TI = TP.getInfer();
4067 for (unsigned i = 0, e = N->getNumTypes(); i != e; ++i) {
4068 if (N->getExtType(i).empty() || TI.isConcrete(N->getExtType(i), false))
4069 continue;
4070
4071 // Otherwise, force its type to an arbitrary choice.
4072 if (TI.forceArbitrary(N->getExtType(i)))
4073 return true;
4074 }
4075
4076 return false;
4077}
4078
4079// Promote xform function to be an explicit node wherever set.
4080static TreePatternNodePtr PromoteXForms(TreePatternNodePtr N) {
4081 if (Record *Xform = N->getTransformFn()) {
4082 N->setTransformFn(nullptr);
4083 std::vector<TreePatternNodePtr> Children;
4084 Children.push_back(PromoteXForms(N));
4085 return std::make_shared<TreePatternNode>(Xform, std::move(Children),
4086 N->getNumTypes());
4087 }
4088
4089 if (!N->isLeaf())
4090 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
4091 TreePatternNodePtr Child = N->getChildShared(i);
4092 N->setChild(i, PromoteXForms(Child));
4093 }
4094 return N;
4095}
4096
4097void CodeGenDAGPatterns::ParseOnePattern(Record *TheDef,
4098 TreePattern &Pattern, TreePattern &Result,
4099 const std::vector<Record *> &InstImpResults) {
4100
4101 // Inline pattern fragments and expand multiple alternatives.
4102 Pattern.InlinePatternFragments();
4103 Result.InlinePatternFragments();
4104
4105 if (Result.getNumTrees() != 1)
4106 Result.error("Cannot use multi-alternative fragments in result pattern!");
4107
4108 // Infer types.
4109 bool IterateInference;
4110 bool InferredAllPatternTypes, InferredAllResultTypes;
4111 do {
4112 // Infer as many types as possible. If we cannot infer all of them, we
4113 // can never do anything with this pattern: report it to the user.
4114 InferredAllPatternTypes =
4115 Pattern.InferAllTypes(&Pattern.getNamedNodesMap());
4116
4117 // Infer as many types as possible. If we cannot infer all of them, we
4118 // can never do anything with this pattern: report it to the user.
4119 InferredAllResultTypes =
4120 Result.InferAllTypes(&Pattern.getNamedNodesMap());
4121
4122 IterateInference = false;
4123
4124 // Apply the type of the result to the source pattern. This helps us
4125 // resolve cases where the input type is known to be a pointer type (which
4126 // is considered resolved), but the result knows it needs to be 32- or
4127 // 64-bits. Infer the other way for good measure.
4128 for (auto T : Pattern.getTrees())
4129 for (unsigned i = 0, e = std::min(Result.getOnlyTree()->getNumTypes(),
4130 T->getNumTypes());
4131 i != e; ++i) {
4132 IterateInference |= T->UpdateNodeType(
4133 i, Result.getOnlyTree()->getExtType(i), Result);
4134 IterateInference |= Result.getOnlyTree()->UpdateNodeType(
4135 i, T->getExtType(i), Result);
4136 }
4137
4138 // If our iteration has converged and the input pattern's types are fully
4139 // resolved but the result pattern is not fully resolved, we may have a
4140 // situation where we have two instructions in the result pattern and
4141 // the instructions require a common register class, but don't care about
4142 // what actual MVT is used. This is actually a bug in our modelling:
4143 // output patterns should have register classes, not MVTs.
4144 //
4145 // In any case, to handle this, we just go through and disambiguate some
4146 // arbitrary types to the result pattern's nodes.
4147 if (!IterateInference && InferredAllPatternTypes &&
4148 !InferredAllResultTypes)
4149 IterateInference =
4150 ForceArbitraryInstResultType(Result.getTree(0).get(), Result);
4151 } while (IterateInference);
4152
4153 // Verify that we inferred enough types that we can do something with the
4154 // pattern and result. If these fire the user has to add type casts.
4155 if (!InferredAllPatternTypes)
4156 Pattern.error("Could not infer all types in pattern!");
4157 if (!InferredAllResultTypes) {
4158 Pattern.dump();
4159 Result.error("Could not infer all types in pattern result!");
4160 }
4161
4162 // Promote xform function to be an explicit node wherever set.
4163 TreePatternNodePtr DstShared = PromoteXForms(Result.getOnlyTree());
4164
4165 TreePattern Temp(Result.getRecord(), DstShared, false, *this);
4166 Temp.InferAllTypes();
4167
4168 ListInit *Preds = TheDef->getValueAsListInit("Predicates");
4169 int Complexity = TheDef->getValueAsInt("AddedComplexity");
4170
4171 if (PatternRewriter)
4172 PatternRewriter(&Pattern);
4173
4174 // A pattern may end up with an "impossible" type, i.e. a situation
4175 // where all types have been eliminated for some node in this pattern.
4176 // This could occur for intrinsics that only make sense for a specific
4177 // value type, and use a specific register class. If, for some mode,
4178 // that register class does not accept that type, the type inference
4179 // will lead to a contradiction, which is not an error however, but
4180 // a sign that this pattern will simply never match.
4181 if (Temp.getOnlyTree()->hasPossibleType())
4182 for (auto T : Pattern.getTrees())
4183 if (T->hasPossibleType())
4184 AddPatternToMatch(&Pattern,
4185 PatternToMatch(TheDef, makePredList(Preds),
4186 T, Temp.getOnlyTree(),
4187 InstImpResults, Complexity,
4188 TheDef->getID()));
4189}
4190
4191void CodeGenDAGPatterns::ParsePatterns() {
4192 std::vector<Record*> Patterns = Records.getAllDerivedDefinitions("Pattern");
4193
4194 for (Record *CurPattern : Patterns) {
4195 DagInit *Tree = CurPattern->getValueAsDag("PatternToMatch");
4196
4197 // If the pattern references the null_frag, there's nothing to do.
4198 if (hasNullFragReference(Tree))
4199 continue;
4200
4201 TreePattern Pattern(CurPattern, Tree, true, *this);
4202
4203 ListInit *LI = CurPattern->getValueAsListInit("ResultInstrs");
4204 if (LI->empty()) continue; // no pattern.
4205
4206 // Parse the instruction.
4207 TreePattern Result(CurPattern, LI, false, *this);
4208
4209 if (Result.getNumTrees() != 1)
4210 Result.error("Cannot handle instructions producing instructions "
4211 "with temporaries yet!");
4212
4213 // Validate that the input pattern is correct.
4214 std::map<std::string, TreePatternNodePtr> InstInputs;
4215 MapVector<std::string, TreePatternNodePtr, std::map<std::string, unsigned>>
4216 InstResults;
4217 std::vector<Record*> InstImpResults;
4218 for (unsigned j = 0, ee = Pattern.getNumTrees(); j != ee; ++j)
4219 FindPatternInputsAndOutputs(Pattern, Pattern.getTree(j), InstInputs,
4220 InstResults, InstImpResults);
4221
4222 ParseOnePattern(CurPattern, Pattern, Result, InstImpResults);
4223 }
4224}
4225
4226static void collectModes(std::set<unsigned> &Modes, const TreePatternNode *N) {
4227 for (const TypeSetByHwMode &VTS : N->getExtTypes())
4228 for (const auto &I : VTS)
4229 Modes.insert(I.first);
4230
4231 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
4232 collectModes(Modes, N->getChild(i));
4233}
4234
4235void CodeGenDAGPatterns::ExpandHwModeBasedTypes() {
4236 const CodeGenHwModes &CGH = getTargetInfo().getHwModes();
4237 std::map<unsigned,std::vector<Predicate>> ModeChecks;
4238 std::vector<PatternToMatch> Copy = PatternsToMatch;
4239 PatternsToMatch.clear();
4240
4241 auto AppendPattern = [this, &ModeChecks](PatternToMatch &P, unsigned Mode) {
4242 TreePatternNodePtr NewSrc = P.SrcPattern->clone();
4243 TreePatternNodePtr NewDst = P.DstPattern->clone();
4244 if (!NewSrc->setDefaultMode(Mode) || !NewDst->setDefaultMode(Mode)) {
4245 return;
4246 }
4247
4248 std::vector<Predicate> Preds = P.Predicates;
4249 const std::vector<Predicate> &MC = ModeChecks[Mode];
4250 Preds.insert(Preds.end(), MC.begin(), MC.end());
4251 PatternsToMatch.emplace_back(P.getSrcRecord(), Preds, std::move(NewSrc),
4252 std::move(NewDst), P.getDstRegs(),
4253 P.getAddedComplexity(), Record::getNewUID(),
4254 Mode);
4255 };
4256
4257 for (PatternToMatch &P : Copy) {
4258 TreePatternNodePtr SrcP = nullptr, DstP = nullptr;
4259 if (P.SrcPattern->hasProperTypeByHwMode())
4260 SrcP = P.SrcPattern;
4261 if (P.DstPattern->hasProperTypeByHwMode())
4262 DstP = P.DstPattern;
4263 if (!SrcP && !DstP) {
4264 PatternsToMatch.push_back(P);
4265 continue;
4266 }
4267
4268 std::set<unsigned> Modes;
4269 if (SrcP)
4270 collectModes(Modes, SrcP.get());
4271 if (DstP)
4272 collectModes(Modes, DstP.get());
4273
4274 // The predicate for the default mode needs to be constructed for each
4275 // pattern separately.
4276 // Since not all modes must be present in each pattern, if a mode m is
4277 // absent, then there is no point in constructing a check for m. If such
4278 // a check was created, it would be equivalent to checking the default
4279 // mode, except not all modes' predicates would be a part of the checking
4280 // code. The subsequently generated check for the default mode would then
4281 // have the exact same patterns, but a different predicate code. To avoid
4282 // duplicated patterns with different predicate checks, construct the
4283 // default check as a negation of all predicates that are actually present
4284 // in the source/destination patterns.
4285 std::vector<Predicate> DefaultPred;
4286
4287 for (unsigned M : Modes) {
4288 if (M == DefaultMode)
4289 continue;
4290 if (ModeChecks.find(M) != ModeChecks.end())
4291 continue;
4292
4293 // Fill the map entry for this mode.
4294 const HwMode &HM = CGH.getMode(M);
4295 ModeChecks[M].emplace_back(Predicate(HM.Features, true));
4296
4297 // Add negations of the HM's predicates to the default predicate.
4298 DefaultPred.emplace_back(Predicate(HM.Features, false));
4299 }
4300
4301 for (unsigned M : Modes) {
4302 if (M == DefaultMode)
4303 continue;
4304 AppendPattern(P, M);
4305 }
4306
4307 bool HasDefault = Modes.count(DefaultMode);
4308 if (HasDefault)
4309 AppendPattern(P, DefaultMode);
4310 }
4311}
4312
4313/// Dependent variable map for CodeGenDAGPattern variant generation
4314typedef StringMap<int> DepVarMap;
4315
4316static void FindDepVarsOf(TreePatternNode *N, DepVarMap &DepMap) {
4317 if (N->isLeaf()) {
4318 if (N->hasName() && isa<DefInit>(N->getLeafValue()))
4319 DepMap[N->getName()]++;
4320 } else {
4321 for (size_t i = 0, e = N->getNumChildren(); i != e; ++i)
4322 FindDepVarsOf(N->getChild(i), DepMap);
4323 }
4324}
4325
4326/// Find dependent variables within child patterns
4327static void FindDepVars(TreePatternNode *N, MultipleUseVarSet &DepVars) {
4328 DepVarMap depcounts;
4329 FindDepVarsOf(N, depcounts);
4330 for (const auto &Pair : depcounts) {
4331 if (Pair.getValue() > 1)
4332 DepVars.insert(Pair.getKey());
4333 }
4334}
4335
4336#ifndef NDEBUG
4337/// Dump the dependent variable set:
4338static void DumpDepVars(MultipleUseVarSet &DepVars) {
4339 if (DepVars.empty()) {
4340 LLVM_DEBUG(errs() << "<empty set>")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << "<empty set>"; } } while
(false)
;
4341 } else {
4342 LLVM_DEBUG(errs() << "[ ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << "[ "; } } while (false)
;
4343 for (const auto &DepVar : DepVars) {
4344 LLVM_DEBUG(errs() << DepVar.getKey() << " ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << DepVar.getKey() << " "
; } } while (false)
;
4345 }
4346 LLVM_DEBUG(errs() << "]")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << "]"; } } while (false)
;
4347 }
4348}
4349#endif
4350
4351
4352/// CombineChildVariants - Given a bunch of permutations of each child of the
4353/// 'operator' node, put them together in all possible ways.
4354static void CombineChildVariants(
4355 TreePatternNodePtr Orig,
4356 const std::vector<std::vector<TreePatternNodePtr>> &ChildVariants,
4357 std::vector<TreePatternNodePtr> &OutVariants, CodeGenDAGPatterns &CDP,
4358 const MultipleUseVarSet &DepVars) {
4359 // Make sure that each operand has at least one variant to choose from.
4360 for (const auto &Variants : ChildVariants)
4361 if (Variants.empty())
4362 return;
4363
4364 // The end result is an all-pairs construction of the resultant pattern.
4365 std::vector<unsigned> Idxs;
4366 Idxs.resize(ChildVariants.size());
4367 bool NotDone;
4368 do {
4369#ifndef NDEBUG
4370 LLVM_DEBUG(if (!Idxs.empty()) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { if (!Idxs.empty()) { errs() << Orig
->getOperator()->getName() << ": Idxs = [ "; for (
unsigned Idx : Idxs) { errs() << Idx << " "; } errs
() << "]\n"; }; } } while (false)
4371 errs() << Orig->getOperator()->getName() << ": Idxs = [ ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { if (!Idxs.empty()) { errs() << Orig
->getOperator()->getName() << ": Idxs = [ "; for (
unsigned Idx : Idxs) { errs() << Idx << " "; } errs
() << "]\n"; }; } } while (false)
4372 for (unsigned Idx : Idxs) {do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { if (!Idxs.empty()) { errs() << Orig
->getOperator()->getName() << ": Idxs = [ "; for (
unsigned Idx : Idxs) { errs() << Idx << " "; } errs
() << "]\n"; }; } } while (false)
4373 errs() << Idx << " ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { if (!Idxs.empty()) { errs() << Orig
->getOperator()->getName() << ": Idxs = [ "; for (
unsigned Idx : Idxs) { errs() << Idx << " "; } errs
() << "]\n"; }; } } while (false)
4374 }do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { if (!Idxs.empty()) { errs() << Orig
->getOperator()->getName() << ": Idxs = [ "; for (
unsigned Idx : Idxs) { errs() << Idx << " "; } errs
() << "]\n"; }; } } while (false)
4375 errs() << "]\n";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { if (!Idxs.empty()) { errs() << Orig
->getOperator()->getName() << ": Idxs = [ "; for (
unsigned Idx : Idxs) { errs() << Idx << " "; } errs
() << "]\n"; }; } } while (false)
4376 })do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { if (!Idxs.empty()) { errs() << Orig
->getOperator()->getName() << ": Idxs = [ "; for (
unsigned Idx : Idxs) { errs() << Idx << " "; } errs
() << "]\n"; }; } } while (false)
;
4377#endif
4378 // Create the variant and add it to the output list.
4379 std::vector<TreePatternNodePtr> NewChildren;
4380 for (unsigned i = 0, e = ChildVariants.size(); i != e; ++i)
4381 NewChildren.push_back(ChildVariants[i][Idxs[i]]);
4382 TreePatternNodePtr R = std::make_shared<TreePatternNode>(
4383 Orig->getOperator(), std::move(NewChildren), Orig->getNumTypes());
4384
4385 // Copy over properties.
4386 R->setName(Orig->getName());
4387 R->setNamesAsPredicateArg(Orig->getNamesAsPredicateArg());
4388 R->setPredicateCalls(Orig->getPredicateCalls());
4389 R->setTransformFn(Orig->getTransformFn());
4390 for (unsigned i = 0, e = Orig->getNumTypes(); i != e; ++i)
4391 R->setType(i, Orig->getExtType(i));
4392
4393 // If this pattern cannot match, do not include it as a variant.
4394 std::string ErrString;
4395 // Scan to see if this pattern has already been emitted. We can get
4396 // duplication due to things like commuting:
4397 // (and GPRC:$a, GPRC:$b) -> (and GPRC:$b, GPRC:$a)
4398 // which are the same pattern. Ignore the dups.
4399 if (R->canPatternMatch(ErrString, CDP) &&
4400 none_of(OutVariants, [&](TreePatternNodePtr Variant) {
4401 return R->isIsomorphicTo(Variant.get(), DepVars);
4402 }))
4403 OutVariants.push_back(R);
4404
4405 // Increment indices to the next permutation by incrementing the
4406 // indices from last index backward, e.g., generate the sequence
4407 // [0, 0], [0, 1], [1, 0], [1, 1].
4408 int IdxsIdx;
4409 for (IdxsIdx = Idxs.size() - 1; IdxsIdx >= 0; --IdxsIdx) {
4410 if (++Idxs[IdxsIdx] == ChildVariants[IdxsIdx].size())
4411 Idxs[IdxsIdx] = 0;
4412 else
4413 break;
4414 }
4415 NotDone = (IdxsIdx >= 0);
4416 } while (NotDone);
4417}
4418
4419/// CombineChildVariants - A helper function for binary operators.
4420///
4421static void CombineChildVariants(TreePatternNodePtr Orig,
4422 const std::vector<TreePatternNodePtr> &LHS,
4423 const std::vector<TreePatternNodePtr> &RHS,
4424 std::vector<TreePatternNodePtr> &OutVariants,
4425 CodeGenDAGPatterns &CDP,
4426 const MultipleUseVarSet &DepVars) {
4427 std::vector<std::vector<TreePatternNodePtr>> ChildVariants;
4428 ChildVariants.push_back(LHS);
4429 ChildVariants.push_back(RHS);
4430 CombineChildVariants(Orig, ChildVariants, OutVariants, CDP, DepVars);
4431}
4432
4433static void
4434GatherChildrenOfAssociativeOpcode(TreePatternNodePtr N,
4435 std::vector<TreePatternNodePtr> &Children) {
4436 assert(N->getNumChildren()==2 &&"Associative but doesn't have 2 children!")((N->getNumChildren()==2 &&"Associative but doesn't have 2 children!"
) ? static_cast<void> (0) : __assert_fail ("N->getNumChildren()==2 &&\"Associative but doesn't have 2 children!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 4436, __PRETTY_FUNCTION__))
;
4437 Record *Operator = N->getOperator();
4438
4439 // Only permit raw nodes.
4440 if (!N->getName().empty() || !N->getPredicateCalls().empty() ||
4441 N->getTransformFn()) {
4442 Children.push_back(N);
4443 return;
4444 }
4445
4446 if (N->getChild(0)->isLeaf() || N->getChild(0)->getOperator() != Operator)
4447 Children.push_back(N->getChildShared(0));
4448 else
4449 GatherChildrenOfAssociativeOpcode(N->getChildShared(0), Children);
4450
4451 if (N->getChild(1)->isLeaf() || N->getChild(1)->getOperator() != Operator)
4452 Children.push_back(N->getChildShared(1));
4453 else
4454 GatherChildrenOfAssociativeOpcode(N->getChildShared(1), Children);
4455}
4456
4457/// GenerateVariantsOf - Given a pattern N, generate all permutations we can of
4458/// the (potentially recursive) pattern by using algebraic laws.
4459///
4460static void GenerateVariantsOf(TreePatternNodePtr N,
4461 std::vector<TreePatternNodePtr> &OutVariants,
4462 CodeGenDAGPatterns &CDP,
4463 const MultipleUseVarSet &DepVars) {
4464 // We cannot permute leaves or ComplexPattern uses.
4465 if (N->isLeaf() || N->getOperator()->isSubClassOf("ComplexPattern")) {
4466 OutVariants.push_back(N);
4467 return;
4468 }
4469
4470 // Look up interesting info about the node.
4471 const SDNodeInfo &NodeInfo = CDP.getSDNodeInfo(N->getOperator());
4472
4473 // If this node is associative, re-associate.
4474 if (NodeInfo.hasProperty(SDNPAssociative)) {
4475 // Re-associate by pulling together all of the linked operators
4476 std::vector<TreePatternNodePtr> MaximalChildren;
4477 GatherChildrenOfAssociativeOpcode(N, MaximalChildren);
4478
4479 // Only handle child sizes of 3. Otherwise we'll end up trying too many
4480 // permutations.
4481 if (MaximalChildren.size() == 3) {
4482 // Find the variants of all of our maximal children.
4483 std::vector<TreePatternNodePtr> AVariants, BVariants, CVariants;
4484 GenerateVariantsOf(MaximalChildren[0], AVariants, CDP, DepVars);
4485 GenerateVariantsOf(MaximalChildren[1], BVariants, CDP, DepVars);
4486 GenerateVariantsOf(MaximalChildren[2], CVariants, CDP, DepVars);
4487
4488 // There are only two ways we can permute the tree:
4489 // (A op B) op C and A op (B op C)
4490 // Within these forms, we can also permute A/B/C.
4491
4492 // Generate legal pair permutations of A/B/C.
4493 std::vector<TreePatternNodePtr> ABVariants;
4494 std::vector<TreePatternNodePtr> BAVariants;
4495 std::vector<TreePatternNodePtr> ACVariants;
4496 std::vector<TreePatternNodePtr> CAVariants;
4497 std::vector<TreePatternNodePtr> BCVariants;
4498 std::vector<TreePatternNodePtr> CBVariants;
4499 CombineChildVariants(N, AVariants, BVariants, ABVariants, CDP, DepVars);
4500 CombineChildVariants(N, BVariants, AVariants, BAVariants, CDP, DepVars);
4501 CombineChildVariants(N, AVariants, CVariants, ACVariants, CDP, DepVars);
4502 CombineChildVariants(N, CVariants, AVariants, CAVariants, CDP, DepVars);
4503 CombineChildVariants(N, BVariants, CVariants, BCVariants, CDP, DepVars);
4504 CombineChildVariants(N, CVariants, BVariants, CBVariants, CDP, DepVars);
4505
4506 // Combine those into the result: (x op x) op x
4507 CombineChildVariants(N, ABVariants, CVariants, OutVariants, CDP, DepVars);
4508 CombineChildVariants(N, BAVariants, CVariants, OutVariants, CDP, DepVars);
4509 CombineChildVariants(N, ACVariants, BVariants, OutVariants, CDP, DepVars);
4510 CombineChildVariants(N, CAVariants, BVariants, OutVariants, CDP, DepVars);
4511 CombineChildVariants(N, BCVariants, AVariants, OutVariants, CDP, DepVars);
4512 CombineChildVariants(N, CBVariants, AVariants, OutVariants, CDP, DepVars);
4513
4514 // Combine those into the result: x op (x op x)
4515 CombineChildVariants(N, CVariants, ABVariants, OutVariants, CDP, DepVars);
4516 CombineChildVariants(N, CVariants, BAVariants, OutVariants, CDP, DepVars);
4517 CombineChildVariants(N, BVariants, ACVariants, OutVariants, CDP, DepVars);
4518 CombineChildVariants(N, BVariants, CAVariants, OutVariants, CDP, DepVars);
4519 CombineChildVariants(N, AVariants, BCVariants, OutVariants, CDP, DepVars);
4520 CombineChildVariants(N, AVariants, CBVariants, OutVariants, CDP, DepVars);
4521 return;
4522 }
4523 }
4524
4525 // Compute permutations of all children.
4526 std::vector<std::vector<TreePatternNodePtr>> ChildVariants;
4527 ChildVariants.resize(N->getNumChildren());
4528 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i)
4529 GenerateVariantsOf(N->getChildShared(i), ChildVariants[i], CDP, DepVars);
4530
4531 // Build all permutations based on how the children were formed.
4532 CombineChildVariants(N, ChildVariants, OutVariants, CDP, DepVars);
4533
4534 // If this node is commutative, consider the commuted order.
4535 bool isCommIntrinsic = N->isCommutativeIntrinsic(CDP);
4536 if (NodeInfo.hasProperty(SDNPCommutative) || isCommIntrinsic) {
4537 assert((N->getNumChildren()>=2 || isCommIntrinsic) &&(((N->getNumChildren()>=2 || isCommIntrinsic) &&
"Commutative but doesn't have 2 children!") ? static_cast<
void> (0) : __assert_fail ("(N->getNumChildren()>=2 || isCommIntrinsic) && \"Commutative but doesn't have 2 children!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 4538, __PRETTY_FUNCTION__))
4538 "Commutative but doesn't have 2 children!")(((N->getNumChildren()>=2 || isCommIntrinsic) &&
"Commutative but doesn't have 2 children!") ? static_cast<
void> (0) : __assert_fail ("(N->getNumChildren()>=2 || isCommIntrinsic) && \"Commutative but doesn't have 2 children!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 4538, __PRETTY_FUNCTION__))
;
4539 // Don't count children which are actually register references.
4540 unsigned NC = 0;
4541 for (unsigned i = 0, e = N->getNumChildren(); i != e; ++i) {
4542 TreePatternNode *Child = N->getChild(i);
4543 if (Child->isLeaf())
4544 if (DefInit *DI = dyn_cast<DefInit>(Child->getLeafValue())) {
4545 Record *RR = DI->getDef();
4546 if (RR->isSubClassOf("Register"))
4547 continue;
4548 }
4549 NC++;
4550 }
4551 // Consider the commuted order.
4552 if (isCommIntrinsic) {
4553 // Commutative intrinsic. First operand is the intrinsic id, 2nd and 3rd
4554 // operands are the commutative operands, and there might be more operands
4555 // after those.
4556 assert(NC >= 3 &&((NC >= 3 && "Commutative intrinsic should have at least 3 children!"
) ? static_cast<void> (0) : __assert_fail ("NC >= 3 && \"Commutative intrinsic should have at least 3 children!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 4557, __PRETTY_FUNCTION__))
4557 "Commutative intrinsic should have at least 3 children!")((NC >= 3 && "Commutative intrinsic should have at least 3 children!"
) ? static_cast<void> (0) : __assert_fail ("NC >= 3 && \"Commutative intrinsic should have at least 3 children!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 4557, __PRETTY_FUNCTION__))
;
4558 std::vector<std::vector<TreePatternNodePtr>> Variants;
4559 Variants.push_back(std::move(ChildVariants[0])); // Intrinsic id.
4560 Variants.push_back(std::move(ChildVariants[2]));
4561 Variants.push_back(std::move(ChildVariants[1]));
4562 for (unsigned i = 3; i != NC; ++i)
4563 Variants.push_back(std::move(ChildVariants[i]));
4564 CombineChildVariants(N, Variants, OutVariants, CDP, DepVars);
4565 } else if (NC == N->getNumChildren()) {
4566 std::vector<std::vector<TreePatternNodePtr>> Variants;
4567 Variants.push_back(std::move(ChildVariants[1]));
4568 Variants.push_back(std::move(ChildVariants[0]));
4569 for (unsigned i = 2; i != NC; ++i)
4570 Variants.push_back(std::move(ChildVariants[i]));
4571 CombineChildVariants(N, Variants, OutVariants, CDP, DepVars);
4572 }
4573 }
4574}
4575
4576
4577// GenerateVariants - Generate variants. For example, commutative patterns can
4578// match multiple ways. Add them to PatternsToMatch as well.
4579void CodeGenDAGPatterns::GenerateVariants() {
4580 LLVM_DEBUG(errs() << "Generating instruction variants.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << "Generating instruction variants.\n"
; } } while (false)
;
4581
4582 // Loop over all of the patterns we've collected, checking to see if we can
4583 // generate variants of the instruction, through the exploitation of
4584 // identities. This permits the target to provide aggressive matching without
4585 // the .td file having to contain tons of variants of instructions.
4586 //
4587 // Note that this loop adds new patterns to the PatternsToMatch list, but we
4588 // intentionally do not reconsider these. Any variants of added patterns have
4589 // already been added.
4590 //
4591 const unsigned NumOriginalPatterns = PatternsToMatch.size();
4592 BitVector MatchedPatterns(NumOriginalPatterns);
4593 std::vector<BitVector> MatchedPredicates(NumOriginalPatterns,
4594 BitVector(NumOriginalPatterns));
4595
4596 typedef std::pair<MultipleUseVarSet, std::vector<TreePatternNodePtr>>
4597 DepsAndVariants;
4598 std::map<unsigned, DepsAndVariants> PatternsWithVariants;
4599
4600 // Collect patterns with more than one variant.
4601 for (unsigned i = 0; i != NumOriginalPatterns; ++i) {
4602 MultipleUseVarSet DepVars;
4603 std::vector<TreePatternNodePtr> Variants;
4604 FindDepVars(PatternsToMatch[i].getSrcPattern(), DepVars);
4605 LLVM_DEBUG(errs() << "Dependent/multiply used variables: ")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << "Dependent/multiply used variables: "
; } } while (false)
;
4606 LLVM_DEBUG(DumpDepVars(DepVars))do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { DumpDepVars(DepVars); } } while (false)
;
4607 LLVM_DEBUG(errs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << "\n"; } } while (false)
;
4608 GenerateVariantsOf(PatternsToMatch[i].getSrcPatternShared(), Variants,
4609 *this, DepVars);
4610
4611 assert(!Variants.empty() && "Must create at least original variant!")((!Variants.empty() && "Must create at least original variant!"
) ? static_cast<void> (0) : __assert_fail ("!Variants.empty() && \"Must create at least original variant!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.cpp"
, 4611, __PRETTY_FUNCTION__))
;
4612 if (Variants.size() == 1) // No additional variants for this pattern.
4613 continue;
4614
4615 LLVM_DEBUG(errs() << "FOUND VARIANTS OF: ";do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << "FOUND VARIANTS OF: "; PatternsToMatch
[i].getSrcPattern()->dump(); errs() << "\n"; } } while
(false)
4616 PatternsToMatch[i].getSrcPattern()->dump(); errs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << "FOUND VARIANTS OF: "; PatternsToMatch
[i].getSrcPattern()->dump(); errs() << "\n"; } } while
(false)
;
4617
4618 PatternsWithVariants[i] = std::make_pair(DepVars, Variants);
4619
4620 // Cache matching predicates.
4621 if (MatchedPatterns[i])
4622 continue;
4623
4624 const std::vector<Predicate> &Predicates =
4625 PatternsToMatch[i].getPredicates();
4626
4627 BitVector &Matches = MatchedPredicates[i];
4628 MatchedPatterns.set(i);
4629 Matches.set(i);
4630
4631 // Don't test patterns that have already been cached - it won't match.
4632 for (unsigned p = 0; p != NumOriginalPatterns; ++p)
4633 if (!MatchedPatterns[p])
4634 Matches[p] = (Predicates == PatternsToMatch[p].getPredicates());
4635
4636 // Copy this to all the matching patterns.
4637 for (int p = Matches.find_first(); p != -1; p = Matches.find_next(p))
4638 if (p != (int)i) {
4639 MatchedPatterns.set(p);
4640 MatchedPredicates[p] = Matches;
4641 }
4642 }
4643
4644 for (auto it : PatternsWithVariants) {
4645 unsigned i = it.first;
4646 const MultipleUseVarSet &DepVars = it.second.first;
4647 const std::vector<TreePatternNodePtr> &Variants = it.second.second;
4648
4649 for (unsigned v = 0, e = Variants.size(); v != e; ++v) {
4650 TreePatternNodePtr Variant = Variants[v];
4651 BitVector &Matches = MatchedPredicates[i];
4652
4653 LLVM_DEBUG(errs() << " VAR#" << v << ": "; Variant->dump();do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << " VAR#" << v <<
": "; Variant->dump(); errs() << "\n"; } } while (false
)
4654 errs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << " VAR#" << v <<
": "; Variant->dump(); errs() << "\n"; } } while (false
)
;
4655
4656 // Scan to see if an instruction or explicit pattern already matches this.
4657 bool AlreadyExists = false;
4658 for (unsigned p = 0, e = PatternsToMatch.size(); p != e; ++p) {
4659 // Skip if the top level predicates do not match.
4660 if (!Matches[p])
4661 continue;
4662 // Check to see if this variant already exists.
4663 if (Variant->isIsomorphicTo(PatternsToMatch[p].getSrcPattern(),
4664 DepVars)) {
4665 LLVM_DEBUG(errs() << " *** ALREADY EXISTS, ignoring variant.\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << " *** ALREADY EXISTS, ignoring variant.\n"
; } } while (false)
;
4666 AlreadyExists = true;
4667 break;
4668 }
4669 }
4670 // If we already have it, ignore the variant.
4671 if (AlreadyExists) continue;
4672
4673 // Otherwise, add it to the list of patterns we have.
4674 PatternsToMatch.push_back(PatternToMatch(
4675 PatternsToMatch[i].getSrcRecord(), PatternsToMatch[i].getPredicates(),
4676 Variant, PatternsToMatch[i].getDstPatternShared(),
4677 PatternsToMatch[i].getDstRegs(),
4678 PatternsToMatch[i].getAddedComplexity(), Record::getNewUID()));
4679 MatchedPredicates.push_back(Matches);
4680
4681 // Add a new match the same as this pattern.
4682 for (auto &P : MatchedPredicates)
4683 P.push_back(P[i]);
4684 }
4685
4686 LLVM_DEBUG(errs() << "\n")do { if (::llvm::DebugFlag && ::llvm::isCurrentDebugType
("dag-patterns")) { errs() << "\n"; } } while (false)
;
4687 }
4688}

/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h

1//===- CodeGenDAGPatterns.h - Read DAG patterns from .td file ---*- C++ -*-===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8//
9// This file declares the CodeGenDAGPatterns class, which is used to read and
10// represent the patterns present in a .td file for instructions.
11//
12//===----------------------------------------------------------------------===//
13
14#ifndef LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H
15#define LLVM_UTILS_TABLEGEN_CODEGENDAGPATTERNS_H
16
17#include "CodeGenHwModes.h"
18#include "CodeGenIntrinsics.h"
19#include "CodeGenTarget.h"
20#include "SDNodeProperties.h"
21#include "llvm/ADT/MapVector.h"
22#include "llvm/ADT/SmallVector.h"
23#include "llvm/ADT/StringMap.h"
24#include "llvm/ADT/StringSet.h"
25#include "llvm/Support/ErrorHandling.h"
26#include "llvm/Support/MathExtras.h"
27#include <algorithm>
28#include <array>
29#include <functional>
30#include <map>
31#include <numeric>
32#include <set>
33#include <vector>
34
35namespace llvm {
36
37class Record;
38class Init;
39class ListInit;
40class DagInit;
41class SDNodeInfo;
42class TreePattern;
43class TreePatternNode;
44class CodeGenDAGPatterns;
45class ComplexPattern;
46
47/// Shared pointer for TreePatternNode.
48using TreePatternNodePtr = std::shared_ptr<TreePatternNode>;
49
50/// This represents a set of MVTs. Since the underlying type for the MVT
51/// is uint8_t, there are at most 256 values. To reduce the number of memory
52/// allocations and deallocations, represent the set as a sequence of bits.
53/// To reduce the allocations even further, make MachineValueTypeSet own
54/// the storage and use std::array as the bit container.
55struct MachineValueTypeSet {
56 static_assert(std::is_same<std::underlying_type<MVT::SimpleValueType>::type,
57 uint8_t>::value,
58 "Change uint8_t here to the SimpleValueType's type");
59 static unsigned constexpr Capacity = std::numeric_limits<uint8_t>::max()+1;
60 using WordType = uint64_t;
61 static unsigned constexpr WordWidth = CHAR_BIT8*sizeof(WordType);
62 static unsigned constexpr NumWords = Capacity/WordWidth;
63 static_assert(NumWords*WordWidth == Capacity,
64 "Capacity should be a multiple of WordWidth");
65
66 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
67 MachineValueTypeSet() {
68 clear();
69 }
70
71 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
72 unsigned size() const {
73 unsigned Count = 0;
74 for (WordType W : Words)
75 Count += countPopulation(W);
76 return Count;
77 }
78 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
79 void clear() {
80 std::memset(Words.data(), 0, NumWords*sizeof(WordType));
81 }
82 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
83 bool empty() const {
84 for (WordType W : Words)
85 if (W != 0)
86 return false;
87 return true;
88 }
89 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
90 unsigned count(MVT T) const {
91 return (Words[T.SimpleTy / WordWidth] >> (T.SimpleTy % WordWidth)) & 1;
92 }
93 std::pair<MachineValueTypeSet&,bool> insert(MVT T) {
94 bool V = count(T.SimpleTy);
95 Words[T.SimpleTy / WordWidth] |= WordType(1) << (T.SimpleTy % WordWidth);
96 return {*this, V};
97 }
98 MachineValueTypeSet &insert(const MachineValueTypeSet &S) {
99 for (unsigned i = 0; i != NumWords; ++i)
100 Words[i] |= S.Words[i];
101 return *this;
102 }
103 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
104 void erase(MVT T) {
105 Words[T.SimpleTy / WordWidth] &= ~(WordType(1) << (T.SimpleTy % WordWidth));
106 }
107
108 struct const_iterator {
109 // Some implementations of the C++ library require these traits to be
110 // defined.
111 using iterator_category = std::forward_iterator_tag;
112 using value_type = MVT;
113 using difference_type = ptrdiff_t;
114 using pointer = const MVT*;
115 using reference = const MVT&;
116
117 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
118 MVT operator*() const {
119 assert(Pos != Capacity)((Pos != Capacity) ? static_cast<void> (0) : __assert_fail
("Pos != Capacity", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 119, __PRETTY_FUNCTION__))
;
120 return MVT::SimpleValueType(Pos);
121 }
122 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
123 const_iterator(const MachineValueTypeSet *S, bool End) : Set(S) {
124 Pos = End ? Capacity : find_from_pos(0);
125 }
126 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
127 const_iterator &operator++() {
128 assert(Pos != Capacity)((Pos != Capacity) ? static_cast<void> (0) : __assert_fail
("Pos != Capacity", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 128, __PRETTY_FUNCTION__))
;
129 Pos = find_from_pos(Pos+1);
130 return *this;
131 }
132
133 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
134 bool operator==(const const_iterator &It) const {
135 return Set == It.Set && Pos == It.Pos;
136 }
137 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
138 bool operator!=(const const_iterator &It) const {
139 return !operator==(It);
140 }
141
142 private:
143 unsigned find_from_pos(unsigned P) const {
144 unsigned SkipWords = P / WordWidth;
145 unsigned SkipBits = P % WordWidth;
146 unsigned Count = SkipWords * WordWidth;
147
148 // If P is in the middle of a word, process it manually here, because
149 // the trailing bits need to be masked off to use findFirstSet.
150 if (SkipBits != 0) {
151 WordType W = Set->Words[SkipWords];
152 W &= maskLeadingOnes<WordType>(WordWidth-SkipBits);
153 if (W != 0)
154 return Count + findFirstSet(W);
155 Count += WordWidth;
156 SkipWords++;
157 }
158
159 for (unsigned i = SkipWords; i != NumWords; ++i) {
160 WordType W = Set->Words[i];
161 if (W != 0)
162 return Count + findFirstSet(W);
163 Count += WordWidth;
164 }
165 return Capacity;
166 }
167
168 const MachineValueTypeSet *Set;
169 unsigned Pos;
170 };
171
172 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
173 const_iterator begin() const { return const_iterator(this, false); }
174 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
175 const_iterator end() const { return const_iterator(this, true); }
176
177 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
178 bool operator==(const MachineValueTypeSet &S) const {
179 return Words == S.Words;
180 }
181 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
182 bool operator!=(const MachineValueTypeSet &S) const {
183 return !operator==(S);
184 }
185
186private:
187 friend struct const_iterator;
188 std::array<WordType,NumWords> Words;
189};
190
191struct TypeSetByHwMode : public InfoByHwMode<MachineValueTypeSet> {
192 using SetType = MachineValueTypeSet;
193 std::vector<unsigned> AddrSpaces;
194
195 TypeSetByHwMode() = default;
196 TypeSetByHwMode(const TypeSetByHwMode &VTS) = default;
197 TypeSetByHwMode(MVT::SimpleValueType VT)
198 : TypeSetByHwMode(ValueTypeByHwMode(VT)) {}
199 TypeSetByHwMode(ValueTypeByHwMode VT)
200 : TypeSetByHwMode(ArrayRef<ValueTypeByHwMode>(&VT, 1)) {}
201 TypeSetByHwMode(ArrayRef<ValueTypeByHwMode> VTList);
202
203 SetType &getOrCreate(unsigned Mode) {
204 if (hasMode(Mode))
205 return get(Mode);
206 return Map.insert({Mode,SetType()}).first->second;
207 }
208
209 bool isValueTypeByHwMode(bool AllowEmpty) const;
210 ValueTypeByHwMode getValueTypeByHwMode() const;
211
212 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
213 bool isMachineValueType() const {
214 return isDefaultOnly() && Map.begin()->second.size() == 1;
215 }
216
217 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
218 MVT getMachineValueType() const {
219 assert(isMachineValueType())((isMachineValueType()) ? static_cast<void> (0) : __assert_fail
("isMachineValueType()", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 219, __PRETTY_FUNCTION__))
;
220 return *Map.begin()->second.begin();
221 }
222
223 bool isPossible() const;
224
225 LLVM_ATTRIBUTE_ALWAYS_INLINE__attribute__((always_inline))
226 bool isDefaultOnly() const {
227 return Map.size() == 1 && Map.begin()->first == DefaultMode;
228 }
229
230 bool isPointer() const {
231 return getValueTypeByHwMode().isPointer();
232 }
233
234 unsigned getPtrAddrSpace() const {
235 assert(isPointer())((isPointer()) ? static_cast<void> (0) : __assert_fail (
"isPointer()", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 235, __PRETTY_FUNCTION__))
;
236 return getValueTypeByHwMode().PtrAddrSpace;
237 }
238
239 bool insert(const ValueTypeByHwMode &VVT);
240 bool constrain(const TypeSetByHwMode &VTS);
241 template <typename Predicate> bool constrain(Predicate P);
242 template <typename Predicate>
243 bool assign_if(const TypeSetByHwMode &VTS, Predicate P);
244
245 void writeToStream(raw_ostream &OS) const;
246 static void writeToStream(const SetType &S, raw_ostream &OS);
247
248 bool operator==(const TypeSetByHwMode &VTS) const;
249 bool operator!=(const TypeSetByHwMode &VTS) const { return !(*this == VTS); }
250
251 void dump() const;
252 bool validate() const;
253
254private:
255 unsigned PtrAddrSpace = std::numeric_limits<unsigned>::max();
256 /// Intersect two sets. Return true if anything has changed.
257 bool intersect(SetType &Out, const SetType &In);
258};
259
260raw_ostream &operator<<(raw_ostream &OS, const TypeSetByHwMode &T);
261
262struct TypeInfer {
263 TypeInfer(TreePattern &T) : TP(T), ForceMode(0) {}
264
265 bool isConcrete(const TypeSetByHwMode &VTS, bool AllowEmpty) const {
266 return VTS.isValueTypeByHwMode(AllowEmpty);
267 }
268 ValueTypeByHwMode getConcrete(const TypeSetByHwMode &VTS,
269 bool AllowEmpty) const {
270 assert(VTS.isValueTypeByHwMode(AllowEmpty))((VTS.isValueTypeByHwMode(AllowEmpty)) ? static_cast<void>
(0) : __assert_fail ("VTS.isValueTypeByHwMode(AllowEmpty)", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 270, __PRETTY_FUNCTION__))
;
271 return VTS.getValueTypeByHwMode();
272 }
273
274 /// The protocol in the following functions (Merge*, force*, Enforce*,
275 /// expand*) is to return "true" if a change has been made, "false"
276 /// otherwise.
277
278 bool MergeInTypeInfo(TypeSetByHwMode &Out, const TypeSetByHwMode &In);
279 bool MergeInTypeInfo(TypeSetByHwMode &Out, MVT::SimpleValueType InVT) {
280 return MergeInTypeInfo(Out, TypeSetByHwMode(InVT));
281 }
282 bool MergeInTypeInfo(TypeSetByHwMode &Out, ValueTypeByHwMode InVT) {
283 return MergeInTypeInfo(Out, TypeSetByHwMode(InVT));
284 }
285
286 /// Reduce the set \p Out to have at most one element for each mode.
287 bool forceArbitrary(TypeSetByHwMode &Out);
288
289 /// The following four functions ensure that upon return the set \p Out
290 /// will only contain types of the specified kind: integer, floating-point,
291 /// scalar, or vector.
292 /// If \p Out is empty, all legal types of the specified kind will be added
293 /// to it. Otherwise, all types that are not of the specified kind will be
294 /// removed from \p Out.
295 bool EnforceInteger(TypeSetByHwMode &Out);
296 bool EnforceFloatingPoint(TypeSetByHwMode &Out);
297 bool EnforceScalar(TypeSetByHwMode &Out);
298 bool EnforceVector(TypeSetByHwMode &Out);
299
300 /// If \p Out is empty, fill it with all legal types. Otherwise, leave it
301 /// unchanged.
302 bool EnforceAny(TypeSetByHwMode &Out);
303 /// Make sure that for each type in \p Small, there exists a larger type
304 /// in \p Big.
305 bool EnforceSmallerThan(TypeSetByHwMode &Small, TypeSetByHwMode &Big);
306 /// 1. Ensure that for each type T in \p Vec, T is a vector type, and that
307 /// for each type U in \p Elem, U is a scalar type.
308 /// 2. Ensure that for each (scalar) type U in \p Elem, there exists a
309 /// (vector) type T in \p Vec, such that U is the element type of T.
310 bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec, TypeSetByHwMode &Elem);
311 bool EnforceVectorEltTypeIs(TypeSetByHwMode &Vec,
312 const ValueTypeByHwMode &VVT);
313 /// Ensure that for each type T in \p Sub, T is a vector type, and there
314 /// exists a type U in \p Vec such that U is a vector type with the same
315 /// element type as T and at least as many elements as T.
316 bool EnforceVectorSubVectorTypeIs(TypeSetByHwMode &Vec,
317 TypeSetByHwMode &Sub);
318 /// 1. Ensure that \p V has a scalar type iff \p W has a scalar type.
319 /// 2. Ensure that for each vector type T in \p V, there exists a vector
320 /// type U in \p W, such that T and U have the same number of elements.
321 /// 3. Ensure that for each vector type U in \p W, there exists a vector
322 /// type T in \p V, such that T and U have the same number of elements
323 /// (reverse of 2).
324 bool EnforceSameNumElts(TypeSetByHwMode &V, TypeSetByHwMode &W);
325 /// 1. Ensure that for each type T in \p A, there exists a type U in \p B,
326 /// such that T and U have equal size in bits.
327 /// 2. Ensure that for each type U in \p B, there exists a type T in \p A
328 /// such that T and U have equal size in bits (reverse of 1).
329 bool EnforceSameSize(TypeSetByHwMode &A, TypeSetByHwMode &B);
330
331 /// For each overloaded type (i.e. of form *Any), replace it with the
332 /// corresponding subset of legal, specific types.
333 void expandOverloads(TypeSetByHwMode &VTS);
334 void expandOverloads(TypeSetByHwMode::SetType &Out,
335 const TypeSetByHwMode::SetType &Legal);
336
337 struct ValidateOnExit {
338 ValidateOnExit(TypeSetByHwMode &T, TypeInfer &TI) : Infer(TI), VTS(T) {}
339 #ifndef NDEBUG
340 ~ValidateOnExit();
341 #else
342 ~ValidateOnExit() {} // Empty destructor with NDEBUG.
343 #endif
344 TypeInfer &Infer;
345 TypeSetByHwMode &VTS;
346 };
347
348 struct SuppressValidation {
349 SuppressValidation(TypeInfer &TI) : Infer(TI), SavedValidate(TI.Validate) {
350 Infer.Validate = false;
351 }
352 ~SuppressValidation() {
353 Infer.Validate = SavedValidate;
354 }
355 TypeInfer &Infer;
356 bool SavedValidate;
357 };
358
359 TreePattern &TP;
360 unsigned ForceMode; // Mode to use when set.
361 bool CodeGen = false; // Set during generation of matcher code.
362 bool Validate = true; // Indicate whether to validate types.
363
364private:
365 const TypeSetByHwMode &getLegalTypes();
366
367 /// Cached legal types (in default mode).
368 bool LegalTypesCached = false;
369 TypeSetByHwMode LegalCache;
370};
371
372/// Set type used to track multiply used variables in patterns
373typedef StringSet<> MultipleUseVarSet;
374
375/// SDTypeConstraint - This is a discriminated union of constraints,
376/// corresponding to the SDTypeConstraint tablegen class in Target.td.
377struct SDTypeConstraint {
378 SDTypeConstraint(Record *R, const CodeGenHwModes &CGH);
379
380 unsigned OperandNo; // The operand # this constraint applies to.
381 enum {
382 SDTCisVT, SDTCisPtrTy, SDTCisInt, SDTCisFP, SDTCisVec, SDTCisSameAs,
383 SDTCisVTSmallerThanOp, SDTCisOpSmallerThanOp, SDTCisEltOfVec,
384 SDTCisSubVecOfVec, SDTCVecEltisVT, SDTCisSameNumEltsAs, SDTCisSameSizeAs
385 } ConstraintType;
386
387 union { // The discriminated union.
388 struct {
389 unsigned OtherOperandNum;
390 } SDTCisSameAs_Info;
391 struct {
392 unsigned OtherOperandNum;
393 } SDTCisVTSmallerThanOp_Info;
394 struct {
395 unsigned BigOperandNum;
396 } SDTCisOpSmallerThanOp_Info;
397 struct {
398 unsigned OtherOperandNum;
399 } SDTCisEltOfVec_Info;
400 struct {
401 unsigned OtherOperandNum;
402 } SDTCisSubVecOfVec_Info;
403 struct {
404 unsigned OtherOperandNum;
405 } SDTCisSameNumEltsAs_Info;
406 struct {
407 unsigned OtherOperandNum;
408 } SDTCisSameSizeAs_Info;
409 } x;
410
411 // The VT for SDTCisVT and SDTCVecEltisVT.
412 // Must not be in the union because it has a non-trivial destructor.
413 ValueTypeByHwMode VVT;
414
415 /// ApplyTypeConstraint - Given a node in a pattern, apply this type
416 /// constraint to the nodes operands. This returns true if it makes a
417 /// change, false otherwise. If a type contradiction is found, an error
418 /// is flagged.
419 bool ApplyTypeConstraint(TreePatternNode *N, const SDNodeInfo &NodeInfo,
420 TreePattern &TP) const;
421};
422
423/// ScopedName - A name of a node associated with a "scope" that indicates
424/// the context (e.g. instance of Pattern or PatFrag) in which the name was
425/// used. This enables substitution of pattern fragments while keeping track
426/// of what name(s) were originally given to various nodes in the tree.
427class ScopedName {
428 unsigned Scope;
429 std::string Identifier;
430public:
431 ScopedName(unsigned Scope, StringRef Identifier)
432 : Scope(Scope), Identifier(Identifier) {
433 assert(Scope != 0 &&((Scope != 0 && "Scope == 0 is used to indicate predicates without arguments"
) ? static_cast<void> (0) : __assert_fail ("Scope != 0 && \"Scope == 0 is used to indicate predicates without arguments\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 434, __PRETTY_FUNCTION__))
434 "Scope == 0 is used to indicate predicates without arguments")((Scope != 0 && "Scope == 0 is used to indicate predicates without arguments"
) ? static_cast<void> (0) : __assert_fail ("Scope != 0 && \"Scope == 0 is used to indicate predicates without arguments\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 434, __PRETTY_FUNCTION__))
;
435 }
436
437 unsigned getScope() const { return Scope; }
438 const std::string &getIdentifier() const { return Identifier; }
439
440 std::string getFullName() const;
441
442 bool operator==(const ScopedName &o) const;
443 bool operator!=(const ScopedName &o) const;
444};
445
446/// SDNodeInfo - One of these records is created for each SDNode instance in
447/// the target .td file. This represents the various dag nodes we will be
448/// processing.
449class SDNodeInfo {
450 Record *Def;
451 StringRef EnumName;
452 StringRef SDClassName;
453 unsigned Properties;
454 unsigned NumResults;
455 int NumOperands;
456 std::vector<SDTypeConstraint> TypeConstraints;
457public:
458 // Parse the specified record.
459 SDNodeInfo(Record *R, const CodeGenHwModes &CGH);
460
461 unsigned getNumResults() const { return NumResults; }
462
463 /// getNumOperands - This is the number of operands required or -1 if
464 /// variadic.
465 int getNumOperands() const { return NumOperands; }
466 Record *getRecord() const { return Def; }
467 StringRef getEnumName() const { return EnumName; }
468 StringRef getSDClassName() const { return SDClassName; }
469
470 const std::vector<SDTypeConstraint> &getTypeConstraints() const {
471 return TypeConstraints;
472 }
473
474 /// getKnownType - If the type constraints on this node imply a fixed type
475 /// (e.g. all stores return void, etc), then return it as an
476 /// MVT::SimpleValueType. Otherwise, return MVT::Other.
477 MVT::SimpleValueType getKnownType(unsigned ResNo) const;
478
479 /// hasProperty - Return true if this node has the specified property.
480 ///
481 bool hasProperty(enum SDNP Prop) const { return Properties & (1 << Prop); }
482
483 /// ApplyTypeConstraints - Given a node in a pattern, apply the type
484 /// constraints for this node to the operands of the node. This returns
485 /// true if it makes a change, false otherwise. If a type contradiction is
486 /// found, an error is flagged.
487 bool ApplyTypeConstraints(TreePatternNode *N, TreePattern &TP) const;
488};
489
490/// TreePredicateFn - This is an abstraction that represents the predicates on
491/// a PatFrag node. This is a simple one-word wrapper around a pointer to
492/// provide nice accessors.
493class TreePredicateFn {
494 /// PatFragRec - This is the TreePattern for the PatFrag that we
495 /// originally came from.
496 TreePattern *PatFragRec;
497public:
498 /// TreePredicateFn constructor. Here 'N' is a subclass of PatFrag.
499 TreePredicateFn(TreePattern *N);
500
501
502 TreePattern *getOrigPatFragRecord() const { return PatFragRec; }
503
504 /// isAlwaysTrue - Return true if this is a noop predicate.
505 bool isAlwaysTrue() const;
506
507 bool isImmediatePattern() const { return hasImmCode(); }
508
509 /// getImmediatePredicateCode - Return the code that evaluates this pattern if
510 /// this is an immediate predicate. It is an error to call this on a
511 /// non-immediate pattern.
512 std::string getImmediatePredicateCode() const {
513 std::string Result = getImmCode();
514 assert(!Result.empty() && "Isn't an immediate pattern!")((!Result.empty() && "Isn't an immediate pattern!") ?
static_cast<void> (0) : __assert_fail ("!Result.empty() && \"Isn't an immediate pattern!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 514, __PRETTY_FUNCTION__))
;
515 return Result;
516 }
517
518 bool operator==(const TreePredicateFn &RHS) const {
519 return PatFragRec == RHS.PatFragRec;
520 }
521
522 bool operator!=(const TreePredicateFn &RHS) const { return !(*this == RHS); }
523
524 /// Return the name to use in the generated code to reference this, this is
525 /// "Predicate_foo" if from a pattern fragment "foo".
526 std::string getFnName() const;
527
528 /// getCodeToRunOnSDNode - Return the code for the function body that
529 /// evaluates this predicate. The argument is expected to be in "Node",
530 /// not N. This handles casting and conversion to a concrete node type as
531 /// appropriate.
532 std::string getCodeToRunOnSDNode() const;
533
534 /// Get the data type of the argument to getImmediatePredicateCode().
535 StringRef getImmType() const;
536
537 /// Get a string that describes the type returned by getImmType() but is
538 /// usable as part of an identifier.
539 StringRef getImmTypeIdentifier() const;
540
541 // Predicate code uses the PatFrag's captured operands.
542 bool usesOperands() const;
543
544 // Is the desired predefined predicate for a load?
545 bool isLoad() const;
546 // Is the desired predefined predicate for a store?
547 bool isStore() const;
548 // Is the desired predefined predicate for an atomic?
549 bool isAtomic() const;
550
551 /// Is this predicate the predefined unindexed load predicate?
552 /// Is this predicate the predefined unindexed store predicate?
553 bool isUnindexed() const;
554 /// Is this predicate the predefined non-extending load predicate?
555 bool isNonExtLoad() const;
556 /// Is this predicate the predefined any-extend load predicate?
557 bool isAnyExtLoad() const;
558 /// Is this predicate the predefined sign-extend load predicate?
559 bool isSignExtLoad() const;
560 /// Is this predicate the predefined zero-extend load predicate?
561 bool isZeroExtLoad() const;
562 /// Is this predicate the predefined non-truncating store predicate?
563 bool isNonTruncStore() const;
564 /// Is this predicate the predefined truncating store predicate?
565 bool isTruncStore() const;
566
567 /// Is this predicate the predefined monotonic atomic predicate?
568 bool isAtomicOrderingMonotonic() const;
569 /// Is this predicate the predefined acquire atomic predicate?
570 bool isAtomicOrderingAcquire() const;
571 /// Is this predicate the predefined release atomic predicate?
572 bool isAtomicOrderingRelease() const;
573 /// Is this predicate the predefined acquire-release atomic predicate?
574 bool isAtomicOrderingAcquireRelease() const;
575 /// Is this predicate the predefined sequentially consistent atomic predicate?
576 bool isAtomicOrderingSequentiallyConsistent() const;
577
578 /// Is this predicate the predefined acquire-or-stronger atomic predicate?
579 bool isAtomicOrderingAcquireOrStronger() const;
580 /// Is this predicate the predefined weaker-than-acquire atomic predicate?
581 bool isAtomicOrderingWeakerThanAcquire() const;
582
583 /// Is this predicate the predefined release-or-stronger atomic predicate?
584 bool isAtomicOrderingReleaseOrStronger() const;
585 /// Is this predicate the predefined weaker-than-release atomic predicate?
586 bool isAtomicOrderingWeakerThanRelease() const;
587
588 /// If non-null, indicates that this predicate is a predefined memory VT
589 /// predicate for a load/store and returns the ValueType record for the memory VT.
590 Record *getMemoryVT() const;
591 /// If non-null, indicates that this predicate is a predefined memory VT
592 /// predicate (checking only the scalar type) for load/store and returns the
593 /// ValueType record for the memory VT.
594 Record *getScalarMemoryVT() const;
595
596 ListInit *getAddressSpaces() const;
597 int64_t getMinAlignment() const;
598
599 // If true, indicates that GlobalISel-based C++ code was supplied.
600 bool hasGISelPredicateCode() const;
601 std::string getGISelPredicateCode() const;
602
603private:
604 bool hasPredCode() const;
605 bool hasImmCode() const;
606 std::string getPredCode() const;
607 std::string getImmCode() const;
608 bool immCodeUsesAPInt() const;
609 bool immCodeUsesAPFloat() const;
610
611 bool isPredefinedPredicateEqualTo(StringRef Field, bool Value) const;
612};
613
614struct TreePredicateCall {
615 TreePredicateFn Fn;
616
617 // Scope -- unique identifier for retrieving named arguments. 0 is used when
618 // the predicate does not use named arguments.
619 unsigned Scope;
620
621 TreePredicateCall(const TreePredicateFn &Fn, unsigned Scope)
622 : Fn(Fn), Scope(Scope) {}
623
624 bool operator==(const TreePredicateCall &o) const {
625 return Fn == o.Fn && Scope == o.Scope;
626 }
627 bool operator!=(const TreePredicateCall &o) const {
628 return !(*this == o);
629 }
630};
631
632class TreePatternNode {
633 /// The type of each node result. Before and during type inference, each
634 /// result may be a set of possible types. After (successful) type inference,
635 /// each is a single concrete type.
636 std::vector<TypeSetByHwMode> Types;
637
638 /// The index of each result in results of the pattern.
639 std::vector<unsigned> ResultPerm;
640
641 /// Operator - The Record for the operator if this is an interior node (not
642 /// a leaf).
643 Record *Operator;
644
645 /// Val - The init value (e.g. the "GPRC" record, or "7") for a leaf.
646 ///
647 Init *Val;
648
649 /// Name - The name given to this node with the :$foo notation.
650 ///
651 std::string Name;
652
653 std::vector<ScopedName> NamesAsPredicateArg;
654
655 /// PredicateCalls - The predicate functions to execute on this node to check
656 /// for a match. If this list is empty, no predicate is involved.
657 std::vector<TreePredicateCall> PredicateCalls;
658
659 /// TransformFn - The transformation function to execute on this node before
660 /// it can be substituted into the resulting instruction on a pattern match.
661 Record *TransformFn;
662
663 std::vector<TreePatternNodePtr> Children;
664
665public:
666 TreePatternNode(Record *Op, std::vector<TreePatternNodePtr> Ch,
667 unsigned NumResults)
668 : Operator(Op), Val(nullptr), TransformFn(nullptr),
669 Children(std::move(Ch)) {
670 Types.resize(NumResults);
671 ResultPerm.resize(NumResults);
672 std::iota(ResultPerm.begin(), ResultPerm.end(), 0);
673 }
674 TreePatternNode(Init *val, unsigned NumResults) // leaf ctor
675 : Operator(nullptr), Val(val), TransformFn(nullptr) {
676 Types.resize(NumResults);
677 ResultPerm.resize(NumResults);
678 std::iota(ResultPerm.begin(), ResultPerm.end(), 0);
679 }
680
681 bool hasName() const { return !Name.empty(); }
682 const std::string &getName() const { return Name; }
683 void setName(StringRef N) { Name.assign(N.begin(), N.end()); }
684
685 const std::vector<ScopedName> &getNamesAsPredicateArg() const {
686 return NamesAsPredicateArg;
687 }
688 void setNamesAsPredicateArg(const std::vector<ScopedName>& Names) {
689 NamesAsPredicateArg = Names;
690 }
691 void addNameAsPredicateArg(const ScopedName &N) {
692 NamesAsPredicateArg.push_back(N);
693 }
694
695 bool isLeaf() const { return Val != nullptr; }
50
Assuming the condition is false
51
Returning zero, which participates in a condition later
696
697 // Type accessors.
698 unsigned getNumTypes() const { return Types.size(); }
699 ValueTypeByHwMode getType(unsigned ResNo) const {
700 return Types[ResNo].getValueTypeByHwMode();
701 }
702 const std::vector<TypeSetByHwMode> &getExtTypes() const { return Types; }
703 const TypeSetByHwMode &getExtType(unsigned ResNo) const {
704 return Types[ResNo];
705 }
706 TypeSetByHwMode &getExtType(unsigned ResNo) { return Types[ResNo]; }
707 void setType(unsigned ResNo, const TypeSetByHwMode &T) { Types[ResNo] = T; }
708 MVT::SimpleValueType getSimpleType(unsigned ResNo) const {
709 return Types[ResNo].getMachineValueType().SimpleTy;
710 }
711
712 bool hasConcreteType(unsigned ResNo) const {
713 return Types[ResNo].isValueTypeByHwMode(false);
714 }
715 bool isTypeCompletelyUnknown(unsigned ResNo, TreePattern &TP) const {
716 return Types[ResNo].empty();
717 }
718
719 unsigned getNumResults() const { return ResultPerm.size(); }
720 unsigned getResultIndex(unsigned ResNo) const { return ResultPerm[ResNo]; }
721 void setResultIndex(unsigned ResNo, unsigned RI) { ResultPerm[ResNo] = RI; }
722
723 Init *getLeafValue() const { assert(isLeaf())((isLeaf()) ? static_cast<void> (0) : __assert_fail ("isLeaf()"
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 723, __PRETTY_FUNCTION__))
; return Val; }
724 Record *getOperator() const { assert(!isLeaf())((!isLeaf()) ? static_cast<void> (0) : __assert_fail ("!isLeaf()"
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 724, __PRETTY_FUNCTION__))
; return Operator; }
725
726 unsigned getNumChildren() const { return Children.size(); }
727 TreePatternNode *getChild(unsigned N) const { return Children[N].get(); }
728 const TreePatternNodePtr &getChildShared(unsigned N) const {
729 return Children[N];
730 }
731 void setChild(unsigned i, TreePatternNodePtr N) { Children[i] = N; }
732
733 /// hasChild - Return true if N is any of our children.
734 bool hasChild(const TreePatternNode *N) const {
735 for (unsigned i = 0, e = Children.size(); i != e; ++i)
736 if (Children[i].get() == N)
737 return true;
738 return false;
739 }
740
741 bool hasProperTypeByHwMode() const;
742 bool hasPossibleType() const;
743 bool setDefaultMode(unsigned Mode);
744
745 bool hasAnyPredicate() const { return !PredicateCalls.empty(); }
746
747 const std::vector<TreePredicateCall> &getPredicateCalls() const {
748 return PredicateCalls;
749 }
750 void clearPredicateCalls() { PredicateCalls.clear(); }
751 void setPredicateCalls(const std::vector<TreePredicateCall> &Calls) {
752 assert(PredicateCalls.empty() && "Overwriting non-empty predicate list!")((PredicateCalls.empty() && "Overwriting non-empty predicate list!"
) ? static_cast<void> (0) : __assert_fail ("PredicateCalls.empty() && \"Overwriting non-empty predicate list!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 752, __PRETTY_FUNCTION__))
;
753 PredicateCalls = Calls;
754 }
755 void addPredicateCall(const TreePredicateCall &Call) {
756 assert(!Call.Fn.isAlwaysTrue() && "Empty predicate string!")((!Call.Fn.isAlwaysTrue() && "Empty predicate string!"
) ? static_cast<void> (0) : __assert_fail ("!Call.Fn.isAlwaysTrue() && \"Empty predicate string!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 756, __PRETTY_FUNCTION__))
;
757 assert(!is_contained(PredicateCalls, Call) && "predicate applied recursively")((!is_contained(PredicateCalls, Call) && "predicate applied recursively"
) ? static_cast<void> (0) : __assert_fail ("!is_contained(PredicateCalls, Call) && \"predicate applied recursively\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 757, __PRETTY_FUNCTION__))
;
758 PredicateCalls.push_back(Call);
759 }
760 void addPredicateCall(const TreePredicateFn &Fn, unsigned Scope) {
761 assert((Scope != 0) == Fn.usesOperands())(((Scope != 0) == Fn.usesOperands()) ? static_cast<void>
(0) : __assert_fail ("(Scope != 0) == Fn.usesOperands()", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 761, __PRETTY_FUNCTION__))
;
762 addPredicateCall(TreePredicateCall(Fn, Scope));
763 }
764
765 Record *getTransformFn() const { return TransformFn; }
766 void setTransformFn(Record *Fn) { TransformFn = Fn; }
767
768 /// getIntrinsicInfo - If this node corresponds to an intrinsic, return the
769 /// CodeGenIntrinsic information for it, otherwise return a null pointer.
770 const CodeGenIntrinsic *getIntrinsicInfo(const CodeGenDAGPatterns &CDP) const;
771
772 /// getComplexPatternInfo - If this node corresponds to a ComplexPattern,
773 /// return the ComplexPattern information, otherwise return null.
774 const ComplexPattern *
775 getComplexPatternInfo(const CodeGenDAGPatterns &CGP) const;
776
777 /// Returns the number of MachineInstr operands that would be produced by this
778 /// node if it mapped directly to an output Instruction's
779 /// operand. ComplexPattern specifies this explicitly; MIOperandInfo gives it
780 /// for Operands; otherwise 1.
781 unsigned getNumMIResults(const CodeGenDAGPatterns &CGP) const;
782
783 /// NodeHasProperty - Return true if this node has the specified property.
784 bool NodeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const;
785
786 /// TreeHasProperty - Return true if any node in this tree has the specified
787 /// property.
788 bool TreeHasProperty(SDNP Property, const CodeGenDAGPatterns &CGP) const;
789
790 /// isCommutativeIntrinsic - Return true if the node is an intrinsic which is
791 /// marked isCommutative.
792 bool isCommutativeIntrinsic(const CodeGenDAGPatterns &CDP) const;
793
794 void print(raw_ostream &OS) const;
795 void dump() const;
796
797public: // Higher level manipulation routines.
798
799 /// clone - Return a new copy of this tree.
800 ///
801 TreePatternNodePtr clone() const;
802
803 /// RemoveAllTypes - Recursively strip all the types of this tree.
804 void RemoveAllTypes();
805
806 /// isIsomorphicTo - Return true if this node is recursively isomorphic to
807 /// the specified node. For this comparison, all of the state of the node
808 /// is considered, except for the assigned name. Nodes with differing names
809 /// that are otherwise identical are considered isomorphic.
810 bool isIsomorphicTo(const TreePatternNode *N,
811 const MultipleUseVarSet &DepVars) const;
812
813 /// SubstituteFormalArguments - Replace the formal arguments in this tree
814 /// with actual values specified by ArgMap.
815 void
816 SubstituteFormalArguments(std::map<std::string, TreePatternNodePtr> &ArgMap);
817
818 /// InlinePatternFragments - If this pattern refers to any pattern
819 /// fragments, return the set of inlined versions (this can be more than
820 /// one if a PatFrags record has multiple alternatives).
821 void InlinePatternFragments(TreePatternNodePtr T,
822 TreePattern &TP,
823 std::vector<TreePatternNodePtr> &OutAlternatives);
824
825 /// ApplyTypeConstraints - Apply all of the type constraints relevant to
826 /// this node and its children in the tree. This returns true if it makes a
827 /// change, false otherwise. If a type contradiction is found, flag an error.
828 bool ApplyTypeConstraints(TreePattern &TP, bool NotRegisters);
829
830 /// UpdateNodeType - Set the node type of N to VT if VT contains
831 /// information. If N already contains a conflicting type, then flag an
832 /// error. This returns true if any information was updated.
833 ///
834 bool UpdateNodeType(unsigned ResNo, const TypeSetByHwMode &InTy,
835 TreePattern &TP);
836 bool UpdateNodeType(unsigned ResNo, MVT::SimpleValueType InTy,
837 TreePattern &TP);
838 bool UpdateNodeType(unsigned ResNo, ValueTypeByHwMode InTy,
839 TreePattern &TP);
840
841 // Update node type with types inferred from an instruction operand or result
842 // def from the ins/outs lists.
843 // Return true if the type changed.
844 bool UpdateNodeTypeFromInst(unsigned ResNo, Record *Operand, TreePattern &TP);
845
846 /// ContainsUnresolvedType - Return true if this tree contains any
847 /// unresolved types.
848 bool ContainsUnresolvedType(TreePattern &TP) const;
849
850 /// canPatternMatch - If it is impossible for this pattern to match on this
851 /// target, fill in Reason and return false. Otherwise, return true.
852 bool canPatternMatch(std::string &Reason, const CodeGenDAGPatterns &CDP);
853};
854
855inline raw_ostream &operator<<(raw_ostream &OS, const TreePatternNode &TPN) {
856 TPN.print(OS);
857 return OS;
858}
859
860
861/// TreePattern - Represent a pattern, used for instructions, pattern
862/// fragments, etc.
863///
864class TreePattern {
865 /// Trees - The list of pattern trees which corresponds to this pattern.
866 /// Note that PatFrag's only have a single tree.
867 ///
868 std::vector<TreePatternNodePtr> Trees;
869
870 /// NamedNodes - This is all of the nodes that have names in the trees in this
871 /// pattern.
872 StringMap<SmallVector<TreePatternNode *, 1>> NamedNodes;
873
874 /// TheRecord - The actual TableGen record corresponding to this pattern.
875 ///
876 Record *TheRecord;
877
878 /// Args - This is a list of all of the arguments to this pattern (for
879 /// PatFrag patterns), which are the 'node' markers in this pattern.
880 std::vector<std::string> Args;
881
882 /// CDP - the top-level object coordinating this madness.
883 ///
884 CodeGenDAGPatterns &CDP;
885
886 /// isInputPattern - True if this is an input pattern, something to match.
887 /// False if this is an output pattern, something to emit.
888 bool isInputPattern;
889
890 /// hasError - True if the currently processed nodes have unresolvable types
891 /// or other non-fatal errors
892 bool HasError;
893
894 /// It's important that the usage of operands in ComplexPatterns is
895 /// consistent: each named operand can be defined by at most one
896 /// ComplexPattern. This records the ComplexPattern instance and the operand
897 /// number for each operand encountered in a ComplexPattern to aid in that
898 /// check.
899 StringMap<std::pair<Record *, unsigned>> ComplexPatternOperands;
900
901 TypeInfer Infer;
902
903public:
904
905 /// TreePattern constructor - Parse the specified DagInits into the
906 /// current record.
907 TreePattern(Record *TheRec, ListInit *RawPat, bool isInput,
908 CodeGenDAGPatterns &ise);
909 TreePattern(Record *TheRec, DagInit *Pat, bool isInput,
910 CodeGenDAGPatterns &ise);
911 TreePattern(Record *TheRec, TreePatternNodePtr Pat, bool isInput,
912 CodeGenDAGPatterns &ise);
913
914 /// getTrees - Return the tree patterns which corresponds to this pattern.
915 ///
916 const std::vector<TreePatternNodePtr> &getTrees() const { return Trees; }
917 unsigned getNumTrees() const { return Trees.size(); }
918 const TreePatternNodePtr &getTree(unsigned i) const { return Trees[i]; }
919 void setTree(unsigned i, TreePatternNodePtr Tree) { Trees[i] = Tree; }
920 const TreePatternNodePtr &getOnlyTree() const {
921 assert(Trees.size() == 1 && "Doesn't have exactly one pattern!")((Trees.size() == 1 && "Doesn't have exactly one pattern!"
) ? static_cast<void> (0) : __assert_fail ("Trees.size() == 1 && \"Doesn't have exactly one pattern!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 921, __PRETTY_FUNCTION__))
;
922 return Trees[0];
923 }
924
925 const StringMap<SmallVector<TreePatternNode *, 1>> &getNamedNodesMap() {
926 if (NamedNodes.empty())
927 ComputeNamedNodes();
928 return NamedNodes;
929 }
930
931 /// getRecord - Return the actual TableGen record corresponding to this
932 /// pattern.
933 ///
934 Record *getRecord() const { return TheRecord; }
935
936 unsigned getNumArgs() const { return Args.size(); }
937 const std::string &getArgName(unsigned i) const {
938 assert(i < Args.size() && "Argument reference out of range!")((i < Args.size() && "Argument reference out of range!"
) ? static_cast<void> (0) : __assert_fail ("i < Args.size() && \"Argument reference out of range!\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 938, __PRETTY_FUNCTION__))
;
939 return Args[i];
940 }
941 std::vector<std::string> &getArgList() { return Args; }
942
943 CodeGenDAGPatterns &getDAGPatterns() const { return CDP; }
944
945 /// InlinePatternFragments - If this pattern refers to any pattern
946 /// fragments, inline them into place, giving us a pattern without any
947 /// PatFrags references. This may increase the number of trees in the
948 /// pattern if a PatFrags has multiple alternatives.
949 void InlinePatternFragments() {
950 std::vector<TreePatternNodePtr> Copy = Trees;
951 Trees.clear();
952 for (unsigned i = 0, e = Copy.size(); i != e; ++i)
953 Copy[i]->InlinePatternFragments(Copy[i], *this, Trees);
954 }
955
956 /// InferAllTypes - Infer/propagate as many types throughout the expression
957 /// patterns as possible. Return true if all types are inferred, false
958 /// otherwise. Bail out if a type contradiction is found.
959 bool InferAllTypes(
960 const StringMap<SmallVector<TreePatternNode *, 1>> *NamedTypes = nullptr);
961
962 /// error - If this is the first error in the current resolution step,
963 /// print it and set the error flag. Otherwise, continue silently.
964 void error(const Twine &Msg);
965 bool hasError() const {
966 return HasError;
967 }
968 void resetError() {
969 HasError = false;
970 }
971
972 TypeInfer &getInfer() { return Infer; }
973
974 void print(raw_ostream &OS) const;
975 void dump() const;
976
977private:
978 TreePatternNodePtr ParseTreePattern(Init *DI, StringRef OpName);
979 void ComputeNamedNodes();
980 void ComputeNamedNodes(TreePatternNode *N);
981};
982
983
984inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
985 const TypeSetByHwMode &InTy,
986 TreePattern &TP) {
987 TypeSetByHwMode VTS(InTy);
988 TP.getInfer().expandOverloads(VTS);
989 return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
990}
991
992inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
993 MVT::SimpleValueType InTy,
994 TreePattern &TP) {
995 TypeSetByHwMode VTS(InTy);
996 TP.getInfer().expandOverloads(VTS);
997 return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
998}
999
1000inline bool TreePatternNode::UpdateNodeType(unsigned ResNo,
1001 ValueTypeByHwMode InTy,
1002 TreePattern &TP) {
1003 TypeSetByHwMode VTS(InTy);
1004 TP.getInfer().expandOverloads(VTS);
1005 return TP.getInfer().MergeInTypeInfo(Types[ResNo], VTS);
1006}
1007
1008
1009/// DAGDefaultOperand - One of these is created for each OperandWithDefaultOps
1010/// that has a set ExecuteAlways / DefaultOps field.
1011struct DAGDefaultOperand {
1012 std::vector<TreePatternNodePtr> DefaultOps;
1013};
1014
1015class DAGInstruction {
1016 std::vector<Record*> Results;
1017 std::vector<Record*> Operands;
1018 std::vector<Record*> ImpResults;
1019 TreePatternNodePtr SrcPattern;
1020 TreePatternNodePtr ResultPattern;
1021
1022public:
1023 DAGInstruction(const std::vector<Record*> &results,
1024 const std::vector<Record*> &operands,
1025 const std::vector<Record*> &impresults,
1026 TreePatternNodePtr srcpattern = nullptr,
1027 TreePatternNodePtr resultpattern = nullptr)
1028 : Results(results), Operands(operands), ImpResults(impresults),
1029 SrcPattern(srcpattern), ResultPattern(resultpattern) {}
1030
1031 unsigned getNumResults() const { return Results.size(); }
1032 unsigned getNumOperands() const { return Operands.size(); }
1033 unsigned getNumImpResults() const { return ImpResults.size(); }
1034 const std::vector<Record*>& getImpResults() const { return ImpResults; }
1035
1036 Record *getResult(unsigned RN) const {
1037 assert(RN < Results.size())((RN < Results.size()) ? static_cast<void> (0) : __assert_fail
("RN < Results.size()", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 1037, __PRETTY_FUNCTION__))
;
1038 return Results[RN];
1039 }
1040
1041 Record *getOperand(unsigned ON) const {
1042 assert(ON < Operands.size())((ON < Operands.size()) ? static_cast<void> (0) : __assert_fail
("ON < Operands.size()", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 1042, __PRETTY_FUNCTION__))
;
1043 return Operands[ON];
1044 }
1045
1046 Record *getImpResult(unsigned RN) const {
1047 assert(RN < ImpResults.size())((RN < ImpResults.size()) ? static_cast<void> (0) : __assert_fail
("RN < ImpResults.size()", "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 1047, __PRETTY_FUNCTION__))
;
1048 return ImpResults[RN];
1049 }
1050
1051 TreePatternNodePtr getSrcPattern() const { return SrcPattern; }
1052 TreePatternNodePtr getResultPattern() const { return ResultPattern; }
1053};
1054
1055/// This class represents a condition that has to be satisfied for a pattern
1056/// to be tried. It is a generalization of a class "Pattern" from Target.td:
1057/// in addition to the Target.td's predicates, this class can also represent
1058/// conditions associated with HW modes. Both types will eventually become
1059/// strings containing C++ code to be executed, the difference is in how
1060/// these strings are generated.
1061class Predicate {
1062public:
1063 Predicate(Record *R, bool C = true) : Def(R), IfCond(C), IsHwMode(false) {
1064 assert(R->isSubClassOf("Predicate") &&((R->isSubClassOf("Predicate") && "Predicate objects should only be created for records derived"
"from Predicate class") ? static_cast<void> (0) : __assert_fail
("R->isSubClassOf(\"Predicate\") && \"Predicate objects should only be created for records derived\" \"from Predicate class\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 1066, __PRETTY_FUNCTION__))
1065 "Predicate objects should only be created for records derived"((R->isSubClassOf("Predicate") && "Predicate objects should only be created for records derived"
"from Predicate class") ? static_cast<void> (0) : __assert_fail
("R->isSubClassOf(\"Predicate\") && \"Predicate objects should only be created for records derived\" \"from Predicate class\""
, "/build/llvm-toolchain-snapshot-10~svn374877/utils/TableGen/CodeGenDAGPatterns.h"
, 1066, __PRETTY_FUNCTION__))
1066 "from Predicate class")((R->isSubClassOf("Predicate") && "Predicate objects should only be created for records derived"
"from Predi