1//===- VecUtils.cpp -------------------------------------------------------===//
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#include "llvm/Transforms/Vectorize/SandboxVectorizer/VecUtils.h"
10
11#include "llvm/ADT/DenseMap.h"
12#include "llvm/ADT/Sequence.h"
13#include "llvm/ADT/SmallPtrSet.h"
14#include "llvm/SandboxIR/Instruction.h"
15#include "llvm/Support/CommandLine.h"
16#include "llvm/Transforms/Vectorize/SandboxVectorizer/Debug.h"
17#include "llvm/Transforms/Vectorize/SandboxVectorizer/InstrMaps.h"
18
19namespace llvm::sandboxir {
20
21static cl::opt<unsigned> MaxUsersToConsider(
22 "sbvec-max-users-to-consider", cl::init(Val: 16), cl::Hidden,
23 cl::desc("Limit the number of a seed's users that getNextUserBundles() "
24 "will examine as candidates for a matching bundle, to cap "
25 "compilation time."));
26
27static SmallVector<unsigned, 2> getOperandIndicesInUser(User *U, Value *Op) {
28 SmallVector<unsigned, 2> OpIdxVec;
29 for (unsigned Idx : seq<unsigned>(Size: U->getNumOperands()))
30 if (U->getOperand(OpIdx: Idx) == Op)
31 OpIdxVec.push_back(Elt: Idx);
32 return OpIdxVec;
33}
34
35static std::optional<BundleTy>
36getMatchingBundle(ArrayRef<Value *> Bndl, const InstrMaps &IMaps, Value *Seed,
37 Instruction *SeedUserInst,
38 SmallPtrSet<Instruction *, 4> &Claimed) {
39 SmallVector<unsigned, 2> OpIdxVec0 =
40 getOperandIndicesInUser(U: SeedUserInst, Op: Seed);
41 assert(!OpIdxVec0.empty() && "U0 does not use Seed!");
42 BundleTy NextUserBndl;
43 NextUserBndl.push_back(Elt: SeedUserInst);
44 Claimed.insert(Ptr: SeedUserInst);
45 for (Value *V : drop_begin(RangeOrContainer&: Bndl)) {
46 Instruction *Match = nullptr;
47 for (User *U : V->users()) {
48 auto *UI = dyn_cast<Instruction>(Val: U);
49 if (!UI || IMaps.isVectorized(Orig: UI) || Claimed.contains(Ptr: UI) ||
50 UI->getOpcode() != SeedUserInst->getOpcode() ||
51 UI->getType() != SeedUserInst->getType() ||
52 UI->getParent() != SeedUserInst->getParent() ||
53 getOperandIndicesInUser(U: UI, Op: V) != OpIdxVec0)
54 continue;
55
56 Match = UI;
57 break;
58 }
59 if (!Match)
60 return std::nullopt;
61 NextUserBndl.push_back(Elt: Match);
62 }
63
64 for (auto *I : NextUserBndl)
65 Claimed.insert(Ptr: cast<Instruction>(Val: I));
66 return NextUserBndl;
67}
68
69SmallVector<BundleTy>
70VecUtils::getNextUserBundles(ArrayRef<Value *> Bndl, const InstrMaps &IMaps,
71 SmallPtrSet<Instruction *, 4> &Claimed) {
72 SmallVector<BundleTy> Bundles;
73 if (Bndl.empty())
74 return Bundles;
75
76 Value *V0 = Bndl[0];
77 DenseSet<User *> SeenUsers;
78 // For each user U0 of lane 0, try to form a bundle of matching users across
79 // all lanes. Cap the number of users considered to bound compilation time,
80 // since each one may trigger an O(Bndl.size()) search across the other
81 // lanes' users.
82 for (User *U0 : V0->users()) {
83 if (SeenUsers.size() >= MaxUsersToConsider)
84 break;
85 if (!SeenUsers.insert(V: U0).second)
86 continue;
87 auto *UI0 = dyn_cast<Instruction>(Val: U0);
88 if (!UI0 || IMaps.isVectorized(Orig: UI0) || Claimed.contains(Ptr: UI0))
89 continue;
90 std::optional<BundleTy> NextUserBndl =
91 getMatchingBundle(Bndl, IMaps, Seed: V0, SeedUserInst: UI0, Claimed);
92 if (NextUserBndl)
93 Bundles.emplace_back(Args: std::move(*NextUserBndl));
94 }
95 return Bundles;
96}
97
98unsigned VecUtils::getFloorPowerOf2(unsigned Num) {
99 if (Num == 0)
100 return Num;
101 unsigned Mask = Num;
102 Mask >>= 1;
103 for (unsigned ShiftBy = 1; ShiftBy < sizeof(Num) * 8; ShiftBy <<= 1)
104 Mask |= Mask >> ShiftBy;
105 return Num & ~Mask;
106}
107
108template <typename T>
109void VecUtils::DeadInstructionMorgue::collectPotentiallyDeadInstrs(
110 ArrayRef<T *> Bndl) {
111 for (T *V : Bndl) {
112 assert(isa<Instruction>(V) && "Only works with instructions");
113 DeadInstrCandidates.insert(cast<Instruction>(V));
114 }
115 // Also collect the GEPs of vectorized loads and stores.
116 auto Opcode = cast<Instruction>(Bndl[0])->getOpcode();
117 switch (Opcode) {
118 case Instruction::Opcode::Load: {
119 for (T *V : drop_begin(Bndl))
120 if (auto *Ptr =
121 dyn_cast<Instruction>(cast<LoadInst>(V)->getPointerOperand()))
122 DeadInstrCandidates.insert(Ptr);
123 break;
124 }
125 case Instruction::Opcode::Store: {
126 for (T *V : drop_begin(Bndl))
127 if (auto *Ptr =
128 dyn_cast<Instruction>(cast<StoreInst>(V)->getPointerOperand()))
129 DeadInstrCandidates.insert(Ptr);
130 break;
131 }
132 default:
133 break;
134 }
135}
136
137template void
138 VecUtils::DeadInstructionMorgue::collectPotentiallyDeadInstrs<Value>(
139 ArrayRef<Value *>);
140template void
141 VecUtils::DeadInstructionMorgue::collectPotentiallyDeadInstrs<Instruction>(
142 ArrayRef<Instruction *>);
143
144void VecUtils::DeadInstructionMorgue::tryEraseDeadInstrs() {
145 DenseMap<BasicBlock *, SmallVector<Instruction *>> SortedDeadInstrCandidates;
146 // The dead instrs could span BBs, so we need to collect and sort them per BB.
147 for (auto *V : DeadInstrCandidates) {
148 auto *DeadI = cast<Instruction>(Val: V);
149 SortedDeadInstrCandidates[DeadI->getParent()].push_back(Elt: DeadI);
150 }
151 for (auto &Pair : SortedDeadInstrCandidates)
152 sort(C&: Pair.second,
153 Comp: [](Instruction *I1, Instruction *I2) { return I1->comesBefore(Other: I2); });
154 for (const auto &Pair : SortedDeadInstrCandidates) {
155 for (Instruction *I : reverse(C: Pair.second)) {
156 if (I->hasNUses(Num: 0)) {
157 // Erase the dead instructions bottom-to-top.
158 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Erase dead: " << *I << "\n");
159 I->eraseFromParent();
160 }
161 }
162 }
163 DeadInstrCandidates.clear();
164}
165
166#ifndef NDEBUG
167template <typename T> static void dumpImpl(ArrayRef<T *> Bndl) {
168 for (auto [Idx, V] : enumerate(Bndl))
169 dbgs() << Idx << "." << *V << "\n";
170}
171void VecUtils::dump(ArrayRef<Value *> Bndl) { dumpImpl(Bndl); }
172void VecUtils::dump(ArrayRef<Instruction *> Bndl) { dumpImpl(Bndl); }
173
174template <typename T> void BndlRef<T>::dump() const {
175 print(dbgs());
176 dbgs() << "\n";
177}
178// Explicit instantiation for commonly used types.
179template class BndlRef<Instruction *>;
180template class BndlRef<Value *>;
181
182#endif // NDEBUG
183
184} // namespace llvm::sandboxir
185