Bug Summary

File:llvm/utils/TableGen/CodeGenDAGPatterns.cpp
Warning:line 3351, column 11
Called C++ object pointer is null

Annotated Source Code

Press '?' to see keyboard shortcuts

clang -cc1 -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 -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -mframe-pointer=none -fmath-errno -fno-rounding-math -mconstructor-aliases -munwind-tables -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -ffunction-sections -fdata-sections -fcoverage-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/utils/TableGen -resource-dir /usr/lib/llvm-13/lib/clang/13.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/utils/TableGen -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/utils/TableGen -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/include -I /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/include -D NDEBUG -U NDEBUG -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/x86_64-linux-gnu/c++/10 -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../include/c++/10/backward -internal-isystem /usr/lib/llvm-13/lib/clang/13.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/10/../../../../x86_64-linux-gnu/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-class-memaccess -Wno-redundant-move -Wno-pessimizing-move -Wno-noexcept-type -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/build-llvm/utils/TableGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c=. -ferror-limit 19 -fvisibility-inlines-hidden -stack-protector 2 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -analyzer-config stable-report-filename=true -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2021-07-26-235520-9401-1 -x c++ /build/llvm-toolchain-snapshot-13~++20210726100616+dead50d4427c/llvm/utils/TableGen/CodeGenDAGPatterns.cpp

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

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