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