1 //===- VPlan.h - VPlan-based SLP ------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 /// \file 10 /// This file contains the declarations for VPlan-based SLP. 11 /// 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANSLP_H 15 #define LLVM_TRANSFORMS_VECTORIZE_VPLANSLP_H 16 17 #include "llvm/ADT/DenseMap.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/Analysis/VectorUtils.h" 21 22 namespace llvm { 23 24 class VPBasicBlock; 25 class VPBlockBase; 26 class VPRegionBlock; 27 class VPlan; 28 class VPValue; 29 class VPInstruction; 30 31 class VPInterleavedAccessInfo { 32 DenseMap<VPInstruction *, InterleaveGroup<VPInstruction> *> 33 InterleaveGroupMap; 34 35 /// Type for mapping of instruction based interleave groups to VPInstruction 36 /// interleave groups 37 using Old2NewTy = DenseMap<InterleaveGroup<Instruction> *, 38 InterleaveGroup<VPInstruction> *>; 39 40 /// Recursively \p Region and populate VPlan based interleave groups based on 41 /// \p IAI. 42 void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New, 43 InterleavedAccessInfo &IAI); 44 /// Recursively traverse \p Block and populate VPlan based interleave groups 45 /// based on \p IAI. 46 void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New, 47 InterleavedAccessInfo &IAI); 48 49 public: 50 LLVM_ABI_FOR_TEST VPInterleavedAccessInfo(VPlan &Plan, 51 InterleavedAccessInfo &IAI); 52 VPInterleavedAccessInfo(const VPInterleavedAccessInfo &) = delete; 53 VPInterleavedAccessInfo &operator=(const VPInterleavedAccessInfo &) = delete; 54 ~VPInterleavedAccessInfo()55 ~VPInterleavedAccessInfo() { 56 // Avoid releasing a pointer twice. 57 SmallPtrSet<InterleaveGroup<VPInstruction> *, 4> DelSet( 58 llvm::from_range, llvm::make_second_range(InterleaveGroupMap)); 59 for (auto *Ptr : DelSet) 60 delete Ptr; 61 } 62 63 /// Get the interleave group that \p Instr belongs to. 64 /// 65 /// \returns nullptr if doesn't have such group. 66 InterleaveGroup<VPInstruction> * getInterleaveGroup(VPInstruction * Instr)67 getInterleaveGroup(VPInstruction *Instr) const { 68 return InterleaveGroupMap.lookup(Instr); 69 } 70 }; 71 72 /// Class that maps (parts of) an existing VPlan to trees of combined 73 /// VPInstructions. 74 class VPlanSlp { 75 enum class OpMode { Failed, Load, Opcode }; 76 77 /// Mapping of values in the original VPlan to a combined VPInstruction. 78 DenseMap<SmallVector<VPValue *, 4>, VPInstruction *> BundleToCombined; 79 80 VPInterleavedAccessInfo &IAI; 81 82 /// Basic block to operate on. For now, only instructions in a single BB are 83 /// considered. 84 const VPBasicBlock &BB; 85 86 /// Indicates whether we managed to combine all visited instructions or not. 87 bool CompletelySLP = true; 88 89 /// Width of the widest combined bundle in bits. 90 unsigned WidestBundleBits = 0; 91 92 using MultiNodeOpTy = 93 typename std::pair<VPInstruction *, SmallVector<VPValue *, 4>>; 94 95 // Input operand bundles for the current multi node. Each multi node operand 96 // bundle contains values not matching the multi node's opcode. They will 97 // be reordered in reorderMultiNodeOps, once we completed building a 98 // multi node. 99 SmallVector<MultiNodeOpTy, 4> MultiNodeOps; 100 101 /// Indicates whether we are building a multi node currently. 102 bool MultiNodeActive = false; 103 104 /// Check if we can vectorize Operands together. 105 bool areVectorizable(ArrayRef<VPValue *> Operands) const; 106 107 /// Add combined instruction \p New for the bundle \p Operands. 108 void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New); 109 110 /// Indicate we hit a bundle we failed to combine. Returns nullptr for now. 111 VPInstruction *markFailed(); 112 113 /// Reorder operands in the multi node to maximize sequential memory access 114 /// and commutative operations. 115 SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps(); 116 117 /// Choose the best candidate to use for the lane after \p Last. The set of 118 /// candidates to choose from are values with an opcode matching \p Last's 119 /// or loads consecutive to \p Last. 120 std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last, 121 SmallPtrSetImpl<VPValue *> &Candidates, 122 VPInterleavedAccessInfo &IAI); 123 124 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 125 /// Print bundle \p Values to dbgs(). 126 void dumpBundle(ArrayRef<VPValue *> Values); 127 #endif 128 129 public: VPlanSlp(VPInterleavedAccessInfo & IAI,VPBasicBlock & BB)130 VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {} 131 132 ~VPlanSlp() = default; 133 134 /// Tries to build an SLP tree rooted at \p Operands and returns a 135 /// VPInstruction combining \p Operands, if they can be combined. 136 LLVM_ABI_FOR_TEST VPInstruction *buildGraph(ArrayRef<VPValue *> Operands); 137 138 /// Return the width of the widest combined bundle in bits. getWidestBundleBits()139 unsigned getWidestBundleBits() const { return WidestBundleBits; } 140 141 /// Return true if all visited instruction can be combined. isCompletelySLP()142 bool isCompletelySLP() const { return CompletelySLP; } 143 }; 144 } // end namespace llvm 145 146 #endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H 147