1//===-- HexagonVectorCombine.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// HexagonVectorCombine is a utility class implementing a variety of functions
9// that assist in vector-based optimizations.
10//
11// AlignVectors: replace unaligned vector loads and stores with aligned ones.
12// HvxIdioms: recognize various opportunities to generate HVX intrinsic code.
13//===----------------------------------------------------------------------===//
14
15#include "llvm/ADT/APInt.h"
16#include "llvm/ADT/ArrayRef.h"
17#include "llvm/ADT/DenseMap.h"
18#include "llvm/ADT/STLExtras.h"
19#include "llvm/ADT/SmallVector.h"
20#include "llvm/Analysis/AliasAnalysis.h"
21#include "llvm/Analysis/AssumptionCache.h"
22#include "llvm/Analysis/InstSimplifyFolder.h"
23#include "llvm/Analysis/InstructionSimplify.h"
24#include "llvm/Analysis/ScalarEvolution.h"
25#include "llvm/Analysis/TargetLibraryInfo.h"
26#include "llvm/Analysis/ValueTracking.h"
27#include "llvm/Analysis/VectorUtils.h"
28#include "llvm/CodeGen/TargetPassConfig.h"
29#include "llvm/CodeGen/ValueTypes.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/IRBuilder.h"
32#include "llvm/IR/IntrinsicInst.h"
33#include "llvm/IR/Intrinsics.h"
34#include "llvm/IR/IntrinsicsHexagon.h"
35#include "llvm/IR/Metadata.h"
36#include "llvm/IR/PatternMatch.h"
37#include "llvm/InitializePasses.h"
38#include "llvm/Pass.h"
39#include "llvm/Support/CommandLine.h"
40#include "llvm/Support/KnownBits.h"
41#include "llvm/Support/MathExtras.h"
42#include "llvm/Support/raw_ostream.h"
43#include "llvm/Target/TargetMachine.h"
44#include "llvm/Transforms/Utils/Local.h"
45
46#include "HexagonSubtarget.h"
47#include "HexagonTargetMachine.h"
48
49#include <algorithm>
50#include <deque>
51#include <map>
52#include <optional>
53#include <set>
54#include <utility>
55#include <vector>
56
57#define DEBUG_TYPE "hexagon-vc"
58
59using namespace llvm;
60
61namespace {
62cl::opt<bool> DumpModule("hvc-dump-module", cl::Hidden);
63cl::opt<bool> VAEnabled("hvc-va", cl::Hidden, cl::init(Val: true)); // Align
64cl::opt<bool> VIEnabled("hvc-vi", cl::Hidden, cl::init(Val: true)); // Idioms
65cl::opt<bool> VADoFullStores("hvc-va-full-stores", cl::Hidden);
66
67cl::opt<unsigned> VAGroupCountLimit("hvc-va-group-count-limit", cl::Hidden,
68 cl::init(Val: ~0));
69cl::opt<unsigned> VAGroupSizeLimit("hvc-va-group-size-limit", cl::Hidden,
70 cl::init(Val: ~0));
71
72class HexagonVectorCombine {
73public:
74 HexagonVectorCombine(Function &F_, AliasAnalysis &AA_, AssumptionCache &AC_,
75 DominatorTree &DT_, ScalarEvolution &SE_,
76 TargetLibraryInfo &TLI_, const TargetMachine &TM_)
77 : F(F_), DL(F.getDataLayout()), AA(AA_), AC(AC_), DT(DT_),
78 SE(SE_), TLI(TLI_),
79 HST(static_cast<const HexagonSubtarget &>(*TM_.getSubtargetImpl(F))) {}
80
81 bool run();
82
83 // Common integer type.
84 IntegerType *getIntTy(unsigned Width = 32) const;
85 // Byte type: either scalar (when Length = 0), or vector with given
86 // element count.
87 Type *getByteTy(int ElemCount = 0) const;
88 // Boolean type: either scalar (when Length = 0), or vector with given
89 // element count.
90 Type *getBoolTy(int ElemCount = 0) const;
91 // Create a ConstantInt of type returned by getIntTy with the value Val.
92 ConstantInt *getConstInt(int Val, unsigned Width = 32) const;
93 // Get the integer value of V, if it exists.
94 std::optional<APInt> getIntValue(const Value *Val) const;
95 // Is Val a constant 0, or a vector of 0s?
96 bool isZero(const Value *Val) const;
97 // Is Val an undef value?
98 bool isUndef(const Value *Val) const;
99 // Is Val a scalar (i1 true) or a vector of (i1 true)?
100 bool isTrue(const Value *Val) const;
101 // Is Val a scalar (i1 false) or a vector of (i1 false)?
102 bool isFalse(const Value *Val) const;
103
104 // Get HVX vector type with the given element type.
105 VectorType *getHvxTy(Type *ElemTy, bool Pair = false) const;
106
107 enum SizeKind {
108 Store, // Store size
109 Alloc, // Alloc size
110 };
111 int getSizeOf(const Value *Val, SizeKind Kind = Store) const;
112 int getSizeOf(const Type *Ty, SizeKind Kind = Store) const;
113 int getTypeAlignment(Type *Ty) const;
114 size_t length(Value *Val) const;
115 size_t length(Type *Ty) const;
116
117 Constant *getNullValue(Type *Ty) const;
118 Constant *getFullValue(Type *Ty) const;
119 Constant *getConstSplat(Type *Ty, int Val) const;
120
121 Value *simplify(Value *Val) const;
122
123 Value *insertb(IRBuilderBase &Builder, Value *Dest, Value *Src, int Start,
124 int Length, int Where) const;
125 Value *vlalignb(IRBuilderBase &Builder, Value *Lo, Value *Hi,
126 Value *Amt) const;
127 Value *vralignb(IRBuilderBase &Builder, Value *Lo, Value *Hi,
128 Value *Amt) const;
129 Value *concat(IRBuilderBase &Builder, ArrayRef<Value *> Vecs) const;
130 Value *vresize(IRBuilderBase &Builder, Value *Val, int NewSize,
131 Value *Pad) const;
132 Value *rescale(IRBuilderBase &Builder, Value *Mask, Type *FromTy,
133 Type *ToTy) const;
134 Value *vlsb(IRBuilderBase &Builder, Value *Val) const;
135 Value *vbytes(IRBuilderBase &Builder, Value *Val) const;
136 Value *subvector(IRBuilderBase &Builder, Value *Val, unsigned Start,
137 unsigned Length) const;
138 Value *sublo(IRBuilderBase &Builder, Value *Val) const;
139 Value *subhi(IRBuilderBase &Builder, Value *Val) const;
140 Value *vdeal(IRBuilderBase &Builder, Value *Val0, Value *Val1) const;
141 Value *vshuff(IRBuilderBase &Builder, Value *Val0, Value *Val1) const;
142
143 Value *createHvxIntrinsic(IRBuilderBase &Builder, Intrinsic::ID IntID,
144 Type *RetTy, ArrayRef<Value *> Args,
145 ArrayRef<Type *> ArgTys = std::nullopt,
146 ArrayRef<Value *> MDSources = std::nullopt) const;
147 SmallVector<Value *> splitVectorElements(IRBuilderBase &Builder, Value *Vec,
148 unsigned ToWidth) const;
149 Value *joinVectorElements(IRBuilderBase &Builder, ArrayRef<Value *> Values,
150 VectorType *ToType) const;
151
152 std::optional<int> calculatePointerDifference(Value *Ptr0, Value *Ptr1) const;
153
154 unsigned getNumSignificantBits(const Value *V,
155 const Instruction *CtxI = nullptr) const;
156 KnownBits getKnownBits(const Value *V,
157 const Instruction *CtxI = nullptr) const;
158
159 bool isSafeToClone(const Instruction &In) const;
160
161 template <typename T = std::vector<Instruction *>>
162 bool isSafeToMoveBeforeInBB(const Instruction &In,
163 BasicBlock::const_iterator To,
164 const T &IgnoreInsts = {}) const;
165
166 // This function is only used for assertions at the moment.
167 [[maybe_unused]] bool isByteVecTy(Type *Ty) const;
168
169 Function &F;
170 const DataLayout &DL;
171 AliasAnalysis &AA;
172 AssumptionCache &AC;
173 DominatorTree &DT;
174 ScalarEvolution &SE;
175 TargetLibraryInfo &TLI;
176 const HexagonSubtarget &HST;
177
178private:
179 Value *getElementRange(IRBuilderBase &Builder, Value *Lo, Value *Hi,
180 int Start, int Length) const;
181};
182
183class AlignVectors {
184 // This code tries to replace unaligned vector loads/stores with aligned
185 // ones.
186 // Consider unaligned load:
187 // %v = original_load %some_addr, align <bad>
188 // %user = %v
189 // It will generate
190 // = load ..., align <good>
191 // = load ..., align <good>
192 // = valign
193 // etc.
194 // %synthesize = combine/shuffle the loaded data so that it looks
195 // exactly like what "original_load" has loaded.
196 // %user = %synthesize
197 // Similarly for stores.
198public:
199 AlignVectors(const HexagonVectorCombine &HVC_) : HVC(HVC_) {}
200
201 bool run();
202
203private:
204 using InstList = std::vector<Instruction *>;
205 using InstMap = DenseMap<Instruction *, Instruction *>;
206
207 struct AddrInfo {
208 AddrInfo(const AddrInfo &) = default;
209 AddrInfo(const HexagonVectorCombine &HVC, Instruction *I, Value *A, Type *T,
210 Align H)
211 : Inst(I), Addr(A), ValTy(T), HaveAlign(H),
212 NeedAlign(HVC.getTypeAlignment(Ty: ValTy)) {}
213 AddrInfo &operator=(const AddrInfo &) = default;
214
215 // XXX: add Size member?
216 Instruction *Inst;
217 Value *Addr;
218 Type *ValTy;
219 Align HaveAlign;
220 Align NeedAlign;
221 int Offset = 0; // Offset (in bytes) from the first member of the
222 // containing AddrList.
223 };
224 using AddrList = std::vector<AddrInfo>;
225
226 struct InstrLess {
227 bool operator()(const Instruction *A, const Instruction *B) const {
228 return A->comesBefore(Other: B);
229 }
230 };
231 using DepList = std::set<Instruction *, InstrLess>;
232
233 struct MoveGroup {
234 MoveGroup(const AddrInfo &AI, Instruction *B, bool Hvx, bool Load)
235 : Base(B), Main{AI.Inst}, Clones{}, IsHvx(Hvx), IsLoad(Load) {}
236 MoveGroup() = default;
237 Instruction *Base; // Base instruction of the parent address group.
238 InstList Main; // Main group of instructions.
239 InstList Deps; // List of dependencies.
240 InstMap Clones; // Map from original Deps to cloned ones.
241 bool IsHvx; // Is this group of HVX instructions?
242 bool IsLoad; // Is this a load group?
243 };
244 using MoveList = std::vector<MoveGroup>;
245
246 struct ByteSpan {
247 // A representation of "interesting" bytes within a given span of memory.
248 // These bytes are those that are loaded or stored, and they don't have
249 // to cover the entire span of memory.
250 //
251 // The representation works by picking a contiguous sequence of bytes
252 // from somewhere within a llvm::Value, and placing it at a given offset
253 // within the span.
254 //
255 // The sequence of bytes from llvm:Value is represented by Segment.
256 // Block is Segment, plus where it goes in the span.
257 //
258 // An important feature of ByteSpan is being able to make a "section",
259 // i.e. creating another ByteSpan corresponding to a range of offsets
260 // relative to the source span.
261
262 struct Segment {
263 // Segment of a Value: 'Len' bytes starting at byte 'Begin'.
264 Segment(Value *Val, int Begin, int Len)
265 : Val(Val), Start(Begin), Size(Len) {}
266 Segment(const Segment &Seg) = default;
267 Segment &operator=(const Segment &Seg) = default;
268 Value *Val; // Value representable as a sequence of bytes.
269 int Start; // First byte of the value that belongs to the segment.
270 int Size; // Number of bytes in the segment.
271 };
272
273 struct Block {
274 Block(Value *Val, int Len, int Pos) : Seg(Val, 0, Len), Pos(Pos) {}
275 Block(Value *Val, int Off, int Len, int Pos)
276 : Seg(Val, Off, Len), Pos(Pos) {}
277 Block(const Block &Blk) = default;
278 Block &operator=(const Block &Blk) = default;
279 Segment Seg; // Value segment.
280 int Pos; // Position (offset) of the block in the span.
281 };
282
283 int extent() const;
284 ByteSpan section(int Start, int Length) const;
285 ByteSpan &shift(int Offset);
286 SmallVector<Value *, 8> values() const;
287
288 int size() const { return Blocks.size(); }
289 Block &operator[](int i) { return Blocks[i]; }
290 const Block &operator[](int i) const { return Blocks[i]; }
291
292 std::vector<Block> Blocks;
293
294 using iterator = decltype(Blocks)::iterator;
295 iterator begin() { return Blocks.begin(); }
296 iterator end() { return Blocks.end(); }
297 using const_iterator = decltype(Blocks)::const_iterator;
298 const_iterator begin() const { return Blocks.begin(); }
299 const_iterator end() const { return Blocks.end(); }
300 };
301
302 Align getAlignFromValue(const Value *V) const;
303 std::optional<AddrInfo> getAddrInfo(Instruction &In) const;
304 bool isHvx(const AddrInfo &AI) const;
305 // This function is only used for assertions at the moment.
306 [[maybe_unused]] bool isSectorTy(Type *Ty) const;
307
308 Value *getPayload(Value *Val) const;
309 Value *getMask(Value *Val) const;
310 Value *getPassThrough(Value *Val) const;
311
312 Value *createAdjustedPointer(IRBuilderBase &Builder, Value *Ptr, Type *ValTy,
313 int Adjust,
314 const InstMap &CloneMap = InstMap()) const;
315 Value *createAlignedPointer(IRBuilderBase &Builder, Value *Ptr, Type *ValTy,
316 int Alignment,
317 const InstMap &CloneMap = InstMap()) const;
318
319 Value *createLoad(IRBuilderBase &Builder, Type *ValTy, Value *Ptr,
320 Value *Predicate, int Alignment, Value *Mask,
321 Value *PassThru,
322 ArrayRef<Value *> MDSources = std::nullopt) const;
323 Value *createSimpleLoad(IRBuilderBase &Builder, Type *ValTy, Value *Ptr,
324 int Alignment,
325 ArrayRef<Value *> MDSources = std::nullopt) const;
326
327 Value *createStore(IRBuilderBase &Builder, Value *Val, Value *Ptr,
328 Value *Predicate, int Alignment, Value *Mask,
329 ArrayRef<Value *> MDSources = std ::nullopt) const;
330 Value *createSimpleStore(IRBuilderBase &Builder, Value *Val, Value *Ptr,
331 int Alignment,
332 ArrayRef<Value *> MDSources = std ::nullopt) const;
333
334 Value *createPredicatedLoad(IRBuilderBase &Builder, Type *ValTy, Value *Ptr,
335 Value *Predicate, int Alignment,
336 ArrayRef<Value *> MDSources = std::nullopt) const;
337 Value *
338 createPredicatedStore(IRBuilderBase &Builder, Value *Val, Value *Ptr,
339 Value *Predicate, int Alignment,
340 ArrayRef<Value *> MDSources = std::nullopt) const;
341
342 DepList getUpwardDeps(Instruction *In, Instruction *Base) const;
343 bool createAddressGroups();
344 MoveList createLoadGroups(const AddrList &Group) const;
345 MoveList createStoreGroups(const AddrList &Group) const;
346 bool moveTogether(MoveGroup &Move) const;
347 template <typename T> InstMap cloneBefore(Instruction *To, T &&Insts) const;
348
349 void realignLoadGroup(IRBuilderBase &Builder, const ByteSpan &VSpan,
350 int ScLen, Value *AlignVal, Value *AlignAddr) const;
351 void realignStoreGroup(IRBuilderBase &Builder, const ByteSpan &VSpan,
352 int ScLen, Value *AlignVal, Value *AlignAddr) const;
353 bool realignGroup(const MoveGroup &Move) const;
354
355 Value *makeTestIfUnaligned(IRBuilderBase &Builder, Value *AlignVal,
356 int Alignment) const;
357
358 friend raw_ostream &operator<<(raw_ostream &OS, const AddrInfo &AI);
359 friend raw_ostream &operator<<(raw_ostream &OS, const MoveGroup &MG);
360 friend raw_ostream &operator<<(raw_ostream &OS, const ByteSpan::Block &B);
361 friend raw_ostream &operator<<(raw_ostream &OS, const ByteSpan &BS);
362
363 std::map<Instruction *, AddrList> AddrGroups;
364 const HexagonVectorCombine &HVC;
365};
366
367LLVM_ATTRIBUTE_UNUSED
368raw_ostream &operator<<(raw_ostream &OS, const AlignVectors::AddrInfo &AI) {
369 OS << "Inst: " << AI.Inst << " " << *AI.Inst << '\n';
370 OS << "Addr: " << *AI.Addr << '\n';
371 OS << "Type: " << *AI.ValTy << '\n';
372 OS << "HaveAlign: " << AI.HaveAlign.value() << '\n';
373 OS << "NeedAlign: " << AI.NeedAlign.value() << '\n';
374 OS << "Offset: " << AI.Offset;
375 return OS;
376}
377
378LLVM_ATTRIBUTE_UNUSED
379raw_ostream &operator<<(raw_ostream &OS, const AlignVectors::MoveGroup &MG) {
380 OS << "IsLoad:" << (MG.IsLoad ? "yes" : "no");
381 OS << ", IsHvx:" << (MG.IsHvx ? "yes" : "no") << '\n';
382 OS << "Main\n";
383 for (Instruction *I : MG.Main)
384 OS << " " << *I << '\n';
385 OS << "Deps\n";
386 for (Instruction *I : MG.Deps)
387 OS << " " << *I << '\n';
388 OS << "Clones\n";
389 for (auto [K, V] : MG.Clones) {
390 OS << " ";
391 K->printAsOperand(O&: OS, PrintType: false);
392 OS << "\t-> " << *V << '\n';
393 }
394 return OS;
395}
396
397LLVM_ATTRIBUTE_UNUSED
398raw_ostream &operator<<(raw_ostream &OS,
399 const AlignVectors::ByteSpan::Block &B) {
400 OS << " @" << B.Pos << " [" << B.Seg.Start << ',' << B.Seg.Size << "] ";
401 if (B.Seg.Val == reinterpret_cast<const Value *>(&B)) {
402 OS << "(self:" << B.Seg.Val << ')';
403 } else if (B.Seg.Val != nullptr) {
404 OS << *B.Seg.Val;
405 } else {
406 OS << "(null)";
407 }
408 return OS;
409}
410
411LLVM_ATTRIBUTE_UNUSED
412raw_ostream &operator<<(raw_ostream &OS, const AlignVectors::ByteSpan &BS) {
413 OS << "ByteSpan[size=" << BS.size() << ", extent=" << BS.extent() << '\n';
414 for (const AlignVectors::ByteSpan::Block &B : BS)
415 OS << B << '\n';
416 OS << ']';
417 return OS;
418}
419
420class HvxIdioms {
421public:
422 HvxIdioms(const HexagonVectorCombine &HVC_) : HVC(HVC_) {
423 auto *Int32Ty = HVC.getIntTy(Width: 32);
424 HvxI32Ty = HVC.getHvxTy(ElemTy: Int32Ty, /*Pair=*/false);
425 HvxP32Ty = HVC.getHvxTy(ElemTy: Int32Ty, /*Pair=*/true);
426 }
427
428 bool run();
429
430private:
431 enum Signedness { Positive, Signed, Unsigned };
432
433 // Value + sign
434 // This is to keep track of whether the value should be treated as signed
435 // or unsigned, or is known to be positive.
436 struct SValue {
437 Value *Val;
438 Signedness Sgn;
439 };
440
441 struct FxpOp {
442 unsigned Opcode;
443 unsigned Frac; // Number of fraction bits
444 SValue X, Y;
445 // If present, add 1 << RoundAt before shift:
446 std::optional<unsigned> RoundAt;
447 VectorType *ResTy;
448 };
449
450 auto getNumSignificantBits(Value *V, Instruction *In) const
451 -> std::pair<unsigned, Signedness>;
452 auto canonSgn(SValue X, SValue Y) const -> std::pair<SValue, SValue>;
453
454 auto matchFxpMul(Instruction &In) const -> std::optional<FxpOp>;
455 auto processFxpMul(Instruction &In, const FxpOp &Op) const -> Value *;
456
457 auto processFxpMulChopped(IRBuilderBase &Builder, Instruction &In,
458 const FxpOp &Op) const -> Value *;
459 auto createMulQ15(IRBuilderBase &Builder, SValue X, SValue Y,
460 bool Rounding) const -> Value *;
461 auto createMulQ31(IRBuilderBase &Builder, SValue X, SValue Y,
462 bool Rounding) const -> Value *;
463 // Return {Result, Carry}, where Carry is a vector predicate.
464 auto createAddCarry(IRBuilderBase &Builder, Value *X, Value *Y,
465 Value *CarryIn = nullptr) const
466 -> std::pair<Value *, Value *>;
467 auto createMul16(IRBuilderBase &Builder, SValue X, SValue Y) const -> Value *;
468 auto createMulH16(IRBuilderBase &Builder, SValue X, SValue Y) const
469 -> Value *;
470 auto createMul32(IRBuilderBase &Builder, SValue X, SValue Y) const
471 -> std::pair<Value *, Value *>;
472 auto createAddLong(IRBuilderBase &Builder, ArrayRef<Value *> WordX,
473 ArrayRef<Value *> WordY) const -> SmallVector<Value *>;
474 auto createMulLong(IRBuilderBase &Builder, ArrayRef<Value *> WordX,
475 Signedness SgnX, ArrayRef<Value *> WordY,
476 Signedness SgnY) const -> SmallVector<Value *>;
477
478 VectorType *HvxI32Ty;
479 VectorType *HvxP32Ty;
480 const HexagonVectorCombine &HVC;
481
482 friend raw_ostream &operator<<(raw_ostream &, const FxpOp &);
483};
484
485[[maybe_unused]] raw_ostream &operator<<(raw_ostream &OS,
486 const HvxIdioms::FxpOp &Op) {
487 static const char *SgnNames[] = {"Positive", "Signed", "Unsigned"};
488 OS << Instruction::getOpcodeName(Opcode: Op.Opcode) << '.' << Op.Frac;
489 if (Op.RoundAt.has_value()) {
490 if (Op.Frac != 0 && *Op.RoundAt == Op.Frac - 1) {
491 OS << ":rnd";
492 } else {
493 OS << " + 1<<" << *Op.RoundAt;
494 }
495 }
496 OS << "\n X:(" << SgnNames[Op.X.Sgn] << ") " << *Op.X.Val << "\n"
497 << " Y:(" << SgnNames[Op.Y.Sgn] << ") " << *Op.Y.Val;
498 return OS;
499}
500
501} // namespace
502
503namespace {
504
505template <typename T> T *getIfUnordered(T *MaybeT) {
506 return MaybeT && MaybeT->isUnordered() ? MaybeT : nullptr;
507}
508template <typename T> T *isCandidate(Instruction *In) {
509 return dyn_cast<T>(In);
510}
511template <> LoadInst *isCandidate<LoadInst>(Instruction *In) {
512 return getIfUnordered(MaybeT: dyn_cast<LoadInst>(Val: In));
513}
514template <> StoreInst *isCandidate<StoreInst>(Instruction *In) {
515 return getIfUnordered(MaybeT: dyn_cast<StoreInst>(Val: In));
516}
517
518#if !defined(_MSC_VER) || _MSC_VER >= 1926
519// VS2017 and some versions of VS2019 have trouble compiling this:
520// error C2976: 'std::map': too few template arguments
521// VS 2019 16.x is known to work, except for 16.4/16.5 (MSC_VER 1924/1925)
522template <typename Pred, typename... Ts>
523void erase_if(std::map<Ts...> &map, Pred p)
524#else
525template <typename Pred, typename T, typename U>
526void erase_if(std::map<T, U> &map, Pred p)
527#endif
528{
529 for (auto i = map.begin(), e = map.end(); i != e;) {
530 if (p(*i))
531 i = map.erase(i);
532 else
533 i = std::next(i);
534 }
535}
536
537// Forward other erase_ifs to the LLVM implementations.
538template <typename Pred, typename T> void erase_if(T &&container, Pred p) {
539 llvm::erase_if(std::forward<T>(container), p);
540}
541
542} // namespace
543
544// --- Begin AlignVectors
545
546// For brevity, only consider loads. We identify a group of loads where we
547// know the relative differences between their addresses, so we know how they
548// are laid out in memory (relative to one another). These loads can overlap,
549// can be shorter or longer than the desired vector length.
550// Ultimately we want to generate a sequence of aligned loads that will load
551// every byte that the original loads loaded, and have the program use these
552// loaded values instead of the original loads.
553// We consider the contiguous memory area spanned by all these loads.
554//
555// Let's say that a single aligned vector load can load 16 bytes at a time.
556// If the program wanted to use a byte at offset 13 from the beginning of the
557// original span, it will be a byte at offset 13+x in the aligned data for
558// some x>=0. This may happen to be in the first aligned load, or in the load
559// following it. Since we generally don't know what the that alignment value
560// is at compile time, we proactively do valigns on the aligned loads, so that
561// byte that was at offset 13 is still at offset 13 after the valigns.
562//
563// This will be the starting point for making the rest of the program use the
564// data loaded by the new loads.
565// For each original load, and its users:
566// %v = load ...
567// ... = %v
568// ... = %v
569// we create
570// %new_v = extract/combine/shuffle data from loaded/valigned vectors so
571// it contains the same value as %v did before
572// then replace all users of %v with %new_v.
573// ... = %new_v
574// ... = %new_v
575
576auto AlignVectors::ByteSpan::extent() const -> int {
577 if (size() == 0)
578 return 0;
579 int Min = Blocks[0].Pos;
580 int Max = Blocks[0].Pos + Blocks[0].Seg.Size;
581 for (int i = 1, e = size(); i != e; ++i) {
582 Min = std::min(a: Min, b: Blocks[i].Pos);
583 Max = std::max(a: Max, b: Blocks[i].Pos + Blocks[i].Seg.Size);
584 }
585 return Max - Min;
586}
587
588auto AlignVectors::ByteSpan::section(int Start, int Length) const -> ByteSpan {
589 ByteSpan Section;
590 for (const ByteSpan::Block &B : Blocks) {
591 int L = std::max(a: B.Pos, b: Start); // Left end.
592 int R = std::min(a: B.Pos + B.Seg.Size, b: Start + Length); // Right end+1.
593 if (L < R) {
594 // How much to chop off the beginning of the segment:
595 int Off = L > B.Pos ? L - B.Pos : 0;
596 Section.Blocks.emplace_back(args: B.Seg.Val, args: B.Seg.Start + Off, args: R - L, args&: L);
597 }
598 }
599 return Section;
600}
601
602auto AlignVectors::ByteSpan::shift(int Offset) -> ByteSpan & {
603 for (Block &B : Blocks)
604 B.Pos += Offset;
605 return *this;
606}
607
608auto AlignVectors::ByteSpan::values() const -> SmallVector<Value *, 8> {
609 SmallVector<Value *, 8> Values(Blocks.size());
610 for (int i = 0, e = Blocks.size(); i != e; ++i)
611 Values[i] = Blocks[i].Seg.Val;
612 return Values;
613}
614
615auto AlignVectors::getAlignFromValue(const Value *V) const -> Align {
616 const auto *C = dyn_cast<ConstantInt>(Val: V);
617 assert(C && "Alignment must be a compile-time constant integer");
618 return C->getAlignValue();
619}
620
621auto AlignVectors::getAddrInfo(Instruction &In) const
622 -> std::optional<AddrInfo> {
623 if (auto *L = isCandidate<LoadInst>(In: &In))
624 return AddrInfo(HVC, L, L->getPointerOperand(), L->getType(),
625 L->getAlign());
626 if (auto *S = isCandidate<StoreInst>(In: &In))
627 return AddrInfo(HVC, S, S->getPointerOperand(),
628 S->getValueOperand()->getType(), S->getAlign());
629 if (auto *II = isCandidate<IntrinsicInst>(In: &In)) {
630 Intrinsic::ID ID = II->getIntrinsicID();
631 switch (ID) {
632 case Intrinsic::masked_load:
633 return AddrInfo(HVC, II, II->getArgOperand(i: 0), II->getType(),
634 getAlignFromValue(V: II->getArgOperand(i: 1)));
635 case Intrinsic::masked_store:
636 return AddrInfo(HVC, II, II->getArgOperand(i: 1),
637 II->getArgOperand(i: 0)->getType(),
638 getAlignFromValue(V: II->getArgOperand(i: 2)));
639 }
640 }
641 return std::nullopt;
642}
643
644auto AlignVectors::isHvx(const AddrInfo &AI) const -> bool {
645 return HVC.HST.isTypeForHVX(VecTy: AI.ValTy);
646}
647
648auto AlignVectors::getPayload(Value *Val) const -> Value * {
649 if (auto *In = dyn_cast<Instruction>(Val)) {
650 Intrinsic::ID ID = 0;
651 if (auto *II = dyn_cast<IntrinsicInst>(Val: In))
652 ID = II->getIntrinsicID();
653 if (isa<StoreInst>(Val: In) || ID == Intrinsic::masked_store)
654 return In->getOperand(i: 0);
655 }
656 return Val;
657}
658
659auto AlignVectors::getMask(Value *Val) const -> Value * {
660 if (auto *II = dyn_cast<IntrinsicInst>(Val)) {
661 switch (II->getIntrinsicID()) {
662 case Intrinsic::masked_load:
663 return II->getArgOperand(i: 2);
664 case Intrinsic::masked_store:
665 return II->getArgOperand(i: 3);
666 }
667 }
668
669 Type *ValTy = getPayload(Val)->getType();
670 if (auto *VecTy = dyn_cast<VectorType>(Val: ValTy))
671 return HVC.getFullValue(Ty: HVC.getBoolTy(ElemCount: HVC.length(Ty: VecTy)));
672 return HVC.getFullValue(Ty: HVC.getBoolTy());
673}
674
675auto AlignVectors::getPassThrough(Value *Val) const -> Value * {
676 if (auto *II = dyn_cast<IntrinsicInst>(Val)) {
677 if (II->getIntrinsicID() == Intrinsic::masked_load)
678 return II->getArgOperand(i: 3);
679 }
680 return UndefValue::get(T: getPayload(Val)->getType());
681}
682
683auto AlignVectors::createAdjustedPointer(IRBuilderBase &Builder, Value *Ptr,
684 Type *ValTy, int Adjust,
685 const InstMap &CloneMap) const
686 -> Value * {
687 if (auto *I = dyn_cast<Instruction>(Val: Ptr))
688 if (Instruction *New = CloneMap.lookup(Val: I))
689 Ptr = New;
690 return Builder.CreatePtrAdd(Ptr, Offset: HVC.getConstInt(Val: Adjust), Name: "gep");
691}
692
693auto AlignVectors::createAlignedPointer(IRBuilderBase &Builder, Value *Ptr,
694 Type *ValTy, int Alignment,
695 const InstMap &CloneMap) const
696 -> Value * {
697 auto remap = [&](Value *V) -> Value * {
698 if (auto *I = dyn_cast<Instruction>(Val: V)) {
699 for (auto [Old, New] : CloneMap)
700 I->replaceUsesOfWith(From: Old, To: New);
701 return I;
702 }
703 return V;
704 };
705 Value *AsInt = Builder.CreatePtrToInt(V: Ptr, DestTy: HVC.getIntTy(), Name: "pti");
706 Value *Mask = HVC.getConstInt(Val: -Alignment);
707 Value *And = Builder.CreateAnd(LHS: remap(AsInt), RHS: Mask, Name: "and");
708 return Builder.CreateIntToPtr(
709 V: And, DestTy: PointerType::getUnqual(C&: ValTy->getContext()), Name: "itp");
710}
711
712auto AlignVectors::createLoad(IRBuilderBase &Builder, Type *ValTy, Value *Ptr,
713 Value *Predicate, int Alignment, Value *Mask,
714 Value *PassThru,
715 ArrayRef<Value *> MDSources) const -> Value * {
716 bool HvxHasPredLoad = HVC.HST.useHVXV62Ops();
717 // Predicate is nullptr if not creating predicated load
718 if (Predicate) {
719 assert(!Predicate->getType()->isVectorTy() &&
720 "Expectning scalar predicate");
721 if (HVC.isFalse(Val: Predicate))
722 return UndefValue::get(T: ValTy);
723 if (!HVC.isTrue(Val: Predicate) && HvxHasPredLoad) {
724 Value *Load = createPredicatedLoad(Builder, ValTy, Ptr, Predicate,
725 Alignment, MDSources);
726 return Builder.CreateSelect(C: Mask, True: Load, False: PassThru);
727 }
728 // Predicate == true here.
729 }
730 assert(!HVC.isUndef(Mask)); // Should this be allowed?
731 if (HVC.isZero(Val: Mask))
732 return PassThru;
733 if (HVC.isTrue(Val: Mask))
734 return createSimpleLoad(Builder, ValTy, Ptr, Alignment, MDSources);
735
736 Instruction *Load = Builder.CreateMaskedLoad(Ty: ValTy, Ptr, Alignment: Align(Alignment),
737 Mask, PassThru, Name: "mld");
738 propagateMetadata(I: Load, VL: MDSources);
739 return Load;
740}
741
742auto AlignVectors::createSimpleLoad(IRBuilderBase &Builder, Type *ValTy,
743 Value *Ptr, int Alignment,
744 ArrayRef<Value *> MDSources) const
745 -> Value * {
746 Instruction *Load =
747 Builder.CreateAlignedLoad(Ty: ValTy, Ptr, Align: Align(Alignment), Name: "ald");
748 propagateMetadata(I: Load, VL: MDSources);
749 return Load;
750}
751
752auto AlignVectors::createPredicatedLoad(IRBuilderBase &Builder, Type *ValTy,
753 Value *Ptr, Value *Predicate,
754 int Alignment,
755 ArrayRef<Value *> MDSources) const
756 -> Value * {
757 assert(HVC.HST.isTypeForHVX(ValTy) &&
758 "Predicates 'scalar' vector loads not yet supported");
759 assert(Predicate);
760 assert(!Predicate->getType()->isVectorTy() && "Expectning scalar predicate");
761 assert(HVC.getSizeOf(ValTy, HVC.Alloc) % Alignment == 0);
762 if (HVC.isFalse(Val: Predicate))
763 return UndefValue::get(T: ValTy);
764 if (HVC.isTrue(Val: Predicate))
765 return createSimpleLoad(Builder, ValTy, Ptr, Alignment, MDSources);
766
767 auto V6_vL32b_pred_ai = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vL32b_pred_ai);
768 // FIXME: This may not put the offset from Ptr into the vmem offset.
769 return HVC.createHvxIntrinsic(Builder, IntID: V6_vL32b_pred_ai, RetTy: ValTy,
770 Args: {Predicate, Ptr, HVC.getConstInt(Val: 0)},
771 ArgTys: std::nullopt, MDSources);
772}
773
774auto AlignVectors::createStore(IRBuilderBase &Builder, Value *Val, Value *Ptr,
775 Value *Predicate, int Alignment, Value *Mask,
776 ArrayRef<Value *> MDSources) const -> Value * {
777 if (HVC.isZero(Val: Mask) || HVC.isUndef(Val) || HVC.isUndef(Val: Mask))
778 return UndefValue::get(T: Val->getType());
779 assert(!Predicate || (!Predicate->getType()->isVectorTy() &&
780 "Expectning scalar predicate"));
781 if (Predicate) {
782 if (HVC.isFalse(Val: Predicate))
783 return UndefValue::get(T: Val->getType());
784 if (HVC.isTrue(Val: Predicate))
785 Predicate = nullptr;
786 }
787 // Here both Predicate and Mask are true or unknown.
788
789 if (HVC.isTrue(Val: Mask)) {
790 if (Predicate) { // Predicate unknown
791 return createPredicatedStore(Builder, Val, Ptr, Predicate, Alignment,
792 MDSources);
793 }
794 // Predicate is true:
795 return createSimpleStore(Builder, Val, Ptr, Alignment, MDSources);
796 }
797
798 // Mask is unknown
799 if (!Predicate) {
800 Instruction *Store =
801 Builder.CreateMaskedStore(Val, Ptr, Alignment: Align(Alignment), Mask);
802 propagateMetadata(I: Store, VL: MDSources);
803 return Store;
804 }
805
806 // Both Predicate and Mask are unknown.
807 // Emulate masked store with predicated-load + mux + predicated-store.
808 Value *PredLoad = createPredicatedLoad(Builder, ValTy: Val->getType(), Ptr,
809 Predicate, Alignment, MDSources);
810 Value *Mux = Builder.CreateSelect(C: Mask, True: Val, False: PredLoad);
811 return createPredicatedStore(Builder, Val: Mux, Ptr, Predicate, Alignment,
812 MDSources);
813}
814
815auto AlignVectors::createSimpleStore(IRBuilderBase &Builder, Value *Val,
816 Value *Ptr, int Alignment,
817 ArrayRef<Value *> MDSources) const
818 -> Value * {
819 Instruction *Store = Builder.CreateAlignedStore(Val, Ptr, Align: Align(Alignment));
820 propagateMetadata(I: Store, VL: MDSources);
821 return Store;
822}
823
824auto AlignVectors::createPredicatedStore(IRBuilderBase &Builder, Value *Val,
825 Value *Ptr, Value *Predicate,
826 int Alignment,
827 ArrayRef<Value *> MDSources) const
828 -> Value * {
829 assert(HVC.HST.isTypeForHVX(Val->getType()) &&
830 "Predicates 'scalar' vector stores not yet supported");
831 assert(Predicate);
832 if (HVC.isFalse(Val: Predicate))
833 return UndefValue::get(T: Val->getType());
834 if (HVC.isTrue(Val: Predicate))
835 return createSimpleStore(Builder, Val, Ptr, Alignment, MDSources);
836
837 assert(HVC.getSizeOf(Val, HVC.Alloc) % Alignment == 0);
838 auto V6_vS32b_pred_ai = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vS32b_pred_ai);
839 // FIXME: This may not put the offset from Ptr into the vmem offset.
840 return HVC.createHvxIntrinsic(Builder, IntID: V6_vS32b_pred_ai, RetTy: nullptr,
841 Args: {Predicate, Ptr, HVC.getConstInt(Val: 0), Val},
842 ArgTys: std::nullopt, MDSources);
843}
844
845auto AlignVectors::getUpwardDeps(Instruction *In, Instruction *Base) const
846 -> DepList {
847 BasicBlock *Parent = Base->getParent();
848 assert(In->getParent() == Parent &&
849 "Base and In should be in the same block");
850 assert(Base->comesBefore(In) && "Base should come before In");
851
852 DepList Deps;
853 std::deque<Instruction *> WorkQ = {In};
854 while (!WorkQ.empty()) {
855 Instruction *D = WorkQ.front();
856 WorkQ.pop_front();
857 if (D != In)
858 Deps.insert(x: D);
859 for (Value *Op : D->operands()) {
860 if (auto *I = dyn_cast<Instruction>(Val: Op)) {
861 if (I->getParent() == Parent && Base->comesBefore(Other: I))
862 WorkQ.push_back(x: I);
863 }
864 }
865 }
866 return Deps;
867}
868
869auto AlignVectors::createAddressGroups() -> bool {
870 // An address group created here may contain instructions spanning
871 // multiple basic blocks.
872 AddrList WorkStack;
873
874 auto findBaseAndOffset = [&](AddrInfo &AI) -> std::pair<Instruction *, int> {
875 for (AddrInfo &W : WorkStack) {
876 if (auto D = HVC.calculatePointerDifference(Ptr0: AI.Addr, Ptr1: W.Addr))
877 return std::make_pair(x&: W.Inst, y&: *D);
878 }
879 return std::make_pair(x: nullptr, y: 0);
880 };
881
882 auto traverseBlock = [&](DomTreeNode *DomN, auto Visit) -> void {
883 BasicBlock &Block = *DomN->getBlock();
884 for (Instruction &I : Block) {
885 auto AI = this->getAddrInfo(In&: I); // Use this-> for gcc6.
886 if (!AI)
887 continue;
888 auto F = findBaseAndOffset(*AI);
889 Instruction *GroupInst;
890 if (Instruction *BI = F.first) {
891 AI->Offset = F.second;
892 GroupInst = BI;
893 } else {
894 WorkStack.push_back(x: *AI);
895 GroupInst = AI->Inst;
896 }
897 AddrGroups[GroupInst].push_back(x: *AI);
898 }
899
900 for (DomTreeNode *C : DomN->children())
901 Visit(C, Visit);
902
903 while (!WorkStack.empty() && WorkStack.back().Inst->getParent() == &Block)
904 WorkStack.pop_back();
905 };
906
907 traverseBlock(HVC.DT.getRootNode(), traverseBlock);
908 assert(WorkStack.empty());
909
910 // AddrGroups are formed.
911
912 // Remove groups of size 1.
913 erase_if(map&: AddrGroups, p: [](auto &G) { return G.second.size() == 1; });
914 // Remove groups that don't use HVX types.
915 erase_if(map&: AddrGroups, p: [&](auto &G) {
916 return llvm::none_of(
917 G.second, [&](auto &I) { return HVC.HST.isTypeForHVX(VecTy: I.ValTy); });
918 });
919
920 return !AddrGroups.empty();
921}
922
923auto AlignVectors::createLoadGroups(const AddrList &Group) const -> MoveList {
924 // Form load groups.
925 // To avoid complications with moving code across basic blocks, only form
926 // groups that are contained within a single basic block.
927 unsigned SizeLimit = VAGroupSizeLimit;
928 if (SizeLimit == 0)
929 return {};
930
931 auto tryAddTo = [&](const AddrInfo &Info, MoveGroup &Move) {
932 assert(!Move.Main.empty() && "Move group should have non-empty Main");
933 if (Move.Main.size() >= SizeLimit)
934 return false;
935 // Don't mix HVX and non-HVX instructions.
936 if (Move.IsHvx != isHvx(AI: Info))
937 return false;
938 // Leading instruction in the load group.
939 Instruction *Base = Move.Main.front();
940 if (Base->getParent() != Info.Inst->getParent())
941 return false;
942 // Check if it's safe to move the load.
943 if (!HVC.isSafeToMoveBeforeInBB(In: *Info.Inst, To: Base->getIterator()))
944 return false;
945 // And if it's safe to clone the dependencies.
946 auto isSafeToCopyAtBase = [&](const Instruction *I) {
947 return HVC.isSafeToMoveBeforeInBB(In: *I, To: Base->getIterator()) &&
948 HVC.isSafeToClone(In: *I);
949 };
950 DepList Deps = getUpwardDeps(In: Info.Inst, Base);
951 if (!llvm::all_of(Range&: Deps, P: isSafeToCopyAtBase))
952 return false;
953
954 Move.Main.push_back(x: Info.Inst);
955 llvm::append_range(C&: Move.Deps, R&: Deps);
956 return true;
957 };
958
959 MoveList LoadGroups;
960
961 for (const AddrInfo &Info : Group) {
962 if (!Info.Inst->mayReadFromMemory())
963 continue;
964 if (LoadGroups.empty() || !tryAddTo(Info, LoadGroups.back()))
965 LoadGroups.emplace_back(args: Info, args: Group.front().Inst, args: isHvx(AI: Info), args: true);
966 }
967
968 // Erase singleton groups.
969 erase_if(container&: LoadGroups, p: [](const MoveGroup &G) { return G.Main.size() <= 1; });
970
971 // Erase HVX groups on targets < HvxV62 (due to lack of predicated loads).
972 if (!HVC.HST.useHVXV62Ops())
973 erase_if(container&: LoadGroups, p: [](const MoveGroup &G) { return G.IsHvx; });
974
975 return LoadGroups;
976}
977
978auto AlignVectors::createStoreGroups(const AddrList &Group) const -> MoveList {
979 // Form store groups.
980 // To avoid complications with moving code across basic blocks, only form
981 // groups that are contained within a single basic block.
982 unsigned SizeLimit = VAGroupSizeLimit;
983 if (SizeLimit == 0)
984 return {};
985
986 auto tryAddTo = [&](const AddrInfo &Info, MoveGroup &Move) {
987 assert(!Move.Main.empty() && "Move group should have non-empty Main");
988 if (Move.Main.size() >= SizeLimit)
989 return false;
990 // For stores with return values we'd have to collect downward depenencies.
991 // There are no such stores that we handle at the moment, so omit that.
992 assert(Info.Inst->getType()->isVoidTy() &&
993 "Not handling stores with return values");
994 // Don't mix HVX and non-HVX instructions.
995 if (Move.IsHvx != isHvx(AI: Info))
996 return false;
997 // For stores we need to be careful whether it's safe to move them.
998 // Stores that are otherwise safe to move together may not appear safe
999 // to move over one another (i.e. isSafeToMoveBefore may return false).
1000 Instruction *Base = Move.Main.front();
1001 if (Base->getParent() != Info.Inst->getParent())
1002 return false;
1003 if (!HVC.isSafeToMoveBeforeInBB(In: *Info.Inst, To: Base->getIterator(), IgnoreInsts: Move.Main))
1004 return false;
1005 Move.Main.push_back(x: Info.Inst);
1006 return true;
1007 };
1008
1009 MoveList StoreGroups;
1010
1011 for (auto I = Group.rbegin(), E = Group.rend(); I != E; ++I) {
1012 const AddrInfo &Info = *I;
1013 if (!Info.Inst->mayWriteToMemory())
1014 continue;
1015 if (StoreGroups.empty() || !tryAddTo(Info, StoreGroups.back()))
1016 StoreGroups.emplace_back(args: Info, args: Group.front().Inst, args: isHvx(AI: Info), args: false);
1017 }
1018
1019 // Erase singleton groups.
1020 erase_if(container&: StoreGroups, p: [](const MoveGroup &G) { return G.Main.size() <= 1; });
1021
1022 // Erase HVX groups on targets < HvxV62 (due to lack of predicated loads).
1023 if (!HVC.HST.useHVXV62Ops())
1024 erase_if(container&: StoreGroups, p: [](const MoveGroup &G) { return G.IsHvx; });
1025
1026 // Erase groups where every store is a full HVX vector. The reason is that
1027 // aligning predicated stores generates complex code that may be less
1028 // efficient than a sequence of unaligned vector stores.
1029 if (!VADoFullStores) {
1030 erase_if(container&: StoreGroups, p: [this](const MoveGroup &G) {
1031 return G.IsHvx && llvm::all_of(Range: G.Main, P: [this](Instruction *S) {
1032 auto MaybeInfo = this->getAddrInfo(In&: *S);
1033 assert(MaybeInfo.has_value());
1034 return HVC.HST.isHVXVectorType(
1035 VecTy: EVT::getEVT(Ty: MaybeInfo->ValTy, HandleUnknown: false));
1036 });
1037 });
1038 }
1039
1040 return StoreGroups;
1041}
1042
1043auto AlignVectors::moveTogether(MoveGroup &Move) const -> bool {
1044 // Move all instructions to be adjacent.
1045 assert(!Move.Main.empty() && "Move group should have non-empty Main");
1046 Instruction *Where = Move.Main.front();
1047
1048 if (Move.IsLoad) {
1049 // Move all the loads (and dependencies) to where the first load is.
1050 // Clone all deps to before Where, keeping order.
1051 Move.Clones = cloneBefore(To: Where, Insts&: Move.Deps);
1052 // Move all main instructions to after Where, keeping order.
1053 ArrayRef<Instruction *> Main(Move.Main);
1054 for (Instruction *M : Main) {
1055 if (M != Where)
1056 M->moveAfter(MovePos: Where);
1057 for (auto [Old, New] : Move.Clones)
1058 M->replaceUsesOfWith(From: Old, To: New);
1059 Where = M;
1060 }
1061 // Replace Deps with the clones.
1062 for (int i = 0, e = Move.Deps.size(); i != e; ++i)
1063 Move.Deps[i] = Move.Clones[Move.Deps[i]];
1064 } else {
1065 // Move all the stores to where the last store is.
1066 // NOTE: Deps are empty for "store" groups. If they need to be
1067 // non-empty, decide on the order.
1068 assert(Move.Deps.empty());
1069 // Move all main instructions to before Where, inverting order.
1070 ArrayRef<Instruction *> Main(Move.Main);
1071 for (Instruction *M : Main.drop_front(N: 1)) {
1072 M->moveBefore(MovePos: Where);
1073 Where = M;
1074 }
1075 }
1076
1077 return Move.Main.size() + Move.Deps.size() > 1;
1078}
1079
1080template <typename T>
1081auto AlignVectors::cloneBefore(Instruction *To, T &&Insts) const -> InstMap {
1082 InstMap Map;
1083
1084 for (Instruction *I : Insts) {
1085 assert(HVC.isSafeToClone(*I));
1086 Instruction *C = I->clone();
1087 C->setName(Twine("c.") + I->getName() + ".");
1088 C->insertBefore(InsertPos: To);
1089
1090 for (auto [Old, New] : Map)
1091 C->replaceUsesOfWith(From: Old, To: New);
1092 Map.insert(KV: std::make_pair(x&: I, y&: C));
1093 }
1094 return Map;
1095}
1096
1097auto AlignVectors::realignLoadGroup(IRBuilderBase &Builder,
1098 const ByteSpan &VSpan, int ScLen,
1099 Value *AlignVal, Value *AlignAddr) const
1100 -> void {
1101 LLVM_DEBUG(dbgs() << __func__ << "\n");
1102
1103 Type *SecTy = HVC.getByteTy(ElemCount: ScLen);
1104 int NumSectors = (VSpan.extent() + ScLen - 1) / ScLen;
1105 bool DoAlign = !HVC.isZero(Val: AlignVal);
1106 BasicBlock::iterator BasePos = Builder.GetInsertPoint();
1107 BasicBlock *BaseBlock = Builder.GetInsertBlock();
1108
1109 ByteSpan ASpan;
1110 auto *True = HVC.getFullValue(Ty: HVC.getBoolTy(ElemCount: ScLen));
1111 auto *Undef = UndefValue::get(T: SecTy);
1112
1113 // Created load does not have to be "Instruction" (e.g. "undef").
1114 SmallVector<Value *> Loads(NumSectors + DoAlign, nullptr);
1115
1116 // We could create all of the aligned loads, and generate the valigns
1117 // at the location of the first load, but for large load groups, this
1118 // could create highly suboptimal code (there have been groups of 140+
1119 // loads in real code).
1120 // Instead, place the loads/valigns as close to the users as possible.
1121 // In any case we need to have a mapping from the blocks of VSpan (the
1122 // span covered by the pre-existing loads) to ASpan (the span covered
1123 // by the aligned loads). There is a small problem, though: ASpan needs
1124 // to have pointers to the loads/valigns, but we don't have these loads
1125 // because we don't know where to put them yet. We find out by creating
1126 // a section of ASpan that corresponds to values (blocks) from VSpan,
1127 // and checking where the new load should be placed. We need to attach
1128 // this location information to each block in ASpan somehow, so we put
1129 // distincts values for Seg.Val in each ASpan.Blocks[i], and use a map
1130 // to store the location for each Seg.Val.
1131 // The distinct values happen to be Blocks[i].Seg.Val = &Blocks[i],
1132 // which helps with printing ByteSpans without crashing when printing
1133 // Segments with these temporary identifiers in place of Val.
1134
1135 // Populate the blocks first, to avoid reallocations of the vector
1136 // interfering with generating the placeholder addresses.
1137 for (int Index = 0; Index != NumSectors; ++Index)
1138 ASpan.Blocks.emplace_back(args: nullptr, args&: ScLen, args: Index * ScLen);
1139 for (int Index = 0; Index != NumSectors; ++Index) {
1140 ASpan.Blocks[Index].Seg.Val =
1141 reinterpret_cast<Value *>(&ASpan.Blocks[Index]);
1142 }
1143
1144 // Multiple values from VSpan can map to the same value in ASpan. Since we
1145 // try to create loads lazily, we need to find the earliest use for each
1146 // value from ASpan.
1147 DenseMap<void *, Instruction *> EarliestUser;
1148 auto isEarlier = [](Instruction *A, Instruction *B) {
1149 if (B == nullptr)
1150 return true;
1151 if (A == nullptr)
1152 return false;
1153 assert(A->getParent() == B->getParent());
1154 return A->comesBefore(Other: B);
1155 };
1156 auto earliestUser = [&](const auto &Uses) {
1157 Instruction *User = nullptr;
1158 for (const Use &U : Uses) {
1159 auto *I = dyn_cast<Instruction>(Val: U.getUser());
1160 assert(I != nullptr && "Load used in a non-instruction?");
1161 // Make sure we only consider users in this block, but we need
1162 // to remember if there were users outside the block too. This is
1163 // because if no users are found, aligned loads will not be created.
1164 if (I->getParent() == BaseBlock) {
1165 if (!isa<PHINode>(Val: I))
1166 User = std::min(a: User, b: I, comp: isEarlier);
1167 } else {
1168 User = std::min(a: User, b: BaseBlock->getTerminator(), comp: isEarlier);
1169 }
1170 }
1171 return User;
1172 };
1173
1174 for (const ByteSpan::Block &B : VSpan) {
1175 ByteSpan ASection = ASpan.section(Start: B.Pos, Length: B.Seg.Size);
1176 for (const ByteSpan::Block &S : ASection) {
1177 EarliestUser[S.Seg.Val] = std::min(
1178 a: EarliestUser[S.Seg.Val], b: earliestUser(B.Seg.Val->uses()), comp: isEarlier);
1179 }
1180 }
1181
1182 LLVM_DEBUG({
1183 dbgs() << "ASpan:\n" << ASpan << '\n';
1184 dbgs() << "Earliest users of ASpan:\n";
1185 for (auto &[Val, User] : EarliestUser) {
1186 dbgs() << Val << "\n ->" << *User << '\n';
1187 }
1188 });
1189
1190 auto createLoad = [&](IRBuilderBase &Builder, const ByteSpan &VSpan,
1191 int Index, bool MakePred) {
1192 Value *Ptr =
1193 createAdjustedPointer(Builder, Ptr: AlignAddr, ValTy: SecTy, Adjust: Index * ScLen);
1194 Value *Predicate =
1195 MakePred ? makeTestIfUnaligned(Builder, AlignVal, Alignment: ScLen) : nullptr;
1196
1197 // If vector shifting is potentially needed, accumulate metadata
1198 // from source sections of twice the load width.
1199 int Start = (Index - DoAlign) * ScLen;
1200 int Width = (1 + DoAlign) * ScLen;
1201 return this->createLoad(Builder, ValTy: SecTy, Ptr, Predicate, Alignment: ScLen, Mask: True, PassThru: Undef,
1202 MDSources: VSpan.section(Start, Length: Width).values());
1203 };
1204
1205 auto moveBefore = [this](Instruction *In, Instruction *To) {
1206 // Move In and its upward dependencies to before To.
1207 assert(In->getParent() == To->getParent());
1208 DepList Deps = getUpwardDeps(In, Base: To);
1209 In->moveBefore(MovePos: To);
1210 // DepList is sorted with respect to positions in the basic block.
1211 InstMap Map = cloneBefore(To: In, Insts&: Deps);
1212 for (auto [Old, New] : Map)
1213 In->replaceUsesOfWith(From: Old, To: New);
1214 };
1215
1216 // Generate necessary loads at appropriate locations.
1217 LLVM_DEBUG(dbgs() << "Creating loads for ASpan sectors\n");
1218 for (int Index = 0; Index != NumSectors + 1; ++Index) {
1219 // In ASpan, each block will be either a single aligned load, or a
1220 // valign of a pair of loads. In the latter case, an aligned load j
1221 // will belong to the current valign, and the one in the previous
1222 // block (for j > 0).
1223 // Place the load at a location which will dominate the valign, assuming
1224 // the valign will be placed right before the earliest user.
1225 Instruction *PrevAt =
1226 DoAlign && Index > 0 ? EarliestUser[&ASpan[Index - 1]] : nullptr;
1227 Instruction *ThisAt =
1228 Index < NumSectors ? EarliestUser[&ASpan[Index]] : nullptr;
1229 if (auto *Where = std::min(a: PrevAt, b: ThisAt, comp: isEarlier)) {
1230 Builder.SetInsertPoint(Where);
1231 Loads[Index] =
1232 createLoad(Builder, VSpan, Index, DoAlign && Index == NumSectors);
1233 // We know it's safe to put the load at BasePos, but we'd prefer to put
1234 // it at "Where". To see if the load is safe to be placed at Where, put
1235 // it there first and then check if it's safe to move it to BasePos.
1236 // If not, then the load needs to be placed at BasePos.
1237 // We can't do this check proactively because we need the load to exist
1238 // in order to check legality.
1239 if (auto *Load = dyn_cast<Instruction>(Val: Loads[Index])) {
1240 if (!HVC.isSafeToMoveBeforeInBB(In: *Load, To: BasePos))
1241 moveBefore(Load, &*BasePos);
1242 }
1243 LLVM_DEBUG(dbgs() << "Loads[" << Index << "]:" << *Loads[Index] << '\n');
1244 }
1245 }
1246
1247 // Generate valigns if needed, and fill in proper values in ASpan
1248 LLVM_DEBUG(dbgs() << "Creating values for ASpan sectors\n");
1249 for (int Index = 0; Index != NumSectors; ++Index) {
1250 ASpan[Index].Seg.Val = nullptr;
1251 if (auto *Where = EarliestUser[&ASpan[Index]]) {
1252 Builder.SetInsertPoint(Where);
1253 Value *Val = Loads[Index];
1254 assert(Val != nullptr);
1255 if (DoAlign) {
1256 Value *NextLoad = Loads[Index + 1];
1257 assert(NextLoad != nullptr);
1258 Val = HVC.vralignb(Builder, Lo: Val, Hi: NextLoad, Amt: AlignVal);
1259 }
1260 ASpan[Index].Seg.Val = Val;
1261 LLVM_DEBUG(dbgs() << "ASpan[" << Index << "]:" << *Val << '\n');
1262 }
1263 }
1264
1265 for (const ByteSpan::Block &B : VSpan) {
1266 ByteSpan ASection = ASpan.section(Start: B.Pos, Length: B.Seg.Size).shift(Offset: -B.Pos);
1267 Value *Accum = UndefValue::get(T: HVC.getByteTy(ElemCount: B.Seg.Size));
1268 Builder.SetInsertPoint(cast<Instruction>(Val: B.Seg.Val));
1269
1270 // We're generating a reduction, where each instruction depends on
1271 // the previous one, so we need to order them according to the position
1272 // of their inputs in the code.
1273 std::vector<ByteSpan::Block *> ABlocks;
1274 for (ByteSpan::Block &S : ASection) {
1275 if (S.Seg.Val != nullptr)
1276 ABlocks.push_back(x: &S);
1277 }
1278 llvm::sort(C&: ABlocks,
1279 Comp: [&](const ByteSpan::Block *A, const ByteSpan::Block *B) {
1280 return isEarlier(cast<Instruction>(Val: A->Seg.Val),
1281 cast<Instruction>(Val: B->Seg.Val));
1282 });
1283 for (ByteSpan::Block *S : ABlocks) {
1284 // The processing of the data loaded by the aligned loads
1285 // needs to be inserted after the data is available.
1286 Instruction *SegI = cast<Instruction>(Val: S->Seg.Val);
1287 Builder.SetInsertPoint(&*std::next(x: SegI->getIterator()));
1288 Value *Pay = HVC.vbytes(Builder, Val: getPayload(Val: S->Seg.Val));
1289 Accum =
1290 HVC.insertb(Builder, Dest: Accum, Src: Pay, Start: S->Seg.Start, Length: S->Seg.Size, Where: S->Pos);
1291 }
1292 // Instead of casting everything to bytes for the vselect, cast to the
1293 // original value type. This will avoid complications with casting masks.
1294 // For example, in cases when the original mask applied to i32, it could
1295 // be converted to a mask applicable to i8 via pred_typecast intrinsic,
1296 // but if the mask is not exactly of HVX length, extra handling would be
1297 // needed to make it work.
1298 Type *ValTy = getPayload(Val: B.Seg.Val)->getType();
1299 Value *Cast = Builder.CreateBitCast(V: Accum, DestTy: ValTy, Name: "cst");
1300 Value *Sel = Builder.CreateSelect(C: getMask(Val: B.Seg.Val), True: Cast,
1301 False: getPassThrough(Val: B.Seg.Val), Name: "sel");
1302 B.Seg.Val->replaceAllUsesWith(V: Sel);
1303 }
1304}
1305
1306auto AlignVectors::realignStoreGroup(IRBuilderBase &Builder,
1307 const ByteSpan &VSpan, int ScLen,
1308 Value *AlignVal, Value *AlignAddr) const
1309 -> void {
1310 LLVM_DEBUG(dbgs() << __func__ << "\n");
1311
1312 Type *SecTy = HVC.getByteTy(ElemCount: ScLen);
1313 int NumSectors = (VSpan.extent() + ScLen - 1) / ScLen;
1314 bool DoAlign = !HVC.isZero(Val: AlignVal);
1315
1316 // Stores.
1317 ByteSpan ASpanV, ASpanM;
1318
1319 // Return a vector value corresponding to the input value Val:
1320 // either <1 x Val> for scalar Val, or Val itself for vector Val.
1321 auto MakeVec = [](IRBuilderBase &Builder, Value *Val) -> Value * {
1322 Type *Ty = Val->getType();
1323 if (Ty->isVectorTy())
1324 return Val;
1325 auto *VecTy = VectorType::get(ElementType: Ty, NumElements: 1, /*Scalable=*/false);
1326 return Builder.CreateBitCast(V: Val, DestTy: VecTy, Name: "cst");
1327 };
1328
1329 // Create an extra "undef" sector at the beginning and at the end.
1330 // They will be used as the left/right filler in the vlalign step.
1331 for (int Index = (DoAlign ? -1 : 0); Index != NumSectors + DoAlign; ++Index) {
1332 // For stores, the size of each section is an aligned vector length.
1333 // Adjust the store offsets relative to the section start offset.
1334 ByteSpan VSection =
1335 VSpan.section(Start: Index * ScLen, Length: ScLen).shift(Offset: -Index * ScLen);
1336 Value *Undef = UndefValue::get(T: SecTy);
1337 Value *Zero = HVC.getNullValue(Ty: SecTy);
1338 Value *AccumV = Undef;
1339 Value *AccumM = Zero;
1340 for (ByteSpan::Block &S : VSection) {
1341 Value *Pay = getPayload(Val: S.Seg.Val);
1342 Value *Mask = HVC.rescale(Builder, Mask: MakeVec(Builder, getMask(Val: S.Seg.Val)),
1343 FromTy: Pay->getType(), ToTy: HVC.getByteTy());
1344 Value *PartM = HVC.insertb(Builder, Dest: Zero, Src: HVC.vbytes(Builder, Val: Mask),
1345 Start: S.Seg.Start, Length: S.Seg.Size, Where: S.Pos);
1346 AccumM = Builder.CreateOr(LHS: AccumM, RHS: PartM);
1347
1348 Value *PartV = HVC.insertb(Builder, Dest: Undef, Src: HVC.vbytes(Builder, Val: Pay),
1349 Start: S.Seg.Start, Length: S.Seg.Size, Where: S.Pos);
1350
1351 AccumV = Builder.CreateSelect(
1352 C: Builder.CreateICmp(P: CmpInst::ICMP_NE, LHS: PartM, RHS: Zero), True: PartV, False: AccumV);
1353 }
1354 ASpanV.Blocks.emplace_back(args&: AccumV, args&: ScLen, args: Index * ScLen);
1355 ASpanM.Blocks.emplace_back(args&: AccumM, args&: ScLen, args: Index * ScLen);
1356 }
1357
1358 LLVM_DEBUG({
1359 dbgs() << "ASpanV before vlalign:\n" << ASpanV << '\n';
1360 dbgs() << "ASpanM before vlalign:\n" << ASpanM << '\n';
1361 });
1362
1363 // vlalign
1364 if (DoAlign) {
1365 for (int Index = 1; Index != NumSectors + 2; ++Index) {
1366 Value *PrevV = ASpanV[Index - 1].Seg.Val, *ThisV = ASpanV[Index].Seg.Val;
1367 Value *PrevM = ASpanM[Index - 1].Seg.Val, *ThisM = ASpanM[Index].Seg.Val;
1368 assert(isSectorTy(PrevV->getType()) && isSectorTy(PrevM->getType()));
1369 ASpanV[Index - 1].Seg.Val = HVC.vlalignb(Builder, Lo: PrevV, Hi: ThisV, Amt: AlignVal);
1370 ASpanM[Index - 1].Seg.Val = HVC.vlalignb(Builder, Lo: PrevM, Hi: ThisM, Amt: AlignVal);
1371 }
1372 }
1373
1374 LLVM_DEBUG({
1375 dbgs() << "ASpanV after vlalign:\n" << ASpanV << '\n';
1376 dbgs() << "ASpanM after vlalign:\n" << ASpanM << '\n';
1377 });
1378
1379 auto createStore = [&](IRBuilderBase &Builder, const ByteSpan &ASpanV,
1380 const ByteSpan &ASpanM, int Index, bool MakePred) {
1381 Value *Val = ASpanV[Index].Seg.Val;
1382 Value *Mask = ASpanM[Index].Seg.Val; // bytes
1383 if (HVC.isUndef(Val) || HVC.isZero(Val: Mask))
1384 return;
1385 Value *Ptr =
1386 createAdjustedPointer(Builder, Ptr: AlignAddr, ValTy: SecTy, Adjust: Index * ScLen);
1387 Value *Predicate =
1388 MakePred ? makeTestIfUnaligned(Builder, AlignVal, Alignment: ScLen) : nullptr;
1389
1390 // If vector shifting is potentially needed, accumulate metadata
1391 // from source sections of twice the store width.
1392 int Start = (Index - DoAlign) * ScLen;
1393 int Width = (1 + DoAlign) * ScLen;
1394 this->createStore(Builder, Val, Ptr, Predicate, Alignment: ScLen,
1395 Mask: HVC.vlsb(Builder, Val: Mask),
1396 MDSources: VSpan.section(Start, Length: Width).values());
1397 };
1398
1399 for (int Index = 0; Index != NumSectors + DoAlign; ++Index) {
1400 createStore(Builder, ASpanV, ASpanM, Index, DoAlign && Index == NumSectors);
1401 }
1402}
1403
1404auto AlignVectors::realignGroup(const MoveGroup &Move) const -> bool {
1405 LLVM_DEBUG(dbgs() << "Realigning group:\n" << Move << '\n');
1406
1407 // TODO: Needs support for masked loads/stores of "scalar" vectors.
1408 if (!Move.IsHvx)
1409 return false;
1410
1411 // Return the element with the maximum alignment from Range,
1412 // where GetValue obtains the value to compare from an element.
1413 auto getMaxOf = [](auto Range, auto GetValue) {
1414 return *llvm::max_element(Range, [&GetValue](auto &A, auto &B) {
1415 return GetValue(A) < GetValue(B);
1416 });
1417 };
1418
1419 const AddrList &BaseInfos = AddrGroups.at(k: Move.Base);
1420
1421 // Conceptually, there is a vector of N bytes covering the addresses
1422 // starting from the minimum offset (i.e. Base.Addr+Start). This vector
1423 // represents a contiguous memory region that spans all accessed memory
1424 // locations.
1425 // The correspondence between loaded or stored values will be expressed
1426 // in terms of this vector. For example, the 0th element of the vector
1427 // from the Base address info will start at byte Start from the beginning
1428 // of this conceptual vector.
1429 //
1430 // This vector will be loaded/stored starting at the nearest down-aligned
1431 // address and the amount od the down-alignment will be AlignVal:
1432 // valign(load_vector(align_down(Base+Start)), AlignVal)
1433
1434 std::set<Instruction *> TestSet(Move.Main.begin(), Move.Main.end());
1435 AddrList MoveInfos;
1436 llvm::copy_if(
1437 Range: BaseInfos, Out: std::back_inserter(x&: MoveInfos),
1438 P: [&TestSet](const AddrInfo &AI) { return TestSet.count(x: AI.Inst); });
1439
1440 // Maximum alignment present in the whole address group.
1441 const AddrInfo &WithMaxAlign =
1442 getMaxOf(MoveInfos, [](const AddrInfo &AI) { return AI.HaveAlign; });
1443 Align MaxGiven = WithMaxAlign.HaveAlign;
1444
1445 // Minimum alignment present in the move address group.
1446 const AddrInfo &WithMinOffset =
1447 getMaxOf(MoveInfos, [](const AddrInfo &AI) { return -AI.Offset; });
1448
1449 const AddrInfo &WithMaxNeeded =
1450 getMaxOf(MoveInfos, [](const AddrInfo &AI) { return AI.NeedAlign; });
1451 Align MinNeeded = WithMaxNeeded.NeedAlign;
1452
1453 // Set the builder's insertion point right before the load group, or
1454 // immediately after the store group. (Instructions in a store group are
1455 // listed in reverse order.)
1456 Instruction *InsertAt = Move.Main.front();
1457 if (!Move.IsLoad) {
1458 // There should be a terminator (which store isn't, but check anyways).
1459 assert(InsertAt->getIterator() != InsertAt->getParent()->end());
1460 InsertAt = &*std::next(x: InsertAt->getIterator());
1461 }
1462
1463 IRBuilder Builder(InsertAt->getParent(), InsertAt->getIterator(),
1464 InstSimplifyFolder(HVC.DL));
1465 Value *AlignAddr = nullptr; // Actual aligned address.
1466 Value *AlignVal = nullptr; // Right-shift amount (for valign).
1467
1468 if (MinNeeded <= MaxGiven) {
1469 int Start = WithMinOffset.Offset;
1470 int OffAtMax = WithMaxAlign.Offset;
1471 // Shift the offset of the maximally aligned instruction (OffAtMax)
1472 // back by just enough multiples of the required alignment to cover the
1473 // distance from Start to OffAtMax.
1474 // Calculate the address adjustment amount based on the address with the
1475 // maximum alignment. This is to allow a simple gep instruction instead
1476 // of potential bitcasts to i8*.
1477 int Adjust = -alignTo(Value: OffAtMax - Start, Align: MinNeeded.value());
1478 AlignAddr = createAdjustedPointer(Builder, Ptr: WithMaxAlign.Addr,
1479 ValTy: WithMaxAlign.ValTy, Adjust, CloneMap: Move.Clones);
1480 int Diff = Start - (OffAtMax + Adjust);
1481 AlignVal = HVC.getConstInt(Val: Diff);
1482 assert(Diff >= 0);
1483 assert(static_cast<decltype(MinNeeded.value())>(Diff) < MinNeeded.value());
1484 } else {
1485 // WithMinOffset is the lowest address in the group,
1486 // WithMinOffset.Addr = Base+Start.
1487 // Align instructions for both HVX (V6_valign) and scalar (S2_valignrb)
1488 // mask off unnecessary bits, so it's ok to just the original pointer as
1489 // the alignment amount.
1490 // Do an explicit down-alignment of the address to avoid creating an
1491 // aligned instruction with an address that is not really aligned.
1492 AlignAddr =
1493 createAlignedPointer(Builder, Ptr: WithMinOffset.Addr, ValTy: WithMinOffset.ValTy,
1494 Alignment: MinNeeded.value(), CloneMap: Move.Clones);
1495 AlignVal =
1496 Builder.CreatePtrToInt(V: WithMinOffset.Addr, DestTy: HVC.getIntTy(), Name: "pti");
1497 if (auto *I = dyn_cast<Instruction>(Val: AlignVal)) {
1498 for (auto [Old, New] : Move.Clones)
1499 I->replaceUsesOfWith(From: Old, To: New);
1500 }
1501 }
1502
1503 ByteSpan VSpan;
1504 for (const AddrInfo &AI : MoveInfos) {
1505 VSpan.Blocks.emplace_back(args: AI.Inst, args: HVC.getSizeOf(Ty: AI.ValTy),
1506 args: AI.Offset - WithMinOffset.Offset);
1507 }
1508
1509 // The aligned loads/stores will use blocks that are either scalars,
1510 // or HVX vectors. Let "sector" be the unified term for such a block.
1511 // blend(scalar, vector) -> sector...
1512 int ScLen = Move.IsHvx ? HVC.HST.getVectorLength()
1513 : std::max<int>(a: MinNeeded.value(), b: 4);
1514 assert(!Move.IsHvx || ScLen == 64 || ScLen == 128);
1515 assert(Move.IsHvx || ScLen == 4 || ScLen == 8);
1516
1517 LLVM_DEBUG({
1518 dbgs() << "ScLen: " << ScLen << "\n";
1519 dbgs() << "AlignVal:" << *AlignVal << "\n";
1520 dbgs() << "AlignAddr:" << *AlignAddr << "\n";
1521 dbgs() << "VSpan:\n" << VSpan << '\n';
1522 });
1523
1524 if (Move.IsLoad)
1525 realignLoadGroup(Builder, VSpan, ScLen, AlignVal, AlignAddr);
1526 else
1527 realignStoreGroup(Builder, VSpan, ScLen, AlignVal, AlignAddr);
1528
1529 for (auto *Inst : Move.Main)
1530 Inst->eraseFromParent();
1531
1532 return true;
1533}
1534
1535auto AlignVectors::makeTestIfUnaligned(IRBuilderBase &Builder, Value *AlignVal,
1536 int Alignment) const -> Value * {
1537 auto *AlignTy = AlignVal->getType();
1538 Value *And = Builder.CreateAnd(
1539 LHS: AlignVal, RHS: ConstantInt::get(Ty: AlignTy, V: Alignment - 1), Name: "and");
1540 Value *Zero = ConstantInt::get(Ty: AlignTy, V: 0);
1541 return Builder.CreateICmpNE(LHS: And, RHS: Zero, Name: "isz");
1542}
1543
1544auto AlignVectors::isSectorTy(Type *Ty) const -> bool {
1545 if (!HVC.isByteVecTy(Ty))
1546 return false;
1547 int Size = HVC.getSizeOf(Ty);
1548 if (HVC.HST.isTypeForHVX(VecTy: Ty))
1549 return Size == static_cast<int>(HVC.HST.getVectorLength());
1550 return Size == 4 || Size == 8;
1551}
1552
1553auto AlignVectors::run() -> bool {
1554 LLVM_DEBUG(dbgs() << "Running HVC::AlignVectors on " << HVC.F.getName()
1555 << '\n');
1556 if (!createAddressGroups())
1557 return false;
1558
1559 LLVM_DEBUG({
1560 dbgs() << "Address groups(" << AddrGroups.size() << "):\n";
1561 for (auto &[In, AL] : AddrGroups) {
1562 for (const AddrInfo &AI : AL)
1563 dbgs() << "---\n" << AI << '\n';
1564 }
1565 });
1566
1567 bool Changed = false;
1568 MoveList LoadGroups, StoreGroups;
1569
1570 for (auto &G : AddrGroups) {
1571 llvm::append_range(C&: LoadGroups, R: createLoadGroups(Group: G.second));
1572 llvm::append_range(C&: StoreGroups, R: createStoreGroups(Group: G.second));
1573 }
1574
1575 LLVM_DEBUG({
1576 dbgs() << "\nLoad groups(" << LoadGroups.size() << "):\n";
1577 for (const MoveGroup &G : LoadGroups)
1578 dbgs() << G << "\n";
1579 dbgs() << "Store groups(" << StoreGroups.size() << "):\n";
1580 for (const MoveGroup &G : StoreGroups)
1581 dbgs() << G << "\n";
1582 });
1583
1584 // Cumulative limit on the number of groups.
1585 unsigned CountLimit = VAGroupCountLimit;
1586 if (CountLimit == 0)
1587 return false;
1588
1589 if (LoadGroups.size() > CountLimit) {
1590 LoadGroups.resize(new_size: CountLimit);
1591 StoreGroups.clear();
1592 } else {
1593 unsigned StoreLimit = CountLimit - LoadGroups.size();
1594 if (StoreGroups.size() > StoreLimit)
1595 StoreGroups.resize(new_size: StoreLimit);
1596 }
1597
1598 for (auto &M : LoadGroups)
1599 Changed |= moveTogether(Move&: M);
1600 for (auto &M : StoreGroups)
1601 Changed |= moveTogether(Move&: M);
1602
1603 LLVM_DEBUG(dbgs() << "After moveTogether:\n" << HVC.F);
1604
1605 for (auto &M : LoadGroups)
1606 Changed |= realignGroup(Move: M);
1607 for (auto &M : StoreGroups)
1608 Changed |= realignGroup(Move: M);
1609
1610 return Changed;
1611}
1612
1613// --- End AlignVectors
1614
1615// --- Begin HvxIdioms
1616
1617auto HvxIdioms::getNumSignificantBits(Value *V, Instruction *In) const
1618 -> std::pair<unsigned, Signedness> {
1619 unsigned Bits = HVC.getNumSignificantBits(V, CtxI: In);
1620 // The significant bits are calculated including the sign bit. This may
1621 // add an extra bit for zero-extended values, e.g. (zext i32 to i64) may
1622 // result in 33 significant bits. To avoid extra words, skip the extra
1623 // sign bit, but keep information that the value is to be treated as
1624 // unsigned.
1625 KnownBits Known = HVC.getKnownBits(V, CtxI: In);
1626 Signedness Sign = Signed;
1627 unsigned NumToTest = 0; // Number of bits used in test for unsignedness.
1628 if (isPowerOf2_32(Value: Bits))
1629 NumToTest = Bits;
1630 else if (Bits > 1 && isPowerOf2_32(Value: Bits - 1))
1631 NumToTest = Bits - 1;
1632
1633 if (NumToTest != 0 && Known.Zero.ashr(ShiftAmt: NumToTest).isAllOnes()) {
1634 Sign = Unsigned;
1635 Bits = NumToTest;
1636 }
1637
1638 // If the top bit of the nearest power-of-2 is zero, this value is
1639 // positive. It could be treated as either signed or unsigned.
1640 if (unsigned Pow2 = PowerOf2Ceil(A: Bits); Pow2 != Bits) {
1641 if (Known.Zero.ashr(ShiftAmt: Pow2 - 1).isAllOnes())
1642 Sign = Positive;
1643 }
1644 return {Bits, Sign};
1645}
1646
1647auto HvxIdioms::canonSgn(SValue X, SValue Y) const
1648 -> std::pair<SValue, SValue> {
1649 // Canonicalize the signedness of X and Y, so that the result is one of:
1650 // S, S
1651 // U/P, S
1652 // U/P, U/P
1653 if (X.Sgn == Signed && Y.Sgn != Signed)
1654 std::swap(a&: X, b&: Y);
1655 return {X, Y};
1656}
1657
1658// Match
1659// (X * Y) [>> N], or
1660// ((X * Y) + (1 << M)) >> N
1661auto HvxIdioms::matchFxpMul(Instruction &In) const -> std::optional<FxpOp> {
1662 using namespace PatternMatch;
1663 auto *Ty = In.getType();
1664
1665 if (!Ty->isVectorTy() || !Ty->getScalarType()->isIntegerTy())
1666 return std::nullopt;
1667
1668 unsigned Width = cast<IntegerType>(Val: Ty->getScalarType())->getBitWidth();
1669
1670 FxpOp Op;
1671 Value *Exp = &In;
1672
1673 // Fixed-point multiplication is always shifted right (except when the
1674 // fraction is 0 bits).
1675 auto m_Shr = [](auto &&V, auto &&S) {
1676 return m_CombineOr(m_LShr(V, S), m_AShr(V, S));
1677 };
1678
1679 const APInt *Qn = nullptr;
1680 if (Value * T; match(V: Exp, P: m_Shr(m_Value(V&: T), m_APInt(Res&: Qn)))) {
1681 Op.Frac = Qn->getZExtValue();
1682 Exp = T;
1683 } else {
1684 Op.Frac = 0;
1685 }
1686
1687 if (Op.Frac > Width)
1688 return std::nullopt;
1689
1690 // Check if there is rounding added.
1691 const APInt *C = nullptr;
1692 if (Value * T; Op.Frac > 0 && match(V: Exp, P: m_Add(L: m_Value(V&: T), R: m_APInt(Res&: C)))) {
1693 uint64_t CV = C->getZExtValue();
1694 if (CV != 0 && !isPowerOf2_64(Value: CV))
1695 return std::nullopt;
1696 if (CV != 0)
1697 Op.RoundAt = Log2_64(Value: CV);
1698 Exp = T;
1699 }
1700
1701 // Check if the rest is a multiplication.
1702 if (match(V: Exp, P: m_Mul(L: m_Value(V&: Op.X.Val), R: m_Value(V&: Op.Y.Val)))) {
1703 Op.Opcode = Instruction::Mul;
1704 // FIXME: The information below is recomputed.
1705 Op.X.Sgn = getNumSignificantBits(V: Op.X.Val, In: &In).second;
1706 Op.Y.Sgn = getNumSignificantBits(V: Op.Y.Val, In: &In).second;
1707 Op.ResTy = cast<VectorType>(Val: Ty);
1708 return Op;
1709 }
1710
1711 return std::nullopt;
1712}
1713
1714auto HvxIdioms::processFxpMul(Instruction &In, const FxpOp &Op) const
1715 -> Value * {
1716 assert(Op.X.Val->getType() == Op.Y.Val->getType());
1717
1718 auto *VecTy = dyn_cast<VectorType>(Val: Op.X.Val->getType());
1719 if (VecTy == nullptr)
1720 return nullptr;
1721 auto *ElemTy = cast<IntegerType>(Val: VecTy->getElementType());
1722 unsigned ElemWidth = ElemTy->getBitWidth();
1723
1724 // TODO: This can be relaxed after legalization is done pre-isel.
1725 if ((HVC.length(Ty: VecTy) * ElemWidth) % (8 * HVC.HST.getVectorLength()) != 0)
1726 return nullptr;
1727
1728 // There are no special intrinsics that should be used for multiplying
1729 // signed 8-bit values, so just skip them. Normal codegen should handle
1730 // this just fine.
1731 if (ElemWidth <= 8)
1732 return nullptr;
1733 // Similarly, if this is just a multiplication that can be handled without
1734 // intervention, then leave it alone.
1735 if (ElemWidth <= 32 && Op.Frac == 0)
1736 return nullptr;
1737
1738 auto [BitsX, SignX] = getNumSignificantBits(V: Op.X.Val, In: &In);
1739 auto [BitsY, SignY] = getNumSignificantBits(V: Op.Y.Val, In: &In);
1740
1741 // TODO: Add multiplication of vectors by scalar registers (up to 4 bytes).
1742
1743 Value *X = Op.X.Val, *Y = Op.Y.Val;
1744 IRBuilder Builder(In.getParent(), In.getIterator(),
1745 InstSimplifyFolder(HVC.DL));
1746
1747 auto roundUpWidth = [](unsigned Width) -> unsigned {
1748 if (Width <= 32 && !isPowerOf2_32(Value: Width)) {
1749 // If the element width is not a power of 2, round it up
1750 // to the next one. Do this for widths not exceeding 32.
1751 return PowerOf2Ceil(A: Width);
1752 }
1753 if (Width > 32 && Width % 32 != 0) {
1754 // For wider elements, round it up to the multiple of 32.
1755 return alignTo(Value: Width, Align: 32u);
1756 }
1757 return Width;
1758 };
1759
1760 BitsX = roundUpWidth(BitsX);
1761 BitsY = roundUpWidth(BitsY);
1762
1763 // For elementwise multiplication vectors must have the same lengths, so
1764 // resize the elements of both inputs to the same width, the max of the
1765 // calculated significant bits.
1766 unsigned Width = std::max(a: BitsX, b: BitsY);
1767
1768 auto *ResizeTy = VectorType::get(ElementType: HVC.getIntTy(Width), Other: VecTy);
1769 if (Width < ElemWidth) {
1770 X = Builder.CreateTrunc(V: X, DestTy: ResizeTy, Name: "trn");
1771 Y = Builder.CreateTrunc(V: Y, DestTy: ResizeTy, Name: "trn");
1772 } else if (Width > ElemWidth) {
1773 X = SignX == Signed ? Builder.CreateSExt(V: X, DestTy: ResizeTy, Name: "sxt")
1774 : Builder.CreateZExt(V: X, DestTy: ResizeTy, Name: "zxt");
1775 Y = SignY == Signed ? Builder.CreateSExt(V: Y, DestTy: ResizeTy, Name: "sxt")
1776 : Builder.CreateZExt(V: Y, DestTy: ResizeTy, Name: "zxt");
1777 };
1778
1779 assert(X->getType() == Y->getType() && X->getType() == ResizeTy);
1780
1781 unsigned VecLen = HVC.length(Ty: ResizeTy);
1782 unsigned ChopLen = (8 * HVC.HST.getVectorLength()) / std::min(a: Width, b: 32u);
1783
1784 SmallVector<Value *> Results;
1785 FxpOp ChopOp = Op;
1786 ChopOp.ResTy = VectorType::get(ElementType: Op.ResTy->getElementType(), NumElements: ChopLen, Scalable: false);
1787
1788 for (unsigned V = 0; V != VecLen / ChopLen; ++V) {
1789 ChopOp.X.Val = HVC.subvector(Builder, Val: X, Start: V * ChopLen, Length: ChopLen);
1790 ChopOp.Y.Val = HVC.subvector(Builder, Val: Y, Start: V * ChopLen, Length: ChopLen);
1791 Results.push_back(Elt: processFxpMulChopped(Builder, In, Op: ChopOp));
1792 if (Results.back() == nullptr)
1793 break;
1794 }
1795
1796 if (Results.empty() || Results.back() == nullptr)
1797 return nullptr;
1798
1799 Value *Cat = HVC.concat(Builder, Vecs: Results);
1800 Value *Ext = SignX == Signed || SignY == Signed
1801 ? Builder.CreateSExt(V: Cat, DestTy: VecTy, Name: "sxt")
1802 : Builder.CreateZExt(V: Cat, DestTy: VecTy, Name: "zxt");
1803 return Ext;
1804}
1805
1806auto HvxIdioms::processFxpMulChopped(IRBuilderBase &Builder, Instruction &In,
1807 const FxpOp &Op) const -> Value * {
1808 assert(Op.X.Val->getType() == Op.Y.Val->getType());
1809 auto *InpTy = cast<VectorType>(Val: Op.X.Val->getType());
1810 unsigned Width = InpTy->getScalarSizeInBits();
1811 bool Rounding = Op.RoundAt.has_value();
1812
1813 if (!Op.RoundAt || *Op.RoundAt == Op.Frac - 1) {
1814 // The fixed-point intrinsics do signed multiplication.
1815 if (Width == Op.Frac + 1 && Op.X.Sgn != Unsigned && Op.Y.Sgn != Unsigned) {
1816 Value *QMul = nullptr;
1817 if (Width == 16) {
1818 QMul = createMulQ15(Builder, X: Op.X, Y: Op.Y, Rounding);
1819 } else if (Width == 32) {
1820 QMul = createMulQ31(Builder, X: Op.X, Y: Op.Y, Rounding);
1821 }
1822 if (QMul != nullptr)
1823 return QMul;
1824 }
1825 }
1826
1827 assert(Width >= 32 || isPowerOf2_32(Width)); // Width <= 32 => Width is 2^n
1828 assert(Width < 32 || Width % 32 == 0); // Width > 32 => Width is 32*k
1829
1830 // If Width < 32, then it should really be 16.
1831 if (Width < 32) {
1832 if (Width < 16)
1833 return nullptr;
1834 // Getting here with Op.Frac == 0 isn't wrong, but suboptimal: here we
1835 // generate a full precision products, which is unnecessary if there is
1836 // no shift.
1837 assert(Width == 16);
1838 assert(Op.Frac != 0 && "Unshifted mul should have been skipped");
1839 if (Op.Frac == 16) {
1840 // Multiply high
1841 if (Value *MulH = createMulH16(Builder, X: Op.X, Y: Op.Y))
1842 return MulH;
1843 }
1844 // Do full-precision multiply and shift.
1845 Value *Prod32 = createMul16(Builder, X: Op.X, Y: Op.Y);
1846 if (Rounding) {
1847 Value *RoundVal = HVC.getConstSplat(Ty: Prod32->getType(), Val: 1 << *Op.RoundAt);
1848 Prod32 = Builder.CreateAdd(LHS: Prod32, RHS: RoundVal, Name: "add");
1849 }
1850
1851 Value *ShiftAmt = HVC.getConstSplat(Ty: Prod32->getType(), Val: Op.Frac);
1852 Value *Shifted = Op.X.Sgn == Signed || Op.Y.Sgn == Signed
1853 ? Builder.CreateAShr(LHS: Prod32, RHS: ShiftAmt, Name: "asr")
1854 : Builder.CreateLShr(LHS: Prod32, RHS: ShiftAmt, Name: "lsr");
1855 return Builder.CreateTrunc(V: Shifted, DestTy: InpTy, Name: "trn");
1856 }
1857
1858 // Width >= 32
1859
1860 // Break up the arguments Op.X and Op.Y into vectors of smaller widths
1861 // in preparation of doing the multiplication by 32-bit parts.
1862 auto WordX = HVC.splitVectorElements(Builder, Vec: Op.X.Val, /*ToWidth=*/32);
1863 auto WordY = HVC.splitVectorElements(Builder, Vec: Op.Y.Val, /*ToWidth=*/32);
1864 auto WordP = createMulLong(Builder, WordX, SgnX: Op.X.Sgn, WordY, SgnY: Op.Y.Sgn);
1865
1866 auto *HvxWordTy = cast<VectorType>(Val: WordP.front()->getType());
1867
1868 // Add the optional rounding to the proper word.
1869 if (Op.RoundAt.has_value()) {
1870 Value *Zero = HVC.getNullValue(Ty: WordX[0]->getType());
1871 SmallVector<Value *> RoundV(WordP.size(), Zero);
1872 RoundV[*Op.RoundAt / 32] =
1873 HVC.getConstSplat(Ty: HvxWordTy, Val: 1 << (*Op.RoundAt % 32));
1874 WordP = createAddLong(Builder, WordX: WordP, WordY: RoundV);
1875 }
1876
1877 // createRightShiftLong?
1878
1879 // Shift all products right by Op.Frac.
1880 unsigned SkipWords = Op.Frac / 32;
1881 Constant *ShiftAmt = HVC.getConstSplat(Ty: HvxWordTy, Val: Op.Frac % 32);
1882
1883 for (int Dst = 0, End = WordP.size() - SkipWords; Dst != End; ++Dst) {
1884 int Src = Dst + SkipWords;
1885 Value *Lo = WordP[Src];
1886 if (Src + 1 < End) {
1887 Value *Hi = WordP[Src + 1];
1888 WordP[Dst] = Builder.CreateIntrinsic(RetTy: HvxWordTy, ID: Intrinsic::fshr,
1889 Args: {Hi, Lo, ShiftAmt},
1890 /*FMFSource*/ nullptr, Name: "int");
1891 } else {
1892 // The shift of the most significant word.
1893 WordP[Dst] = Builder.CreateAShr(LHS: Lo, RHS: ShiftAmt, Name: "asr");
1894 }
1895 }
1896 if (SkipWords != 0)
1897 WordP.resize(N: WordP.size() - SkipWords);
1898
1899 return HVC.joinVectorElements(Builder, Values: WordP, ToType: Op.ResTy);
1900}
1901
1902auto HvxIdioms::createMulQ15(IRBuilderBase &Builder, SValue X, SValue Y,
1903 bool Rounding) const -> Value * {
1904 assert(X.Val->getType() == Y.Val->getType());
1905 assert(X.Val->getType()->getScalarType() == HVC.getIntTy(16));
1906 assert(HVC.HST.isHVXVectorType(EVT::getEVT(X.Val->getType(), false)));
1907
1908 // There is no non-rounding intrinsic for i16.
1909 if (!Rounding || X.Sgn == Unsigned || Y.Sgn == Unsigned)
1910 return nullptr;
1911
1912 auto V6_vmpyhvsrs = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vmpyhvsrs);
1913 return HVC.createHvxIntrinsic(Builder, IntID: V6_vmpyhvsrs, RetTy: X.Val->getType(),
1914 Args: {X.Val, Y.Val});
1915}
1916
1917auto HvxIdioms::createMulQ31(IRBuilderBase &Builder, SValue X, SValue Y,
1918 bool Rounding) const -> Value * {
1919 Type *InpTy = X.Val->getType();
1920 assert(InpTy == Y.Val->getType());
1921 assert(InpTy->getScalarType() == HVC.getIntTy(32));
1922 assert(HVC.HST.isHVXVectorType(EVT::getEVT(InpTy, false)));
1923
1924 if (X.Sgn == Unsigned || Y.Sgn == Unsigned)
1925 return nullptr;
1926
1927 auto V6_vmpyewuh = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vmpyewuh);
1928 auto V6_vmpyo_acc = Rounding
1929 ? HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vmpyowh_rnd_sacc)
1930 : HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vmpyowh_sacc);
1931 Value *V1 =
1932 HVC.createHvxIntrinsic(Builder, IntID: V6_vmpyewuh, RetTy: InpTy, Args: {X.Val, Y.Val});
1933 return HVC.createHvxIntrinsic(Builder, IntID: V6_vmpyo_acc, RetTy: InpTy,
1934 Args: {V1, X.Val, Y.Val});
1935}
1936
1937auto HvxIdioms::createAddCarry(IRBuilderBase &Builder, Value *X, Value *Y,
1938 Value *CarryIn) const
1939 -> std::pair<Value *, Value *> {
1940 assert(X->getType() == Y->getType());
1941 auto VecTy = cast<VectorType>(Val: X->getType());
1942 if (VecTy == HvxI32Ty && HVC.HST.useHVXV62Ops()) {
1943 SmallVector<Value *> Args = {X, Y};
1944 Intrinsic::ID AddCarry;
1945 if (CarryIn == nullptr && HVC.HST.useHVXV66Ops()) {
1946 AddCarry = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vaddcarryo);
1947 } else {
1948 AddCarry = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vaddcarry);
1949 if (CarryIn == nullptr)
1950 CarryIn = HVC.getNullValue(Ty: HVC.getBoolTy(ElemCount: HVC.length(Ty: VecTy)));
1951 Args.push_back(Elt: CarryIn);
1952 }
1953 Value *Ret = HVC.createHvxIntrinsic(Builder, IntID: AddCarry,
1954 /*RetTy=*/nullptr, Args);
1955 Value *Result = Builder.CreateExtractValue(Agg: Ret, Idxs: {0}, Name: "ext");
1956 Value *CarryOut = Builder.CreateExtractValue(Agg: Ret, Idxs: {1}, Name: "ext");
1957 return {Result, CarryOut};
1958 }
1959
1960 // In other cases, do a regular add, and unsigned compare-less-than.
1961 // The carry-out can originate in two places: adding the carry-in or adding
1962 // the two input values.
1963 Value *Result1 = X; // Result1 = X + CarryIn
1964 if (CarryIn != nullptr) {
1965 unsigned Width = VecTy->getScalarSizeInBits();
1966 uint32_t Mask = 1;
1967 if (Width < 32) {
1968 for (unsigned i = 0, e = 32 / Width; i != e; ++i)
1969 Mask = (Mask << Width) | 1;
1970 }
1971 auto V6_vandqrt = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vandqrt);
1972 Value *ValueIn =
1973 HVC.createHvxIntrinsic(Builder, IntID: V6_vandqrt, /*RetTy=*/nullptr,
1974 Args: {CarryIn, HVC.getConstInt(Val: Mask)});
1975 Result1 = Builder.CreateAdd(LHS: X, RHS: ValueIn, Name: "add");
1976 }
1977
1978 Value *CarryOut1 = Builder.CreateCmp(Pred: CmpInst::ICMP_ULT, LHS: Result1, RHS: X, Name: "cmp");
1979 Value *Result2 = Builder.CreateAdd(LHS: Result1, RHS: Y, Name: "add");
1980 Value *CarryOut2 = Builder.CreateCmp(Pred: CmpInst::ICMP_ULT, LHS: Result2, RHS: Y, Name: "cmp");
1981 return {Result2, Builder.CreateOr(LHS: CarryOut1, RHS: CarryOut2, Name: "orb")};
1982}
1983
1984auto HvxIdioms::createMul16(IRBuilderBase &Builder, SValue X, SValue Y) const
1985 -> Value * {
1986 Intrinsic::ID V6_vmpyh = 0;
1987 std::tie(args&: X, args&: Y) = canonSgn(X, Y);
1988
1989 if (X.Sgn == Signed) {
1990 V6_vmpyh = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vmpyhv);
1991 } else if (Y.Sgn == Signed) {
1992 // In vmpyhus the second operand is unsigned
1993 V6_vmpyh = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vmpyhus);
1994 } else {
1995 V6_vmpyh = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vmpyuhv);
1996 }
1997
1998 // i16*i16 -> i32 / interleaved
1999 Value *P =
2000 HVC.createHvxIntrinsic(Builder, IntID: V6_vmpyh, RetTy: HvxP32Ty, Args: {Y.Val, X.Val});
2001 // Deinterleave
2002 return HVC.vshuff(Builder, Val0: HVC.sublo(Builder, Val: P), Val1: HVC.subhi(Builder, Val: P));
2003}
2004
2005auto HvxIdioms::createMulH16(IRBuilderBase &Builder, SValue X, SValue Y) const
2006 -> Value * {
2007 Type *HvxI16Ty = HVC.getHvxTy(ElemTy: HVC.getIntTy(Width: 16), /*Pair=*/false);
2008
2009 if (HVC.HST.useHVXV69Ops()) {
2010 if (X.Sgn != Signed && Y.Sgn != Signed) {
2011 auto V6_vmpyuhvs = HVC.HST.getIntrinsicId(Opc: Hexagon::V6_vmpyuhvs);
2012 return HVC.createHvxIntrinsic(Builder, IntID: V6_vmpyuhvs, RetTy: HvxI16Ty,
2013 Args: {X.Val, Y.Val});
2014 }
2015 }
2016
2017 Type *HvxP16Ty = HVC.getHvxTy(ElemTy: HVC.getIntTy(Width: 16), /*Pair=*/true);
2018 Value *Pair16 =
2019 Builder.CreateBitCast(V: createMul16(Builder, X, Y), DestTy: HvxP16Ty, Name: "cst");
2020 unsigned Len = HVC.length(Ty: HvxP16Ty) / 2;
2021
2022 SmallVector<int, 128> PickOdd(Len);
2023 for (int i = 0; i != static_cast<int>(Len); ++i)
2024 PickOdd[i] = 2 * i + 1;
2025
2026 return Builder.CreateShuffleVector(
2027 V1: HVC.sublo(Builder, Val: Pair16), V2: HVC.subhi(Builder, Val: Pair16), Mask: PickOdd, Name: "shf");
2028}
2029
2030auto HvxIdioms::createMul32(IRBuilderBase &Builder, SValue X, SValue Y) const
2031 -> std::pair<Value *, Value *> {
2032 assert(X.Val->getType() == Y.Val->getType());
2033 assert(X.Val->getType() == HvxI32Ty);
2034
2035 Intrinsic::ID V6_vmpy_parts;
2036 std::tie(args&: X, args&: Y) = canonSgn(X, Y);
2037
2038 if (X.Sgn == Signed) {
2039 V6_vmpy_parts = Intrinsic::hexagon_V6_vmpyss_parts;
2040 } else if (Y.Sgn == Signed) {
2041 V6_vmpy_parts = Intrinsic::hexagon_V6_vmpyus_parts;
2042 } else {
2043 V6_vmpy_parts = Intrinsic::hexagon_V6_vmpyuu_parts;
2044 }
2045
2046 Value *Parts = HVC.createHvxIntrinsic(Builder, IntID: V6_vmpy_parts, RetTy: nullptr,
2047 Args: {X.Val, Y.Val}, ArgTys: {HvxI32Ty});
2048 Value *Hi = Builder.CreateExtractValue(Agg: Parts, Idxs: {0}, Name: "ext");
2049 Value *Lo = Builder.CreateExtractValue(Agg: Parts, Idxs: {1}, Name: "ext");
2050 return {Lo, Hi};
2051}
2052
2053auto HvxIdioms::createAddLong(IRBuilderBase &Builder, ArrayRef<Value *> WordX,
2054 ArrayRef<Value *> WordY) const
2055 -> SmallVector<Value *> {
2056 assert(WordX.size() == WordY.size());
2057 unsigned Idx = 0, Length = WordX.size();
2058 SmallVector<Value *> Sum(Length);
2059
2060 while (Idx != Length) {
2061 if (HVC.isZero(Val: WordX[Idx]))
2062 Sum[Idx] = WordY[Idx];
2063 else if (HVC.isZero(Val: WordY[Idx]))
2064 Sum[Idx] = WordX[Idx];
2065 else
2066 break;
2067 ++Idx;
2068 }
2069
2070 Value *Carry = nullptr;
2071 for (; Idx != Length; ++Idx) {
2072 std::tie(args&: Sum[Idx], args&: Carry) =
2073 createAddCarry(Builder, X: WordX[Idx], Y: WordY[Idx], CarryIn: Carry);
2074 }
2075
2076 // This drops the final carry beyond the highest word.
2077 return Sum;
2078}
2079
2080auto HvxIdioms::createMulLong(IRBuilderBase &Builder, ArrayRef<Value *> WordX,
2081 Signedness SgnX, ArrayRef<Value *> WordY,
2082 Signedness SgnY) const -> SmallVector<Value *> {
2083 SmallVector<SmallVector<Value *>> Products(WordX.size() + WordY.size());
2084
2085 // WordX[i] * WordY[j] produces words i+j and i+j+1 of the results,
2086 // that is halves 2(i+j), 2(i+j)+1, 2(i+j)+2, 2(i+j)+3.
2087 for (int i = 0, e = WordX.size(); i != e; ++i) {
2088 for (int j = 0, f = WordY.size(); j != f; ++j) {
2089 // Check the 4 halves that this multiplication can generate.
2090 Signedness SX = (i + 1 == e) ? SgnX : Unsigned;
2091 Signedness SY = (j + 1 == f) ? SgnY : Unsigned;
2092 auto [Lo, Hi] = createMul32(Builder, X: {.Val: WordX[i], .Sgn: SX}, Y: {.Val: WordY[j], .Sgn: SY});
2093 Products[i + j + 0].push_back(Elt: Lo);
2094 Products[i + j + 1].push_back(Elt: Hi);
2095 }
2096 }
2097
2098 Value *Zero = HVC.getNullValue(Ty: WordX[0]->getType());
2099
2100 auto pop_back_or_zero = [Zero](auto &Vector) -> Value * {
2101 if (Vector.empty())
2102 return Zero;
2103 auto Last = Vector.back();
2104 Vector.pop_back();
2105 return Last;
2106 };
2107
2108 for (int i = 0, e = Products.size(); i != e; ++i) {
2109 while (Products[i].size() > 1) {
2110 Value *Carry = nullptr; // no carry-in
2111 for (int j = i; j != e; ++j) {
2112 auto &ProdJ = Products[j];
2113 auto [Sum, CarryOut] = createAddCarry(Builder, X: pop_back_or_zero(ProdJ),
2114 Y: pop_back_or_zero(ProdJ), CarryIn: Carry);
2115 ProdJ.insert(I: ProdJ.begin(), Elt: Sum);
2116 Carry = CarryOut;
2117 }
2118 }
2119 }
2120
2121 SmallVector<Value *> WordP;
2122 for (auto &P : Products) {
2123 assert(P.size() == 1 && "Should have been added together");
2124 WordP.push_back(Elt: P.front());
2125 }
2126
2127 return WordP;
2128}
2129
2130auto HvxIdioms::run() -> bool {
2131 bool Changed = false;
2132
2133 for (BasicBlock &B : HVC.F) {
2134 for (auto It = B.rbegin(); It != B.rend(); ++It) {
2135 if (auto Fxm = matchFxpMul(In&: *It)) {
2136 Value *New = processFxpMul(In&: *It, Op: *Fxm);
2137 // Always report "changed" for now.
2138 Changed = true;
2139 if (!New)
2140 continue;
2141 bool StartOver = !isa<Instruction>(Val: New);
2142 It->replaceAllUsesWith(V: New);
2143 RecursivelyDeleteTriviallyDeadInstructions(V: &*It, TLI: &HVC.TLI);
2144 It = StartOver ? B.rbegin()
2145 : cast<Instruction>(Val: New)->getReverseIterator();
2146 Changed = true;
2147 }
2148 }
2149 }
2150
2151 return Changed;
2152}
2153
2154// --- End HvxIdioms
2155
2156auto HexagonVectorCombine::run() -> bool {
2157 if (DumpModule)
2158 dbgs() << "Module before HexagonVectorCombine\n" << *F.getParent();
2159
2160 bool Changed = false;
2161 if (HST.useHVXOps()) {
2162 if (VAEnabled)
2163 Changed |= AlignVectors(*this).run();
2164 if (VIEnabled)
2165 Changed |= HvxIdioms(*this).run();
2166 }
2167
2168 if (DumpModule) {
2169 dbgs() << "Module " << (Changed ? "(modified)" : "(unchanged)")
2170 << " after HexagonVectorCombine\n"
2171 << *F.getParent();
2172 }
2173 return Changed;
2174}
2175
2176auto HexagonVectorCombine::getIntTy(unsigned Width) const -> IntegerType * {
2177 return IntegerType::get(C&: F.getContext(), NumBits: Width);
2178}
2179
2180auto HexagonVectorCombine::getByteTy(int ElemCount) const -> Type * {
2181 assert(ElemCount >= 0);
2182 IntegerType *ByteTy = Type::getInt8Ty(C&: F.getContext());
2183 if (ElemCount == 0)
2184 return ByteTy;
2185 return VectorType::get(ElementType: ByteTy, NumElements: ElemCount, /*Scalable=*/false);
2186}
2187
2188auto HexagonVectorCombine::getBoolTy(int ElemCount) const -> Type * {
2189 assert(ElemCount >= 0);
2190 IntegerType *BoolTy = Type::getInt1Ty(C&: F.getContext());
2191 if (ElemCount == 0)
2192 return BoolTy;
2193 return VectorType::get(ElementType: BoolTy, NumElements: ElemCount, /*Scalable=*/false);
2194}
2195
2196auto HexagonVectorCombine::getConstInt(int Val, unsigned Width) const
2197 -> ConstantInt * {
2198 return ConstantInt::getSigned(Ty: getIntTy(Width), V: Val);
2199}
2200
2201auto HexagonVectorCombine::isZero(const Value *Val) const -> bool {
2202 if (auto *C = dyn_cast<Constant>(Val))
2203 return C->isZeroValue();
2204 return false;
2205}
2206
2207auto HexagonVectorCombine::getIntValue(const Value *Val) const
2208 -> std::optional<APInt> {
2209 if (auto *CI = dyn_cast<ConstantInt>(Val))
2210 return CI->getValue();
2211 return std::nullopt;
2212}
2213
2214auto HexagonVectorCombine::isUndef(const Value *Val) const -> bool {
2215 return isa<UndefValue>(Val);
2216}
2217
2218auto HexagonVectorCombine::isTrue(const Value *Val) const -> bool {
2219 return Val == ConstantInt::getTrue(Ty: Val->getType());
2220}
2221
2222auto HexagonVectorCombine::isFalse(const Value *Val) const -> bool {
2223 return isZero(Val);
2224}
2225
2226auto HexagonVectorCombine::getHvxTy(Type *ElemTy, bool Pair) const
2227 -> VectorType * {
2228 EVT ETy = EVT::getEVT(Ty: ElemTy, HandleUnknown: false);
2229 assert(ETy.isSimple() && "Invalid HVX element type");
2230 // Do not allow boolean types here: they don't have a fixed length.
2231 assert(HST.isHVXElementType(ETy.getSimpleVT(), /*IncludeBool=*/false) &&
2232 "Invalid HVX element type");
2233 unsigned HwLen = HST.getVectorLength();
2234 unsigned NumElems = (8 * HwLen) / ETy.getSizeInBits();
2235 return VectorType::get(ElementType: ElemTy, NumElements: Pair ? 2 * NumElems : NumElems,
2236 /*Scalable=*/false);
2237}
2238
2239auto HexagonVectorCombine::getSizeOf(const Value *Val, SizeKind Kind) const
2240 -> int {
2241 return getSizeOf(Ty: Val->getType(), Kind);
2242}
2243
2244auto HexagonVectorCombine::getSizeOf(const Type *Ty, SizeKind Kind) const
2245 -> int {
2246 auto *NcTy = const_cast<Type *>(Ty);
2247 switch (Kind) {
2248 case Store:
2249 return DL.getTypeStoreSize(Ty: NcTy).getFixedValue();
2250 case Alloc:
2251 return DL.getTypeAllocSize(Ty: NcTy).getFixedValue();
2252 }
2253 llvm_unreachable("Unhandled SizeKind enum");
2254}
2255
2256auto HexagonVectorCombine::getTypeAlignment(Type *Ty) const -> int {
2257 // The actual type may be shorter than the HVX vector, so determine
2258 // the alignment based on subtarget info.
2259 if (HST.isTypeForHVX(VecTy: Ty))
2260 return HST.getVectorLength();
2261 return DL.getABITypeAlign(Ty).value();
2262}
2263
2264auto HexagonVectorCombine::length(Value *Val) const -> size_t {
2265 return length(Ty: Val->getType());
2266}
2267
2268auto HexagonVectorCombine::length(Type *Ty) const -> size_t {
2269 auto *VecTy = dyn_cast<VectorType>(Val: Ty);
2270 assert(VecTy && "Must be a vector type");
2271 return VecTy->getElementCount().getFixedValue();
2272}
2273
2274auto HexagonVectorCombine::getNullValue(Type *Ty) const -> Constant * {
2275 assert(Ty->isIntOrIntVectorTy());
2276 auto Zero = ConstantInt::get(Ty: Ty->getScalarType(), V: 0);
2277 if (auto *VecTy = dyn_cast<VectorType>(Val: Ty))
2278 return ConstantVector::getSplat(EC: VecTy->getElementCount(), Elt: Zero);
2279 return Zero;
2280}
2281
2282auto HexagonVectorCombine::getFullValue(Type *Ty) const -> Constant * {
2283 assert(Ty->isIntOrIntVectorTy());
2284 auto Minus1 = ConstantInt::get(Ty: Ty->getScalarType(), V: -1);
2285 if (auto *VecTy = dyn_cast<VectorType>(Val: Ty))
2286 return ConstantVector::getSplat(EC: VecTy->getElementCount(), Elt: Minus1);
2287 return Minus1;
2288}
2289
2290auto HexagonVectorCombine::getConstSplat(Type *Ty, int Val) const
2291 -> Constant * {
2292 assert(Ty->isVectorTy());
2293 auto VecTy = cast<VectorType>(Val: Ty);
2294 Type *ElemTy = VecTy->getElementType();
2295 // Add support for floats if needed.
2296 auto *Splat = ConstantVector::getSplat(EC: VecTy->getElementCount(),
2297 Elt: ConstantInt::get(Ty: ElemTy, V: Val));
2298 return Splat;
2299}
2300
2301auto HexagonVectorCombine::simplify(Value *V) const -> Value * {
2302 if (auto *In = dyn_cast<Instruction>(Val: V)) {
2303 SimplifyQuery Q(DL, &TLI, &DT, &AC, In);
2304 return simplifyInstruction(I: In, Q);
2305 }
2306 return nullptr;
2307}
2308
2309// Insert bytes [Start..Start+Length) of Src into Dst at byte Where.
2310auto HexagonVectorCombine::insertb(IRBuilderBase &Builder, Value *Dst,
2311 Value *Src, int Start, int Length,
2312 int Where) const -> Value * {
2313 assert(isByteVecTy(Dst->getType()) && isByteVecTy(Src->getType()));
2314 int SrcLen = getSizeOf(Val: Src);
2315 int DstLen = getSizeOf(Val: Dst);
2316 assert(0 <= Start && Start + Length <= SrcLen);
2317 assert(0 <= Where && Where + Length <= DstLen);
2318
2319 int P2Len = PowerOf2Ceil(A: SrcLen | DstLen);
2320 auto *Undef = UndefValue::get(T: getByteTy());
2321 Value *P2Src = vresize(Builder, Val: Src, NewSize: P2Len, Pad: Undef);
2322 Value *P2Dst = vresize(Builder, Val: Dst, NewSize: P2Len, Pad: Undef);
2323
2324 SmallVector<int, 256> SMask(P2Len);
2325 for (int i = 0; i != P2Len; ++i) {
2326 // If i is in [Where, Where+Length), pick Src[Start+(i-Where)].
2327 // Otherwise, pick Dst[i];
2328 SMask[i] =
2329 (Where <= i && i < Where + Length) ? P2Len + Start + (i - Where) : i;
2330 }
2331
2332 Value *P2Insert = Builder.CreateShuffleVector(V1: P2Dst, V2: P2Src, Mask: SMask, Name: "shf");
2333 return vresize(Builder, Val: P2Insert, NewSize: DstLen, Pad: Undef);
2334}
2335
2336auto HexagonVectorCombine::vlalignb(IRBuilderBase &Builder, Value *Lo,
2337 Value *Hi, Value *Amt) const -> Value * {
2338 assert(Lo->getType() == Hi->getType() && "Argument type mismatch");
2339 if (isZero(Val: Amt))
2340 return Hi;
2341 int VecLen = getSizeOf(Val: Hi);
2342 if (auto IntAmt = getIntValue(Val: Amt))
2343 return getElementRange(Builder, Lo, Hi, Start: VecLen - IntAmt->getSExtValue(),
2344 Length: VecLen);
2345
2346 if (HST.isTypeForHVX(VecTy: Hi->getType())) {
2347 assert(static_cast<unsigned>(VecLen) == HST.getVectorLength() &&
2348 "Expecting an exact HVX type");
2349 return createHvxIntrinsic(Builder, IntID: HST.getIntrinsicId(Opc: Hexagon::V6_vlalignb),
2350 RetTy: Hi->getType(), Args: {Hi, Lo, Amt});
2351 }
2352
2353 if (VecLen == 4) {
2354 Value *Pair = concat(Builder, Vecs: {Lo, Hi});
2355 Value *Shift =
2356 Builder.CreateLShr(LHS: Builder.CreateShl(LHS: Pair, RHS: Amt, Name: "shl"), RHS: 32, Name: "lsr");
2357 Value *Trunc =
2358 Builder.CreateTrunc(V: Shift, DestTy: Type::getInt32Ty(C&: F.getContext()), Name: "trn");
2359 return Builder.CreateBitCast(V: Trunc, DestTy: Hi->getType(), Name: "cst");
2360 }
2361 if (VecLen == 8) {
2362 Value *Sub = Builder.CreateSub(LHS: getConstInt(Val: VecLen), RHS: Amt, Name: "sub");
2363 return vralignb(Builder, Lo, Hi, Amt: Sub);
2364 }
2365 llvm_unreachable("Unexpected vector length");
2366}
2367
2368auto HexagonVectorCombine::vralignb(IRBuilderBase &Builder, Value *Lo,
2369 Value *Hi, Value *Amt) const -> Value * {
2370 assert(Lo->getType() == Hi->getType() && "Argument type mismatch");
2371 if (isZero(Val: Amt))
2372 return Lo;
2373 int VecLen = getSizeOf(Val: Lo);
2374 if (auto IntAmt = getIntValue(Val: Amt))
2375 return getElementRange(Builder, Lo, Hi, Start: IntAmt->getSExtValue(), Length: VecLen);
2376
2377 if (HST.isTypeForHVX(VecTy: Lo->getType())) {
2378 assert(static_cast<unsigned>(VecLen) == HST.getVectorLength() &&
2379 "Expecting an exact HVX type");
2380 return createHvxIntrinsic(Builder, IntID: HST.getIntrinsicId(Opc: Hexagon::V6_valignb),
2381 RetTy: Lo->getType(), Args: {Hi, Lo, Amt});
2382 }
2383
2384 if (VecLen == 4) {
2385 Value *Pair = concat(Builder, Vecs: {Lo, Hi});
2386 Value *Shift = Builder.CreateLShr(LHS: Pair, RHS: Amt, Name: "lsr");
2387 Value *Trunc =
2388 Builder.CreateTrunc(V: Shift, DestTy: Type::getInt32Ty(C&: F.getContext()), Name: "trn");
2389 return Builder.CreateBitCast(V: Trunc, DestTy: Lo->getType(), Name: "cst");
2390 }
2391 if (VecLen == 8) {
2392 Type *Int64Ty = Type::getInt64Ty(C&: F.getContext());
2393 Value *Lo64 = Builder.CreateBitCast(V: Lo, DestTy: Int64Ty, Name: "cst");
2394 Value *Hi64 = Builder.CreateBitCast(V: Hi, DestTy: Int64Ty, Name: "cst");
2395 Function *FI = Intrinsic::getDeclaration(M: F.getParent(),
2396 id: Intrinsic::hexagon_S2_valignrb);
2397 Value *Call = Builder.CreateCall(Callee: FI, Args: {Hi64, Lo64, Amt}, Name: "cup");
2398 return Builder.CreateBitCast(V: Call, DestTy: Lo->getType(), Name: "cst");
2399 }
2400 llvm_unreachable("Unexpected vector length");
2401}
2402
2403// Concatenates a sequence of vectors of the same type.
2404auto HexagonVectorCombine::concat(IRBuilderBase &Builder,
2405 ArrayRef<Value *> Vecs) const -> Value * {
2406 assert(!Vecs.empty());
2407 SmallVector<int, 256> SMask;
2408 std::vector<Value *> Work[2];
2409 int ThisW = 0, OtherW = 1;
2410
2411 Work[ThisW].assign(first: Vecs.begin(), last: Vecs.end());
2412 while (Work[ThisW].size() > 1) {
2413 auto *Ty = cast<VectorType>(Val: Work[ThisW].front()->getType());
2414 SMask.resize(N: length(Ty) * 2);
2415 std::iota(first: SMask.begin(), last: SMask.end(), value: 0);
2416
2417 Work[OtherW].clear();
2418 if (Work[ThisW].size() % 2 != 0)
2419 Work[ThisW].push_back(x: UndefValue::get(T: Ty));
2420 for (int i = 0, e = Work[ThisW].size(); i < e; i += 2) {
2421 Value *Joined = Builder.CreateShuffleVector(
2422 V1: Work[ThisW][i], V2: Work[ThisW][i + 1], Mask: SMask, Name: "shf");
2423 Work[OtherW].push_back(x: Joined);
2424 }
2425 std::swap(a&: ThisW, b&: OtherW);
2426 }
2427
2428 // Since there may have been some undefs appended to make shuffle operands
2429 // have the same type, perform the last shuffle to only pick the original
2430 // elements.
2431 SMask.resize(N: Vecs.size() * length(Ty: Vecs.front()->getType()));
2432 std::iota(first: SMask.begin(), last: SMask.end(), value: 0);
2433 Value *Total = Work[ThisW].front();
2434 return Builder.CreateShuffleVector(V: Total, Mask: SMask, Name: "shf");
2435}
2436
2437auto HexagonVectorCombine::vresize(IRBuilderBase &Builder, Value *Val,
2438 int NewSize, Value *Pad) const -> Value * {
2439 assert(isa<VectorType>(Val->getType()));
2440 auto *ValTy = cast<VectorType>(Val: Val->getType());
2441 assert(ValTy->getElementType() == Pad->getType());
2442
2443 int CurSize = length(Ty: ValTy);
2444 if (CurSize == NewSize)
2445 return Val;
2446 // Truncate?
2447 if (CurSize > NewSize)
2448 return getElementRange(Builder, Lo: Val, /*Ignored*/ Hi: Val, Start: 0, Length: NewSize);
2449 // Extend.
2450 SmallVector<int, 128> SMask(NewSize);
2451 std::iota(first: SMask.begin(), last: SMask.begin() + CurSize, value: 0);
2452 std::fill(SMask.begin() + CurSize, SMask.end(), CurSize);
2453 Value *PadVec = Builder.CreateVectorSplat(NumElts: CurSize, V: Pad, Name: "spt");
2454 return Builder.CreateShuffleVector(V1: Val, V2: PadVec, Mask: SMask, Name: "shf");
2455}
2456
2457auto HexagonVectorCombine::rescale(IRBuilderBase &Builder, Value *Mask,
2458 Type *FromTy, Type *ToTy) const -> Value * {
2459 // Mask is a vector <N x i1>, where each element corresponds to an
2460 // element of FromTy. Remap it so that each element will correspond
2461 // to an element of ToTy.
2462 assert(isa<VectorType>(Mask->getType()));
2463
2464 Type *FromSTy = FromTy->getScalarType();
2465 Type *ToSTy = ToTy->getScalarType();
2466 if (FromSTy == ToSTy)
2467 return Mask;
2468
2469 int FromSize = getSizeOf(Ty: FromSTy);
2470 int ToSize = getSizeOf(Ty: ToSTy);
2471 assert(FromSize % ToSize == 0 || ToSize % FromSize == 0);
2472
2473 auto *MaskTy = cast<VectorType>(Val: Mask->getType());
2474 int FromCount = length(Ty: MaskTy);
2475 int ToCount = (FromCount * FromSize) / ToSize;
2476 assert((FromCount * FromSize) % ToSize == 0);
2477
2478 auto *FromITy = getIntTy(Width: FromSize * 8);
2479 auto *ToITy = getIntTy(Width: ToSize * 8);
2480
2481 // Mask <N x i1> -> sext to <N x FromTy> -> bitcast to <M x ToTy> ->
2482 // -> trunc to <M x i1>.
2483 Value *Ext = Builder.CreateSExt(
2484 V: Mask, DestTy: VectorType::get(ElementType: FromITy, NumElements: FromCount, /*Scalable=*/false), Name: "sxt");
2485 Value *Cast = Builder.CreateBitCast(
2486 V: Ext, DestTy: VectorType::get(ElementType: ToITy, NumElements: ToCount, /*Scalable=*/false), Name: "cst");
2487 return Builder.CreateTrunc(
2488 V: Cast, DestTy: VectorType::get(ElementType: getBoolTy(), NumElements: ToCount, /*Scalable=*/false), Name: "trn");
2489}
2490
2491// Bitcast to bytes, and return least significant bits.
2492auto HexagonVectorCombine::vlsb(IRBuilderBase &Builder, Value *Val) const
2493 -> Value * {
2494 Type *ScalarTy = Val->getType()->getScalarType();
2495 if (ScalarTy == getBoolTy())
2496 return Val;
2497
2498 Value *Bytes = vbytes(Builder, Val);
2499 if (auto *VecTy = dyn_cast<VectorType>(Val: Bytes->getType()))
2500 return Builder.CreateTrunc(V: Bytes, DestTy: getBoolTy(ElemCount: getSizeOf(Ty: VecTy)), Name: "trn");
2501 // If Bytes is a scalar (i.e. Val was a scalar byte), return i1, not
2502 // <1 x i1>.
2503 return Builder.CreateTrunc(V: Bytes, DestTy: getBoolTy(), Name: "trn");
2504}
2505
2506// Bitcast to bytes for non-bool. For bool, convert i1 -> i8.
2507auto HexagonVectorCombine::vbytes(IRBuilderBase &Builder, Value *Val) const
2508 -> Value * {
2509 Type *ScalarTy = Val->getType()->getScalarType();
2510 if (ScalarTy == getByteTy())
2511 return Val;
2512
2513 if (ScalarTy != getBoolTy())
2514 return Builder.CreateBitCast(V: Val, DestTy: getByteTy(ElemCount: getSizeOf(Val)), Name: "cst");
2515 // For bool, return a sext from i1 to i8.
2516 if (auto *VecTy = dyn_cast<VectorType>(Val: Val->getType()))
2517 return Builder.CreateSExt(V: Val, DestTy: VectorType::get(ElementType: getByteTy(), Other: VecTy), Name: "sxt");
2518 return Builder.CreateSExt(V: Val, DestTy: getByteTy(), Name: "sxt");
2519}
2520
2521auto HexagonVectorCombine::subvector(IRBuilderBase &Builder, Value *Val,
2522 unsigned Start, unsigned Length) const
2523 -> Value * {
2524 assert(Start + Length <= length(Val));
2525 return getElementRange(Builder, Lo: Val, /*Ignored*/ Hi: Val, Start, Length);
2526}
2527
2528auto HexagonVectorCombine::sublo(IRBuilderBase &Builder, Value *Val) const
2529 -> Value * {
2530 size_t Len = length(Val);
2531 assert(Len % 2 == 0 && "Length should be even");
2532 return subvector(Builder, Val, Start: 0, Length: Len / 2);
2533}
2534
2535auto HexagonVectorCombine::subhi(IRBuilderBase &Builder, Value *Val) const
2536 -> Value * {
2537 size_t Len = length(Val);
2538 assert(Len % 2 == 0 && "Length should be even");
2539 return subvector(Builder, Val, Start: Len / 2, Length: Len / 2);
2540}
2541
2542auto HexagonVectorCombine::vdeal(IRBuilderBase &Builder, Value *Val0,
2543 Value *Val1) const -> Value * {
2544 assert(Val0->getType() == Val1->getType());
2545 int Len = length(Val: Val0);
2546 SmallVector<int, 128> Mask(2 * Len);
2547
2548 for (int i = 0; i != Len; ++i) {
2549 Mask[i] = 2 * i; // Even
2550 Mask[i + Len] = 2 * i + 1; // Odd
2551 }
2552 return Builder.CreateShuffleVector(V1: Val0, V2: Val1, Mask, Name: "shf");
2553}
2554
2555auto HexagonVectorCombine::vshuff(IRBuilderBase &Builder, Value *Val0,
2556 Value *Val1) const -> Value * { //
2557 assert(Val0->getType() == Val1->getType());
2558 int Len = length(Val: Val0);
2559 SmallVector<int, 128> Mask(2 * Len);
2560
2561 for (int i = 0; i != Len; ++i) {
2562 Mask[2 * i + 0] = i; // Val0
2563 Mask[2 * i + 1] = i + Len; // Val1
2564 }
2565 return Builder.CreateShuffleVector(V1: Val0, V2: Val1, Mask, Name: "shf");
2566}
2567
2568auto HexagonVectorCombine::createHvxIntrinsic(IRBuilderBase &Builder,
2569 Intrinsic::ID IntID, Type *RetTy,
2570 ArrayRef<Value *> Args,
2571 ArrayRef<Type *> ArgTys,
2572 ArrayRef<Value *> MDSources) const
2573 -> Value * {
2574 auto getCast = [&](IRBuilderBase &Builder, Value *Val,
2575 Type *DestTy) -> Value * {
2576 Type *SrcTy = Val->getType();
2577 if (SrcTy == DestTy)
2578 return Val;
2579
2580 // Non-HVX type. It should be a scalar, and it should already have
2581 // a valid type.
2582 assert(HST.isTypeForHVX(SrcTy, /*IncludeBool=*/true));
2583
2584 Type *BoolTy = Type::getInt1Ty(C&: F.getContext());
2585 if (cast<VectorType>(Val: SrcTy)->getElementType() != BoolTy)
2586 return Builder.CreateBitCast(V: Val, DestTy, Name: "cst");
2587
2588 // Predicate HVX vector.
2589 unsigned HwLen = HST.getVectorLength();
2590 Intrinsic::ID TC = HwLen == 64 ? Intrinsic::hexagon_V6_pred_typecast
2591 : Intrinsic::hexagon_V6_pred_typecast_128B;
2592 Function *FI =
2593 Intrinsic::getDeclaration(M: F.getParent(), id: TC, Tys: {DestTy, Val->getType()});
2594 return Builder.CreateCall(Callee: FI, Args: {Val}, Name: "cup");
2595 };
2596
2597 Function *IntrFn = Intrinsic::getDeclaration(M: F.getParent(), id: IntID, Tys: ArgTys);
2598 FunctionType *IntrTy = IntrFn->getFunctionType();
2599
2600 SmallVector<Value *, 4> IntrArgs;
2601 for (int i = 0, e = Args.size(); i != e; ++i) {
2602 Value *A = Args[i];
2603 Type *T = IntrTy->getParamType(i);
2604 if (A->getType() != T) {
2605 IntrArgs.push_back(Elt: getCast(Builder, A, T));
2606 } else {
2607 IntrArgs.push_back(Elt: A);
2608 }
2609 }
2610 StringRef MaybeName = !IntrTy->getReturnType()->isVoidTy() ? "cup" : "";
2611 CallInst *Call = Builder.CreateCall(Callee: IntrFn, Args: IntrArgs, Name: MaybeName);
2612
2613 MemoryEffects ME = Call->getAttributes().getMemoryEffects();
2614 if (!ME.doesNotAccessMemory() && !ME.onlyAccessesInaccessibleMem())
2615 propagateMetadata(I: Call, VL: MDSources);
2616
2617 Type *CallTy = Call->getType();
2618 if (RetTy == nullptr || CallTy == RetTy)
2619 return Call;
2620 // Scalar types should have RetTy matching the call return type.
2621 assert(HST.isTypeForHVX(CallTy, /*IncludeBool=*/true));
2622 return getCast(Builder, Call, RetTy);
2623}
2624
2625auto HexagonVectorCombine::splitVectorElements(IRBuilderBase &Builder,
2626 Value *Vec,
2627 unsigned ToWidth) const
2628 -> SmallVector<Value *> {
2629 // Break a vector of wide elements into a series of vectors with narrow
2630 // elements:
2631 // (...c0:b0:a0, ...c1:b1:a1, ...c2:b2:a2, ...)
2632 // -->
2633 // (a0, a1, a2, ...) // lowest "ToWidth" bits
2634 // (b0, b1, b2, ...) // the next lowest...
2635 // (c0, c1, c2, ...) // ...
2636 // ...
2637 //
2638 // The number of elements in each resulting vector is the same as
2639 // in the original vector.
2640
2641 auto *VecTy = cast<VectorType>(Val: Vec->getType());
2642 assert(VecTy->getElementType()->isIntegerTy());
2643 unsigned FromWidth = VecTy->getScalarSizeInBits();
2644 assert(isPowerOf2_32(ToWidth) && isPowerOf2_32(FromWidth));
2645 assert(ToWidth <= FromWidth && "Breaking up into wider elements?");
2646 unsigned NumResults = FromWidth / ToWidth;
2647
2648 SmallVector<Value *> Results(NumResults);
2649 Results[0] = Vec;
2650 unsigned Length = length(Ty: VecTy);
2651
2652 // Do it by splitting in half, since those operations correspond to deal
2653 // instructions.
2654 auto splitInHalf = [&](unsigned Begin, unsigned End, auto splitFunc) -> void {
2655 // Take V = Results[Begin], split it in L, H.
2656 // Store Results[Begin] = L, Results[(Begin+End)/2] = H
2657 // Call itself recursively split(Begin, Half), split(Half+1, End)
2658 if (Begin + 1 == End)
2659 return;
2660
2661 Value *Val = Results[Begin];
2662 unsigned Width = Val->getType()->getScalarSizeInBits();
2663
2664 auto *VTy = VectorType::get(ElementType: getIntTy(Width: Width / 2), NumElements: 2 * Length, Scalable: false);
2665 Value *VVal = Builder.CreateBitCast(V: Val, DestTy: VTy, Name: "cst");
2666
2667 Value *Res = vdeal(Builder, Val0: sublo(Builder, Val: VVal), Val1: subhi(Builder, Val: VVal));
2668
2669 unsigned Half = (Begin + End) / 2;
2670 Results[Begin] = sublo(Builder, Val: Res);
2671 Results[Half] = subhi(Builder, Val: Res);
2672
2673 splitFunc(Begin, Half, splitFunc);
2674 splitFunc(Half, End, splitFunc);
2675 };
2676
2677 splitInHalf(0, NumResults, splitInHalf);
2678 return Results;
2679}
2680
2681auto HexagonVectorCombine::joinVectorElements(IRBuilderBase &Builder,
2682 ArrayRef<Value *> Values,
2683 VectorType *ToType) const
2684 -> Value * {
2685 assert(ToType->getElementType()->isIntegerTy());
2686
2687 // If the list of values does not have power-of-2 elements, append copies
2688 // of the sign bit to it, to make the size be 2^n.
2689 // The reason for this is that the values will be joined in pairs, because
2690 // otherwise the shuffles will result in convoluted code. With pairwise
2691 // joins, the shuffles will hopefully be folded into a perfect shuffle.
2692 // The output will need to be sign-extended to a type with element width
2693 // being a power-of-2 anyways.
2694 SmallVector<Value *> Inputs(Values.begin(), Values.end());
2695
2696 unsigned ToWidth = ToType->getScalarSizeInBits();
2697 unsigned Width = Inputs.front()->getType()->getScalarSizeInBits();
2698 assert(Width <= ToWidth);
2699 assert(isPowerOf2_32(Width) && isPowerOf2_32(ToWidth));
2700 unsigned Length = length(Ty: Inputs.front()->getType());
2701
2702 unsigned NeedInputs = ToWidth / Width;
2703 if (Inputs.size() != NeedInputs) {
2704 // Having too many inputs is ok: drop the high bits (usual wrap-around).
2705 // If there are too few, fill them with the sign bit.
2706 Value *Last = Inputs.back();
2707 Value *Sign = Builder.CreateAShr(
2708 LHS: Last, RHS: getConstSplat(Ty: Last->getType(), Val: Width - 1), Name: "asr");
2709 Inputs.resize(N: NeedInputs, NV: Sign);
2710 }
2711
2712 while (Inputs.size() > 1) {
2713 Width *= 2;
2714 auto *VTy = VectorType::get(ElementType: getIntTy(Width), NumElements: Length, Scalable: false);
2715 for (int i = 0, e = Inputs.size(); i < e; i += 2) {
2716 Value *Res = vshuff(Builder, Val0: Inputs[i], Val1: Inputs[i + 1]);
2717 Inputs[i / 2] = Builder.CreateBitCast(V: Res, DestTy: VTy, Name: "cst");
2718 }
2719 Inputs.resize(N: Inputs.size() / 2);
2720 }
2721
2722 assert(Inputs.front()->getType() == ToType);
2723 return Inputs.front();
2724}
2725
2726auto HexagonVectorCombine::calculatePointerDifference(Value *Ptr0,
2727 Value *Ptr1) const
2728 -> std::optional<int> {
2729 // Try SCEV first.
2730 const SCEV *Scev0 = SE.getSCEV(V: Ptr0);
2731 const SCEV *Scev1 = SE.getSCEV(V: Ptr1);
2732 const SCEV *ScevDiff = SE.getMinusSCEV(LHS: Scev0, RHS: Scev1);
2733 if (auto *Const = dyn_cast<SCEVConstant>(Val: ScevDiff)) {
2734 APInt V = Const->getAPInt();
2735 if (V.isSignedIntN(N: 8 * sizeof(int)))
2736 return static_cast<int>(V.getSExtValue());
2737 }
2738
2739 struct Builder : IRBuilder<> {
2740 Builder(BasicBlock *B) : IRBuilder<>(B->getTerminator()) {}
2741 ~Builder() {
2742 for (Instruction *I : llvm::reverse(C&: ToErase))
2743 I->eraseFromParent();
2744 }
2745 SmallVector<Instruction *, 8> ToErase;
2746 };
2747
2748#define CallBuilder(B, F) \
2749 [&](auto &B_) { \
2750 Value *V = B_.F; \
2751 if (auto *I = dyn_cast<Instruction>(V)) \
2752 B_.ToErase.push_back(I); \
2753 return V; \
2754 }(B)
2755
2756 auto Simplify = [this](Value *V) {
2757 if (Value *S = simplify(V))
2758 return S;
2759 return V;
2760 };
2761
2762 auto StripBitCast = [](Value *V) {
2763 while (auto *C = dyn_cast<BitCastInst>(Val: V))
2764 V = C->getOperand(i_nocapture: 0);
2765 return V;
2766 };
2767
2768 Ptr0 = StripBitCast(Ptr0);
2769 Ptr1 = StripBitCast(Ptr1);
2770 if (!isa<GetElementPtrInst>(Val: Ptr0) || !isa<GetElementPtrInst>(Val: Ptr1))
2771 return std::nullopt;
2772
2773 auto *Gep0 = cast<GetElementPtrInst>(Val: Ptr0);
2774 auto *Gep1 = cast<GetElementPtrInst>(Val: Ptr1);
2775 if (Gep0->getPointerOperand() != Gep1->getPointerOperand())
2776 return std::nullopt;
2777 if (Gep0->getSourceElementType() != Gep1->getSourceElementType())
2778 return std::nullopt;
2779
2780 Builder B(Gep0->getParent());
2781 int Scale = getSizeOf(Ty: Gep0->getSourceElementType(), Kind: Alloc);
2782
2783 // FIXME: for now only check GEPs with a single index.
2784 if (Gep0->getNumOperands() != 2 || Gep1->getNumOperands() != 2)
2785 return std::nullopt;
2786
2787 Value *Idx0 = Gep0->getOperand(i_nocapture: 1);
2788 Value *Idx1 = Gep1->getOperand(i_nocapture: 1);
2789
2790 // First, try to simplify the subtraction directly.
2791 if (auto *Diff = dyn_cast<ConstantInt>(
2792 Val: Simplify(CallBuilder(B, CreateSub(Idx0, Idx1)))))
2793 return Diff->getSExtValue() * Scale;
2794
2795 KnownBits Known0 = getKnownBits(V: Idx0, CtxI: Gep0);
2796 KnownBits Known1 = getKnownBits(V: Idx1, CtxI: Gep1);
2797 APInt Unknown = ~(Known0.Zero | Known0.One) | ~(Known1.Zero | Known1.One);
2798 if (Unknown.isAllOnes())
2799 return std::nullopt;
2800
2801 Value *MaskU = ConstantInt::get(Ty: Idx0->getType(), V: Unknown);
2802 Value *AndU0 = Simplify(CallBuilder(B, CreateAnd(Idx0, MaskU)));
2803 Value *AndU1 = Simplify(CallBuilder(B, CreateAnd(Idx1, MaskU)));
2804 Value *SubU = Simplify(CallBuilder(B, CreateSub(AndU0, AndU1)));
2805 int Diff0 = 0;
2806 if (auto *C = dyn_cast<ConstantInt>(Val: SubU)) {
2807 Diff0 = C->getSExtValue();
2808 } else {
2809 return std::nullopt;
2810 }
2811
2812 Value *MaskK = ConstantInt::get(Ty: MaskU->getType(), V: ~Unknown);
2813 Value *AndK0 = Simplify(CallBuilder(B, CreateAnd(Idx0, MaskK)));
2814 Value *AndK1 = Simplify(CallBuilder(B, CreateAnd(Idx1, MaskK)));
2815 Value *SubK = Simplify(CallBuilder(B, CreateSub(AndK0, AndK1)));
2816 int Diff1 = 0;
2817 if (auto *C = dyn_cast<ConstantInt>(Val: SubK)) {
2818 Diff1 = C->getSExtValue();
2819 } else {
2820 return std::nullopt;
2821 }
2822
2823 return (Diff0 + Diff1) * Scale;
2824
2825#undef CallBuilder
2826}
2827
2828auto HexagonVectorCombine::getNumSignificantBits(const Value *V,
2829 const Instruction *CtxI) const
2830 -> unsigned {
2831 return ComputeMaxSignificantBits(Op: V, DL, /*Depth=*/0, AC: &AC, CxtI: CtxI, DT: &DT);
2832}
2833
2834auto HexagonVectorCombine::getKnownBits(const Value *V,
2835 const Instruction *CtxI) const
2836 -> KnownBits {
2837 return computeKnownBits(V, DL, /*Depth=*/0, AC: &AC, CxtI: CtxI, DT: &DT);
2838}
2839
2840auto HexagonVectorCombine::isSafeToClone(const Instruction &In) const -> bool {
2841 if (In.mayHaveSideEffects() || In.isAtomic() || In.isVolatile() ||
2842 In.isFenceLike() || In.mayReadOrWriteMemory()) {
2843 return false;
2844 }
2845 if (isa<CallBase>(Val: In) || isa<AllocaInst>(Val: In))
2846 return false;
2847 return true;
2848}
2849
2850template <typename T>
2851auto HexagonVectorCombine::isSafeToMoveBeforeInBB(const Instruction &In,
2852 BasicBlock::const_iterator To,
2853 const T &IgnoreInsts) const
2854 -> bool {
2855 auto getLocOrNone =
2856 [this](const Instruction &I) -> std::optional<MemoryLocation> {
2857 if (const auto *II = dyn_cast<IntrinsicInst>(Val: &I)) {
2858 switch (II->getIntrinsicID()) {
2859 case Intrinsic::masked_load:
2860 return MemoryLocation::getForArgument(Call: II, ArgIdx: 0, TLI);
2861 case Intrinsic::masked_store:
2862 return MemoryLocation::getForArgument(Call: II, ArgIdx: 1, TLI);
2863 }
2864 }
2865 return MemoryLocation::getOrNone(Inst: &I);
2866 };
2867
2868 // The source and the destination must be in the same basic block.
2869 const BasicBlock &Block = *In.getParent();
2870 assert(Block.begin() == To || Block.end() == To || To->getParent() == &Block);
2871 // No PHIs.
2872 if (isa<PHINode>(Val: In) || (To != Block.end() && isa<PHINode>(Val: *To)))
2873 return false;
2874
2875 if (!mayHaveNonDefUseDependency(I: In))
2876 return true;
2877 bool MayWrite = In.mayWriteToMemory();
2878 auto MaybeLoc = getLocOrNone(In);
2879
2880 auto From = In.getIterator();
2881 if (From == To)
2882 return true;
2883 bool MoveUp = (To != Block.end() && To->comesBefore(Other: &In));
2884 auto Range =
2885 MoveUp ? std::make_pair(x&: To, y&: From) : std::make_pair(x: std::next(x: From), y&: To);
2886 for (auto It = Range.first; It != Range.second; ++It) {
2887 const Instruction &I = *It;
2888 if (llvm::is_contained(IgnoreInsts, &I))
2889 continue;
2890 // assume intrinsic can be ignored
2891 if (auto *II = dyn_cast<IntrinsicInst>(Val: &I)) {
2892 if (II->getIntrinsicID() == Intrinsic::assume)
2893 continue;
2894 }
2895 // Parts based on isSafeToMoveBefore from CoveMoverUtils.cpp.
2896 if (I.mayThrow())
2897 return false;
2898 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
2899 if (!CB->hasFnAttr(Kind: Attribute::WillReturn))
2900 return false;
2901 if (!CB->hasFnAttr(Kind: Attribute::NoSync))
2902 return false;
2903 }
2904 if (I.mayReadOrWriteMemory()) {
2905 auto MaybeLocI = getLocOrNone(I);
2906 if (MayWrite || I.mayWriteToMemory()) {
2907 if (!MaybeLoc || !MaybeLocI)
2908 return false;
2909 if (!AA.isNoAlias(*MaybeLoc, *MaybeLocI))
2910 return false;
2911 }
2912 }
2913 }
2914 return true;
2915}
2916
2917auto HexagonVectorCombine::isByteVecTy(Type *Ty) const -> bool {
2918 if (auto *VecTy = dyn_cast<VectorType>(Val: Ty))
2919 return VecTy->getElementType() == getByteTy();
2920 return false;
2921}
2922
2923auto HexagonVectorCombine::getElementRange(IRBuilderBase &Builder, Value *Lo,
2924 Value *Hi, int Start,
2925 int Length) const -> Value * {
2926 assert(0 <= Start && size_t(Start + Length) < length(Lo) + length(Hi));
2927 SmallVector<int, 128> SMask(Length);
2928 std::iota(first: SMask.begin(), last: SMask.end(), value: Start);
2929 return Builder.CreateShuffleVector(V1: Lo, V2: Hi, Mask: SMask, Name: "shf");
2930}
2931
2932// Pass management.
2933
2934namespace llvm {
2935void initializeHexagonVectorCombineLegacyPass(PassRegistry &);
2936FunctionPass *createHexagonVectorCombineLegacyPass();
2937} // namespace llvm
2938
2939namespace {
2940class HexagonVectorCombineLegacy : public FunctionPass {
2941public:
2942 static char ID;
2943
2944 HexagonVectorCombineLegacy() : FunctionPass(ID) {}
2945
2946 StringRef getPassName() const override { return "Hexagon Vector Combine"; }
2947
2948 void getAnalysisUsage(AnalysisUsage &AU) const override {
2949 AU.setPreservesCFG();
2950 AU.addRequired<AAResultsWrapperPass>();
2951 AU.addRequired<AssumptionCacheTracker>();
2952 AU.addRequired<DominatorTreeWrapperPass>();
2953 AU.addRequired<ScalarEvolutionWrapperPass>();
2954 AU.addRequired<TargetLibraryInfoWrapperPass>();
2955 AU.addRequired<TargetPassConfig>();
2956 FunctionPass::getAnalysisUsage(AU);
2957 }
2958
2959 bool runOnFunction(Function &F) override {
2960 if (skipFunction(F))
2961 return false;
2962 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2963 AssumptionCache &AC =
2964 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
2965 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2966 ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
2967 TargetLibraryInfo &TLI =
2968 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
2969 auto &TM = getAnalysis<TargetPassConfig>().getTM<HexagonTargetMachine>();
2970 HexagonVectorCombine HVC(F, AA, AC, DT, SE, TLI, TM);
2971 return HVC.run();
2972 }
2973};
2974} // namespace
2975
2976char HexagonVectorCombineLegacy::ID = 0;
2977
2978INITIALIZE_PASS_BEGIN(HexagonVectorCombineLegacy, DEBUG_TYPE,
2979 "Hexagon Vector Combine", false, false)
2980INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
2981INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
2982INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
2983INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
2984INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
2985INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
2986INITIALIZE_PASS_END(HexagonVectorCombineLegacy, DEBUG_TYPE,
2987 "Hexagon Vector Combine", false, false)
2988
2989FunctionPass *llvm::createHexagonVectorCombineLegacyPass() {
2990 return new HexagonVectorCombineLegacy();
2991}
2992