llvm/lib/Transforms/Vectorize/VPlanTransforms.cpp

   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"
  15 #include "llvm/ADT/PostOrderIterator.h"
  16
  17 using namespace llvm;
  18
  19 void VPlanTransforms::VPInstructionsToVPRecipes(
  20     Loop *OrigLoop, VPlanPtr &Plan,
  21     LoopVectorizationLegality::InductionList &Inductions,
  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 (auto I = VPBB->begin(), E = VPBB->end(); I != E;) {
  35       VPRecipeBase *Ingredient = &*I++;
  36       VPValue *VPV = Ingredient->getVPSingleValue();
  37       Instruction *Inst = cast<Instruction>(VPV->getUnderlyingValue());
  38       if (DeadInstructions.count(Inst)) {
  39         VPValue DummyValue;
  40         VPV->replaceAllUsesWith(&DummyValue);
  41         Ingredient->eraseFromParent();
  42         continue;
  43       }
  44
  45       VPRecipeBase *NewRecipe = nullptr;
  46       if (auto *VPPhi = dyn_cast<VPWidenPHIRecipe>(Ingredient)) {
  47         auto *Phi = cast<PHINode>(VPPhi->getUnderlyingValue());
  48         InductionDescriptor II = Inductions.lookup(Phi);
  49         if (II.getKind() == InductionDescriptor::IK_IntInduction ||
  50             II.getKind() == InductionDescriptor::IK_FpInduction) {
  51           VPValue *Start = Plan->getOrAddVPValue(II.getStartValue());
  52           NewRecipe = new VPWidenIntOrFpInductionRecipe(Phi, Start, nullptr);
  53         } else {
  54           Plan->addVPValue(Phi, VPPhi);
  55           continue;
  56         }
  57       } else {
  58         assert(isa<VPInstruction>(Ingredient) &&
  59                "only VPInstructions expected here");
  60         assert(!isa<PHINode>(Inst) && "phis should be handled above");
  61         // Create VPWidenMemoryInstructionRecipe for loads and stores.
  62         if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
  63           NewRecipe = new VPWidenMemoryInstructionRecipe(
  64               *Load, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)),
  65               nullptr /*Mask*/);
  66         } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) {
  67           NewRecipe = new VPWidenMemoryInstructionRecipe(
  68               *Store, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)),
  69               Plan->getOrAddVPValue(Store->getValueOperand()),
  70               nullptr /*Mask*/);
  71         } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) {
  72           NewRecipe = new VPWidenGEPRecipe(
  73               GEP, Plan->mapToVPValues(GEP->operands()), OrigLoop);
  74         } else if (CallInst *CI = dyn_cast<CallInst>(Inst)) {
  75           NewRecipe = new VPWidenCallRecipe(
  76               *CI, Plan->mapToVPValues(CI->arg_operands()));
  77         } else if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) {
  78           bool InvariantCond =
  79               SE.isLoopInvariant(SE.getSCEV(SI->getOperand(0)), OrigLoop);
  80           NewRecipe = new VPWidenSelectRecipe(
  81               *SI, Plan->mapToVPValues(SI->operands()), InvariantCond);
  82         } else {
  83           NewRecipe =
  84               new VPWidenRecipe(*Inst, Plan->mapToVPValues(Inst->operands()));
  85         }
  86       }
  87
  88       NewRecipe->insertBefore(Ingredient);
  89       if (NewRecipe->getNumDefinedValues() == 1)
  90         VPV->replaceAllUsesWith(NewRecipe->getVPSingleValue());
  91       else
  92         assert(NewRecipe->getNumDefinedValues() == 0 &&
  93                "Only recpies with zero or one defined values expected");
  94       Ingredient->eraseFromParent();
  95       Plan->removeVPValueFor(Inst);
  96       for (auto *Def : NewRecipe->definedValues()) {
  97         Plan->addVPValue(Inst, Def);
  98       }
  99     }
 100   }
 101 }
 102
 103 bool VPlanTransforms::sinkScalarOperands(VPlan &Plan) {
 104   auto Iter = depth_first(
 105       VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry()));
 106   bool Changed = false;
 107   // First, collect the operands of all predicated replicate recipes as seeds
 108   // for sinking.
 109   SetVector<VPValue *> WorkList;
 110   for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) {
 111     for (auto &Recipe : *VPBB) {
 112       auto *RepR = dyn_cast<VPReplicateRecipe>(&Recipe);
 113       if (!RepR || !RepR->isPredicated())
 114         continue;
 115       WorkList.insert(RepR->op_begin(), RepR->op_end());
 116     }
 117   }
 118
 119   // Try to sink each replicate recipe in the worklist.
 120   while (!WorkList.empty()) {
 121     auto *C = WorkList.pop_back_val();
 122     auto *SinkCandidate = dyn_cast_or_null<VPReplicateRecipe>(C->Def);
 123     if (!SinkCandidate || SinkCandidate->isUniform())
 124       continue;
 125
 126     // All users of SinkCandidate must be in the same block in order to perform
 127     // sinking. Therefore the destination block for sinking must match the block
 128     // containing the first user.
 129     auto *FirstUser = dyn_cast<VPRecipeBase>(*SinkCandidate->user_begin());
 130     if (!FirstUser)
 131       continue;
 132     VPBasicBlock *SinkTo = FirstUser->getParent();
 133     if (SinkCandidate->getParent() == SinkTo ||
 134         SinkCandidate->mayHaveSideEffects() ||
 135         SinkCandidate->mayReadOrWriteMemory())
 136       continue;
 137
 138     // All recipe users of the sink candidate must be in the same block SinkTo.
 139     if (any_of(SinkCandidate->users(), [SinkTo](VPUser *U) {
 140           auto *UI = dyn_cast<VPRecipeBase>(U);
 141           return !UI || UI->getParent() != SinkTo;
 142         }))
 143       continue;
 144
 145     SinkCandidate->moveBefore(*SinkTo, SinkTo->getFirstNonPhi());
 146     WorkList.insert(SinkCandidate->op_begin(), SinkCandidate->op_end());
 147     Changed = true;
 148   }
 149   return Changed;
 150 }
 151
 152 /// If \p R is a region with a VPBranchOnMaskRecipe in the entry block, return
 153 /// the mask.
 154 VPValue *getPredicatedMask(VPRegionBlock *R) {
 155   auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry());
 156   if (!EntryBB || EntryBB->size() != 1 ||
 157       !isa<VPBranchOnMaskRecipe>(EntryBB->begin()))
 158     return nullptr;
 159
 160   return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0);
 161 }
 162
 163 /// If \p R is a triangle region, return the 'then' block of the triangle.
 164 static VPBasicBlock *getPredicatedThenBlock(VPRegionBlock *R) {
 165   auto *EntryBB = cast<VPBasicBlock>(R->getEntry());
 166   if (EntryBB->getNumSuccessors() != 2)
 167     return nullptr;
 168
 169   auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]);
 170   auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]);
 171   if (!Succ0 || !Succ1)
 172     return nullptr;
 173
 174   if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1)
 175     return nullptr;
 176   if (Succ0->getSingleSuccessor() == Succ1)
 177     return Succ0;
 178   if (Succ1->getSingleSuccessor() == Succ0)
 179     return Succ1;
 180   return nullptr;
 181 }
 182
 183 bool VPlanTransforms::mergeReplicateRegions(VPlan &Plan) {
 184   SetVector<VPRegionBlock *> DeletedRegions;
 185   bool Changed = false;
 186
 187   // Collect region blocks to process up-front, to avoid iterator invalidation
 188   // issues while merging regions.
 189   SmallVector<VPRegionBlock *, 8> CandidateRegions(
 190       VPBlockUtils::blocksOnly<VPRegionBlock>(depth_first(
 191           VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry()))));
 192
 193   // Check if Base is a predicated triangle, followed by an empty block,
 194   // followed by another predicate triangle. If that's the case, move the
 195   // recipes from the first to the second triangle.
 196   for (VPRegionBlock *Region1 : CandidateRegions) {
 197     if (DeletedRegions.contains(Region1))
 198       continue;
 199     auto *MiddleBasicBlock =
 200         dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor());
 201     if (!MiddleBasicBlock || !MiddleBasicBlock->empty())
 202       continue;
 203
 204     auto *Region2 =
 205         dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor());
 206     if (!Region2)
 207       continue;
 208
 209     VPValue *Mask1 = getPredicatedMask(Region1);
 210     VPValue *Mask2 = getPredicatedMask(Region2);
 211     if (!Mask1 || Mask1 != Mask2)
 212       continue;
 213     VPBasicBlock *Then1 = getPredicatedThenBlock(Region1);
 214     VPBasicBlock *Then2 = getPredicatedThenBlock(Region2);
 215     if (!Then1 || !Then2)
 216       continue;
 217
 218     assert(Mask1 && Mask2 && "both region must have conditions");
 219
 220     // Note: No fusion-preventing memory dependencies are expected in either
 221     // region. Such dependencies should be rejected during earlier dependence
 222     // checks, which guarantee accesses can be re-ordered for vectorization.
 223     //
 224     // Move recipes to the successor region.
 225     for (VPRecipeBase &ToMove : make_early_inc_range(reverse(*Then1)))
 226       ToMove.moveBefore(*Then2, Then2->getFirstNonPhi());
 227
 228     auto *Merge1 = cast<VPBasicBlock>(Then1->getSingleSuccessor());
 229     auto *Merge2 = cast<VPBasicBlock>(Then2->getSingleSuccessor());
 230
 231     // Move VPPredInstPHIRecipes from the merge block to the successor region's
 232     // merge block. Update all users inside the successor region to use the
 233     // original values.
 234     for (VPRecipeBase &Phi1ToMove : make_early_inc_range(reverse(*Merge1))) {
 235       VPValue *PredInst1 =
 236           cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0);
 237       for (VPUser *U : Phi1ToMove.getVPSingleValue()->users()) {
 238         auto *UI = dyn_cast<VPRecipeBase>(U);
 239         if (!UI || UI->getParent() != Then2)
 240           continue;
 241         for (unsigned I = 0, E = U->getNumOperands(); I != E; ++I) {
 242           if (Phi1ToMove.getVPSingleValue() != U->getOperand(I))
 243             continue;
 244           U->setOperand(I, PredInst1);
 245         }
 246       }
 247
 248       Phi1ToMove.moveBefore(*Merge2, Merge2->begin());
 249     }
 250
 251     // Finally, remove the first region.
 252     for (VPBlockBase *Pred : make_early_inc_range(Region1->getPredecessors())) {
 253       VPBlockUtils::disconnectBlocks(Pred, Region1);
 254       VPBlockUtils::connectBlocks(Pred, MiddleBasicBlock);
 255     }
 256     VPBlockUtils::disconnectBlocks(Region1, MiddleBasicBlock);
 257     DeletedRegions.insert(Region1);
 258   }
 259
 260   for (VPRegionBlock *ToDelete : DeletedRegions)
 261     delete ToDelete;
 262   return Changed;
 263 }