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