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 =
73 V0->getContext().getLibraryOptions().get<VectorizeOptions>();
74 // For each user U0 of lane 0, try to form a bundle of matching users across
75 // all lanes. Cap the number of users considered to bound compilation time,
76 // since each one may trigger an O(Bndl.size()) search across the other
77 // lanes' users.
78 for (User *U0 : V0->users()) {
79 if (SeenUsers.size() >= Opts.sbvec_max_users_to_consider)
80 break;
81 if (!SeenUsers.insert(V: U0).second)
82 continue;
83 auto *UI0 = dyn_cast<Instruction>(Val: U0);
84 if (!UI0 || IMaps.isVectorized(Orig: UI0) || Claimed.contains(Ptr: UI0))
85 continue;
86 std::optional<BundleTy> NextUserBndl =
87 getMatchingBundle(Bndl, IMaps, Seed: V0, SeedUserInst: UI0, Claimed);
88 if (NextUserBndl)
89 Bundles.emplace_back(Args: std::move(*NextUserBndl));
90 }
91 return Bundles;
92}
93
94unsigned VecUtils::getFloorPowerOf2(unsigned Num) {
95 if (Num == 0)
96 return Num;
97 unsigned Mask = Num;
98 Mask >>= 1;
99 for (unsigned ShiftBy = 1; ShiftBy < sizeof(Num) * 8; ShiftBy <<= 1)
100 Mask |= Mask >> ShiftBy;
101 return Num & ~Mask;
102}
103
104template <typename T>
105void VecUtils::DeadInstructionMorgue::collectPotentiallyDeadInstrs(
106 BndlRef<T *> Bndl) {
107 for (T *V : Bndl) {
108 assert(isa<Instruction>(V) && "Only works with instructions");
109 DeadInstrCandidates.insert(cast<Instruction>(V));
110 }
111 // Also collect the GEPs of vectorized loads and stores.
112 auto Opcode = cast<Instruction>(Bndl[0])->getOpcode();
113 switch (Opcode) {
114 case Instruction::Opcode::Load: {
115 for (T *V : drop_begin(Bndl))
116 if (auto *Ptr =
117 dyn_cast<Instruction>(cast<LoadInst>(V)->getPointerOperand()))
118 DeadInstrCandidates.insert(Ptr);
119 break;
120 }
121 case Instruction::Opcode::Store: {
122 for (T *V : drop_begin(Bndl))
123 if (auto *Ptr =
124 dyn_cast<Instruction>(cast<StoreInst>(V)->getPointerOperand()))
125 DeadInstrCandidates.insert(Ptr);
126 break;
127 }
128 default:
129 break;
130 }
131}
132
133template void
134 VecUtils::DeadInstructionMorgue::collectPotentiallyDeadInstrs<Value>(
135 BndlRef<Value *>);
136template LLVM_EXPORT_TEMPLATE void
137 VecUtils::DeadInstructionMorgue::collectPotentiallyDeadInstrs<Instruction>(
138 BndlRef<Instruction *>);
139
140void VecUtils::DeadInstructionMorgue::tryEraseDeadInstrs() {
141 DenseMap<BasicBlock *, SmallVector<Instruction *>> SortedDeadInstrCandidates;
142 // The dead instrs could span BBs, so we need to collect and sort them per BB.
143 for (auto *V : DeadInstrCandidates) {
144 auto *DeadI = cast<Instruction>(Val: V);
145 SortedDeadInstrCandidates[DeadI->getParent()].push_back(Elt: DeadI);
146 }
147 for (auto &Pair : SortedDeadInstrCandidates)
148 sort(C&: Pair.second,
149 Comp: [](Instruction *I1, Instruction *I2) { return I1->comesBefore(Other: I2); });
150 for (const auto &Pair : SortedDeadInstrCandidates) {
151 for (Instruction *I : reverse(C: Pair.second)) {
152 if (I->hasNUses(Num: 0)) {
153 // Erase the dead instructions bottom-to-top.
154 LLVM_DEBUG(dbgs() << DEBUG_PREFIX << "Erase dead: " << *I << "\n");
155 I->eraseFromParent();
156 }
157 }
158 }
159 DeadInstrCandidates.clear();
160}
161
162#ifndef NDEBUG
163template <typename T> static void dumpImpl(ArrayRef<T *> Bndl) {
164 for (auto [Idx, V] : enumerate(Bndl))
165 dbgs() << Idx << "." << *V << "\n";
166}
167void VecUtils::dump(ArrayRef<Value *> Bndl) { dumpImpl(Bndl); }
168void VecUtils::dump(ArrayRef<Instruction *> Bndl) { dumpImpl(Bndl); }
169
170template <typename T> void BndlRef<T>::dump() const {
171 print(dbgs());
172 dbgs() << "\n";
173}
174// Explicit instantiation for commonly used types.
175template class BndlRef<Instruction *>;
176template class BndlRef<Value *>;
177
178#endif // NDEBUG
179
180} // namespace llvm::sandboxir
181