diff options
Diffstat (limited to 'llvm/lib/Transforms/InstCombine/InstructionCombining.cpp')
| -rw-r--r-- | llvm/lib/Transforms/InstCombine/InstructionCombining.cpp | 318 |
1 files changed, 161 insertions, 157 deletions
diff --git a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp index 5ee3bb1abe86..c2f045a2ab02 100644 --- a/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp +++ b/llvm/lib/Transforms/InstCombine/InstructionCombining.cpp @@ -2027,9 +2027,7 @@ Instruction *InstCombinerImpl::foldOpIntoPhi(Instruction &I, PHINode *PN, } if (OneUse) { - replaceAllDbgUsesWith(const_cast<PHINode &>(*PN), - const_cast<PHINode &>(*NewPN), - const_cast<PHINode &>(*PN), DT); + replaceAllDbgUsesWith(*PN, *NewPN, *PN, DT); } return replaceInstUsesWith(I, NewPN); } @@ -2570,7 +2568,7 @@ Instruction *InstCombinerImpl::narrowMathIfNoOverflow(BinaryOperator &BO) { Constant *WideC; if (!Op0->hasOneUse() || !match(Op1, m_Constant(WideC))) return nullptr; - Constant *NarrowC = getLosslessTrunc(WideC, X->getType(), CastOpc); + Constant *NarrowC = getLosslessInvCast(WideC, X->getType(), CastOpc, DL); if (!NarrowC) return nullptr; Y = NarrowC; @@ -2676,6 +2674,62 @@ static Instruction *canonicalizeGEPOfConstGEPI8(GetElementPtrInst &GEP, return nullptr; } +/// Combine constant offsets separated by variable offsets. +/// ptradd (ptradd (ptradd p, C1), x), C2 -> ptradd (ptradd p, x), C1+C2 +static Instruction *combineConstantOffsets(GetElementPtrInst &GEP, + InstCombinerImpl &IC) { + if (!GEP.hasAllConstantIndices()) + return nullptr; + + GEPNoWrapFlags NW = GEPNoWrapFlags::all(); + SmallVector<GetElementPtrInst *> Skipped; + auto *InnerGEP = dyn_cast<GetElementPtrInst>(GEP.getPointerOperand()); + while (true) { + if (!InnerGEP) + return nullptr; + + NW = NW.intersectForReassociate(InnerGEP->getNoWrapFlags()); + if (InnerGEP->hasAllConstantIndices()) + break; + + if (!InnerGEP->hasOneUse()) + return nullptr; + + Skipped.push_back(InnerGEP); + InnerGEP = dyn_cast<GetElementPtrInst>(InnerGEP->getPointerOperand()); + } + + // The two constant offset GEPs are directly adjacent: Let normal offset + // merging handle it. + if (Skipped.empty()) + return nullptr; + + // FIXME: This one-use check is not strictly necessary. Consider relaxing it + // if profitable. + if (!InnerGEP->hasOneUse()) + return nullptr; + + // Don't bother with vector splats. + Type *Ty = GEP.getType(); + if (InnerGEP->getType() != Ty) + return nullptr; + + const DataLayout &DL = IC.getDataLayout(); + APInt Offset(DL.getIndexTypeSizeInBits(Ty), 0); + if (!GEP.accumulateConstantOffset(DL, Offset) || + !InnerGEP->accumulateConstantOffset(DL, Offset)) + return nullptr; + + IC.replaceOperand(*Skipped.back(), 0, InnerGEP->getPointerOperand()); + for (GetElementPtrInst *SkippedGEP : Skipped) + SkippedGEP->setNoWrapFlags(NW); + + return IC.replaceInstUsesWith( + GEP, + IC.Builder.CreatePtrAdd(Skipped.front(), IC.Builder.getInt(Offset), "", + NW.intersectForOffsetAdd(GEP.getNoWrapFlags()))); +} + Instruction *InstCombinerImpl::visitGEPOfGEP(GetElementPtrInst &GEP, GEPOperator *Src) { // Combine Indices - If the source pointer to this getelementptr instruction @@ -2687,125 +2741,56 @@ Instruction *InstCombinerImpl::visitGEPOfGEP(GetElementPtrInst &GEP, if (auto *I = canonicalizeGEPOfConstGEPI8(GEP, Src, *this)) return I; - // For constant GEPs, use a more general offset-based folding approach. - Type *PtrTy = Src->getType()->getScalarType(); - if (GEP.hasAllConstantIndices() && - (Src->hasOneUse() || Src->hasAllConstantIndices())) { - // Split Src into a variable part and a constant suffix. - gep_type_iterator GTI = gep_type_begin(*Src); - Type *BaseType = GTI.getIndexedType(); - bool IsFirstType = true; - unsigned NumVarIndices = 0; - for (auto Pair : enumerate(Src->indices())) { - if (!isa<ConstantInt>(Pair.value())) { - BaseType = GTI.getIndexedType(); - IsFirstType = false; - NumVarIndices = Pair.index() + 1; - } - ++GTI; - } - - // Determine the offset for the constant suffix of Src. - APInt Offset(DL.getIndexTypeSizeInBits(PtrTy), 0); - if (NumVarIndices != Src->getNumIndices()) { - // FIXME: getIndexedOffsetInType() does not handled scalable vectors. - if (BaseType->isScalableTy()) - return nullptr; - - SmallVector<Value *> ConstantIndices; - if (!IsFirstType) - ConstantIndices.push_back( - Constant::getNullValue(Type::getInt32Ty(GEP.getContext()))); - append_range(ConstantIndices, drop_begin(Src->indices(), NumVarIndices)); - Offset += DL.getIndexedOffsetInType(BaseType, ConstantIndices); - } - - // Add the offset for GEP (which is fully constant). - if (!GEP.accumulateConstantOffset(DL, Offset)) - return nullptr; - - // Convert the total offset back into indices. - SmallVector<APInt> ConstIndices = - DL.getGEPIndicesForOffset(BaseType, Offset); - if (!Offset.isZero() || (!IsFirstType && !ConstIndices[0].isZero())) - return nullptr; - - GEPNoWrapFlags NW = getMergedGEPNoWrapFlags(*Src, *cast<GEPOperator>(&GEP)); - SmallVector<Value *> Indices( - drop_end(Src->indices(), Src->getNumIndices() - NumVarIndices)); - for (const APInt &Idx : drop_begin(ConstIndices, !IsFirstType)) { - Indices.push_back(ConstantInt::get(GEP.getContext(), Idx)); - // Even if the total offset is inbounds, we may end up representing it - // by first performing a larger negative offset, and then a smaller - // positive one. The large negative offset might go out of bounds. Only - // preserve inbounds if all signs are the same. - if (Idx.isNonNegative() != ConstIndices[0].isNonNegative()) - NW = NW.withoutNoUnsignedSignedWrap(); - if (!Idx.isNonNegative()) - NW = NW.withoutNoUnsignedWrap(); - } - - return replaceInstUsesWith( - GEP, Builder.CreateGEP(Src->getSourceElementType(), Src->getOperand(0), - Indices, "", NW)); - } + if (auto *I = combineConstantOffsets(GEP, *this)) + return I; if (Src->getResultElementType() != GEP.getSourceElementType()) return nullptr; - SmallVector<Value*, 8> Indices; - // Find out whether the last index in the source GEP is a sequential idx. bool EndsWithSequential = false; for (gep_type_iterator I = gep_type_begin(*Src), E = gep_type_end(*Src); I != E; ++I) EndsWithSequential = I.isSequential(); + if (!EndsWithSequential) + return nullptr; - // Can we combine the two pointer arithmetics offsets? - if (EndsWithSequential) { - // Replace: gep (gep %P, long B), long A, ... - // With: T = long A+B; gep %P, T, ... - Value *SO1 = Src->getOperand(Src->getNumOperands()-1); - Value *GO1 = GEP.getOperand(1); - - // If they aren't the same type, then the input hasn't been processed - // by the loop above yet (which canonicalizes sequential index types to - // intptr_t). Just avoid transforming this until the input has been - // normalized. - if (SO1->getType() != GO1->getType()) - return nullptr; + // Replace: gep (gep %P, long B), long A, ... + // With: T = long A+B; gep %P, T, ... + Value *SO1 = Src->getOperand(Src->getNumOperands() - 1); + Value *GO1 = GEP.getOperand(1); - Value *Sum = - simplifyAddInst(GO1, SO1, false, false, SQ.getWithInstruction(&GEP)); - // Only do the combine when we are sure the cost after the - // merge is never more than that before the merge. - if (Sum == nullptr) - return nullptr; + // If they aren't the same type, then the input hasn't been processed + // by the loop above yet (which canonicalizes sequential index types to + // intptr_t). Just avoid transforming this until the input has been + // normalized. + if (SO1->getType() != GO1->getType()) + return nullptr; - Indices.append(Src->op_begin()+1, Src->op_end()-1); - Indices.push_back(Sum); - Indices.append(GEP.op_begin()+2, GEP.op_end()); - } else if (isa<Constant>(*GEP.idx_begin()) && - cast<Constant>(*GEP.idx_begin())->isNullValue() && - Src->getNumOperands() != 1) { - // Otherwise we can do the fold if the first index of the GEP is a zero - Indices.append(Src->op_begin()+1, Src->op_end()); - Indices.append(GEP.idx_begin()+1, GEP.idx_end()); - } - - // Don't create GEPs with more than one variable index. - unsigned NumVarIndices = - count_if(Indices, [](Value *Idx) { return !isa<Constant>(Idx); }); - if (NumVarIndices > 1) + Value *Sum = + simplifyAddInst(GO1, SO1, false, false, SQ.getWithInstruction(&GEP)); + // Only do the combine when we are sure the cost after the + // merge is never more than that before the merge. + if (Sum == nullptr) return nullptr; - if (!Indices.empty()) - return replaceInstUsesWith( - GEP, Builder.CreateGEP( - Src->getSourceElementType(), Src->getOperand(0), Indices, "", - getMergedGEPNoWrapFlags(*Src, *cast<GEPOperator>(&GEP)))); + SmallVector<Value *, 8> Indices; + Indices.append(Src->op_begin() + 1, Src->op_end() - 1); + Indices.push_back(Sum); + Indices.append(GEP.op_begin() + 2, GEP.op_end()); - return nullptr; + // Don't create GEPs with more than one non-zero index. + unsigned NumNonZeroIndices = count_if(Indices, [](Value *Idx) { + auto *C = dyn_cast<Constant>(Idx); + return !C || !C->isNullValue(); + }); + if (NumNonZeroIndices > 1) + return nullptr; + + return replaceInstUsesWith( + GEP, Builder.CreateGEP( + Src->getSourceElementType(), Src->getOperand(0), Indices, "", + getMergedGEPNoWrapFlags(*Src, *cast<GEPOperator>(&GEP)))); } Value *InstCombiner::getFreelyInvertedImpl(Value *V, bool WillInvertAllUses, @@ -3238,6 +3223,19 @@ Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) { drop_end(Indices), "", GEP.getNoWrapFlags())); } + // Strip leading zero indices. + auto *FirstIdx = dyn_cast<Constant>(Indices.front()); + if (FirstIdx && FirstIdx->isNullValue() && + !FirstIdx->getType()->isVectorTy()) { + gep_type_iterator GTI = gep_type_begin(GEP); + ++GTI; + if (!GTI.isStruct()) + return replaceInstUsesWith(GEP, Builder.CreateGEP(GTI.getIndexedType(), + GEP.getPointerOperand(), + drop_begin(Indices), "", + GEP.getNoWrapFlags())); + } + // Scalarize vector operands; prefer splat-of-gep.as canonical form. // Note that this looses information about undef lanes; we run it after // demanded bits to partially mitigate that loss. @@ -3264,17 +3262,18 @@ Instruction *InstCombinerImpl::visitGetElementPtrInst(GetElementPtrInst &GEP) { return replaceInstUsesWith(GEP, Res); } - bool SeenVarIndex = false; + bool SeenNonZeroIndex = false; for (auto [IdxNum, Idx] : enumerate(Indices)) { - if (isa<Constant>(Idx)) + auto *C = dyn_cast<Constant>(Idx); + if (C && C->isNullValue()) continue; - if (!SeenVarIndex) { - SeenVarIndex = true; + if (!SeenNonZeroIndex) { + SeenNonZeroIndex = true; continue; } - // GEP has multiple variable indices: Split it. + // GEP has multiple non-zero indices: Split it. ArrayRef<Value *> FrontIndices = ArrayRef(Indices).take_front(IdxNum); Value *FrontGEP = Builder.CreateGEP(GEPEltType, PtrOp, FrontIndices, @@ -4961,63 +4960,68 @@ Instruction *InstCombinerImpl::visitLandingPadInst(LandingPadInst &LI) { Value * InstCombinerImpl::pushFreezeToPreventPoisonFromPropagating(FreezeInst &OrigFI) { // Try to push freeze through instructions that propagate but don't produce - // poison as far as possible. If an operand of freeze follows three - // conditions 1) one-use, 2) does not produce poison, and 3) has all but one - // guaranteed-non-poison operands then push the freeze through to the one - // operand that is not guaranteed non-poison. The actual transform is as - // follows. - // Op1 = ... ; Op1 can be posion - // Op0 = Inst(Op1, NonPoisonOps...) ; Op0 has only one use and only have - // ; single guaranteed-non-poison operands + // poison as far as possible. If an operand of freeze does not produce poison + // then push the freeze through to the operands that are not guaranteed + // non-poison. The actual transform is as follows. + // Op1 = ... ; Op1 can be poison + // Op0 = Inst(Op1, NonPoisonOps...) // ... = Freeze(Op0) // => // Op1 = ... // Op1.fr = Freeze(Op1) // ... = Inst(Op1.fr, NonPoisonOps...) - auto *OrigOp = OrigFI.getOperand(0); - auto *OrigOpInst = dyn_cast<Instruction>(OrigOp); - // While we could change the other users of OrigOp to use freeze(OrigOp), that - // potentially reduces their optimization potential, so let's only do this iff - // the OrigOp is only used by the freeze. - if (!OrigOpInst || !OrigOpInst->hasOneUse() || isa<PHINode>(OrigOp)) - return nullptr; + auto CanPushFreeze = [](Value *V) { + if (!isa<Instruction>(V) || isa<PHINode>(V)) + return false; - // We can't push the freeze through an instruction which can itself create - // poison. If the only source of new poison is flags, we can simply - // strip them (since we know the only use is the freeze and nothing can - // benefit from them.) - if (canCreateUndefOrPoison(cast<Operator>(OrigOp), - /*ConsiderFlagsAndMetadata*/ false)) - return nullptr; + // We can't push the freeze through an instruction which can itself create + // poison. If the only source of new poison is flags, we can simply + // strip them (since we know the only use is the freeze and nothing can + // benefit from them.) + return !canCreateUndefOrPoison(cast<Operator>(V), + /*ConsiderFlagsAndMetadata*/ false); + }; - // If operand is guaranteed not to be poison, there is no need to add freeze - // to the operand. So we first find the operand that is not guaranteed to be - // poison. - Value *MaybePoisonOperand = nullptr; - for (Value *V : OrigOpInst->operands()) { - if (isa<MetadataAsValue>(V) || isGuaranteedNotToBeUndefOrPoison(V) || - // Treat identical operands as a single operand. - (MaybePoisonOperand && MaybePoisonOperand == V)) + // Pushing freezes up long instruction chains can be expensive. Instead, + // we directly push the freeze all the way to the leaves. However, we leave + // deduplication of freezes on the same value for freezeOtherUses(). + Use *OrigUse = &OrigFI.getOperandUse(0); + SmallPtrSet<Instruction *, 8> Visited; + SmallVector<Use *, 8> Worklist; + Worklist.push_back(OrigUse); + while (!Worklist.empty()) { + auto *U = Worklist.pop_back_val(); + Value *V = U->get(); + if (!CanPushFreeze(V)) { + // If we can't push through the original instruction, abort the transform. + if (U == OrigUse) + return nullptr; + + auto *UserI = cast<Instruction>(U->getUser()); + Builder.SetInsertPoint(UserI); + Value *Frozen = Builder.CreateFreeze(V, V->getName() + ".fr"); + U->set(Frozen); continue; - if (!MaybePoisonOperand) - MaybePoisonOperand = V; - else - return nullptr; - } + } - OrigOpInst->dropPoisonGeneratingAnnotations(); + auto *I = cast<Instruction>(V); + if (!Visited.insert(I).second) + continue; - // If all operands are guaranteed to be non-poison, we can drop freeze. - if (!MaybePoisonOperand) - return OrigOp; + // reverse() to emit freezes in a more natural order. + for (Use &Op : reverse(I->operands())) { + Value *OpV = Op.get(); + if (isa<MetadataAsValue>(OpV) || isGuaranteedNotToBeUndefOrPoison(OpV)) + continue; + Worklist.push_back(&Op); + } - Builder.SetInsertPoint(OrigOpInst); - Value *FrozenMaybePoisonOperand = Builder.CreateFreeze( - MaybePoisonOperand, MaybePoisonOperand->getName() + ".fr"); + I->dropPoisonGeneratingAnnotations(); + this->Worklist.add(I); + } - OrigOpInst->replaceUsesOfWith(MaybePoisonOperand, FrozenMaybePoisonOperand); - return OrigOp; + return OrigUse->get(); } Instruction *InstCombinerImpl::foldFreezeIntoRecurrence(FreezeInst &FI, |