Bug Summary

File:llvm/utils/TableGen/CodeGenDAGPatterns.cpp
Warning:line 3350, 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-10/lib/clang/10.0.0 -D _DEBUG -D _GNU_SOURCE -D __STDC_CONSTANT_MACROS -D __STDC_FORMAT_MACROS -D __STDC_LIMIT_MACROS -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/utils/TableGen -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/utils/TableGen -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/include -I /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/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-10/lib/clang/10.0.0/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -O2 -Wno-unused-parameter -Wwrite-strings -Wno-missing-field-initializers -Wno-long-long -Wno-maybe-uninitialized -Wno-comment -std=c++14 -fdeprecated-macro -fdebug-compilation-dir /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/build-llvm/utils/TableGen -fdebug-prefix-map=/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd=. -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-01-13-084841-49055-1 -x c++ /build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/utils/TableGen/CodeGenDAGPatterns.cpp

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

/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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(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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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-10~++20200112100611+7fa5290d5bd/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 TreePatternNodePtr srcpattern = nullptr,
1028 TreePatternNodePtr resultpattern = nullptr)
1029 : Results(results), Operands(operands), ImpResults(impresults),
1030 SrcPattern(srcpattern), ResultPattern(resultpattern) {}
1031
1032 unsigned getNumResults() const { return Results.size(); }
1033 unsigned getNumOperands() const { return Operands.size(); }
1034 unsigned getNumImpResults() const { return ImpResults.size(); }
1035 const std::vector<Record*>& getImpResults() const { return ImpResults; }
1036
1037 Record *getResult(unsigned RN) const {
1038 assert(RN < Results.size())((RN < Results.size()) ? static_cast<void> (0) : __assert_fail
("RN < Results.size()", "/build/llvm-toolchain-snapshot-10~++20200112100611+7fa5290d5bd/llvm/utils/TableGen/CodeGenDAGPatterns.h"
, 1038, __PRETTY_FUNCTION__))
;