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 #include "llvm/ADT/SetVector.h" 17 #include "llvm/Analysis/IVDescriptors.h" 18 19 using namespace llvm; 20 21 void VPlanTransforms::VPInstructionsToVPRecipes( 22 Loop *OrigLoop, VPlanPtr &Plan, 23 function_ref<const InductionDescriptor *(PHINode *)> 24 GetIntOrFpInductionDescriptor, 25 SmallPtrSetImpl<Instruction *> &DeadInstructions, ScalarEvolution &SE) { 26 27 ReversePostOrderTraversal<VPBlockRecursiveTraversalWrapper<VPBlockBase *>> 28 RPOT(Plan->getEntry()); 29 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT)) { 30 VPRecipeBase *Term = VPBB->getTerminator(); 31 auto EndIter = Term ? Term->getIterator() : VPBB->end(); 32 // Introduce each ingredient into VPlan. 33 for (VPRecipeBase &Ingredient : 34 make_early_inc_range(make_range(VPBB->begin(), EndIter))) { 35 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 if (const auto *II = GetIntOrFpInductionDescriptor(Phi)) { 49 VPValue *Start = Plan->getOrAddVPValue(II->getStartValue()); 50 VPValue *Step = 51 vputils::getOrCreateVPValueForSCEVExpr(*Plan, II->getStep(), SE); 52 NewRecipe = 53 new VPWidenIntOrFpInductionRecipe(Phi, Start, Step, *II, true); 54 } else { 55 Plan->addVPValue(Phi, VPPhi); 56 continue; 57 } 58 } else { 59 assert(isa<VPInstruction>(&Ingredient) && 60 "only VPInstructions expected here"); 61 assert(!isa<PHINode>(Inst) && "phis should be handled above"); 62 // Create VPWidenMemoryInstructionRecipe for loads and stores. 63 if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) { 64 NewRecipe = new VPWidenMemoryInstructionRecipe( 65 *Load, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)), 66 nullptr /*Mask*/, false /*Consecutive*/, false /*Reverse*/); 67 } else if (StoreInst *Store = dyn_cast<StoreInst>(Inst)) { 68 NewRecipe = new VPWidenMemoryInstructionRecipe( 69 *Store, Plan->getOrAddVPValue(getLoadStorePointerOperand(Inst)), 70 Plan->getOrAddVPValue(Store->getValueOperand()), nullptr /*Mask*/, 71 false /*Consecutive*/, false /*Reverse*/); 72 } else if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Inst)) { 73 NewRecipe = new VPWidenGEPRecipe( 74 GEP, Plan->mapToVPValues(GEP->operands()), OrigLoop); 75 } else if (CallInst *CI = dyn_cast<CallInst>(Inst)) { 76 NewRecipe = 77 new VPWidenCallRecipe(*CI, Plan->mapToVPValues(CI->args())); 78 } else if (SelectInst *SI = dyn_cast<SelectInst>(Inst)) { 79 bool InvariantCond = 80 SE.isLoopInvariant(SE.getSCEV(SI->getOperand(0)), OrigLoop); 81 NewRecipe = new VPWidenSelectRecipe( 82 *SI, Plan->mapToVPValues(SI->operands()), InvariantCond); 83 } else { 84 NewRecipe = 85 new VPWidenRecipe(*Inst, Plan->mapToVPValues(Inst->operands())); 86 } 87 } 88 89 NewRecipe->insertBefore(&Ingredient); 90 if (NewRecipe->getNumDefinedValues() == 1) 91 VPV->replaceAllUsesWith(NewRecipe->getVPSingleValue()); 92 else 93 assert(NewRecipe->getNumDefinedValues() == 0 && 94 "Only recpies with zero or one defined values expected"); 95 Ingredient.eraseFromParent(); 96 Plan->removeVPValueFor(Inst); 97 for (auto *Def : NewRecipe->definedValues()) { 98 Plan->addVPValue(Inst, Def); 99 } 100 } 101 } 102 } 103 104 bool VPlanTransforms::sinkScalarOperands(VPlan &Plan) { 105 auto Iter = depth_first( 106 VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry())); 107 bool Changed = false; 108 // First, collect the operands of all predicated replicate recipes as seeds 109 // for sinking. 110 SetVector<std::pair<VPBasicBlock *, VPValue *>> WorkList; 111 for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>(Iter)) { 112 for (auto &Recipe : *VPBB) { 113 auto *RepR = dyn_cast<VPReplicateRecipe>(&Recipe); 114 if (!RepR || !RepR->isPredicated()) 115 continue; 116 for (VPValue *Op : RepR->operands()) 117 WorkList.insert(std::make_pair(RepR->getParent(), Op)); 118 } 119 } 120 121 // Try to sink each replicate recipe in the worklist. 122 while (!WorkList.empty()) { 123 VPBasicBlock *SinkTo; 124 VPValue *C; 125 std::tie(SinkTo, C) = WorkList.pop_back_val(); 126 auto *SinkCandidate = dyn_cast_or_null<VPReplicateRecipe>(C->Def); 127 if (!SinkCandidate || SinkCandidate->isUniform() || 128 SinkCandidate->getParent() == SinkTo || 129 SinkCandidate->mayHaveSideEffects() || 130 SinkCandidate->mayReadOrWriteMemory()) 131 continue; 132 133 bool NeedsDuplicating = false; 134 // All recipe users of the sink candidate must be in the same block SinkTo 135 // or all users outside of SinkTo must be uniform-after-vectorization ( 136 // i.e., only first lane is used) . In the latter case, we need to duplicate 137 // SinkCandidate. At the moment, we identify such UAV's by looking for the 138 // address operands of widened memory recipes. 139 auto CanSinkWithUser = [SinkTo, &NeedsDuplicating, 140 SinkCandidate](VPUser *U) { 141 auto *UI = dyn_cast<VPRecipeBase>(U); 142 if (!UI) 143 return false; 144 if (UI->getParent() == SinkTo) 145 return true; 146 auto *WidenI = dyn_cast<VPWidenMemoryInstructionRecipe>(UI); 147 if (WidenI && WidenI->getAddr() == SinkCandidate) { 148 NeedsDuplicating = true; 149 return true; 150 } 151 return false; 152 }; 153 if (!all_of(SinkCandidate->users(), CanSinkWithUser)) 154 continue; 155 156 if (NeedsDuplicating) { 157 Instruction *I = cast<Instruction>(SinkCandidate->getUnderlyingValue()); 158 auto *Clone = 159 new VPReplicateRecipe(I, SinkCandidate->operands(), true, false); 160 // TODO: add ".cloned" suffix to name of Clone's VPValue. 161 162 Clone->insertBefore(SinkCandidate); 163 SmallVector<VPUser *, 4> Users(SinkCandidate->users()); 164 for (auto *U : Users) { 165 auto *UI = cast<VPRecipeBase>(U); 166 if (UI->getParent() == SinkTo) 167 continue; 168 169 for (unsigned Idx = 0; Idx != UI->getNumOperands(); Idx++) { 170 if (UI->getOperand(Idx) != SinkCandidate) 171 continue; 172 UI->setOperand(Idx, Clone); 173 } 174 } 175 } 176 SinkCandidate->moveBefore(*SinkTo, SinkTo->getFirstNonPhi()); 177 for (VPValue *Op : SinkCandidate->operands()) 178 WorkList.insert(std::make_pair(SinkTo, Op)); 179 Changed = true; 180 } 181 return Changed; 182 } 183 184 /// If \p R is a region with a VPBranchOnMaskRecipe in the entry block, return 185 /// the mask. 186 VPValue *getPredicatedMask(VPRegionBlock *R) { 187 auto *EntryBB = dyn_cast<VPBasicBlock>(R->getEntry()); 188 if (!EntryBB || EntryBB->size() != 1 || 189 !isa<VPBranchOnMaskRecipe>(EntryBB->begin())) 190 return nullptr; 191 192 return cast<VPBranchOnMaskRecipe>(&*EntryBB->begin())->getOperand(0); 193 } 194 195 /// If \p R is a triangle region, return the 'then' block of the triangle. 196 static VPBasicBlock *getPredicatedThenBlock(VPRegionBlock *R) { 197 auto *EntryBB = cast<VPBasicBlock>(R->getEntry()); 198 if (EntryBB->getNumSuccessors() != 2) 199 return nullptr; 200 201 auto *Succ0 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[0]); 202 auto *Succ1 = dyn_cast<VPBasicBlock>(EntryBB->getSuccessors()[1]); 203 if (!Succ0 || !Succ1) 204 return nullptr; 205 206 if (Succ0->getNumSuccessors() + Succ1->getNumSuccessors() != 1) 207 return nullptr; 208 if (Succ0->getSingleSuccessor() == Succ1) 209 return Succ0; 210 if (Succ1->getSingleSuccessor() == Succ0) 211 return Succ1; 212 return nullptr; 213 } 214 215 bool VPlanTransforms::mergeReplicateRegions(VPlan &Plan) { 216 SetVector<VPRegionBlock *> DeletedRegions; 217 bool Changed = false; 218 219 // Collect region blocks to process up-front, to avoid iterator invalidation 220 // issues while merging regions. 221 SmallVector<VPRegionBlock *, 8> CandidateRegions( 222 VPBlockUtils::blocksOnly<VPRegionBlock>(depth_first( 223 VPBlockRecursiveTraversalWrapper<VPBlockBase *>(Plan.getEntry())))); 224 225 // Check if Base is a predicated triangle, followed by an empty block, 226 // followed by another predicate triangle. If that's the case, move the 227 // recipes from the first to the second triangle. 228 for (VPRegionBlock *Region1 : CandidateRegions) { 229 if (DeletedRegions.contains(Region1)) 230 continue; 231 auto *MiddleBasicBlock = 232 dyn_cast_or_null<VPBasicBlock>(Region1->getSingleSuccessor()); 233 if (!MiddleBasicBlock || !MiddleBasicBlock->empty()) 234 continue; 235 236 auto *Region2 = 237 dyn_cast_or_null<VPRegionBlock>(MiddleBasicBlock->getSingleSuccessor()); 238 if (!Region2) 239 continue; 240 241 VPValue *Mask1 = getPredicatedMask(Region1); 242 VPValue *Mask2 = getPredicatedMask(Region2); 243 if (!Mask1 || Mask1 != Mask2) 244 continue; 245 VPBasicBlock *Then1 = getPredicatedThenBlock(Region1); 246 VPBasicBlock *Then2 = getPredicatedThenBlock(Region2); 247 if (!Then1 || !Then2) 248 continue; 249 250 assert(Mask1 && Mask2 && "both region must have conditions"); 251 252 // Note: No fusion-preventing memory dependencies are expected in either 253 // region. Such dependencies should be rejected during earlier dependence 254 // checks, which guarantee accesses can be re-ordered for vectorization. 255 // 256 // Move recipes to the successor region. 257 for (VPRecipeBase &ToMove : make_early_inc_range(reverse(*Then1))) 258 ToMove.moveBefore(*Then2, Then2->getFirstNonPhi()); 259 260 auto *Merge1 = cast<VPBasicBlock>(Then1->getSingleSuccessor()); 261 auto *Merge2 = cast<VPBasicBlock>(Then2->getSingleSuccessor()); 262 263 // Move VPPredInstPHIRecipes from the merge block to the successor region's 264 // merge block. Update all users inside the successor region to use the 265 // original values. 266 for (VPRecipeBase &Phi1ToMove : make_early_inc_range(reverse(*Merge1))) { 267 VPValue *PredInst1 = 268 cast<VPPredInstPHIRecipe>(&Phi1ToMove)->getOperand(0); 269 VPValue *Phi1ToMoveV = Phi1ToMove.getVPSingleValue(); 270 SmallVector<VPUser *> Users(Phi1ToMoveV->users()); 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 } 298 299 void VPlanTransforms::removeRedundantInductionCasts(VPlan &Plan) { 300 for (auto &Phi : Plan.getVectorLoopRegion()->getEntryBasicBlock()->phis()) { 301 auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi); 302 if (!IV || IV->getTruncInst()) 303 continue; 304 305 // A sequence of IR Casts has potentially been recorded for IV, which 306 // *must be bypassed* when the IV is vectorized, because the vectorized IV 307 // will produce the desired casted value. This sequence forms a def-use 308 // chain and is provided in reverse order, ending with the cast that uses 309 // the IV phi. Search for the recipe of the last cast in the chain and 310 // replace it with the original IV. Note that only the final cast is 311 // expected to have users outside the cast-chain and the dead casts left 312 // over will be cleaned up later. 313 auto &Casts = IV->getInductionDescriptor().getCastInsts(); 314 VPValue *FindMyCast = IV; 315 for (Instruction *IRCast : reverse(Casts)) { 316 VPRecipeBase *FoundUserCast = nullptr; 317 for (auto *U : FindMyCast->users()) { 318 auto *UserCast = cast<VPRecipeBase>(U); 319 if (UserCast->getNumDefinedValues() == 1 && 320 UserCast->getVPSingleValue()->getUnderlyingValue() == IRCast) { 321 FoundUserCast = UserCast; 322 break; 323 } 324 } 325 FindMyCast = FoundUserCast->getVPSingleValue(); 326 } 327 FindMyCast->replaceAllUsesWith(IV); 328 } 329 } 330 331 void VPlanTransforms::removeRedundantCanonicalIVs(VPlan &Plan) { 332 VPCanonicalIVPHIRecipe *CanonicalIV = Plan.getCanonicalIV(); 333 VPWidenCanonicalIVRecipe *WidenNewIV = nullptr; 334 for (VPUser *U : CanonicalIV->users()) { 335 WidenNewIV = dyn_cast<VPWidenCanonicalIVRecipe>(U); 336 if (WidenNewIV) 337 break; 338 } 339 340 if (!WidenNewIV) 341 return; 342 343 VPBasicBlock *HeaderVPBB = Plan.getVectorLoopRegion()->getEntryBasicBlock(); 344 for (VPRecipeBase &Phi : HeaderVPBB->phis()) { 345 auto *WidenOriginalIV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi); 346 347 if (!WidenOriginalIV || !WidenOriginalIV->isCanonical() || 348 WidenOriginalIV->getScalarType() != WidenNewIV->getScalarType()) 349 continue; 350 351 // Replace WidenNewIV with WidenOriginalIV if WidenOriginalIV provides 352 // everything WidenNewIV's users need. That is, WidenOriginalIV will 353 // generate a vector phi or all users of WidenNewIV demand the first lane 354 // only. 355 if (WidenOriginalIV->needsVectorIV() || 356 vputils::onlyFirstLaneUsed(WidenNewIV)) { 357 WidenNewIV->replaceAllUsesWith(WidenOriginalIV); 358 WidenNewIV->eraseFromParent(); 359 return; 360 } 361 } 362 } 363 364 void VPlanTransforms::removeDeadRecipes(VPlan &Plan) { 365 ReversePostOrderTraversal<VPBlockRecursiveTraversalWrapper<VPBlockBase *>> 366 RPOT(Plan.getEntry()); 367 368 for (VPBasicBlock *VPBB : reverse(VPBlockUtils::blocksOnly<VPBasicBlock>(RPOT))) { 369 // The recipes in the block are processed in reverse order, to catch chains 370 // of dead recipes. 371 for (VPRecipeBase &R : make_early_inc_range(reverse(*VPBB))) { 372 if (R.mayHaveSideEffects() || any_of(R.definedValues(), [](VPValue *V) { 373 return V->getNumUsers() > 0; 374 })) 375 continue; 376 R.eraseFromParent(); 377 } 378 } 379 } 380 381 void VPlanTransforms::optimizeInductions(VPlan &Plan, ScalarEvolution &SE) { 382 SmallVector<VPRecipeBase *> ToRemove; 383 VPBasicBlock *HeaderVPBB = Plan.getVectorLoopRegion()->getEntryBasicBlock(); 384 bool HasOnlyVectorVFs = !Plan.hasVF(ElementCount::getFixed(1)); 385 for (VPRecipeBase &Phi : HeaderVPBB->phis()) { 386 auto *IV = dyn_cast<VPWidenIntOrFpInductionRecipe>(&Phi); 387 if (!IV) 388 continue; 389 if (HasOnlyVectorVFs && 390 none_of(IV->users(), [IV](VPUser *U) { return U->usesScalars(IV); })) 391 continue; 392 393 const InductionDescriptor &ID = IV->getInductionDescriptor(); 394 VPValue *Step = 395 vputils::getOrCreateVPValueForSCEVExpr(Plan, ID.getStep(), SE); 396 Instruction *TruncI = IV->getTruncInst(); 397 VPScalarIVStepsRecipe *Steps = new VPScalarIVStepsRecipe( 398 IV->getPHINode()->getType(), ID, Plan.getCanonicalIV(), 399 IV->getStartValue(), Step, TruncI ? TruncI->getType() : nullptr); 400 HeaderVPBB->insert(Steps, HeaderVPBB->getFirstNonPhi()); 401 402 // Update scalar users of IV to use Step instead. Use SetVector to ensure 403 // the list of users doesn't contain duplicates. 404 SetVector<VPUser *> Users(IV->user_begin(), IV->user_end()); 405 for (VPUser *U : Users) { 406 if (HasOnlyVectorVFs && !U->usesScalars(IV)) 407 continue; 408 for (unsigned I = 0, E = U->getNumOperands(); I != E; I++) { 409 if (U->getOperand(I) != IV) 410 continue; 411 U->setOperand(I, Steps); 412 } 413 } 414 } 415 } 416 417 void VPlanTransforms::removeRedundantExpandSCEVRecipes(VPlan &Plan) { 418 DenseMap<const SCEV *, VPValue *> SCEV2VPV; 419 420 for (VPRecipeBase &R : 421 make_early_inc_range(*Plan.getEntry()->getEntryBasicBlock())) { 422 auto *ExpR = dyn_cast<VPExpandSCEVRecipe>(&R); 423 if (!ExpR) 424 continue; 425 426 auto I = SCEV2VPV.insert({ExpR->getSCEV(), ExpR}); 427 if (I.second) 428 continue; 429 ExpR->replaceAllUsesWith(I.first->second); 430 ExpR->eraseFromParent(); 431 } 432 } 433