Bug Summary

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

Annotated Source Code

Press '?' to see keyboard shortcuts

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

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

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