xref: /llvm-project/llvm/lib/Target/Hexagon/HexagonVectorCombine.cpp (revision 2d8cc5479b9e9eb96a0e7f70f473c03b82f4084c)
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/Optional.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallVector.h"
20 #include "llvm/Analysis/AliasAnalysis.h"
21 #include "llvm/Analysis/AssumptionCache.h"
22 #include "llvm/Analysis/InstructionSimplify.h"
23 #include "llvm/Analysis/TargetLibraryInfo.h"
24 #include "llvm/Analysis/ValueTracking.h"
25 #include "llvm/CodeGen/TargetPassConfig.h"
26 #include "llvm/IR/Dominators.h"
27 #include "llvm/IR/IRBuilder.h"
28 #include "llvm/IR/IntrinsicInst.h"
29 #include "llvm/IR/Intrinsics.h"
30 #include "llvm/IR/IntrinsicsHexagon.h"
31 #include "llvm/InitializePasses.h"
32 #include "llvm/Pass.h"
33 #include "llvm/Support/KnownBits.h"
34 #include "llvm/Support/MathExtras.h"
35 #include "llvm/Support/raw_ostream.h"
36 #include "llvm/Target/TargetMachine.h"
37 
38 #include "HexagonSubtarget.h"
39 #include "HexagonTargetMachine.h"
40 
41 #include <algorithm>
42 #include <deque>
43 #include <map>
44 #include <set>
45 #include <utility>
46 #include <vector>
47 
48 #define DEBUG_TYPE "hexagon-vc"
49 
50 using namespace llvm;
51 
52 namespace {
53 class HexagonVectorCombine {
54 public:
55   HexagonVectorCombine(Function &F_, AliasAnalysis &AA_, AssumptionCache &AC_,
56                        DominatorTree &DT_, TargetLibraryInfo &TLI_,
57                        const TargetMachine &TM_)
58       : F(F_), DL(F.getParent()->getDataLayout()), AA(AA_), AC(AC_), DT(DT_),
59         TLI(TLI_),
60         HST(static_cast<const HexagonSubtarget &>(*TM_.getSubtargetImpl(F))) {}
61 
62   bool run();
63 
64   // Common integer type.
65   IntegerType *getIntTy() const;
66   // Byte type: either scalar (when Length = 0), or vector with given
67   // element count.
68   Type *getByteTy(int ElemCount = 0) const;
69   // Boolean type: either scalar (when Length = 0), or vector with given
70   // element count.
71   Type *getBoolTy(int ElemCount = 0) const;
72   // Create a ConstantInt of type returned by getIntTy with the value Val.
73   ConstantInt *getConstInt(int Val) const;
74   // Get the integer value of V, if it exists.
75   Optional<APInt> getIntValue(const Value *Val) const;
76   // Is V a constant 0, or a vector of 0s?
77   bool isZero(const Value *Val) const;
78   // Is V an undef value?
79   bool isUndef(const Value *Val) const;
80 
81   int getSizeOf(const Value *Val) const;
82   int getSizeOf(const Type *Ty) const;
83   int getTypeAlignment(Type *Ty) const;
84 
85   VectorType *getByteVectorTy(int ScLen) const;
86   Constant *getNullValue(Type *Ty) const;
87   Constant *getFullValue(Type *Ty) const;
88 
89   Value *insertb(IRBuilder<> &Builder, Value *Dest, Value *Src, int Start,
90                  int Length, int Where) const;
91   Value *vlalignb(IRBuilder<> &Builder, Value *Lo, Value *Hi, Value *Amt) const;
92   Value *vralignb(IRBuilder<> &Builder, Value *Lo, Value *Hi, Value *Amt) const;
93   Value *concat(IRBuilder<> &Builder, ArrayRef<Value *> Vecs) const;
94   Value *vresize(IRBuilder<> &Builder, Value *Val, int NewSize,
95                  Value *Pad) const;
96   Value *rescale(IRBuilder<> &Builder, Value *Mask, Type *FromTy,
97                  Type *ToTy) const;
98   Value *vlsb(IRBuilder<> &Builder, Value *Val) const;
99   Value *vbytes(IRBuilder<> &Builder, Value *Val) const;
100 
101   Value *createHvxIntrinsic(IRBuilder<> &Builder, Intrinsic::ID IntID,
102                             Type *RetTy, ArrayRef<Value *> Args) const;
103 
104   Optional<int> calculatePointerDifference(Value *Ptr0, Value *Ptr1) const;
105 
106   template <typename T = std::vector<Instruction *>>
107   bool isSafeToMoveBeforeInBB(const Instruction &In,
108                               BasicBlock::const_iterator To,
109                               const T &Ignore = {}) const;
110 
111   Function &F;
112   const DataLayout &DL;
113   AliasAnalysis &AA;
114   AssumptionCache &AC;
115   DominatorTree &DT;
116   TargetLibraryInfo &TLI;
117   const HexagonSubtarget &HST;
118 
119 private:
120   bool isByteVecTy(Type *Ty) const;
121   bool isSectorTy(Type *Ty) const;
122   Value *getElementRange(IRBuilder<> &Builder, Value *Lo, Value *Hi, int Start,
123                          int Length) const;
124 };
125 
126 class AlignVectors {
127 public:
128   AlignVectors(HexagonVectorCombine &HVC_) : HVC(HVC_) {}
129 
130   bool run();
131 
132 private:
133   using InstList = std::vector<Instruction *>;
134 
135   struct Segment {
136     void *Data;
137     int Start;
138     int Size;
139   };
140 
141   struct AddrInfo {
142     AddrInfo(const AddrInfo &) = default;
143     AddrInfo(const HexagonVectorCombine &HVC, Instruction *I, Value *A, Type *T,
144              Align H)
145         : Inst(I), Addr(A), ValTy(T), HaveAlign(H),
146           NeedAlign(HVC.getTypeAlignment(ValTy)) {}
147 
148     // XXX: add Size member?
149     Instruction *Inst;
150     Value *Addr;
151     Type *ValTy;
152     Align HaveAlign;
153     Align NeedAlign;
154     int Offset = 0; // Offset (in bytes) from the first member of the
155                     // containing AddrList.
156   };
157   using AddrList = std::vector<AddrInfo>;
158 
159   struct InstrLess {
160     bool operator()(const Instruction *A, const Instruction *B) const {
161       return A->comesBefore(B);
162     }
163   };
164   using DepList = std::set<Instruction *, InstrLess>;
165 
166   struct MoveGroup {
167     MoveGroup(const AddrInfo &AI, Instruction *B, bool Hvx, bool Load)
168         : Base(B), Main{AI.Inst}, IsHvx(Hvx), IsLoad(Load) {}
169     Instruction *Base; // Base instruction of the parent address group.
170     InstList Main;     // Main group of instructions.
171     InstList Deps;     // List of dependencies.
172     bool IsHvx;        // Is this group of HVX instructions?
173     bool IsLoad;       // Is this a load group?
174   };
175   using MoveList = std::vector<MoveGroup>;
176 
177   struct ByteSpan {
178     struct Segment {
179       Segment(Value *Val, int Begin, int Len)
180           : Val(Val), Start(Begin), Size(Len) {}
181       Segment(const Segment &Seg) = default;
182       Value *Val;
183       int Start;
184       int Size;
185     };
186 
187     struct Block {
188       Block(Value *Val, int Len, int Pos) : Seg(Val, 0, Len), Pos(Pos) {}
189       Block(Value *Val, int Off, int Len, int Pos)
190           : Seg(Val, Off, Len), Pos(Pos) {}
191       Block(const Block &Blk) = default;
192       Segment Seg;
193       int Pos;
194     };
195 
196     int extent() const;
197     ByteSpan section(int Start, int Length) const;
198     ByteSpan &normalize();
199 
200     int size() const { return Blocks.size(); }
201     Block &operator[](int i) { return Blocks[i]; }
202 
203     std::vector<Block> Blocks;
204 
205     using iterator = decltype(Blocks)::iterator;
206     iterator begin() { return Blocks.begin(); }
207     iterator end() { return Blocks.end(); }
208     using const_iterator = decltype(Blocks)::const_iterator;
209     const_iterator begin() const { return Blocks.begin(); }
210     const_iterator end() const { return Blocks.end(); }
211   };
212 
213   Align getAlignFromValue(const Value *V) const;
214   Optional<MemoryLocation> getLocation(const Instruction &In) const;
215   Optional<AddrInfo> getAddrInfo(Instruction &In) const;
216   bool isHvx(const AddrInfo &AI) const;
217 
218   Value *getPayload(Value *Val) const;
219   Value *getMask(Value *Val) const;
220   Value *getPassThrough(Value *Val) const;
221 
222   Value *createAdjustedPointer(IRBuilder<> &Builder, Value *Ptr, Type *ValTy,
223                                int Adjust) const;
224   Value *createAlignedPointer(IRBuilder<> &Builder, Value *Ptr, Type *ValTy,
225                               int Alignment) const;
226   Value *createAlignedLoad(IRBuilder<> &Builder, Type *ValTy, Value *Ptr,
227                            int Alignment, Value *Mask, Value *PassThru) const;
228   Value *createAlignedStore(IRBuilder<> &Builder, Value *Val, Value *Ptr,
229                             int Alignment, Value *Mask) const;
230 
231   bool createAddressGroups();
232   MoveList createLoadGroups(const AddrList &Group) const;
233   MoveList createStoreGroups(const AddrList &Group) const;
234   bool move(const MoveGroup &Move) const;
235   bool realignGroup(const MoveGroup &Move) const;
236 
237   friend raw_ostream &operator<<(raw_ostream &OS, const AddrInfo &AI);
238   friend raw_ostream &operator<<(raw_ostream &OS, const MoveGroup &MG);
239   friend raw_ostream &operator<<(raw_ostream &OS, const ByteSpan &BS);
240 
241   std::map<Instruction *, AddrList> AddrGroups;
242   HexagonVectorCombine &HVC;
243 };
244 
245 LLVM_ATTRIBUTE_UNUSED
246 raw_ostream &operator<<(raw_ostream &OS, const AlignVectors::AddrInfo &AI) {
247   OS << "Inst: " << AI.Inst << "  " << *AI.Inst << '\n';
248   OS << "Addr: " << *AI.Addr << '\n';
249   OS << "Type: " << *AI.ValTy << '\n';
250   OS << "HaveAlign: " << AI.HaveAlign.value() << '\n';
251   OS << "NeedAlign: " << AI.NeedAlign.value() << '\n';
252   OS << "Offset: " << AI.Offset;
253   return OS;
254 }
255 
256 LLVM_ATTRIBUTE_UNUSED
257 raw_ostream &operator<<(raw_ostream &OS, const AlignVectors::MoveGroup &MG) {
258   OS << "Main\n";
259   for (Instruction *I : MG.Main)
260     OS << "  " << *I << '\n';
261   OS << "Deps\n";
262   for (Instruction *I : MG.Deps)
263     OS << "  " << *I << '\n';
264   return OS;
265 }
266 
267 LLVM_ATTRIBUTE_UNUSED
268 raw_ostream &operator<<(raw_ostream &OS, const AlignVectors::ByteSpan &BS) {
269   OS << "ByteSpan[size=" << BS.size() << ", extent=" << BS.extent() << '\n';
270   for (const AlignVectors::ByteSpan::Block &B : BS) {
271     OS << "  @" << B.Pos << " [" << B.Seg.Start << ',' << B.Seg.Size << "] "
272        << *B.Seg.Val << '\n';
273   }
274   OS << ']';
275   return OS;
276 }
277 
278 } // namespace
279 
280 namespace {
281 
282 template <typename T> T *getIfUnordered(T *MaybeT) {
283   return MaybeT && MaybeT->isUnordered() ? MaybeT : nullptr;
284 }
285 template <typename T> T *isCandidate(Instruction *In) {
286   return dyn_cast<T>(In);
287 }
288 template <> LoadInst *isCandidate<LoadInst>(Instruction *In) {
289   return getIfUnordered(dyn_cast<LoadInst>(In));
290 }
291 template <> StoreInst *isCandidate<StoreInst>(Instruction *In) {
292   return getIfUnordered(dyn_cast<StoreInst>(In));
293 }
294 
295 #if !defined(_MSC_VER) || _MSC_VER >= 1920
296 // VS2017 has trouble compiling this:
297 // error C2976: 'std::map': too few template arguments
298 template <typename Pred, typename... Ts>
299 void erase_if(std::map<Ts...> &map, Pred p)
300 #else
301 template <typename Pred, typename T, typename U>
302 void erase_if(std::map<T, U> &map, Pred p)
303 #endif
304 {
305   for (auto i = map.begin(), e = map.end(); i != e;) {
306     if (p(*i))
307       i = map.erase(i);
308     else
309       i = std::next(i);
310   }
311 }
312 
313 // Forward other erase_ifs to the LLVM implementations.
314 template <typename Pred, typename T> void erase_if(T &&container, Pred p) {
315   llvm::erase_if(std::forward<T>(container), p);
316 }
317 
318 } // namespace
319 
320 // --- Begin AlignVectors
321 
322 auto AlignVectors::ByteSpan::extent() const -> int {
323   if (size() == 0)
324     return 0;
325   int Min = Blocks[0].Pos;
326   int Max = Blocks[0].Pos + Blocks[0].Seg.Size;
327   for (int i = 1, e = size(); i != e; ++i) {
328     Min = std::min(Min, Blocks[i].Pos);
329     Max = std::max(Max, Blocks[i].Pos + Blocks[i].Seg.Size);
330   }
331   return Max - Min;
332 }
333 
334 auto AlignVectors::ByteSpan::section(int Start, int Length) const -> ByteSpan {
335   ByteSpan Section;
336   for (const ByteSpan::Block &B : Blocks) {
337     int L = std::max(B.Pos, Start);                       // Left end.
338     int R = std::min(B.Pos + B.Seg.Size, Start + Length); // Right end+1.
339     if (L < R) {
340       // How much to chop off the beginning of the segment:
341       int Off = L > B.Pos ? L - B.Pos : 0;
342       Section.Blocks.emplace_back(B.Seg.Val, B.Seg.Start + Off, R - L, L);
343     }
344   }
345   return Section;
346 }
347 
348 auto AlignVectors::ByteSpan::normalize() -> ByteSpan & {
349   if (size() == 0)
350     return *this;
351   int Min = Blocks[0].Pos;
352   for (int i = 1, e = size(); i != e; ++i)
353     Min = std::min(Min, Blocks[i].Pos);
354   if (Min != 0) {
355     for (Block &B : Blocks)
356       B.Pos -= Min;
357   }
358   return *this;
359 }
360 
361 auto AlignVectors::getAlignFromValue(const Value *V) const -> Align {
362   const auto *C = dyn_cast<ConstantInt>(V);
363   assert(C && "Alignment must be a compile-time constant integer");
364   return C->getAlignValue();
365 }
366 
367 auto AlignVectors::getAddrInfo(Instruction &In) const -> Optional<AddrInfo> {
368   if (auto *L = isCandidate<LoadInst>(&In))
369     return AddrInfo(HVC, L, L->getPointerOperand(), L->getType(),
370                     L->getAlign());
371   if (auto *S = isCandidate<StoreInst>(&In))
372     return AddrInfo(HVC, S, S->getPointerOperand(),
373                     S->getValueOperand()->getType(), S->getAlign());
374   if (auto *II = isCandidate<IntrinsicInst>(&In)) {
375     Intrinsic::ID ID = II->getIntrinsicID();
376     switch (ID) {
377     case Intrinsic::masked_load:
378       return AddrInfo(HVC, II, II->getArgOperand(0), II->getType(),
379                       getAlignFromValue(II->getArgOperand(1)));
380     case Intrinsic::masked_store:
381       return AddrInfo(HVC, II, II->getArgOperand(1),
382                       II->getArgOperand(0)->getType(),
383                       getAlignFromValue(II->getArgOperand(2)));
384     }
385   }
386   return Optional<AddrInfo>();
387 }
388 
389 auto AlignVectors::isHvx(const AddrInfo &AI) const -> bool {
390   return HVC.HST.isTypeForHVX(AI.ValTy);
391 }
392 
393 auto AlignVectors::getPayload(Value *Val) const -> Value * {
394   if (auto *In = dyn_cast<Instruction>(Val)) {
395     Intrinsic::ID ID = 0;
396     if (auto *II = dyn_cast<IntrinsicInst>(In))
397       ID = II->getIntrinsicID();
398     if (isa<StoreInst>(In) || ID == Intrinsic::masked_store)
399       return In->getOperand(0);
400   }
401   return Val;
402 }
403 
404 auto AlignVectors::getMask(Value *Val) const -> Value * {
405   if (auto *II = dyn_cast<IntrinsicInst>(Val)) {
406     switch (II->getIntrinsicID()) {
407     case Intrinsic::masked_load:
408       return II->getArgOperand(2);
409     case Intrinsic::masked_store:
410       return II->getArgOperand(3);
411     }
412   }
413 
414   Type *ValTy = getPayload(Val)->getType();
415   if (auto *VecTy = dyn_cast<VectorType>(ValTy)) {
416     int ElemCount = VecTy->getElementCount().getFixedValue();
417     return HVC.getFullValue(HVC.getBoolTy(ElemCount));
418   }
419   return HVC.getFullValue(HVC.getBoolTy());
420 }
421 
422 auto AlignVectors::getPassThrough(Value *Val) const -> Value * {
423   if (auto *II = dyn_cast<IntrinsicInst>(Val)) {
424     if (II->getIntrinsicID() == Intrinsic::masked_load)
425       return II->getArgOperand(3);
426   }
427   return UndefValue::get(getPayload(Val)->getType());
428 }
429 
430 auto AlignVectors::createAdjustedPointer(IRBuilder<> &Builder, Value *Ptr,
431                                          Type *ValTy, int Adjust) const
432     -> Value * {
433   // The adjustment is in bytes, but if it's a multiple of the type size,
434   // we don't need to do pointer casts.
435   Type *ElemTy = cast<PointerType>(Ptr->getType())->getElementType();
436   int ElemSize = HVC.getSizeOf(ElemTy);
437   if (Adjust % ElemSize == 0) {
438     Value *Tmp0 = Builder.CreateGEP(Ptr, HVC.getConstInt(Adjust / ElemSize));
439     return Builder.CreatePointerCast(Tmp0, ValTy->getPointerTo());
440   }
441 
442   PointerType *CharPtrTy = Type::getInt8PtrTy(HVC.F.getContext());
443   Value *Tmp0 = Builder.CreatePointerCast(Ptr, CharPtrTy);
444   Value *Tmp1 = Builder.CreateGEP(Tmp0, HVC.getConstInt(Adjust));
445   return Builder.CreatePointerCast(Tmp1, ValTy->getPointerTo());
446 }
447 
448 auto AlignVectors::createAlignedPointer(IRBuilder<> &Builder, Value *Ptr,
449                                         Type *ValTy, int Alignment) const
450     -> Value * {
451   Value *AsInt = Builder.CreatePtrToInt(Ptr, HVC.getIntTy());
452   Value *Mask = HVC.getConstInt(-Alignment);
453   Value *And = Builder.CreateAnd(AsInt, Mask);
454   return Builder.CreateIntToPtr(And, ValTy->getPointerTo());
455 }
456 
457 auto AlignVectors::createAlignedLoad(IRBuilder<> &Builder, Type *ValTy,
458                                      Value *Ptr, int Alignment, Value *Mask,
459                                      Value *PassThru) const -> Value * {
460   assert(!HVC.isUndef(Mask)); // Should this be allowed?
461   if (HVC.isZero(Mask))
462     return PassThru;
463   if (Mask == ConstantInt::getTrue(Mask->getType()))
464     return Builder.CreateAlignedLoad(ValTy, Ptr, Align(Alignment));
465   return Builder.CreateMaskedLoad(Ptr, Align(Alignment), Mask, PassThru);
466 }
467 
468 auto AlignVectors::createAlignedStore(IRBuilder<> &Builder, Value *Val,
469                                       Value *Ptr, int Alignment,
470                                       Value *Mask) const -> Value * {
471   if (HVC.isZero(Mask) || HVC.isUndef(Val) || HVC.isUndef(Mask))
472     return UndefValue::get(Val->getType());
473   if (Mask == ConstantInt::getTrue(Mask->getType()))
474     return Builder.CreateAlignedStore(Val, Ptr, Align(Alignment));
475   return Builder.CreateMaskedStore(Val, Ptr, Align(Alignment), Mask);
476 }
477 
478 auto AlignVectors::createAddressGroups() -> bool {
479   // An address group created here may contain instructions spanning
480   // multiple basic blocks.
481   AddrList WorkStack;
482 
483   auto findBaseAndOffset = [&](AddrInfo &AI) -> std::pair<Instruction *, int> {
484     for (AddrInfo &W : WorkStack) {
485       if (auto D = HVC.calculatePointerDifference(AI.Addr, W.Addr))
486         return std::make_pair(W.Inst, *D);
487     }
488     return std::make_pair(nullptr, 0);
489   };
490 
491   auto traverseBlock = [&](DomTreeNode *DomN, auto Visit) -> void {
492     BasicBlock &Block = *DomN->getBlock();
493     for (Instruction &I : Block) {
494       auto AI = this->getAddrInfo(I); // Use this-> for gcc6.
495       if (!AI)
496         continue;
497       auto F = findBaseAndOffset(*AI);
498       Instruction *GroupInst;
499       if (Instruction *BI = F.first) {
500         AI->Offset = F.second;
501         GroupInst = BI;
502       } else {
503         WorkStack.push_back(*AI);
504         GroupInst = AI->Inst;
505       }
506       AddrGroups[GroupInst].push_back(*AI);
507     }
508 
509     for (DomTreeNode *C : DomN->children())
510       Visit(C, Visit);
511 
512     while (!WorkStack.empty() && WorkStack.back().Inst->getParent() == &Block)
513       WorkStack.pop_back();
514   };
515 
516   traverseBlock(HVC.DT.getRootNode(), traverseBlock);
517   assert(WorkStack.empty());
518 
519   // AddrGroups are formed.
520 
521   // Remove groups of size 1.
522   erase_if(AddrGroups, [](auto &G) { return G.second.size() == 1; });
523   // Remove groups that don't use HVX types.
524   erase_if(AddrGroups, [&](auto &G) {
525     return !llvm::any_of(
526         G.second, [&](auto &I) { return HVC.HST.isTypeForHVX(I.ValTy); });
527   });
528   // Remove groups where everything is properly aligned.
529   erase_if(AddrGroups, [&](auto &G) {
530     return llvm::all_of(G.second,
531                         [&](auto &I) { return I.HaveAlign >= I.NeedAlign; });
532   });
533 
534   return !AddrGroups.empty();
535 }
536 
537 auto AlignVectors::createLoadGroups(const AddrList &Group) const -> MoveList {
538   // Form load groups.
539   // To avoid complications with moving code across basic blocks, only form
540   // groups that are contained within a single basic block.
541 
542   auto getUpwardDeps = [](Instruction *In, Instruction *Base) {
543     BasicBlock *Parent = Base->getParent();
544     assert(In->getParent() == Parent &&
545            "Base and In should be in the same block");
546     assert(Base->comesBefore(In) && "Base should come before In");
547 
548     DepList Deps;
549     std::deque<Instruction *> WorkQ = {In};
550     while (!WorkQ.empty()) {
551       Instruction *D = WorkQ.front();
552       WorkQ.pop_front();
553       Deps.insert(D);
554       for (Value *Op : D->operands()) {
555         if (auto *I = dyn_cast<Instruction>(Op)) {
556           if (I->getParent() == Parent && Base->comesBefore(I))
557             WorkQ.push_back(I);
558         }
559       }
560     }
561     return Deps;
562   };
563 
564   auto tryAddTo = [&](const AddrInfo &Info, MoveGroup &Move) {
565     assert(!Move.Main.empty() && "Move group should have non-empty Main");
566     // Don't mix HVX and non-HVX instructions.
567     if (Move.IsHvx != isHvx(Info))
568       return false;
569     // Leading instruction in the load group.
570     Instruction *Base = Move.Main.front();
571     if (Base->getParent() != Info.Inst->getParent())
572       return false;
573 
574     auto isSafeToMoveToBase = [&](const Instruction *I) {
575       return HVC.isSafeToMoveBeforeInBB(*I, Base->getIterator());
576     };
577     DepList Deps = getUpwardDeps(Info.Inst, Base);
578     if (!llvm::all_of(Deps, isSafeToMoveToBase))
579       return false;
580 
581     // The dependencies will be moved together with the load, so make sure
582     // that none of them could be moved independently in another group.
583     Deps.erase(Info.Inst);
584     auto inAddrMap = [&](Instruction *I) { return AddrGroups.count(I) > 0; };
585     if (llvm::any_of(Deps, inAddrMap))
586       return false;
587     Move.Main.push_back(Info.Inst);
588     Move.Deps.insert(Move.Deps.end(), Deps.begin(), Deps.end());
589     return true;
590   };
591 
592   MoveList LoadGroups;
593 
594   for (const AddrInfo &Info : Group) {
595     if (!Info.Inst->mayReadFromMemory())
596       continue;
597     if (LoadGroups.empty() || !tryAddTo(Info, LoadGroups.back()))
598       LoadGroups.emplace_back(Info, Group.front().Inst, isHvx(Info), true);
599   }
600 
601   // Erase singleton groups.
602   erase_if(LoadGroups, [](const MoveGroup &G) { return G.Main.size() <= 1; });
603   return LoadGroups;
604 }
605 
606 auto AlignVectors::createStoreGroups(const AddrList &Group) const -> MoveList {
607   // Form store groups.
608   // To avoid complications with moving code across basic blocks, only form
609   // groups that are contained within a single basic block.
610 
611   auto tryAddTo = [&](const AddrInfo &Info, MoveGroup &Move) {
612     assert(!Move.Main.empty() && "Move group should have non-empty Main");
613     // For stores with return values we'd have to collect downward depenencies.
614     // There are no such stores that we handle at the moment, so omit that.
615     assert(Info.Inst->getType()->isVoidTy() &&
616            "Not handling stores with return values");
617     // Don't mix HVX and non-HVX instructions.
618     if (Move.IsHvx != isHvx(Info))
619       return false;
620     // For stores we need to be careful whether it's safe to move them.
621     // Stores that are otherwise safe to move together may not appear safe
622     // to move over one another (i.e. isSafeToMoveBefore may return false).
623     Instruction *Base = Move.Main.front();
624     if (Base->getParent() != Info.Inst->getParent())
625       return false;
626     if (!HVC.isSafeToMoveBeforeInBB(*Info.Inst, Base->getIterator(), Move.Main))
627       return false;
628     Move.Main.push_back(Info.Inst);
629     return true;
630   };
631 
632   MoveList StoreGroups;
633 
634   for (auto I = Group.rbegin(), E = Group.rend(); I != E; ++I) {
635     const AddrInfo &Info = *I;
636     if (!Info.Inst->mayWriteToMemory())
637       continue;
638     if (StoreGroups.empty() || !tryAddTo(Info, StoreGroups.back()))
639       StoreGroups.emplace_back(Info, Group.front().Inst, isHvx(Info), false);
640   }
641 
642   // Erase singleton groups.
643   erase_if(StoreGroups, [](const MoveGroup &G) { return G.Main.size() <= 1; });
644   return StoreGroups;
645 }
646 
647 auto AlignVectors::move(const MoveGroup &Move) const -> bool {
648   assert(!Move.Main.empty() && "Move group should have non-empty Main");
649   Instruction *Where = Move.Main.front();
650 
651   if (Move.IsLoad) {
652     // Move all deps to before Where, keeping order.
653     for (Instruction *D : Move.Deps)
654       D->moveBefore(Where);
655     // Move all main instructions to after Where, keeping order.
656     ArrayRef<Instruction *> Main(Move.Main);
657     for (Instruction *M : Main.drop_front(1)) {
658       M->moveAfter(Where);
659       Where = M;
660     }
661   } else {
662     // NOTE: Deps are empty for "store" groups. If they need to be
663     // non-empty, decide on the order.
664     assert(Move.Deps.empty());
665     // Move all main instructions to before Where, inverting order.
666     ArrayRef<Instruction *> Main(Move.Main);
667     for (Instruction *M : Main.drop_front(1)) {
668       M->moveBefore(Where);
669       Where = M;
670     }
671   }
672 
673   return Move.Main.size() + Move.Deps.size() > 1;
674 }
675 
676 auto AlignVectors::realignGroup(const MoveGroup &Move) const -> bool {
677   // Return the element with the maximum alignment from Range,
678   // where GetValue obtains the value to compare from an element.
679   auto getMaxOf = [](auto Range, auto GetValue) {
680     return *std::max_element(
681         Range.begin(), Range.end(),
682         [&GetValue](auto &A, auto &B) { return GetValue(A) < GetValue(B); });
683   };
684 
685   const AddrList &BaseInfos = AddrGroups.at(Move.Base);
686 
687   // Conceptually, there is a vector of N bytes covering the addresses
688   // starting from the minimum offset (i.e. Base.Addr+Start). This vector
689   // represents a contiguous memory region that spans all accessed memory
690   // locations.
691   // The correspondence between loaded or stored values will be expressed
692   // in terms of this vector. For example, the 0th element of the vector
693   // from the Base address info will start at byte Start from the beginning
694   // of this conceptual vector.
695   //
696   // This vector will be loaded/stored starting at the nearest down-aligned
697   // address and the amount od the down-alignment will be AlignVal:
698   //   valign(load_vector(align_down(Base+Start)), AlignVal)
699 
700   std::set<Instruction *> TestSet(Move.Main.begin(), Move.Main.end());
701   AddrList MoveInfos;
702   llvm::copy_if(
703       BaseInfos, std::back_inserter(MoveInfos),
704       [&TestSet](const AddrInfo &AI) { return TestSet.count(AI.Inst); });
705 
706   // Maximum alignment present in the whole address group.
707   const AddrInfo &WithMaxAlign =
708       getMaxOf(BaseInfos, [](const AddrInfo &AI) { return AI.HaveAlign; });
709   Align MaxGiven = WithMaxAlign.HaveAlign;
710 
711   // Minimum alignment present in the move address group.
712   const AddrInfo &WithMinOffset =
713       getMaxOf(MoveInfos, [](const AddrInfo &AI) { return -AI.Offset; });
714 
715   const AddrInfo &WithMaxNeeded =
716       getMaxOf(MoveInfos, [](const AddrInfo &AI) { return AI.NeedAlign; });
717   Align MinNeeded = WithMaxNeeded.NeedAlign;
718 
719   // Set the builder at the top instruction in the move group.
720   Instruction *TopIn = Move.IsLoad ? Move.Main.front() : Move.Main.back();
721   IRBuilder<> Builder(TopIn);
722   Value *AlignAddr = nullptr; // Actual aligned address.
723   Value *AlignVal = nullptr;  // Right-shift amount (for valign).
724 
725   if (MinNeeded <= MaxGiven) {
726     int Start = WithMinOffset.Offset;
727     int OffAtMax = WithMaxAlign.Offset;
728     // Shift the offset of the maximally aligned instruction (OffAtMax)
729     // back by just enough multiples of the required alignment to cover the
730     // distance from Start to OffAtMax.
731     // Calculate the address adjustment amount based on the address with the
732     // maximum alignment. This is to allow a simple gep instruction instead
733     // of potential bitcasts to i8*.
734     int Adjust = -alignTo(OffAtMax - Start, MinNeeded.value());
735     AlignAddr = createAdjustedPointer(Builder, WithMaxAlign.Addr,
736                                       WithMaxAlign.ValTy, Adjust);
737     int Diff = Start - (OffAtMax + Adjust);
738     AlignVal = HVC.getConstInt(Diff);
739     // Sanity.
740     assert(Diff >= 0);
741     assert(static_cast<decltype(MinNeeded.value())>(Diff) < MinNeeded.value());
742   } else {
743     // WithMinOffset is the lowest address in the group,
744     //   WithMinOffset.Addr = Base+Start.
745     // Align instructions for both HVX (V6_valign) and scalar (S2_valignrb)
746     // mask off unnecessary bits, so it's ok to just the original pointer as
747     // the alignment amount.
748     // Do an explicit down-alignment of the address to avoid creating an
749     // aligned instruction with an address that is not really aligned.
750     AlignAddr = createAlignedPointer(Builder, WithMinOffset.Addr,
751                                      WithMinOffset.ValTy, MinNeeded.value());
752     AlignVal = Builder.CreatePtrToInt(WithMinOffset.Addr, HVC.getIntTy());
753   }
754 
755   ByteSpan VSpan;
756   for (const AddrInfo &AI : MoveInfos) {
757     VSpan.Blocks.emplace_back(AI.Inst, HVC.getSizeOf(AI.ValTy),
758                               AI.Offset - WithMinOffset.Offset);
759   }
760 
761   // The aligned loads/stores will use blocks that are either scalars,
762   // or HVX vectors. Let "sector" be the unified term for such a block.
763   // blend(scalar, vector) -> sector...
764   int ScLen = Move.IsHvx ? HVC.HST.getVectorLength()
765                          : std::max<int>(MinNeeded.value(), 4);
766   assert(!Move.IsHvx || ScLen == 64 || ScLen == 128);
767   assert(Move.IsHvx || ScLen == 4 || ScLen == 8);
768 
769   Type *SecTy = HVC.getByteTy(ScLen);
770   int NumSectors = (VSpan.extent() + ScLen - 1) / ScLen;
771 
772   if (Move.IsLoad) {
773     ByteSpan ASpan;
774     auto *True = HVC.getFullValue(HVC.getBoolTy(ScLen));
775     auto *Undef = UndefValue::get(SecTy);
776 
777     for (int i = 0; i != NumSectors + 1; ++i) {
778       Value *Ptr = createAdjustedPointer(Builder, AlignAddr, SecTy, i * ScLen);
779       // FIXME: generate a predicated load?
780       Value *Load = createAlignedLoad(Builder, SecTy, Ptr, ScLen, True, Undef);
781       ASpan.Blocks.emplace_back(Load, ScLen, i * ScLen);
782     }
783 
784     for (int j = 0; j != NumSectors; ++j) {
785       ASpan[j].Seg.Val = HVC.vralignb(Builder, ASpan[j].Seg.Val,
786                                       ASpan[j + 1].Seg.Val, AlignVal);
787     }
788 
789     for (ByteSpan::Block &B : VSpan) {
790       ByteSpan Section = ASpan.section(B.Pos, B.Seg.Size).normalize();
791       Value *Accum = UndefValue::get(HVC.getByteTy(B.Seg.Size));
792       for (ByteSpan::Block &S : Section) {
793         Value *Pay = HVC.vbytes(Builder, getPayload(S.Seg.Val));
794         Accum =
795             HVC.insertb(Builder, Accum, Pay, S.Seg.Start, S.Seg.Size, S.Pos);
796       }
797       // Instead of casting everything to bytes for the vselect, cast to the
798       // original value type. This will avoid complications with casting masks.
799       // For example, in cases when the original mask applied to i32, it could
800       // be converted to a mask applicable to i8 via pred_typecast intrinsic,
801       // but if the mask is not exactly of HVX length, extra handling would be
802       // needed to make it work.
803       Type *ValTy = getPayload(B.Seg.Val)->getType();
804       Value *Cast = Builder.CreateBitCast(Accum, ValTy);
805       Value *Sel = Builder.CreateSelect(getMask(B.Seg.Val), Cast,
806                                         getPassThrough(B.Seg.Val));
807       B.Seg.Val->replaceAllUsesWith(Sel);
808     }
809   } else {
810     // Stores.
811     ByteSpan ASpanV, ASpanM;
812 
813     for (int i = -1; i != NumSectors; ++i) {
814       ByteSpan Section = VSpan.section(i * ScLen, ScLen).normalize();
815       Value *AccumV = UndefValue::get(SecTy);
816       Value *AccumM = HVC.getNullValue(SecTy);
817       for (ByteSpan::Block &S : Section) {
818         Value *Pay = getPayload(S.Seg.Val);
819         Value *Mask = HVC.rescale(Builder, getMask(S.Seg.Val), Pay->getType(),
820                                   HVC.getByteTy());
821         AccumM = HVC.insertb(Builder, AccumM, HVC.vbytes(Builder, Mask),
822                              S.Seg.Start, S.Seg.Size, S.Pos);
823         AccumV = HVC.insertb(Builder, AccumV, HVC.vbytes(Builder, Pay),
824                              S.Seg.Start, S.Seg.Size, S.Pos);
825       }
826       ASpanV.Blocks.emplace_back(AccumV, ScLen, i * ScLen);
827       ASpanM.Blocks.emplace_back(AccumM, ScLen, i * ScLen);
828     }
829 
830     // vlalign
831     for (int j = 1; j != NumSectors + 1; ++j) {
832       ASpanV[j - 1].Seg.Val = HVC.vlalignb(Builder, ASpanV[j - 1].Seg.Val,
833                                            ASpanV[j].Seg.Val, AlignVal);
834       ASpanM[j - 1].Seg.Val = HVC.vlalignb(Builder, ASpanM[j - 1].Seg.Val,
835                                            ASpanM[j].Seg.Val, AlignVal);
836     }
837 
838     for (int i = 0; i != NumSectors; ++i) {
839       Value *Ptr = createAdjustedPointer(Builder, AlignAddr, SecTy, i * ScLen);
840       Value *Val = ASpanV[i].Seg.Val;
841       Value *Mask = ASpanM[i].Seg.Val; // bytes
842       if (!HVC.isUndef(Val) && !HVC.isZero(Mask))
843         createAlignedStore(Builder, Val, Ptr, ScLen, HVC.vlsb(Builder, Mask));
844     }
845   }
846 
847   for (auto *Inst : Move.Main)
848     Inst->eraseFromParent();
849 
850   return true;
851 }
852 
853 auto AlignVectors::run() -> bool {
854   if (!createAddressGroups())
855     return false;
856 
857   bool Changed = false;
858   MoveList LoadGroups, StoreGroups;
859 
860   for (auto &G : AddrGroups) {
861     llvm::append_range(LoadGroups, createLoadGroups(G.second));
862     llvm::append_range(StoreGroups, createStoreGroups(G.second));
863   }
864 
865   for (auto &M : LoadGroups)
866     Changed |= move(M);
867   for (auto &M : StoreGroups)
868     Changed |= move(M);
869 
870   for (auto &M : LoadGroups)
871     Changed |= realignGroup(M);
872   for (auto &M : StoreGroups)
873     Changed |= realignGroup(M);
874 
875   return Changed;
876 }
877 
878 // --- End AlignVectors
879 
880 auto HexagonVectorCombine::run() -> bool {
881   if (!HST.useHVXOps())
882     return false;
883 
884   bool Changed = AlignVectors(*this).run();
885   return Changed;
886 }
887 
888 auto HexagonVectorCombine::getIntTy() const -> IntegerType * {
889   return Type::getInt32Ty(F.getContext());
890 }
891 
892 auto HexagonVectorCombine::getByteTy(int ElemCount) const -> Type * {
893   assert(ElemCount >= 0);
894   IntegerType *ByteTy = Type::getInt8Ty(F.getContext());
895   if (ElemCount == 0)
896     return ByteTy;
897   return VectorType::get(ByteTy, ElemCount, /*Scalable*/ false);
898 }
899 
900 auto HexagonVectorCombine::getBoolTy(int ElemCount) const -> Type * {
901   assert(ElemCount >= 0);
902   IntegerType *BoolTy = Type::getInt1Ty(F.getContext());
903   if (ElemCount == 0)
904     return BoolTy;
905   return VectorType::get(BoolTy, ElemCount, /*Scalable*/ false);
906 }
907 
908 auto HexagonVectorCombine::getConstInt(int Val) const -> ConstantInt * {
909   return ConstantInt::getSigned(getIntTy(), Val);
910 }
911 
912 auto HexagonVectorCombine::isZero(const Value *Val) const -> bool {
913   if (auto *C = dyn_cast<Constant>(Val))
914     return C->isZeroValue();
915   return false;
916 }
917 
918 auto HexagonVectorCombine::getIntValue(const Value *Val) const
919     -> Optional<APInt> {
920   if (auto *CI = dyn_cast<ConstantInt>(Val))
921     return CI->getValue();
922   return None;
923 }
924 
925 auto HexagonVectorCombine::isUndef(const Value *Val) const -> bool {
926   return isa<UndefValue>(Val);
927 }
928 
929 auto HexagonVectorCombine::getSizeOf(const Value *Val) const -> int {
930   return getSizeOf(Val->getType());
931 }
932 
933 auto HexagonVectorCombine::getSizeOf(const Type *Ty) const -> int {
934   return DL.getTypeStoreSize(const_cast<Type *>(Ty)).getFixedValue();
935 }
936 
937 auto HexagonVectorCombine::getTypeAlignment(Type *Ty) const -> int {
938   // The actual type may be shorter than the HVX vector, so determine
939   // the alignment based on subtarget info.
940   if (HST.isTypeForHVX(Ty))
941     return HST.getVectorLength();
942   return DL.getABITypeAlign(Ty).value();
943 }
944 
945 auto HexagonVectorCombine::getNullValue(Type *Ty) const -> Constant * {
946   assert(Ty->isIntOrIntVectorTy());
947   auto Zero = ConstantInt::get(Ty->getScalarType(), 0);
948   if (auto *VecTy = dyn_cast<VectorType>(Ty))
949     return ConstantVector::getSplat(VecTy->getElementCount(), Zero);
950   return Zero;
951 }
952 
953 auto HexagonVectorCombine::getFullValue(Type *Ty) const -> Constant * {
954   assert(Ty->isIntOrIntVectorTy());
955   auto Minus1 = ConstantInt::get(Ty->getScalarType(), -1);
956   if (auto *VecTy = dyn_cast<VectorType>(Ty))
957     return ConstantVector::getSplat(VecTy->getElementCount(), Minus1);
958   return Minus1;
959 }
960 
961 // Insert bytes [Start..Start+Length) of Src into Dst at byte Where.
962 auto HexagonVectorCombine::insertb(IRBuilder<> &Builder, Value *Dst, Value *Src,
963                                    int Start, int Length, int Where) const
964     -> Value * {
965   assert(isByteVecTy(Dst->getType()) && isByteVecTy(Src->getType()));
966   int SrcLen = getSizeOf(Src);
967   int DstLen = getSizeOf(Dst);
968   assert(0 <= Start && Start + Length <= SrcLen);
969   assert(0 <= Where && Where + Length <= DstLen);
970 
971   int P2Len = PowerOf2Ceil(SrcLen | DstLen);
972   auto *Undef = UndefValue::get(getByteTy());
973   Value *P2Src = vresize(Builder, Src, P2Len, Undef);
974   Value *P2Dst = vresize(Builder, Dst, P2Len, Undef);
975 
976   SmallVector<int, 256> SMask(P2Len);
977   for (int i = 0; i != P2Len; ++i) {
978     // If i is in [Where, Where+Length), pick Src[Start+(i-Where)].
979     // Otherwise, pick Dst[i];
980     SMask[i] =
981         (Where <= i && i < Where + Length) ? P2Len + Start + (i - Where) : i;
982   }
983 
984   Value *P2Insert = Builder.CreateShuffleVector(P2Dst, P2Src, SMask);
985   return vresize(Builder, P2Insert, DstLen, Undef);
986 }
987 
988 auto HexagonVectorCombine::vlalignb(IRBuilder<> &Builder, Value *Lo, Value *Hi,
989                                     Value *Amt) const -> Value * {
990   assert(Lo->getType() == Hi->getType() && "Argument type mismatch");
991   assert(isSectorTy(Hi->getType()));
992   if (isZero(Amt))
993     return Hi;
994   int VecLen = getSizeOf(Hi);
995   if (auto IntAmt = getIntValue(Amt))
996     return getElementRange(Builder, Lo, Hi, VecLen - IntAmt->getSExtValue(),
997                            VecLen);
998 
999   if (HST.isTypeForHVX(Hi->getType())) {
1000     int HwLen = HST.getVectorLength();
1001     assert(VecLen == HwLen && "Expecting an exact HVX type");
1002     Intrinsic::ID V6_vlalignb = HwLen == 64
1003                                     ? Intrinsic::hexagon_V6_vlalignb
1004                                     : Intrinsic::hexagon_V6_vlalignb_128B;
1005     return createHvxIntrinsic(Builder, V6_vlalignb, Hi->getType(),
1006                               {Hi, Lo, Amt});
1007   }
1008 
1009   if (VecLen == 4) {
1010     Value *Pair = concat(Builder, {Lo, Hi});
1011     Value *Shift = Builder.CreateLShr(Builder.CreateShl(Pair, Amt), 32);
1012     Value *Trunc = Builder.CreateTrunc(Shift, Type::getInt32Ty(F.getContext()));
1013     return Builder.CreateBitCast(Trunc, Hi->getType());
1014   }
1015   if (VecLen == 8) {
1016     Value *Sub = Builder.CreateSub(getConstInt(VecLen), Amt);
1017     return vralignb(Builder, Lo, Hi, Sub);
1018   }
1019   llvm_unreachable("Unexpected vector length");
1020 }
1021 
1022 auto HexagonVectorCombine::vralignb(IRBuilder<> &Builder, Value *Lo, Value *Hi,
1023                                     Value *Amt) const -> Value * {
1024   assert(Lo->getType() == Hi->getType() && "Argument type mismatch");
1025   assert(isSectorTy(Lo->getType()));
1026   if (isZero(Amt))
1027     return Lo;
1028   int VecLen = getSizeOf(Lo);
1029   if (auto IntAmt = getIntValue(Amt))
1030     return getElementRange(Builder, Lo, Hi, IntAmt->getSExtValue(), VecLen);
1031 
1032   if (HST.isTypeForHVX(Lo->getType())) {
1033     int HwLen = HST.getVectorLength();
1034     assert(VecLen == HwLen && "Expecting an exact HVX type");
1035     Intrinsic::ID V6_valignb = HwLen == 64 ? Intrinsic::hexagon_V6_valignb
1036                                            : Intrinsic::hexagon_V6_valignb_128B;
1037     return createHvxIntrinsic(Builder, V6_valignb, Lo->getType(),
1038                               {Hi, Lo, Amt});
1039   }
1040 
1041   if (VecLen == 4) {
1042     Value *Pair = concat(Builder, {Lo, Hi});
1043     Value *Shift = Builder.CreateLShr(Pair, Amt);
1044     Value *Trunc = Builder.CreateTrunc(Shift, Type::getInt32Ty(F.getContext()));
1045     return Builder.CreateBitCast(Trunc, Lo->getType());
1046   }
1047   if (VecLen == 8) {
1048     Type *Int64Ty = Type::getInt64Ty(F.getContext());
1049     Value *Lo64 = Builder.CreateBitCast(Lo, Int64Ty);
1050     Value *Hi64 = Builder.CreateBitCast(Hi, Int64Ty);
1051     Function *FI = Intrinsic::getDeclaration(F.getParent(),
1052                                              Intrinsic::hexagon_S2_valignrb);
1053     Value *Call = Builder.CreateCall(FI, {Hi64, Lo64, Amt});
1054     return Builder.CreateBitCast(Call, Lo->getType());
1055   }
1056   llvm_unreachable("Unexpected vector length");
1057 }
1058 
1059 // Concatenates a sequence of vectors of the same type.
1060 auto HexagonVectorCombine::concat(IRBuilder<> &Builder,
1061                                   ArrayRef<Value *> Vecs) const -> Value * {
1062   assert(!Vecs.empty());
1063   SmallVector<int, 256> SMask;
1064   std::vector<Value *> Work[2];
1065   int ThisW = 0, OtherW = 1;
1066 
1067   Work[ThisW].assign(Vecs.begin(), Vecs.end());
1068   while (Work[ThisW].size() > 1) {
1069     auto *Ty = cast<VectorType>(Work[ThisW].front()->getType());
1070     int ElemCount = Ty->getElementCount().getFixedValue();
1071     SMask.resize(ElemCount * 2);
1072     std::iota(SMask.begin(), SMask.end(), 0);
1073 
1074     Work[OtherW].clear();
1075     if (Work[ThisW].size() % 2 != 0)
1076       Work[ThisW].push_back(UndefValue::get(Ty));
1077     for (int i = 0, e = Work[ThisW].size(); i < e; i += 2) {
1078       Value *Joined = Builder.CreateShuffleVector(Work[ThisW][i],
1079                                                   Work[ThisW][i + 1], SMask);
1080       Work[OtherW].push_back(Joined);
1081     }
1082     std::swap(ThisW, OtherW);
1083   }
1084 
1085   // Since there may have been some undefs appended to make shuffle operands
1086   // have the same type, perform the last shuffle to only pick the original
1087   // elements.
1088   SMask.resize(Vecs.size() * getSizeOf(Vecs.front()->getType()));
1089   std::iota(SMask.begin(), SMask.end(), 0);
1090   Value *Total = Work[OtherW].front();
1091   return Builder.CreateShuffleVector(Total, UndefValue::get(Total->getType()),
1092                                      SMask);
1093 }
1094 
1095 auto HexagonVectorCombine::vresize(IRBuilder<> &Builder, Value *Val,
1096                                    int NewSize, Value *Pad) const -> Value * {
1097   assert(isa<VectorType>(Val->getType()));
1098   auto *ValTy = cast<VectorType>(Val->getType());
1099   assert(ValTy->getElementType() == Pad->getType());
1100 
1101   int CurSize = ValTy->getElementCount().getFixedValue();
1102   if (CurSize == NewSize)
1103     return Val;
1104   // Truncate?
1105   if (CurSize > NewSize)
1106     return getElementRange(Builder, Val, /*Unused*/ Val, 0, NewSize);
1107   // Extend.
1108   SmallVector<int, 128> SMask(NewSize);
1109   std::iota(SMask.begin(), SMask.begin() + CurSize, 0);
1110   std::fill(SMask.begin() + CurSize, SMask.end(), CurSize);
1111   Value *PadVec = Builder.CreateVectorSplat(CurSize, Pad);
1112   return Builder.CreateShuffleVector(Val, PadVec, SMask);
1113 }
1114 
1115 auto HexagonVectorCombine::rescale(IRBuilder<> &Builder, Value *Mask,
1116                                    Type *FromTy, Type *ToTy) const -> Value * {
1117   // Mask is a vector <N x i1>, where each element corresponds to an
1118   // element of FromTy. Remap it so that each element will correspond
1119   // to an element of ToTy.
1120   assert(isa<VectorType>(Mask->getType()));
1121 
1122   Type *FromSTy = FromTy->getScalarType();
1123   Type *ToSTy = ToTy->getScalarType();
1124   if (FromSTy == ToSTy)
1125     return Mask;
1126 
1127   int FromSize = getSizeOf(FromSTy);
1128   int ToSize = getSizeOf(ToSTy);
1129   assert(FromSize % ToSize == 0 || ToSize % FromSize == 0);
1130 
1131   auto *MaskTy = cast<VectorType>(Mask->getType());
1132   int FromCount = MaskTy->getElementCount().getFixedValue();
1133   int ToCount = (FromCount * FromSize) / ToSize;
1134   assert((FromCount * FromSize) % ToSize == 0);
1135 
1136   // Mask <N x i1> -> sext to <N x FromTy> -> bitcast to <M x ToTy> ->
1137   // -> trunc to <M x i1>.
1138   Value *Ext = Builder.CreateSExt(
1139       Mask, VectorType::get(FromSTy, FromCount, /*Scalable*/ false));
1140   Value *Cast = Builder.CreateBitCast(
1141       Ext, VectorType::get(ToSTy, ToCount, /*Scalable*/ false));
1142   return Builder.CreateTrunc(
1143       Cast, VectorType::get(getBoolTy(), ToCount, /*Scalable*/ false));
1144 }
1145 
1146 // Bitcast to bytes, and return least significant bits.
1147 auto HexagonVectorCombine::vlsb(IRBuilder<> &Builder, Value *Val) const
1148     -> Value * {
1149   Type *ScalarTy = Val->getType()->getScalarType();
1150   if (ScalarTy == getBoolTy())
1151     return Val;
1152 
1153   Value *Bytes = vbytes(Builder, Val);
1154   if (auto *VecTy = dyn_cast<VectorType>(Bytes->getType()))
1155     return Builder.CreateTrunc(Bytes, getBoolTy(getSizeOf(VecTy)));
1156   // If Bytes is a scalar (i.e. Val was a scalar byte), return i1, not
1157   // <1 x i1>.
1158   return Builder.CreateTrunc(Bytes, getBoolTy());
1159 }
1160 
1161 // Bitcast to bytes for non-bool. For bool, convert i1 -> i8.
1162 auto HexagonVectorCombine::vbytes(IRBuilder<> &Builder, Value *Val) const
1163     -> Value * {
1164   Type *ScalarTy = Val->getType()->getScalarType();
1165   if (ScalarTy == getByteTy())
1166     return Val;
1167 
1168   if (ScalarTy != getBoolTy())
1169     return Builder.CreateBitCast(Val, getByteTy(getSizeOf(Val)));
1170   // For bool, return a sext from i1 to i8.
1171   if (auto *VecTy = dyn_cast<VectorType>(Val->getType()))
1172     return Builder.CreateSExt(Val, VectorType::get(getByteTy(), VecTy));
1173   return Builder.CreateSExt(Val, getByteTy());
1174 }
1175 
1176 auto HexagonVectorCombine::createHvxIntrinsic(IRBuilder<> &Builder,
1177                                               Intrinsic::ID IntID, Type *RetTy,
1178                                               ArrayRef<Value *> Args) const
1179     -> Value * {
1180   int HwLen = HST.getVectorLength();
1181   Type *BoolTy = Type::getInt1Ty(F.getContext());
1182   Type *Int32Ty = Type::getInt32Ty(F.getContext());
1183   // HVX vector -> v16i32/v32i32
1184   // HVX vector predicate -> v512i1/v1024i1
1185   auto getTypeForIntrin = [&](Type *Ty) -> Type * {
1186     if (HST.isTypeForHVX(Ty, /*IncludeBool*/ true)) {
1187       Type *ElemTy = cast<VectorType>(Ty)->getElementType();
1188       if (ElemTy == Int32Ty)
1189         return Ty;
1190       if (ElemTy == BoolTy)
1191         return VectorType::get(BoolTy, 8 * HwLen, /*Scalable*/ false);
1192       return VectorType::get(Int32Ty, HwLen / 4, /*Scalable*/ false);
1193     }
1194     // Non-HVX type. It should be a scalar.
1195     assert(Ty == Int32Ty || Ty->isIntegerTy(64));
1196     return Ty;
1197   };
1198 
1199   auto getCast = [&](IRBuilder<> &Builder, Value *Val,
1200                      Type *DestTy) -> Value * {
1201     Type *SrcTy = Val->getType();
1202     if (SrcTy == DestTy)
1203       return Val;
1204     if (HST.isTypeForHVX(SrcTy, /*IncludeBool*/ true)) {
1205       if (cast<VectorType>(SrcTy)->getElementType() == BoolTy) {
1206         // This should take care of casts the other way too, for example
1207         // v1024i1 -> v32i1.
1208         Intrinsic::ID TC = HwLen == 64
1209                                ? Intrinsic::hexagon_V6_pred_typecast
1210                                : Intrinsic::hexagon_V6_pred_typecast_128B;
1211         Function *FI = Intrinsic::getDeclaration(F.getParent(), TC,
1212                                                  {DestTy, Val->getType()});
1213         return Builder.CreateCall(FI, {Val});
1214       }
1215       // Non-predicate HVX vector.
1216       return Builder.CreateBitCast(Val, DestTy);
1217     }
1218     // Non-HVX type. It should be a scalar, and it should already have
1219     // a valid type.
1220     llvm_unreachable("Unexpected type");
1221   };
1222 
1223   SmallVector<Value *, 4> IntOps;
1224   for (Value *A : Args)
1225     IntOps.push_back(getCast(Builder, A, getTypeForIntrin(A->getType())));
1226   Function *FI = Intrinsic::getDeclaration(F.getParent(), IntID);
1227   Value *Call = Builder.CreateCall(FI, IntOps);
1228 
1229   Type *CallTy = Call->getType();
1230   if (CallTy == RetTy)
1231     return Call;
1232   // Scalar types should have RetTy matching the call return type.
1233   assert(HST.isTypeForHVX(CallTy, /*IncludeBool*/ true));
1234   if (cast<VectorType>(CallTy)->getElementType() == BoolTy)
1235     return getCast(Builder, Call, RetTy);
1236   return Builder.CreateBitCast(Call, RetTy);
1237 }
1238 
1239 auto HexagonVectorCombine::calculatePointerDifference(Value *Ptr0,
1240                                                       Value *Ptr1) const
1241     -> Optional<int> {
1242   struct Builder : IRBuilder<> {
1243     Builder(BasicBlock *B) : IRBuilder<>(B) {}
1244     ~Builder() {
1245       for (Instruction *I : llvm::reverse(ToErase))
1246         I->eraseFromParent();
1247     }
1248     SmallVector<Instruction *, 8> ToErase;
1249   };
1250 
1251 #define CallBuilder(B, F)                                                      \
1252   [&](auto &B_) {                                                              \
1253     Value *V = B_.F;                                                           \
1254     if (auto *I = dyn_cast<Instruction>(V))                                    \
1255       B_.ToErase.push_back(I);                                                 \
1256     return V;                                                                  \
1257   }(B)
1258 
1259   auto Simplify = [&](Value *V) {
1260     if (auto *I = dyn_cast<Instruction>(V)) {
1261       SimplifyQuery Q(DL, &TLI, &DT, &AC, I);
1262       if (Value *S = SimplifyInstruction(I, Q))
1263         return S;
1264     }
1265     return V;
1266   };
1267 
1268   auto StripBitCast = [](Value *V) {
1269     while (auto *C = dyn_cast<BitCastInst>(V))
1270       V = C->getOperand(0);
1271     return V;
1272   };
1273 
1274   Ptr0 = StripBitCast(Ptr0);
1275   Ptr1 = StripBitCast(Ptr1);
1276   if (!isa<GetElementPtrInst>(Ptr0) || !isa<GetElementPtrInst>(Ptr1))
1277     return None;
1278 
1279   auto *Gep0 = cast<GetElementPtrInst>(Ptr0);
1280   auto *Gep1 = cast<GetElementPtrInst>(Ptr1);
1281   if (Gep0->getPointerOperand() != Gep1->getPointerOperand())
1282     return None;
1283 
1284   Builder B(Gep0->getParent());
1285   Value *BasePtr = Gep0->getPointerOperand();
1286   int Scale = DL.getTypeStoreSize(BasePtr->getType()->getPointerElementType());
1287 
1288   // FIXME: for now only check GEPs with a single index.
1289   if (Gep0->getNumOperands() != 2 || Gep1->getNumOperands() != 2)
1290     return None;
1291 
1292   Value *Idx0 = Gep0->getOperand(1);
1293   Value *Idx1 = Gep1->getOperand(1);
1294 
1295   // First, try to simplify the subtraction directly.
1296   if (auto *Diff = dyn_cast<ConstantInt>(
1297           Simplify(CallBuilder(B, CreateSub(Idx0, Idx1)))))
1298     return Diff->getSExtValue() * Scale;
1299 
1300   KnownBits Known0 = computeKnownBits(Idx0, DL, 0, &AC, Gep0, &DT);
1301   KnownBits Known1 = computeKnownBits(Idx1, DL, 0, &AC, Gep1, &DT);
1302   APInt Unknown = ~(Known0.Zero | Known0.One) | ~(Known1.Zero | Known1.One);
1303   if (Unknown.isAllOnesValue())
1304     return None;
1305 
1306   Value *MaskU = ConstantInt::get(Idx0->getType(), Unknown);
1307   Value *AndU0 = Simplify(CallBuilder(B, CreateAnd(Idx0, MaskU)));
1308   Value *AndU1 = Simplify(CallBuilder(B, CreateAnd(Idx1, MaskU)));
1309   Value *SubU = Simplify(CallBuilder(B, CreateSub(AndU0, AndU1)));
1310   int Diff0 = 0;
1311   if (auto *C = dyn_cast<ConstantInt>(SubU)) {
1312     Diff0 = C->getSExtValue();
1313   } else {
1314     return None;
1315   }
1316 
1317   Value *MaskK = ConstantInt::get(MaskU->getType(), ~Unknown);
1318   Value *AndK0 = Simplify(CallBuilder(B, CreateAnd(Idx0, MaskK)));
1319   Value *AndK1 = Simplify(CallBuilder(B, CreateAnd(Idx1, MaskK)));
1320   Value *SubK = Simplify(CallBuilder(B, CreateSub(AndK0, AndK1)));
1321   int Diff1 = 0;
1322   if (auto *C = dyn_cast<ConstantInt>(SubK)) {
1323     Diff1 = C->getSExtValue();
1324   } else {
1325     return None;
1326   }
1327 
1328   return (Diff0 + Diff1) * Scale;
1329 
1330 #undef CallBuilder
1331 }
1332 
1333 template <typename T>
1334 auto HexagonVectorCombine::isSafeToMoveBeforeInBB(const Instruction &In,
1335                                                   BasicBlock::const_iterator To,
1336                                                   const T &Ignore) const
1337     -> bool {
1338   auto getLocOrNone = [this](const Instruction &I) -> Optional<MemoryLocation> {
1339     if (const auto *II = dyn_cast<IntrinsicInst>(&I)) {
1340       switch (II->getIntrinsicID()) {
1341       case Intrinsic::masked_load:
1342         return MemoryLocation::getForArgument(II, 0, TLI);
1343       case Intrinsic::masked_store:
1344         return MemoryLocation::getForArgument(II, 1, TLI);
1345       }
1346     }
1347     return MemoryLocation::getOrNone(&I);
1348   };
1349 
1350   // The source and the destination must be in the same basic block.
1351   const BasicBlock &Block = *In.getParent();
1352   assert(Block.begin() == To || Block.end() == To || To->getParent() == &Block);
1353   // No PHIs.
1354   if (isa<PHINode>(In) || (To != Block.end() && isa<PHINode>(*To)))
1355     return false;
1356 
1357   if (!mayBeMemoryDependent(In))
1358     return true;
1359   bool MayWrite = In.mayWriteToMemory();
1360   auto MaybeLoc = getLocOrNone(In);
1361 
1362   auto From = In.getIterator();
1363   if (From == To)
1364     return true;
1365   bool MoveUp = (To != Block.end() && To->comesBefore(&In));
1366   auto Range =
1367       MoveUp ? std::make_pair(To, From) : std::make_pair(std::next(From), To);
1368   for (auto It = Range.first; It != Range.second; ++It) {
1369     const Instruction &I = *It;
1370     if (llvm::is_contained(Ignore, &I))
1371       continue;
1372     // Parts based on isSafeToMoveBefore from CoveMoverUtils.cpp.
1373     if (I.mayThrow())
1374       return false;
1375     if (auto *CB = dyn_cast<CallBase>(&I)) {
1376       if (!CB->hasFnAttr(Attribute::WillReturn))
1377         return false;
1378       if (!CB->hasFnAttr(Attribute::NoSync))
1379         return false;
1380     }
1381     if (I.mayReadOrWriteMemory()) {
1382       auto MaybeLocI = getLocOrNone(I);
1383       if (MayWrite || I.mayWriteToMemory()) {
1384         if (!MaybeLoc || !MaybeLocI)
1385           return false;
1386         if (!AA.isNoAlias(*MaybeLoc, *MaybeLocI))
1387           return false;
1388       }
1389     }
1390   }
1391   return true;
1392 }
1393 
1394 auto HexagonVectorCombine::isByteVecTy(Type *Ty) const -> bool {
1395   if (auto *VecTy = dyn_cast<VectorType>(Ty))
1396     return VecTy->getElementType() == getByteTy();
1397   return false;
1398 }
1399 
1400 auto HexagonVectorCombine::isSectorTy(Type *Ty) const -> bool {
1401   if (!isByteVecTy(Ty))
1402     return false;
1403   int Size = getSizeOf(Ty);
1404   if (HST.isTypeForHVX(Ty))
1405     return Size == static_cast<int>(HST.getVectorLength());
1406   return Size == 4 || Size == 8;
1407 }
1408 
1409 auto HexagonVectorCombine::getElementRange(IRBuilder<> &Builder, Value *Lo,
1410                                            Value *Hi, int Start,
1411                                            int Length) const -> Value * {
1412   assert(0 <= Start && Start < Length);
1413   SmallVector<int, 128> SMask(Length);
1414   std::iota(SMask.begin(), SMask.end(), Start);
1415   return Builder.CreateShuffleVector(Lo, Hi, SMask);
1416 }
1417 
1418 // Pass management.
1419 
1420 namespace llvm {
1421 void initializeHexagonVectorCombineLegacyPass(PassRegistry &);
1422 FunctionPass *createHexagonVectorCombineLegacyPass();
1423 } // namespace llvm
1424 
1425 namespace {
1426 class HexagonVectorCombineLegacy : public FunctionPass {
1427 public:
1428   static char ID;
1429 
1430   HexagonVectorCombineLegacy() : FunctionPass(ID) {}
1431 
1432   StringRef getPassName() const override { return "Hexagon Vector Combine"; }
1433 
1434   void getAnalysisUsage(AnalysisUsage &AU) const override {
1435     AU.setPreservesCFG();
1436     AU.addRequired<AAResultsWrapperPass>();
1437     AU.addRequired<AssumptionCacheTracker>();
1438     AU.addRequired<DominatorTreeWrapperPass>();
1439     AU.addRequired<TargetLibraryInfoWrapperPass>();
1440     AU.addRequired<TargetPassConfig>();
1441     FunctionPass::getAnalysisUsage(AU);
1442   }
1443 
1444   bool runOnFunction(Function &F) override {
1445     AliasAnalysis &AA = getAnalysis<AAResultsWrapperPass>().getAAResults();
1446     AssumptionCache &AC =
1447         getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
1448     DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1449     TargetLibraryInfo &TLI =
1450         getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
1451     auto &TM = getAnalysis<TargetPassConfig>().getTM<HexagonTargetMachine>();
1452     HexagonVectorCombine HVC(F, AA, AC, DT, TLI, TM);
1453     return HVC.run();
1454   }
1455 };
1456 } // namespace
1457 
1458 char HexagonVectorCombineLegacy::ID = 0;
1459 
1460 INITIALIZE_PASS_BEGIN(HexagonVectorCombineLegacy, DEBUG_TYPE,
1461                       "Hexagon Vector Combine", false, false)
1462 INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
1463 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
1464 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
1465 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
1466 INITIALIZE_PASS_DEPENDENCY(TargetPassConfig)
1467 INITIALIZE_PASS_END(HexagonVectorCombineLegacy, DEBUG_TYPE,
1468                     "Hexagon Vector Combine", false, false)
1469 
1470 FunctionPass *llvm::createHexagonVectorCombineLegacyPass() {
1471   return new HexagonVectorCombineLegacy();
1472 }
1473