diff options
Diffstat (limited to 'llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp')
| -rw-r--r-- | llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp | 247 |
1 files changed, 96 insertions, 151 deletions
diff --git a/llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp b/llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp index 06deaf3c4f9a..bccf94fc217f 100644 --- a/llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp +++ b/llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp @@ -15,6 +15,7 @@ // //===----------------------------------------------------------------------===// +#include "llvm/IR/Instructions.h" #include "llvm/InitializePasses.h" #define AA_NAME "alignment-from-assumptions" #define DEBUG_TYPE AA_NAME @@ -30,6 +31,7 @@ #include "llvm/IR/Constant.h" #include "llvm/IR/Dominators.h" #include "llvm/IR/Instruction.h" +#include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/Intrinsics.h" #include "llvm/IR/Module.h" #include "llvm/Support/Debug.h" @@ -90,9 +92,9 @@ FunctionPass *llvm::createAlignmentFromAssumptionsPass() { // to a constant. Using SCEV to compute alignment handles the case where // DiffSCEV is a recurrence with constant start such that the aligned offset // is constant. e.g. {16,+,32} % 32 -> 16. -static unsigned getNewAlignmentDiff(const SCEV *DiffSCEV, - const SCEV *AlignSCEV, - ScalarEvolution *SE) { +static MaybeAlign getNewAlignmentDiff(const SCEV *DiffSCEV, + const SCEV *AlignSCEV, + ScalarEvolution *SE) { // DiffUnits = Diff % int64_t(Alignment) const SCEV *DiffUnitsSCEV = SE->getURemExpr(DiffSCEV, AlignSCEV); @@ -107,26 +109,30 @@ static unsigned getNewAlignmentDiff(const SCEV *DiffSCEV, // displaced pointer has the same alignment as the aligned pointer, so // return the alignment value. if (!DiffUnits) - return (unsigned) - cast<SCEVConstant>(AlignSCEV)->getValue()->getSExtValue(); + return cast<SCEVConstant>(AlignSCEV)->getValue()->getAlignValue(); // If the displacement is not an exact multiple, but the remainder is a // constant, then return this remainder (but only if it is a power of 2). uint64_t DiffUnitsAbs = std::abs(DiffUnits); if (isPowerOf2_64(DiffUnitsAbs)) - return (unsigned) DiffUnitsAbs; + return Align(DiffUnitsAbs); } - return 0; + return None; } // There is an address given by an offset OffSCEV from AASCEV which has an // alignment AlignSCEV. Use that information, if possible, to compute a new // alignment for Ptr. -static unsigned getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV, - const SCEV *OffSCEV, Value *Ptr, - ScalarEvolution *SE) { +static Align getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV, + const SCEV *OffSCEV, Value *Ptr, + ScalarEvolution *SE) { const SCEV *PtrSCEV = SE->getSCEV(Ptr); + // On a platform with 32-bit allocas, but 64-bit flat/global pointer sizes + // (*cough* AMDGPU), the effective SCEV type of AASCEV and PtrSCEV + // may disagree. Trunc/extend so they agree. + PtrSCEV = SE->getTruncateOrZeroExtend( + PtrSCEV, SE->getEffectiveSCEVType(AASCEV->getType())); const SCEV *DiffSCEV = SE->getMinusSCEV(PtrSCEV, AASCEV); // On 32-bit platforms, DiffSCEV might now have type i32 -- we've always @@ -141,13 +147,12 @@ static unsigned getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV, << *AlignSCEV << " and offset " << *OffSCEV << " using diff " << *DiffSCEV << "\n"); - unsigned NewAlignment = getNewAlignmentDiff(DiffSCEV, AlignSCEV, SE); - LLVM_DEBUG(dbgs() << "\tnew alignment: " << NewAlignment << "\n"); + if (MaybeAlign NewAlignment = getNewAlignmentDiff(DiffSCEV, AlignSCEV, SE)) { + LLVM_DEBUG(dbgs() << "\tnew alignment: " << DebugStr(NewAlignment) << "\n"); + return *NewAlignment; + } - if (NewAlignment) { - return NewAlignment; - } else if (const SCEVAddRecExpr *DiffARSCEV = - dyn_cast<SCEVAddRecExpr>(DiffSCEV)) { + if (const SCEVAddRecExpr *DiffARSCEV = dyn_cast<SCEVAddRecExpr>(DiffSCEV)) { // The relative offset to the alignment assumption did not yield a constant, // but we should try harder: if we assume that a is 32-byte aligned, then in // for (i = 0; i < 1024; i += 4) r += a[i]; not all of the loads from a are @@ -165,134 +170,67 @@ static unsigned getNewAlignment(const SCEV *AASCEV, const SCEV *AlignSCEV, // first iteration, and also the alignment using the per-iteration delta. // If these are the same, then use that answer. Otherwise, use the smaller // one, but only if it divides the larger one. - NewAlignment = getNewAlignmentDiff(DiffStartSCEV, AlignSCEV, SE); - unsigned NewIncAlignment = getNewAlignmentDiff(DiffIncSCEV, AlignSCEV, SE); - - LLVM_DEBUG(dbgs() << "\tnew start alignment: " << NewAlignment << "\n"); - LLVM_DEBUG(dbgs() << "\tnew inc alignment: " << NewIncAlignment << "\n"); - - if (!NewAlignment || !NewIncAlignment) { - return 0; - } else if (NewAlignment > NewIncAlignment) { - if (NewAlignment % NewIncAlignment == 0) { - LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << NewIncAlignment - << "\n"); - return NewIncAlignment; - } - } else if (NewIncAlignment > NewAlignment) { - if (NewIncAlignment % NewAlignment == 0) { - LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << NewAlignment - << "\n"); - return NewAlignment; - } - } else if (NewIncAlignment == NewAlignment) { - LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << NewAlignment + MaybeAlign NewAlignment = getNewAlignmentDiff(DiffStartSCEV, AlignSCEV, SE); + MaybeAlign NewIncAlignment = + getNewAlignmentDiff(DiffIncSCEV, AlignSCEV, SE); + + LLVM_DEBUG(dbgs() << "\tnew start alignment: " << DebugStr(NewAlignment) + << "\n"); + LLVM_DEBUG(dbgs() << "\tnew inc alignment: " << DebugStr(NewIncAlignment) + << "\n"); + + if (!NewAlignment || !NewIncAlignment) + return Align(1); + + const Align NewAlign = *NewAlignment; + const Align NewIncAlign = *NewIncAlignment; + if (NewAlign > NewIncAlign) { + LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " + << DebugStr(NewIncAlign) << "\n"); + return NewIncAlign; + } + if (NewIncAlign > NewAlign) { + LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << DebugStr(NewAlign) << "\n"); - return NewAlignment; + return NewAlign; } + assert(NewIncAlign == NewAlign); + LLVM_DEBUG(dbgs() << "\tnew start/inc alignment: " << DebugStr(NewAlign) + << "\n"); + return NewAlign; } - return 0; + return Align(1); } bool AlignmentFromAssumptionsPass::extractAlignmentInfo(CallInst *I, + unsigned Idx, Value *&AAPtr, const SCEV *&AlignSCEV, const SCEV *&OffSCEV) { - // An alignment assume must be a statement about the least-significant - // bits of the pointer being zero, possibly with some offset. - ICmpInst *ICI = dyn_cast<ICmpInst>(I->getArgOperand(0)); - if (!ICI) - return false; - - // This must be an expression of the form: x & m == 0. - if (ICI->getPredicate() != ICmpInst::ICMP_EQ) - return false; - - // Swap things around so that the RHS is 0. - Value *CmpLHS = ICI->getOperand(0); - Value *CmpRHS = ICI->getOperand(1); - const SCEV *CmpLHSSCEV = SE->getSCEV(CmpLHS); - const SCEV *CmpRHSSCEV = SE->getSCEV(CmpRHS); - if (CmpLHSSCEV->isZero()) - std::swap(CmpLHS, CmpRHS); - else if (!CmpRHSSCEV->isZero()) + Type *Int64Ty = Type::getInt64Ty(I->getContext()); + OperandBundleUse AlignOB = I->getOperandBundleAt(Idx); + if (AlignOB.getTagName() != "align") return false; - - BinaryOperator *CmpBO = dyn_cast<BinaryOperator>(CmpLHS); - if (!CmpBO || CmpBO->getOpcode() != Instruction::And) - return false; - - // Swap things around so that the right operand of the and is a constant - // (the mask); we cannot deal with variable masks. - Value *AndLHS = CmpBO->getOperand(0); - Value *AndRHS = CmpBO->getOperand(1); - const SCEV *AndLHSSCEV = SE->getSCEV(AndLHS); - const SCEV *AndRHSSCEV = SE->getSCEV(AndRHS); - if (isa<SCEVConstant>(AndLHSSCEV)) { - std::swap(AndLHS, AndRHS); - std::swap(AndLHSSCEV, AndRHSSCEV); - } - - const SCEVConstant *MaskSCEV = dyn_cast<SCEVConstant>(AndRHSSCEV); - if (!MaskSCEV) - return false; - - // The mask must have some trailing ones (otherwise the condition is - // trivial and tells us nothing about the alignment of the left operand). - unsigned TrailingOnes = MaskSCEV->getAPInt().countTrailingOnes(); - if (!TrailingOnes) - return false; - - // Cap the alignment at the maximum with which LLVM can deal (and make sure - // we don't overflow the shift). - uint64_t Alignment; - TrailingOnes = std::min(TrailingOnes, - unsigned(sizeof(unsigned) * CHAR_BIT - 1)); - Alignment = std::min(1u << TrailingOnes, +Value::MaximumAlignment); - - Type *Int64Ty = Type::getInt64Ty(I->getParent()->getParent()->getContext()); - AlignSCEV = SE->getConstant(Int64Ty, Alignment); - - // The LHS might be a ptrtoint instruction, or it might be the pointer - // with an offset. - AAPtr = nullptr; - OffSCEV = nullptr; - if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(AndLHS)) { - AAPtr = PToI->getPointerOperand(); + assert(AlignOB.Inputs.size() >= 2); + AAPtr = AlignOB.Inputs[0].get(); + // TODO: Consider accumulating the offset to the base. + AAPtr = AAPtr->stripPointerCastsSameRepresentation(); + AlignSCEV = SE->getSCEV(AlignOB.Inputs[1].get()); + AlignSCEV = SE->getTruncateOrZeroExtend(AlignSCEV, Int64Ty); + if (AlignOB.Inputs.size() == 3) + OffSCEV = SE->getSCEV(AlignOB.Inputs[2].get()); + else OffSCEV = SE->getZero(Int64Ty); - } else if (const SCEVAddExpr* AndLHSAddSCEV = - dyn_cast<SCEVAddExpr>(AndLHSSCEV)) { - // Try to find the ptrtoint; subtract it and the rest is the offset. - for (SCEVAddExpr::op_iterator J = AndLHSAddSCEV->op_begin(), - JE = AndLHSAddSCEV->op_end(); J != JE; ++J) - if (const SCEVUnknown *OpUnk = dyn_cast<SCEVUnknown>(*J)) - if (PtrToIntInst *PToI = dyn_cast<PtrToIntInst>(OpUnk->getValue())) { - AAPtr = PToI->getPointerOperand(); - OffSCEV = SE->getMinusSCEV(AndLHSAddSCEV, *J); - break; - } - } - - if (!AAPtr) - return false; - - // Sign extend the offset to 64 bits (so that it is like all of the other - // expressions). - unsigned OffSCEVBits = OffSCEV->getType()->getPrimitiveSizeInBits(); - if (OffSCEVBits < 64) - OffSCEV = SE->getSignExtendExpr(OffSCEV, Int64Ty); - else if (OffSCEVBits > 64) - return false; - - AAPtr = AAPtr->stripPointerCasts(); + OffSCEV = SE->getTruncateOrZeroExtend(OffSCEV, Int64Ty); return true; } -bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall) { +bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall, + unsigned Idx) { Value *AAPtr; const SCEV *AlignSCEV, *OffSCEV; - if (!extractAlignmentInfo(ACall, AAPtr, AlignSCEV, OffSCEV)) + if (!extractAlignmentInfo(ACall, Idx, AAPtr, AlignSCEV, OffSCEV)) return false; // Skip ConstantPointerNull and UndefValue. Assumptions on these shouldn't @@ -310,35 +248,38 @@ bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall) { continue; if (Instruction *K = dyn_cast<Instruction>(J)) - if (isValidAssumeForContext(ACall, K, DT)) WorkList.push_back(K); } while (!WorkList.empty()) { Instruction *J = WorkList.pop_back_val(); - if (LoadInst *LI = dyn_cast<LoadInst>(J)) { - unsigned NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, - LI->getPointerOperand(), SE); - - if (NewAlignment > LI->getAlignment()) { - LI->setAlignment(MaybeAlign(NewAlignment)); + if (!isValidAssumeForContext(ACall, J, DT)) + continue; + Align NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, + LI->getPointerOperand(), SE); + if (NewAlignment > LI->getAlign()) { + LI->setAlignment(NewAlignment); ++NumLoadAlignChanged; } } else if (StoreInst *SI = dyn_cast<StoreInst>(J)) { - unsigned NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, - SI->getPointerOperand(), SE); - - if (NewAlignment > SI->getAlignment()) { - SI->setAlignment(MaybeAlign(NewAlignment)); + if (!isValidAssumeForContext(ACall, J, DT)) + continue; + Align NewAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, + SI->getPointerOperand(), SE); + if (NewAlignment > SI->getAlign()) { + SI->setAlignment(NewAlignment); ++NumStoreAlignChanged; } } else if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(J)) { - unsigned NewDestAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, - MI->getDest(), SE); - - LLVM_DEBUG(dbgs() << "\tmem inst: " << NewDestAlignment << "\n";); - if (NewDestAlignment > MI->getDestAlignment()) { + if (!isValidAssumeForContext(ACall, J, DT)) + continue; + Align NewDestAlignment = + getNewAlignment(AASCEV, AlignSCEV, OffSCEV, MI->getDest(), SE); + + LLVM_DEBUG(dbgs() << "\tmem inst: " << DebugStr(NewDestAlignment) + << "\n";); + if (NewDestAlignment > *MI->getDestAlign()) { MI->setDestAlignment(NewDestAlignment); ++NumMemIntAlignChanged; } @@ -346,12 +287,13 @@ bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall) { // For memory transfers, there is also a source alignment that // can be set. if (MemTransferInst *MTI = dyn_cast<MemTransferInst>(MI)) { - unsigned NewSrcAlignment = getNewAlignment(AASCEV, AlignSCEV, OffSCEV, - MTI->getSource(), SE); + Align NewSrcAlignment = + getNewAlignment(AASCEV, AlignSCEV, OffSCEV, MTI->getSource(), SE); - LLVM_DEBUG(dbgs() << "\tmem trans: " << NewSrcAlignment << "\n";); + LLVM_DEBUG(dbgs() << "\tmem trans: " << DebugStr(NewSrcAlignment) + << "\n";); - if (NewSrcAlignment > MTI->getSourceAlignment()) { + if (NewSrcAlignment > *MTI->getSourceAlign()) { MTI->setSourceAlignment(NewSrcAlignment); ++NumMemIntAlignChanged; } @@ -363,7 +305,7 @@ bool AlignmentFromAssumptionsPass::processAssumption(CallInst *ACall) { Visited.insert(J); for (User *UJ : J->users()) { Instruction *K = cast<Instruction>(UJ); - if (!Visited.count(K) && isValidAssumeForContext(ACall, K, DT)) + if (!Visited.count(K)) WorkList.push_back(K); } } @@ -390,8 +332,11 @@ bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC, bool Changed = false; for (auto &AssumeVH : AC.assumptions()) - if (AssumeVH) - Changed |= processAssumption(cast<CallInst>(AssumeVH)); + if (AssumeVH) { + CallInst *Call = cast<CallInst>(AssumeVH); + for (unsigned Idx = 0; Idx < Call->getNumOperandBundles(); Idx++) + Changed |= processAssumption(Call, Idx); + } return Changed; } |