198 using namespace llvm;
202 "disable-separate-const-offset-from-gep",
cl::init(
false),
203 cl::desc(
"Do not separate the constant offset from a GEP instruction"),
211 cl::desc(
"Verify this pass produces no dead code"),
229 class ConstantOffsetExtractor {
249 :
IP(InsertionPt),
DL(InsertionPt->getModule()->getDataLayout()), DT(DT) {
266 APInt find(
Value *V,
bool SignExtended,
bool ZeroExtended,
bool NonNegative);
287 Value *rebuildWithoutConstOffset();
304 Value *distributeExtsAndCloneChain(
unsigned ChainIndex);
307 Value *removeConstOffset(
unsigned ChainIndex);
321 bool CanTraceInto(
bool SignExtended,
bool ZeroExtended,
BinaryOperator *BO,
346 class SeparateConstOffsetFromGEPLegacyPass :
public FunctionPass {
350 SeparateConstOffsetFromGEPLegacyPass(
bool LowerGEP =
false)
374 class SeparateConstOffsetFromGEP {
376 SeparateConstOffsetFromGEP(
380 : DT(DT), SE(SE), LI(LI), TLI(TLI), GetTTI(GetTTI), LowerGEP(LowerGEP) {}
397 int64_t AccumulativeByteOffset);
407 int64_t AccumulativeByteOffset);
455 bool hasMoreThanOneUseInLoop(
Value *v,
Loop *L);
485 SeparateConstOffsetFromGEPLegacyPass,
"separate-const-offset-from-gep",
486 "Split GEPs to a variadic base and a constant offset for better CSE",
false,
494 SeparateConstOffsetFromGEPLegacyPass, "separate-
const-offset-from-
gep",
499 return new SeparateConstOffsetFromGEPLegacyPass(LowerGEP);
502 bool ConstantOffsetExtractor::CanTraceInto(
bool SignExtended,
520 if (BO->
getOpcode() == Instruction::Or &&
545 if (!ConstLHS->isNegative())
549 if (!ConstRHS->isNegative())
571 size_t ChainLength = UserChain.size();
582 if (ConstantOffset != 0)
return ConstantOffset;
586 UserChain.resize(ChainLength);
588 ConstantOffset =
find(BO->
getOperand(1), SignExtended, ZeroExtended,
593 ConstantOffset = -ConstantOffset;
596 if (ConstantOffset == 0)
597 UserChain.resize(ChainLength);
599 return ConstantOffset;
603 bool ZeroExtended,
bool NonNegative) {
610 User *U = dyn_cast<User>(V);
616 ConstantOffset = CI->getValue();
619 if (CanTraceInto(SignExtended, ZeroExtended, BO, NonNegative))
620 ConstantOffset = findInEitherOperand(BO, SignExtended, ZeroExtended);
621 }
else if (isa<TruncInst>(V)) {
625 }
else if (isa<SExtInst>(V)) {
627 ZeroExtended, NonNegative).sext(
BitWidth);
628 }
else if (isa<ZExtInst>(V)) {
641 if (ConstantOffset != 0)
642 UserChain.push_back(U);
643 return ConstantOffset;
646 Value *ConstantOffsetExtractor::applyExts(
Value *V) {
651 if (
Constant *
C = dyn_cast<Constant>(Current)) {
657 Ext->setOperand(0, Current);
658 Ext->insertBefore(
IP);
665 Value *ConstantOffsetExtractor::rebuildWithoutConstOffset() {
666 distributeExtsAndCloneChain(UserChain.size() - 1);
668 unsigned NewSize = 0;
669 for (
User *
I : UserChain) {
671 UserChain[NewSize] =
I;
675 UserChain.resize(NewSize);
676 return removeConstOffset(UserChain.size() - 1);
680 ConstantOffsetExtractor::distributeExtsAndCloneChain(
unsigned ChainIndex) {
681 User *U = UserChain[ChainIndex];
682 if (ChainIndex == 0) {
683 assert(isa<ConstantInt>(U));
685 return UserChain[ChainIndex] = cast<ConstantInt>(applyExts(U));
688 if (
CastInst *Cast = dyn_cast<CastInst>(U)) {
690 (isa<SExtInst>(Cast) || isa<ZExtInst>(Cast) || isa<TruncInst>(Cast)) &&
691 "Only following instructions can be traced: sext, zext & trunc");
692 ExtInsts.push_back(Cast);
693 UserChain[ChainIndex] =
nullptr;
694 return distributeExtsAndCloneChain(ChainIndex - 1);
700 unsigned OpNo = (BO->
getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);
702 Value *NextInChain = distributeExtsAndCloneChain(ChainIndex - 1);
712 return UserChain[ChainIndex] = NewBO;
715 Value *ConstantOffsetExtractor::removeConstOffset(
unsigned ChainIndex) {
716 if (ChainIndex == 0) {
717 assert(isa<ConstantInt>(UserChain[ChainIndex]));
723 "distributeExtsAndCloneChain clones each BinaryOperator in "
724 "UserChain, so no one should be used more than "
727 unsigned OpNo = (BO->
getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);
729 Value *NextInChain = removeConstOffset(ChainIndex - 1);
734 if (
ConstantInt *CI = dyn_cast<ConstantInt>(NextInChain)) {
735 if (CI->isZero() && !(BO->
getOpcode() == Instruction::Sub && OpNo == 0))
740 if (BO->
getOpcode() == Instruction::Or) {
768 User *&UserChainTail,
770 ConstantOffsetExtractor Extractor(
GEP, DT);
772 APInt ConstantOffset =
773 Extractor.find(Idx,
false,
false,
775 if (ConstantOffset == 0) {
776 UserChainTail =
nullptr;
780 Value *IdxWithoutConstOffset = Extractor.rebuildWithoutConstOffset();
781 UserChainTail = Extractor.UserChain.back();
782 return IdxWithoutConstOffset;
788 return ConstantOffsetExtractor(
GEP, DT)
789 .find(Idx,
false,
false,
794 bool SeparateConstOffsetFromGEP::canonicalizeArrayIndicesToPointerSize(
796 bool Changed =
false;
797 Type *IntPtrTy =
DL->getIntPtrType(
GEP->getType());
800 I !=
E; ++
I, ++GTI) {
803 if ((*I)->getType() != IntPtrTy) {
814 bool &NeedsExtraction) {
815 NeedsExtraction =
false;
816 int64_t AccumulativeByteOffset = 0;
818 for (
unsigned I = 1,
E =
GEP->getNumOperands();
I !=
E; ++
I, ++GTI) {
821 int64_t ConstantOffset =
823 if (ConstantOffset != 0) {
824 NeedsExtraction =
true;
828 AccumulativeByteOffset +=
831 }
else if (LowerGEP) {
836 NeedsExtraction =
true;
837 AccumulativeByteOffset +=
838 DL->getStructLayout(StTy)->getElementOffset(
Field);
842 return AccumulativeByteOffset;
845 void SeparateConstOffsetFromGEP::lowerToSingleIndexGEPs(
855 bool isSwapCandidate =
857 !hasMoreThanOneUseInLoop(ResultPtr, L);
858 Value *FirstResult =
nullptr;
860 if (ResultPtr->
getType() != I8PtrTy)
861 ResultPtr =
Builder.CreateBitCast(ResultPtr, I8PtrTy);
866 for (
unsigned I = 1,
E =
Variadic->getNumOperands();
I !=
E; ++
I, ++GTI) {
877 if (ElementSize != 1) {
887 Builder.CreateGEP(
Builder.getInt8Ty(), ResultPtr, Idx,
"uglygep");
888 if (FirstResult ==
nullptr)
889 FirstResult = ResultPtr;
894 if (AccumulativeByteOffset != 0) {
897 Builder.CreateGEP(
Builder.getInt8Ty(), ResultPtr, Offset,
"uglygep");
899 isSwapCandidate =
false;
904 auto *FirstGEP = dyn_cast_or_null<GetElementPtrInst>(FirstResult);
905 auto *SecondGEP = dyn_cast<GetElementPtrInst>(ResultPtr);
906 if (isSwapCandidate && isLegalToSwapOperand(FirstGEP, SecondGEP, L))
907 swapGEPOperand(FirstGEP, SecondGEP);
912 Variadic->replaceAllUsesWith(ResultPtr);
918 int64_t AccumulativeByteOffset) {
927 for (
unsigned I = 1,
E =
Variadic->getNumOperands();
I !=
E; ++
I, ++GTI) {
938 if (ElementSize != 1) {
947 ResultPtr =
Builder.CreateAdd(ResultPtr, Idx);
952 if (AccumulativeByteOffset != 0) {
958 Variadic->replaceAllUsesWith(ResultPtr);
964 if (
GEP->getType()->isVectorTy())
969 if (
GEP->hasAllConstantIndices())
972 bool Changed = canonicalizeArrayIndicesToPointerSize(
GEP);
974 bool NeedsExtraction;
975 int64_t AccumulativeByteOffset = accumulateByteOffset(
GEP, NeedsExtraction);
977 if (!NeedsExtraction)
990 unsigned AddrSpace =
GEP->getPointerAddressSpace();
992 nullptr, AccumulativeByteOffset,
1007 for (
unsigned I = 1,
E =
GEP->getNumOperands();
I !=
E; ++
I, ++GTI) {
1012 User *UserChainTail;
1014 ConstantOffsetExtractor::Extract(OldIdx,
GEP, UserChainTail, DT);
1015 if (NewIdx !=
nullptr) {
1017 GEP->setOperand(
I, NewIdx);
1045 bool GEPWasInBounds =
GEP->isInBounds();
1046 GEP->setIsInBounds(
false);
1053 lowerToSingleIndexGEPs(
GEP, AccumulativeByteOffset);
1055 lowerToArithmetics(
GEP, AccumulativeByteOffset);
1060 if (AccumulativeByteOffset == 0)
1097 int64_t ElementTypeSizeOfGEP =
static_cast<int64_t
>(
1098 DL->getTypeAllocSize(
GEP->getResultElementType()));
1099 Type *IntPtrTy =
DL->getIntPtrType(
GEP->getType());
1100 if (AccumulativeByteOffset % ElementTypeSizeOfGEP == 0) {
1103 int64_t
Index = AccumulativeByteOffset / ElementTypeSizeOfGEP;
1109 cast<GetElementPtrInst>(NewGEP)->setIsInBounds(GEPWasInBounds);
1126 GEP->getPointerAddressSpace());
1134 cast<GetElementPtrInst>(NewGEP)->setIsInBounds(GEPWasInBounds);
1135 if (
GEP->getType() != I8PtrTy)
1139 GEP->replaceAllUsesWith(NewGEP);
1140 GEP->eraseFromParent();
1146 if (skipFunction(
F))
1148 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
1149 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
1150 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
1151 auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(
F);
1153 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
1155 SeparateConstOffsetFromGEP Impl(DT, SE, LI, TLI, GetTTI, LowerGEP);
1163 DL = &
F.getParent()->getDataLayout();
1164 bool Changed =
false;
1171 Changed |= splitGEP(
GEP);
1176 Changed |= reuniteExts(
F);
1179 verifyNoDeadCode(
F);
1184 Instruction *SeparateConstOffsetFromGEP::findClosestMatchingDominator(
1187 auto Pos = DominatingExprs.find(
Key);
1188 if (Pos == DominatingExprs.end())
1191 auto &Candidates = Pos->second;
1196 while (!Candidates.empty()) {
1198 if (DT->
dominates(Candidate, Dominatee))
1200 Candidates.pop_back();
1205 bool SeparateConstOffsetFromGEP::reuniteExts(
Instruction *
I) {
1206 if (!SE->isSCEVable(
I->getType()))
1217 SE->getAddExpr(SE->getUnknown(
LHS), SE->getUnknown(
RHS));
1218 if (
auto *Dom = findClosestMatchingDominator(
Key,
I, DominatingAdds)) {
1221 I->replaceAllUsesWith(NewSExt);
1229 SE->getAddExpr(SE->getUnknown(
LHS), SE->getUnknown(
RHS));
1230 if (
auto *Dom = findClosestMatchingDominator(
Key,
I, DominatingSubs)) {
1233 I->replaceAllUsesWith(NewSExt);
1244 SE->getAddExpr(SE->getUnknown(
LHS), SE->getUnknown(
RHS));
1245 DominatingAdds[
Key].push_back(
I);
1250 SE->getAddExpr(SE->getUnknown(
LHS), SE->getUnknown(
RHS));
1251 DominatingSubs[
Key].push_back(
I);
1257 bool SeparateConstOffsetFromGEP::reuniteExts(
Function &
F) {
1258 bool Changed =
false;
1259 DominatingAdds.clear();
1260 DominatingSubs.clear();
1264 Changed |= reuniteExts(&
I);
1269 void SeparateConstOffsetFromGEP::verifyNoDeadCode(
Function &
F) {
1273 std::string ErrMessage;
1275 RSO <<
"Dead instruction detected!\n" <<
I <<
"\n";
1282 bool SeparateConstOffsetFromGEP::isLegalToSwapOperand(
1284 if (!FirstGEP || !FirstGEP->
hasOneUse())
1290 if (FirstGEP == SecondGEP)
1296 if (FirstNum != SecondNum || FirstNum != 2)
1310 Instruction *FirstOffsetDef = dyn_cast<Instruction>(FirstOffset);
1321 if (FirstOffsetDef && FirstOffsetDef->
isShift() &&
1322 isa<ConstantInt>(FirstOffsetDef->
getOperand(1)))
1323 FirstOffsetDef = dyn_cast<Instruction>(FirstOffsetDef->
getOperand(0));
1328 if (
BinaryOperator *BO = dyn_cast<BinaryOperator>(FirstOffsetDef)) {
1338 bool SeparateConstOffsetFromGEP::hasMoreThanOneUseInLoop(
Value *V,
Loop *L) {
1343 if (++UsesInLoop > 1)
1353 First->setOperand(1, Offset2);
1359 cast<PointerType>(
First->getType())->getAddressSpace()),
1362 First->stripAndAccumulateInBoundsConstantOffsets(DAL, Offset);
1365 Offset.ugt(ObjectSize)) {
1366 First->setIsInBounds(
false);
1369 First->setIsInBounds(
true);
1381 SeparateConstOffsetFromGEP Impl(DT, SE, LI, TLI, GetTTI, LowerGEP);