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/Sequence.h"
12#include "llvm/ADT/SmallPtrSet.h"
13#include "llvm/SandboxIR/Instruction.h"
14#include "llvm/Support/CommandLine.h"
15#include "llvm/Transforms/Vectorize/SandboxVectorizer/InstrMaps.h"
16
17namespace llvm::sandboxir {
18
19static cl::opt<unsigned> MaxUsersToConsider(
20 "sbvec-max-users-to-consider", cl::init(Val: 16), cl::Hidden,
21 cl::desc("Limit the number of a seed's users that getNextUserBundles() "
22 "will examine as candidates for a matching bundle, to cap "
23 "compilation time."));
24
25static SmallVector<unsigned, 2> getOperandIndicesInUser(User *U, Value *Op) {
26 SmallVector<unsigned, 2> OpIdxVec;
27 for (unsigned Idx : seq<unsigned>(Size: U->getNumOperands()))
28 if (U->getOperand(OpIdx: Idx) == Op)
29 OpIdxVec.push_back(Elt: Idx);
30 return OpIdxVec;
31}
32
33static std::optional<BundleTy>
34getMatchingBundle(ArrayRef<Value *> Bndl, const InstrMaps &IMaps, Value *Seed,
35 Instruction *SeedUserInst,
36 SmallPtrSet<Instruction *, 4> &Claimed) {
37 SmallVector<unsigned, 2> OpIdxVec0 =
38 getOperandIndicesInUser(U: SeedUserInst, Op: Seed);
39 assert(!OpIdxVec0.empty() && "U0 does not use Seed!");
40 BundleTy NextUserBndl;
41 NextUserBndl.push_back(Elt: SeedUserInst);
42 Claimed.insert(Ptr: SeedUserInst);
43 for (Value *V : drop_begin(RangeOrContainer&: Bndl)) {
44 Instruction *Match = nullptr;
45 for (User *U : V->users()) {
46 auto *UI = dyn_cast<Instruction>(Val: U);
47 if (!UI || IMaps.isVectorized(Orig: UI) || Claimed.contains(Ptr: UI) ||
48 UI->getOpcode() != SeedUserInst->getOpcode() ||
49 UI->getType() != SeedUserInst->getType() ||
50 UI->getParent() != SeedUserInst->getParent() ||
51 getOperandIndicesInUser(U: UI, Op: V) != OpIdxVec0)
52 continue;
53
54 Match = UI;
55 break;
56 }
57 if (!Match)
58 return std::nullopt;
59 NextUserBndl.push_back(Elt: Match);
60 }
61
62 for (auto *I : NextUserBndl)
63 Claimed.insert(Ptr: cast<Instruction>(Val: I));
64 return NextUserBndl;
65}
66
67SmallVector<BundleTy>
68VecUtils::getNextUserBundles(ArrayRef<Value *> Bndl, const InstrMaps &IMaps,
69 SmallPtrSet<Instruction *, 4> &Claimed) {
70 SmallVector<BundleTy> Bundles;
71 if (Bndl.empty())
72 return Bundles;
73
74 Value *V0 = Bndl[0];
75 DenseSet<User *> SeenUsers;
76 // For each user U0 of lane 0, try to form a bundle of matching users across
77 // all lanes. Cap the number of users considered to bound compilation time,
78 // since each one may trigger an O(Bndl.size()) search across the other
79 // lanes' users.
80 for (User *U0 : V0->users()) {
81 if (SeenUsers.size() >= MaxUsersToConsider)
82 break;
83 if (!SeenUsers.insert(V: U0).second)
84 continue;
85 auto *UI0 = dyn_cast<Instruction>(Val: U0);
86 if (!UI0 || IMaps.isVectorized(Orig: UI0) || Claimed.contains(Ptr: UI0))
87 continue;
88 std::optional<BundleTy> NextUserBndl =
89 getMatchingBundle(Bndl, IMaps, Seed: V0, SeedUserInst: UI0, Claimed);
90 if (NextUserBndl)
91 Bundles.emplace_back(Args: std::move(*NextUserBndl));
92 }
93 return Bundles;
94}
95
96unsigned VecUtils::getFloorPowerOf2(unsigned Num) {
97 if (Num == 0)
98 return Num;
99 unsigned Mask = Num;
100 Mask >>= 1;
101 for (unsigned ShiftBy = 1; ShiftBy < sizeof(Num) * 8; ShiftBy <<= 1)
102 Mask |= Mask >> ShiftBy;
103 return Num & ~Mask;
104}
105
106#ifndef NDEBUG
107template <typename T> static void dumpImpl(ArrayRef<T *> Bndl) {
108 for (auto [Idx, V] : enumerate(Bndl))
109 dbgs() << Idx << "." << *V << "\n";
110}
111void VecUtils::dump(ArrayRef<Value *> Bndl) { dumpImpl(Bndl); }
112void VecUtils::dump(ArrayRef<Instruction *> Bndl) { dumpImpl(Bndl); }
113#endif // NDEBUG
114
115} // namespace llvm::sandboxir
116