1//===- RISCVVSETVLIInfoAnalysis.h - VSETVLI Info Analysis -----------------===//
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 an analysis of the vtype/vl information that is needed
10// by RISCVInsertVSETVLI pass and others.
11//
12//===----------------------------------------------------------------------===//
13
14#include "RISCV.h"
15#include "RISCVSubtarget.h"
16#include "llvm/ADT/Statistic.h"
17#include "llvm/CodeGen/LiveDebugVariables.h"
18#include "llvm/CodeGen/LiveIntervals.h"
19#include "llvm/CodeGen/LiveStacks.h"
20
21namespace llvm {
22namespace RISCV {
23/// Which subfields of VL or VTYPE have values we need to preserve?
24struct DemandedFields {
25 // Some unknown property of VL is used. If demanded, must preserve entire
26 // value.
27 bool VLAny = false;
28 // Only zero vs non-zero is used. If demanded, can change non-zero values.
29 bool VLZeroness = false;
30 // What properties of SEW we need to preserve.
31 enum : uint8_t {
32 SEWEqual = 3, // The exact value of SEW needs to be preserved.
33 SEWGreaterThanOrEqualAndLessThan64 =
34 2, // SEW can be changed as long as it's greater
35 // than or equal to the original value, but must be less
36 // than 64.
37 SEWGreaterThanOrEqual = 1, // SEW can be changed as long as it's greater
38 // than or equal to the original value.
39 SEWNone = 0 // We don't need to preserve SEW at all.
40 } SEW = SEWNone;
41 enum : uint8_t {
42 LMULEqual = 2, // The exact value of LMUL needs to be preserved.
43 LMULLessThanOrEqualToM1 = 1, // We can use any LMUL <= M1.
44 LMULNone = 0 // We don't need to preserve LMUL at all.
45 } LMUL = LMULNone;
46 bool SEWLMULRatio = false;
47 bool TailPolicy = false;
48 bool MaskPolicy = false;
49 // If this is true, we demand that VTYPE is set to some legal state, i.e. that
50 // vill is unset.
51 bool VILL = false;
52 bool TWiden = false;
53 bool AltFmt = false;
54
55 // Return true if any part of VTYPE was used
56 bool usedVTYPE() const {
57 return SEW || LMUL || SEWLMULRatio || TailPolicy || MaskPolicy || VILL ||
58 TWiden || AltFmt;
59 }
60
61 // Return true if any property of VL was used
62 bool usedVL() { return VLAny || VLZeroness; }
63
64 // Mark all VTYPE subfields and properties as demanded
65 void demandVTYPE() {
66 SEW = SEWEqual;
67 LMUL = LMULEqual;
68 SEWLMULRatio = true;
69 TailPolicy = true;
70 MaskPolicy = true;
71 VILL = true;
72 TWiden = true;
73 AltFmt = true;
74 }
75
76 // Mark all VL properties as demanded
77 void demandVL() {
78 VLAny = true;
79 VLZeroness = true;
80 }
81
82 static DemandedFields all() {
83 DemandedFields DF;
84 DF.demandVTYPE();
85 DF.demandVL();
86 return DF;
87 }
88
89 // Make this the result of demanding both the fields in this and B.
90 void doUnion(const DemandedFields &B) {
91 VLAny |= B.VLAny;
92 VLZeroness |= B.VLZeroness;
93 SEW = std::max(a: SEW, b: B.SEW);
94 LMUL = std::max(a: LMUL, b: B.LMUL);
95 SEWLMULRatio |= B.SEWLMULRatio;
96 TailPolicy |= B.TailPolicy;
97 MaskPolicy |= B.MaskPolicy;
98 VILL |= B.VILL;
99 AltFmt |= B.AltFmt;
100 TWiden |= B.TWiden;
101 }
102
103#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
104 /// Support for debugging, callable in GDB: V->dump()
105 LLVM_DUMP_METHOD void dump() const {
106 print(dbgs());
107 dbgs() << "\n";
108 }
109
110 /// Implement operator<<.
111 void print(raw_ostream &OS) const {
112 OS << "{";
113 OS << "VLAny=" << VLAny << ", ";
114 OS << "VLZeroness=" << VLZeroness << ", ";
115 OS << "SEW=";
116 switch (SEW) {
117 case SEWEqual:
118 OS << "SEWEqual";
119 break;
120 case SEWGreaterThanOrEqual:
121 OS << "SEWGreaterThanOrEqual";
122 break;
123 case SEWGreaterThanOrEqualAndLessThan64:
124 OS << "SEWGreaterThanOrEqualAndLessThan64";
125 break;
126 case SEWNone:
127 OS << "SEWNone";
128 break;
129 };
130 OS << ", ";
131 OS << "LMUL=";
132 switch (LMUL) {
133 case LMULEqual:
134 OS << "LMULEqual";
135 break;
136 case LMULLessThanOrEqualToM1:
137 OS << "LMULLessThanOrEqualToM1";
138 break;
139 case LMULNone:
140 OS << "LMULNone";
141 break;
142 };
143 OS << ", ";
144 OS << "SEWLMULRatio=" << SEWLMULRatio << ", ";
145 OS << "TailPolicy=" << TailPolicy << ", ";
146 OS << "MaskPolicy=" << MaskPolicy << ", ";
147 OS << "VILL=" << VILL << ", ";
148 OS << "AltFmt=" << AltFmt << ", ";
149 OS << "TWiden=" << TWiden;
150 OS << "}";
151 }
152#endif
153};
154
155#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
156LLVM_ATTRIBUTE_USED
157inline raw_ostream &operator<<(raw_ostream &OS, const DemandedFields &DF) {
158 DF.print(OS);
159 return OS;
160}
161#endif
162
163bool areCompatibleVTYPEs(uint64_t CurVType, uint64_t NewVType,
164 const DemandedFields &Used);
165
166/// Return the fields and properties demanded by the provided instruction.
167DemandedFields getDemanded(const MachineInstr &MI, const RISCVSubtarget *ST);
168
169/// Defines the abstract state with which the forward dataflow models the
170/// values of the VL and VTYPE registers after insertion.
171class VSETVLIInfo {
172 struct AVLDef {
173 // Every AVLDef should have a VNInfo, unless we're running without
174 // LiveIntervals in which case this will be nullptr.
175 const VNInfo *ValNo;
176 Register DefReg;
177 };
178 union {
179 AVLDef AVLRegDef;
180 unsigned AVLImm;
181 };
182
183 enum class AVLState : uint8_t {
184 Uninitialized,
185 AVLIsReg,
186 AVLIsImm,
187 AVLIsVLMAX,
188 Unknown, // AVL and VTYPE are fully unknown
189 } State = AVLState::Uninitialized;
190
191 // Fields from VTYPE.
192 RISCVVType::VLMUL VLMul = RISCVVType::LMUL_1;
193 uint8_t SEW = 0;
194 uint8_t TailAgnostic : 1;
195 uint8_t MaskAgnostic : 1;
196 uint8_t SEWLMULRatioOnly : 1;
197 uint8_t AltFmt : 1;
198 uint8_t TWiden : 3;
199
200public:
201 VSETVLIInfo()
202 : AVLImm(0), TailAgnostic(false), MaskAgnostic(false),
203 SEWLMULRatioOnly(false), AltFmt(false), TWiden(0) {}
204
205 static VSETVLIInfo getUnknown() {
206 VSETVLIInfo Info;
207 Info.setUnknown();
208 return Info;
209 }
210
211 bool isValid() const { return State != AVLState::Uninitialized; }
212 void setUnknown() { State = AVLState::Unknown; }
213 bool isUnknown() const { return State == AVLState::Unknown; }
214
215 void setAVLRegDef(const VNInfo *VNInfo, Register AVLReg) {
216 assert(AVLReg.isVirtual());
217 AVLRegDef.ValNo = VNInfo;
218 AVLRegDef.DefReg = AVLReg;
219 State = AVLState::AVLIsReg;
220 }
221
222 void setAVLImm(unsigned Imm) {
223 AVLImm = Imm;
224 State = AVLState::AVLIsImm;
225 }
226
227 void setAVLVLMAX() { State = AVLState::AVLIsVLMAX; }
228
229 bool hasAVLImm() const { return State == AVLState::AVLIsImm; }
230 bool hasAVLReg() const { return State == AVLState::AVLIsReg; }
231 bool hasAVLVLMAX() const { return State == AVLState::AVLIsVLMAX; }
232 Register getAVLReg() const {
233 assert(hasAVLReg() && AVLRegDef.DefReg.isVirtual());
234 return AVLRegDef.DefReg;
235 }
236 unsigned getAVLImm() const {
237 assert(hasAVLImm());
238 return AVLImm;
239 }
240 const VNInfo *getAVLVNInfo() const {
241 assert(hasAVLReg());
242 return AVLRegDef.ValNo;
243 }
244 // Most AVLIsReg infos will have a single defining MachineInstr, unless it was
245 // a PHI node. In that case getAVLVNInfo()->def will point to the block
246 // boundary slot and this will return nullptr. If LiveIntervals isn't
247 // available, nullptr is also returned.
248 const MachineInstr *getAVLDefMI(const LiveIntervals *LIS) const {
249 assert(hasAVLReg());
250 if (!LIS || getAVLVNInfo()->isPHIDef())
251 return nullptr;
252 auto *MI = LIS->getInstructionFromIndex(index: getAVLVNInfo()->def);
253 assert(MI);
254 return MI;
255 }
256
257 void setAVL(const VSETVLIInfo &Info) {
258 assert(Info.isValid());
259 if (Info.isUnknown())
260 setUnknown();
261 else if (Info.hasAVLReg())
262 setAVLRegDef(VNInfo: Info.getAVLVNInfo(), AVLReg: Info.getAVLReg());
263 else if (Info.hasAVLVLMAX())
264 setAVLVLMAX();
265 else {
266 assert(Info.hasAVLImm());
267 setAVLImm(Info.getAVLImm());
268 }
269 }
270
271 bool hasSEWLMULRatioOnly() const {
272 assert(isValid() && !isUnknown() &&
273 "Can't use VTYPE for uninitialized or unknown");
274 return SEWLMULRatioOnly;
275 }
276
277 unsigned getSEW() const {
278 assert(isValid() && !isUnknown() && !hasSEWLMULRatioOnly() &&
279 "Can't use VTYPE for uninitialized or unknown");
280 return SEW;
281 }
282 RISCVVType::VLMUL getVLMUL() const {
283 assert(isValid() && !isUnknown() && !hasSEWLMULRatioOnly() &&
284 "Can't use VTYPE for uninitialized or unknown");
285 return VLMul;
286 }
287 bool getTailAgnostic() const {
288 assert(isValid() && !isUnknown() &&
289 "Can't use VTYPE for uninitialized or unknown");
290 return TailAgnostic;
291 }
292 bool getMaskAgnostic() const {
293 assert(isValid() && !isUnknown() &&
294 "Can't use VTYPE for uninitialized or unknown");
295 return MaskAgnostic;
296 }
297 bool getAltFmt() const {
298 assert(isValid() && !isUnknown() &&
299 "Can't use VTYPE for uninitialized or unknown");
300 return AltFmt;
301 }
302 unsigned getTWiden() const {
303 assert(isValid() && !isUnknown() &&
304 "Can't use VTYPE for uninitialized or unknown");
305 return TWiden;
306 }
307
308 bool hasNonZeroAVL(const LiveIntervals *LIS) const {
309 if (hasAVLImm())
310 return getAVLImm() > 0;
311 if (hasAVLReg()) {
312 if (auto *DefMI = getAVLDefMI(LIS))
313 return RISCVInstrInfo::isNonZeroLoadImmediate(MI: *DefMI);
314 }
315 if (hasAVLVLMAX())
316 return true;
317 return false;
318 }
319
320 bool hasEquallyZeroAVL(const VSETVLIInfo &Other,
321 const LiveIntervals *LIS) const {
322 if (hasSameAVL(Other))
323 return true;
324 return (hasNonZeroAVL(LIS) && Other.hasNonZeroAVL(LIS));
325 }
326
327 bool hasSameAVLLatticeValue(const VSETVLIInfo &Other) const {
328 if (hasAVLReg() && Other.hasAVLReg()) {
329 assert(!getAVLVNInfo() == !Other.getAVLVNInfo() &&
330 "we either have intervals or we don't");
331 if (!getAVLVNInfo())
332 return getAVLReg() == Other.getAVLReg();
333 return getAVLVNInfo()->id == Other.getAVLVNInfo()->id &&
334 getAVLReg() == Other.getAVLReg();
335 }
336
337 if (hasAVLImm() && Other.hasAVLImm())
338 return getAVLImm() == Other.getAVLImm();
339
340 if (hasAVLVLMAX())
341 return Other.hasAVLVLMAX() && hasSameVLMAX(Other);
342
343 return false;
344 }
345
346 // Return true if the two lattice values are guaranteed to have
347 // the same AVL value at runtime.
348 bool hasSameAVL(const VSETVLIInfo &Other) const {
349 // Without LiveIntervals, we don't know which instruction defines a
350 // register. Since a register may be redefined, this means all AVLIsReg
351 // states must be treated as possibly distinct.
352 if (hasAVLReg() && Other.hasAVLReg()) {
353 assert(!getAVLVNInfo() == !Other.getAVLVNInfo() &&
354 "we either have intervals or we don't");
355 if (!getAVLVNInfo())
356 return false;
357 }
358 return hasSameAVLLatticeValue(Other);
359 }
360
361 void setVTYPE(unsigned VType) {
362 assert(isValid() && !isUnknown() &&
363 "Can't set VTYPE for uninitialized or unknown");
364 VLMul = RISCVVType::getVLMUL(VType);
365 SEW = RISCVVType::getSEW(VType);
366 TailAgnostic = RISCVVType::isTailAgnostic(VType);
367 MaskAgnostic = RISCVVType::isMaskAgnostic(VType);
368 AltFmt = RISCVVType::isAltFmt(VType);
369 TWiden =
370 RISCVVType::hasXSfmmWiden(VType) ? RISCVVType::getXSfmmWiden(VType) : 0;
371 }
372 void setVTYPE(RISCVVType::VLMUL L, unsigned S, bool TA, bool MA, bool Altfmt,
373 unsigned W) {
374 assert(isValid() && !isUnknown() &&
375 "Can't set VTYPE for uninitialized or unknown");
376 VLMul = L;
377 SEW = S;
378 TailAgnostic = TA;
379 MaskAgnostic = MA;
380 AltFmt = Altfmt;
381 TWiden = W;
382 }
383
384 void setAltFmt(bool AF) { AltFmt = AF; }
385
386 void setVLMul(RISCVVType::VLMUL VLMul) { this->VLMul = VLMul; }
387
388 unsigned encodeVTYPE() const {
389 assert(isValid() && !isUnknown() && !SEWLMULRatioOnly &&
390 "Can't encode VTYPE for uninitialized or unknown");
391 if (TWiden != 0)
392 return RISCVVType::encodeXSfmmVType(SEW, Widen: TWiden, AltFmt);
393 return RISCVVType::encodeVTYPE(VLMUL: VLMul, SEW, TailAgnostic, MaskAgnostic,
394 AltFmt);
395 }
396
397 bool hasSameVTYPE(const VSETVLIInfo &Other) const {
398 assert(isValid() && Other.isValid() &&
399 "Can't compare invalid VSETVLIInfos");
400 assert(!isUnknown() && !Other.isUnknown() &&
401 "Can't compare VTYPE in unknown state");
402 assert(!SEWLMULRatioOnly && !Other.SEWLMULRatioOnly &&
403 "Can't compare when only LMUL/SEW ratio is valid.");
404 return std::tie(args: VLMul, args: SEW, args: TailAgnostic, args: MaskAgnostic, args: AltFmt, args: TWiden) ==
405 std::tie(args: Other.VLMul, args: Other.SEW, args: Other.TailAgnostic,
406 args: Other.MaskAgnostic, args: Other.AltFmt, args: Other.TWiden);
407 }
408
409 unsigned getSEWLMULRatio() const {
410 assert(isValid() && !isUnknown() &&
411 "Can't use VTYPE for uninitialized or unknown");
412 return RISCVVType::getSEWLMULRatio(SEW, VLMul);
413 }
414
415 // Check if the VTYPE for these two VSETVLIInfos produce the same VLMAX.
416 // Note that having the same VLMAX ensures that both share the same
417 // function from AVL to VL; that is, they must produce the same VL value
418 // for any given AVL value.
419 bool hasSameVLMAX(const VSETVLIInfo &Other) const {
420 assert(isValid() && Other.isValid() &&
421 "Can't compare invalid VSETVLIInfos");
422 assert(!isUnknown() && !Other.isUnknown() &&
423 "Can't compare VTYPE in unknown state");
424 return getSEWLMULRatio() == Other.getSEWLMULRatio();
425 }
426
427 bool hasCompatibleVTYPE(const DemandedFields &Used,
428 const VSETVLIInfo &Require) const;
429
430 // Determine whether the vector instructions requirements represented by
431 // Require are compatible with the previous vsetvli instruction represented
432 // by this. MI is the instruction whose requirements we're considering.
433 bool isCompatible(const DemandedFields &Used, const VSETVLIInfo &Require,
434 const LiveIntervals *LIS) const {
435 assert(isValid() && Require.isValid() &&
436 "Can't compare invalid VSETVLIInfos");
437 // Nothing is compatible with Unknown.
438 if (isUnknown() || Require.isUnknown())
439 return false;
440
441 // If only our VLMAX ratio is valid, then this isn't compatible.
442 if (SEWLMULRatioOnly || Require.SEWLMULRatioOnly)
443 return false;
444
445 if (Used.VLAny && !(hasSameAVL(Other: Require) && hasSameVLMAX(Other: Require)))
446 return false;
447
448 if (Used.VLZeroness && !hasEquallyZeroAVL(Other: Require, LIS))
449 return false;
450
451 return hasCompatibleVTYPE(Used, Require);
452 }
453
454 bool operator==(const VSETVLIInfo &Other) const {
455 // Uninitialized is only equal to another Uninitialized.
456 if (!isValid())
457 return !Other.isValid();
458 if (!Other.isValid())
459 return !isValid();
460
461 // Unknown is only equal to another Unknown.
462 if (isUnknown())
463 return Other.isUnknown();
464 if (Other.isUnknown())
465 return isUnknown();
466
467 if (!hasSameAVLLatticeValue(Other))
468 return false;
469
470 // If the SEWLMULRatioOnly bits are different, then they aren't equal.
471 if (SEWLMULRatioOnly != Other.SEWLMULRatioOnly)
472 return false;
473
474 // If only the VLMAX is valid, check that it is the same.
475 if (SEWLMULRatioOnly)
476 return hasSameVLMAX(Other);
477
478 // If the full VTYPE is valid, check that it is the same.
479 return hasSameVTYPE(Other);
480 }
481
482 bool operator!=(const VSETVLIInfo &Other) const { return !(*this == Other); }
483
484 // Calculate the VSETVLIInfo visible to a block assuming this and Other are
485 // both predecessors.
486 VSETVLIInfo intersect(const VSETVLIInfo &Other) const {
487 // If the new value isn't valid, ignore it.
488 if (!Other.isValid())
489 return *this;
490
491 // If this value isn't valid, this must be the first predecessor, use it.
492 if (!isValid())
493 return Other;
494
495 // If either is unknown, the result is unknown.
496 if (isUnknown() || Other.isUnknown())
497 return VSETVLIInfo::getUnknown();
498
499 // If we have an exact, match return this.
500 if (*this == Other)
501 return *this;
502
503 // Not an exact match, but maybe the AVL and VLMAX are the same. If so,
504 // return an SEW/LMUL ratio only value.
505 if (hasSameAVL(Other) && hasSameVLMAX(Other)) {
506 VSETVLIInfo MergeInfo = *this;
507 MergeInfo.SEWLMULRatioOnly = true;
508 return MergeInfo;
509 }
510
511 // Otherwise the result is unknown.
512 return VSETVLIInfo::getUnknown();
513 }
514
515#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
516 /// Support for debugging, callable in GDB: V->dump()
517 LLVM_DUMP_METHOD void dump() const {
518 print(dbgs());
519 dbgs() << "\n";
520 }
521
522 /// Implement operator<<.
523 /// @{
524 void print(raw_ostream &OS) const {
525 OS << '{';
526 switch (State) {
527 case AVLState::Uninitialized:
528 OS << "Uninitialized";
529 break;
530 case AVLState::Unknown:
531 OS << "unknown";
532 break;
533 case AVLState::AVLIsReg:
534 OS << "AVLReg=" << llvm::printReg(getAVLReg());
535 break;
536 case AVLState::AVLIsImm:
537 OS << "AVLImm=" << (unsigned)AVLImm;
538 break;
539 case AVLState::AVLIsVLMAX:
540 OS << "AVLVLMAX";
541 break;
542 }
543 if (isValid() && !isUnknown()) {
544 OS << ", ";
545
546 unsigned LMul;
547 bool Fractional;
548 std::tie(LMul, Fractional) = decodeVLMUL(VLMul);
549
550 OS << "VLMul=m";
551 if (Fractional)
552 OS << 'f';
553 OS << LMul << ", "
554 << "SEW=e" << (unsigned)SEW << ", "
555 << "TailAgnostic=" << (bool)TailAgnostic << ", "
556 << "MaskAgnostic=" << (bool)MaskAgnostic << ", "
557 << "SEWLMULRatioOnly=" << (bool)SEWLMULRatioOnly << ", "
558 << "TWiden=" << (unsigned)TWiden << ", "
559 << "AltFmt=" << (bool)AltFmt;
560 }
561
562 OS << '}';
563 }
564#endif
565};
566
567#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
568LLVM_ATTRIBUTE_USED
569inline raw_ostream &operator<<(raw_ostream &OS, const VSETVLIInfo &V) {
570 V.print(OS);
571 return OS;
572}
573#endif
574
575class RISCVVSETVLIInfoAnalysis {
576 const RISCVSubtarget *ST;
577 // Possibly null!
578 LiveIntervals *LIS;
579
580public:
581 RISCVVSETVLIInfoAnalysis() = default;
582 RISCVVSETVLIInfoAnalysis(const RISCVSubtarget *ST, LiveIntervals *LIS)
583 : ST(ST), LIS(LIS) {}
584
585 VSETVLIInfo getInfoForVSETVLI(const MachineInstr &MI) const;
586 VSETVLIInfo computeInfoForInstr(const MachineInstr &MI) const;
587
588private:
589 void forwardVSETVLIAVL(VSETVLIInfo &Info) const;
590};
591
592} // namespace RISCV
593} // namespace llvm
594