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 { return SEWLMULRatioOnly; }
272
273 unsigned getSEW() const {
274 assert(isValid() && !isUnknown() && !hasSEWLMULRatioOnly() &&
275 "Can't use VTYPE for uninitialized or unknown");
276 return SEW;
277 }
278 RISCVVType::VLMUL getVLMUL() const {
279 assert(isValid() && !isUnknown() && !hasSEWLMULRatioOnly() &&
280 "Can't use VTYPE for uninitialized or unknown");
281 return VLMul;
282 }
283 bool getTailAgnostic() const {
284 assert(isValid() && !isUnknown() &&
285 "Can't use VTYPE for uninitialized or unknown");
286 return TailAgnostic;
287 }
288 bool getMaskAgnostic() const {
289 assert(isValid() && !isUnknown() &&
290 "Can't use VTYPE for uninitialized or unknown");
291 return MaskAgnostic;
292 }
293 bool getAltFmt() const {
294 assert(isValid() && !isUnknown() &&
295 "Can't use VTYPE for uninitialized or unknown");
296 return AltFmt;
297 }
298 unsigned getTWiden() const {
299 assert(isValid() && !isUnknown() &&
300 "Can't use VTYPE for uninitialized or unknown");
301 return TWiden;
302 }
303
304 bool hasNonZeroAVL(const LiveIntervals *LIS) const {
305 if (hasAVLImm())
306 return getAVLImm() > 0;
307 if (hasAVLReg()) {
308 if (auto *DefMI = getAVLDefMI(LIS))
309 return RISCVInstrInfo::isNonZeroLoadImmediate(MI: *DefMI);
310 }
311 if (hasAVLVLMAX())
312 return true;
313 return false;
314 }
315
316 bool hasEquallyZeroAVL(const VSETVLIInfo &Other,
317 const LiveIntervals *LIS) const {
318 if (hasSameAVL(Other))
319 return true;
320 return (hasNonZeroAVL(LIS) && Other.hasNonZeroAVL(LIS));
321 }
322
323 bool hasSameAVLLatticeValue(const VSETVLIInfo &Other) const {
324 if (hasAVLReg() && Other.hasAVLReg()) {
325 assert(!getAVLVNInfo() == !Other.getAVLVNInfo() &&
326 "we either have intervals or we don't");
327 if (!getAVLVNInfo())
328 return getAVLReg() == Other.getAVLReg();
329 return getAVLVNInfo()->id == Other.getAVLVNInfo()->id &&
330 getAVLReg() == Other.getAVLReg();
331 }
332
333 if (hasAVLImm() && Other.hasAVLImm())
334 return getAVLImm() == Other.getAVLImm();
335
336 if (hasAVLVLMAX())
337 return Other.hasAVLVLMAX() && hasSameVLMAX(Other);
338
339 return false;
340 }
341
342 // Return true if the two lattice values are guaranteed to have
343 // the same AVL value at runtime.
344 bool hasSameAVL(const VSETVLIInfo &Other) const {
345 // Without LiveIntervals, we don't know which instruction defines a
346 // register. Since a register may be redefined, this means all AVLIsReg
347 // states must be treated as possibly distinct.
348 if (hasAVLReg() && Other.hasAVLReg()) {
349 assert(!getAVLVNInfo() == !Other.getAVLVNInfo() &&
350 "we either have intervals or we don't");
351 if (!getAVLVNInfo())
352 return false;
353 }
354 return hasSameAVLLatticeValue(Other);
355 }
356
357 void setVTYPE(unsigned VType) {
358 assert(isValid() && !isUnknown() &&
359 "Can't set VTYPE for uninitialized or unknown");
360 VLMul = RISCVVType::getVLMUL(VType);
361 SEW = RISCVVType::getSEW(VType);
362 TailAgnostic = RISCVVType::isTailAgnostic(VType);
363 MaskAgnostic = RISCVVType::isMaskAgnostic(VType);
364 AltFmt = RISCVVType::isAltFmt(VType);
365 TWiden =
366 RISCVVType::hasXSfmmWiden(VType) ? RISCVVType::getXSfmmWiden(VType) : 0;
367 }
368 void setVTYPE(RISCVVType::VLMUL L, unsigned S, bool TA, bool MA, bool Altfmt,
369 unsigned W) {
370 assert(isValid() && !isUnknown() &&
371 "Can't set VTYPE for uninitialized or unknown");
372 VLMul = L;
373 SEW = S;
374 TailAgnostic = TA;
375 MaskAgnostic = MA;
376 AltFmt = Altfmt;
377 TWiden = W;
378 }
379
380 void setAltFmt(bool AF) { AltFmt = AF; }
381
382 void setVLMul(RISCVVType::VLMUL VLMul) { this->VLMul = VLMul; }
383
384 unsigned encodeVTYPE() const {
385 assert(isValid() && !isUnknown() && !SEWLMULRatioOnly &&
386 "Can't encode VTYPE for uninitialized or unknown");
387 if (TWiden != 0)
388 return RISCVVType::encodeXSfmmVType(SEW, Widen: TWiden, AltFmt);
389 return RISCVVType::encodeVTYPE(VLMUL: VLMul, SEW, TailAgnostic, MaskAgnostic,
390 AltFmt);
391 }
392
393 bool hasSameVTYPE(const VSETVLIInfo &Other) const {
394 assert(isValid() && Other.isValid() &&
395 "Can't compare invalid VSETVLIInfos");
396 assert(!isUnknown() && !Other.isUnknown() &&
397 "Can't compare VTYPE in unknown state");
398 assert(!SEWLMULRatioOnly && !Other.SEWLMULRatioOnly &&
399 "Can't compare when only LMUL/SEW ratio is valid.");
400 return std::tie(args: VLMul, args: SEW, args: TailAgnostic, args: MaskAgnostic, args: AltFmt, args: TWiden) ==
401 std::tie(args: Other.VLMul, args: Other.SEW, args: Other.TailAgnostic,
402 args: Other.MaskAgnostic, args: Other.AltFmt, args: Other.TWiden);
403 }
404
405 unsigned getSEWLMULRatio() const {
406 assert(isValid() && !isUnknown() &&
407 "Can't use VTYPE for uninitialized or unknown");
408 return RISCVVType::getSEWLMULRatio(SEW, VLMul);
409 }
410
411 // Check if the VTYPE for these two VSETVLIInfos produce the same VLMAX.
412 // Note that having the same VLMAX ensures that both share the same
413 // function from AVL to VL; that is, they must produce the same VL value
414 // for any given AVL value.
415 bool hasSameVLMAX(const VSETVLIInfo &Other) const {
416 assert(isValid() && Other.isValid() &&
417 "Can't compare invalid VSETVLIInfos");
418 assert(!isUnknown() && !Other.isUnknown() &&
419 "Can't compare VTYPE in unknown state");
420 return getSEWLMULRatio() == Other.getSEWLMULRatio();
421 }
422
423 bool hasCompatibleVTYPE(const DemandedFields &Used,
424 const VSETVLIInfo &Require) const;
425
426 // Determine whether the vector instructions requirements represented by
427 // Require are compatible with the previous vsetvli instruction represented
428 // by this. MI is the instruction whose requirements we're considering.
429 bool isCompatible(const DemandedFields &Used, const VSETVLIInfo &Require,
430 const LiveIntervals *LIS) const {
431 assert(isValid() && Require.isValid() &&
432 "Can't compare invalid VSETVLIInfos");
433 // Nothing is compatible with Unknown.
434 if (isUnknown() || Require.isUnknown())
435 return false;
436
437 // If only our VLMAX ratio is valid, then this isn't compatible.
438 if (SEWLMULRatioOnly || Require.SEWLMULRatioOnly)
439 return false;
440
441 if (Used.VLAny && !(hasSameAVL(Other: Require) && hasSameVLMAX(Other: Require)))
442 return false;
443
444 if (Used.VLZeroness && !hasEquallyZeroAVL(Other: Require, LIS))
445 return false;
446
447 return hasCompatibleVTYPE(Used, Require);
448 }
449
450 bool operator==(const VSETVLIInfo &Other) const {
451 // Uninitialized is only equal to another Uninitialized.
452 if (!isValid())
453 return !Other.isValid();
454 if (!Other.isValid())
455 return !isValid();
456
457 // Unknown is only equal to another Unknown.
458 if (isUnknown())
459 return Other.isUnknown();
460 if (Other.isUnknown())
461 return isUnknown();
462
463 if (!hasSameAVLLatticeValue(Other))
464 return false;
465
466 // If the SEWLMULRatioOnly bits are different, then they aren't equal.
467 if (SEWLMULRatioOnly != Other.SEWLMULRatioOnly)
468 return false;
469
470 // If only the VLMAX is valid, check that it is the same.
471 if (SEWLMULRatioOnly)
472 return hasSameVLMAX(Other);
473
474 // If the full VTYPE is valid, check that it is the same.
475 return hasSameVTYPE(Other);
476 }
477
478 bool operator!=(const VSETVLIInfo &Other) const { return !(*this == Other); }
479
480 // Calculate the VSETVLIInfo visible to a block assuming this and Other are
481 // both predecessors.
482 VSETVLIInfo intersect(const VSETVLIInfo &Other) const {
483 // If the new value isn't valid, ignore it.
484 if (!Other.isValid())
485 return *this;
486
487 // If this value isn't valid, this must be the first predecessor, use it.
488 if (!isValid())
489 return Other;
490
491 // If either is unknown, the result is unknown.
492 if (isUnknown() || Other.isUnknown())
493 return VSETVLIInfo::getUnknown();
494
495 // If we have an exact, match return this.
496 if (*this == Other)
497 return *this;
498
499 // Not an exact match, but maybe the AVL and VLMAX are the same. If so,
500 // return an SEW/LMUL ratio only value.
501 if (hasSameAVL(Other) && hasSameVLMAX(Other)) {
502 VSETVLIInfo MergeInfo = *this;
503 MergeInfo.SEWLMULRatioOnly = true;
504 return MergeInfo;
505 }
506
507 // Otherwise the result is unknown.
508 return VSETVLIInfo::getUnknown();
509 }
510
511#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
512 /// Support for debugging, callable in GDB: V->dump()
513 LLVM_DUMP_METHOD void dump() const {
514 print(dbgs());
515 dbgs() << "\n";
516 }
517
518 /// Implement operator<<.
519 /// @{
520 void print(raw_ostream &OS) const {
521 OS << '{';
522 switch (State) {
523 case AVLState::Uninitialized:
524 OS << "Uninitialized";
525 break;
526 case AVLState::Unknown:
527 OS << "unknown";
528 break;
529 case AVLState::AVLIsReg:
530 OS << "AVLReg=" << llvm::printReg(getAVLReg());
531 break;
532 case AVLState::AVLIsImm:
533 OS << "AVLImm=" << (unsigned)AVLImm;
534 break;
535 case AVLState::AVLIsVLMAX:
536 OS << "AVLVLMAX";
537 break;
538 }
539 if (isValid() && !isUnknown()) {
540 OS << ", ";
541
542 unsigned LMul;
543 bool Fractional;
544 std::tie(LMul, Fractional) = decodeVLMUL(VLMul);
545
546 OS << "VLMul=m";
547 if (Fractional)
548 OS << 'f';
549 OS << LMul << ", "
550 << "SEW=e" << (unsigned)SEW << ", "
551 << "TailAgnostic=" << (bool)TailAgnostic << ", "
552 << "MaskAgnostic=" << (bool)MaskAgnostic << ", "
553 << "SEWLMULRatioOnly=" << (bool)SEWLMULRatioOnly << ", "
554 << "TWiden=" << (unsigned)TWiden << ", "
555 << "AltFmt=" << (bool)AltFmt;
556 }
557
558 OS << '}';
559 }
560#endif
561};
562
563#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
564LLVM_ATTRIBUTE_USED
565inline raw_ostream &operator<<(raw_ostream &OS, const VSETVLIInfo &V) {
566 V.print(OS);
567 return OS;
568}
569#endif
570
571class RISCVVSETVLIInfoAnalysis {
572 const RISCVSubtarget *ST;
573 // Possibly null!
574 LiveIntervals *LIS;
575
576public:
577 RISCVVSETVLIInfoAnalysis() = default;
578 RISCVVSETVLIInfoAnalysis(const RISCVSubtarget *ST, LiveIntervals *LIS)
579 : ST(ST), LIS(LIS) {}
580
581 VSETVLIInfo getInfoForVSETVLI(const MachineInstr &MI) const;
582 VSETVLIInfo computeInfoForInstr(const MachineInstr &MI) const;
583
584private:
585 void forwardVSETVLIAVL(VSETVLIInfo &Info) const;
586};
587
588} // namespace RISCV
589} // namespace llvm
590