LLVM 17.0.0git
HexagonVectorCombine.cpp
Go to the documentation of this file.
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//===----------------------------------------------------------------------===//
13
14#include "llvm/ADT/APInt.h"
15#include "llvm/ADT/ArrayRef.h"
16#include "llvm/ADT/DenseMap.h"
17#include "llvm/ADT/STLExtras.h"
28#include "llvm/IR/Dominators.h"
29#include "llvm/IR/IRBuilder.h"
31#include "llvm/IR/Intrinsics.h"
32#include "llvm/IR/IntrinsicsHexagon.h"
33#include "llvm/IR/Metadata.h"
36#include "llvm/Pass.h"
42
43#include "HexagonSubtarget.h"
45
46#include <algorithm>
47#include <deque>
48#include <map>
49#include <optional>
50#include <set>
51#include <utility>
52#include <vector>
53
54#define DEBUG_TYPE "hexagon-vc"
55
56using namespace llvm;
57
58namespace {
59class HexagonVectorCombine {
60public:
61 HexagonVectorCombine(Function &F_, AliasAnalysis &AA_, AssumptionCache &AC_,
63 const TargetMachine &TM_)
64 : F(F_), DL(F.getParent()->getDataLayout()), AA(AA_), AC(AC_), DT(DT_),
65 TLI(TLI_),
66 HST(static_cast<const HexagonSubtarget &>(*TM_.getSubtargetImpl(F))) {}
67
68 bool run();
69
70 // Common integer type.
71 IntegerType *getIntTy(unsigned Width = 32) const;
72 // Byte type: either scalar (when Length = 0), or vector with given
73 // element count.
74 Type *getByteTy(int ElemCount = 0) const;
75 // Boolean type: either scalar (when Length = 0), or vector with given
76 // element count.
77 Type *getBoolTy(int ElemCount = 0) const;
78 // Create a ConstantInt of type returned by getIntTy with the value Val.
79 ConstantInt *getConstInt(int Val, unsigned Width = 32) const;
80 // Get the integer value of V, if it exists.
81 std::optional<APInt> getIntValue(const Value *Val) const;
82 // Is V a constant 0, or a vector of 0s?
83 bool isZero(const Value *Val) const;
84 // Is V an undef value?
85 bool isUndef(const Value *Val) const;
86
87 // Get HVX vector type with the given element type.
88 VectorType *getHvxTy(Type *ElemTy, bool Pair = false) const;
89
90 enum SizeKind {
91 Store, // Store size
92 Alloc, // Alloc size
93 };
94 int getSizeOf(const Value *Val, SizeKind Kind = Store) const;
95 int getSizeOf(const Type *Ty, SizeKind Kind = Store) const;
96 int getTypeAlignment(Type *Ty) const;
97 size_t length(Value *Val) const;
98 size_t length(Type *Ty) const;
99
100 Constant *getNullValue(Type *Ty) const;
101 Constant *getFullValue(Type *Ty) const;
102 Constant *getConstSplat(Type *Ty, int Val) const;
103
104 Value *simplify(Value *Val) const;
105
106 Value *insertb(IRBuilderBase &Builder, Value *Dest, Value *Src, int Start,
107 int Length, int Where) const;
108 Value *vlalignb(IRBuilderBase &Builder, Value *Lo, Value *Hi,
109 Value *Amt) const;
110 Value *vralignb(IRBuilderBase &Builder, Value *Lo, Value *Hi,
111 Value *Amt) const;
113 Value *vresize(IRBuilderBase &Builder, Value *Val, int NewSize,
114 Value *Pad) const;
115 Value *rescale(IRBuilderBase &Builder, Value *Mask, Type *FromTy,
116 Type *ToTy) const;
117 Value *vlsb(IRBuilderBase &Builder, Value *Val) const;
118 Value *vbytes(IRBuilderBase &Builder, Value *Val) const;
119 Value *subvector(IRBuilderBase &Builder, Value *Val, unsigned Start,
120 unsigned Length) const;
121 Value *sublo(IRBuilderBase &Builder, Value *Val) const;
122 Value *subhi(IRBuilderBase &Builder, Value *Val) const;
123 Value *vdeal(IRBuilderBase &Builder, Value *Val0, Value *Val1) const;
124 Value *vshuff(IRBuilderBase &Builder, Value *Val0, Value *Val1) const;
125
126 Value *createHvxIntrinsic(IRBuilderBase &Builder, Intrinsic::ID IntID,
128 ArrayRef<Type *> ArgTys = std::nullopt) const;
129 SmallVector<Value *> splitVectorElements(IRBuilderBase &Builder, Value *Vec,
130 unsigned ToWidth) const;
131 Value *joinVectorElements(IRBuilderBase &Builder, ArrayRef<Value *> Values,
132 VectorType *ToType) const;
133
134 std::optional<int> calculatePointerDifference(Value *Ptr0, Value *Ptr1) const;
135
136 unsigned getNumSignificantBits(const Value *V,
137 const Instruction *CtxI = nullptr) const;
138 KnownBits getKnownBits(const Value *V,
139 const Instruction *CtxI = nullptr) const;
140
141 template <typename T = std::vector<Instruction *>>
142 bool isSafeToMoveBeforeInBB(const Instruction &In,
144 const T &IgnoreInsts = {}) const;
145
146 // This function is only used for assertions at the moment.
147 [[maybe_unused]] bool isByteVecTy(Type *Ty) const;
148
149 Function &F;
150 const DataLayout &DL;
151 AliasAnalysis &AA;
152 AssumptionCache &AC;
153 DominatorTree &DT;
155 const HexagonSubtarget &HST;
156
157private:
158 Value *getElementRange(IRBuilderBase &Builder, Value *Lo, Value *Hi,
159 int Start, int Length) const;
160};
161
162class AlignVectors {
163public:
164 AlignVectors(const HexagonVectorCombine &HVC_) : HVC(HVC_) {}
165
166 bool run();
167
168private:
169 using InstList = std::vector<Instruction *>;
170
171 struct Segment {
172 void *Data;
173 int Start;
174 int Size;
175 };
176
177 struct AddrInfo {
178 AddrInfo(const AddrInfo &) = default;
179 AddrInfo(const HexagonVectorCombine &HVC, Instruction *I, Value *A, Type *T,
180 Align H)
181 : Inst(I), Addr(A), ValTy(T), HaveAlign(H),
182 NeedAlign(HVC.getTypeAlignment(ValTy)) {}
183 AddrInfo &operator=(const AddrInfo &) = default;
184
185 // XXX: add Size member?
186 Instruction *Inst;
187 Value *Addr;
188 Type *ValTy;
189 Align HaveAlign;
190 Align NeedAlign;
191 int Offset = 0; // Offset (in bytes) from the first member of the
192 // containing AddrList.
193 };
194 using AddrList = std::vector<AddrInfo>;
195
196 struct InstrLess {
197 bool operator()(const Instruction *A, const Instruction *B) const {
198 return A->comesBefore(B);
199 }
200 };
201 using DepList = std::set<Instruction *, InstrLess>;
202
203 struct MoveGroup {
204 MoveGroup(const AddrInfo &AI, Instruction *B, bool Hvx, bool Load)
205 : Base(B), Main{AI.Inst}, IsHvx(Hvx), IsLoad(Load) {}
206 Instruction *Base; // Base instruction of the parent address group.
207 InstList Main; // Main group of instructions.
208 InstList Deps; // List of dependencies.
209 bool IsHvx; // Is this group of HVX instructions?
210 bool IsLoad; // Is this a load group?
211 };
212 using MoveList = std::vector<MoveGroup>;
213
214 struct ByteSpan {
215 struct Segment {
216 // Segment of a Value: 'Len' bytes starting at byte 'Begin'.
217 Segment(Value *Val, int Begin, int Len)
218 : Val(Val), Start(Begin), Size(Len) {}
219 Segment(const Segment &Seg) = default;
220 Segment &operator=(const Segment &Seg) = default;
221 Value *Val; // Value representable as a sequence of bytes.
222 int Start; // First byte of the value that belongs to the segment.
223 int Size; // Number of bytes in the segment.
224 };
225
226 struct Block {
227 Block(Value *Val, int Len, int Pos) : Seg(Val, 0, Len), Pos(Pos) {}
228 Block(Value *Val, int Off, int Len, int Pos)
229 : Seg(Val, Off, Len), Pos(Pos) {}
230 Block(const Block &Blk) = default;
231 Block &operator=(const Block &Blk) = default;
232 Segment Seg; // Value segment.
233 int Pos; // Position (offset) of the segment in the Block.
234 };
235
236 int extent() const;
237 ByteSpan section(int Start, int Length) const;
238 ByteSpan &shift(int Offset);
240
241 int size() const { return Blocks.size(); }
242 Block &operator[](int i) { return Blocks[i]; }
243
244 std::vector<Block> Blocks;
245
246 using iterator = decltype(Blocks)::iterator;
247 iterator begin() { return Blocks.begin(); }
248 iterator end() { return Blocks.end(); }
249 using const_iterator = decltype(Blocks)::const_iterator;
250 const_iterator begin() const { return Blocks.begin(); }
251 const_iterator end() const { return Blocks.end(); }
252 };
253
254 Align getAlignFromValue(const Value *V) const;
255 std::optional<MemoryLocation> getLocation(const Instruction &In) const;
256 std::optional<AddrInfo> getAddrInfo(Instruction &In) const;
257 bool isHvx(const AddrInfo &AI) const;
258 // This function is only used for assertions at the moment.
259 [[maybe_unused]] bool isSectorTy(Type *Ty) const;
260
261 Value *getPayload(Value *Val) const;
262 Value *getMask(Value *Val) const;
263 Value *getPassThrough(Value *Val) const;
264
265 Value *createAdjustedPointer(IRBuilderBase &Builder, Value *Ptr, Type *ValTy,
266 int Adjust) const;
267 Value *createAlignedPointer(IRBuilderBase &Builder, Value *Ptr, Type *ValTy,
268 int Alignment) const;
269 Value *createAlignedLoad(IRBuilderBase &Builder, Type *ValTy, Value *Ptr,
270 int Alignment, Value *Mask, Value *PassThru) const;
271 Value *createAlignedStore(IRBuilderBase &Builder, Value *Val, Value *Ptr,
272 int Alignment, Value *Mask) const;
273
274 DepList getUpwardDeps(Instruction *In, Instruction *Base) const;
275 bool createAddressGroups();
276 MoveList createLoadGroups(const AddrList &Group) const;
277 MoveList createStoreGroups(const AddrList &Group) const;
278 bool move(const MoveGroup &Move) const;
279 void realignLoadGroup(IRBuilderBase &Builder, const ByteSpan &VSpan,
280 int ScLen, Value *AlignVal, Value *AlignAddr) const;
281 void realignStoreGroup(IRBuilderBase &Builder, const ByteSpan &VSpan,
282 int ScLen, Value *AlignVal, Value *AlignAddr) const;
283 bool realignGroup(const MoveGroup &Move) const;
284
285 friend raw_ostream &operator<<(raw_ostream &OS, const AddrInfo &AI);
286 friend raw_ostream &operator<<(raw_ostream &OS, const MoveGroup &MG);
287 friend raw_ostream &operator<<(raw_ostream &OS, const ByteSpan::Block &B);
288 friend raw_ostream &operator<<(raw_ostream &OS, const ByteSpan &BS);
289
290 std::map<Instruction *, AddrList> AddrGroups;
291 const HexagonVectorCombine &HVC;
292};
293
295raw_ostream &operator<<(raw_ostream &OS, const AlignVectors::AddrInfo &AI) {
296 OS << "Inst: " << AI.Inst << " " << *AI.Inst << '\n';
297 OS << "Addr: " << *AI.Addr << '\n';
298 OS << "Type: " << *AI.ValTy << '\n';
299 OS << "HaveAlign: " << AI.HaveAlign.value() << '\n';
300 OS << "NeedAlign: " << AI.NeedAlign.value() << '\n';
301 OS << "Offset: " << AI.Offset;
302 return OS;
303}
304
306raw_ostream &operator<<(raw_ostream &OS, const AlignVectors::MoveGroup &MG) {
307 OS << "IsLoad:" << (MG.IsLoad ? "yes" : "no");
308 OS << ", IsHvx:" << (MG.IsHvx ? "yes" : "no") << '\n';
309 OS << "Main\n";
310 for (Instruction *I : MG.Main)
311 OS << " " << *I << '\n';
312 OS << "Deps\n";
313 for (Instruction *I : MG.Deps)
314 OS << " " << *I << '\n';
315 return OS;
316}
317
320 const AlignVectors::ByteSpan::Block &B) {
321 OS << " @" << B.Pos << " [" << B.Seg.Start << ',' << B.Seg.Size << "] ";
322 if (B.Seg.Val == reinterpret_cast<const Value *>(&B)) {
323 OS << "(self:" << B.Seg.Val << ')';
324 } else if (B.Seg.Val != nullptr) {
325 OS << *B.Seg.Val;
326 } else {
327 OS << "(null)";
328 }
329 return OS;
330}
331
333raw_ostream &operator<<(raw_ostream &OS, const AlignVectors::ByteSpan &BS) {
334 OS << "ByteSpan[size=" << BS.size() << ", extent=" << BS.extent() << '\n';
335 for (const AlignVectors::ByteSpan::Block &B : BS)
336 OS << B << '\n';
337 OS << ']';
338 return OS;
339}
340
341class HvxIdioms {
342public:
343 HvxIdioms(const HexagonVectorCombine &HVC_) : HVC(HVC_) {
344 auto *Int32Ty = HVC.getIntTy(32);
345 HvxI32Ty = HVC.getHvxTy(Int32Ty, /*Pair=*/false);
346 HvxP32Ty = HVC.getHvxTy(Int32Ty, /*Pair=*/true);
347 }
348
349 bool run();
350
351private:
352 enum Signedness { Positive, Signed, Unsigned };
353
354 // Value + sign
355 // This is to keep track of whether the value should be treated as signed
356 // or unsigned, or is known to be positive.
357 struct SValue {
358 Value *Val;
359 Signedness Sgn;
360 };
361
362 struct FxpOp {
363 unsigned Opcode;
364 unsigned Frac; // Number of fraction bits
365 SValue X, Y;
366 // If present, add 1 << RoundAt before shift:
367 std::optional<unsigned> RoundAt;
368 VectorType *ResTy;
369 };
370
371 auto getNumSignificantBits(Value *V, Instruction *In) const
372 -> std::pair<unsigned, Signedness>;
373 auto canonSgn(SValue X, SValue Y) const -> std::pair<SValue, SValue>;
374
375 auto matchFxpMul(Instruction &In) const -> std::optional<FxpOp>;
376 auto processFxpMul(Instruction &In, const FxpOp &Op) const -> Value *;
377
378 auto processFxpMulChopped(IRBuilderBase &Builder, Instruction &In,
379 const FxpOp &Op) const -> Value *;
380 auto createMulQ15(IRBuilderBase &Builder, SValue X, SValue Y,
381 bool Rounding) const -> Value *;
382 auto createMulQ31(IRBuilderBase &Builder, SValue X, SValue Y,
383 bool Rounding) const -> Value *;
384 // Return {Result, Carry}, where Carry is a vector predicate.
385 auto createAddCarry(IRBuilderBase &Builder, Value *X, Value *Y,
386 Value *CarryIn = nullptr) const
387 -> std::pair<Value *, Value *>;
388 auto createMul16(IRBuilderBase &Builder, SValue X, SValue Y) const -> Value *;
389 auto createMulH16(IRBuilderBase &Builder, SValue X, SValue Y) const
390 -> Value *;
391 auto createMul32(IRBuilderBase &Builder, SValue X, SValue Y) const
392 -> std::pair<Value *, Value *>;
393 auto createAddLong(IRBuilderBase &Builder, ArrayRef<Value *> WordX,
395 auto createMulLong(IRBuilderBase &Builder, ArrayRef<Value *> WordX,
396 Signedness SgnX, ArrayRef<Value *> WordY,
397 Signedness SgnY) const -> SmallVector<Value *>;
398
399 VectorType *HvxI32Ty;
400 VectorType *HvxP32Ty;
401 const HexagonVectorCombine &HVC;
402
403 friend raw_ostream &operator<<(raw_ostream &, const FxpOp &);
404};
405
406[[maybe_unused]] raw_ostream &operator<<(raw_ostream &OS,
407 const HvxIdioms::FxpOp &Op) {
408 static const char *SgnNames[] = {"Positive", "Signed", "Unsigned"};
409 OS << Instruction::getOpcodeName(Op.Opcode) << '.' << Op.Frac;
410 if (Op.RoundAt.has_value()) {
411 if (Op.Frac != 0 && *Op.RoundAt == Op.Frac - 1) {
412 OS << ":rnd";
413 } else {
414 OS << " + 1<<" << *Op.RoundAt;
415 }
416 }
417 OS << "\n X:(" << SgnNames[Op.X.Sgn] << ") " << *Op.X.Val << "\n"
418 << " Y:(" << SgnNames[Op.Y.Sgn] << ") " << *Op.Y.Val;
419 return OS;
420}
421
422} // namespace
423
424namespace {
425
426template <typename T> T *getIfUnordered(T *MaybeT) {
427 return MaybeT && MaybeT->isUnordered() ? MaybeT : nullptr;
428}
429template <typename T> T *isCandidate(Instruction *In) {
430 return dyn_cast<T>(In);
431}
432template <> LoadInst *isCandidate<LoadInst>(Instruction *In) {
433 return getIfUnordered(dyn_cast<LoadInst>(In));
434}
435template <> StoreInst *isCandidate<StoreInst>(Instruction *In) {
436 return getIfUnordered(dyn_cast<StoreInst>(In));
437}
438
439#if !defined(_MSC_VER) || _MSC_VER >= 1926
440// VS2017 and some versions of VS2019 have trouble compiling this:
441// error C2976: 'std::map': too few template arguments
442// VS 2019 16.x is known to work, except for 16.4/16.5 (MSC_VER 1924/1925)
443template <typename Pred, typename... Ts>
444void erase_if(std::map<Ts...> &map, Pred p)
445#else
446template <typename Pred, typename T, typename U>
447void erase_if(std::map<T, U> &map, Pred p)
448#endif
449{
450 for (auto i = map.begin(), e = map.end(); i != e;) {
451 if (p(*i))
452 i = map.erase(i);
453 else
454 i = std::next(i);
455 }
456}
457
458// Forward other erase_ifs to the LLVM implementations.
459template <typename Pred, typename T> void erase_if(T &&container, Pred p) {
460 llvm::erase_if(std::forward<T>(container), p);
461}
462
463} // namespace
464
465// --- Begin AlignVectors
466
467auto AlignVectors::ByteSpan::extent() const -> int {
468 if (size() == 0)
469 return 0;
470 int Min = Blocks[0].Pos;
471 int Max = Blocks[0].Pos + Blocks[0].Seg.Size;
472 for (int i = 1, e = size(); i != e; ++i) {
473 Min = std::min(Min, Blocks[i].Pos);
474 Max = std::max(Max, Blocks[i].Pos + Blocks[i].Seg.Size);
475 }
476 return Max - Min;
477}
478
479auto AlignVectors::ByteSpan::section(int Start, int Length) const -> ByteSpan {
480 ByteSpan Section;
481 for (const ByteSpan::Block &B : Blocks) {
482 int L = std::max(B.Pos, Start); // Left end.
483 int R = std::min(B.Pos + B.Seg.Size, Start + Length); // Right end+1.
484 if (L < R) {
485 // How much to chop off the beginning of the segment:
486 int Off = L > B.Pos ? L - B.Pos : 0;
487 Section.Blocks.emplace_back(B.Seg.Val, B.Seg.Start + Off, R - L, L);
488 }
489 }
490 return Section;
491}
492
493auto AlignVectors::ByteSpan::shift(int Offset) -> ByteSpan & {
494 for (Block &B : Blocks)
495 B.Pos += Offset;
496 return *this;
497}
498
499auto AlignVectors::ByteSpan::values() const -> SmallVector<Value *, 8> {
500 SmallVector<Value *, 8> Values(Blocks.size());
501 for (int i = 0, e = Blocks.size(); i != e; ++i)
502 Values[i] = Blocks[i].Seg.Val;
503 return Values;
504}
505
506auto AlignVectors::getAlignFromValue(const Value *V) const -> Align {
507 const auto *C = dyn_cast<ConstantInt>(V);
508 assert(C && "Alignment must be a compile-time constant integer");
509 return C->getAlignValue();
510}
511
512auto AlignVectors::getAddrInfo(Instruction &In) const
513 -> std::optional<AddrInfo> {
514 if (auto *L = isCandidate<LoadInst>(&In))
515 return AddrInfo(HVC, L, L->getPointerOperand(), L->getType(),
516 L->getAlign());
517 if (auto *S = isCandidate<StoreInst>(&In))
518 return AddrInfo(HVC, S, S->getPointerOperand(),
519 S->getValueOperand()->getType(), S->getAlign());
520 if (auto *II = isCandidate<IntrinsicInst>(&In)) {
521 Intrinsic::ID ID = II->getIntrinsicID();
522 switch (ID) {
523 case Intrinsic::masked_load:
524 return AddrInfo(HVC, II, II->getArgOperand(0), II->getType(),
525 getAlignFromValue(II->getArgOperand(1)));
526 case Intrinsic::masked_store:
527 return AddrInfo(HVC, II, II->getArgOperand(1),
528 II->getArgOperand(0)->getType(),
529 getAlignFromValue(II->getArgOperand(2)));
530 }
531 }
532 return std::nullopt;
533}
534
535auto AlignVectors::isHvx(const AddrInfo &AI) const -> bool {
536 return HVC.HST.isTypeForHVX(AI.ValTy);
537}
538
539auto AlignVectors::getPayload(Value *Val) const -> Value * {
540 if (auto *In = dyn_cast<Instruction>(Val)) {
541 Intrinsic::ID ID = 0;
542 if (auto *II = dyn_cast<IntrinsicInst>(In))
543 ID = II->getIntrinsicID();
544 if (isa<StoreInst>(In) || ID == Intrinsic::masked_store)
545 return In->getOperand(0);
546 }
547 return Val;
548}
549
550auto AlignVectors::getMask(Value *Val) const -> Value * {
551 if (auto *II = dyn_cast<IntrinsicInst>(Val)) {
552 switch (II->getIntrinsicID()) {
553 case Intrinsic::masked_load:
554 return II->getArgOperand(2);
555 case Intrinsic::masked_store:
556 return II->getArgOperand(3);
557 }
558 }
559
560 Type *ValTy = getPayload(Val)->getType();
561 if (auto *VecTy = dyn_cast<VectorType>(ValTy))
562 return HVC.getFullValue(HVC.getBoolTy(HVC.length(VecTy)));
563 return HVC.getFullValue(HVC.getBoolTy());
564}
565
566auto AlignVectors::getPassThrough(Value *Val) const -> Value * {
567 if (auto *II = dyn_cast<IntrinsicInst>(Val)) {
568 if (II->getIntrinsicID() == Intrinsic::masked_load)
569 return II->getArgOperand(3);
570 }
571 return UndefValue::get(getPayload(Val)->getType());
572}
573
574auto AlignVectors::createAdjustedPointer(IRBuilderBase &Builder, Value *Ptr,
575 Type *ValTy, int Adjust) const
576 -> Value * {
577 // The adjustment is in bytes, but if it's a multiple of the type size,
578 // we don't need to do pointer casts.
579 auto *PtrTy = cast<PointerType>(Ptr->getType());
580 if (!PtrTy->isOpaque()) {
581 Type *ElemTy = PtrTy->getNonOpaquePointerElementType();
582 int ElemSize = HVC.getSizeOf(ElemTy, HVC.Alloc);
583 if (Adjust % ElemSize == 0 && Adjust != 0) {
584 Value *Tmp0 = Builder.CreateGEP(
585 ElemTy, Ptr, HVC.getConstInt(Adjust / ElemSize), "gep");
586 return Builder.CreatePointerCast(Tmp0, ValTy->getPointerTo(), "cst");
587 }
588 }
589
590 PointerType *CharPtrTy = Type::getInt8PtrTy(HVC.F.getContext());
591 Value *Tmp0 = Builder.CreatePointerCast(Ptr, CharPtrTy, "cst");
592 Value *Tmp1 = Builder.CreateGEP(Type::getInt8Ty(HVC.F.getContext()), Tmp0,
593 HVC.getConstInt(Adjust), "gep");
594 return Builder.CreatePointerCast(Tmp1, ValTy->getPointerTo(), "cst");
595}
596
597auto AlignVectors::createAlignedPointer(IRBuilderBase &Builder, Value *Ptr,
598 Type *ValTy, int Alignment) const
599 -> Value * {
600 Value *AsInt = Builder.CreatePtrToInt(Ptr, HVC.getIntTy(), "pti");
601 Value *Mask = HVC.getConstInt(-Alignment);
602 Value *And = Builder.CreateAnd(AsInt, Mask, "add");
603 return Builder.CreateIntToPtr(And, ValTy->getPointerTo(), "itp");
604}
605
606auto AlignVectors::createAlignedLoad(IRBuilderBase &Builder, Type *ValTy,
607 Value *Ptr, int Alignment, Value *Mask,
608 Value *PassThru) const -> Value * {
609 assert(!HVC.isUndef(Mask)); // Should this be allowed?
610 if (HVC.isZero(Mask))
611 return PassThru;
612 if (Mask == ConstantInt::getTrue(Mask->getType()))
613 return Builder.CreateAlignedLoad(ValTy, Ptr, Align(Alignment), "ald");
614 return Builder.CreateMaskedLoad(ValTy, Ptr, Align(Alignment), Mask, PassThru,
615 "mld");
616}
617
618auto AlignVectors::createAlignedStore(IRBuilderBase &Builder, Value *Val,
619 Value *Ptr, int Alignment,
620 Value *Mask) const -> Value * {
621 if (HVC.isZero(Mask) || HVC.isUndef(Val) || HVC.isUndef(Mask))
622 return UndefValue::get(Val->getType());
623 if (Mask == ConstantInt::getTrue(Mask->getType()))
624 return Builder.CreateAlignedStore(Val, Ptr, Align(Alignment));
625 return Builder.CreateMaskedStore(Val, Ptr, Align(Alignment), Mask);
626}
627
628auto AlignVectors::getUpwardDeps(Instruction *In, Instruction *Base) const
629 -> DepList {
630 BasicBlock *Parent = Base->getParent();
631 assert(In->getParent() == Parent &&
632 "Base and In should be in the same block");
633 assert(Base->comesBefore(In) && "Base should come before In");
634
635 DepList Deps;
636 std::deque<Instruction *> WorkQ = {In};
637 while (!WorkQ.empty()) {
638 Instruction *D = WorkQ.front();
639 WorkQ.pop_front();
640 Deps.insert(D);
641 for (Value *Op : D->operands()) {
642 if (auto *I = dyn_cast<Instruction>(Op)) {
643 if (I->getParent() == Parent && Base->comesBefore(I))
644 WorkQ.push_back(I);
645 }
646 }
647 }
648 return Deps;
649}
650
651auto AlignVectors::createAddressGroups() -> bool {
652 // An address group created here may contain instructions spanning
653 // multiple basic blocks.
654 AddrList WorkStack;
655
656 auto findBaseAndOffset = [&](AddrInfo &AI) -> std::pair<Instruction *, int> {
657 for (AddrInfo &W : WorkStack) {
658 if (auto D = HVC.calculatePointerDifference(AI.Addr, W.Addr))
659 return std::make_pair(W.Inst, *D);
660 }
661 return std::make_pair(nullptr, 0);
662 };
663
664 auto traverseBlock = [&](DomTreeNode *DomN, auto Visit) -> void {
665 BasicBlock &Block = *DomN->getBlock();
666 for (Instruction &I : Block) {
667 auto AI = this->getAddrInfo(I); // Use this-> for gcc6.
668 if (!AI)
669 continue;
670 auto F = findBaseAndOffset(*AI);
671 Instruction *GroupInst;
672 if (Instruction *BI = F.first) {
673 AI->Offset = F.second;
674 GroupInst = BI;
675 } else {
676 WorkStack.push_back(*AI);
677 GroupInst = AI->Inst;
678 }
679 AddrGroups[GroupInst].push_back(*AI);
680 }
681
682 for (DomTreeNode *C : DomN->children())
683 Visit(C, Visit);
684
685 while (!WorkStack.empty() && WorkStack.back().Inst->getParent() == &Block)
686 WorkStack.pop_back();
687 };
688
689 traverseBlock(HVC.DT.getRootNode(), traverseBlock);
690 assert(WorkStack.empty());
691
692 // AddrGroups are formed.
693
694 // Remove groups of size 1.
695 erase_if(AddrGroups, [](auto &G) { return G.second.size() == 1; });
696 // Remove groups that don't use HVX types.
697 erase_if(AddrGroups, [&](auto &G) {
698 return llvm::none_of(
699 G.second, [&](auto &I) { return HVC.HST.isTypeForHVX(I.ValTy); });
700 });
701
702 return !AddrGroups.empty();
703}
704
705auto AlignVectors::createLoadGroups(const AddrList &Group) const -> MoveList {
706 // Form load groups.
707 // To avoid complications with moving code across basic blocks, only form
708 // groups that are contained within a single basic block.
709
710 auto tryAddTo = [&](const AddrInfo &Info, MoveGroup &Move) {
711 assert(!Move.Main.empty() && "Move group should have non-empty Main");
712 // Don't mix HVX and non-HVX instructions.
713 if (Move.IsHvx != isHvx(Info))
714 return false;
715 // Leading instruction in the load group.
716 Instruction *Base = Move.Main.front();
717 if (Base->getParent() != Info.Inst->getParent())
718 return false;
719
720 auto isSafeToMoveToBase = [&](const Instruction *I) {
721 return HVC.isSafeToMoveBeforeInBB(*I, Base->getIterator());
722 };
723 DepList Deps = getUpwardDeps(Info.Inst, Base);
724 if (!llvm::all_of(Deps, isSafeToMoveToBase))
725 return false;
726
727 // The dependencies will be moved together with the load, so make sure
728 // that none of them could be moved independently in another group.
729 Deps.erase(Info.Inst);
730 auto inAddrMap = [&](Instruction *I) { return AddrGroups.count(I) > 0; };
731 if (llvm::any_of(Deps, inAddrMap))
732 return false;
733 Move.Main.push_back(Info.Inst);
734 llvm::append_range(Move.Deps, Deps);
735 return true;
736 };
737
738 MoveList LoadGroups;
739
740 for (const AddrInfo &Info : Group) {
741 if (!Info.Inst->mayReadFromMemory())
742 continue;
743 if (LoadGroups.empty() || !tryAddTo(Info, LoadGroups.back()))
744 LoadGroups.emplace_back(Info, Group.front().Inst, isHvx(Info), true);
745 }
746
747 // Erase singleton groups.
748 erase_if(LoadGroups, [](const MoveGroup &G) { return G.Main.size() <= 1; });
749 return LoadGroups;
750}
751
752auto AlignVectors::createStoreGroups(const AddrList &Group) const -> MoveList {
753 // Form store groups.
754 // To avoid complications with moving code across basic blocks, only form
755 // groups that are contained within a single basic block.
756
757 auto tryAddTo = [&](const AddrInfo &Info, MoveGroup &Move) {
758 assert(!Move.Main.empty() && "Move group should have non-empty Main");
759 // For stores with return values we'd have to collect downward depenencies.
760 // There are no such stores that we handle at the moment, so omit that.
761 assert(Info.Inst->getType()->isVoidTy() &&
762 "Not handling stores with return values");
763 // Don't mix HVX and non-HVX instructions.
764 if (Move.IsHvx != isHvx(Info))
765 return false;
766 // For stores we need to be careful whether it's safe to move them.
767 // Stores that are otherwise safe to move together may not appear safe
768 // to move over one another (i.e. isSafeToMoveBefore may return false).
769 Instruction *Base = Move.Main.front();
770 if (Base->getParent() != Info.Inst->getParent())
771 return false;
772 if (!HVC.isSafeToMoveBeforeInBB(*Info.Inst, Base->getIterator(), Move.Main))
773 return false;
774 Move.Main.push_back(Info.Inst);
775 return true;
776 };
777
778 MoveList StoreGroups;
779
780 for (auto I = Group.rbegin(), E = Group.rend(); I != E; ++I) {
781 const AddrInfo &Info = *I;
782 if (!Info.Inst->mayWriteToMemory())
783 continue;
784 if (StoreGroups.empty() || !tryAddTo(Info, StoreGroups.back()))
785 StoreGroups.emplace_back(Info, Group.front().Inst, isHvx(Info), false);
786 }
787
788 // Erase singleton groups.
789 erase_if(StoreGroups, [](const MoveGroup &G) { return G.Main.size() <= 1; });
790 return StoreGroups;
791}
792
793auto AlignVectors::move(const MoveGroup &Move) const -> bool {
794 assert(!Move.Main.empty() && "Move group should have non-empty Main");
795 Instruction *Where = Move.Main.front();
796
797 if (Move.IsLoad) {
798 // Move all deps to before Where, keeping order.
799 for (Instruction *D : Move.Deps)
800 D->moveBefore(Where);
801 // Move all main instructions to after Where, keeping order.
802 ArrayRef<Instruction *> Main(Move.Main);
803 for (Instruction *M : Main.drop_front(1)) {
804 M->moveAfter(Where);
805 Where = M;
806 }
807 } else {
808 // NOTE: Deps are empty for "store" groups. If they need to be
809 // non-empty, decide on the order.
810 assert(Move.Deps.empty());
811 // Move all main instructions to before Where, inverting order.
812 ArrayRef<Instruction *> Main(Move.Main);
813 for (Instruction *M : Main.drop_front(1)) {
814 M->moveBefore(Where);
815 Where = M;
816 }
817 }
818
819 return Move.Main.size() + Move.Deps.size() > 1;
820}
821
822auto AlignVectors::realignLoadGroup(IRBuilderBase &Builder,
823 const ByteSpan &VSpan, int ScLen,
824 Value *AlignVal, Value *AlignAddr) const
825 -> void {
826 LLVM_DEBUG(dbgs() << __func__ << "\n");
827
828 Type *SecTy = HVC.getByteTy(ScLen);
829 int NumSectors = (VSpan.extent() + ScLen - 1) / ScLen;
830 bool DoAlign = !HVC.isZero(AlignVal);
831 BasicBlock::iterator BasePos = Builder.GetInsertPoint();
832 BasicBlock *BaseBlock = Builder.GetInsertBlock();
833
834 ByteSpan ASpan;
835 auto *True = HVC.getFullValue(HVC.getBoolTy(ScLen));
836 auto *Undef = UndefValue::get(SecTy);
837
838 SmallVector<Instruction *> Loads(NumSectors + DoAlign, nullptr);
839
840 // We could create all of the aligned loads, and generate the valigns
841 // at the location of the first load, but for large load groups, this
842 // could create highly suboptimal code (there have been groups of 140+
843 // loads in real code).
844 // Instead, place the loads/valigns as close to the users as possible.
845 // In any case we need to have a mapping from the blocks of VSpan (the
846 // span covered by the pre-existing loads) to ASpan (the span covered
847 // by the aligned loads). There is a small problem, though: ASpan needs
848 // to have pointers to the loads/valigns, but we don't know where to put
849 // them yet. We can't use nullptr, because when we create sections of
850 // ASpan (corresponding to blocks from VSpan), for each block in the
851 // section we need to know which blocks of ASpan they are a part of.
852 // To have 1-1 mapping between blocks of ASpan and the temporary value
853 // pointers, use the addresses of the blocks themselves.
854
855 // Populate the blocks first, to avoid reallocations of the vector
856 // interfering with generating the placeholder addresses.
857 for (int Index = 0; Index != NumSectors; ++Index)
858 ASpan.Blocks.emplace_back(nullptr, ScLen, Index * ScLen);
859 for (int Index = 0; Index != NumSectors; ++Index) {
860 ASpan.Blocks[Index].Seg.Val =
861 reinterpret_cast<Value *>(&ASpan.Blocks[Index]);
862 }
863
864 // Multiple values from VSpan can map to the same value in ASpan. Since we
865 // try to create loads lazily, we need to find the earliest use for each
866 // value from ASpan.
868 auto isEarlier = [](Instruction *A, Instruction *B) {
869 if (B == nullptr)
870 return true;
871 if (A == nullptr)
872 return false;
873 assert(A->getParent() == B->getParent());
874 return A->comesBefore(B);
875 };
876 auto earliestUser = [&](const auto &Uses) {
877 Instruction *User = nullptr;
878 for (const Use &U : Uses) {
879 auto *I = dyn_cast<Instruction>(U.getUser());
880 assert(I != nullptr && "Load used in a non-instruction?");
881 // Make sure we only consider at users in this block, but we need
882 // to remember if there were users outside the block too. This is
883 // because if no users are found, aligned loads will not be created.
884 if (I->getParent() == BaseBlock) {
885 if (!isa<PHINode>(I))
886 User = std::min(User, I, isEarlier);
887 } else {
888 User = std::min(User, BaseBlock->getTerminator(), isEarlier);
889 }
890 }
891 return User;
892 };
893
894 for (const ByteSpan::Block &B : VSpan) {
895 ByteSpan ASection = ASpan.section(B.Pos, B.Seg.Size);
896 for (const ByteSpan::Block &S : ASection) {
897 EarliestUser[S.Seg.Val] = std::min(
898 EarliestUser[S.Seg.Val], earliestUser(B.Seg.Val->uses()), isEarlier);
899 }
900 }
901
902 LLVM_DEBUG({
903 dbgs() << "ASpan:\n" << ASpan << '\n';
904 dbgs() << "Earliest users of ASpan:\n";
905 for (auto &[Val, User] : EarliestUser) {
906 dbgs() << Val << "\n ->" << *User << '\n';
907 }
908 });
909
910 auto createLoad = [&](IRBuilderBase &Builder, const ByteSpan &VSpan,
911 int Index) {
912 Value *Ptr =
913 createAdjustedPointer(Builder, AlignAddr, SecTy, Index * ScLen);
914 // FIXME: generate a predicated load?
915 Value *Load = createAlignedLoad(Builder, SecTy, Ptr, ScLen, True, Undef);
916 // If vector shifting is potentially needed, accumulate metadata
917 // from source sections of twice the load width.
918 int Start = (Index - DoAlign) * ScLen;
919 int Width = (1 + DoAlign) * ScLen;
920 propagateMetadata(cast<Instruction>(Load),
921 VSpan.section(Start, Width).values());
922 return cast<Instruction>(Load);
923 };
924
925 auto moveBefore = [this](Instruction *In, Instruction *To) {
926 // Move In and its upward dependencies to before To.
927 assert(In->getParent() == To->getParent());
928 DepList Deps = getUpwardDeps(In, To);
929 // DepList is sorted with respect to positions in the basic block.
930 for (Instruction *I : Deps)
931 I->moveBefore(To);
932 };
933
934 // Generate necessary loads at appropriate locations.
935 LLVM_DEBUG(dbgs() << "Creating loads for ASpan sectors\n");
936 for (int Index = 0; Index != NumSectors + 1; ++Index) {
937 // In ASpan, each block will be either a single aligned load, or a
938 // valign of a pair of loads. In the latter case, an aligned load j
939 // will belong to the current valign, and the one in the previous
940 // block (for j > 0).
941 // Place the load at a location which will dominate the valign, assuming
942 // the valign will be placed right before the earliest user.
943 Instruction *PrevAt =
944 DoAlign && Index > 0 ? EarliestUser[&ASpan[Index - 1]] : nullptr;
945 Instruction *ThisAt =
946 Index < NumSectors ? EarliestUser[&ASpan[Index]] : nullptr;
947 if (auto *Where = std::min(PrevAt, ThisAt, isEarlier)) {
948 Builder.SetInsertPoint(Where);
949 Loads[Index] = createLoad(Builder, VSpan, Index);
950 // We know it's safe to put the load at BasePos, but we'd prefer to put
951 // it at "Where". To see if the load is safe to be placed at Where, put
952 // it there first and then check if it's safe to move it to BasePos.
953 // If not, then the load needs to be placed at BasePos.
954 // We can't do this check proactively because we need the load to exist
955 // in order to check legality.
956 if (!HVC.isSafeToMoveBeforeInBB(*Loads[Index], BasePos))
957 moveBefore(Loads[Index], &*BasePos);
958 LLVM_DEBUG(dbgs() << "Loads[" << Index << "]:" << *Loads[Index] << '\n');
959 }
960 }
961
962 // Generate valigns if needed, and fill in proper values in ASpan
963 LLVM_DEBUG(dbgs() << "Creating values for ASpan sectors\n");
964 for (int Index = 0; Index != NumSectors; ++Index) {
965 ASpan[Index].Seg.Val = nullptr;
966 if (auto *Where = EarliestUser[&ASpan[Index]]) {
967 Builder.SetInsertPoint(Where);
968 Value *Val = Loads[Index];
969 assert(Val != nullptr);
970 if (DoAlign) {
971 Value *NextLoad = Loads[Index + 1];
972 assert(NextLoad != nullptr);
973 Val = HVC.vralignb(Builder, Val, NextLoad, AlignVal);
974 }
975 ASpan[Index].Seg.Val = Val;
976 LLVM_DEBUG(dbgs() << "ASpan[" << Index << "]:" << *Val << '\n');
977 }
978 }
979
980 for (const ByteSpan::Block &B : VSpan) {
981 ByteSpan ASection = ASpan.section(B.Pos, B.Seg.Size).shift(-B.Pos);
982 Value *Accum = UndefValue::get(HVC.getByteTy(B.Seg.Size));
983 Builder.SetInsertPoint(cast<Instruction>(B.Seg.Val));
984
985 // We're generating a reduction, where each instruction depends on
986 // the previous one, so we need to order them according to the position
987 // of their inputs in the code.
988 std::vector<ByteSpan::Block *> ABlocks;
989 for (ByteSpan::Block &S : ASection) {
990 if (S.Seg.Val != nullptr)
991 ABlocks.push_back(&S);
992 }
993 llvm::sort(ABlocks,
994 [&](const ByteSpan::Block *A, const ByteSpan::Block *B) {
995 return isEarlier(cast<Instruction>(A->Seg.Val),
996 cast<Instruction>(B->Seg.Val));
997 });
998 for (ByteSpan::Block *S : ABlocks) {
999 // The processing of the data loaded by the aligned loads
1000 // needs to be inserted after the data is available.
1001 Instruction *SegI = cast<Instruction>(S->Seg.Val);
1002 Builder.SetInsertPoint(&*std::next(SegI->getIterator()));
1003 Value *Pay = HVC.vbytes(Builder, getPayload(S->Seg.Val));
1004 Accum =
1005 HVC.insertb(Builder, Accum, Pay, S->Seg.Start, S->Seg.Size, S->Pos);
1006 }
1007 // Instead of casting everything to bytes for the vselect, cast to the
1008 // original value type. This will avoid complications with casting masks.
1009 // For example, in cases when the original mask applied to i32, it could
1010 // be converted to a mask applicable to i8 via pred_typecast intrinsic,
1011 // but if the mask is not exactly of HVX length, extra handling would be
1012 // needed to make it work.
1013 Type *ValTy = getPayload(B.Seg.Val)->getType();
1014 Value *Cast = Builder.CreateBitCast(Accum, ValTy, "cst");
1015 Value *Sel = Builder.CreateSelect(getMask(B.Seg.Val), Cast,
1016 getPassThrough(B.Seg.Val), "sel");
1017 B.Seg.Val->replaceAllUsesWith(Sel);
1018 }
1019}
1020
1021auto AlignVectors::realignStoreGroup(IRBuilderBase &Builder,
1022 const ByteSpan &VSpan, int ScLen,
1023 Value *AlignVal, Value *AlignAddr) const
1024 -> void {
1025 LLVM_DEBUG(dbgs() << __func__ << "\n");
1026
1027 Type *SecTy = HVC.getByteTy(ScLen);
1028 int NumSectors = (VSpan.extent() + ScLen - 1) / ScLen;
1029 bool DoAlign = !HVC.isZero(AlignVal);
1030
1031 // Stores.
1032 ByteSpan ASpanV, ASpanM;
1033
1034 // Return a vector value corresponding to the input value Val:
1035 // either <1 x Val> for scalar Val, or Val itself for vector Val.
1036 auto MakeVec = [](IRBuilderBase &Builder, Value *Val) -> Value * {
1037 Type *Ty = Val->getType();
1038 if (Ty->isVectorTy())
1039 return Val;
1040 auto *VecTy = VectorType::get(Ty, 1, /*Scalable=*/false);
1041 return Builder.CreateBitCast(Val, VecTy, "cst");
1042 };
1043
1044 // Create an extra "undef" sector at the beginning and at the end.
1045 // They will be used as the left/right filler in the vlalign step.
1046 for (int i = (DoAlign ? -1 : 0); i != NumSectors + DoAlign; ++i) {
1047 // For stores, the size of each section is an aligned vector length.
1048 // Adjust the store offsets relative to the section start offset.
1049 ByteSpan VSection = VSpan.section(i * ScLen, ScLen).shift(-i * ScLen);
1050 Value *AccumV = UndefValue::get(SecTy);
1051 Value *AccumM = HVC.getNullValue(SecTy);
1052 for (ByteSpan::Block &S : VSection) {
1053 Value *Pay = getPayload(S.Seg.Val);
1054 Value *Mask = HVC.rescale(Builder, MakeVec(Builder, getMask(S.Seg.Val)),
1055 Pay->getType(), HVC.getByteTy());
1056 AccumM = HVC.insertb(Builder, AccumM, HVC.vbytes(Builder, Mask),
1057 S.Seg.Start, S.Seg.Size, S.Pos);
1058 AccumV = HVC.insertb(Builder, AccumV, HVC.vbytes(Builder, Pay),
1059 S.Seg.Start, S.Seg.Size, S.Pos);
1060 }
1061 ASpanV.Blocks.emplace_back(AccumV, ScLen, i * ScLen);
1062 ASpanM.Blocks.emplace_back(AccumM, ScLen, i * ScLen);
1063 }
1064
1065 // vlalign
1066 if (DoAlign) {
1067 for (int j = 1; j != NumSectors + 2; ++j) {
1068 Value *PrevV = ASpanV[j - 1].Seg.Val, *ThisV = ASpanV[j].Seg.Val;
1069 Value *PrevM = ASpanM[j - 1].Seg.Val, *ThisM = ASpanM[j].Seg.Val;
1070 assert(isSectorTy(PrevV->getType()) && isSectorTy(PrevM->getType()));
1071 ASpanV[j - 1].Seg.Val = HVC.vlalignb(Builder, PrevV, ThisV, AlignVal);
1072 ASpanM[j - 1].Seg.Val = HVC.vlalignb(Builder, PrevM, ThisM, AlignVal);
1073 }
1074 }
1075
1076 for (int i = 0; i != NumSectors + DoAlign; ++i) {
1077 Value *Ptr = createAdjustedPointer(Builder, AlignAddr, SecTy, i * ScLen);
1078 Value *Val = ASpanV[i].Seg.Val;
1079 Value *Mask = ASpanM[i].Seg.Val; // bytes
1080 if (!HVC.isUndef(Val) && !HVC.isZero(Mask)) {
1081 Value *Store =
1082 createAlignedStore(Builder, Val, Ptr, ScLen, HVC.vlsb(Builder, Mask));
1083 // If vector shifting is potentially needed, accumulate metadata
1084 // from source sections of twice the store width.
1085 int Start = (i - DoAlign) * ScLen;
1086 int Width = (1 + DoAlign) * ScLen;
1087 propagateMetadata(cast<Instruction>(Store),
1088 VSpan.section(Start, Width).values());
1089 }
1090 }
1091}
1092
1093auto AlignVectors::realignGroup(const MoveGroup &Move) const -> bool {
1094 LLVM_DEBUG(dbgs() << "Realigning group:\n" << Move << '\n');
1095
1096 // TODO: Needs support for masked loads/stores of "scalar" vectors.
1097 if (!Move.IsHvx)
1098 return false;
1099
1100 // Return the element with the maximum alignment from Range,
1101 // where GetValue obtains the value to compare from an element.
1102 auto getMaxOf = [](auto Range, auto GetValue) {
1103 return *std::max_element(
1104 Range.begin(), Range.end(),
1105 [&GetValue](auto &A, auto &B) { return GetValue(A) < GetValue(B); });
1106 };
1107
1108 const AddrList &BaseInfos = AddrGroups.at(Move.Base);
1109
1110 // Conceptually, there is a vector of N bytes covering the addresses
1111 // starting from the minimum offset (i.e. Base.Addr+Start). This vector
1112 // represents a contiguous memory region that spans all accessed memory
1113 // locations.
1114 // The correspondence between loaded or stored values will be expressed
1115 // in terms of this vector. For example, the 0th element of the vector
1116 // from the Base address info will start at byte Start from the beginning
1117 // of this conceptual vector.
1118 //
1119 // This vector will be loaded/stored starting at the nearest down-aligned
1120 // address and the amount od the down-alignment will be AlignVal:
1121 // valign(load_vector(align_down(Base+Start)), AlignVal)
1122
1123 std::set<Instruction *> TestSet(Move.Main.begin(), Move.Main.end());
1124 AddrList MoveInfos;
1126 BaseInfos, std::back_inserter(MoveInfos),
1127 [&TestSet](const AddrInfo &AI) { return TestSet.count(AI.Inst); });
1128
1129 // Maximum alignment present in the whole address group.
1130 const AddrInfo &WithMaxAlign =
1131 getMaxOf(MoveInfos, [](const AddrInfo &AI) { return AI.HaveAlign; });
1132 Align MaxGiven = WithMaxAlign.HaveAlign;
1133
1134 // Minimum alignment present in the move address group.
1135 const AddrInfo &WithMinOffset =
1136 getMaxOf(MoveInfos, [](const AddrInfo &AI) { return -AI.Offset; });
1137
1138 const AddrInfo &WithMaxNeeded =
1139 getMaxOf(MoveInfos, [](const AddrInfo &AI) { return AI.NeedAlign; });
1140 Align MinNeeded = WithMaxNeeded.NeedAlign;
1141
1142 // Set the builder's insertion point right before the load group, or
1143 // immediately after the store group. (Instructions in a store group are
1144 // listed in reverse order.)
1145 Instruction *InsertAt = Move.Main.front();
1146 if (!Move.IsLoad) {
1147 // There should be a terminator (which store isn't, but check anyways).
1148 assert(InsertAt->getIterator() != InsertAt->getParent()->end());
1149 InsertAt = &*std::next(InsertAt->getIterator());
1150 }
1151
1152 IRBuilder Builder(InsertAt->getParent(), InsertAt->getIterator(),
1153 InstSimplifyFolder(HVC.DL));
1154 Value *AlignAddr = nullptr; // Actual aligned address.
1155 Value *AlignVal = nullptr; // Right-shift amount (for valign).
1156
1157 if (MinNeeded <= MaxGiven) {
1158 int Start = WithMinOffset.Offset;
1159 int OffAtMax = WithMaxAlign.Offset;
1160 // Shift the offset of the maximally aligned instruction (OffAtMax)
1161 // back by just enough multiples of the required alignment to cover the
1162 // distance from Start to OffAtMax.
1163 // Calculate the address adjustment amount based on the address with the
1164 // maximum alignment. This is to allow a simple gep instruction instead
1165 // of potential bitcasts to i8*.
1166 int Adjust = -alignTo(OffAtMax - Start, MinNeeded.value());
1167 AlignAddr = createAdjustedPointer(Builder, WithMaxAlign.Addr,
1168 WithMaxAlign.ValTy, Adjust);
1169 int Diff = Start - (OffAtMax + Adjust);
1170 AlignVal = HVC.getConstInt(Diff);
1171 assert(Diff >= 0);
1172 assert(static_cast<decltype(MinNeeded.value())>(Diff) < MinNeeded.value());
1173 } else {
1174 // WithMinOffset is the lowest address in the group,
1175 // WithMinOffset.Addr = Base+Start.
1176 // Align instructions for both HVX (V6_valign) and scalar (S2_valignrb)
1177 // mask off unnecessary bits, so it's ok to just the original pointer as
1178 // the alignment amount.
1179 // Do an explicit down-alignment of the address to avoid creating an
1180 // aligned instruction with an address that is not really aligned.
1181 AlignAddr = createAlignedPointer(Builder, WithMinOffset.Addr,
1182 WithMinOffset.ValTy, MinNeeded.value());
1183 AlignVal =
1184 Builder.CreatePtrToInt(WithMinOffset.Addr, HVC.getIntTy(), "pti");
1185 }
1186
1187 ByteSpan VSpan;
1188 for (const AddrInfo &AI : MoveInfos) {
1189 VSpan.Blocks.emplace_back(AI.Inst, HVC.getSizeOf(AI.ValTy),
1190 AI.Offset - WithMinOffset.Offset);
1191 }
1192
1193 // The aligned loads/stores will use blocks that are either scalars,
1194 // or HVX vectors. Let "sector" be the unified term for such a block.
1195 // blend(scalar, vector) -> sector...
1196 int ScLen = Move.IsHvx ? HVC.HST.getVectorLength()
1197 : std::max<int>(MinNeeded.value(), 4);
1198 assert(!Move.IsHvx || ScLen == 64 || ScLen == 128);
1199 assert(Move.IsHvx || ScLen == 4 || ScLen == 8);
1200
1201 LLVM_DEBUG({
1202 dbgs() << "ScLen: " << ScLen << "\n";
1203 dbgs() << "AlignVal:" << *AlignVal << "\n";
1204 dbgs() << "AlignAddr:" << *AlignAddr << "\n";
1205 dbgs() << "VSpan:\n" << VSpan << '\n';
1206 });
1207
1208 if (Move.IsLoad)
1209 realignLoadGroup(Builder, VSpan, ScLen, AlignVal, AlignAddr);
1210 else
1211 realignStoreGroup(Builder, VSpan, ScLen, AlignVal, AlignAddr);
1212
1213 for (auto *Inst : Move.Main)
1214 Inst->eraseFromParent();
1215
1216 return true;
1217}
1218
1219auto AlignVectors::isSectorTy(Type *Ty) const -> bool {
1220 if (!HVC.isByteVecTy(Ty))
1221 return false;
1222 int Size = HVC.getSizeOf(Ty);
1223 if (HVC.HST.isTypeForHVX(Ty))
1224 return Size == static_cast<int>(HVC.HST.getVectorLength());
1225 return Size == 4 || Size == 8;
1226}
1227
1228auto AlignVectors::run() -> bool {
1229 LLVM_DEBUG(dbgs() << "Running HVC::AlignVectors\n");
1230 if (!createAddressGroups())
1231 return false;
1232
1233 LLVM_DEBUG({
1234 dbgs() << "Address groups(" << AddrGroups.size() << "):\n";
1235 for (auto &[In, AL] : AddrGroups) {
1236 for (const AddrInfo &AI : AL)
1237 dbgs() << "---\n" << AI << '\n';
1238 }
1239 });
1240
1241 bool Changed = false;
1242 MoveList LoadGroups, StoreGroups;
1243
1244 for (auto &G : AddrGroups) {
1245 llvm::append_range(LoadGroups, createLoadGroups(G.second));
1246 llvm::append_range(StoreGroups, createStoreGroups(G.second));
1247 }
1248
1249 LLVM_DEBUG({
1250 dbgs() << "\nLoad groups(" << LoadGroups.size() << "):\n";
1251 for (const MoveGroup &G : LoadGroups)
1252 dbgs() << G << "\n";
1253 dbgs() << "Store groups(" << StoreGroups.size() << "):\n";
1254 for (const MoveGroup &G : StoreGroups)
1255 dbgs() << G << "\n";
1256 });
1257
1258 for (auto &M : LoadGroups)
1259 Changed |= move(M);
1260 for (auto &M : StoreGroups)
1261 Changed |= move(M);
1262
1263 LLVM_DEBUG(dbgs() << "After move:\n" << HVC.F);
1264
1265 for (auto &M : LoadGroups)
1266 Changed |= realignGroup(M);
1267 for (auto &M : StoreGroups)
1268 Changed |= realignGroup(M);
1269
1270 return Changed;
1271}
1272
1273// --- End AlignVectors
1274
1275// --- Begin HvxIdioms
1276
1277auto HvxIdioms::getNumSignificantBits(Value *V, Instruction *In) const
1278 -> std::pair<unsigned, Signedness> {
1279 unsigned Bits = HVC.getNumSignificantBits(V, In);
1280 // The significant bits are calculated including the sign bit. This may
1281 // add an extra bit for zero-extended values, e.g. (zext i32 to i64) may
1282 // result in 33 significant bits. To avoid extra words, skip the extra
1283 // sign bit, but keep information that the value is to be treated as
1284 // unsigned.
1285 KnownBits Known = HVC.getKnownBits(V, In);
1286 Signedness Sign = Signed;
1287 unsigned NumToTest = 0; // Number of bits used in test for unsignedness.
1288 if (isPowerOf2_32(Bits))
1289 NumToTest = Bits;
1290 else if (Bits > 1 && isPowerOf2_32(Bits - 1))
1291 NumToTest = Bits - 1;
1292
1293 if (NumToTest != 0 && Known.Zero.ashr(NumToTest).isAllOnes()) {
1294 Sign = Unsigned;
1295 Bits = NumToTest;
1296 }
1297
1298 // If the top bit of the nearest power-of-2 is zero, this value is
1299 // positive. It could be treated as either signed or unsigned.
1300 if (unsigned Pow2 = PowerOf2Ceil(Bits); Pow2 != Bits) {
1301 if (Known.Zero.ashr(Pow2 - 1).isAllOnes())
1302 Sign = Positive;
1303 }
1304 return {Bits, Sign};
1305}
1306
1307auto HvxIdioms::canonSgn(SValue X, SValue Y) const
1308 -> std::pair<SValue, SValue> {
1309 // Canonicalize the signedness of X and Y, so that the result is one of:
1310 // S, S
1311 // U/P, S
1312 // U/P, U/P
1313 if (X.Sgn == Signed && Y.Sgn != Signed)
1314 std::swap(X, Y);
1315 return {X, Y};
1316}
1317
1318// Match
1319// (X * Y) [>> N], or
1320// ((X * Y) + (1 << M)) >> N
1321auto HvxIdioms::matchFxpMul(Instruction &In) const -> std::optional<FxpOp> {
1322 using namespace PatternMatch;
1323 auto *Ty = In.getType();
1324
1325 if (!Ty->isVectorTy() || !Ty->getScalarType()->isIntegerTy())
1326 return std::nullopt;
1327
1328 unsigned Width = cast<IntegerType>(Ty->getScalarType())->getBitWidth();
1329
1330 FxpOp Op;
1331 Value *Exp = &In;
1332
1333 // Fixed-point multiplication is always shifted right (except when the
1334 // fraction is 0 bits).
1335 auto m_Shr = [](auto &&V, auto &&S) {
1336 return m_CombineOr(m_LShr(V, S), m_AShr(V, S));
1337 };
1338
1339 const APInt *Qn = nullptr;
1340 if (Value * T; match(Exp, m_Shr(m_Value(T), m_APInt(Qn)))) {
1341 Op.Frac = Qn->getZExtValue();
1342 Exp = T;
1343 } else {
1344 Op.Frac = 0;
1345 }
1346
1347 if (Op.Frac > Width)
1348 return std::nullopt;
1349
1350 // Check if there is rounding added.
1351 const APInt *C = nullptr;
1352 if (Value * T; Op.Frac > 0 && match(Exp, m_Add(m_Value(T), m_APInt(C)))) {
1353 uint64_t CV = C->getZExtValue();
1354 if (CV != 0 && !isPowerOf2_64(CV))
1355 return std::nullopt;
1356 if (CV != 0)
1357 Op.RoundAt = Log2_64(CV);
1358 Exp = T;
1359 }
1360
1361 // Check if the rest is a multiplication.
1362 if (match(Exp, m_Mul(m_Value(Op.X.Val), m_Value(Op.Y.Val)))) {
1363 Op.Opcode = Instruction::Mul;
1364 // FIXME: The information below is recomputed.
1365 Op.X.Sgn = getNumSignificantBits(Op.X.Val, &In).second;
1366 Op.Y.Sgn = getNumSignificantBits(Op.Y.Val, &In).second;
1367 Op.ResTy = cast<VectorType>(Ty);
1368 return Op;
1369 }
1370
1371 return std::nullopt;
1372}
1373
1374auto HvxIdioms::processFxpMul(Instruction &In, const FxpOp &Op) const
1375 -> Value * {
1376 assert(Op.X.Val->getType() == Op.Y.Val->getType());
1377
1378 auto *VecTy = dyn_cast<VectorType>(Op.X.Val->getType());
1379 if (VecTy == nullptr)
1380 return nullptr;
1381 auto *ElemTy = cast<IntegerType>(VecTy->getElementType());
1382 unsigned ElemWidth = ElemTy->getBitWidth();
1383
1384 // TODO: This can be relaxed after legalization is done pre-isel.
1385 if ((HVC.length(VecTy) * ElemWidth) % (8 * HVC.HST.getVectorLength()) != 0)
1386 return nullptr;
1387
1388 // There are no special intrinsics that should be used for multiplying
1389 // signed 8-bit values, so just skip them. Normal codegen should handle
1390 // this just fine.
1391 if (ElemWidth <= 8)
1392 return nullptr;
1393 // Similarly, if this is just a multiplication that can be handled without
1394 // intervention, then leave it alone.
1395 if (ElemWidth <= 32 && Op.Frac == 0)
1396 return nullptr;
1397
1398 auto [BitsX, SignX] = getNumSignificantBits(Op.X.Val, &In);
1399 auto [BitsY, SignY] = getNumSignificantBits(Op.Y.Val, &In);
1400
1401 // TODO: Add multiplication of vectors by scalar registers (up to 4 bytes).
1402
1403 Value *X = Op.X.Val, *Y = Op.Y.Val;
1404 IRBuilder Builder(In.getParent(), In.getIterator(),
1405 InstSimplifyFolder(HVC.DL));
1406
1407 auto roundUpWidth = [](unsigned Width) -> unsigned {
1408 if (Width <= 32 && !isPowerOf2_32(Width)) {
1409 // If the element width is not a power of 2, round it up
1410 // to the next one. Do this for widths not exceeding 32.
1411 return PowerOf2Ceil(Width);
1412 }
1413 if (Width > 32 && Width % 32 != 0) {
1414 // For wider elements, round it up to the multiple of 32.
1415 return alignTo(Width, 32u);
1416 }
1417 return Width;
1418 };
1419
1420 BitsX = roundUpWidth(BitsX);
1421 BitsY = roundUpWidth(BitsY);
1422
1423 // For elementwise multiplication vectors must have the same lengths, so
1424 // resize the elements of both inputs to the same width, the max of the
1425 // calculated significant bits.
1426 unsigned Width = std::max(BitsX, BitsY);
1427
1428 auto *ResizeTy = VectorType::get(HVC.getIntTy(Width), VecTy);
1429 if (Width < ElemWidth) {
1430 X = Builder.CreateTrunc(X, ResizeTy, "trn");
1431 Y = Builder.CreateTrunc(Y, ResizeTy, "trn");
1432 } else if (Width > ElemWidth) {
1433 X = SignX == Signed ? Builder.CreateSExt(X, ResizeTy, "sxt")
1434 : Builder.CreateZExt(X, ResizeTy, "zxt");
1435 Y = SignY == Signed ? Builder.CreateSExt(Y, ResizeTy, "sxt")
1436 : Builder.CreateZExt(Y, ResizeTy, "zxt");
1437 };
1438
1439 assert(X->getType() == Y->getType() && X->getType() == ResizeTy);
1440
1441 unsigned VecLen = HVC.length(ResizeTy);
1442 unsigned ChopLen = (8 * HVC.HST.getVectorLength()) / std::min(Width, 32u);
1443
1445 FxpOp ChopOp = Op;
1446 ChopOp.ResTy = VectorType::get(Op.ResTy->getElementType(), ChopLen, false);
1447
1448 for (unsigned V = 0; V != VecLen / ChopLen; ++V) {
1449 ChopOp.X.Val = HVC.subvector(Builder, X, V * ChopLen, ChopLen);
1450 ChopOp.Y.Val = HVC.subvector(Builder, Y, V * ChopLen, ChopLen);
1451 Results.push_back(processFxpMulChopped(Builder, In, ChopOp));
1452 if (Results.back() == nullptr)
1453 break;
1454 }
1455
1456 if (Results.empty() || Results.back() == nullptr)
1457 return nullptr;
1458
1459 Value *Cat = HVC.concat(Builder, Results);
1460 Value *Ext = SignX == Signed || SignY == Signed
1461 ? Builder.CreateSExt(Cat, VecTy, "sxt")
1462 : Builder.CreateZExt(Cat, VecTy, "zxt");
1463 return Ext;
1464}
1465
1466auto HvxIdioms::processFxpMulChopped(IRBuilderBase &Builder, Instruction &In,
1467 const FxpOp &Op) const -> Value * {
1468 assert(Op.X.Val->getType() == Op.Y.Val->getType());
1469 auto *InpTy = cast<VectorType>(Op.X.Val->getType());
1470 unsigned Width = InpTy->getScalarSizeInBits();
1471 bool Rounding = Op.RoundAt.has_value();
1472
1473 if (!Op.RoundAt || *Op.RoundAt == Op.Frac - 1) {
1474 // The fixed-point intrinsics do signed multiplication.
1475 if (Width == Op.Frac + 1 && Op.X.Sgn != Unsigned && Op.Y.Sgn != Unsigned) {
1476 Value *QMul = nullptr;
1477 if (Width == 16) {
1478 QMul = createMulQ15(Builder, Op.X, Op.Y, Rounding);
1479 } else if (Width == 32) {
1480 QMul = createMulQ31(Builder, Op.X, Op.Y, Rounding);
1481 }
1482 if (QMul != nullptr)
1483 return QMul;
1484 }
1485 }
1486
1487 assert(Width >= 32 || isPowerOf2_32(Width)); // Width <= 32 => Width is 2^n
1488 assert(Width < 32 || Width % 32 == 0); // Width > 32 => Width is 32*k
1489
1490 // If Width < 32, then it should really be 16.
1491 if (Width < 32) {
1492 if (Width < 16)
1493 return nullptr;
1494 // Getting here with Op.Frac == 0 isn't wrong, but suboptimal: here we
1495 // generate a full precision products, which is unnecessary if there is
1496 // no shift.
1497 assert(Width == 16);
1498 assert(Op.Frac != 0 && "Unshifted mul should have been skipped");
1499 if (Op.Frac == 16) {
1500 // Multiply high
1501 if (Value *MulH = createMulH16(Builder, Op.X, Op.Y))
1502 return MulH;
1503 }
1504 // Do full-precision multiply and shift.
1505 Value *Prod32 = createMul16(Builder, Op.X, Op.Y);
1506 if (Rounding) {
1507 Value *RoundVal = HVC.getConstSplat(Prod32->getType(), 1 << *Op.RoundAt);
1508 Prod32 = Builder.CreateAdd(Prod32, RoundVal, "add");
1509 }
1510
1511 Value *ShiftAmt = HVC.getConstSplat(Prod32->getType(), Op.Frac);
1512 Value *Shifted = Op.X.Sgn == Signed || Op.Y.Sgn == Signed
1513 ? Builder.CreateAShr(Prod32, ShiftAmt, "asr")
1514 : Builder.CreateLShr(Prod32, ShiftAmt, "lsr");
1515 return Builder.CreateTrunc(Shifted, InpTy, "trn");
1516 }
1517
1518 // Width >= 32
1519
1520 // Break up the arguments Op.X and Op.Y into vectors of smaller widths
1521 // in preparation of doing the multiplication by 32-bit parts.
1522 auto WordX = HVC.splitVectorElements(Builder, Op.X.Val, /*ToWidth=*/32);
1523 auto WordY = HVC.splitVectorElements(Builder, Op.Y.Val, /*ToWidth=*/32);
1524 auto WordP = createMulLong(Builder, WordX, Op.X.Sgn, WordY, Op.Y.Sgn);
1525
1526 auto *HvxWordTy = cast<VectorType>(WordP.front()->getType());
1527
1528 // Add the optional rounding to the proper word.
1529 if (Op.RoundAt.has_value()) {
1530 Value *Zero = HVC.getNullValue(WordX[0]->getType());
1531 SmallVector<Value *> RoundV(WordP.size(), Zero);
1532 RoundV[*Op.RoundAt / 32] =
1533 HVC.getConstSplat(HvxWordTy, 1 << (*Op.RoundAt % 32));
1534 WordP = createAddLong(Builder, WordP, RoundV);
1535 }
1536
1537 // createRightShiftLong?
1538
1539 // Shift all products right by Op.Frac.
1540 unsigned SkipWords = Op.Frac / 32;
1541 Constant *ShiftAmt = HVC.getConstSplat(HvxWordTy, Op.Frac % 32);
1542
1543 for (int Dst = 0, End = WordP.size() - SkipWords; Dst != End; ++Dst) {
1544 int Src = Dst + SkipWords;
1545 Value *Lo = WordP[Src];
1546 if (Src + 1 < End) {
1547 Value *Hi = WordP[Src + 1];
1548 WordP[Dst] = Builder.CreateIntrinsic(HvxWordTy, Intrinsic::fshr,
1549 {Hi, Lo, ShiftAmt},
1550 /*FMFSource*/ nullptr, "int");
1551 } else {
1552 // The shift of the most significant word.
1553 WordP[Dst] = Builder.CreateAShr(Lo, ShiftAmt, "asr");
1554 }
1555 }
1556 if (SkipWords != 0)
1557 WordP.resize(WordP.size() - SkipWords);
1558
1559 return HVC.joinVectorElements(Builder, WordP, Op.ResTy);
1560}
1561
1562auto HvxIdioms::createMulQ15(IRBuilderBase &Builder, SValue X, SValue Y,
1563 bool Rounding) const -> Value * {
1564 assert(X.Val->getType() == Y.Val->getType());
1565 assert(X.Val->getType()->getScalarType() == HVC.getIntTy(16));
1566 assert(HVC.HST.isHVXVectorType(EVT::getEVT(X.Val->getType(), false)));
1567
1568 // There is no non-rounding intrinsic for i16.
1569 if (!Rounding || X.Sgn == Unsigned || Y.Sgn == Unsigned)
1570 return nullptr;
1571
1572 auto V6_vmpyhvsrs = HVC.HST.getIntrinsicId(Hexagon::V6_vmpyhvsrs);
1573 return HVC.createHvxIntrinsic(Builder, V6_vmpyhvsrs, X.Val->getType(),
1574 {X.Val, Y.Val});
1575}
1576
1577auto HvxIdioms::createMulQ31(IRBuilderBase &Builder, SValue X, SValue Y,
1578 bool Rounding) const -> Value * {
1579 Type *InpTy = X.Val->getType();
1580 assert(InpTy == Y.Val->getType());
1581 assert(InpTy->getScalarType() == HVC.getIntTy(32));
1582 assert(HVC.HST.isHVXVectorType(EVT::getEVT(InpTy, false)));
1583
1584 if (X.Sgn == Unsigned || Y.Sgn == Unsigned)
1585 return nullptr;
1586
1587 auto V6_vmpyewuh = HVC.HST.getIntrinsicId(Hexagon::V6_vmpyewuh);
1588 auto V6_vmpyo_acc = Rounding
1589 ? HVC.HST.getIntrinsicId(Hexagon::V6_vmpyowh_rnd_sacc)
1590 : HVC.HST.getIntrinsicId(Hexagon::V6_vmpyowh_sacc);
1591 Value *V1 =
1592 HVC.createHvxIntrinsic(Builder, V6_vmpyewuh, InpTy, {X.Val, Y.Val});
1593 return HVC.createHvxIntrinsic(Builder, V6_vmpyo_acc, InpTy,
1594 {V1, X.Val, Y.Val});
1595}
1596
1597auto HvxIdioms::createAddCarry(IRBuilderBase &Builder, Value *X, Value *Y,
1598 Value *CarryIn) const
1599 -> std::pair<Value *, Value *> {
1600 assert(X->getType() == Y->getType());
1601 auto VecTy = cast<VectorType>(X->getType());
1602 if (VecTy == HvxI32Ty && HVC.HST.useHVXV62Ops()) {
1604 Intrinsic::ID AddCarry;
1605 if (CarryIn == nullptr && HVC.HST.useHVXV66Ops()) {
1606 AddCarry = HVC.HST.getIntrinsicId(Hexagon::V6_vaddcarryo);
1607 } else {
1608 AddCarry = HVC.HST.getIntrinsicId(Hexagon::V6_vaddcarry);
1609 if (CarryIn == nullptr)
1610 CarryIn = HVC.getNullValue(HVC.getBoolTy(HVC.length(VecTy)));
1611 Args.push_back(CarryIn);
1612 }
1613 Value *Ret = HVC.createHvxIntrinsic(Builder, AddCarry,
1614 /*RetTy=*/nullptr, Args);
1615 Value *Result = Builder.CreateExtractValue(Ret, {0}, "ext");
1616 Value *CarryOut = Builder.CreateExtractValue(Ret, {1}, "ext");
1617 return {Result, CarryOut};
1618 }
1619
1620 // In other cases, do a regular add, and unsigned compare-less-than.
1621 // The carry-out can originate in two places: adding the carry-in or adding
1622 // the two input values.
1623 Value *Result1 = X; // Result1 = X + CarryIn
1624 if (CarryIn != nullptr) {
1625 unsigned Width = VecTy->getScalarSizeInBits();
1626 uint32_t Mask = 1;
1627 if (Width < 32) {
1628 for (unsigned i = 0, e = 32 / Width; i != e; ++i)
1629 Mask = (Mask << Width) | 1;
1630 }
1631 auto V6_vandqrt = HVC.HST.getIntrinsicId(Hexagon::V6_vandqrt);
1632 Value *ValueIn =
1633 HVC.createHvxIntrinsic(Builder, V6_vandqrt, /*RetTy=*/nullptr,
1634 {CarryIn, HVC.getConstInt(Mask)});
1635 Result1 = Builder.CreateAdd(X, ValueIn, "add");
1636 }
1637
1638 Value *CarryOut1 = Builder.CreateCmp(CmpInst::ICMP_ULT, Result1, X, "cmp");
1639 Value *Result2 = Builder.CreateAdd(Result1, Y, "add");
1640 Value *CarryOut2 = Builder.CreateCmp(CmpInst::ICMP_ULT, Result2, Y, "cmp");
1641 return {Result2, Builder.CreateOr(CarryOut1, CarryOut2, "orb")};
1642}
1643
1644auto HvxIdioms::createMul16(IRBuilderBase &Builder, SValue X, SValue Y) const
1645 -> Value * {
1646 Intrinsic::ID V6_vmpyh = 0;
1647 std::tie(X, Y) = canonSgn(X, Y);
1648
1649 if (X.Sgn == Signed) {
1650 V6_vmpyh = HVC.HST.getIntrinsicId(Hexagon::V6_vmpyhv);
1651 } else if (Y.Sgn == Signed) {
1652 // In vmpyhus the second operand is unsigned
1653 V6_vmpyh = HVC.HST.getIntrinsicId(Hexagon::V6_vmpyhus);
1654 } else {
1655 V6_vmpyh = HVC.HST.getIntrinsicId(Hexagon::V6_vmpyuhv);
1656 }
1657
1658 // i16*i16 -> i32 / interleaved
1659 Value *P =
1660 HVC.createHvxIntrinsic(Builder, V6_vmpyh, HvxP32Ty, {Y.Val, X.Val});
1661 // Deinterleave
1662 return HVC.vshuff(Builder, HVC.sublo(Builder, P), HVC.subhi(Builder, P));
1663}
1664
1665auto HvxIdioms::createMulH16(IRBuilderBase &Builder, SValue X, SValue Y) const
1666 -> Value * {
1667 Type *HvxI16Ty = HVC.getHvxTy(HVC.getIntTy(16), /*Pair=*/false);
1668
1669 if (HVC.HST.useHVXV69Ops()) {
1670 if (X.Sgn != Signed && Y.Sgn != Signed) {
1671 auto V6_vmpyuhvs = HVC.HST.getIntrinsicId(Hexagon::V6_vmpyuhvs);
1672 return HVC.createHvxIntrinsic(Builder, V6_vmpyuhvs, HvxI16Ty,
1673 {X.Val, Y.Val});
1674 }
1675 }
1676
1677 Type *HvxP16Ty = HVC.getHvxTy(HVC.getIntTy(16), /*Pair=*/true);
1678 Value *Pair16 =
1679 Builder.CreateBitCast(createMul16(Builder, X, Y), HvxP16Ty, "cst");
1680 unsigned Len = HVC.length(HvxP16Ty) / 2;
1681
1682 SmallVector<int, 128> PickOdd(Len);
1683 for (int i = 0; i != static_cast<int>(Len); ++i)
1684 PickOdd[i] = 2 * i + 1;
1685
1686 return Builder.CreateShuffleVector(
1687 HVC.sublo(Builder, Pair16), HVC.subhi(Builder, Pair16), PickOdd, "shf");
1688}
1689
1690auto HvxIdioms::createMul32(IRBuilderBase &Builder, SValue X, SValue Y) const
1691 -> std::pair<Value *, Value *> {
1692 assert(X.Val->getType() == Y.Val->getType());
1693 assert(X.Val->getType() == HvxI32Ty);
1694
1695 Intrinsic::ID V6_vmpy_parts;
1696 std::tie(X, Y) = canonSgn(X, Y);
1697
1698 if (X.Sgn == Signed) {
1699 V6_vmpy_parts = Intrinsic::hexagon_V6_vmpyss_parts;
1700 } else if (Y.Sgn == Signed) {
1701 V6_vmpy_parts = Intrinsic::hexagon_V6_vmpyus_parts;
1702 } else {
1703 V6_vmpy_parts = Intrinsic::hexagon_V6_vmpyuu_parts;
1704 }
1705
1706 Value *Parts = HVC.createHvxIntrinsic(Builder, V6_vmpy_parts, nullptr,
1707 {X.Val, Y.Val}, {HvxI32Ty});
1708 Value *Hi = Builder.CreateExtractValue(Parts, {0}, "ext");
1709 Value *Lo = Builder.CreateExtractValue(Parts, {1}, "ext");
1710 return {Lo, Hi};
1711}
1712
1713auto HvxIdioms::createAddLong(IRBuilderBase &Builder, ArrayRef<Value *> WordX,
1714 ArrayRef<Value *> WordY) const
1716 assert(WordX.size() == WordY.size());
1717 unsigned Idx = 0, Length = WordX.size();
1719
1720 while (Idx != Length) {
1721 if (HVC.isZero(WordX[Idx]))
1722 Sum[Idx] = WordY[Idx];
1723 else if (HVC.isZero(WordY[Idx]))
1724 Sum[Idx] = WordX[Idx];
1725 else
1726 break;
1727 ++Idx;
1728 }
1729
1730 Value *Carry = nullptr;
1731 for (; Idx != Length; ++Idx) {
1732 std::tie(Sum[Idx], Carry) =
1733 createAddCarry(Builder, WordX[Idx], WordY[Idx], Carry);
1734 }
1735
1736 // This drops the final carry beyond the highest word.
1737 return Sum;
1738}
1739
1740auto HvxIdioms::createMulLong(IRBuilderBase &Builder, ArrayRef<Value *> WordX,
1741 Signedness SgnX, ArrayRef<Value *> WordY,
1742 Signedness SgnY) const -> SmallVector<Value *> {
1743 SmallVector<SmallVector<Value *>> Products(WordX.size() + WordY.size());
1744
1745 // WordX[i] * WordY[j] produces words i+j and i+j+1 of the results,
1746 // that is halves 2(i+j), 2(i+j)+1, 2(i+j)+2, 2(i+j)+3.
1747 for (int i = 0, e = WordX.size(); i != e; ++i) {
1748 for (int j = 0, f = WordY.size(); j != f; ++j) {
1749 // Check the 4 halves that this multiplication can generate.
1750 Signedness SX = (i + 1 == e) ? SgnX : Unsigned;
1751 Signedness SY = (j + 1 == f) ? SgnY : Unsigned;
1752 auto [Lo, Hi] = createMul32(Builder, {WordX[i], SX}, {WordY[j], SY});
1753 Products[i + j + 0].push_back(Lo);
1754 Products[i + j + 1].push_back(Hi);
1755 }
1756 }
1757
1758 Value *Zero = HVC.getNullValue(WordX[0]->getType());
1759
1760 auto pop_back_or_zero = [Zero](auto &Vector) -> Value * {
1761 if (Vector.empty())
1762 return Zero;
1763 auto Last = Vector.back();
1764 Vector.pop_back();
1765 return Last;
1766 };
1767
1768 for (int i = 0, e = Products.size(); i != e; ++i) {
1769 while (Products[i].size() > 1) {
1770 Value *Carry = nullptr; // no carry-in
1771 for (int j = i; j != e; ++j) {
1772 auto &ProdJ = Products[j];
1773 auto [Sum, CarryOut] = createAddCarry(Builder, pop_back_or_zero(ProdJ),
1774 pop_back_or_zero(ProdJ), Carry);
1775 ProdJ.insert(ProdJ.begin(), Sum);
1776 Carry = CarryOut;
1777 }
1778 }
1779 }
1780
1782 for (auto &P : Products) {
1783 assert(P.size() == 1 && "Should have been added together");
1784 WordP.push_back(P.front());
1785 }
1786
1787 return WordP;
1788}
1789
1790auto HvxIdioms::run() -> bool {
1791 bool Changed = false;
1792
1793 for (BasicBlock &B : HVC.F) {
1794 for (auto It = B.rbegin(); It != B.rend(); ++It) {
1795 if (auto Fxm = matchFxpMul(*It)) {
1796 Value *New = processFxpMul(*It, *Fxm);
1797 // Always report "changed" for now.
1798 Changed = true;
1799 if (!New)
1800 continue;
1801 bool StartOver = !isa<Instruction>(New);
1802 It->replaceAllUsesWith(New);
1804 It = StartOver ? B.rbegin()
1805 : cast<Instruction>(New)->getReverseIterator();
1806 Changed = true;
1807 }
1808 }
1809 }
1810
1811 return Changed;
1812}
1813
1814// --- End HvxIdioms
1815
1816auto HexagonVectorCombine::run() -> bool {
1817 if (!HST.useHVXOps())
1818 return false;
1819
1820 bool Changed = false;
1821 Changed |= AlignVectors(*this).run();
1822 Changed |= HvxIdioms(*this).run();
1823
1824 return Changed;
1825}
1826
1827auto HexagonVectorCombine::getIntTy(unsigned Width) const -> IntegerType * {
1828 return IntegerType::get(F.getContext(), Width);
1829}
1830
1831auto HexagonVectorCombine::getByteTy(int ElemCount) const -> Type * {
1832 assert(ElemCount >= 0);
1833 IntegerType *ByteTy = Type::getInt8Ty(F.getContext());
1834 if (ElemCount == 0)
1835 return ByteTy;
1836 return VectorType::get(ByteTy, ElemCount, /*Scalable=*/false);
1837}
1838
1839auto HexagonVectorCombine::getBoolTy(int ElemCount) const -> Type * {
1840 assert(ElemCount >= 0);
1841 IntegerType *BoolTy = Type::getInt1Ty(F.getContext());
1842 if (ElemCount == 0)
1843 return BoolTy;
1844 return VectorType::get(BoolTy, ElemCount, /*Scalable=*/false);
1845}
1846
1847auto HexagonVectorCombine::getConstInt(int Val, unsigned Width) const
1848 -> ConstantInt * {
1849 return ConstantInt::getSigned(getIntTy(Width), Val);
1850}
1851
1852auto HexagonVectorCombine::isZero(const Value *Val) const -> bool {
1853 if (auto *C = dyn_cast<Constant>(Val))
1854 return C->isZeroValue();
1855 return false;
1856}
1857
1858auto HexagonVectorCombine::getIntValue(const Value *Val) const
1859 -> std::optional<APInt> {
1860 if (auto *CI = dyn_cast<ConstantInt>(Val))
1861 return CI->getValue();
1862 return std::nullopt;
1863}
1864
1865auto HexagonVectorCombine::isUndef(const Value *Val) const -> bool {
1866 return isa<UndefValue>(Val);
1867}
1868
1869auto HexagonVectorCombine::getHvxTy(Type *ElemTy, bool Pair) const
1870 -> VectorType * {
1871 EVT ETy = EVT::getEVT(ElemTy, false);
1872 assert(ETy.isSimple() && "Invalid HVX element type");
1873 // Do not allow boolean types here: they don't have a fixed length.
1874 assert(HST.isHVXElementType(ETy.getSimpleVT(), /*IncludeBool=*/false) &&
1875 "Invalid HVX element type");
1876 unsigned HwLen = HST.getVectorLength();
1877 unsigned NumElems = (8 * HwLen) / ETy.getSizeInBits();
1878 return VectorType::get(ElemTy, Pair ? 2 * NumElems : NumElems,
1879 /*Scalable=*/false);
1880}
1881
1882auto HexagonVectorCombine::getSizeOf(const Value *Val, SizeKind Kind) const
1883 -> int {
1884 return getSizeOf(Val->getType(), Kind);
1885}
1886
1887auto HexagonVectorCombine::getSizeOf(const Type *Ty, SizeKind Kind) const
1888 -> int {
1889 auto *NcTy = const_cast<Type *>(Ty);
1890 switch (Kind) {
1891 case Store:
1892 return DL.getTypeStoreSize(NcTy).getFixedValue();
1893 case Alloc:
1894 return DL.getTypeAllocSize(NcTy).getFixedValue();
1895 }
1896 llvm_unreachable("Unhandled SizeKind enum");
1897}
1898
1899auto HexagonVectorCombine::getTypeAlignment(Type *Ty) const -> int {
1900 // The actual type may be shorter than the HVX vector, so determine
1901 // the alignment based on subtarget info.
1902 if (HST.isTypeForHVX(Ty))
1903 return HST.getVectorLength();
1904 return DL.getABITypeAlign(Ty).value();
1905}
1906
1907auto HexagonVectorCombine::length(Value *Val) const -> size_t {
1908 return length(Val->getType());
1909}
1910
1911auto HexagonVectorCombine::length(Type *Ty) const -> size_t {
1912 auto *VecTy = dyn_cast<VectorType>(Ty);
1913 assert(VecTy && "Must be a vector type");
1914 return VecTy->getElementCount().getFixedValue();
1915}
1916
1917auto HexagonVectorCombine::getNullValue(Type *Ty) const -> Constant * {
1919 auto Zero = ConstantInt::get(Ty->getScalarType(), 0);
1920 if (auto *VecTy = dyn_cast<VectorType>(Ty))
1921 return ConstantVector::getSplat(VecTy->getElementCount(), Zero);
1922 return Zero;
1923}
1924
1925auto HexagonVectorCombine::getFullValue(Type *Ty) const -> Constant * {
1927 auto Minus1 = ConstantInt::get(Ty->getScalarType(), -1);
1928 if (auto *VecTy = dyn_cast<VectorType>(Ty))
1929 return ConstantVector::getSplat(VecTy->getElementCount(), Minus1);
1930 return Minus1;
1931}
1932
1933auto HexagonVectorCombine::getConstSplat(Type *Ty, int Val) const
1934 -> Constant * {
1935 assert(Ty->isVectorTy());
1936 auto VecTy = cast<VectorType>(Ty);
1937 Type *ElemTy = VecTy->getElementType();
1938 // Add support for floats if needed.
1939 auto *Splat = ConstantVector::getSplat(VecTy->getElementCount(),
1940 ConstantInt::get(ElemTy, Val));
1941 return Splat;
1942}
1943
1944auto HexagonVectorCombine::simplify(Value *V) const -> Value * {
1945 if (auto *In = dyn_cast<Instruction>(V)) {
1946 SimplifyQuery Q(DL, &TLI, &DT, &AC, In);
1947 return simplifyInstruction(In, Q);
1948 }
1949 return nullptr;
1950}
1951
1952// Insert bytes [Start..Start+Length) of Src into Dst at byte Where.
1953auto HexagonVectorCombine::insertb(IRBuilderBase &Builder, Value *Dst,
1954 Value *Src, int Start, int Length,
1955 int Where) const -> Value * {
1956 assert(isByteVecTy(Dst->getType()) && isByteVecTy(Src->getType()));
1957 int SrcLen = getSizeOf(Src);
1958 int DstLen = getSizeOf(Dst);
1959 assert(0 <= Start && Start + Length <= SrcLen);
1960 assert(0 <= Where && Where + Length <= DstLen);
1961
1962 int P2Len = PowerOf2Ceil(SrcLen | DstLen);
1963 auto *Undef = UndefValue::get(getByteTy());
1964 Value *P2Src = vresize(Builder, Src, P2Len, Undef);
1965 Value *P2Dst = vresize(Builder, Dst, P2Len, Undef);
1966
1967 SmallVector<int, 256> SMask(P2Len);
1968 for (int i = 0; i != P2Len; ++i) {
1969 // If i is in [Where, Where+Length), pick Src[Start+(i-Where)].
1970 // Otherwise, pick Dst[i];
1971 SMask[i] =
1972 (Where <= i && i < Where + Length) ? P2Len + Start + (i - Where) : i;
1973 }
1974
1975 Value *P2Insert = Builder.CreateShuffleVector(P2Dst, P2Src, SMask, "shf");
1976 return vresize(Builder, P2Insert, DstLen, Undef);
1977}
1978
1979auto HexagonVectorCombine::vlalignb(IRBuilderBase &Builder, Value *Lo,
1980 Value *Hi, Value *Amt) const -> Value * {
1981 assert(Lo->getType() == Hi->getType() && "Argument type mismatch");
1982 if (isZero(Amt))
1983 return Hi;
1984 int VecLen = getSizeOf(Hi);
1985 if (auto IntAmt = getIntValue(Amt))
1986 return getElementRange(Builder, Lo, Hi, VecLen - IntAmt->getSExtValue(),
1987 VecLen);
1988
1989 if (HST.isTypeForHVX(Hi->getType())) {
1990 assert(static_cast<unsigned>(VecLen) == HST.getVectorLength() &&
1991 "Expecting an exact HVX type");
1992 return createHvxIntrinsic(Builder, HST.getIntrinsicId(Hexagon::V6_vlalignb),
1993 Hi->getType(), {Hi, Lo, Amt});
1994 }
1995
1996 if (VecLen == 4) {
1997 Value *Pair = concat(Builder, {Lo, Hi});
1998 Value *Shift =
1999 Builder.CreateLShr(Builder.CreateShl(Pair, Amt, "shl"), 32, "lsr");
2000 Value *Trunc =
2001 Builder.CreateTrunc(Shift, Type::getInt32Ty(F.getContext()), "trn");
2002 return Builder.CreateBitCast(Trunc, Hi->getType(), "cst");
2003 }
2004 if (VecLen == 8) {
2005 Value *Sub = Builder.CreateSub(getConstInt(VecLen), Amt, "sub");
2006 return vralignb(Builder, Lo, Hi, Sub);
2007 }
2008 llvm_unreachable("Unexpected vector length");
2009}
2010
2011auto HexagonVectorCombine::vralignb(IRBuilderBase &Builder, Value *Lo,
2012 Value *Hi, Value *Amt) const -> Value * {
2013 assert(Lo->getType() == Hi->getType() && "Argument type mismatch");
2014 if (isZero(Amt))
2015 return Lo;
2016 int VecLen = getSizeOf(Lo);
2017 if (auto IntAmt = getIntValue(Amt))
2018 return getElementRange(Builder, Lo, Hi, IntAmt->getSExtValue(), VecLen);
2019
2020 if (HST.isTypeForHVX(Lo->getType())) {
2021 assert(static_cast<unsigned>(VecLen) == HST.getVectorLength() &&
2022 "Expecting an exact HVX type");
2023 return createHvxIntrinsic(Builder, HST.getIntrinsicId(Hexagon::V6_valignb),
2024 Lo->getType(), {Hi, Lo, Amt});
2025 }
2026
2027 if (VecLen == 4) {
2028 Value *Pair = concat(Builder, {Lo, Hi});
2029 Value *Shift = Builder.CreateLShr(Pair, Amt, "lsr");
2030 Value *Trunc =
2031 Builder.CreateTrunc(Shift, Type::getInt32Ty(F.getContext()), "trn");
2032 return Builder.CreateBitCast(Trunc, Lo->getType(), "cst");
2033 }
2034 if (VecLen == 8) {
2035 Type *Int64Ty = Type::getInt64Ty(F.getContext());
2036 Value *Lo64 = Builder.CreateBitCast(Lo, Int64Ty, "cst");
2037 Value *Hi64 = Builder.CreateBitCast(Hi, Int64Ty, "cst");
2038 Function *FI = Intrinsic::getDeclaration(F.getParent(),
2039 Intrinsic::hexagon_S2_valignrb);
2040 Value *Call = Builder.CreateCall(FI, {Hi64, Lo64, Amt}, "cup");
2041 return Builder.CreateBitCast(Call, Lo->getType(), "cst");
2042 }
2043 llvm_unreachable("Unexpected vector length");
2044}
2045
2046// Concatenates a sequence of vectors of the same type.
2047auto HexagonVectorCombine::concat(IRBuilderBase &Builder,
2048 ArrayRef<Value *> Vecs) const -> Value * {
2049 assert(!Vecs.empty());
2051 std::vector<Value *> Work[2];
2052 int ThisW = 0, OtherW = 1;
2053
2054 Work[ThisW].assign(Vecs.begin(), Vecs.end());
2055 while (Work[ThisW].size() > 1) {
2056 auto *Ty = cast<VectorType>(Work[ThisW].front()->getType());
2057 SMask.resize(length(Ty) * 2);
2058 std::iota(SMask.begin(), SMask.end(), 0);
2059
2060 Work[OtherW].clear();
2061 if (Work[ThisW].size() % 2 != 0)
2062 Work[ThisW].push_back(UndefValue::get(Ty));
2063 for (int i = 0, e = Work[ThisW].size(); i < e; i += 2) {
2064 Value *Joined = Builder.CreateShuffleVector(
2065 Work[ThisW][i], Work[ThisW][i + 1], SMask, "shf");
2066 Work[OtherW].push_back(Joined);
2067 }
2068 std::swap(ThisW, OtherW);
2069 }
2070
2071 // Since there may have been some undefs appended to make shuffle operands
2072 // have the same type, perform the last shuffle to only pick the original
2073 // elements.
2074 SMask.resize(Vecs.size() * length(Vecs.front()->getType()));
2075 std::iota(SMask.begin(), SMask.end(), 0);
2076 Value *Total = Work[ThisW].front();
2077 return Builder.CreateShuffleVector(Total, SMask, "shf");
2078}
2079
2080auto HexagonVectorCombine::vresize(IRBuilderBase &Builder, Value *Val,
2081 int NewSize, Value *Pad) const -> Value * {
2082 assert(isa<VectorType>(Val->getType()));
2083 auto *ValTy = cast<VectorType>(Val->getType());
2084 assert(ValTy->getElementType() == Pad->getType());
2085
2086 int CurSize = length(ValTy);
2087 if (CurSize == NewSize)
2088 return Val;
2089 // Truncate?
2090 if (CurSize > NewSize)
2091 return getElementRange(Builder, Val, /*Ignored*/ Val, 0, NewSize);
2092 // Extend.
2093 SmallVector<int, 128> SMask(NewSize);
2094 std::iota(SMask.begin(), SMask.begin() + CurSize, 0);
2095 std::fill(SMask.begin() + CurSize, SMask.end(), CurSize);
2096 Value *PadVec = Builder.CreateVectorSplat(CurSize, Pad, "spt");
2097 return Builder.CreateShuffleVector(Val, PadVec, SMask, "shf");
2098}
2099
2100auto HexagonVectorCombine::rescale(IRBuilderBase &Builder, Value *Mask,
2101 Type *FromTy, Type *ToTy) const -> Value * {
2102 // Mask is a vector <N x i1>, where each element corresponds to an
2103 // element of FromTy. Remap it so that each element will correspond
2104 // to an element of ToTy.
2105 assert(isa<VectorType>(Mask->getType()));
2106
2107 Type *FromSTy = FromTy->getScalarType();
2108 Type *ToSTy = ToTy->getScalarType();
2109 if (FromSTy == ToSTy)
2110 return Mask;
2111
2112 int FromSize = getSizeOf(FromSTy);
2113 int ToSize = getSizeOf(ToSTy);
2114 assert(FromSize % ToSize == 0 || ToSize % FromSize == 0);
2115
2116 auto *MaskTy = cast<VectorType>(Mask->getType());
2117 int FromCount = length(MaskTy);
2118 int ToCount = (FromCount * FromSize) / ToSize;
2119 assert((FromCount * FromSize) % ToSize == 0);
2120
2121 auto *FromITy = getIntTy(FromSize * 8);
2122 auto *ToITy = getIntTy(ToSize * 8);
2123
2124 // Mask <N x i1> -> sext to <N x FromTy> -> bitcast to <M x ToTy> ->
2125 // -> trunc to <M x i1>.
2126 Value *Ext = Builder.CreateSExt(
2127 Mask, VectorType::get(FromITy, FromCount, /*Scalable=*/false), "sxt");
2128 Value *Cast = Builder.CreateBitCast(
2129 Ext, VectorType::get(ToITy, ToCount, /*Scalable=*/false), "cst");
2130 return Builder.CreateTrunc(
2131 Cast, VectorType::get(getBoolTy(), ToCount, /*Scalable=*/false), "trn");
2132}
2133
2134// Bitcast to bytes, and return least significant bits.
2135auto HexagonVectorCombine::vlsb(IRBuilderBase &Builder, Value *Val) const
2136 -> Value * {
2137 Type *ScalarTy = Val->getType()->getScalarType();
2138 if (ScalarTy == getBoolTy())
2139 return Val;
2140
2141 Value *Bytes = vbytes(Builder, Val);
2142 if (auto *VecTy = dyn_cast<VectorType>(Bytes->getType()))
2143 return Builder.CreateTrunc(Bytes, getBoolTy(getSizeOf(VecTy)), "trn");
2144 // If Bytes is a scalar (i.e. Val was a scalar byte), return i1, not
2145 // <1 x i1>.
2146 return Builder.CreateTrunc(Bytes, getBoolTy(), "trn");
2147}
2148
2149// Bitcast to bytes for non-bool. For bool, convert i1 -> i8.
2150auto HexagonVectorCombine::vbytes(IRBuilderBase &Builder, Value *Val) const
2151 -> Value * {
2152 Type *ScalarTy = Val->getType()->getScalarType();
2153 if (ScalarTy == getByteTy())
2154 return Val;
2155
2156 if (ScalarTy != getBoolTy())
2157 return Builder.CreateBitCast(Val, getByteTy(getSizeOf(Val)), "cst");
2158 // For bool, return a sext from i1 to i8.
2159 if (auto *VecTy = dyn_cast<VectorType>(Val->getType()))
2160 return Builder.CreateSExt(Val, VectorType::get(getByteTy(), VecTy), "sxt");
2161 return Builder.CreateSExt(Val, getByteTy(), "sxt");
2162}
2163
2164auto HexagonVectorCombine::subvector(IRBuilderBase &Builder, Value *Val,
2165 unsigned Start, unsigned Length) const
2166 -> Value * {
2167 assert(Start + Length <= length(Val));
2168 return getElementRange(Builder, Val, /*Ignored*/ Val, Start, Length);
2169}
2170
2171auto HexagonVectorCombine::sublo(IRBuilderBase &Builder, Value *Val) const
2172 -> Value * {
2173 size_t Len = length(Val);
2174 assert(Len % 2 == 0 && "Length should be even");
2175 return subvector(Builder, Val, 0, Len / 2);
2176}
2177
2178auto HexagonVectorCombine::subhi(IRBuilderBase &Builder, Value *Val) const
2179 -> Value * {
2180 size_t Len = length(Val);
2181 assert(Len % 2 == 0 && "Length should be even");
2182 return subvector(Builder, Val, Len / 2, Len / 2);
2183}
2184
2185auto HexagonVectorCombine::vdeal(IRBuilderBase &Builder, Value *Val0,
2186 Value *Val1) const -> Value * {
2187 assert(Val0->getType() == Val1->getType());
2188 int Len = length(Val0);
2189 SmallVector<int, 128> Mask(2 * Len);
2190
2191 for (int i = 0; i != Len; ++i) {
2192 Mask[i] = 2 * i; // Even
2193 Mask[i + Len] = 2 * i + 1; // Odd
2194 }
2195 return Builder.CreateShuffleVector(Val0, Val1, Mask, "shf");
2196}
2197
2198auto HexagonVectorCombine::vshuff(IRBuilderBase &Builder, Value *Val0,
2199 Value *Val1) const -> Value * { //
2200 assert(Val0->getType() == Val1->getType());
2201 int Len = length(Val0);
2202 SmallVector<int, 128> Mask(2 * Len);
2203
2204 for (int i = 0; i != Len; ++i) {
2205 Mask[2 * i + 0] = i; // Val0
2206 Mask[2 * i + 1] = i + Len; // Val1
2207 }
2208 return Builder.CreateShuffleVector(Val0, Val1, Mask, "shf");
2209}
2210
2211auto HexagonVectorCombine::createHvxIntrinsic(IRBuilderBase &Builder,
2212 Intrinsic::ID IntID, Type *RetTy,
2213 ArrayRef<Value *> Args,
2214 ArrayRef<Type *> ArgTys) const
2215 -> Value * {
2216 auto getCast = [&](IRBuilderBase &Builder, Value *Val,
2217 Type *DestTy) -> Value * {
2218 Type *SrcTy = Val->getType();
2219 if (SrcTy == DestTy)
2220 return Val;
2221
2222 // Non-HVX type. It should be a scalar, and it should already have
2223 // a valid type.
2224 assert(HST.isTypeForHVX(SrcTy, /*IncludeBool=*/true));
2225
2226 Type *BoolTy = Type::getInt1Ty(F.getContext());
2227 if (cast<VectorType>(SrcTy)->getElementType() != BoolTy)
2228 return Builder.CreateBitCast(Val, DestTy, "cst");
2229
2230 // Predicate HVX vector.
2231 unsigned HwLen = HST.getVectorLength();
2232 Intrinsic::ID TC = HwLen == 64 ? Intrinsic::hexagon_V6_pred_typecast
2233 : Intrinsic::hexagon_V6_pred_typecast_128B;
2234 Function *FI =
2235 Intrinsic::getDeclaration(F.getParent(), TC, {DestTy, Val->getType()});
2236 return Builder.CreateCall(FI, {Val}, "cup");
2237 };
2238
2239 Function *IntrFn = Intrinsic::getDeclaration(F.getParent(), IntID, ArgTys);
2240 FunctionType *IntrTy = IntrFn->getFunctionType();
2241
2242 SmallVector<Value *, 4> IntrArgs;
2243 for (int i = 0, e = Args.size(); i != e; ++i) {
2244 Value *A = Args[i];
2245 Type *T = IntrTy->getParamType(i);
2246 if (A->getType() != T) {
2247 IntrArgs.push_back(getCast(Builder, A, T));
2248 } else {
2249 IntrArgs.push_back(A);
2250 }
2251 }
2252 Value *Call = Builder.CreateCall(IntrFn, IntrArgs, "cup");
2253
2254 Type *CallTy = Call->getType();
2255 if (RetTy == nullptr || CallTy == RetTy)
2256 return Call;
2257 // Scalar types should have RetTy matching the call return type.
2258 assert(HST.isTypeForHVX(CallTy, /*IncludeBool=*/true));
2259 return getCast(Builder, Call, RetTy);
2260}
2261
2262auto HexagonVectorCombine::splitVectorElements(IRBuilderBase &Builder,
2263 Value *Vec,
2264 unsigned ToWidth) const
2266 // Break a vector of wide elements into a series of vectors with narrow
2267 // elements:
2268 // (...c0:b0:a0, ...c1:b1:a1, ...c2:b2:a2, ...)
2269 // -->
2270 // (a0, a1, a2, ...) // lowest "ToWidth" bits
2271 // (b0, b1, b2, ...) // the next lowest...
2272 // (c0, c1, c2, ...) // ...
2273 // ...
2274 //
2275 // The number of elements in each resulting vector is the same as
2276 // in the original vector.
2277
2278 auto *VecTy = cast<VectorType>(Vec->getType());
2279 assert(VecTy->getElementType()->isIntegerTy());
2280 unsigned FromWidth = VecTy->getScalarSizeInBits();
2281 assert(isPowerOf2_32(ToWidth) && isPowerOf2_32(FromWidth));
2282 assert(ToWidth <= FromWidth && "Breaking up into wider elements?");
2283 unsigned NumResults = FromWidth / ToWidth;
2284
2285 SmallVector<Value *> Results(NumResults);
2286 Results[0] = Vec;
2287 unsigned Length = length(VecTy);
2288
2289 // Do it by splitting in half, since those operations correspond to deal
2290 // instructions.
2291 auto splitInHalf = [&](unsigned Begin, unsigned End, auto splitFunc) -> void {
2292 // Take V = Results[Begin], split it in L, H.
2293 // Store Results[Begin] = L, Results[(Begin+End)/2] = H
2294 // Call itself recursively split(Begin, Half), split(Half+1, End)
2295 if (Begin + 1 == End)
2296 return;
2297
2298 Value *Val = Results[Begin];
2299 unsigned Width = Val->getType()->getScalarSizeInBits();
2300
2301 auto *VTy = VectorType::get(getIntTy(Width / 2), 2 * Length, false);
2302 Value *VVal = Builder.CreateBitCast(Val, VTy, "cst");
2303
2304 Value *Res = vdeal(Builder, sublo(Builder, VVal), subhi(Builder, VVal));
2305
2306 unsigned Half = (Begin + End) / 2;
2307 Results[Begin] = sublo(Builder, Res);
2308 Results[Half] = subhi(Builder, Res);
2309
2310 splitFunc(Begin, Half, splitFunc);
2311 splitFunc(Half, End, splitFunc);
2312 };
2313
2314 splitInHalf(0, NumResults, splitInHalf);
2315 return Results;
2316}
2317
2318auto HexagonVectorCombine::joinVectorElements(IRBuilderBase &Builder,
2319 ArrayRef<Value *> Values,
2320 VectorType *ToType) const
2321 -> Value * {
2322 assert(ToType->getElementType()->isIntegerTy());
2323
2324 // If the list of values does not have power-of-2 elements, append copies
2325 // of the sign bit to it, to make the size be 2^n.
2326 // The reason for this is that the values will be joined in pairs, because
2327 // otherwise the shuffles will result in convoluted code. With pairwise
2328 // joins, the shuffles will hopefully be folded into a perfect shuffle.
2329 // The output will need to be sign-extended to a type with element width
2330 // being a power-of-2 anyways.
2331 SmallVector<Value *> Inputs(Values.begin(), Values.end());
2332
2333 unsigned ToWidth = ToType->getScalarSizeInBits();
2334 unsigned Width = Inputs.front()->getType()->getScalarSizeInBits();
2335 assert(Width <= ToWidth);
2336 assert(isPowerOf2_32(Width) && isPowerOf2_32(ToWidth));
2337 unsigned Length = length(Inputs.front()->getType());
2338
2339 unsigned NeedInputs = ToWidth / Width;
2340 if (Inputs.size() != NeedInputs) {
2341 // Having too many inputs is ok: drop the high bits (usual wrap-around).
2342 // If there are too few, fill them with the sign bit.
2343 Value *Last = Inputs.back();
2344 Value *Sign = Builder.CreateAShr(
2345 Last, getConstSplat(Last->getType(), Width - 1), "asr");
2346 Inputs.resize(NeedInputs, Sign);
2347 }
2348
2349 while (Inputs.size() > 1) {
2350 Width *= 2;
2351 auto *VTy = VectorType::get(getIntTy(Width), Length, false);
2352 for (int i = 0, e = Inputs.size(); i < e; i += 2) {
2353 Value *Res = vshuff(Builder, Inputs[i], Inputs[i + 1]);
2354 Inputs[i / 2] = Builder.CreateBitCast(Res, VTy, "cst");
2355 }
2356 Inputs.resize(Inputs.size() / 2);
2357 }
2358
2359 assert(Inputs.front()->getType() == ToType);
2360 return Inputs.front();
2361}
2362
2363auto HexagonVectorCombine::calculatePointerDifference(Value *Ptr0,
2364 Value *Ptr1) const
2365 -> std::optional<int> {
2366 struct Builder : IRBuilder<> {
2367 Builder(BasicBlock *B) : IRBuilder<>(B->getTerminator()) {}
2368 ~Builder() {
2369 for (Instruction *I : llvm::reverse(ToErase))
2370 I->eraseFromParent();
2371 }
2373 };
2374
2375#define CallBuilder(B, F) \
2376 [&](auto &B_) { \
2377 Value *V = B_.F; \
2378 if (auto *I = dyn_cast<Instruction>(V)) \
2379 B_.ToErase.push_back(I); \
2380 return V; \
2381 }(B)
2382
2383 auto Simplify = [this](Value *V) {
2384 if (Value *S = simplify(V))
2385 return S;
2386 return V;
2387 };
2388
2389 auto StripBitCast = [](Value *V) {
2390 while (auto *C = dyn_cast<BitCastInst>(V))
2391 V = C->getOperand(0);
2392 return V;
2393 };
2394
2395 Ptr0 = StripBitCast(Ptr0);
2396 Ptr1 = StripBitCast(Ptr1);
2397 if (!isa<GetElementPtrInst>(Ptr0) || !isa<GetElementPtrInst>(Ptr1))
2398 return std::nullopt;
2399
2400 auto *Gep0 = cast<GetElementPtrInst>(Ptr0);
2401 auto *Gep1 = cast<GetElementPtrInst>(Ptr1);
2402 if (Gep0->getPointerOperand() != Gep1->getPointerOperand())
2403 return std::nullopt;
2404 if (Gep0->getSourceElementType() != Gep1->getSourceElementType())
2405 return std::nullopt;
2406
2407 Builder B(Gep0->getParent());
2408 int Scale = getSizeOf(Gep0->getSourceElementType(), Alloc);
2409
2410 // FIXME: for now only check GEPs with a single index.
2411 if (Gep0->getNumOperands() != 2 || Gep1->getNumOperands() != 2)
2412 return std::nullopt;
2413
2414 Value *Idx0 = Gep0->getOperand(1);
2415 Value *Idx1 = Gep1->getOperand(1);
2416
2417 // First, try to simplify the subtraction directly.
2418 if (auto *Diff = dyn_cast<ConstantInt>(
2419 Simplify(CallBuilder(B, CreateSub(Idx0, Idx1)))))
2420 return Diff->getSExtValue() * Scale;
2421
2422 KnownBits Known0 = getKnownBits(Idx0, Gep0);
2423 KnownBits Known1 = getKnownBits(Idx1, Gep1);
2424 APInt Unknown = ~(Known0.Zero | Known0.One) | ~(Known1.Zero | Known1.One);
2425 if (Unknown.isAllOnes())
2426 return std::nullopt;
2427
2428 Value *MaskU = ConstantInt::get(Idx0->getType(), Unknown);
2429 Value *AndU0 = Simplify(CallBuilder(B, CreateAnd(Idx0, MaskU)));
2430 Value *AndU1 = Simplify(CallBuilder(B, CreateAnd(Idx1, MaskU)));
2431 Value *SubU = Simplify(CallBuilder(B, CreateSub(AndU0, AndU1)));
2432 int Diff0 = 0;
2433 if (auto *C = dyn_cast<ConstantInt>(SubU)) {
2434 Diff0 = C->getSExtValue();
2435 } else {
2436 return std::nullopt;
2437 }
2438
2439 Value *MaskK = ConstantInt::get(MaskU->getType(), ~Unknown);
2440 Value *AndK0 = Simplify(CallBuilder(B, CreateAnd(Idx0, MaskK)));
2441 Value *AndK1 = Simplify(CallBuilder(B, CreateAnd(Idx1, MaskK)));
2442 Value *SubK = Simplify(CallBuilder(B, CreateSub(AndK0, AndK1)));
2443 int Diff1 = 0;
2444 if (auto *C = dyn_cast<ConstantInt>(SubK)) {
2445 Diff1 = C->getSExtValue();
2446 } else {
2447 return std::nullopt;
2448 }
2449
2450 return (Diff0 + Diff1) * Scale;
2451
2452#undef CallBuilder
2453}
2454
2455auto HexagonVectorCombine::getNumSignificantBits(const Value *V,
2456 const Instruction *CtxI) const
2457 -> unsigned {
2458 return ComputeMaxSignificantBits(V, DL, /*Depth=*/0, &AC, CtxI, &DT);
2459}
2460
2461auto HexagonVectorCombine::getKnownBits(const Value *V,
2462 const Instruction *CtxI) const
2463 -> KnownBits {
2464 return computeKnownBits(V, DL, /*Depth=*/0, &AC, CtxI, &DT, /*ORE=*/nullptr,
2465 /*UseInstrInfo=*/true);
2466}
2467
2468template <typename T>
2469auto HexagonVectorCombine::isSafeToMoveBeforeInBB(const Instruction &In,
2471 const T &IgnoreInsts) const
2472 -> bool {
2473 auto getLocOrNone =
2474 [this](const Instruction &I) -> std::optional<MemoryLocation> {
2475 if (const auto *II = dyn_cast<IntrinsicInst>(&I)) {
2476 switch (II->getIntrinsicID()) {
2477 case Intrinsic::masked_load:
2478 return MemoryLocation::getForArgument(II, 0, TLI);
2479 case Intrinsic::masked_store:
2480 return MemoryLocation::getForArgument(II, 1, TLI);
2481 }
2482 }
2484 };
2485
2486 // The source and the destination must be in the same basic block.
2487 const BasicBlock &Block = *In.getParent();
2488 assert(Block.begin() == To || Block.end() == To || To->getParent() == &Block);
2489 // No PHIs.
2490 if (isa<PHINode>(In) || (To != Block.end() && isa<PHINode>(*To)))
2491 return false;
2492
2494 return true;
2495 bool MayWrite = In.mayWriteToMemory();
2496 auto MaybeLoc = getLocOrNone(In);
2497
2498 auto From = In.getIterator();
2499 if (From == To)
2500 return true;
2501 bool MoveUp = (To != Block.end() && To->comesBefore(&In));
2502 auto Range =
2503 MoveUp ? std::make_pair(To, From) : std::make_pair(std::next(From), To);
2504 for (auto It = Range.first; It != Range.second; ++It) {
2505 const Instruction &I = *It;
2506 if (llvm::is_contained(IgnoreInsts, &I))
2507 continue;
2508 // assume intrinsic can be ignored
2509 if (auto *II = dyn_cast<IntrinsicInst>(&I)) {
2510 if (II->getIntrinsicID() == Intrinsic::assume)
2511 continue;
2512 }
2513 // Parts based on isSafeToMoveBefore from CoveMoverUtils.cpp.
2514 if (I.mayThrow())
2515 return false;
2516 if (auto *CB = dyn_cast<CallBase>(&I)) {
2517 if (!CB->hasFnAttr(Attribute::WillReturn))
2518 return false;
2519 if (!CB->hasFnAttr(Attribute::NoSync))
2520 return false;
2521 }
2522 if (I.mayReadOrWriteMemory()) {
2523 auto MaybeLocI = getLocOrNone(I);
2524 if (MayWrite || I.mayWriteToMemory()) {
2525 if (!MaybeLoc || !MaybeLocI)
2526 return false;
2527 if (!AA.isNoAlias(*MaybeLoc, *MaybeLocI))
2528 return false;
2529 }
2530 }
2531 }
2532 return true;
2533}
2534
2535auto HexagonVectorCombine::isByteVecTy(Type *Ty) const -> bool {
2536 if (auto *VecTy = dyn_cast<VectorType>(Ty))
2537 return VecTy->getElementType() == getByteTy();
2538 return false;
2539}
2540
2541auto HexagonVectorCombine::getElementRange(IRBuilderBase &Builder, Value *Lo,
2542 Value *Hi, int Start,
2543 int Length) const -> Value * {
2544 assert(0 <= Start && size_t(Start + Length) < length(Lo) + length(Hi));
2546 std::iota(SMask.begin(), SMask.end(), Start);
2547 return Builder.CreateShuffleVector(Lo, Hi, SMask, "shf");
2548}
2549
2550// Pass management.
2551
2552namespace llvm {
2555} // namespace llvm
2556
2557namespace {
2558class HexagonVectorCombineLegacy : public FunctionPass {
2559public:
2560 static char ID;
2561
2562 HexagonVectorCombineLegacy() : FunctionPass(ID) {}
2563
2564 StringRef getPassName() const override { return "Hexagon Vector Combine"; }
2565
2566 void getAnalysisUsage(AnalysisUsage &AU) const override {
2567 AU.setPreservesCFG();
2574 }
2575
2576 bool runOnFunction(Function &F) override {
2577 if (skipFunction(F))
2578 return false;
2579 AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
2580 AssumptionCache &AC =
2581 getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
2582 DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
2583 TargetLibraryInfo &TLI =
2584 getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
2585 auto &TM = getAnalysis<TargetPassConfig>().getTM<HexagonTargetMachine>();
2586 HexagonVectorCombine HVC(F, AA, AC, DT, TLI, TM);
2587 return HVC.run();
2588 }
2589};
2590} // namespace
2591
2592char HexagonVectorCombineLegacy::ID = 0;
2593
2594INITIALIZE_PASS_BEGIN(HexagonVectorCombineLegacy, DEBUG_TYPE,
2595 "Hexagon Vector Combine", false, false)
2601INITIALIZE_PASS_END(HexagonVectorCombineLegacy, DEBUG_TYPE,
2603
2605 return new HexagonVectorCombineLegacy();
2606}
aarch64 promote const
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
SmallPtrSet< MachineInstr *, 2 > Uses
Function Alias Analysis Results
assume Assume Simplify
assume Assume Builder
BlockVerifier::State From
static IntegerType * getIntTy(IRBuilderBase &B, const TargetLibraryInfo *TLI)
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Analysis containing CSE Info
Definition: CSEInfo.cpp:27
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:172
return RetTy
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Given that RA is a live value
Mark the given Function as meaning that it cannot be changed in any way mark any values that are used as this function s parameters or by its return values(according to Uses) live as well. void DeadArgumentEliminationPass
#define LLVM_DEBUG(X)
Definition: Debug.h:101
This file defines the DenseMap class.
uint64_t Addr
uint64_t Size
static GCMetadataPrinterRegistry::Add< ErlangGCPrinter > X("erlang", "erlang-compatible garbage collector")
hexagon bit simplify
static bool isUndef(ArrayRef< int > Mask)
#define CallBuilder(B, F)
Hexagon Vector Combine
#define DEBUG_TYPE
static bool isZero(Value *V, const DataLayout &DL, DominatorTree *DT, AssumptionCache *AC)
Definition: Lint.cpp:524
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
#define G(x, y, z)
Definition: MD5.cpp:56
#define H(x, y, z)
Definition: MD5.cpp:57
static bool isCandidate(const MachineInstr *MI, Register &DefedReg, Register FrameReg)
This file contains the declarations for metadata subclasses.
IntegerType * Int32Ty
return ToRemove size() > 0
static GCMetadataPrinterRegistry::Add< OcamlGCMetadataPrinter > Y("ocaml", "ocaml 3.10-compatible collector")
#define P(N)
const char LLVMTargetMachineRef TM
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:55
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:59
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:52
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
static MemoryLocation getLocation(Instruction *I)
static ConstantInt * getConstInt(MDNode *MD, unsigned NumOp)
This file contains some templates that are useful if you are working with the STL at all.
raw_pwrite_stream & OS
This file defines the SmallVector class.
static SymbolRef::Type getType(const Symbol *Sym)
Definition: TapiFile.cpp:40
Target-Independent Code Generator Pass Configuration Options pass.
A wrapper pass to provide the legacy pass manager access to a suitably prepared AAResults object.
Class for arbitrary precision integers.
Definition: APInt.h:75
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1494
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:354
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:815
Represent the analysis usage information of a pass.
AnalysisUsage & addRequired()
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Definition: Pass.cpp:265
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of @llvm.assume calls within a function.
LLVM Basic Block Representation.
Definition: BasicBlock.h:56
iterator end()
Definition: BasicBlock.h:316
InstListType::const_iterator const_iterator
Definition: BasicBlock.h:88
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction if the block is well formed or null if the block is not well forme...
Definition: BasicBlock.h:127
@ ICMP_ULT
unsigned less than
Definition: InstrTypes.h:743
This is the shared class of boolean and integer constants.
Definition: Constants.h:78
static ConstantInt * getTrue(LLVMContext &Context)
Definition: Constants.cpp:833
static Constant * get(Type *Ty, uint64_t V, bool IsSigned=false)
If Ty is a vector type, return a Constant with a splat of the given value.
Definition: Constants.cpp:888
static ConstantInt * getSigned(IntegerType *Ty, int64_t V)
Return a ConstantInt with the specified value for the specified type.
Definition: Constants.cpp:902
static Constant * getSplat(ElementCount EC, Constant *Elt)
Return a ConstantVector with the specified constant in each element.
Definition: Constants.cpp:1400
This is an important base class in LLVM.
Definition: Constant.h:41
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
iterator_range< iterator > children()
NodeT * getBlock() const
Legacy analysis pass which computes a DominatorTree.
Definition: Dominators.h:314
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
virtual bool runOnFunction(Function &F)=0
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
bool skipFunction(const Function &F) const
Optional passes call this function to check whether the pass should be skipped.
Definition: Pass.cpp:174
bool empty() const
Definition: Function.h:762
FunctionType * getFunctionType() const
Returns the FunctionType for me.
Definition: Function.h:174
const BasicBlock & back() const
Definition: Function.h:765
Common base class shared among various IRBuilders.
Definition: IRBuilder.h:94
This provides a uniform API for creating instructions and inserting them into a basic block: either a...
Definition: IRBuilder.h:2558
InstSimplifyFolder - Use InstructionSimplify to fold operations to existing values.
const BasicBlock * getParent() const
Definition: Instruction.h:90
const char * getOpcodeName() const
Definition: Instruction.h:170
Class to represent integer types.
Definition: DerivedTypes.h:40
static IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
Definition: Type.cpp:331
An instruction for reading from memory.
Definition: Instructions.h:177
static std::optional< MemoryLocation > getOrNone(const Instruction *Inst)
static MemoryLocation getForArgument(const CallBase *Call, unsigned ArgIdx, const TargetLibraryInfo *TLI)
Return a location representing a particular argument of a call.
PassRegistry - This class manages the registration and intitialization of the pass subsystem as appli...
Definition: PassRegistry.h:38
virtual void getAnalysisUsage(AnalysisUsage &) const
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: Pass.cpp:98
virtual StringRef getPassName() const
getPassName - Return a nice clean name for a pass.
Definition: Pass.cpp:81
void assign(size_type NumElts, ValueParamT Elt)
Definition: SmallVector.h:708
void resize(size_type N)
Definition: SmallVector.h:642
void push_back(const T &Elt)
Definition: SmallVector.h:416
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1200
An instruction for storing to memory.
Definition: Instructions.h:301
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
Provides information about what library functions are available for the current target.
Primary interface to the complete machine description for the target machine.
Definition: TargetMachine.h:78
virtual const TargetSubtargetInfo * getSubtargetImpl(const Function &) const
Virtual method implemented by subclasses that returns a reference to that target's TargetSubtargetInf...
Target-Independent Code Generator Pass Configuration Options.
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isVectorTy() const
True if this is an instance of VectorType.
Definition: Type.h:267
PointerType * getPointerTo(unsigned AddrSpace=0) const
Return a pointer to the current type.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:237
static IntegerType * getInt1Ty(LLVMContext &C)
Type * getNonOpaquePointerElementType() const
Only use this method in code that is not reachable with opaque pointers, or part of deprecated method...
Definition: Type.h:425
unsigned getScalarSizeInBits() const LLVM_READONLY
If this is a vector type, return the getPrimitiveSizeInBits value for the element type.
static IntegerType * getInt8Ty(LLVMContext &C)
static PointerType * getInt8PtrTy(LLVMContext &C, unsigned AS=0)
static IntegerType * getInt32Ty(LLVMContext &C)
static IntegerType * getInt64Ty(LLVMContext &C)
bool isIntegerTy() const
True if this is an instance of IntegerType.
Definition: Type.h:231
Type * getScalarType() const
If this is a vector type, return the element type, otherwise return 'this'.
Definition: Type.h:350
static UndefValue * get(Type *T)
Static factory methods - Return an 'undef' object of the specified type.
Definition: Constants.cpp:1739
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
self_iterator getIterator()
Definition: ilist_node.h:82
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
friend const_iterator begin(StringRef path, Style style)
Get begin iterator over path.
Definition: Path.cpp:226
friend const_iterator end(StringRef path)
Get end iterator over path.
Definition: Path.cpp:235
#define llvm_unreachable(msg)
Marks that the current location is not supposed to be reachable.
Rounding
Possible values of current rounding mode, which is specified in bits 23:22 of FPCR.
constexpr char Args[]
Key for Kernel::Metadata::mArgs.
constexpr std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:119
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
Function * getDeclaration(Module *M, ID id, ArrayRef< Type * > Tys=std::nullopt)
Create or insert an LLVM Function declaration for an intrinsic, and return it.
Definition: Function.cpp:1506
BinaryOp_match< LHS, RHS, Instruction::Add > m_Add(const LHS &L, const RHS &R)
Definition: PatternMatch.h:979
BinaryOp_match< LHS, RHS, Instruction::AShr > m_AShr(const LHS &L, const RHS &R)
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
BinOpPred_match< LHS, RHS, is_right_shift_op > m_Shr(const LHS &L, const RHS &R)
Matches logical shift operations.
BinaryOp_match< LHS, RHS, Instruction::Mul > m_Mul(const LHS &L, const RHS &R)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:278
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:76
BinaryOp_match< LHS, RHS, Instruction::LShr > m_LShr(const LHS &L, const RHS &R)
match_combine_or< LTy, RTy > m_CombineOr(const LTy &L, const RTy &R)
Combine two pattern matchers matching L || R.
Definition: PatternMatch.h:218
@ Undef
Value of the register doesn't matter.
constexpr double e
Definition: MathExtras.h:31
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
FunctionPass * createHexagonVectorCombineLegacyPass()
@ Offset
Definition: DWP.cpp:406
@ Length
Definition: DWP.cpp:406
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1782
bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
Definition: Local.cpp:537
void append_range(Container &C, Range &&R)
Wrapper function to append a range to a container.
Definition: STLExtras.h:2092
constexpr bool isPowerOf2_64(uint64_t Value)
Return true if the argument is a power of two > 0 (64 bit edition.)
Definition: MathExtras.h:297
Instruction * propagateMetadata(Instruction *I, ArrayRef< Value * > VL)
Specifically, let Kinds = [MD_tbaa, MD_alias_scope, MD_noalias, MD_fpmath, MD_nontemporal,...
OutputIt copy_if(R &&Range, OutputIt Out, UnaryPredicate P)
Provide wrappers to std::copy_if which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1828
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:388
uint64_t PowerOf2Ceil(uint64_t A)
Returns the power of two which is greater than or equal to the given value.
Definition: MathExtras.h:469
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1789
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:495
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:292
void sort(IteratorTy Start, IteratorTy End)
Definition: STLExtras.h:1730
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
bool none_of(R &&Range, UnaryPredicate P)
Provide wrappers to std::none_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1796
detail::concat_range< ValueT, RangeTs... > concat(RangeTs &&... Ranges)
Concatenated range across two or more ranges.
Definition: STLExtras.h:1254
void initializeHexagonVectorCombineLegacyPass(PassRegistry &)
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, OptimizationRemarkEmitter *ORE=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
Value * simplifyInstruction(Instruction *I, const SimplifyQuery &Q, OptimizationRemarkEmitter *ORE=nullptr)
See if we can compute a simplified version of this instruction.
@ And
Bitwise or logical AND of integers.
uint64_t alignTo(uint64_t Size, Align A)
Returns a multiple of A needed to store Size bytes.
Definition: Alignment.h:155
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:292
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1909
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:2076
bool is_contained(R &&Range, const E &Element)
Returns true if Element is found in Range.
Definition: STLExtras.h:1939
unsigned ComputeMaxSignificantBits(const Value *Op, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr)
Get the upper bound on bit size for this Value Op as a signed integer.
bool mayHaveNonDefUseDependency(const Instruction &I)
Returns true if the result or effects of the given instructions I depend values not reachable through...
MaskT vshuff(ArrayRef< int > Vu, ArrayRef< int > Vv, unsigned Size, bool TakeOdd)
MaskT vdeal(ArrayRef< int > Vu, ArrayRef< int > Vv, unsigned Size, bool TakeOdd)
Definition: BitVector.h:851
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:853
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
Extended Value Type.
Definition: ValueTypes.h:34
bool isSimple() const
Test if the given EVT is simple (as opposed to being extended).
Definition: ValueTypes.h:129
TypeSize getSizeInBits() const
Return the size of the specified value type in bits.
Definition: ValueTypes.h:351
static EVT getEVT(Type *Ty, bool HandleUnknown=false)
Return the value type corresponding to the specified type.
Definition: ValueTypes.cpp:615
MVT getSimpleVT() const
Return the SimpleValueType held in the specified simple EVT.
Definition: ValueTypes.h:299