xref: /freebsd/contrib/llvm-project/llvm/lib/Target/RISCV/RISCVInsertVSETVLI.cpp (revision e9e8876a4d6afc1ad5315faaa191b25121a813d7)
1 //===- RISCVInsertVSETVLI.cpp - Insert VSETVLI instructions ---------------===//
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 a function pass that inserts VSETVLI instructions where
10 // needed.
11 //
12 // This pass consists of 3 phases:
13 //
14 // Phase 1 collects how each basic block affects VL/VTYPE.
15 //
16 // Phase 2 uses the information from phase 1 to do a data flow analysis to
17 // propagate the VL/VTYPE changes through the function. This gives us the
18 // VL/VTYPE at the start of each basic block.
19 //
20 // Phase 3 inserts VSETVLI instructions in each basic block. Information from
21 // phase 2 is used to prevent inserting a VSETVLI before the first vector
22 // instruction in the block if possible.
23 //
24 //===----------------------------------------------------------------------===//
25 
26 #include "RISCV.h"
27 #include "RISCVSubtarget.h"
28 #include "llvm/CodeGen/LiveIntervals.h"
29 #include "llvm/CodeGen/MachineFunctionPass.h"
30 #include <queue>
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "riscv-insert-vsetvli"
34 #define RISCV_INSERT_VSETVLI_NAME "RISCV Insert VSETVLI pass"
35 
36 static cl::opt<bool> DisableInsertVSETVLPHIOpt(
37     "riscv-disable-insert-vsetvl-phi-opt", cl::init(false), cl::Hidden,
38     cl::desc("Disable looking through phis when inserting vsetvlis."));
39 
40 namespace {
41 
42 class VSETVLIInfo {
43   union {
44     Register AVLReg;
45     unsigned AVLImm;
46   };
47 
48   enum : uint8_t {
49     Uninitialized,
50     AVLIsReg,
51     AVLIsImm,
52     Unknown,
53   } State = Uninitialized;
54 
55   // Fields from VTYPE.
56   RISCVII::VLMUL VLMul = RISCVII::LMUL_1;
57   uint8_t SEW = 0;
58   uint8_t TailAgnostic : 1;
59   uint8_t MaskAgnostic : 1;
60   uint8_t MaskRegOp : 1;
61   uint8_t SEWLMULRatioOnly : 1;
62 
63 public:
64   VSETVLIInfo()
65       : AVLImm(0), TailAgnostic(false), MaskAgnostic(false), MaskRegOp(false),
66         SEWLMULRatioOnly(false) {}
67 
68   static VSETVLIInfo getUnknown() {
69     VSETVLIInfo Info;
70     Info.setUnknown();
71     return Info;
72   }
73 
74   bool isValid() const { return State != Uninitialized; }
75   void setUnknown() { State = Unknown; }
76   bool isUnknown() const { return State == Unknown; }
77 
78   void setAVLReg(Register Reg) {
79     AVLReg = Reg;
80     State = AVLIsReg;
81   }
82 
83   void setAVLImm(unsigned Imm) {
84     AVLImm = Imm;
85     State = AVLIsImm;
86   }
87 
88   bool hasAVLImm() const { return State == AVLIsImm; }
89   bool hasAVLReg() const { return State == AVLIsReg; }
90   Register getAVLReg() const {
91     assert(hasAVLReg());
92     return AVLReg;
93   }
94   unsigned getAVLImm() const {
95     assert(hasAVLImm());
96     return AVLImm;
97   }
98 
99   bool hasSameAVL(const VSETVLIInfo &Other) const {
100     assert(isValid() && Other.isValid() &&
101            "Can't compare invalid VSETVLIInfos");
102     assert(!isUnknown() && !Other.isUnknown() &&
103            "Can't compare AVL in unknown state");
104     if (hasAVLReg() && Other.hasAVLReg())
105       return getAVLReg() == Other.getAVLReg();
106 
107     if (hasAVLImm() && Other.hasAVLImm())
108       return getAVLImm() == Other.getAVLImm();
109 
110     return false;
111   }
112 
113   void setVTYPE(unsigned VType) {
114     assert(isValid() && !isUnknown() &&
115            "Can't set VTYPE for uninitialized or unknown");
116     VLMul = RISCVVType::getVLMUL(VType);
117     SEW = RISCVVType::getSEW(VType);
118     TailAgnostic = RISCVVType::isTailAgnostic(VType);
119     MaskAgnostic = RISCVVType::isMaskAgnostic(VType);
120   }
121   void setVTYPE(RISCVII::VLMUL L, unsigned S, bool TA, bool MA, bool MRO) {
122     assert(isValid() && !isUnknown() &&
123            "Can't set VTYPE for uninitialized or unknown");
124     VLMul = L;
125     SEW = S;
126     TailAgnostic = TA;
127     MaskAgnostic = MA;
128     MaskRegOp = MRO;
129   }
130 
131   unsigned encodeVTYPE() const {
132     assert(isValid() && !isUnknown() && !SEWLMULRatioOnly &&
133            "Can't encode VTYPE for uninitialized or unknown");
134     return RISCVVType::encodeVTYPE(VLMul, SEW, TailAgnostic, MaskAgnostic);
135   }
136 
137   bool hasSEWLMULRatioOnly() const { return SEWLMULRatioOnly; }
138 
139   bool hasSameVTYPE(const VSETVLIInfo &Other) const {
140     assert(isValid() && Other.isValid() &&
141            "Can't compare invalid VSETVLIInfos");
142     assert(!isUnknown() && !Other.isUnknown() &&
143            "Can't compare VTYPE in unknown state");
144     assert(!SEWLMULRatioOnly && !Other.SEWLMULRatioOnly &&
145            "Can't compare when only LMUL/SEW ratio is valid.");
146     return std::tie(VLMul, SEW, TailAgnostic, MaskAgnostic) ==
147            std::tie(Other.VLMul, Other.SEW, Other.TailAgnostic,
148                     Other.MaskAgnostic);
149   }
150 
151   // Convert VLMUL to a fixed point value with 3 bits of fraction.
152   unsigned getSEWLMULRatio() const {
153     assert(isValid() && !isUnknown() &&
154            "Can't use VTYPE for uninitialized or unknown");
155     unsigned LMul;
156     bool Fractional;
157     std::tie(LMul, Fractional) = RISCVVType::decodeVLMUL(VLMul);
158 
159     // Convert LMul to a fixed point value with 3 fractional bits.
160     LMul = Fractional ? (8 / LMul) : (LMul * 8);
161 
162     assert(SEW >= 8 && "Unexpected SEW value");
163     return (SEW * 8) / LMul;
164   }
165 
166   // Check if the VTYPE for these two VSETVLIInfos produce the same VLMAX.
167   bool hasSameVLMAX(const VSETVLIInfo &Other) const {
168     assert(isValid() && Other.isValid() &&
169            "Can't compare invalid VSETVLIInfos");
170     assert(!isUnknown() && !Other.isUnknown() &&
171            "Can't compare VTYPE in unknown state");
172     return getSEWLMULRatio() == Other.getSEWLMULRatio();
173   }
174 
175   // Determine whether the vector instructions requirements represented by
176   // InstrInfo are compatible with the previous vsetvli instruction represented
177   // by this.
178   bool isCompatible(const VSETVLIInfo &InstrInfo) const {
179     assert(isValid() && InstrInfo.isValid() &&
180            "Can't compare invalid VSETVLIInfos");
181     assert(!InstrInfo.SEWLMULRatioOnly &&
182            "Expected a valid VTYPE for instruction!");
183     // Nothing is compatible with Unknown.
184     if (isUnknown() || InstrInfo.isUnknown())
185       return false;
186 
187     // If only our VLMAX ratio is valid, then this isn't compatible.
188     if (SEWLMULRatioOnly)
189       return false;
190 
191     // If the instruction doesn't need an AVLReg and the SEW matches, consider
192     // it compatible.
193     if (InstrInfo.hasAVLReg() && InstrInfo.AVLReg == RISCV::NoRegister) {
194       if (SEW == InstrInfo.SEW)
195         return true;
196     }
197 
198     // VTypes must match unless the instruction is a mask reg operation, then it
199     // only care about VLMAX.
200     // FIXME: Mask reg operations are probably ok if "this" VLMAX is larger
201     // than "InstrInfo".
202     if (!hasSameVTYPE(InstrInfo) &&
203         !(InstrInfo.MaskRegOp && hasSameVLMAX(InstrInfo) &&
204           TailAgnostic == InstrInfo.TailAgnostic &&
205           MaskAgnostic == InstrInfo.MaskAgnostic))
206       return false;
207 
208     return hasSameAVL(InstrInfo);
209   }
210 
211   bool operator==(const VSETVLIInfo &Other) const {
212     // Uninitialized is only equal to another Uninitialized.
213     if (!isValid())
214       return !Other.isValid();
215     if (!Other.isValid())
216       return !isValid();
217 
218     // Unknown is only equal to another Unknown.
219     if (isUnknown())
220       return Other.isUnknown();
221     if (Other.isUnknown())
222       return isUnknown();
223 
224     if (!hasSameAVL(Other))
225       return false;
226 
227     // If only the VLMAX is valid, check that it is the same.
228     if (SEWLMULRatioOnly && Other.SEWLMULRatioOnly)
229       return hasSameVLMAX(Other);
230 
231     // If the full VTYPE is valid, check that it is the same.
232     if (!SEWLMULRatioOnly && !Other.SEWLMULRatioOnly)
233       return hasSameVTYPE(Other);
234 
235     // If the SEWLMULRatioOnly bits are different, then they aren't equal.
236     return false;
237   }
238 
239   // Calculate the VSETVLIInfo visible to a block assuming this and Other are
240   // both predecessors.
241   VSETVLIInfo intersect(const VSETVLIInfo &Other) const {
242     // If the new value isn't valid, ignore it.
243     if (!Other.isValid())
244       return *this;
245 
246     // If this value isn't valid, this must be the first predecessor, use it.
247     if (!isValid())
248       return Other;
249 
250     // If either is unknown, the result is unknown.
251     if (isUnknown() || Other.isUnknown())
252       return VSETVLIInfo::getUnknown();
253 
254     // If we have an exact, match return this.
255     if (*this == Other)
256       return *this;
257 
258     // Not an exact match, but maybe the AVL and VLMAX are the same. If so,
259     // return an SEW/LMUL ratio only value.
260     if (hasSameAVL(Other) && hasSameVLMAX(Other)) {
261       VSETVLIInfo MergeInfo = *this;
262       MergeInfo.SEWLMULRatioOnly = true;
263       return MergeInfo;
264     }
265 
266     // Otherwise the result is unknown.
267     return VSETVLIInfo::getUnknown();
268   }
269 
270   // Calculate the VSETVLIInfo visible at the end of the block assuming this
271   // is the predecessor value, and Other is change for this block.
272   VSETVLIInfo merge(const VSETVLIInfo &Other) const {
273     assert(isValid() && "Can only merge with a valid VSETVLInfo");
274 
275     // Nothing changed from the predecessor, keep it.
276     if (!Other.isValid())
277       return *this;
278 
279     // If the change is compatible with the input, we won't create a VSETVLI
280     // and should keep the predecessor.
281     if (isCompatible(Other))
282       return *this;
283 
284     // Otherwise just use whatever is in this block.
285     return Other;
286   }
287 };
288 
289 struct BlockData {
290   // The VSETVLIInfo that represents the net changes to the VL/VTYPE registers
291   // made by this block. Calculated in Phase 1.
292   VSETVLIInfo Change;
293 
294   // The VSETVLIInfo that represents the VL/VTYPE settings on exit from this
295   // block. Calculated in Phase 2.
296   VSETVLIInfo Exit;
297 
298   // The VSETVLIInfo that represents the VL/VTYPE settings from all predecessor
299   // blocks. Calculated in Phase 2, and used by Phase 3.
300   VSETVLIInfo Pred;
301 
302   // Keeps track of whether the block is already in the queue.
303   bool InQueue = false;
304 
305   BlockData() {}
306 };
307 
308 class RISCVInsertVSETVLI : public MachineFunctionPass {
309   const TargetInstrInfo *TII;
310   MachineRegisterInfo *MRI;
311 
312   std::vector<BlockData> BlockInfo;
313   std::queue<const MachineBasicBlock *> WorkList;
314 
315 public:
316   static char ID;
317 
318   RISCVInsertVSETVLI() : MachineFunctionPass(ID) {
319     initializeRISCVInsertVSETVLIPass(*PassRegistry::getPassRegistry());
320   }
321   bool runOnMachineFunction(MachineFunction &MF) override;
322 
323   void getAnalysisUsage(AnalysisUsage &AU) const override {
324     AU.setPreservesCFG();
325     MachineFunctionPass::getAnalysisUsage(AU);
326   }
327 
328   StringRef getPassName() const override { return RISCV_INSERT_VSETVLI_NAME; }
329 
330 private:
331   bool needVSETVLI(const VSETVLIInfo &Require, const VSETVLIInfo &CurInfo);
332   bool needVSETVLIPHI(const VSETVLIInfo &Require, const MachineBasicBlock &MBB);
333   void insertVSETVLI(MachineBasicBlock &MBB, MachineInstr &MI,
334                      const VSETVLIInfo &Info, const VSETVLIInfo &PrevInfo);
335 
336   bool computeVLVTYPEChanges(const MachineBasicBlock &MBB);
337   void computeIncomingVLVTYPE(const MachineBasicBlock &MBB);
338   void emitVSETVLIs(MachineBasicBlock &MBB);
339 };
340 
341 } // end anonymous namespace
342 
343 char RISCVInsertVSETVLI::ID = 0;
344 
345 INITIALIZE_PASS(RISCVInsertVSETVLI, DEBUG_TYPE, RISCV_INSERT_VSETVLI_NAME,
346                 false, false)
347 
348 static MachineInstr *elideCopies(MachineInstr *MI,
349                                  const MachineRegisterInfo *MRI) {
350   while (true) {
351     if (!MI->isFullCopy())
352       return MI;
353     if (!Register::isVirtualRegister(MI->getOperand(1).getReg()))
354       return nullptr;
355     MI = MRI->getVRegDef(MI->getOperand(1).getReg());
356     if (!MI)
357       return nullptr;
358   }
359 }
360 
361 static VSETVLIInfo computeInfoForInstr(const MachineInstr &MI, uint64_t TSFlags,
362                                        const MachineRegisterInfo *MRI) {
363   VSETVLIInfo InstrInfo;
364   unsigned NumOperands = MI.getNumExplicitOperands();
365 
366   RISCVII::VLMUL VLMul = RISCVII::getLMul(TSFlags);
367 
368   unsigned Log2SEW = MI.getOperand(NumOperands - 1).getImm();
369   // A Log2SEW of 0 is an operation on mask registers only.
370   bool MaskRegOp = Log2SEW == 0;
371   unsigned SEW = Log2SEW ? 1 << Log2SEW : 8;
372   assert(RISCVVType::isValidSEW(SEW) && "Unexpected SEW");
373 
374   // Default to tail agnostic unless the destination is tied to a source.
375   // Unless the source is undef. In that case the user would have some control
376   // over the tail values. Some pseudo instructions force a tail agnostic policy
377   // despite having a tied def.
378   bool ForceTailAgnostic = RISCVII::doesForceTailAgnostic(TSFlags);
379   bool TailAgnostic = true;
380   unsigned UseOpIdx;
381   if (!ForceTailAgnostic && MI.isRegTiedToUseOperand(0, &UseOpIdx)) {
382     TailAgnostic = false;
383     // If the tied operand is an IMPLICIT_DEF we can keep TailAgnostic.
384     const MachineOperand &UseMO = MI.getOperand(UseOpIdx);
385     MachineInstr *UseMI = MRI->getVRegDef(UseMO.getReg());
386     if (UseMI) {
387       UseMI = elideCopies(UseMI, MRI);
388       if (UseMI && UseMI->isImplicitDef())
389         TailAgnostic = true;
390     }
391   }
392 
393   if (RISCVII::hasVLOp(TSFlags)) {
394     const MachineOperand &VLOp = MI.getOperand(MI.getNumExplicitOperands() - 2);
395     if (VLOp.isImm())
396       InstrInfo.setAVLImm(VLOp.getImm());
397     else
398       InstrInfo.setAVLReg(VLOp.getReg());
399   } else
400     InstrInfo.setAVLReg(RISCV::NoRegister);
401   InstrInfo.setVTYPE(VLMul, SEW, /*TailAgnostic*/ TailAgnostic,
402                      /*MaskAgnostic*/ false, MaskRegOp);
403 
404   return InstrInfo;
405 }
406 
407 void RISCVInsertVSETVLI::insertVSETVLI(MachineBasicBlock &MBB, MachineInstr &MI,
408                                        const VSETVLIInfo &Info,
409                                        const VSETVLIInfo &PrevInfo) {
410   DebugLoc DL = MI.getDebugLoc();
411 
412   // Use X0, X0 form if the AVL is the same and the SEW+LMUL gives the same
413   // VLMAX.
414   if (PrevInfo.isValid() && !PrevInfo.isUnknown() &&
415       Info.hasSameAVL(PrevInfo) && Info.hasSameVLMAX(PrevInfo)) {
416     BuildMI(MBB, MI, DL, TII->get(RISCV::PseudoVSETVLI))
417         .addReg(RISCV::X0, RegState::Define | RegState::Dead)
418         .addReg(RISCV::X0, RegState::Kill)
419         .addImm(Info.encodeVTYPE())
420         .addReg(RISCV::VL, RegState::Implicit);
421     return;
422   }
423 
424   if (Info.hasAVLImm()) {
425     BuildMI(MBB, MI, DL, TII->get(RISCV::PseudoVSETIVLI))
426         .addReg(RISCV::X0, RegState::Define | RegState::Dead)
427         .addImm(Info.getAVLImm())
428         .addImm(Info.encodeVTYPE());
429     return;
430   }
431 
432   Register AVLReg = Info.getAVLReg();
433   if (AVLReg == RISCV::NoRegister) {
434     // We can only use x0, x0 if there's no chance of the vtype change causing
435     // the previous vl to become invalid.
436     if (PrevInfo.isValid() && !PrevInfo.isUnknown() &&
437         Info.hasSameVLMAX(PrevInfo)) {
438       BuildMI(MBB, MI, DL, TII->get(RISCV::PseudoVSETVLI))
439           .addReg(RISCV::X0, RegState::Define | RegState::Dead)
440           .addReg(RISCV::X0, RegState::Kill)
441           .addImm(Info.encodeVTYPE())
442           .addReg(RISCV::VL, RegState::Implicit);
443       return;
444     }
445     // Otherwise use an AVL of 0 to avoid depending on previous vl.
446     BuildMI(MBB, MI, DL, TII->get(RISCV::PseudoVSETIVLI))
447         .addReg(RISCV::X0, RegState::Define | RegState::Dead)
448         .addImm(0)
449         .addImm(Info.encodeVTYPE());
450     return;
451   }
452 
453   // Use X0 as the DestReg unless AVLReg is X0.
454   Register DestReg = RISCV::X0;
455   if (AVLReg == RISCV::X0)
456     DestReg = MRI->createVirtualRegister(&RISCV::GPRRegClass);
457   BuildMI(MBB, MI, DL, TII->get(RISCV::PseudoVSETVLI))
458       .addReg(DestReg, RegState::Define | RegState::Dead)
459       .addReg(AVLReg)
460       .addImm(Info.encodeVTYPE());
461 }
462 
463 // Return a VSETVLIInfo representing the changes made by this VSETVLI or
464 // VSETIVLI instruction.
465 static VSETVLIInfo getInfoForVSETVLI(const MachineInstr &MI) {
466   VSETVLIInfo NewInfo;
467   if (MI.getOpcode() == RISCV::PseudoVSETVLI) {
468     Register AVLReg = MI.getOperand(1).getReg();
469     assert((AVLReg != RISCV::X0 || MI.getOperand(0).getReg() != RISCV::X0) &&
470            "Can't handle X0, X0 vsetvli yet");
471     NewInfo.setAVLReg(AVLReg);
472   } else {
473     assert(MI.getOpcode() == RISCV::PseudoVSETIVLI);
474     NewInfo.setAVLImm(MI.getOperand(1).getImm());
475   }
476   NewInfo.setVTYPE(MI.getOperand(2).getImm());
477 
478   return NewInfo;
479 }
480 
481 bool RISCVInsertVSETVLI::needVSETVLI(const VSETVLIInfo &Require,
482                                      const VSETVLIInfo &CurInfo) {
483   if (CurInfo.isCompatible(Require))
484     return false;
485 
486   // We didn't find a compatible value. If our AVL is a virtual register,
487   // it might be defined by a VSET(I)VLI. If it has the same VTYPE we need
488   // and the last VL/VTYPE we observed is the same, we don't need a
489   // VSETVLI here.
490   if (!CurInfo.isUnknown() && Require.hasAVLReg() &&
491       Require.getAVLReg().isVirtual() && !CurInfo.hasSEWLMULRatioOnly() &&
492       Require.hasSameVTYPE(CurInfo)) {
493     if (MachineInstr *DefMI = MRI->getVRegDef(Require.getAVLReg())) {
494       if (DefMI->getOpcode() == RISCV::PseudoVSETVLI ||
495           DefMI->getOpcode() == RISCV::PseudoVSETIVLI) {
496         VSETVLIInfo DefInfo = getInfoForVSETVLI(*DefMI);
497         if (DefInfo.hasSameAVL(CurInfo) && DefInfo.hasSameVTYPE(CurInfo))
498           return false;
499       }
500     }
501   }
502 
503   return true;
504 }
505 
506 bool RISCVInsertVSETVLI::computeVLVTYPEChanges(const MachineBasicBlock &MBB) {
507   bool HadVectorOp = false;
508 
509   BlockData &BBInfo = BlockInfo[MBB.getNumber()];
510   for (const MachineInstr &MI : MBB) {
511     // If this is an explicit VSETVLI or VSETIVLI, update our state.
512     if (MI.getOpcode() == RISCV::PseudoVSETVLI ||
513         MI.getOpcode() == RISCV::PseudoVSETIVLI) {
514       HadVectorOp = true;
515       BBInfo.Change = getInfoForVSETVLI(MI);
516       continue;
517     }
518 
519     uint64_t TSFlags = MI.getDesc().TSFlags;
520     if (RISCVII::hasSEWOp(TSFlags)) {
521       HadVectorOp = true;
522 
523       VSETVLIInfo NewInfo = computeInfoForInstr(MI, TSFlags, MRI);
524 
525       if (!BBInfo.Change.isValid()) {
526         BBInfo.Change = NewInfo;
527       } else {
528         // If this instruction isn't compatible with the previous VL/VTYPE
529         // we need to insert a VSETVLI.
530         if (needVSETVLI(NewInfo, BBInfo.Change))
531           BBInfo.Change = NewInfo;
532       }
533     }
534 
535     // If this is something that updates VL/VTYPE that we don't know about, set
536     // the state to unknown.
537     if (MI.isCall() || MI.isInlineAsm() || MI.modifiesRegister(RISCV::VL) ||
538         MI.modifiesRegister(RISCV::VTYPE)) {
539       BBInfo.Change = VSETVLIInfo::getUnknown();
540     }
541   }
542 
543   // Initial exit state is whatever change we found in the block.
544   BBInfo.Exit = BBInfo.Change;
545 
546   return HadVectorOp;
547 }
548 
549 void RISCVInsertVSETVLI::computeIncomingVLVTYPE(const MachineBasicBlock &MBB) {
550   BlockData &BBInfo = BlockInfo[MBB.getNumber()];
551 
552   BBInfo.InQueue = false;
553 
554   VSETVLIInfo InInfo;
555   if (MBB.pred_empty()) {
556     // There are no predecessors, so use the default starting status.
557     InInfo.setUnknown();
558   } else {
559     for (MachineBasicBlock *P : MBB.predecessors())
560       InInfo = InInfo.intersect(BlockInfo[P->getNumber()].Exit);
561   }
562 
563   // If we don't have any valid predecessor value, wait until we do.
564   if (!InInfo.isValid())
565     return;
566 
567   BBInfo.Pred = InInfo;
568 
569   VSETVLIInfo TmpStatus = BBInfo.Pred.merge(BBInfo.Change);
570 
571   // If the new exit value matches the old exit value, we don't need to revisit
572   // any blocks.
573   if (BBInfo.Exit == TmpStatus)
574     return;
575 
576   BBInfo.Exit = TmpStatus;
577 
578   // Add the successors to the work list so we can propagate the changed exit
579   // status.
580   for (MachineBasicBlock *S : MBB.successors())
581     if (!BlockInfo[S->getNumber()].InQueue)
582       WorkList.push(S);
583 }
584 
585 // If we weren't able to prove a vsetvli was directly unneeded, it might still
586 // be/ unneeded if the AVL is a phi node where all incoming values are VL
587 // outputs from the last VSETVLI in their respective basic blocks.
588 bool RISCVInsertVSETVLI::needVSETVLIPHI(const VSETVLIInfo &Require,
589                                         const MachineBasicBlock &MBB) {
590   if (DisableInsertVSETVLPHIOpt)
591     return true;
592 
593   if (!Require.hasAVLReg())
594     return true;
595 
596   Register AVLReg = Require.getAVLReg();
597   if (!AVLReg.isVirtual())
598     return true;
599 
600   // We need the AVL to be produce by a PHI node in this basic block.
601   MachineInstr *PHI = MRI->getVRegDef(AVLReg);
602   if (!PHI || PHI->getOpcode() != RISCV::PHI || PHI->getParent() != &MBB)
603     return true;
604 
605   for (unsigned PHIOp = 1, NumOps = PHI->getNumOperands(); PHIOp != NumOps;
606        PHIOp += 2) {
607     Register InReg = PHI->getOperand(PHIOp).getReg();
608     MachineBasicBlock *PBB = PHI->getOperand(PHIOp + 1).getMBB();
609     const BlockData &PBBInfo = BlockInfo[PBB->getNumber()];
610     // If the exit from the predecessor has the VTYPE we are looking for
611     // we might be able to avoid a VSETVLI.
612     if (PBBInfo.Exit.isUnknown() || !PBBInfo.Exit.hasSameVTYPE(Require))
613       return true;
614 
615     // We need the PHI input to the be the output of a VSET(I)VLI.
616     MachineInstr *DefMI = MRI->getVRegDef(InReg);
617     if (!DefMI || (DefMI->getOpcode() != RISCV::PseudoVSETVLI &&
618                    DefMI->getOpcode() != RISCV::PseudoVSETIVLI))
619       return true;
620 
621     // We found a VSET(I)VLI make sure it matches the output of the
622     // predecessor block.
623     VSETVLIInfo DefInfo = getInfoForVSETVLI(*DefMI);
624     if (!DefInfo.hasSameAVL(PBBInfo.Exit) ||
625         !DefInfo.hasSameVTYPE(PBBInfo.Exit))
626       return true;
627   }
628 
629   // If all the incoming values to the PHI checked out, we don't need
630   // to insert a VSETVLI.
631   return false;
632 }
633 
634 void RISCVInsertVSETVLI::emitVSETVLIs(MachineBasicBlock &MBB) {
635   VSETVLIInfo CurInfo;
636 
637   for (MachineInstr &MI : MBB) {
638     // If this is an explicit VSETVLI or VSETIVLI, update our state.
639     if (MI.getOpcode() == RISCV::PseudoVSETVLI ||
640         MI.getOpcode() == RISCV::PseudoVSETIVLI) {
641       // Conservatively, mark the VL and VTYPE as live.
642       assert(MI.getOperand(3).getReg() == RISCV::VL &&
643              MI.getOperand(4).getReg() == RISCV::VTYPE &&
644              "Unexpected operands where VL and VTYPE should be");
645       MI.getOperand(3).setIsDead(false);
646       MI.getOperand(4).setIsDead(false);
647       CurInfo = getInfoForVSETVLI(MI);
648       continue;
649     }
650 
651     uint64_t TSFlags = MI.getDesc().TSFlags;
652     if (RISCVII::hasSEWOp(TSFlags)) {
653       VSETVLIInfo NewInfo = computeInfoForInstr(MI, TSFlags, MRI);
654       if (RISCVII::hasVLOp(TSFlags)) {
655         MachineOperand &VLOp = MI.getOperand(MI.getNumExplicitOperands() - 2);
656         if (VLOp.isReg()) {
657           // Erase the AVL operand from the instruction.
658           VLOp.setReg(RISCV::NoRegister);
659           VLOp.setIsKill(false);
660         }
661         MI.addOperand(MachineOperand::CreateReg(RISCV::VL, /*isDef*/ false,
662                                                 /*isImp*/ true));
663       }
664       MI.addOperand(MachineOperand::CreateReg(RISCV::VTYPE, /*isDef*/ false,
665                                               /*isImp*/ true));
666 
667       if (!CurInfo.isValid()) {
668         // We haven't found any vector instructions or VL/VTYPE changes yet,
669         // use the predecessor information.
670         assert(BlockInfo[MBB.getNumber()].Pred.isValid() &&
671                "Expected a valid predecessor state.");
672         if (needVSETVLI(NewInfo, BlockInfo[MBB.getNumber()].Pred) &&
673             needVSETVLIPHI(NewInfo, MBB)) {
674           insertVSETVLI(MBB, MI, NewInfo, BlockInfo[MBB.getNumber()].Pred);
675           CurInfo = NewInfo;
676         }
677       } else {
678         // If this instruction isn't compatible with the previous VL/VTYPE
679         // we need to insert a VSETVLI.
680         if (needVSETVLI(NewInfo, CurInfo)) {
681           insertVSETVLI(MBB, MI, NewInfo, CurInfo);
682           CurInfo = NewInfo;
683         }
684       }
685     }
686 
687     // If this is something updates VL/VTYPE that we don't know about, set
688     // the state to unknown.
689     if (MI.isCall() || MI.isInlineAsm() || MI.modifiesRegister(RISCV::VL) ||
690         MI.modifiesRegister(RISCV::VTYPE)) {
691       CurInfo = VSETVLIInfo::getUnknown();
692     }
693   }
694 }
695 
696 bool RISCVInsertVSETVLI::runOnMachineFunction(MachineFunction &MF) {
697   // Skip if the vector extension is not enabled.
698   const RISCVSubtarget &ST = MF.getSubtarget<RISCVSubtarget>();
699   if (!ST.hasStdExtV())
700     return false;
701 
702   TII = ST.getInstrInfo();
703   MRI = &MF.getRegInfo();
704 
705   assert(BlockInfo.empty() && "Expect empty block infos");
706   BlockInfo.resize(MF.getNumBlockIDs());
707 
708   bool HaveVectorOp = false;
709 
710   // Phase 1 - determine how VL/VTYPE are affected by the each block.
711   for (const MachineBasicBlock &MBB : MF)
712     HaveVectorOp |= computeVLVTYPEChanges(MBB);
713 
714   // If we didn't find any instructions that need VSETVLI, we're done.
715   if (HaveVectorOp) {
716     // Phase 2 - determine the exit VL/VTYPE from each block. We add all
717     // blocks to the list here, but will also add any that need to be revisited
718     // during Phase 2 processing.
719     for (const MachineBasicBlock &MBB : MF) {
720       WorkList.push(&MBB);
721       BlockInfo[MBB.getNumber()].InQueue = true;
722     }
723     while (!WorkList.empty()) {
724       const MachineBasicBlock &MBB = *WorkList.front();
725       WorkList.pop();
726       computeIncomingVLVTYPE(MBB);
727     }
728 
729     // Phase 3 - add any vsetvli instructions needed in the block. Use the
730     // Phase 2 information to avoid adding vsetvlis before the first vector
731     // instruction in the block if the VL/VTYPE is satisfied by its
732     // predecessors.
733     for (MachineBasicBlock &MBB : MF)
734       emitVSETVLIs(MBB);
735   }
736 
737   BlockInfo.clear();
738 
739   return HaveVectorOp;
740 }
741 
742 /// Returns an instance of the Insert VSETVLI pass.
743 FunctionPass *llvm::createRISCVInsertVSETVLIPass() {
744   return new RISCVInsertVSETVLI();
745 }
746