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 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue(); 238 SmallVector<VPUser *> Users(Phi1ToMoveV->user_begin(), 239 Phi1ToMoveV->user_end()); 240 for (VPUser *U : Users) { 241 auto *UI = dyn_cast<VPRecipeBase>(U); 242 if (!UI || UI->getParent() != Then2) 243 continue; 244 for (unsigned I = 0, E = U->getNumOperands(); I != E; ++I) { 245 if (Phi1ToMoveV != U->getOperand(I)) 246 continue; 247 U->setOperand(I, PredInst1); 248 } 249 } 250 251 Phi1ToMove.moveBefore(*Merge2, Merge2->begin()); 252 } 253 254 // Finally, remove the first region. 255 for (VPBlockBase *Pred : make_early_inc_range(Region1->getPredecessors())) { 256 VPBlockUtils::disconnectBlocks(Pred, Region1); 257 VPBlockUtils::connectBlocks(Pred, MiddleBasicBlock); 258 } 259 VPBlockUtils::disconnectBlocks(Region1, MiddleBasicBlock); 260 DeletedRegions.insert(Region1); 261 } 262 263 for (VPRegionBlock *ToDelete : DeletedRegions) 264 delete ToDelete; 265 return Changed; 266 } 267