Index: include/llvm/Analysis/ScalarEvolution.h =================================================================== --- include/llvm/Analysis/ScalarEvolution.h +++ include/llvm/Analysis/ScalarEvolution.h @@ -657,6 +657,16 @@ SmallVector NewOp(Operands.begin(), Operands.end()); return getAddRecExpr(NewOp, L, Flags); } + // \brief Returns an expression for getelementptr(Base, Indices...). + // \p BaseExpr The expression for the pointer operand. + // \p BaseType The type of the pointer operand. It can be different from + // Base->getType() for example when the pointer operand is + // a bitcast. + // \p IndexExprs The expressions for the indices. + // \p InBounds Whether the GEP is in bounds. + const SCEV *getGEPExpr(const SCEV *BaseExpr, Type *BaseType, + const SmallVectorImpl &IndexExprs, + bool InBounds = false); const SCEV *getSMaxExpr(const SCEV *LHS, const SCEV *RHS); const SCEV *getSMaxExpr(SmallVectorImpl &Operands); const SCEV *getUMaxExpr(const SCEV *LHS, const SCEV *RHS); Index: lib/Analysis/ScalarEvolution.cpp =================================================================== --- lib/Analysis/ScalarEvolution.cpp +++ lib/Analysis/ScalarEvolution.cpp @@ -2926,6 +2926,52 @@ return S; } +const SCEV * +ScalarEvolution::getGEPExpr(const SCEV *BaseExpr, Type *BaseType, + const SmallVectorImpl &IndexExprs, + bool InBounds) { + Type *IntPtrTy = getEffectiveSCEVType(BaseType); + // FIXME(PR23527): Don't blindly transfer the inbounds flag from the GEP + // instruction to its SCEV, because the Instruction may be guarded by control + // flow and the no-overflow bits may not be valid for the expression in any + // context. + SCEV::NoWrapFlags Wrap = InBounds ? SCEV::FlagNSW : SCEV::FlagAnyWrap; + + const SCEV *TotalOffset = getConstant(IntPtrTy, 0); + Type *CurTy = BaseType; + for (const SCEV *IndexExpr : IndexExprs) { + // Compute the (potentially symbolic) offset in bytes for this index. + if (StructType *STy = dyn_cast(CurTy)) { + // For a struct, add the member offset. + ConstantInt *Index = cast(IndexExpr)->getValue(); + unsigned FieldNo = Index->getZExtValue(); + const SCEV *FieldOffset = getOffsetOfExpr(IntPtrTy, STy, FieldNo); + + // Add the field offset to the running total offset. + TotalOffset = getAddExpr(TotalOffset, FieldOffset); + + // Update CurTy to the type of the field at Index. + CurTy = STy->getTypeAtIndex(Index); + } else { + // Update CurTy to its element type. + CurTy = cast(CurTy)->getElementType(); + // For an array, add the element offset, explicitly scaled. + const SCEV *ElementSize = getSizeOfExpr(IntPtrTy, CurTy); + // Getelementptr indices are signed. + IndexExpr = getTruncateOrSignExtend(IndexExpr, IntPtrTy); + + // Multiply the index by the element size to compute the element offset. + const SCEV *LocalOffset = getMulExpr(IndexExpr, ElementSize, Wrap); + + // Add the element offset to the running total offset. + TotalOffset = getAddExpr(TotalOffset, LocalOffset); + } + } + + // Add the total offset from all the GEP indices to the base. + return getAddExpr(BaseExpr, TotalOffset, Wrap); +} + const SCEV *ScalarEvolution::getSMaxExpr(const SCEV *LHS, const SCEV *RHS) { SmallVector Ops; @@ -3700,52 +3746,16 @@ /// operations. This allows them to be analyzed by regular SCEV code. /// const SCEV *ScalarEvolution::createNodeForGEP(GEPOperator *GEP) { - Type *IntPtrTy = getEffectiveSCEVType(GEP->getType()); Value *Base = GEP->getOperand(0); // Don't attempt to analyze GEPs over unsized objects. if (!Base->getType()->getPointerElementType()->isSized()) return getUnknown(GEP); - // Don't blindly transfer the inbounds flag from the GEP instruction to the - // Add expression, because the Instruction may be guarded by control flow - // and the no-overflow bits may not be valid for the expression in any - // context. - SCEV::NoWrapFlags Wrap = GEP->isInBounds() ? SCEV::FlagNSW : SCEV::FlagAnyWrap; - - const SCEV *TotalOffset = getConstant(IntPtrTy, 0); - gep_type_iterator GTI = gep_type_begin(GEP); - for (GetElementPtrInst::op_iterator I = std::next(GEP->op_begin()), - E = GEP->op_end(); - I != E; ++I) { - Value *Index = *I; - // Compute the (potentially symbolic) offset in bytes for this index. - if (StructType *STy = dyn_cast(*GTI++)) { - // For a struct, add the member offset. - unsigned FieldNo = cast(Index)->getZExtValue(); - const SCEV *FieldOffset = getOffsetOfExpr(IntPtrTy, STy, FieldNo); - - // Add the field offset to the running total offset. - TotalOffset = getAddExpr(TotalOffset, FieldOffset); - } else { - // For an array, add the element offset, explicitly scaled. - const SCEV *ElementSize = getSizeOfExpr(IntPtrTy, *GTI); - const SCEV *IndexS = getSCEV(Index); - // Getelementptr indices are signed. - IndexS = getTruncateOrSignExtend(IndexS, IntPtrTy); - - // Multiply the index by the element size to compute the element offset. - const SCEV *LocalOffset = getMulExpr(IndexS, ElementSize, Wrap); - - // Add the element offset to the running total offset. - TotalOffset = getAddExpr(TotalOffset, LocalOffset); - } - } - - // Get the SCEV for the GEP base. - const SCEV *BaseS = getSCEV(Base); - - // Add the total offset from all the GEP indices to the base. - return getAddExpr(BaseS, TotalOffset, Wrap); + SmallVector IndexExprs; + for (auto Index = GEP->idx_begin(); Index != GEP->idx_end(); ++Index) + IndexExprs.push_back(getSCEV(*Index)); + return getGEPExpr(getSCEV(Base), Base->getType(), IndexExprs, + GEP->isInBounds()); } /// GetMinTrailingZeros - Determine the minimum number of zero bits that S is Index: lib/Transforms/Scalar/StraightLineStrengthReduce.cpp =================================================================== --- lib/Transforms/Scalar/StraightLineStrengthReduce.cpp +++ lib/Transforms/Scalar/StraightLineStrengthReduce.cpp @@ -491,31 +491,35 @@ if (GEP->getType()->isVectorTy()) return; - const SCEV *GEPExpr = SE->getSCEV(GEP); - Type *IntPtrTy = DL->getIntPtrType(GEP->getType()); + SmallVector IndexExprs; + for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) + IndexExprs.push_back(SE->getSCEV(*I)); + Value *GEPBase = GEP->getPointerOperand(); gep_type_iterator GTI = gep_type_begin(GEP); - for (auto I = GEP->idx_begin(); I != GEP->idx_end(); ++I) { + for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I) { if (!isa(*GTI++)) continue; - Value *ArrayIdx = *I; - // Compute the byte offset of this index. + + const SCEV *OrigIndexExpr = IndexExprs[I - 1]; + IndexExprs[I - 1] = SE->getConstant(OrigIndexExpr->getType(), 0); + + // The base of this candidate is GEP's base plus the offsets of all + // indices except this current one. + const SCEV *BaseExpr = + SE->getGEPExpr(SE->getSCEV(GEPBase), GEPBase->getType(), IndexExprs, + GEP->isInBounds()); + Value *ArrayIdx = GEP->getOperand(I); uint64_t ElementSize = DL->getTypeAllocSize(*GTI); - const SCEV *ElementSizeExpr = SE->getSizeOfExpr(IntPtrTy, *GTI); - const SCEV *ArrayIdxExpr = SE->getSCEV(ArrayIdx); - ArrayIdxExpr = SE->getTruncateOrSignExtend(ArrayIdxExpr, IntPtrTy); - const SCEV *LocalOffset = - SE->getMulExpr(ArrayIdxExpr, ElementSizeExpr, SCEV::FlagNSW); - // The base of this candidate equals GEPExpr less the byte offset of this - // index. - const SCEV *Base = SE->getMinusSCEV(GEPExpr, LocalOffset); - factorArrayIndex(ArrayIdx, Base, ElementSize, GEP); + factorArrayIndex(ArrayIdx, BaseExpr, ElementSize, GEP); // When ArrayIdx is the sext of a value, we try to factor that value as // well. Handling this case is important because array indices are // typically sign-extended to the pointer size. Value *TruncatedArrayIdx = nullptr; if (match(ArrayIdx, m_SExt(m_Value(TruncatedArrayIdx)))) - factorArrayIndex(TruncatedArrayIdx, Base, ElementSize, GEP); + factorArrayIndex(TruncatedArrayIdx, BaseExpr, ElementSize, GEP); + + IndexExprs[I - 1] = OrigIndexExpr; } }