146 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9/// \file10/// This file contains the declarations for VPlan-based SLP.11///12//===----------------------------------------------------------------------===//13 14#ifndef LLVM_TRANSFORMS_VECTORIZE_VPLANSLP_H15#define LLVM_TRANSFORMS_VECTORIZE_VPLANSLP_H16 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 22namespace llvm {23 24class VPBasicBlock;25class VPBlockBase;26class VPRegionBlock;27class VPlan;28class VPValue;29class VPInstruction;30 31class VPInterleavedAccessInfo {32 DenseMap<VPInstruction *, InterleaveGroup<VPInstruction> *>33 InterleaveGroupMap;34 35 /// Type for mapping of instruction based interleave groups to VPInstruction36 /// interleave groups37 using Old2NewTy = DenseMap<InterleaveGroup<Instruction> *,38 InterleaveGroup<VPInstruction> *>;39 40 /// Recursively \p Region and populate VPlan based interleave groups based on41 /// \p IAI.42 void visitRegion(VPRegionBlock *Region, Old2NewTy &Old2New,43 InterleavedAccessInfo &IAI);44 /// Recursively traverse \p Block and populate VPlan based interleave groups45 /// based on \p IAI.46 void visitBlock(VPBlockBase *Block, Old2NewTy &Old2New,47 InterleavedAccessInfo &IAI);48 49public:50 LLVM_ABI_FOR_TEST VPInterleavedAccessInfo(VPlan &Plan,51 InterleavedAccessInfo &IAI);52 VPInterleavedAccessInfo(const VPInterleavedAccessInfo &) = delete;53 VPInterleavedAccessInfo &operator=(const VPInterleavedAccessInfo &) = delete;54 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> *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 combined73/// VPInstructions.74class 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 are83 /// 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 = std::pair<VPInstruction *, SmallVector<VPValue *, 4>>;93 94 // Input operand bundles for the current multi node. Each multi node operand95 // bundle contains values not matching the multi node's opcode. They will96 // be reordered in reorderMultiNodeOps, once we completed building a97 // multi node.98 SmallVector<MultiNodeOpTy, 4> MultiNodeOps;99 100 /// Indicates whether we are building a multi node currently.101 bool MultiNodeActive = false;102 103 /// Check if we can vectorize Operands together.104 bool areVectorizable(ArrayRef<VPValue *> Operands) const;105 106 /// Add combined instruction \p New for the bundle \p Operands.107 void addCombined(ArrayRef<VPValue *> Operands, VPInstruction *New);108 109 /// Indicate we hit a bundle we failed to combine. Returns nullptr for now.110 VPInstruction *markFailed();111 112 /// Reorder operands in the multi node to maximize sequential memory access113 /// and commutative operations.114 SmallVector<MultiNodeOpTy, 4> reorderMultiNodeOps();115 116 /// Choose the best candidate to use for the lane after \p Last. The set of117 /// candidates to choose from are values with an opcode matching \p Last's118 /// or loads consecutive to \p Last.119 std::pair<OpMode, VPValue *> getBest(OpMode Mode, VPValue *Last,120 SmallPtrSetImpl<VPValue *> &Candidates,121 VPInterleavedAccessInfo &IAI);122 123#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)124 /// Print bundle \p Values to dbgs().125 void dumpBundle(ArrayRef<VPValue *> Values);126#endif127 128public:129 VPlanSlp(VPInterleavedAccessInfo &IAI, VPBasicBlock &BB) : IAI(IAI), BB(BB) {}130 131 ~VPlanSlp() = default;132 133 /// Tries to build an SLP tree rooted at \p Operands and returns a134 /// VPInstruction combining \p Operands, if they can be combined.135 LLVM_ABI_FOR_TEST VPInstruction *buildGraph(ArrayRef<VPValue *> Operands);136 137 /// Return the width of the widest combined bundle in bits.138 unsigned getWidestBundleBits() const { return WidestBundleBits; }139 140 /// Return true if all visited instruction can be combined.141 bool isCompletelySLP() const { return CompletelySLP; }142};143} // end namespace llvm144 145#endif // LLVM_TRANSFORMS_VECTORIZE_VPLAN_H146