LLVM  14.0.0git
VPlanTransforms.cpp
Go to the documentation of this file.
1 //===-- VPlanTransforms.cpp - Utility VPlan to VPlan transforms -----------===//
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 implements a set of utility VPlan to VPlan transformations.
11 ///
12 //===----------------------------------------------------------------------===//
13 
14 #include "VPlanTransforms.h"
16 
17 using namespace llvm;
18 
20  Loop *OrigLoop, VPlanPtr &Plan,
22  SmallPtrSetImpl<Instruction *> &DeadInstructions, ScalarEvolution &SE) {
23 
24  auto *TopRegion = cast<VPRegionBlock>(Plan->getEntry());
25  ReversePostOrderTraversal<VPBlockBase *> RPOT(TopRegion->getEntry());
26 
27  for (VPBlockBase *Base : RPOT) {
28  // Do not widen instructions in pre-header and exit blocks.
29  if (Base->getNumPredecessors() == 0 || Base->getNumSuccessors() == 0)
30  continue;
31 
32  VPBasicBlock *VPBB = Base->getEntryBasicBlock();
33  // Introduce each ingredient into VPlan.
34  for (VPRecipeBase &Ingredient : llvm::make_early_inc_range(*VPBB)) {
35  VPValue *VPV = Ingredient.getVPSingleValue();
36  Instruction *Inst = cast<Instruction>(VPV->getUnderlyingValue());
37  if (DeadInstructions.count(Inst)) {
38  VPValue DummyValue;
39  VPV->replaceAllUsesWith(&DummyValue);
40  Ingredient.eraseFromParent();
41  continue;
42  }
43 
44  VPRecipeBase *NewRecipe = nullptr;
45  if (auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(&Ingredient)) {
46  auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
47  InductionDescriptor II = Inductions.lookup(Phi);
50  VPValue *Start = Plan->getOrAddVPValue(II.getStartValue());
51  NewRecipe = new VPWidenIntOrFpInductionRecipe(Phi, Start, nullptr);
52  } else {
53  Plan->addVPValue(Phi, VPPhi);
54  continue;
55  }
56  } else {
57  assert(isa<VPInstruction>(&Ingredient) &&
58  "only VPInstructions expected here");
59  assert(!isa<PHINode>(Inst) && "phis should be handled above");
60  // Create VPWidenMemoryInstructionRecipe for loads and stores.
61  if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
62  NewRecipe = new VPWidenMemoryInstructionRecipe(
63  *Load, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)),
64  nullptr /*Mask*/);
65  } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
66  NewRecipe = new VPWidenMemoryInstructionRecipe(
67  *Store, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)),
68  Plan->getOrAddVPValue(Store->getValueOperand()),
69  nullptr /*Mask*/);
70  } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
71  NewRecipe = new VPWidenGEPRecipe(
72  GEP, Plan->mapToVPValues(GEP->operands()), OrigLoop);
73  } else if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
74  NewRecipe = new VPWidenCallRecipe(
75  *CI, Plan->mapToVPValues(CI->arg_operands()));
76  } else if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
77  bool InvariantCond =
78  SE.isLoopInvariant(SE.getSCEV(SI->getOperand(0)), OrigLoop);
79  NewRecipe = new VPWidenSelectRecipe(
80  *SI, Plan->mapToVPValues(SI->operands()), InvariantCond);
81  } else {
82  NewRecipe =
83  new VPWidenRecipe(*Inst, Plan->mapToVPValues(Inst->operands()));
84  }
85  }
86 
87  NewRecipe->insertBefore(&Ingredient);
88  if (NewRecipe->getNumDefinedValues() == 1)
89  VPV->replaceAllUsesWith(NewRecipe->getVPSingleValue());
90  else
91  assert(NewRecipe->getNumDefinedValues() == 0 &&
92  "Only recpies with zero or one defined values expected");
93  Ingredient.eraseFromParent();
94  Plan->removeVPValueFor(Inst);
95  for (auto *Def : NewRecipe->definedValues()) {
96  Plan->addVPValue(Inst, Def);
97  }
98  }
99  }
100 }
101 
103  auto Iter = depth_first(
105  bool Changed = false;
106  // First, collect the operands of all predicated replicate recipes as seeds
107  // for sinking.
109  for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
110  for (auto &Recipe : *VPBB) {
111  auto *RepR = dyn_cast<VPReplicateRecipe>(&Recipe);
112  if (!RepR || !RepR->isPredicated())
113  continue;
114  for (VPValue *Op : RepR->operands())
115  WorkList.insert(std::make_pair(RepR->getParent(), Op));
116  }
117  }
118 
119  // Try to sink each replicate recipe in the worklist.
120  while (!WorkList.empty()) {
121  VPBasicBlock *SinkTo;
122  VPValue *C;
123  std::tie(SinkTo, C) = WorkList.pop_back_val();
124  auto *SinkCandidate = dyn_cast_or_null<VPReplicateRecipe>(C->Def);
125  if (!SinkCandidate || SinkCandidate->isUniform() ||
126  SinkCandidate->getParent() == SinkTo ||
127  SinkCandidate->mayHaveSideEffects() ||
128  SinkCandidate->mayReadOrWriteMemory())
129  continue;
130 
131  bool NeedsDuplicating = false;
132  // All recipe users of the sink candidate must be in the same block SinkTo
133  // or all users outside of SinkTo must be uniform-after-vectorization (
134  // i.e., only first lane is used) . In the latter case, we need to duplicate
135  // SinkCandidate. At the moment, we identify such UAV's by looking for the
136  // address operands of widened memory recipes.
137  auto CanSinkWithUser = [SinkTo, &NeedsDuplicating,
138  SinkCandidate](VPUser *U) {
139  auto *UI = dyn_cast<VPRecipeBase>(U);
140  if (!UI)
141  return false;
142  if (UI->getParent() == SinkTo)
143  return true;
144  auto *WidenI = dyn_cast<VPWidenMemoryInstructionRecipe>(UI);
145  if (WidenI && WidenI->getAddr() == SinkCandidate) {
146  NeedsDuplicating = true;
147  return true;
148  }
149  return false;
150  };
151  if (!all_of(SinkCandidate->users(), CanSinkWithUser))
152  continue;
153 
154  if (NeedsDuplicating) {
155  Instruction *I = cast<Instruction>(SinkCandidate->getUnderlyingValue());
156  auto *Clone =
157  new VPReplicateRecipe(I, SinkCandidate->operands(), true, false);
158  // TODO: add ".cloned" suffix to name of Clone's VPValue.
159 
160  Clone->insertBefore(SinkCandidate);
161  SmallVector<VPUser *, 4> Users(SinkCandidate->user_begin(),
162  SinkCandidate->user_end());
163  for (auto *U : Users) {
164  auto *UI = cast<VPRecipeBase>(U);
165  if (UI->getParent() == SinkTo)
166  continue;
167 
168  for (unsigned Idx = 0; Idx != UI->getNumOperands(); Idx++) {
169  if (UI->getOperand(Idx) != SinkCandidate)
170  continue;
171  UI->setOperand(Idx, Clone);
172  }
173  }
174  }
175  SinkCandidate->moveBefore(*SinkTo, SinkTo->getFirstNonPhi());
176  for (VPValue *Op : SinkCandidate->operands())
177  WorkList.insert(std::make_pair(SinkTo, Op));
178  Changed = true;
179  }
180  return Changed;
181 }
182 
183 /// If \p R is a region with a VPBranchOnMaskRecipe in the entry block, return
184 /// the mask.
186  auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
187  if (!EntryBB || EntryBB->size() != 1 ||
188  !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
189  return nullptr;
190 
191  return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
192 }
193 
194 /// If \p R is a triangle region, return the 'then' block of the triangle.
196  auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
197  if (EntryBB->getNumSuccessors() != 2)
198  return nullptr;
199 
200  auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
201  auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
202  if (!Succ0 || !Succ1)
203  return nullptr;
204 
205  if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
206  return nullptr;
207  if (Succ0->getSingleSuccessor() == Succ1)
208  return Succ0;
209  if (Succ1->getSingleSuccessor() == Succ0)
210  return Succ1;
211  return nullptr;
212 }
213 
215  SetVector<VPRegionBlock *> DeletedRegions;
216  bool Changed = false;
217 
218  // Collect region blocks to process up-front, to avoid iterator invalidation
219  // issues while merging regions.
220  SmallVector<VPRegionBlock *, 8> CandidateRegions(
221  VPBlockUtils::blocksOnly<VPRegionBlock>(depth_first(
223 
224  // Check if Base is a predicated triangle, followed by an empty block,
225  // followed by another predicate triangle. If that's the case, move the
226  // recipes from the first to the second triangle.
227  for (VPRegionBlock *Region1 : CandidateRegions) {
228  if (DeletedRegions.contains(Region1))
229  continue;
230  auto *MiddleBasicBlock =
231  dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
232  if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
233  continue;
234 
235  auto *Region2 =
236  dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
237  if (!Region2)
238  continue;
239 
240  VPValue *Mask1 = getPredicatedMask(Region1);
241  VPValue *Mask2 = getPredicatedMask(Region2);
242  if (!Mask1 || Mask1 != Mask2)
243  continue;
244  VPBasicBlock *Then1 = getPredicatedThenBlock(Region1);
245  VPBasicBlock *Then2 = getPredicatedThenBlock(Region2);
246  if (!Then1 || !Then2)
247  continue;
248 
249  assert(Mask1 && Mask2 && "both region must have conditions");
250 
251  // Note: No fusion-preventing memory dependencies are expected in either
252  // region. Such dependencies should be rejected during earlier dependence
253  // checks, which guarantee accesses can be re-ordered for vectorization.
254  //
255  // Move recipes to the successor region.
256  for (VPRecipeBase &ToMove : make_early_inc_range(reverse(*Then1)))
257  ToMove.moveBefore(*Then2, Then2->getFirstNonPhi());
258 
259  auto *Merge1 = cast<VPBasicBlock>(Then1->getSingleSuccessor());
260  auto *Merge2 = cast<VPBasicBlock>(Then2->getSingleSuccessor());
261 
262  // Move VPPredInstPHIRecipes from the merge block to the successor region's
263  // merge block. Update all users inside the successor region to use the
264  // original values.
265  for (VPRecipeBase &Phi1ToMove : make_early_inc_range(reverse(*Merge1))) {
266  VPValue *PredInst1 =
267  cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
268  VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue();
269  SmallVector<VPUser *> Users(Phi1ToMoveV->user_begin(),
270  Phi1ToMoveV->user_end());
271  for (VPUser *U : Users) {
272  auto *UI = dyn_cast<VPRecipeBase>(U);
273  if (!UI || UI->getParent() != Then2)
274  continue;
275  for (unsigned I = 0, E = U->getNumOperands(); I != E; ++I) {
276  if (Phi1ToMoveV != U->getOperand(I))
277  continue;
278  U->setOperand(I, PredInst1);
279  }
280  }
281 
282  Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
283  }
284 
285  // Finally, remove the first region.
286  for (VPBlockBase *Pred : make_early_inc_range(Region1->getPredecessors())) {
287  VPBlockUtils::disconnectBlocks(Pred, Region1);
288  VPBlockUtils::connectBlocks(Pred, MiddleBasicBlock);
289  }
290  VPBlockUtils::disconnectBlocks(Region1, MiddleBasicBlock);
291  DeletedRegions.insert(Region1);
292  }
293 
294  for (VPRegionBlock *ToDelete : DeletedRegions)
295  delete ToDelete;
296  return Changed;
297 }
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::tgtok::Def
@ Def
Definition: TGLexer.h:50
llvm::User::operands
op_range operands()
Definition: User.h:242
getPredicatedMask
VPValue * getPredicatedMask(VPRegionBlock *R)
If R is a region with a VPBranchOnMaskRecipe in the entry block, return the mask.
Definition: VPlanTransforms.cpp:185
llvm::VPBasicBlock
VPBasicBlock serves as the leaf of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:1606
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:530
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
llvm::VPDef::getVPSingleValue
VPValue * getVPSingleValue()
Returns the only VPValue defined by the VPDef.
Definition: VPlanValue.h:360
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:461
llvm::InductionDescriptor::IK_IntInduction
@ IK_IntInduction
Integer induction variable. Step = C.
Definition: IVDescriptors.h:274
llvm::VPlanPtr
std::unique_ptr< VPlan > VPlanPtr
Definition: VPlan.h:92
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:333
llvm::MapVector< PHINode *, InductionDescriptor >
llvm::VPWidenCallRecipe
A recipe for widening Call instructions.
Definition: VPlan.h:906
llvm::InductionDescriptor::getKind
InductionKind getKind() const
Definition: IVDescriptors.h:284
llvm::VPReplicateRecipe
VPReplicateRecipe replicates a given instruction producing multiple scalar copies of the original sca...
Definition: VPlan.h:1385
llvm::VPBlockBase
VPBlockBase is the building block of the Hierarchical Control-Flow Graph.
Definition: VPlan.h:388
llvm::all_of
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1551
llvm::InductionDescriptor
A struct for saving information about induction variables.
Definition: IVDescriptors.h:269
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::Instruction
Definition: Instruction.h:45
llvm::VPValue::replaceAllUsesWith
void replaceAllUsesWith(VPValue *New)
Definition: VPlan.cpp:1385
llvm::VPValue
Definition: VPlanValue.h:44
llvm::VPDef::getNumDefinedValues
unsigned getNumDefinedValues() const
Returns the number of values defined by the VPDef.
Definition: VPlanValue.h:387
llvm::SPII::Load
@ Load
Definition: SparcInstrInfo.h:32
llvm::SetVector::empty
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:72
llvm::VPRegionBlock
VPRegionBlock represents a collection of VPBasicBlocks and VPRegionBlocks which form a Single-Entry-S...
Definition: VPlan.h:1720
llvm::ScalarEvolution::getSCEV
const SCEV * getSCEV(Value *V)
Return a SCEV expression for the full generality of the specified expression.
Definition: ScalarEvolution.cpp:4066
llvm::InductionDescriptor::getStartValue
Value * getStartValue() const
Definition: IVDescriptors.h:283
llvm::StoreInst
An instruction for storing to memory.
Definition: Instructions.h:304
llvm::SetVector::contains
bool contains(const key_type &key) const
Check if the SetVector contains the given key.
Definition: SetVector.h:209
llvm::VPWidenRecipe
VPWidenRecipe is a recipe for producing a copy of vector type its ingredient.
Definition: VPlan.h:878
llvm::VPlanTransforms::sinkScalarOperands
static bool sinkScalarOperands(VPlan &Plan)
Definition: VPlanTransforms.cpp:102
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::VPBlockUtils::connectBlocks
static void connectBlocks(VPBlockBase *From, VPBlockBase *To)
Connect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2359
llvm::GetElementPtrInst
an instruction for type-safe pointer arithmetic to access elements of arrays and structs
Definition: Instructions.h:928
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:576
llvm::VPValue::user_end
user_iterator user_end()
Definition: VPlanValue.h:158
llvm::VPBlockUtils::disconnectBlocks
static void disconnectBlocks(VPBlockBase *From, VPBlockBase *To)
Disconnect VPBlockBases From and To bi-directionally.
Definition: VPlan.h:2370
llvm::VPlan::getEntry
VPBlockBase * getEntry()
Definition: VPlan.h:2132
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
VPlanTransforms.h
llvm::VPWidenIntOrFpInductionRecipe
A recipe for handling phi nodes of integer and floating-point inductions, producing their vector and ...
Definition: VPlan.h:1004
SI
StandardInstrumentations SI(Debug, VerifyEach)
llvm::VPWidenGEPRecipe
A recipe for handling GEP instructions.
Definition: VPlan.h:963
llvm::SPII::Store
@ Store
Definition: SparcInstrInfo.h:33
llvm::InductionDescriptor::IK_FpInduction
@ IK_FpInduction
Floating point induction variable.
Definition: IVDescriptors.h:276
llvm::SelectInst
This class represents the LLVM 'select' instruction.
Definition: Instructions.h:1738
llvm::VPWidenMemoryInstructionRecipe
A Recipe for widening load/store operations.
Definition: VPlan.h:1514
llvm::VPWidenSelectRecipe
A recipe for widening select instructions.
Definition: VPlan.h:932
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
llvm::SetVector::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::VPValue::user_begin
user_iterator user_begin()
Definition: VPlanValue.h:156
getPredicatedThenBlock
static VPBasicBlock * getPredicatedThenBlock(VPRegionBlock *R)
If R is a triangle region, return the 'then' block of the triangle.
Definition: VPlanTransforms.cpp:195
llvm::VPBlockBase::getSingleSuccessor
VPBlockBase * getSingleSuccessor() const
Definition: VPlan.h:503
llvm::MapVector::lookup
ValueT lookup(const KeyT &Key) const
Definition: MapVector.h:110
llvm::VPlanTransforms::VPInstructionsToVPRecipes
static void VPInstructionsToVPRecipes(Loop *OrigLoop, VPlanPtr &Plan, LoopVectorizationLegality::InductionList &Inductions, SmallPtrSetImpl< Instruction * > &DeadInstructions, ScalarEvolution &SE)
Replaces the VPInstructions in Plan with corresponding widen recipes.
Definition: VPlanTransforms.cpp:19
llvm::LoadInst
An instruction for reading from memory.
Definition: Instructions.h:175
llvm::ScalarEvolution::isLoopInvariant
bool isLoopInvariant(const SCEV *S, const Loop *L)
Return true if the value of the given SCEV is unchanging in the specified loop.
Definition: ScalarEvolution.cpp:12619
llvm::depth_first
iterator_range< df_iterator< T > > depth_first(const T &G)
Definition: DepthFirstIterator.h:229
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:321
llvm::VPRecipeBase
VPRecipeBase is a base class modeling a sequence of one or more output IR instructions.
Definition: VPlan.h:664
llvm::ReversePostOrderTraversal
Definition: PostOrderIterator.h:290
llvm::VPUser
This class augments VPValue with operands which provide the inverse def-use edges from VPValue's user...
Definition: VPlanValue.h:198
PostOrderIterator.h
Users
iv Induction Variable Users
Definition: IVUsers.cpp:52
llvm::VPDef::definedValues
ArrayRef< VPValue * > definedValues()
Returns an ArrayRef of the values defined by the VPDef.
Definition: VPlanValue.h:382
llvm::SmallPtrSetImpl< Instruction * >
llvm::getLoadStorePointerOperand
const Value * getLoadStorePointerOperand(const Value *V)
A helper function that returns the pointer operand of a load or store instruction.
Definition: Instructions.h:5301
llvm::CallInst
This class represents a function call, abstracting a target machine's calling convention.
Definition: Instructions.h:1475
GEP
Hexagon Common GEP
Definition: HexagonCommonGEP.cpp:172
llvm::VPBasicBlock::getFirstNonPhi
iterator getFirstNonPhi()
Return the position of the first non-phi node recipe in the block.
Definition: VPlan.cpp:220
llvm::VPBlockRecursiveTraversalWrapper
Helper for GraphTraits specialization that traverses through VPRegionBlocks.
Definition: VPlan.h:2012
llvm::SetVector
A vector that has set insertion semantics.
Definition: SetVector.h:40
llvm::VPlanTransforms::mergeReplicateRegions
static bool mergeReplicateRegions(VPlan &Plan)
Definition: VPlanTransforms.cpp:214
llvm::VPValue::getUnderlyingValue
Value * getUnderlyingValue()
Return the underlying Value attached to this VPValue.
Definition: VPlanValue.h:84
llvm::VPlan
VPlan models a candidate for vectorization, encoding various decisions take to produce efficient outp...
Definition: VPlan.h:2068
llvm::SetVector::pop_back_val
LLVM_NODISCARD T pop_back_val()
Definition: SetVector.h:232
llvm::VPRecipeBase::insertBefore
void insertBefore(VPRecipeBase *InsertPos)
Insert an unlinked recipe into a basic block immediately before the specified recipe.
Definition: VPlan.cpp:602
llvm::sampleprof::Base
@ Base
Definition: Discriminator.h:58