| 1 | //===- VPlanUtils.cpp - VPlan-related utilities ---------------------------===// |
| 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 | #include "VPlanUtils.h" |
| 10 | #include "LoopVectorizationPlanner.h" |
| 11 | #include "VPlanAnalysis.h" |
| 12 | #include "VPlanCFG.h" |
| 13 | #include "VPlanDominatorTree.h" |
| 14 | #include "VPlanPatternMatch.h" |
| 15 | #include "llvm/ADT/SetVector.h" |
| 16 | #include "llvm/ADT/TypeSwitch.h" |
| 17 | #include "llvm/Analysis/BlockFrequencyInfoImpl.h" |
| 18 | #include "llvm/Analysis/BranchProbabilityInfo.h" |
| 19 | #include "llvm/Analysis/InstSimplifyFolder.h" |
| 20 | #include "llvm/Analysis/LoopAccessAnalysis.h" |
| 21 | #include "llvm/Analysis/LoopInfo.h" |
| 22 | #include "llvm/Analysis/MemoryLocation.h" |
| 23 | #include "llvm/Analysis/ScalarEvolutionExpressions.h" |
| 24 | #include "llvm/Analysis/ScalarEvolutionPatternMatch.h" |
| 25 | #include "llvm/IR/Dominators.h" |
| 26 | #include "llvm/IR/ProfDataUtils.h" |
| 27 | #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h" |
| 28 | |
| 29 | using namespace llvm; |
| 30 | using namespace llvm::VPlanPatternMatch; |
| 31 | using namespace llvm::SCEVPatternMatch; |
| 32 | |
| 33 | bool vputils::propagatesFirstLaneUse(const VPUser *U, const VPValue *Op) { |
| 34 | if (isa<VPBlendRecipe>(Val: U)) |
| 35 | return true; |
| 36 | auto *VPI = dyn_cast<VPInstruction>(Val: U); |
| 37 | if (!VPI) |
| 38 | return false; |
| 39 | unsigned Opcode = VPI->getOpcode(); |
| 40 | switch (Opcode) { |
| 41 | case Instruction::ExtractValue: |
| 42 | case Instruction::FCmp: |
| 43 | case Instruction::ICmp: |
| 44 | case Instruction::Select: |
| 45 | case Instruction::Freeze: |
| 46 | case VPInstruction::Not: |
| 47 | // TODO: Cover additional opcodes. |
| 48 | return true; |
| 49 | case VPInstruction::PtrAdd: |
| 50 | return Op != VPI->getOperand(N: 0); |
| 51 | default: |
| 52 | return Instruction::isBinaryOp(Opcode) || Instruction::isCast(Opcode); |
| 53 | } |
| 54 | } |
| 55 | |
| 56 | bool vputils::onlyFirstLaneUsed(const VPValue *Def) { |
| 57 | SmallSetVector<const VPValue *, 8> Worklist; |
| 58 | Worklist.insert(X: Def); |
| 59 | for (unsigned I = 0; I != Worklist.size(); ++I) { |
| 60 | const VPValue *Cur = Worklist[I]; |
| 61 | for (const VPUser *U : Cur->users()) { |
| 62 | if (propagatesFirstLaneUse(U, Op: Cur)) |
| 63 | Worklist.insert(X: cast<VPSingleDefRecipe>(Val: U)); |
| 64 | else if (!U->usesFirstLaneOnly(Op: Cur)) |
| 65 | return false; |
| 66 | } |
| 67 | } |
| 68 | return true; |
| 69 | } |
| 70 | |
| 71 | bool vputils::onlyFirstPartUsed(const VPValue *Def) { |
| 72 | return all_of(Range: Def->users(), |
| 73 | P: [](const VPUser *U) { return U->usesFirstPartOnly(); }); |
| 74 | } |
| 75 | |
| 76 | bool vputils::onlyScalarValuesUsed(const VPValue *Def) { |
| 77 | return all_of(Range: Def->users(), |
| 78 | P: [Def](const VPUser *U) { return U->usesScalars(Op: Def); }); |
| 79 | } |
| 80 | |
| 81 | bool vputils::onlyScalarValuesOrLanesUsed(const VPValue *Def) { |
| 82 | return all_of(Range: Def->users(), P: [Def](VPUser *U) { |
| 83 | uint64_t Lane; |
| 84 | return U->usesScalars(Op: Def) || |
| 85 | match(U, P: m_ExtractElement(Op0: m_Specific(VPV: Def), Op1: m_ConstantInt(C&: Lane))); |
| 86 | }); |
| 87 | } |
| 88 | |
| 89 | VPValue *vputils::getOrCreateVPValueForSCEVExpr(VPlan &Plan, const SCEV *Expr, |
| 90 | bool ExpandInIR) { |
| 91 | if (auto *E = dyn_cast<SCEVConstant>(Val: Expr)) |
| 92 | return Plan.getOrAddLiveIn(V: E->getValue()); |
| 93 | // Skip SCEV expansion if Expr is a SCEVUnknown wrapping a non-instruction |
| 94 | // value. Otherwise the value may be defined in a loop and using it directly |
| 95 | // will break LCSSA form. The SCEV expansion takes care of preserving LCSSA |
| 96 | // form. |
| 97 | auto *U = dyn_cast<SCEVUnknown>(Val: Expr); |
| 98 | if (U && !isa<Instruction>(Val: U->getValue())) |
| 99 | return Plan.getOrAddLiveIn(V: U->getValue()); |
| 100 | auto *Expanded = new VPExpandSCEVRecipe(Expr, ExpandInIR); |
| 101 | VPBasicBlock *EntryVPBB = Plan.getEntry(); |
| 102 | auto Iter = EntryVPBB->getFirstNonPhi(); |
| 103 | while (Iter != EntryVPBB->end() && isa<VPIRInstruction>(Val: *Iter)) |
| 104 | ++Iter; |
| 105 | Expanded->insertBefore(IP: Iter); |
| 106 | return Expanded; |
| 107 | } |
| 108 | |
| 109 | /// Returns true if \p V being poison is guaranteed to trigger UB because it |
| 110 | /// propagates to the address of a memory recipe. |
| 111 | static bool poisonGuaranteesUB(const VPValue *V) { |
| 112 | SmallPtrSet<const VPValue *, 8> Visited; |
| 113 | SmallVector<const VPValue *, 16> Worklist; |
| 114 | |
| 115 | auto PropagatesPoisonFromRecipeOp = [](const VPRecipeBase *R) { |
| 116 | if (!isa<VPSingleDefRecipe>(Val: R)) |
| 117 | return false; |
| 118 | unsigned Opcode = vputils::getOpcode(V: R->getVPSingleValue()); |
| 119 | return Instruction::isCast(Opcode) || Opcode == Instruction::GetElementPtr; |
| 120 | }; |
| 121 | |
| 122 | Worklist.push_back(Elt: V); |
| 123 | |
| 124 | while (!Worklist.empty()) { |
| 125 | const VPValue *Current = Worklist.pop_back_val(); |
| 126 | if (!Visited.insert(Ptr: Current).second) |
| 127 | continue; |
| 128 | |
| 129 | for (VPUser *U : Current->users()) { |
| 130 | // Check if Current is used as an address operand for load/store. |
| 131 | auto *R = cast<VPRecipeBase>(Val: U); |
| 132 | if (auto *MemR = dyn_cast<VPWidenMemoryRecipe>(Val: R)) { |
| 133 | if (MemR->getAddr() == Current) |
| 134 | return true; |
| 135 | continue; |
| 136 | } |
| 137 | if (auto *Rep = dyn_cast<VPReplicateRecipe>(Val: U)) { |
| 138 | unsigned Opcode = Rep->getOpcode(); |
| 139 | if ((Opcode == Instruction::Load && Rep->getOperand(N: 0) == Current) || |
| 140 | (Opcode == Instruction::Store && Rep->getOperand(N: 1) == Current)) |
| 141 | return true; |
| 142 | } |
| 143 | |
| 144 | // Check if poison propagates through this recipe to any of its users. |
| 145 | for (const VPValue *Op : R->operands()) { |
| 146 | if (Op == Current && PropagatesPoisonFromRecipeOp(R)) { |
| 147 | Worklist.push_back(Elt: R->getVPSingleValue()); |
| 148 | break; |
| 149 | } |
| 150 | } |
| 151 | } |
| 152 | } |
| 153 | |
| 154 | return false; |
| 155 | } |
| 156 | |
| 157 | GEPNoWrapFlags vputils::getGEPFlagsForPtr(VPValue *Ptr) { |
| 158 | // Like IR stripPointerCasts, look through GEPs with all-zero indices and |
| 159 | // casts to find a root GEP VPInstruction. |
| 160 | while (auto *PtrVPI = dyn_cast<VPInstruction>(Val: Ptr)) { |
| 161 | unsigned Opcode = PtrVPI->getOpcode(); |
| 162 | if (Opcode == Instruction::GetElementPtr) { |
| 163 | if (!all_of(Range: drop_begin(RangeOrContainer: PtrVPI->operands()), P: match_fn(P: m_ZeroInt()))) |
| 164 | return PtrVPI->getGEPNoWrapFlags(); |
| 165 | Ptr = PtrVPI->getOperand(N: 0); |
| 166 | continue; |
| 167 | } |
| 168 | if (Opcode != Instruction::BitCast && Opcode != Instruction::AddrSpaceCast) |
| 169 | break; |
| 170 | Ptr = PtrVPI->getOperand(N: 0); |
| 171 | } |
| 172 | return GEPNoWrapFlags::none(); |
| 173 | } |
| 174 | |
| 175 | const SCEV *vputils::getSCEVExprForVPValue(const VPValue *V, |
| 176 | PredicatedScalarEvolution &PSE, |
| 177 | const Loop *L) { |
| 178 | ScalarEvolution &SE = *PSE.getSE(); |
| 179 | if (auto *RV = dyn_cast<VPRegionValue>(Val: V)) { |
| 180 | assert(RV == RV->getDefiningRegion()->getCanonicalIV() && |
| 181 | "RegionValue must be canonical IV" ); |
| 182 | if (!L) |
| 183 | return SE.getCouldNotCompute(); |
| 184 | return SE.getAddRecExpr(Start: SE.getZero(Ty: RV->getType()), Step: SE.getOne(Ty: RV->getType()), |
| 185 | L, Flags: SCEV::FlagNone); |
| 186 | } |
| 187 | |
| 188 | if (isa<VPIRValue, VPSymbolicValue>(Val: V)) { |
| 189 | Value *LiveIn = V->getUnderlyingValue(); |
| 190 | if (LiveIn && SE.isSCEVable(Ty: LiveIn->getType())) |
| 191 | return SE.getSCEV(V: LiveIn); |
| 192 | return SE.getCouldNotCompute(); |
| 193 | } |
| 194 | |
| 195 | // Helper to create SCEVs for binary and unary operations. |
| 196 | auto CreateSCEV = [&](ArrayRef<VPValue *> Ops, |
| 197 | function_ref<const SCEV *(ArrayRef<SCEVUse>)> CreateFn) |
| 198 | -> const SCEV * { |
| 199 | SmallVector<SCEVUse, 2> SCEVOps; |
| 200 | for (VPValue *Op : Ops) { |
| 201 | const SCEV *S = getSCEVExprForVPValue(V: Op, PSE, L); |
| 202 | if (isa<SCEVCouldNotCompute>(Val: S)) |
| 203 | return SE.getCouldNotCompute(); |
| 204 | SCEVOps.push_back(Elt: S); |
| 205 | } |
| 206 | return PSE.getPredicatedSCEV(Expr: CreateFn(SCEVOps)); |
| 207 | }; |
| 208 | |
| 209 | VPValue *LHSVal, *RHSVal; |
| 210 | if (match(V, P: m_Add(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) |
| 211 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 212 | return SE.getAddExpr(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagNone, Depth: 0); |
| 213 | }); |
| 214 | if (match(V, P: m_BinaryOr(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) |
| 215 | if (cast<VPRecipeWithIRFlags>(Val: V->getDefiningRecipe())->isDisjoint()) |
| 216 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 217 | return SE.getAddExpr(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagNone, Depth: 0); |
| 218 | }); |
| 219 | if (match(V, P: m_Sub(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) |
| 220 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 221 | return SE.getMinusSCEV(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagNone, Depth: 0); |
| 222 | }); |
| 223 | if (match(V, P: m_Not(Op0: m_VPValue(V&: LHSVal)))) { |
| 224 | // not X = xor X, -1 = -1 - X |
| 225 | return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 226 | return SE.getMinusSCEV(LHS: SE.getMinusOne(Ty: Ops[0]->getType()), RHS: Ops[0]); |
| 227 | }); |
| 228 | } |
| 229 | if (match(V, P: m_Mul(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) |
| 230 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 231 | return SE.getMulExpr(LHS: Ops[0], RHS: Ops[1], Flags: SCEV::FlagNone, Depth: 0); |
| 232 | }); |
| 233 | // Handle shl by constant: x << c is equivalent to x * (1 << c). A shift |
| 234 | // amount >= the bit width produces poison; do not rewrite it, as |
| 235 | // getPowerOfTwo requires the power to be in range. |
| 236 | uint64_t ShiftAmt; |
| 237 | if (match(V, P: m_Shl(Op0: m_VPValue(V&: LHSVal), Op1: m_ConstantInt(C&: ShiftAmt))) && |
| 238 | ShiftAmt < LHSVal->getScalarType()->getScalarSizeInBits()) |
| 239 | return CreateSCEV(LHSVal, [&](ArrayRef<SCEVUse> Ops) { |
| 240 | return SE.getMulExpr(LHS: Ops[0], |
| 241 | RHS: SE.getPowerOfTwo(Ty: Ops[0]->getType(), Power: ShiftAmt)); |
| 242 | }); |
| 243 | if (match(V, P: m_LShr(Op0: m_VPValue(V&: LHSVal), Op1: m_ConstantInt(C&: ShiftAmt)))) { |
| 244 | Type *Ty = V->getScalarType(); |
| 245 | if (ShiftAmt < SE.getTypeSizeInBits(Ty)) |
| 246 | return CreateSCEV(LHSVal, [&](ArrayRef<SCEVUse> Ops) { |
| 247 | return SE.getUDivExpr(LHS: Ops[0], RHS: SE.getPowerOfTwo(Ty, Power: ShiftAmt)); |
| 248 | }); |
| 249 | } |
| 250 | if (match(V, P: m_UDiv(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) |
| 251 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 252 | return SE.getUDivExpr(LHS: Ops[0], RHS: Ops[1]); |
| 253 | }); |
| 254 | if (match(V, P: m_URem(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) |
| 255 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 256 | return SE.getURemExpr(LHS: Ops[0], RHS: Ops[1]); |
| 257 | }); |
| 258 | // A SDiv with non-negative operands is equivalent to an UDiv. |
| 259 | if (match(V, P: m_SDiv(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) { |
| 260 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 261 | if (!SE.isKnownNonNegative(S: Ops[0]) || !SE.isKnownNonNegative(S: Ops[1])) |
| 262 | return SE.getCouldNotCompute(); |
| 263 | return SE.getUDivExpr(LHS: Ops[0], RHS: Ops[1]); |
| 264 | }); |
| 265 | } |
| 266 | // A SRem with non-negative operands is equivalent to an URem. |
| 267 | if (match(V, P: m_SRem(Op0: m_VPValue(V&: LHSVal), Op1: m_VPValue(V&: RHSVal)))) { |
| 268 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 269 | if (!SE.isKnownNonNegative(S: Ops[0]) || !SE.isKnownNonNegative(S: Ops[1])) |
| 270 | return SE.getCouldNotCompute(); |
| 271 | return SE.getURemExpr(LHS: Ops[0], RHS: Ops[1]); |
| 272 | }); |
| 273 | } |
| 274 | // Handle AND with constant mask: x & (2^n - 1) can be represented as x % 2^n. |
| 275 | const APInt *Mask; |
| 276 | if (match(V, P: m_c_BinaryAnd(Op0: m_VPValue(V&: LHSVal), Op1: m_APInt(C&: Mask))) && |
| 277 | (*Mask + 1).isPowerOf2()) |
| 278 | return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 279 | return SE.getURemExpr(LHS: Ops[0], RHS: SE.getConstant(Val: *Mask + 1)); |
| 280 | }); |
| 281 | // SCEV models ptrtoaddr, but not ptrtoint, mirroring createSCEV. |
| 282 | if (match(V, P: m_PtrToAddr(Op0: m_VPValue(V&: LHSVal)))) |
| 283 | return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 284 | return SE.getPtrToAddrExpr(Op: Ops[0]); |
| 285 | }); |
| 286 | if (match(V, P: m_Trunc(Op0: m_VPValue(V&: LHSVal)))) { |
| 287 | Type *DestTy = V->getScalarType(); |
| 288 | return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 289 | return SE.getTruncateExpr(Op: Ops[0], Ty: DestTy); |
| 290 | }); |
| 291 | } |
| 292 | if (match(V, P: m_ZExt(Op0: m_VPValue(V&: LHSVal)))) { |
| 293 | Type *DestTy = V->getScalarType(); |
| 294 | return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 295 | return SE.getZeroExtendExpr(Op: Ops[0], Ty: DestTy); |
| 296 | }); |
| 297 | } |
| 298 | if (match(V, P: m_SExt(Op0: m_VPValue(V&: LHSVal)))) { |
| 299 | Type *DestTy = V->getScalarType(); |
| 300 | |
| 301 | // Mirror SCEV's createSCEV handling for sext(sub nsw): push sign extension |
| 302 | // onto the operands before computing the subtraction. |
| 303 | VPValue *SubLHS, *SubRHS; |
| 304 | auto *SubR = dyn_cast<VPRecipeWithIRFlags>(Val: LHSVal); |
| 305 | if (match(V: LHSVal, P: m_Sub(Op0: m_VPValue(V&: SubLHS), Op1: m_VPValue(V&: SubRHS))) && SubR && |
| 306 | SubR->hasNoSignedWrap() && poisonGuaranteesUB(V: LHSVal)) { |
| 307 | const SCEV *V1 = getSCEVExprForVPValue(V: SubLHS, PSE, L); |
| 308 | const SCEV *V2 = getSCEVExprForVPValue(V: SubRHS, PSE, L); |
| 309 | if (!isa<SCEVCouldNotCompute>(Val: V1) && !isa<SCEVCouldNotCompute>(Val: V2)) |
| 310 | return SE.getMinusSCEV(LHS: SE.getSignExtendExpr(Op: V1, Ty: DestTy), |
| 311 | RHS: SE.getSignExtendExpr(Op: V2, Ty: DestTy), Flags: SCEV::FlagNSW); |
| 312 | } |
| 313 | |
| 314 | return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 315 | return SE.getSignExtendExpr(Op: Ops[0], Ty: DestTy); |
| 316 | }); |
| 317 | } |
| 318 | if (match(V, |
| 319 | P: m_Intrinsic<Intrinsic::umax>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal)))) |
| 320 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 321 | return SE.getUMaxExpr(LHS: Ops[0], RHS: Ops[1]); |
| 322 | }); |
| 323 | if (match(V, |
| 324 | P: m_Intrinsic<Intrinsic::smax>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal)))) |
| 325 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 326 | return SE.getSMaxExpr(LHS: Ops[0], RHS: Ops[1]); |
| 327 | }); |
| 328 | if (match(V, |
| 329 | P: m_Intrinsic<Intrinsic::umin>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal)))) |
| 330 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 331 | return SE.getUMinExpr(LHS: Ops[0], RHS: Ops[1]); |
| 332 | }); |
| 333 | if (match(V, |
| 334 | P: m_Intrinsic<Intrinsic::smin>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue(V&: RHSVal)))) |
| 335 | return CreateSCEV({LHSVal, RHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 336 | return SE.getSMinExpr(LHS: Ops[0], RHS: Ops[1]); |
| 337 | }); |
| 338 | if (match(V, P: m_Intrinsic<Intrinsic::abs>(Ops: m_VPValue(V&: LHSVal), Ops: m_VPValue()))) |
| 339 | return CreateSCEV({LHSVal}, [&](ArrayRef<SCEVUse> Ops) { |
| 340 | // is_int_min_poison is local to this intrinsic: poison on INT_MIN is |
| 341 | // not proof that the input is never INT_MIN, nor that poison reaches |
| 342 | // UB. Do not translate it to SCEV's global IsNSW flag. |
| 343 | return SE.getAbsExpr(Op: Ops[0], /*IsNSW=*/false); |
| 344 | }); |
| 345 | |
| 346 | ArrayRef<VPValue *> Ops; |
| 347 | Type *SourceElementType; |
| 348 | if (match(V, P: m_GetElementPtr(SourceElementType, Operands&: Ops))) { |
| 349 | return CreateSCEV(Ops, [&](ArrayRef<SCEVUse> Ops) { |
| 350 | return SE.getGEPExpr(BaseExpr: Ops.front(), IndexExprs: Ops.drop_front(), SrcElementTy: SourceElementType); |
| 351 | }); |
| 352 | } |
| 353 | |
| 354 | // TODO: Support constructing SCEVs for more recipes as needed. |
| 355 | const VPRecipeBase *DefR = V->getDefiningRecipe(); |
| 356 | const SCEV *Expr = |
| 357 | TypeSwitch<const VPRecipeBase *, const SCEV *>(DefR) |
| 358 | .Case(caseFn: [](const VPExpandSCEVRecipe *R) { return R->getSCEV(); }) |
| 359 | .Case(caseFn: [&SE, &PSE, L](const VPWidenIntOrFpInductionRecipe *R) { |
| 360 | const SCEV *Step = getSCEVExprForVPValue(V: R->getStepValue(), PSE, L); |
| 361 | if (!L || isa<SCEVCouldNotCompute>(Val: Step)) |
| 362 | return SE.getCouldNotCompute(); |
| 363 | const SCEV *Start = |
| 364 | getSCEVExprForVPValue(V: R->getStartValue(), PSE, L); |
| 365 | const SCEV *AddRec = |
| 366 | SE.getAddRecExpr(Start, Step, L, Flags: SCEV::FlagNone); |
| 367 | if (R->isTruncated()) |
| 368 | return SE.getTruncateExpr(Op: AddRec, Ty: R->getScalarType()); |
| 369 | return AddRec; |
| 370 | }) |
| 371 | .Case(caseFn: [&SE, &PSE, |
| 372 | L](const VPWidenPointerInductionRecipe *R) -> const SCEV * { |
| 373 | const SCEV *Start = |
| 374 | getSCEVExprForVPValue(V: R->getStartValue(), PSE, L); |
| 375 | if (!L || isa<SCEVCouldNotCompute>(Val: Start)) |
| 376 | return SE.getCouldNotCompute(); |
| 377 | const SCEV *Step = getSCEVExprForVPValue(V: R->getStepValue(), PSE, L); |
| 378 | if (isa<SCEVCouldNotCompute>(Val: Step)) |
| 379 | return SE.getCouldNotCompute(); |
| 380 | return SE.getAddRecExpr(Start, Step, L, Flags: SCEV::FlagNone); |
| 381 | }) |
| 382 | .Case(caseFn: [&SE, &PSE, L](const VPDerivedIVRecipe *R) -> const SCEV * { |
| 383 | const SCEV *Start = |
| 384 | getSCEVExprForVPValue(V: R->getStartValue(), PSE, L); |
| 385 | const SCEV *Index = getSCEVExprForVPValue(V: R->getIndex(), PSE, L); |
| 386 | const SCEV *Step = getSCEVExprForVPValue(V: R->getStepValue(), PSE, L); |
| 387 | if (any_of(Range: ArrayRef({Start, Index, Step}), |
| 388 | P: IsaPred<SCEVCouldNotCompute>)) |
| 389 | return SE.getCouldNotCompute(); |
| 390 | |
| 391 | // Convert Index to the step type, matching expandVPDerivedIV. |
| 392 | Index = SE.getTruncateOrZeroExtend(V: Index, Ty: Step->getType()); |
| 393 | return SE.getAddExpr(LHS: Start, RHS: SE.getMulExpr(LHS: Index, RHS: Step)); |
| 394 | }) |
| 395 | .Case(caseFn: [&SE, &PSE, L](const VPScalarIVStepsRecipe *R) { |
| 396 | // A start index, set for parts and lanes other than the first, |
| 397 | // adds StartIndex * Step, which is not modeled. |
| 398 | const SCEV *IV = getSCEVExprForVPValue(V: R->getOperand(N: 0), PSE, L); |
| 399 | if (isa<SCEVCouldNotCompute>(Val: IV) || R->getStartIndex()) |
| 400 | return SE.getCouldNotCompute(); |
| 401 | return IV; |
| 402 | }) |
| 403 | .Default( |
| 404 | defaultFn: [&SE](const VPRecipeBase *) { return SE.getCouldNotCompute(); }); |
| 405 | |
| 406 | return PSE.getPredicatedSCEV(Expr); |
| 407 | } |
| 408 | |
| 409 | std::optional<int64_t> |
| 410 | vputils::getConstantStride(VPValue *Addr, Type *AccessTy, |
| 411 | PredicatedScalarEvolution &PSE, const Loop *L) { |
| 412 | assert(!hasIrregularType(AccessTy, L->getHeader()->getDataLayout()) && |
| 413 | "should not try to widen irregular types" ); |
| 414 | const SCEV *AddrSCEV = getSCEVExprForVPValue(V: Addr, PSE, L); |
| 415 | auto *AddRec = dyn_cast<SCEVAddRecExpr>(Val: AddrSCEV); |
| 416 | if (!AddRec) |
| 417 | return {}; |
| 418 | |
| 419 | return getStrideFromAddRec(AR: AddRec, Lp: L, AccessTy, /*Ptr=*/nullptr, PSE); |
| 420 | } |
| 421 | |
| 422 | bool vputils::isAddressSCEVForCost(const SCEV *Addr, ScalarEvolution &SE, |
| 423 | const Loop *L) { |
| 424 | // If address is an SCEVAddExpr, we require that all operands must be either |
| 425 | // be invariant or a (possibly sign-extend) affine AddRec. |
| 426 | if (auto *PtrAdd = dyn_cast<SCEVAddExpr>(Val: Addr)) { |
| 427 | return all_of(Range: PtrAdd->operands(), P: [&SE, L](const SCEV *Op) { |
| 428 | return SE.isLoopInvariant(S: Op, L) || |
| 429 | match(S: Op, P: m_scev_SExt(Op0: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV()))) || |
| 430 | match(S: Op, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV())); |
| 431 | }); |
| 432 | } |
| 433 | |
| 434 | // Otherwise, check if address is loop invariant or an affine add recurrence. |
| 435 | return SE.isLoopInvariant(S: Addr, L) || |
| 436 | match(S: Addr, P: m_scev_AffineAddRec(Op0: m_SCEV(), Op1: m_SCEV())); |
| 437 | } |
| 438 | |
| 439 | unsigned vputils::getOpcode(const VPValue *V) { |
| 440 | return TypeSwitch<const VPValue *, unsigned>(V) |
| 441 | .Case<VPInstruction, VPWidenRecipe, VPWidenCastRecipe, VPWidenGEPRecipe, |
| 442 | VPReplicateRecipe, VPWidenPHIRecipe, VPWidenLoadRecipe, |
| 443 | VPWidenLoadEVLRecipe>(caseFn: [](auto *I) { return I->getOpcode(); }) |
| 444 | .Case<VPVectorPointerRecipe, VPPredInstPHIRecipe, VPScalarIVStepsRecipe, |
| 445 | VPDerivedIVRecipe, VPExpandSCEVRecipe>(caseFn: [](auto *I) { |
| 446 | // For recipes that do not directly map to LLVM IR instructions, |
| 447 | // assign opcodes after the last VPInstruction opcode (which is also |
| 448 | // after the last IR Instruction opcode), based on the VPRecipeID. |
| 449 | return VPInstruction::OpsEnd + 1 + I->getVPRecipeID(); |
| 450 | }) |
| 451 | .Default(defaultFn: [](auto *) { return 0; }); |
| 452 | } |
| 453 | |
| 454 | std::optional<std::pair<bool, unsigned>> |
| 455 | vputils::getOpcodeOrIntrinsicID(const VPValue *V) { |
| 456 | if (Intrinsic::ID IID = vputils::getIntrinsicID(R: V)) |
| 457 | return std::make_pair(x: true, y&: IID); |
| 458 | if (unsigned Opcode = vputils::getOpcode(V)) |
| 459 | return std::make_pair(x: false, y&: Opcode); |
| 460 | return {}; |
| 461 | } |
| 462 | |
| 463 | /// Returns true if \p Opcode preserves uniformity, i.e., if all operands are |
| 464 | /// uniform, the result will also be uniform. |
| 465 | static bool preservesUniformity(unsigned Opcode) { |
| 466 | if (Instruction::isBinaryOp(Opcode) || Instruction::isCast(Opcode)) |
| 467 | return true; |
| 468 | switch (Opcode) { |
| 469 | case Instruction::Freeze: |
| 470 | case Instruction::GetElementPtr: |
| 471 | case Instruction::ICmp: |
| 472 | case Instruction::FCmp: |
| 473 | case Instruction::Select: |
| 474 | case VPInstruction::Not: |
| 475 | case VPInstruction::Broadcast: |
| 476 | case VPInstruction::MaskedCond: |
| 477 | case VPInstruction::PtrAdd: |
| 478 | return true; |
| 479 | default: |
| 480 | return false; |
| 481 | } |
| 482 | } |
| 483 | |
| 484 | bool vputils::isElementwise(const VPValue *V) { |
| 485 | // TODO: Handle more opcodes and recipes. |
| 486 | if (!isa<VPInstruction, VPWidenRecipe>(Val: V)) |
| 487 | return false; |
| 488 | unsigned Opcode = getOpcode(V); |
| 489 | return Instruction::isUnaryOp(Opcode) || Instruction::isBinaryOp(Opcode); |
| 490 | } |
| 491 | |
| 492 | bool vputils::isSingleScalar(const VPValue *VPV) { |
| 493 | // Live-in, symbolic and canonical-IV region values are single-scalar. |
| 494 | if (auto *RV = dyn_cast<VPRegionValue>(Val: VPV)) |
| 495 | return RV == RV->getDefiningRegion()->getCanonicalIV(); |
| 496 | if (isa<VPIRValue, VPSymbolicValue>(Val: VPV)) |
| 497 | return true; |
| 498 | |
| 499 | if (auto *Rep = dyn_cast<VPReplicateRecipe>(Val: VPV)) { |
| 500 | const VPRegionBlock *RegionOfR = Rep->getRegion(); |
| 501 | // Don't consider recipes in replicate regions as uniform yet; their first |
| 502 | // lane cannot be accessed when executing the replicate region for other |
| 503 | // lanes. |
| 504 | if (RegionOfR && RegionOfR->isReplicator()) |
| 505 | return false; |
| 506 | return Rep->isSingleScalar() || (preservesUniformity(Opcode: Rep->getOpcode()) && |
| 507 | all_of(Range: Rep->operands(), P: isSingleScalar)); |
| 508 | } |
| 509 | if (isa<VPWidenGEPRecipe, VPBlendRecipe>(Val: VPV)) |
| 510 | return all_of(Range: VPV->getDefiningRecipe()->operands(), P: isSingleScalar); |
| 511 | if (auto *WidenR = dyn_cast<VPWidenRecipe>(Val: VPV)) { |
| 512 | return preservesUniformity(Opcode: WidenR->getOpcode()) && |
| 513 | all_of(Range: WidenR->operands(), P: isSingleScalar); |
| 514 | } |
| 515 | if (auto *VPI = dyn_cast<VPInstruction>(Val: VPV)) |
| 516 | return VPI->isSingleScalar() || VPI->isVectorToScalar() || |
| 517 | (preservesUniformity(Opcode: VPI->getOpcode()) && |
| 518 | all_of(Range: VPI->operands(), P: isSingleScalar)); |
| 519 | if (auto *RR = dyn_cast<VPReductionRecipe>(Val: VPV)) |
| 520 | return !RR->isPartialReduction(); |
| 521 | if (isa<VPVectorPointerRecipe, VPVectorEndPointerRecipe, VPDerivedIVRecipe, |
| 522 | VPConditionalInductionPHIRecipe>(Val: VPV)) |
| 523 | return true; |
| 524 | if (auto *Expr = dyn_cast<VPExpressionRecipe>(Val: VPV)) |
| 525 | return Expr->isVectorToScalar(); |
| 526 | |
| 527 | // VPExpandSCEVRecipes must be placed in the entry and are always uniform. |
| 528 | return isa<VPExpandSCEVRecipe>(Val: VPV); |
| 529 | } |
| 530 | |
| 531 | static bool isUniformAcrossVFsAndUFsImpl( |
| 532 | const VPValue *V, |
| 533 | function_ref<void(VPUser::const_operand_range)> AddToWorklist) { |
| 534 | // Live-ins, symbolic and canonical-IV region values are uniform. |
| 535 | if (auto *RV = dyn_cast<VPRegionValue>(Val: V)) |
| 536 | return RV == RV->getDefiningRegion()->getCanonicalIV(); |
| 537 | if (isa<VPIRValue, VPSymbolicValue>(Val: V)) |
| 538 | return true; |
| 539 | |
| 540 | const VPRecipeBase *R = V->getDefiningRecipe(); |
| 541 | const VPBasicBlock *VPBB = R ? R->getParent() : nullptr; |
| 542 | const VPlan *Plan = VPBB ? VPBB->getPlan() : nullptr; |
| 543 | if (VPBB && |
| 544 | (VPBB == Plan->getVectorPreheader() || VPBB == Plan->getEntry())) { |
| 545 | if (match(V: R, |
| 546 | P: m_VPInstruction<VPInstruction::CanonicalIVIncrementForPart>()) || |
| 547 | match(V: R, P: m_ExtractVectorForPart(Op: m_VPValue(), Op: m_VPValue()))) |
| 548 | return false; |
| 549 | AddToWorklist(R->operands()); |
| 550 | return true; |
| 551 | } |
| 552 | |
| 553 | return TypeSwitch<const VPRecipeBase *, bool>(R) |
| 554 | .Case(caseFn: [](const VPDerivedIVRecipe *) { return true; }) |
| 555 | .Case(caseFn: [&](const VPReplicateRecipe *R) { |
| 556 | // Be conservative about side-effects, except for the |
| 557 | // known-side-effecting assumes and stores, which we know will be |
| 558 | // uniform. Each alloca creates a distinct allocation, so allocas are |
| 559 | // never uniform. |
| 560 | if (!R->isSingleScalar() || R->getOpcode() == Instruction::Alloca || |
| 561 | (R->mayHaveSideEffects() && |
| 562 | !isa<AssumeInst, StoreInst>(Val: R->getUnderlyingInstr()))) |
| 563 | return false; |
| 564 | AddToWorklist(R->operands()); |
| 565 | return true; |
| 566 | }) |
| 567 | .Case(caseFn: [&](const VPWidenRecipe *R) { |
| 568 | if (!preservesUniformity(Opcode: R->getOpcode())) |
| 569 | return false; |
| 570 | AddToWorklist(R->operands()); |
| 571 | return true; |
| 572 | }) |
| 573 | .Case(caseFn: [](const VPPhi *) { |
| 574 | // Bail out on VPPhi, as we can end up in infinite cycles. |
| 575 | return false; |
| 576 | }) |
| 577 | .Case(caseFn: [&](const VPInstruction *VPI) { |
| 578 | if (!VPI->isSingleScalar() && !VPI->isVectorToScalar() && |
| 579 | !preservesUniformity(Opcode: VPI->getOpcode())) |
| 580 | return false; |
| 581 | AddToWorklist(VPI->operands()); |
| 582 | return true; |
| 583 | }) |
| 584 | .Case(caseFn: [&](const VPWidenCastRecipe *R) { |
| 585 | // A cast is uniform according to its operand. |
| 586 | AddToWorklist(R->operands()); |
| 587 | return true; |
| 588 | }) |
| 589 | .Default(defaultFn: [](const VPRecipeBase *) { |
| 590 | // A value is considered non-uniform unless proven otherwise. |
| 591 | return false; |
| 592 | }); |
| 593 | } |
| 594 | |
| 595 | bool vputils::isUniformAcrossVFsAndUFs(const VPValue *V) { |
| 596 | SmallSetVector<const VPValue *, 8> Worklist; |
| 597 | Worklist.insert(X: V); |
| 598 | |
| 599 | auto AddToWorklist = [&Worklist](VPUser::const_operand_range Operands) { |
| 600 | Worklist.insert_range(R&: Operands); |
| 601 | }; |
| 602 | |
| 603 | // All dependency checks are conjunctive, so each value needs checking once. |
| 604 | for (unsigned I = 0; I != Worklist.size(); ++I) { |
| 605 | if (!isUniformAcrossVFsAndUFsImpl(V: Worklist[I], AddToWorklist)) |
| 606 | return false; |
| 607 | } |
| 608 | return true; |
| 609 | } |
| 610 | |
| 611 | bool vputils::doesGeneratePerAllLanes(const VPRecipeBase *R) { |
| 612 | if (auto *RepR = dyn_cast<VPReplicateRecipe>(Val: R)) |
| 613 | return RepR->doesGeneratePerAllLanes(); |
| 614 | if (auto *VPI = dyn_cast<VPInstruction>(Val: R)) |
| 615 | return VPI->doesGeneratePerAllLanes(); |
| 616 | if (auto *SIVSteps = dyn_cast<VPScalarIVStepsRecipe>(Val: R)) |
| 617 | return SIVSteps->doesGeneratePerAllLanes(); |
| 618 | return false; |
| 619 | } |
| 620 | |
| 621 | VPBasicBlock *vputils::(VPlan &Plan, VPDominatorTree &VPDT) { |
| 622 | auto DepthFirst = vp_depth_first_shallow(G: Plan.getEntry()); |
| 623 | auto I = find_if(Range&: DepthFirst, P: [&VPDT](VPBlockBase *VPB) { |
| 624 | return VPBlockUtils::isHeader(VPB, VPDT); |
| 625 | }); |
| 626 | return I == DepthFirst.end() ? nullptr : cast<VPBasicBlock>(Val: *I); |
| 627 | } |
| 628 | |
| 629 | unsigned vputils::getVFScaleFactor(VPRecipeBase *R) { |
| 630 | if (!R) |
| 631 | return 1; |
| 632 | if (auto *RR = dyn_cast<VPReductionPHIRecipe>(Val: R)) |
| 633 | return RR->getVFScaleFactor(); |
| 634 | if (auto *RR = dyn_cast<VPReductionRecipe>(Val: R)) |
| 635 | return RR->getVFScaleFactor(); |
| 636 | if (auto *ER = dyn_cast<VPExpressionRecipe>(Val: R)) |
| 637 | return ER->getVFScaleFactor(); |
| 638 | assert( |
| 639 | (!isa<VPInstruction>(R) || cast<VPInstruction>(R)->getOpcode() != |
| 640 | VPInstruction::ReductionStartVector) && |
| 641 | "getting scaling factor of reduction-start-vector not implemented yet" ); |
| 642 | return 1; |
| 643 | } |
| 644 | |
| 645 | bool vputils::cannotHoistOrSinkRecipe(const VPRecipeBase &R, bool Sinking) { |
| 646 | // Assumes don't alias anything or throw; as long as they're guaranteed to |
| 647 | // execute, they're safe to hoist. They should however not be sunk, as it |
| 648 | // would destroy information. |
| 649 | if (match(V: &R, P: m_Intrinsic<Intrinsic::assume>())) |
| 650 | return Sinking; |
| 651 | if (R.mayHaveSideEffects() || R.mayReadFromMemory() || R.isPhi()) |
| 652 | return true; |
| 653 | // Allocas cannot be hoisted. |
| 654 | auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &R); |
| 655 | return RepR && RepR->getOpcode() == Instruction::Alloca; |
| 656 | } |
| 657 | |
| 658 | SmallVector<VPBasicBlock *> |
| 659 | VPBlockUtils::blocksInSingleSuccessorChainBetween(VPBasicBlock *FirstBB, |
| 660 | VPBasicBlock *LastBB) { |
| 661 | assert(FirstBB->getParent() == LastBB->getParent() && |
| 662 | "FirstBB and LastBB from different regions" ); |
| 663 | #ifndef NDEBUG |
| 664 | bool InSingleSuccChain = false; |
| 665 | for (VPBlockBase *Succ = FirstBB; Succ; Succ = Succ->getSingleSuccessor()) |
| 666 | InSingleSuccChain |= (Succ == LastBB); |
| 667 | assert(InSingleSuccChain && |
| 668 | "LastBB unreachable from FirstBB in single-successor chain" ); |
| 669 | #endif |
| 670 | auto Blocks = to_vector( |
| 671 | Range: VPBlockUtils::blocksOnly<VPBasicBlock>(Range: vp_depth_first_deep(G: FirstBB))); |
| 672 | auto *LastIt = find(Range&: Blocks, Val: LastBB); |
| 673 | assert(LastIt != Blocks.end() && |
| 674 | "LastBB unreachable from FirstBB in depth-first traversal" ); |
| 675 | Blocks.erase(CS: std::next(x: LastIt), CE: Blocks.end()); |
| 676 | return Blocks; |
| 677 | } |
| 678 | |
| 679 | VPValue *vputils::findIncomingAliasMask(const VPlan &Plan) { |
| 680 | for (VPRecipeBase &R : *Plan.getVectorPreheader()) |
| 681 | if (match(V: &R, P: m_VPInstruction<VPInstruction::IncomingAliasMask>())) |
| 682 | return cast<VPInstruction>(Val: &R); |
| 683 | return nullptr; |
| 684 | } |
| 685 | |
| 686 | SmallVector<std::pair<VPBasicBlock *, VPIRBasicBlock *>> |
| 687 | vputils::getEarlyExits(const VPlan &Plan, const VPBlockBase *MiddleVPBB) { |
| 688 | SmallVector<std::pair<VPBasicBlock *, VPIRBasicBlock *>> Exits; |
| 689 | for (VPIRBasicBlock *ExitVPBB : Plan.getExitBlocks()) |
| 690 | for (VPBlockBase *Pred : ExitVPBB->getPredecessors()) |
| 691 | if (Pred != MiddleVPBB) |
| 692 | Exits.emplace_back(Args: cast<VPBasicBlock>(Val: Pred), Args&: ExitVPBB); |
| 693 | return Exits; |
| 694 | } |
| 695 | |
| 696 | VPScalarIVStepsRecipe *vputils::createScalarIVSteps( |
| 697 | VPlan &Plan, InductionDescriptor::InductionKind Kind, |
| 698 | Instruction::BinaryOps InductionOpcode, FPMathOperator *FPBinOp, |
| 699 | Type *ResultTy, VPValue *StartV, VPValue *Step, DebugLoc DL, |
| 700 | VPBuilder &Builder, const VPIRFlags::WrapFlagsTy &Flags) { |
| 701 | VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion(); |
| 702 | VPBasicBlock * = LoopRegion->getEntryBasicBlock(); |
| 703 | VPValue *CanonicalIV = LoopRegion->getCanonicalIV(); |
| 704 | VPValue *BaseIV = |
| 705 | Builder.createDerivedIV(Kind, FPBinOp, Start: StartV, Current: CanonicalIV, Step, Flags); |
| 706 | |
| 707 | // Truncate BaseIV and Step to ResultTy. |
| 708 | if (ResultTy->isIntegerTy()) { |
| 709 | [[maybe_unused]] Type *BaseIVTy = BaseIV->getScalarType(); |
| 710 | assert(BaseIVTy->isIntegerTy() && "Integral BaseIV type expected" ); |
| 711 | assert(BaseIVTy->getPrimitiveSizeInBits() >= |
| 712 | ResultTy->getPrimitiveSizeInBits() && |
| 713 | "BaseIV's type must be at least as large as ResultTy" ); |
| 714 | BaseIV = Builder.createScalarZExtOrTrunc(Op: BaseIV, ResultTy, DL); |
| 715 | [[maybe_unused]] Type *StepTy = Step->getScalarType(); |
| 716 | assert(StepTy->isIntegerTy() && "Integral Step type expected" ); |
| 717 | assert(StepTy->getPrimitiveSizeInBits() >= |
| 718 | ResultTy->getPrimitiveSizeInBits() && |
| 719 | "Step's type must be at least as large as ResultTy" ); |
| 720 | auto * = |
| 721 | cast<VPBasicBlock>(Val: HeaderVPBB->getSingleHierarchicalPredecessor()); |
| 722 | VPBuilder::InsertPointGuard Guard(Builder); |
| 723 | Builder.setInsertPoint(VecPreheader); |
| 724 | Step = Builder.createScalarZExtOrTrunc(Op: Step, ResultTy, DL); |
| 725 | } |
| 726 | return Builder.createScalarIVSteps(InductionOpcode, FPBinOp, IV: BaseIV, Step, |
| 727 | VF: &Plan.getVF(), DL); |
| 728 | } |
| 729 | |
| 730 | VPValue * |
| 731 | vputils::scalarizeVPWidenPointerInduction(VPWidenPointerInductionRecipe *PtrIV, |
| 732 | VPlan &Plan, VPBuilder &Builder) { |
| 733 | VPValue *StepV = PtrIV->getStepValue(); |
| 734 | VPIRValue *StartV = Plan.getZero(Ty: StepV->getScalarType()); |
| 735 | VPScalarIVStepsRecipe *Steps = createScalarIVSteps( |
| 736 | Plan, Kind: InductionDescriptor::IK_IntInduction, InductionOpcode: Instruction::Add, FPBinOp: nullptr, |
| 737 | ResultTy: StartV->getScalarType(), StartV, Step: StepV, DL: PtrIV->getDebugLoc(), Builder); |
| 738 | |
| 739 | return Builder.createPtrAdd(Ptr: PtrIV->getStartValue(), Offset: Steps, |
| 740 | DL: PtrIV->getDebugLoc(), Name: "next.gep" ); |
| 741 | } |
| 742 | |
| 743 | bool VPBlockUtils::(const VPBlockBase *VPB, |
| 744 | const VPDominatorTree &VPDT) { |
| 745 | auto *VPBB = dyn_cast<VPBasicBlock>(Val: VPB); |
| 746 | if (!VPBB) |
| 747 | return false; |
| 748 | |
| 749 | // If VPBB is in a region R, VPBB is a loop header if R is a loop region with |
| 750 | // VPBB as its entry, i.e., free of predecessors. |
| 751 | if (auto *R = VPBB->getParent()) |
| 752 | return !R->isReplicator() && !VPBB->hasPredecessors(); |
| 753 | |
| 754 | // A header dominates its second predecessor (the latch), with the other |
| 755 | // predecessor being the preheader |
| 756 | return VPB->getPredecessors().size() == 2 && |
| 757 | VPDT.dominates(A: VPB, B: VPB->getPredecessors()[1]); |
| 758 | } |
| 759 | |
| 760 | bool VPBlockUtils::isLatch(const VPBlockBase *VPB, |
| 761 | const VPDominatorTree &VPDT) { |
| 762 | // A latch has a header as its last successor, with its other successors |
| 763 | // leaving the loop. A preheader OTOH has a header as its first (and only) |
| 764 | // successor. |
| 765 | return VPB->getNumSuccessors() >= 2 && |
| 766 | VPBlockUtils::isHeader(VPB: VPB->getSuccessors().back(), VPDT); |
| 767 | } |
| 768 | |
| 769 | std::pair<VPBasicBlock *, VPBasicBlock *> |
| 770 | VPBlockUtils::getPlainCFGHeaderAndLatch(const VPlan &Plan) { |
| 771 | VPBasicBlock * = cast<VPBasicBlock>( |
| 772 | Val: Plan.getEntry()->getNumSuccessors() == 1 |
| 773 | ? Plan.getEntry()->getSingleSuccessor() |
| 774 | : Plan.getEntry()->getSuccessors()[1]->getSingleSuccessor()); |
| 775 | assert(Header->getNumPredecessors() == 2 && |
| 776 | "Header must have exactly 2 predecessors" ); |
| 777 | auto *Latch = cast<VPBasicBlock>(Val: Header->getPredecessors()[1]); |
| 778 | return {Header, Latch}; |
| 779 | } |
| 780 | |
| 781 | VPBasicBlock *VPBlockUtils::getPlainCFGMiddleBlock(const VPlan &Plan) { |
| 782 | return cast<VPBasicBlock>(Val: Plan.getScalarPreheader()->getPredecessors()[0]); |
| 783 | } |
| 784 | |
| 785 | VPIRFlags vputils::getFlagsForInduction(const InductionDescriptor &ID, |
| 786 | const VPPhi *PhiR) { |
| 787 | if (ID.getKind() == InductionDescriptor::IK_FpInduction) |
| 788 | return ID.getInductionBinOp()->getFastMathFlags(); |
| 789 | |
| 790 | // The flags only bound the induction values if the increment directly |
| 791 | // updates PhiR. |
| 792 | VPValue *Inc = PhiR->getOperand(N: 1); |
| 793 | if (match(V: Inc, P: m_c_Add(Op0: m_Specific(VPV: PhiR), Op1: m_VPValue()))) |
| 794 | return cast<VPInstruction>(Val: Inc)->getNoWrapFlagsOrNone(); |
| 795 | |
| 796 | if (match(V: Inc, P: m_Sub(Op0: m_Specific(VPV: PhiR), Op1: m_VPValue()))) { |
| 797 | // The step of a sub induction is negated, so NUW cannot be preserved. NSW |
| 798 | // can, if the step is not the signed minimum. |
| 799 | std::optional<APInt> Step = ID.getConstStepValue(); |
| 800 | bool NSW = cast<VPInstruction>(Val: Inc)->getNoWrapFlagsOrNone().HasNSW && |
| 801 | Step && !Step->isMinSignedValue(); |
| 802 | return VPIRFlags::WrapFlagsTy(/*NUW*/ false, NSW); |
| 803 | } |
| 804 | |
| 805 | return VPIRFlags::WrapFlagsTy(false, false); |
| 806 | } |
| 807 | |
| 808 | std::optional<MemoryLocation> |
| 809 | vputils::getMemoryLocation(const VPRecipeBase &R) { |
| 810 | auto *M = dyn_cast<VPIRMetadata>(Val: &R); |
| 811 | if (!M) |
| 812 | return std::nullopt; |
| 813 | MemoryLocation Loc; |
| 814 | // Populate noalias metadata from VPIRMetadata. |
| 815 | if (MDNode *NoAliasMD = M->getMetadata(Kind: LLVMContext::MD_noalias)) |
| 816 | Loc.AATags.NoAlias = NoAliasMD; |
| 817 | if (MDNode *AliasScopeMD = M->getMetadata(Kind: LLVMContext::MD_alias_scope)) |
| 818 | Loc.AATags.Scope = AliasScopeMD; |
| 819 | return Loc; |
| 820 | } |
| 821 | |
| 822 | VPInstruction *vputils::findCanonicalIVIncrement(VPlan &Plan) { |
| 823 | VPRegionBlock *LoopRegion = Plan.getVectorLoopRegion(); |
| 824 | VPRegionValue *CanIV = LoopRegion->getCanonicalIV(); |
| 825 | assert(CanIV && "Expected loop region to have a canonical IV" ); |
| 826 | |
| 827 | VPSymbolicValue &VFxUF = Plan.getVFxUF(); |
| 828 | |
| 829 | // Check if \p Step matches the expected increment step, accounting for |
| 830 | // materialization of VFxUF and UF. |
| 831 | auto IsIncrementStep = [&](VPValue *Step) -> bool { |
| 832 | if (!VFxUF.isMaterialized()) |
| 833 | return Step == &VFxUF; |
| 834 | |
| 835 | VPSymbolicValue &UF = Plan.getUF(); |
| 836 | if (!UF.isMaterialized()) |
| 837 | return Step == &UF || |
| 838 | match(V: Step, P: m_c_Mul(Op0: m_Specific(VPV: &Plan.getUF()), Op1: m_VScale())); |
| 839 | |
| 840 | // Alias masking: step is number of active lanes of a dependence mask. |
| 841 | if (match(V: Step, P: m_ZExtOrTruncOrSelf( |
| 842 | Op0: m_VPInstruction<VPInstruction::NumActiveLanes>()))) |
| 843 | return true; |
| 844 | |
| 845 | unsigned ConcreteUF = Plan.getConcreteUF(); |
| 846 | // Fixed VF: step is just the concrete UF. |
| 847 | if (match(V: Step, P: m_SpecificInt(V: ConcreteUF))) |
| 848 | return true; |
| 849 | |
| 850 | // Scalable VF: step involves VScale. |
| 851 | if (ConcreteUF == 1) |
| 852 | return match(V: Step, P: m_VScale()); |
| 853 | if (match(V: Step, P: m_c_Mul(Op0: m_SpecificInt(V: ConcreteUF), Op1: m_VScale()))) |
| 854 | return true; |
| 855 | // mul(VScale, ConcreteUF) may have been simplified to |
| 856 | // shl(VScale, log2(ConcreteUF)) when ConcreteUF is a power of 2. |
| 857 | return isPowerOf2_32(Value: ConcreteUF) && |
| 858 | match(V: Step, P: m_Shl(Op0: m_VScale(), Op1: m_SpecificInt(V: Log2_32(Value: ConcreteUF)))); |
| 859 | }; |
| 860 | |
| 861 | VPInstruction *Increment = nullptr; |
| 862 | for (VPUser *U : CanIV->users()) { |
| 863 | VPValue *Step; |
| 864 | if (isa<VPInstruction>(Val: U) && |
| 865 | match(U, P: m_c_Add(Op0: m_Specific(VPV: CanIV), Op1: m_VPValue(V&: Step))) && |
| 866 | IsIncrementStep(Step)) { |
| 867 | assert(!Increment && "There must be a unique increment" ); |
| 868 | Increment = cast<VPInstruction>(Val: U); |
| 869 | } |
| 870 | } |
| 871 | |
| 872 | assert((!VFxUF.isMaterialized() || Increment) && |
| 873 | "After materializing VFxUF, an increment must exist" ); |
| 874 | assert((!Increment || |
| 875 | LoopRegion->hasCanonicalIVNUW() == Increment->hasNoUnsignedWrap()) && |
| 876 | "NUW flag in region and increment must match" ); |
| 877 | return Increment; |
| 878 | } |
| 879 | |
| 880 | /// Find the ComputeReductionResult recipe for \p PhiR, looking through selects |
| 881 | /// inserted for predicated reductions or tail folding. |
| 882 | VPInstruction *vputils::findComputeReductionResult(VPReductionPHIRecipe *PhiR) { |
| 883 | VPValue *BackedgeVal = PhiR->getBackedgeValue(); |
| 884 | if (auto *Res = |
| 885 | findSingleUser<VPInstruction::ComputeReductionResult>(V: BackedgeVal)) |
| 886 | return Res; |
| 887 | |
| 888 | // Look through selects inserted for tail folding or predicated reductions. |
| 889 | auto *SelR = findSingleUser<VPSingleDefRecipe>( |
| 890 | V: BackedgeVal, P: m_Select(Op0: m_VPValue(), Op1: m_VPValue(), Op2: m_VPValue())); |
| 891 | if (!SelR) |
| 892 | return nullptr; |
| 893 | return findSingleUser<VPInstruction::ComputeReductionResult>(V: SelR); |
| 894 | } |
| 895 | |
| 896 | bool vputils::isUsedByLoadStoreAddress(const VPValue *V) { |
| 897 | SmallPtrSet<const VPValue *, 4> Seen; |
| 898 | SmallVector<const VPValue *> WorkList = {V}; |
| 899 | |
| 900 | while (!WorkList.empty()) { |
| 901 | const VPValue *Cur = WorkList.pop_back_val(); |
| 902 | if (!Seen.insert(Ptr: Cur).second) |
| 903 | continue; |
| 904 | |
| 905 | auto *Blend = dyn_cast<VPBlendRecipe>(Val: Cur); |
| 906 | // Skip blends that use V only through a compare by checking if any incoming |
| 907 | // value was already visited. |
| 908 | if (Blend && none_of(Range: seq<unsigned>(Begin: 0, End: Blend->getNumIncomingValues()), |
| 909 | P: [&](unsigned I) { |
| 910 | return Seen.contains(Ptr: Blend->getIncomingValue(Idx: I)); |
| 911 | })) |
| 912 | continue; |
| 913 | |
| 914 | for (VPUser *U : Cur->users()) { |
| 915 | if (auto *InterleaveR = dyn_cast<VPInterleaveBase>(Val: U)) |
| 916 | if (InterleaveR->getAddr() == Cur) |
| 917 | return true; |
| 918 | // Cur is used as the pointer of a (possibly masked) load (operand 0) or |
| 919 | // store (operand 1). |
| 920 | if (match(U, P: m_CombineOr(Ps: m_Unary<Instruction::Load>(Op0: m_Specific(VPV: Cur)), |
| 921 | Ps: m_Binary<Instruction::Store>(Op0: m_VPValue(), |
| 922 | Op1: m_Specific(VPV: Cur))))) |
| 923 | return true; |
| 924 | if (auto *MemR = dyn_cast<VPWidenMemoryRecipe>(Val: cast<VPRecipeBase>(Val: U))) { |
| 925 | if (MemR->getAddr() == Cur && MemR->isConsecutive()) |
| 926 | return true; |
| 927 | } |
| 928 | } |
| 929 | |
| 930 | // The legacy cost model only supports scalarization loads/stores with phi |
| 931 | // addresses, if the phi is directly used as load/store address. Don't |
| 932 | // traverse further for Blends and first-order recurrence splices. |
| 933 | if (Blend || |
| 934 | match(V: Cur, |
| 935 | P: m_VPInstruction<VPInstruction::FirstOrderRecurrenceSplice>())) |
| 936 | continue; |
| 937 | |
| 938 | // Only traverse further through users that also define a value (and can |
| 939 | // thus have their own users walked). Skip when Cur is only used as mask , |
| 940 | // as well as loads: a loaded value does not depend on the load's operand. |
| 941 | for (VPUser *U : Cur->users()) { |
| 942 | auto *VPI = dyn_cast<VPInstruction>(Val: U); |
| 943 | if (VPI && VPI->getMask() == Cur && |
| 944 | none_of(Range: VPI->operandsWithoutMask(), P: equal_to(Arg&: Cur))) |
| 945 | continue; |
| 946 | if (match(U, P: m_VPInstruction<Instruction::Load>())) |
| 947 | continue; |
| 948 | if (auto *SDR = dyn_cast<VPSingleDefRecipe>(Val: U)) |
| 949 | WorkList.push_back(Elt: SDR); |
| 950 | } |
| 951 | } |
| 952 | return false; |
| 953 | } |
| 954 | |
| 955 | /// Try to find a loop-invariant IR value for \p S in the plan's entry block |
| 956 | /// that can be reused. Returns the corresponding live-in VPValue, or nullptr |
| 957 | /// if no reusable IR value is found. |
| 958 | VPValue *VPSCEVExpander::tryToReuseIRValue(const SCEV *S) { |
| 959 | if (isa<SCEVConstant, SCEVUnknown>(Val: S)) |
| 960 | return nullptr; |
| 961 | VPlan &Plan = Builder.getPlan(); |
| 962 | BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock(); |
| 963 | for (Value *V : SE.getSCEVValues(S)) { |
| 964 | // Only reuse instructions in the plan's entry block, or, when a |
| 965 | // DominatorTree is available, any instruction that dominates it. |
| 966 | // Instructions in sibling branches may not dominate the entry block. |
| 967 | auto *I = dyn_cast<Instruction>(Val: V); |
| 968 | if (!I) |
| 969 | return Plan.getOrAddLiveIn(V); |
| 970 | if (!SE.DT.dominates(A: I->getParent(), B: PH)) |
| 971 | continue; |
| 972 | Loop *IL = SE.LI.getLoopFor(BB: I->getParent()); |
| 973 | if (IL && !IL->contains(BB: PH)) |
| 974 | continue; |
| 975 | SmallVector<Instruction *> DropPoisonGeneratingInsts; |
| 976 | if (!SE.canReuseInstruction(S, I, DropPoisonGeneratingInsts)) |
| 977 | continue; |
| 978 | for (Instruction *DropI : DropPoisonGeneratingInsts) |
| 979 | SCEVExpander::dropPoisonGeneratingAnnotationsAndReinfer(SE, I: DropI); |
| 980 | return Plan.getOrAddLiveIn(V); |
| 981 | } |
| 982 | return nullptr; |
| 983 | } |
| 984 | |
| 985 | bool VPSCEVExpander::canExpandInIR(const SCEV *S) { |
| 986 | return HoistOutOf && !SafeUDivMode && SE.isLoopInvariant(S, L: HoistOutOf) && |
| 987 | SE.isGuaranteedNotToCauseUB(Op: S); |
| 988 | } |
| 989 | |
| 990 | /// Returns the sums of the operands of \p S invariant in \p L and of the |
| 991 | /// remaining operands, if there are at least 2 invariant and 1 variant |
| 992 | /// operands. |
| 993 | static std::pair<const SCEV *, const SCEV *> |
| 994 | splitInvariantSum(const SCEVAddExpr *S, const Loop *L, ScalarEvolution &SE) { |
| 995 | if (!L) |
| 996 | return {nullptr, nullptr}; |
| 997 | SmallVector<SCEVUse> InvOps, VarOps; |
| 998 | for (SCEVUse Op : S->operands()) |
| 999 | (SE.isLoopInvariant(S: Op, L) ? InvOps : VarOps).push_back(Elt: Op); |
| 1000 | if (InvOps.size() < 2 || VarOps.empty()) |
| 1001 | return {nullptr, nullptr}; |
| 1002 | return {SE.getAddExpr(Ops&: InvOps), SE.getAddExpr(Ops&: VarOps)}; |
| 1003 | } |
| 1004 | |
| 1005 | VPValue *VPSCEVExpander::expandAsPtrAdd(const SCEVNAryExpr *S) { |
| 1006 | const SCEV *Base = SE.getPointerBase(V: S); |
| 1007 | const SCEV *Offset = SE.removePointerBase(S); |
| 1008 | // If the pointer is invariant in HoistOutOf, use the sum of all invariant |
| 1009 | // operands as base, so it is hoisted whole. |
| 1010 | if (auto *AddE = dyn_cast<SCEVAddExpr>(Val: S)) { |
| 1011 | auto [InvS, VarS] = splitInvariantSum(S: AddE, L: HoistOutOf, SE); |
| 1012 | if (InvS && InvS->getType()->isPointerTy() && canExpandInIR(S: InvS)) |
| 1013 | std::tie(args&: Base, args&: Offset) = std::tie(args&: InvS, args&: VarS); |
| 1014 | } |
| 1015 | GEPNoWrapFlags GEPFlags = S->hasNoUnsignedWrap() |
| 1016 | ? GEPNoWrapFlags::noUnsignedWrap() |
| 1017 | : GEPNoWrapFlags::none(); |
| 1018 | VPValue *BaseV = expand(S: Base); |
| 1019 | VPValue *OffsetV = expand(S: Offset); |
| 1020 | return Builder.createNoWrapPtrAdd(Ptr: BaseV, Offset: OffsetV, GEPFlags, DL); |
| 1021 | } |
| 1022 | |
| 1023 | VPValue *VPSCEVExpander::expandAddOps(ArrayRef<const SCEV *> Operands, |
| 1024 | VPIRFlags::WrapFlagsTy WrapFlags) { |
| 1025 | // Non-constant-negative add operands are expanded negated and subtracted |
| 1026 | // from the running result below, instead of being negated and added. |
| 1027 | auto UseSubtract = [](const SCEV *Op) { return Op->isNonConstantNegative(); }; |
| 1028 | // Move the subtracted operands last, matching SCEVExpander's LoopCompare, so |
| 1029 | // that they don't start the running result. |
| 1030 | SmallVector<const SCEV *, 2> SCEVOps(Operands); |
| 1031 | stable_sort(Range&: SCEVOps, C: [&](const SCEV *L, const SCEV *R) { |
| 1032 | return !UseSubtract(L) && UseSubtract(R); |
| 1033 | }); |
| 1034 | SmallVector<VPValue *, 2> Ops; |
| 1035 | for (const SCEV *Op : SCEVOps) { |
| 1036 | // The first operand starts the result, so it is never subtracted. |
| 1037 | bool Negate = !Ops.empty() && UseSubtract(Op); |
| 1038 | Ops.push_back(Elt: expand(S: Negate ? SE.getNegativeSCEV(V: Op) : Op)); |
| 1039 | } |
| 1040 | VPValue *Result = Ops.front(); |
| 1041 | for (auto [Op, OpV] : drop_begin(RangeOrContainer: zip_equal(t&: SCEVOps, u&: Ops))) { |
| 1042 | if (UseSubtract(Op)) { |
| 1043 | // Result + (-Op) == Result - Op, which saves the multiply for the |
| 1044 | // negation. NSW only transfers if negating Op cannot overflow, see |
| 1045 | // ScalarEvolution::getMinusSCEV. |
| 1046 | bool HasNSW = |
| 1047 | WrapFlags.HasNSW && !SE.getSignedRangeMin(S: Op).isMinSignedValue(); |
| 1048 | Result = Builder.createOverflowingOp(Opcode: Instruction::Sub, Operands: {Result, OpV}, |
| 1049 | WrapFlags: {/*HasNUW=*/false, HasNSW}, DL); |
| 1050 | continue; |
| 1051 | } |
| 1052 | Result = Builder.createOverflowingOp(Opcode: Instruction::Add, Operands: {Result, OpV}, |
| 1053 | WrapFlags, DL); |
| 1054 | } |
| 1055 | return Result; |
| 1056 | } |
| 1057 | |
| 1058 | #ifndef NDEBUG |
| 1059 | /// Returns true if \p V dominates the insert point of \p Builder. |
| 1060 | static bool dominatesInsertPoint(const VPValue *V, const VPBuilder &Builder) { |
| 1061 | const VPRecipeBase *R = V->getDefiningRecipe(); |
| 1062 | if (!R) |
| 1063 | return true; |
| 1064 | VPDominatorTree VPDT(Builder.getPlan()); |
| 1065 | if (VPRecipeBase *InsertPt = Builder.getRecipeAtInsertPoint()) |
| 1066 | return VPDT.properlyDominates(R, InsertPt); |
| 1067 | return VPDT.dominates(R->getParent(), Builder.getInsertBlock()); |
| 1068 | } |
| 1069 | #endif |
| 1070 | |
| 1071 | VPValue *VPSCEVExpander::expand(const SCEV *S) { |
| 1072 | PointerIntPair<const SCEV *, 1, bool> Key(S, SafeUDivMode); |
| 1073 | if (VPValue *V = InsertedExpressions.lookup(Val: Key)) { |
| 1074 | assert(dominatesInsertPoint(V, Builder) && |
| 1075 | "reused expansion must dominate the insert point" ); |
| 1076 | return V; |
| 1077 | } |
| 1078 | VPValue *V = expandImpl(S); |
| 1079 | InsertedExpressions[Key] = V; |
| 1080 | return V; |
| 1081 | } |
| 1082 | |
| 1083 | VPValue *VPSCEVExpander::expandImpl(const SCEV *S) { |
| 1084 | if (VPValue *V = tryToReuseIRValue(S)) |
| 1085 | return V; |
| 1086 | |
| 1087 | if (canExpandInIR(S)) |
| 1088 | return vputils::getOrCreateVPValueForSCEVExpr(Plan&: Builder.getPlan(), Expr: S, |
| 1089 | /*ExpandInIR=*/true); |
| 1090 | |
| 1091 | switch (S->getSCEVType()) { |
| 1092 | case scConstant: |
| 1093 | return Builder.getPlan().getOrAddLiveIn(V: cast<SCEVConstant>(Val: S)->getValue()); |
| 1094 | case scUnknown: |
| 1095 | return Builder.getPlan().getOrAddLiveIn(V: cast<SCEVUnknown>(Val: S)->getValue()); |
| 1096 | case scVScale: |
| 1097 | return Builder.createVScale(ResultTy: S->getType(), DL); |
| 1098 | case scAddExpr: { |
| 1099 | auto *AddE = cast<SCEVAddExpr>(Val: S); |
| 1100 | VPIRFlags::WrapFlagsTy WrapFlags(AddE->hasNoUnsignedWrap(), |
| 1101 | AddE->hasNoSignedWrap()); |
| 1102 | |
| 1103 | // Expand pointer SCEVAddExpr as a ptradd of the pointer base and the |
| 1104 | // integer offset, matching SCEVExpander. |
| 1105 | if (S->getType()->isPointerTy()) |
| 1106 | return expandAsPtrAdd(S: AddE); |
| 1107 | |
| 1108 | // Iterate in reverse so that constants are emitted last. |
| 1109 | SmallVector<const SCEV *, 2> SCEVOps(reverse(C: AddE->operands())); |
| 1110 | // Sum the invariant operands separately, so the sum can be hoisted. |
| 1111 | auto [InvS, VarS] = splitInvariantSum(S: AddE, L: HoistOutOf, SE); |
| 1112 | if (InvS && canExpandInIR(S: InvS)) |
| 1113 | SCEVOps = {InvS, VarS}; |
| 1114 | return expandAddOps(Operands: SCEVOps, WrapFlags); |
| 1115 | } |
| 1116 | case scMulExpr: { |
| 1117 | auto *MulE = cast<SCEVMulExpr>(Val: S); |
| 1118 | VPIRFlags::WrapFlagsTy WrapFlags(MulE->hasNoUnsignedWrap(), |
| 1119 | MulE->hasNoSignedWrap()); |
| 1120 | SmallVector<VPValue *, 2> Ops; |
| 1121 | for (const SCEV *Op : reverse(C: MulE->operands())) |
| 1122 | Ops.push_back(Elt: expand(S: Op)); |
| 1123 | VPValue *Result = Ops.front(); |
| 1124 | for (VPValue *OpV : drop_begin(RangeOrContainer&: Ops)) { |
| 1125 | Result = Builder.createOverflowingOp(Opcode: Instruction::Mul, Operands: {Result, OpV}, |
| 1126 | WrapFlags, DL); |
| 1127 | } |
| 1128 | return Result; |
| 1129 | } |
| 1130 | case scUDivExpr: { |
| 1131 | auto *UDiv = cast<SCEVUDivExpr>(Val: S); |
| 1132 | VPValue *LHS = expand(S: UDiv->getLHS()); |
| 1133 | const SCEV *RHSExpr = UDiv->getRHS(); |
| 1134 | VPValue *RHS = expand(S: RHSExpr); |
| 1135 | if (SafeUDivMode) { |
| 1136 | // Make sure the UDiv's divisor is guaranteed to not be zero/poison, to |
| 1137 | // avoid UB. |
| 1138 | Type *Ty = UDiv->getType(); |
| 1139 | bool GuaranteedNotPoison = |
| 1140 | ScalarEvolution::isGuaranteedNotToBePoison(Op: RHSExpr); |
| 1141 | if (!GuaranteedNotPoison) |
| 1142 | RHS = Builder.createFreeze(Op: RHS, DL); |
| 1143 | if (!SE.isKnownNonZero(S: RHSExpr) || !GuaranteedNotPoison) |
| 1144 | RHS = Builder.createScalarIntrinsic( |
| 1145 | IntrinsicID: Intrinsic::umax, Operands: {RHS, Builder.getPlan().getConstantInt(Ty, Val: 1)}, ResultTy: Ty, |
| 1146 | DL); |
| 1147 | } |
| 1148 | return Builder.createNaryOp(Opcode: Instruction::UDiv, Operands: {LHS, RHS}, |
| 1149 | Flags: VPIRFlags::getDefaultFlags(Opcode: Instruction::UDiv), |
| 1150 | DL); |
| 1151 | } |
| 1152 | case scTruncate: |
| 1153 | case scZeroExtend: |
| 1154 | case scSignExtend: |
| 1155 | case scPtrToAddr: { |
| 1156 | auto *Cast = cast<SCEVCastExpr>(Val: S); |
| 1157 | VPValue *Op = expand(S: Cast->getOperand()); |
| 1158 | Instruction::CastOps Opcode; |
| 1159 | switch (S->getSCEVType()) { |
| 1160 | case scTruncate: |
| 1161 | Opcode = Instruction::Trunc; |
| 1162 | break; |
| 1163 | case scZeroExtend: |
| 1164 | Opcode = Instruction::ZExt; |
| 1165 | break; |
| 1166 | case scSignExtend: |
| 1167 | Opcode = Instruction::SExt; |
| 1168 | break; |
| 1169 | case scPtrToAddr: |
| 1170 | Opcode = Instruction::PtrToAddr; |
| 1171 | break; |
| 1172 | default: |
| 1173 | llvm_unreachable("Unhandled cast SCEV" ); |
| 1174 | } |
| 1175 | |
| 1176 | // For ptrtoaddr of an IR value, reuse an existing cast dominating the |
| 1177 | // entry if there is one. Otherwise leave it to SCEVExpander, which places |
| 1178 | // the cast right after the IR value's definition, so all users can share |
| 1179 | // it. |
| 1180 | if (Opcode == Instruction::PtrToAddr) { |
| 1181 | VPlan &Plan = Builder.getPlan(); |
| 1182 | BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock(); |
| 1183 | if (auto *IRV = dyn_cast<VPIRValue>(Val: Op)) { |
| 1184 | if (CastInst *CI = SCEVExpander::findReusableCastForPtrToAddr( |
| 1185 | PtrOp: IRV->getValue(), Ty: S->getType(), DL: PH->getDataLayout(), |
| 1186 | Dominates: [&](const CastInst *CI) { |
| 1187 | return SE.DT.dominates(A: CI->getParent(), B: PH); |
| 1188 | })) |
| 1189 | return Plan.getOrAddLiveIn(V: CI); |
| 1190 | return vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: S); |
| 1191 | } |
| 1192 | } |
| 1193 | |
| 1194 | std::optional<VPIRFlags> Flags; |
| 1195 | if (Opcode == Instruction::ZExt) |
| 1196 | Flags = |
| 1197 | VPIRFlags::NonNegFlagsTy(SE.isKnownNonNegative(S: Cast->getOperand())); |
| 1198 | |
| 1199 | return Builder.createScalarCast(Opcode, Op, ResultTy: S->getType(), DL, Flags); |
| 1200 | } |
| 1201 | case scUMaxExpr: |
| 1202 | case scSMaxExpr: |
| 1203 | case scUMinExpr: |
| 1204 | case scSMinExpr: |
| 1205 | case scSequentialUMinExpr: { |
| 1206 | auto *MinMax = cast<SCEVNAryExpr>(Val: S); |
| 1207 | Intrinsic::ID IntrinsicID; |
| 1208 | switch (S->getSCEVType()) { |
| 1209 | case scUMaxExpr: |
| 1210 | IntrinsicID = Intrinsic::umax; |
| 1211 | break; |
| 1212 | case scSMaxExpr: |
| 1213 | IntrinsicID = Intrinsic::smax; |
| 1214 | break; |
| 1215 | case scUMinExpr: |
| 1216 | case scSequentialUMinExpr: |
| 1217 | IntrinsicID = Intrinsic::umin; |
| 1218 | break; |
| 1219 | case scSMinExpr: |
| 1220 | IntrinsicID = Intrinsic::smin; |
| 1221 | break; |
| 1222 | default: |
| 1223 | llvm_unreachable("Unexpected min/max SCEV type" ); |
| 1224 | } |
| 1225 | // Chain operands in reverse order matching SCEVExpander's expansion of |
| 1226 | // min/max expressions. In SafeUDivMode freeze expansion results of operands |
| 1227 | // other than the first for sequential UMins, to avoid short-circuiting |
| 1228 | // divide-by-0/poison. |
| 1229 | bool IsSequential = S->getSCEVType() == scSequentialUMinExpr; |
| 1230 | Type *ResultTy = MinMax->getType(); |
| 1231 | bool PrevSafeMode = SafeUDivMode; |
| 1232 | SmallVector<VPValue *, 2> Ops; |
| 1233 | for (const SCEV *SCEVOp : reverse(C: MinMax->operands())) { |
| 1234 | bool MayShortCircuit = |
| 1235 | IsSequential && Ops.size() != MinMax->getNumOperands() - 1; |
| 1236 | SafeUDivMode = MayShortCircuit || PrevSafeMode; |
| 1237 | VPValue *OpV = expand(S: SCEVOp); |
| 1238 | SafeUDivMode = PrevSafeMode; |
| 1239 | if (MayShortCircuit) |
| 1240 | OpV = Builder.createFreeze(Op: OpV, DL); |
| 1241 | Ops.push_back(Elt: OpV); |
| 1242 | } |
| 1243 | VPValue *Result = Ops.front(); |
| 1244 | for (VPValue *Op : drop_begin(RangeOrContainer&: Ops)) { |
| 1245 | if (!ResultTy->isPointerTy()) { |
| 1246 | Result = Builder.createScalarIntrinsic(IntrinsicID, Operands: {Result, Op}, |
| 1247 | ResultTy, DL); |
| 1248 | continue; |
| 1249 | } |
| 1250 | // The min/max intrinsics don't support pointer operands, so expand |
| 1251 | // pointer-typed min/max as cmp + select, matching SCEVExpander. |
| 1252 | VPValue *Cmp = Builder.createICmp( |
| 1253 | Pred: MinMaxIntrinsic::getPredicate(ID: IntrinsicID), A: Result, B: Op, DL); |
| 1254 | Result = Builder.createSelect(Cond: Cmp, TrueVal: Result, FalseVal: Op, DL); |
| 1255 | Function &F = *Builder.getPlan().getIRFunction(); |
| 1256 | if (MDNode *MD = |
| 1257 | getExplicitlyUnknownBranchWeightsIfProfiled(F, PassName: "scev-expander" )) |
| 1258 | cast<VPInstruction>(Val: Result)->setMetadata(Kind: LLVMContext::MD_prof, Node: MD); |
| 1259 | } |
| 1260 | return Result; |
| 1261 | } |
| 1262 | case scAddRecExpr: { |
| 1263 | auto *AR = cast<SCEVAddRecExpr>(Val: S); |
| 1264 | VPlan &Plan = Builder.getPlan(); |
| 1265 | BasicBlock *PH = cast<VPIRBasicBlock>(Val: Plan.getEntry())->getIRBasicBlock(); |
| 1266 | assert(SE.DT.dominates(AR->getLoop()->getHeader(), PH) && |
| 1267 | "can only expand AddRecs for loops outside VPlan's scope" ); |
| 1268 | |
| 1269 | Type *Ty = AR->getType(); |
| 1270 | if (auto [LCSSAPhi, Diff] = SCEVExpander::findReusableLCSSAPhi(SE, S: AR, InsertBB: PH); |
| 1271 | LCSSAPhi) { |
| 1272 | VPValue *DiffV = expand(S: Diff); |
| 1273 | VPValue *BaseV = Plan.getOrAddLiveIn(V: LCSSAPhi); |
| 1274 | if (LCSSAPhi->getType()->isPointerTy()) { |
| 1275 | if (Ty->isPointerTy()) |
| 1276 | return Builder.createPtrAdd(Ptr: BaseV, Offset: DiffV, DL); |
| 1277 | BaseV = Builder.createScalarCast(Opcode: Instruction::PtrToAddr, Op: BaseV, ResultTy: Ty, DL); |
| 1278 | } |
| 1279 | return Builder.createAdd(LHS: BaseV, RHS: DiffV, DL); |
| 1280 | } |
| 1281 | |
| 1282 | // Mirror SCEVExpander::visitAddRecExpr, but only expand the canonical IV |
| 1283 | // {0,+,1} and non-affine AddRecs to IR (which will be created outside the |
| 1284 | // scope of VPlan). The AddRec is then scaled and offset using |
| 1285 | // VPInstructions. |
| 1286 | const Loop *L = AR->getLoop(); |
| 1287 | auto m_scev_CanonicalIV = // NOLINT |
| 1288 | m_scev_AffineAddRec(Op0: m_scev_Zero(), Op1: m_scev_One(), L: m_SpecificLoop(L)); |
| 1289 | if (!AR->isAffine() || match(V: AR, P: m_scev_CanonicalIV)) |
| 1290 | return vputils::getOrCreateVPValueForSCEVExpr(Plan, Expr: AR); |
| 1291 | |
| 1292 | const SCEV *Step = AR->getStepRecurrence(SE); |
| 1293 | // {0,+,F} --> {0,+,1} * F |
| 1294 | if (AR->getStart()->isZero()) { |
| 1295 | const SCEV *CanIV = |
| 1296 | SE.getAddRecExpr(Start: SE.getZero(Ty), Step: SE.getOne(Ty), L, Flags: SCEV::FlagNone); |
| 1297 | return Builder.createOverflowingOp( |
| 1298 | Opcode: Instruction::Mul, Operands: {expand(S: CanIV), expand(S: Step)}, |
| 1299 | WrapFlags: {SE.willNotOverflow(BinOp: Instruction::Mul, /*Signed=*/false, LHS: CanIV, RHS: Step), |
| 1300 | SE.willNotOverflow(BinOp: Instruction::Mul, /*Signed=*/true, LHS: CanIV, RHS: Step)}, |
| 1301 | DL); |
| 1302 | } |
| 1303 | |
| 1304 | // {X,+,F} --> X + {0,+,F} |
| 1305 | if (Ty->isPointerTy()) |
| 1306 | return expandAsPtrAdd(S: AR); |
| 1307 | VPValue *Start = expand(S: AR->getStart()); |
| 1308 | VPValue *Rest = expand(S: SE.getAddRecExpr(Start: SE.getZero(Ty), Step, L, |
| 1309 | Flags: AR->getNoWrapFlags(Mask: SCEV::FlagNW))); |
| 1310 | return Builder.createAdd(LHS: Start, RHS: Rest, DL, Name: "" , |
| 1311 | WrapFlags: {AR->hasNoUnsignedWrap(), false}); |
| 1312 | } |
| 1313 | case scCouldNotCompute: |
| 1314 | llvm_unreachable("Attempt to expand a SCEVCouldNotCompute" ); |
| 1315 | } |
| 1316 | llvm_unreachable("Unknown SCEV kind!" ); |
| 1317 | } |
| 1318 | |
| 1319 | bool vputils::isDeadRecipe(VPRecipeBase &R) { |
| 1320 | // Do remove conditional assume instructions as their conditions may be |
| 1321 | // flattened. |
| 1322 | auto *RepR = dyn_cast<VPReplicateRecipe>(Val: &R); |
| 1323 | bool IsConditionalAssume = RepR && RepR->isPredicated() && |
| 1324 | match(V: RepR, P: m_Intrinsic<Intrinsic::assume>()); |
| 1325 | if (IsConditionalAssume) |
| 1326 | return true; |
| 1327 | |
| 1328 | if (R.mayHaveSideEffects()) |
| 1329 | return false; |
| 1330 | |
| 1331 | // Forbid removing trip-count expressions. |
| 1332 | if (isa<VPExpandSCEVRecipe>(Val: R) && |
| 1333 | R.getVPSingleValue() == R.getParent()->getPlan()->getTripCount()) |
| 1334 | return false; |
| 1335 | |
| 1336 | // Recipe is dead if no user keeps the recipe alive. |
| 1337 | return all_of(Range: R.definedValues(), P: [](VPValue *V) { return V->user_empty(); }); |
| 1338 | } |
| 1339 | |
| 1340 | void vputils::recursivelyDeleteDeadRecipes(VPValue *V) { |
| 1341 | SmallVector<VPValue *> WorkList; |
| 1342 | SmallPtrSet<VPValue *, 8> Seen; |
| 1343 | WorkList.push_back(Elt: V); |
| 1344 | |
| 1345 | while (!WorkList.empty()) { |
| 1346 | VPValue *Cur = WorkList.pop_back_val(); |
| 1347 | if (!Seen.insert(Ptr: Cur).second) |
| 1348 | continue; |
| 1349 | VPRecipeBase *R = Cur->getDefiningRecipe(); |
| 1350 | if (!R) |
| 1351 | continue; |
| 1352 | if (!isDeadRecipe(R&: *R)) |
| 1353 | continue; |
| 1354 | append_range(C&: WorkList, R: R->operands()); |
| 1355 | R->eraseFromParent(); |
| 1356 | } |
| 1357 | } |
| 1358 | |
| 1359 | SmallVector<VPUser *> vputils::collectUsersRecursively(VPValue *V) { |
| 1360 | SetVector<VPUser *> Users(llvm::from_range, V->users()); |
| 1361 | for (unsigned I = 0; I != Users.size(); ++I) { |
| 1362 | VPRecipeBase *Cur = cast<VPRecipeBase>(Val: Users[I]); |
| 1363 | for (VPValue *V : Cur->definedValues()) |
| 1364 | Users.insert_range(R: V->users()); |
| 1365 | } |
| 1366 | return Users.takeVector(); |
| 1367 | } |
| 1368 | |
| 1369 | /// Returns \p Num / \p Denom as a BranchProbability, clamped so a ratio that is |
| 1370 | /// neither zero nor one does not round to zero or one. BlockFrequencyInfo also |
| 1371 | /// keeps a zero-weight edge distinguishable from an unreachable one. |
| 1372 | static BranchProbability getBranchProbabilityKeepingPartial(uint64_t Num, |
| 1373 | uint64_t Denom) { |
| 1374 | BranchProbability P = BranchProbability::getBranchProbability(Numerator: Num, Denominator: Denom); |
| 1375 | if (Num == 0 || Num == Denom) |
| 1376 | return P; |
| 1377 | return BranchProbability::getRaw(N: std::clamp( |
| 1378 | val: P.getNumerator(), lo: 1u, hi: BranchProbability::getDenominator() - 1)); |
| 1379 | } |
| 1380 | |
| 1381 | BranchProbability vputils::getExecutionProbability(BlockFrequency Freq) { |
| 1382 | return getBranchProbabilityKeepingPartial( |
| 1383 | Num: Freq.getFrequency(), |
| 1384 | Denom: BlockFrequencyInfoImplBase::BlockMass::getFull().getMass()); |
| 1385 | } |
| 1386 | |
| 1387 | /// Returns the probability of each successor edge of \p VPBB, computed via |
| 1388 | /// BranchProbabilityInfo::getEdgeProbabilitiesFromWeights from the branch |
| 1389 | /// weights recorded on its terminator, or std::nullopt if not available. |
| 1390 | static std::optional<SmallVector<BranchProbability>> |
| 1391 | getSuccessorProbabilities(const VPBasicBlock *VPBB) { |
| 1392 | // With a single successor the edge is always taken and needs no weights. |
| 1393 | if (VPBB->getSingleSuccessor()) |
| 1394 | return SmallVector<BranchProbability>{BranchProbability::getOne()}; |
| 1395 | |
| 1396 | SmallVector<uint32_t> Weights; |
| 1397 | auto *Term = dyn_cast_if_present<VPInstruction>(Val: VPBB->getTerminator()); |
| 1398 | if (!Term || !extractBranchWeights(ProfileData: Term->getBranchWeights(), Weights) || |
| 1399 | Weights.size() != VPBB->getNumSuccessors()) |
| 1400 | return std::nullopt; |
| 1401 | return BranchProbabilityInfo::getEdgeProbabilitiesFromWeights(Weights); |
| 1402 | } |
| 1403 | |
| 1404 | DenseMap<const VPBasicBlock *, std::optional<VPExecutionFrequency>> |
| 1405 | vputils::computeExecutionFrequencies(ArrayRef<VPBasicBlock *> Blocks) { |
| 1406 | using BFIBase = BlockFrequencyInfoImplBase; |
| 1407 | assert(!Blocks.empty() && "expected at least the header block" ); |
| 1408 | // Distribute the header's frequency using BFI. Nodes for blocks are numbered |
| 1409 | // in reverse post-order. Edges leaving Blocks, i.e. a plain CFG's edges to |
| 1410 | // the middle block or to an exit block, exit to a node outside the loop. |
| 1411 | BFIBase BFI; |
| 1412 | BFIBase::BlockNode (0), Outside(Blocks.size()); |
| 1413 | BFIBase::LoopData &Loop = BFI.Loops.emplace_back(args: nullptr, args&: Header); |
| 1414 | DenseMap<const VPBlockBase *, BFIBase::BlockNode> Nodes; |
| 1415 | for (auto [Idx, VPBB] : enumerate(First&: Blocks)) { |
| 1416 | Nodes[VPBB] = BFIBase::BlockNode(Idx); |
| 1417 | BFI.Working.emplace_back(args: BFIBase::BlockNode(Idx)).Loop = &Loop; |
| 1418 | } |
| 1419 | BFI.Working.emplace_back(args&: Outside); |
| 1420 | BFI.Working[Header.Index].getMass() = BFIBase::BlockMass::getFull(); |
| 1421 | |
| 1422 | // Keep track nodes reached via an edge without branch weighs or with |
| 1423 | // estimated ones |
| 1424 | SmallVector<bool> IsUnknown(Blocks.size()), IsEstimated(Blocks.size()); |
| 1425 | for (auto [Idx, VPBB] : enumerate(First&: Blocks)) { |
| 1426 | BFIBase::BlockNode Node(Idx); |
| 1427 | auto Probs = getSuccessorProbabilities(VPBB); |
| 1428 | auto *Term = dyn_cast_if_present<VPInstruction>(Val: VPBB->getTerminator()); |
| 1429 | bool TermIsEstimated = Term && Term->hasEstimatedBranchWeights(); |
| 1430 | BFIBase::Distribution Dist; |
| 1431 | for (auto [SuccIdx, Succ] : enumerate(First&: VPBB->getSuccessors())) { |
| 1432 | BFIBase::BlockNode SuccNode = Nodes.lookup_or(Val: Succ, Default&: Outside); |
| 1433 | if (SuccNode != Header && SuccNode != Outside) { |
| 1434 | IsUnknown[SuccNode.Index] |= IsUnknown[Idx] || !Probs; |
| 1435 | IsEstimated[SuccNode.Index] |= IsEstimated[Idx] || TermIsEstimated; |
| 1436 | } |
| 1437 | if (Probs) |
| 1438 | BFI.addToDist(Dist, OuterLoop: &Loop, Pred: Node, Succ: SuccNode, |
| 1439 | Weight: getWeightFromBranchProb(Prob: (*Probs)[SuccIdx])); |
| 1440 | } |
| 1441 | if (Probs) |
| 1442 | BFI.distributeMass(Source: Node, OuterLoop: &Loop, Dist); |
| 1443 | } |
| 1444 | |
| 1445 | // Round frequencies up to at least 1, so all edges are reached with a |
| 1446 | // non-zero frequency, to distinguish rarely executed blocks from unreachable |
| 1447 | // ones. blocks distinguishable from unreachable ones. |
| 1448 | DenseMap<const VPBasicBlock *, std::optional<VPExecutionFrequency>> |
| 1449 | Frequencies; |
| 1450 | for (auto [Idx, VPBB] : enumerate(First&: Blocks)) { |
| 1451 | std::optional<VPExecutionFrequency> &Freq = Frequencies[VPBB]; |
| 1452 | if (IsUnknown[Idx]) |
| 1453 | continue; |
| 1454 | uint64_t Mass = BFI.Working[Idx].getMass().getMass(); |
| 1455 | Freq.emplace(args: BlockFrequency(std::max<uint64_t>(a: Mass, b: 1)), args&: IsEstimated[Idx]); |
| 1456 | } |
| 1457 | return Frequencies; |
| 1458 | } |
| 1459 | |
| 1460 | VPIRValue *vputils::tryToFoldLiveIns(VPSingleDefRecipe &R, |
| 1461 | ArrayRef<VPValue *> Operands, |
| 1462 | const DataLayout &DL) { |
| 1463 | auto OpcodeOrIID = getOpcodeOrIntrinsicID(V: &R); |
| 1464 | if (!OpcodeOrIID) |
| 1465 | return nullptr; |
| 1466 | |
| 1467 | SmallVector<Value *, 4> Ops; |
| 1468 | for (VPValue *Op : Operands) { |
| 1469 | VPValue *Candidate = Op; |
| 1470 | match(V: Op, P: m_Broadcast(Op0: m_VPValue(V&: Candidate))); |
| 1471 | if (!match(V: Candidate, P: m_LiveIn())) |
| 1472 | return nullptr; |
| 1473 | Value *V = Candidate->getUnderlyingValue(); |
| 1474 | if (!V) |
| 1475 | return nullptr; |
| 1476 | Ops.push_back(Elt: V); |
| 1477 | } |
| 1478 | |
| 1479 | VPlan &Plan = *R.getParent()->getPlan(); |
| 1480 | auto FoldToIRValue = [&]() -> Value * { |
| 1481 | InstSimplifyFolder Folder(DL); |
| 1482 | if (OpcodeOrIID->first) { |
| 1483 | // VPInstructions store the called intrinsic as last operand. |
| 1484 | if (isa<VPInstruction>(Val: R)) |
| 1485 | Ops.pop_back(); |
| 1486 | |
| 1487 | auto *RFlags = dyn_cast<VPRecipeWithIRFlags>(Val: &R); |
| 1488 | return Folder.FoldIntrinsic(ID: OpcodeOrIID->second, Ops, Ty: R.getScalarType(), |
| 1489 | FMF: RFlags ? RFlags->getFastMathFlagsOrNone() |
| 1490 | : FastMathFlags()); |
| 1491 | } |
| 1492 | unsigned Opcode = OpcodeOrIID->second; |
| 1493 | if (Instruction::isBinaryOp(Opcode)) |
| 1494 | return Folder.FoldBinOp(Opc: static_cast<Instruction::BinaryOps>(Opcode), |
| 1495 | LHS: Ops[0], RHS: Ops[1]); |
| 1496 | if (Instruction::isCast(Opcode)) |
| 1497 | return Folder.FoldCast(Op: static_cast<Instruction::CastOps>(Opcode), V: Ops[0], |
| 1498 | DestTy: R.getVPSingleValue()->getScalarType()); |
| 1499 | switch (Opcode) { |
| 1500 | case VPInstruction::Not: |
| 1501 | return Folder.FoldBinOp(Opc: Instruction::BinaryOps::Xor, LHS: Ops[0], |
| 1502 | RHS: Constant::getAllOnesValue(Ty: Ops[0]->getType())); |
| 1503 | case Instruction::Select: |
| 1504 | return Folder.FoldSelect(C: Ops[0], True: Ops[1], False: Ops[2]); |
| 1505 | case Instruction::ICmp: |
| 1506 | case Instruction::FCmp: |
| 1507 | return Folder.FoldCmp(P: cast<VPRecipeWithIRFlags>(Val&: R).getPredicate(), LHS: Ops[0], |
| 1508 | RHS: Ops[1]); |
| 1509 | case Instruction::GetElementPtr: { |
| 1510 | auto &RFlags = cast<VPRecipeWithIRFlags>(Val&: R); |
| 1511 | auto *GEP = cast<GetElementPtrInst>(Val: RFlags.getUnderlyingInstr()); |
| 1512 | return Folder.FoldGEP(DL, Ty: GEP->getSourceElementType(), Ptr: Ops[0], |
| 1513 | IdxList: drop_begin(RangeOrContainer&: Ops), NW: RFlags.getGEPNoWrapFlags()); |
| 1514 | } |
| 1515 | case VPInstruction::PtrAdd: |
| 1516 | case VPInstruction::WidePtrAdd: |
| 1517 | return Folder.FoldGEP(DL, Ty: IntegerType::getInt8Ty(C&: Plan.getContext()), |
| 1518 | Ptr: Ops[0], IdxList: Ops[1], |
| 1519 | NW: cast<VPRecipeWithIRFlags>(Val&: R).getGEPNoWrapFlags()); |
| 1520 | // An extract of a live-in is an extract of a broadcast, so return the |
| 1521 | // broadcasted element. |
| 1522 | case Instruction::ExtractElement: |
| 1523 | assert(!Ops[0]->getType()->isVectorTy() && "Live-ins should be scalar" ); |
| 1524 | return Ops[0]; |
| 1525 | case VPInstruction::ActiveLaneMask: |
| 1526 | case VPInstruction::WideActiveLaneMask: { |
| 1527 | uint64_t Multiplier = 1; |
| 1528 | if (Opcode == VPInstruction::WideActiveLaneMask) { |
| 1529 | // Optimizing WideALM can only happen after the Plan is unrolled. |
| 1530 | if (!Plan.isUnrolled()) |
| 1531 | return nullptr; |
| 1532 | |
| 1533 | Multiplier = cast<ConstantInt>(Val: Ops[2])->getZExtValue(); |
| 1534 | |
| 1535 | // TODO: We can't fold if any users require a wide value. |
| 1536 | if (Multiplier != 1 && |
| 1537 | !all_of(Range: R.users(), P: match_fn(P: m_ExtractVectorForPart()))) |
| 1538 | return nullptr; |
| 1539 | |
| 1540 | Ops.pop_back(); |
| 1541 | } |
| 1542 | |
| 1543 | // We rely on the fact that different VPlans are created for the |
| 1544 | // fixed-vector and scalable-vector cases. |
| 1545 | ElementCount MaxVF = |
| 1546 | *max_element(Range: Plan.vectorFactors(), C: ElementCount::isKnownLT) * |
| 1547 | Multiplier; |
| 1548 | |
| 1549 | Type *I1Ty = IntegerType::getInt1Ty(C&: Plan.getContext()); |
| 1550 | if (auto *C = dyn_cast_if_present<Constant>(Val: Folder.FoldIntrinsic( |
| 1551 | ID: Intrinsic::get_active_lane_mask, Ops, |
| 1552 | Ty: VectorType::get(ElementType: I1Ty, EC: MaxVF), FMF: {}, CtxF: Plan.getIRFunction()))) { |
| 1553 | // We cannot handle vector constants that are not all-true or all-false, |
| 1554 | // because they would not be collapsable to a scalar constant, that |
| 1555 | // would be necessary for live-in simplification. |
| 1556 | if (C->isOneValue()) |
| 1557 | return ConstantInt::getTrue(Ty: I1Ty); |
| 1558 | if (C->isNullValue()) |
| 1559 | return ConstantInt::getFalse(Ty: I1Ty); |
| 1560 | } |
| 1561 | } |
| 1562 | } |
| 1563 | return nullptr; |
| 1564 | }; |
| 1565 | |
| 1566 | if (Value *V = FoldToIRValue()) |
| 1567 | return Plan.getOrAddLiveIn(V); |
| 1568 | return nullptr; |
| 1569 | } |
| 1570 | |
| 1571 | void vputils::detail::pullOutPermutationsImpl( |
| 1572 | VPlan &Plan, function_ref<VPValue *(VPValue *Op)> MatchPerm, |
| 1573 | function_ref<VPSingleDefRecipe *(VPSingleDefRecipe *X)> BuildPerm) { |
| 1574 | for (VPBasicBlock *VPBB : VPBlockUtils::blocksOnly<VPBasicBlock>( |
| 1575 | Range: vp_depth_first_deep(G: Plan.getEntry()))) { |
| 1576 | for (VPSingleDefRecipe &Def : |
| 1577 | make_early_inc_range(Range: make_isa_range<VPSingleDefRecipe>(Range&: *VPBB))) { |
| 1578 | if (!isElementwise(V: &Def)) |
| 1579 | continue; |
| 1580 | |
| 1581 | // At least one of the ops must be a permutation. |
| 1582 | if (none_of(Range: Def.operands(), P: MatchPerm)) |
| 1583 | continue; |
| 1584 | |
| 1585 | // All operands must be a single-use permutation or a live in (splat). |
| 1586 | if (!all_of(Range: Def.operands(), P: [&MatchPerm](VPValue *Op) { |
| 1587 | return (Op->hasOneUse() && MatchPerm(Op)) || match(V: Op, P: m_LiveIn()); |
| 1588 | })) |
| 1589 | continue; |
| 1590 | |
| 1591 | // Remove the inner permutations. |
| 1592 | for (unsigned I = 0, E = Def.getNumOperands(); I != E; ++I) |
| 1593 | if (VPValue *X = MatchPerm(Def.getOperand(N: I))) |
| 1594 | Def.setOperand(I, New: X); |
| 1595 | |
| 1596 | VPSingleDefRecipe *Res = BuildPerm(&Def); |
| 1597 | Res->insertAfter(InsertPos: &Def); |
| 1598 | Def.replaceUsesWithIf(New: Res, ShouldReplace: not_equal_to(Arg&: Res)); |
| 1599 | } |
| 1600 | } |
| 1601 | } |
| 1602 | |
| 1603 | // Implements the algorithm described in "Simple and Efficient Construction of |
| 1604 | // Static Single Assignment Form" by Braun et al. |
| 1605 | VPValue *vputils::reconstructSSA(VPBasicBlock *VPBB, |
| 1606 | DenseMap<VPBasicBlock *, VPValue *> &Defs) { |
| 1607 | assert(!Defs.empty() && "Defs shouldn't be empty" ); |
| 1608 | assert( |
| 1609 | is_contained(vp_depth_first_shallow(VPBB->getPlan()->getEntry()), VPBB) && |
| 1610 | "VPBB isn't reachable from entry" ); |
| 1611 | if (VPValue *Def = Defs.lookup(Val: VPBB)) |
| 1612 | return Def; |
| 1613 | // If the entry block is reached and there's still no def, then Defs is |
| 1614 | // missing a definition that covers this path. |
| 1615 | assert(VPBB->getNumPredecessors() && "Not all paths have def" ); |
| 1616 | |
| 1617 | if (VPBlockBase *Pred = VPBB->getSinglePredecessor()) |
| 1618 | return reconstructSSA(VPBB: cast<VPBasicBlock>(Val: Pred), Defs); |
| 1619 | |
| 1620 | // Multiple predecessors, create a join. |
| 1621 | Type *Ty = Defs.begin()->second->getScalarType(); |
| 1622 | VPPhi *Phi = VPBuilder(VPBB->getFirstNonPhi()) |
| 1623 | .createScalarPhi(IncomingValues: {}, DL: DebugLoc::getUnknown(), Name: "" , Flags: {}, ResultTy: Ty); |
| 1624 | Defs[VPBB] = Phi; |
| 1625 | for (auto *Pred : VPBB->predecessors()) |
| 1626 | Phi->addIncoming(IncomingV: reconstructSSA(VPBB: cast<VPBasicBlock>(Val: Pred), Defs)); |
| 1627 | |
| 1628 | // Fold away trivial phis. |
| 1629 | // TODO: Remove phi users which have become trivial too. |
| 1630 | if (all_equal(Range: Phi->incoming_values())) { |
| 1631 | VPValue *Common = Phi->getIncomingValue(Idx: 0); |
| 1632 | Phi->replaceAllUsesWith(New: Common); |
| 1633 | for (auto &[_, V] : Defs) |
| 1634 | if (V == Phi) |
| 1635 | V = Common; |
| 1636 | Defs[VPBB] = Common; |
| 1637 | Phi->eraseFromParent(); |
| 1638 | return Common; |
| 1639 | } |
| 1640 | |
| 1641 | return Phi; |
| 1642 | } |
| 1643 | |