diff --git a/llvm/include/llvm/Transforms/Utils/ConstantOffsetExtractor.h b/llvm/include/llvm/Transforms/Utils/ConstantOffsetExtractor.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Transforms/Utils/ConstantOffsetExtractor.h @@ -0,0 +1,142 @@ +//===- llvm/Transforms/Utils/ConstantOffsetExtractor.h - Extract ConstantOffset +//from GEPs --*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +#ifndef LLVM_CONSTANTOFFSETEXTRACTOR_H +#define LLVM_CONSTANTOFFSETEXTRACTOR_H +#include "llvm/IR/DataLayout.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instructions.h" +namespace llvm { +/// A helper class for separating a constant offset from a GEP index. +/// +/// In real programs, a GEP index may be more complicated than a simple addition +/// of something and a constant integer which can be trivially splitted. For +/// example, to split ((a << 3) | 5) + b, we need to search deeper for the +/// constant offset, so that we can separate the index to (a << 3) + b and 5. +/// +/// Therefore, this class looks into the expression that computes a given GEP +/// index, and tries to find a constant integer that can be hoisted to the +/// outermost level of the expression as an addition. Not every constant in an +/// expression can jump out. e.g., we cannot transform (b * (a + 5)) to (b * a + +/// 5); nor can we transform (3 * (a + 5)) to (3 * a + 5), however in this case, +/// -instcombine probably already optimized (3 * (a + 5)) to (3 * a + 15). +class ConstantOffsetExtractor { +public: + /// Extracts a constant offset from the given GEP index. It returns the + /// new index representing the remainder (equal to the original index minus + /// the constant offset), or nullptr if we cannot extract a constant offset. + /// \p Idx The given GEP index + /// \p GEP The given GEP + /// \p UserChainTail Outputs the tail of UserChain so that we can + /// garbage-collect unused instructions in UserChain. + static Value *Extract(Value *Idx, GetElementPtrInst *GEP, + User *&UserChainTail, const DominatorTree *DT); + + /// Looks for a constant offset from the given GEP index without extracting + /// it. It returns the numeric value of the extracted constant offset (0 if + /// failed). The meaning of the arguments are the same as Extract. + static int64_t Find(Value *Idx, GetElementPtrInst *GEP, + const DominatorTree *DT); + +private: + ConstantOffsetExtractor(Instruction *InsertionPt, const DominatorTree *DT) + : IP(InsertionPt), DL(InsertionPt->getModule()->getDataLayout()), DT(DT) { + } + + /// Searches the expression that computes V for a non-zero constant C s.t. + /// V can be reassociated into the form V' + C. If the searching is + /// successful, returns C and update UserChain as a def-use chain from C to V; + /// otherwise, UserChain is empty. + /// + /// \p V The given expression + /// \p SignExtended Whether V will be sign-extended in the computation of the + /// GEP index + /// \p ZeroExtended Whether V will be zero-extended in the computation of the + /// GEP index + /// \p NonNegative Whether V is guaranteed to be non-negative. For example, + /// an index of an inbounds GEP is guaranteed to be + /// non-negative. Levaraging this, we can better split + /// inbounds GEPs. + APInt find(Value *V, bool SignExtended, bool ZeroExtended, bool NonNegative); + + /// A helper function to look into both operands of a binary operator. + APInt findInEitherOperand(BinaryOperator *BO, bool SignExtended, + bool ZeroExtended); + + /// After finding the constant offset C from the GEP index I, we build a new + /// index I' s.t. I' + C = I. This function builds and returns the new + /// index I' according to UserChain produced by function "find". + /// + /// The building conceptually takes two steps: + /// 1) iteratively distribute s/zext towards the leaves of the expression tree + /// that computes I + /// 2) reassociate the expression tree to the form I' + C. + /// + /// For example, to extract the 5 from sext(a + (b + 5)), we first distribute + /// sext to a, b and 5 so that we have + /// sext(a) + (sext(b) + 5). + /// Then, we reassociate it to + /// (sext(a) + sext(b)) + 5. + /// Given this form, we know I' is sext(a) + sext(b). + Value *rebuildWithoutConstOffset(); + + /// After the first step of rebuilding the GEP index without the constant + /// offset, distribute s/zext to the operands of all operators in UserChain. + /// e.g., zext(sext(a + (b + 5)) (assuming no overflow) => + /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5))). + /// + /// The function also updates UserChain to point to new subexpressions after + /// distributing s/zext. e.g., the old UserChain of the above example is + /// 5 -> b + 5 -> a + (b + 5) -> sext(...) -> zext(sext(...)), + /// and the new UserChain is + /// zext(sext(5)) -> zext(sext(b)) + zext(sext(5)) -> + /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5)) + /// + /// \p ChainIndex The index to UserChain. ChainIndex is initially + /// UserChain.size() - 1, and is decremented during + /// the recursion. + Value *distributeExtsAndCloneChain(unsigned ChainIndex); + + /// Reassociates the GEP index to the form I' + C and returns I'. + Value *removeConstOffset(unsigned ChainIndex); + + /// A helper function to apply ExtInsts, a list of s/zext, to value V. + /// e.g., if ExtInsts = [sext i32 to i64, zext i16 to i32], this function + /// returns "sext i32 (zext i16 V to i32) to i64". + Value *applyExts(Value *V); + + /// A helper function that returns whether we can trace into the operands + /// of binary operator BO for a constant offset. + /// + /// \p SignExtended Whether BO is surrounded by sext + /// \p ZeroExtended Whether BO is surrounded by zext + /// \p NonNegative Whether BO is known to be non-negative, e.g., an in-bound + /// array index. + bool CanTraceInto(bool SignExtended, bool ZeroExtended, BinaryOperator *BO, + bool NonNegative); + + /// The path from the constant offset to the old GEP index. e.g., if the GEP + /// index is "a * b + (c + 5)". After running function find, UserChain[0] will + /// be the constant 5, UserChain[1] will be the subexpression "c + 5", and + /// UserChain[2] will be the entire expression "a * b + (c + 5)". + /// + /// This path helps to rebuild the new GEP index. + SmallVector UserChain; + + /// A data structure used in rebuildWithoutConstOffset. Contains all + /// sext/zext instructions along UserChain. + SmallVector ExtInsts; + + /// Insertion position of cloned instructions. + Instruction *IP; + + const DataLayout &DL; + const DominatorTree *DT; +}; +} // namespace llvm + +#endif // LLVM_CONSTANTOFFSETEXTRACTOR_H diff --git a/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp b/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp --- a/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp +++ b/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp @@ -190,6 +190,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Utils/ConstantOffsetExtractor.h" #include "llvm/Transforms/Utils/Local.h" #include #include @@ -212,134 +213,6 @@ cl::Hidden); namespace { - -/// A helper class for separating a constant offset from a GEP index. -/// -/// In real programs, a GEP index may be more complicated than a simple addition -/// of something and a constant integer which can be trivially splitted. For -/// example, to split ((a << 3) | 5) + b, we need to search deeper for the -/// constant offset, so that we can separate the index to (a << 3) + b and 5. -/// -/// Therefore, this class looks into the expression that computes a given GEP -/// index, and tries to find a constant integer that can be hoisted to the -/// outermost level of the expression as an addition. Not every constant in an -/// expression can jump out. e.g., we cannot transform (b * (a + 5)) to (b * a + -/// 5); nor can we transform (3 * (a + 5)) to (3 * a + 5), however in this case, -/// -instcombine probably already optimized (3 * (a + 5)) to (3 * a + 15). -class ConstantOffsetExtractor { -public: - /// Extracts a constant offset from the given GEP index. It returns the - /// new index representing the remainder (equal to the original index minus - /// the constant offset), or nullptr if we cannot extract a constant offset. - /// \p Idx The given GEP index - /// \p GEP The given GEP - /// \p UserChainTail Outputs the tail of UserChain so that we can - /// garbage-collect unused instructions in UserChain. - static Value *Extract(Value *Idx, GetElementPtrInst *GEP, - User *&UserChainTail, const DominatorTree *DT); - - /// Looks for a constant offset from the given GEP index without extracting - /// it. It returns the numeric value of the extracted constant offset (0 if - /// failed). The meaning of the arguments are the same as Extract. - static int64_t Find(Value *Idx, GetElementPtrInst *GEP, - const DominatorTree *DT); - -private: - ConstantOffsetExtractor(Instruction *InsertionPt, const DominatorTree *DT) - : IP(InsertionPt), DL(InsertionPt->getModule()->getDataLayout()), DT(DT) { - } - - /// Searches the expression that computes V for a non-zero constant C s.t. - /// V can be reassociated into the form V' + C. If the searching is - /// successful, returns C and update UserChain as a def-use chain from C to V; - /// otherwise, UserChain is empty. - /// - /// \p V The given expression - /// \p SignExtended Whether V will be sign-extended in the computation of the - /// GEP index - /// \p ZeroExtended Whether V will be zero-extended in the computation of the - /// GEP index - /// \p NonNegative Whether V is guaranteed to be non-negative. For example, - /// an index of an inbounds GEP is guaranteed to be - /// non-negative. Levaraging this, we can better split - /// inbounds GEPs. - APInt find(Value *V, bool SignExtended, bool ZeroExtended, bool NonNegative); - - /// A helper function to look into both operands of a binary operator. - APInt findInEitherOperand(BinaryOperator *BO, bool SignExtended, - bool ZeroExtended); - - /// After finding the constant offset C from the GEP index I, we build a new - /// index I' s.t. I' + C = I. This function builds and returns the new - /// index I' according to UserChain produced by function "find". - /// - /// The building conceptually takes two steps: - /// 1) iteratively distribute s/zext towards the leaves of the expression tree - /// that computes I - /// 2) reassociate the expression tree to the form I' + C. - /// - /// For example, to extract the 5 from sext(a + (b + 5)), we first distribute - /// sext to a, b and 5 so that we have - /// sext(a) + (sext(b) + 5). - /// Then, we reassociate it to - /// (sext(a) + sext(b)) + 5. - /// Given this form, we know I' is sext(a) + sext(b). - Value *rebuildWithoutConstOffset(); - - /// After the first step of rebuilding the GEP index without the constant - /// offset, distribute s/zext to the operands of all operators in UserChain. - /// e.g., zext(sext(a + (b + 5)) (assuming no overflow) => - /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5))). - /// - /// The function also updates UserChain to point to new subexpressions after - /// distributing s/zext. e.g., the old UserChain of the above example is - /// 5 -> b + 5 -> a + (b + 5) -> sext(...) -> zext(sext(...)), - /// and the new UserChain is - /// zext(sext(5)) -> zext(sext(b)) + zext(sext(5)) -> - /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5)) - /// - /// \p ChainIndex The index to UserChain. ChainIndex is initially - /// UserChain.size() - 1, and is decremented during - /// the recursion. - Value *distributeExtsAndCloneChain(unsigned ChainIndex); - - /// Reassociates the GEP index to the form I' + C and returns I'. - Value *removeConstOffset(unsigned ChainIndex); - - /// A helper function to apply ExtInsts, a list of s/zext, to value V. - /// e.g., if ExtInsts = [sext i32 to i64, zext i16 to i32], this function - /// returns "sext i32 (zext i16 V to i32) to i64". - Value *applyExts(Value *V); - - /// A helper function that returns whether we can trace into the operands - /// of binary operator BO for a constant offset. - /// - /// \p SignExtended Whether BO is surrounded by sext - /// \p ZeroExtended Whether BO is surrounded by zext - /// \p NonNegative Whether BO is known to be non-negative, e.g., an in-bound - /// array index. - bool CanTraceInto(bool SignExtended, bool ZeroExtended, BinaryOperator *BO, - bool NonNegative); - - /// The path from the constant offset to the old GEP index. e.g., if the GEP - /// index is "a * b + (c + 5)". After running function find, UserChain[0] will - /// be the constant 5, UserChain[1] will be the subexpression "c + 5", and - /// UserChain[2] will be the entire expression "a * b + (c + 5)". - /// - /// This path helps to rebuild the new GEP index. - SmallVector UserChain; - - /// A data structure used in rebuildWithoutConstOffset. Contains all - /// sext/zext instructions along UserChain. - SmallVector ExtInsts; - - /// Insertion position of cloned instructions. - Instruction *IP; - - const DataLayout &DL; - const DominatorTree *DT; -}; - /// A pass that tries to split every GEP in the function into a variadic /// base and a constant offset. It is a FunctionPass because searching for the /// constant offset may inspect other basic blocks. @@ -499,305 +372,13 @@ return new SeparateConstOffsetFromGEPLegacyPass(LowerGEP); } -bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended, - bool ZeroExtended, - BinaryOperator *BO, - bool NonNegative) { - // We only consider ADD, SUB and OR, because a non-zero constant found in - // expressions composed of these operations can be easily hoisted as a - // constant offset by reassociation. - if (BO->getOpcode() != Instruction::Add && - BO->getOpcode() != Instruction::Sub && - BO->getOpcode() != Instruction::Or) { - return false; - } - - Value *LHS = BO->getOperand(0), *RHS = BO->getOperand(1); - // Do not trace into "or" unless it is equivalent to "add". If LHS and RHS - // don't have common bits, (LHS | RHS) is equivalent to (LHS + RHS). - // FIXME: this does not appear to be covered by any tests - // (with x86/aarch64 backends at least) - if (BO->getOpcode() == Instruction::Or && - !haveNoCommonBitsSet(LHS, RHS, DL, nullptr, BO, DT)) - return false; - - // In addition, tracing into BO requires that its surrounding s/zext (if - // any) is distributable to both operands. - // - // Suppose BO = A op B. - // SignExtended | ZeroExtended | Distributable? - // --------------+--------------+---------------------------------- - // 0 | 0 | true because no s/zext exists - // 0 | 1 | zext(BO) == zext(A) op zext(B) - // 1 | 0 | sext(BO) == sext(A) op sext(B) - // 1 | 1 | zext(sext(BO)) == - // | | zext(sext(A)) op zext(sext(B)) - if (BO->getOpcode() == Instruction::Add && !ZeroExtended && NonNegative) { - // If a + b >= 0 and (a >= 0 or b >= 0), then - // sext(a + b) = sext(a) + sext(b) - // even if the addition is not marked nsw. - // - // Leveraging this invariant, we can trace into an sext'ed inbound GEP - // index if the constant offset is non-negative. - // - // Verified in @sext_add in split-gep.ll. - if (ConstantInt *ConstLHS = dyn_cast(LHS)) { - if (!ConstLHS->isNegative()) - return true; - } - if (ConstantInt *ConstRHS = dyn_cast(RHS)) { - if (!ConstRHS->isNegative()) - return true; - } - } - - // sext (add/sub nsw A, B) == add/sub nsw (sext A), (sext B) - // zext (add/sub nuw A, B) == add/sub nuw (zext A), (zext B) - if (BO->getOpcode() == Instruction::Add || - BO->getOpcode() == Instruction::Sub) { - if (SignExtended && !BO->hasNoSignedWrap()) - return false; - if (ZeroExtended && !BO->hasNoUnsignedWrap()) - return false; - } - - return true; -} - -APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO, - bool SignExtended, - bool ZeroExtended) { - // Save off the current height of the chain, in case we need to restore it. - size_t ChainLength = UserChain.size(); - - // BO being non-negative does not shed light on whether its operands are - // non-negative. Clear the NonNegative flag here. - APInt ConstantOffset = find(BO->getOperand(0), SignExtended, ZeroExtended, - /* NonNegative */ false); - // If we found a constant offset in the left operand, stop and return that. - // This shortcut might cause us to miss opportunities of combining the - // constant offsets in both operands, e.g., (a + 4) + (b + 5) => (a + b) + 9. - // However, such cases are probably already handled by -instcombine, - // given this pass runs after the standard optimizations. - if (ConstantOffset != 0) return ConstantOffset; - - // Reset the chain back to where it was when we started exploring this node, - // since visiting the LHS didn't pan out. - UserChain.resize(ChainLength); - - ConstantOffset = find(BO->getOperand(1), SignExtended, ZeroExtended, - /* NonNegative */ false); - // If U is a sub operator, negate the constant offset found in the right - // operand. - if (BO->getOpcode() == Instruction::Sub) - ConstantOffset = -ConstantOffset; - - // If RHS wasn't a suitable candidate either, reset the chain again. - if (ConstantOffset == 0) - UserChain.resize(ChainLength); - - return ConstantOffset; -} - -APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended, - bool ZeroExtended, bool NonNegative) { - // TODO(jingyue): We could trace into integer/pointer casts, such as - // inttoptr, ptrtoint, bitcast, and addrspacecast. We choose to handle only - // integers because it gives good enough results for our benchmarks. - unsigned BitWidth = cast(V->getType())->getBitWidth(); - - // We cannot do much with Values that are not a User, such as an Argument. - User *U = dyn_cast(V); - if (U == nullptr) return APInt(BitWidth, 0); - - APInt ConstantOffset(BitWidth, 0); - if (ConstantInt *CI = dyn_cast(V)) { - // Hooray, we found it! - ConstantOffset = CI->getValue(); - } else if (BinaryOperator *BO = dyn_cast(V)) { - // Trace into subexpressions for more hoisting opportunities. - if (CanTraceInto(SignExtended, ZeroExtended, BO, NonNegative)) - ConstantOffset = findInEitherOperand(BO, SignExtended, ZeroExtended); - } else if (isa(V)) { - ConstantOffset = - find(U->getOperand(0), SignExtended, ZeroExtended, NonNegative) - .trunc(BitWidth); - } else if (isa(V)) { - ConstantOffset = find(U->getOperand(0), /* SignExtended */ true, - ZeroExtended, NonNegative).sext(BitWidth); - } else if (isa(V)) { - // As an optimization, we can clear the SignExtended flag because - // sext(zext(a)) = zext(a). Verified in @sext_zext in split-gep.ll. - // - // Clear the NonNegative flag, because zext(a) >= 0 does not imply a >= 0. - ConstantOffset = - find(U->getOperand(0), /* SignExtended */ false, - /* ZeroExtended */ true, /* NonNegative */ false).zext(BitWidth); - } - - // If we found a non-zero constant offset, add it to the path for - // rebuildWithoutConstOffset. Zero is a valid constant offset, but doesn't - // help this optimization. - if (ConstantOffset != 0) - UserChain.push_back(U); - return ConstantOffset; -} - -Value *ConstantOffsetExtractor::applyExts(Value *V) { - Value *Current = V; - // ExtInsts is built in the use-def order. Therefore, we apply them to V - // in the reversed order. - for (CastInst *I : llvm::reverse(ExtInsts)) { - if (Constant *C = dyn_cast(Current)) { - // If Current is a constant, apply s/zext using ConstantExpr::getCast. - // ConstantExpr::getCast emits a ConstantInt if C is a ConstantInt. - Current = ConstantExpr::getCast(I->getOpcode(), C, I->getType()); - } else { - Instruction *Ext = I->clone(); - Ext->setOperand(0, Current); - Ext->insertBefore(IP); - Current = Ext; - } - } - return Current; -} - -Value *ConstantOffsetExtractor::rebuildWithoutConstOffset() { - distributeExtsAndCloneChain(UserChain.size() - 1); - // Remove all nullptrs (used to be s/zext) from UserChain. - unsigned NewSize = 0; - for (User *I : UserChain) { - if (I != nullptr) { - UserChain[NewSize] = I; - NewSize++; - } - } - UserChain.resize(NewSize); - return removeConstOffset(UserChain.size() - 1); -} - -Value * -ConstantOffsetExtractor::distributeExtsAndCloneChain(unsigned ChainIndex) { - User *U = UserChain[ChainIndex]; - if (ChainIndex == 0) { - assert(isa(U)); - // If U is a ConstantInt, applyExts will return a ConstantInt as well. - return UserChain[ChainIndex] = cast(applyExts(U)); - } - - if (CastInst *Cast = dyn_cast(U)) { - assert( - (isa(Cast) || isa(Cast) || isa(Cast)) && - "Only following instructions can be traced: sext, zext & trunc"); - ExtInsts.push_back(Cast); - UserChain[ChainIndex] = nullptr; - return distributeExtsAndCloneChain(ChainIndex - 1); - } - - // Function find only trace into BinaryOperator and CastInst. - BinaryOperator *BO = cast(U); - // OpNo = which operand of BO is UserChain[ChainIndex - 1] - unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1); - Value *TheOther = applyExts(BO->getOperand(1 - OpNo)); - Value *NextInChain = distributeExtsAndCloneChain(ChainIndex - 1); - - BinaryOperator *NewBO = nullptr; - if (OpNo == 0) { - NewBO = BinaryOperator::Create(BO->getOpcode(), NextInChain, TheOther, - BO->getName(), IP); - } else { - NewBO = BinaryOperator::Create(BO->getOpcode(), TheOther, NextInChain, - BO->getName(), IP); - } - return UserChain[ChainIndex] = NewBO; -} - -Value *ConstantOffsetExtractor::removeConstOffset(unsigned ChainIndex) { - if (ChainIndex == 0) { - assert(isa(UserChain[ChainIndex])); - return ConstantInt::getNullValue(UserChain[ChainIndex]->getType()); - } - - BinaryOperator *BO = cast(UserChain[ChainIndex]); - assert((BO->use_empty() || BO->hasOneUse()) && - "distributeExtsAndCloneChain clones each BinaryOperator in " - "UserChain, so no one should be used more than " - "once"); - - unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1); - assert(BO->getOperand(OpNo) == UserChain[ChainIndex - 1]); - Value *NextInChain = removeConstOffset(ChainIndex - 1); - Value *TheOther = BO->getOperand(1 - OpNo); - - // If NextInChain is 0 and not the LHS of a sub, we can simplify the - // sub-expression to be just TheOther. - if (ConstantInt *CI = dyn_cast(NextInChain)) { - if (CI->isZero() && !(BO->getOpcode() == Instruction::Sub && OpNo == 0)) - return TheOther; - } - - BinaryOperator::BinaryOps NewOp = BO->getOpcode(); - if (BO->getOpcode() == Instruction::Or) { - // Rebuild "or" as "add", because "or" may be invalid for the new - // expression. - // - // For instance, given - // a | (b + 5) where a and b + 5 have no common bits, - // we can extract 5 as the constant offset. - // - // However, reusing the "or" in the new index would give us - // (a | b) + 5 - // which does not equal a | (b + 5). - // - // Replacing the "or" with "add" is fine, because - // a | (b + 5) = a + (b + 5) = (a + b) + 5 - NewOp = Instruction::Add; - } - - BinaryOperator *NewBO; - if (OpNo == 0) { - NewBO = BinaryOperator::Create(NewOp, NextInChain, TheOther, "", IP); - } else { - NewBO = BinaryOperator::Create(NewOp, TheOther, NextInChain, "", IP); - } - NewBO->takeName(BO); - return NewBO; -} - -Value *ConstantOffsetExtractor::Extract(Value *Idx, GetElementPtrInst *GEP, - User *&UserChainTail, - const DominatorTree *DT) { - ConstantOffsetExtractor Extractor(GEP, DT); - // Find a non-zero constant offset first. - APInt ConstantOffset = - Extractor.find(Idx, /* SignExtended */ false, /* ZeroExtended */ false, - GEP->isInBounds()); - if (ConstantOffset == 0) { - UserChainTail = nullptr; - return nullptr; - } - // Separates the constant offset from the GEP index. - Value *IdxWithoutConstOffset = Extractor.rebuildWithoutConstOffset(); - UserChainTail = Extractor.UserChain.back(); - return IdxWithoutConstOffset; -} - -int64_t ConstantOffsetExtractor::Find(Value *Idx, GetElementPtrInst *GEP, - const DominatorTree *DT) { - // If Idx is an index of an inbound GEP, Idx is guaranteed to be non-negative. - return ConstantOffsetExtractor(GEP, DT) - .find(Idx, /* SignExtended */ false, /* ZeroExtended */ false, - GEP->isInBounds()) - .getSExtValue(); -} - bool SeparateConstOffsetFromGEP::canonicalizeArrayIndicesToPointerSize( GetElementPtrInst *GEP) { bool Changed = false; Type *IntPtrTy = DL->getIntPtrType(GEP->getType()); gep_type_iterator GTI = gep_type_begin(*GEP); - for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end(); - I != E; ++I, ++GTI) { + for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end(); I != E; + ++I, ++GTI) { // Skip struct member indices which must be i32. if (GTI.isSequential()) { if ((*I)->getType() != IntPtrTy) { @@ -856,9 +437,8 @@ Value *ResultPtr = Variadic->getOperand(0); Loop *L = LI->getLoopFor(Variadic->getParent()); // Check if the base is not loop invariant or used more than once. - bool isSwapCandidate = - L && L->isLoopInvariant(ResultPtr) && - !hasMoreThanOneUseInLoop(ResultPtr, L); + bool isSwapCandidate = L && L->isLoopInvariant(ResultPtr) && + !hasMoreThanOneUseInLoop(ResultPtr, L); Value *FirstResult = nullptr; if (ResultPtr->getType() != I8PtrTy) @@ -917,9 +497,8 @@ Variadic->eraseFromParent(); } -void -SeparateConstOffsetFromGEP::lowerToArithmetics(GetElementPtrInst *Variadic, - int64_t AccumulativeByteOffset) { +void SeparateConstOffsetFromGEP::lowerToArithmetics( + GetElementPtrInst *Variadic, int64_t AccumulativeByteOffset) { IRBuilder<> Builder(Variadic); Type *IntPtrTy = DL->getIntPtrType(Variadic->getType()); @@ -1102,8 +681,8 @@ // Per ANSI C standard, signed / unsigned = unsigned and signed % unsigned = // unsigned.. Therefore, we cast ElementTypeSizeOfGEP to signed because it is // used with unsigned integers later. - int64_t ElementTypeSizeOfGEP = static_cast( - DL->getTypeAllocSize(GEP->getResultElementType())); + int64_t ElementTypeSizeOfGEP = + static_cast(DL->getTypeAllocSize(GEP->getResultElementType())); Type *IntPtrTy = DL->getIntPtrType(GEP->getType()); if (AccumulativeByteOffset % ElementTypeSizeOfGEP == 0) { // Very likely. As long as %gep is naturally aligned, the byte offset we @@ -1368,8 +947,7 @@ Value *NewBase = First->stripAndAccumulateInBoundsConstantOffsets(DAL, Offset); uint64_t ObjectSize; - if (!getObjectSize(NewBase, ObjectSize, DAL, TLI) || - Offset.ugt(ObjectSize)) { + if (!getObjectSize(NewBase, ObjectSize, DAL, TLI) || Offset.ugt(ObjectSize)) { First->setIsInBounds(false); Second->setIsInBounds(false); } else diff --git a/llvm/lib/Transforms/Utils/CMakeLists.txt b/llvm/lib/Transforms/Utils/CMakeLists.txt --- a/llvm/lib/Transforms/Utils/CMakeLists.txt +++ b/llvm/lib/Transforms/Utils/CMakeLists.txt @@ -16,6 +16,7 @@ CodeExtractor.cpp CodeLayout.cpp CodeMoverUtils.cpp + ConstantOffsetExtractor.cpp CtorUtils.cpp Debugify.cpp DemoteRegToStack.cpp diff --git a/llvm/lib/Transforms/Utils/ConstantOffsetExtractor.cpp b/llvm/lib/Transforms/Utils/ConstantOffsetExtractor.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Transforms/Utils/ConstantOffsetExtractor.cpp @@ -0,0 +1,301 @@ +// +// Created by Naville on 2023/1/14. +// + +#include "llvm/Transforms/Utils/ConstantOffsetExtractor.h" +#include "llvm/Analysis/ValueTracking.h" +#include "llvm/IR/Constants.h" +namespace llvm { +bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended, bool ZeroExtended, + BinaryOperator *BO, + bool NonNegative) { + // We only consider ADD, SUB and OR, because a non-zero constant found in + // expressions composed of these operations can be easily hoisted as a + // constant offset by reassociation. + if (BO->getOpcode() != Instruction::Add && + BO->getOpcode() != Instruction::Sub && + BO->getOpcode() != Instruction::Or) { + return false; + } + + Value *LHS = BO->getOperand(0), *RHS = BO->getOperand(1); + // Do not trace into "or" unless it is equivalent to "add". If LHS and RHS + // don't have common bits, (LHS | RHS) is equivalent to (LHS + RHS). + // FIXME: this does not appear to be covered by any tests + // (with x86/aarch64 backends at least) + if (BO->getOpcode() == Instruction::Or && + !haveNoCommonBitsSet(LHS, RHS, DL, nullptr, BO, DT)) + return false; + + // In addition, tracing into BO requires that its surrounding s/zext (if + // any) is distributable to both operands. + // + // Suppose BO = A op B. + // SignExtended | ZeroExtended | Distributable? + // --------------+--------------+---------------------------------- + // 0 | 0 | true because no s/zext exists + // 0 | 1 | zext(BO) == zext(A) op zext(B) + // 1 | 0 | sext(BO) == sext(A) op sext(B) + // 1 | 1 | zext(sext(BO)) == + // | | zext(sext(A)) op zext(sext(B)) + if (BO->getOpcode() == Instruction::Add && !ZeroExtended && NonNegative) { + // If a + b >= 0 and (a >= 0 or b >= 0), then + // sext(a + b) = sext(a) + sext(b) + // even if the addition is not marked nsw. + // + // Leveraging this invariant, we can trace into an sext'ed inbound GEP + // index if the constant offset is non-negative. + // + // Verified in @sext_add in split-gep.ll. + if (ConstantInt *ConstLHS = dyn_cast(LHS)) { + if (!ConstLHS->isNegative()) + return true; + } + if (ConstantInt *ConstRHS = dyn_cast(RHS)) { + if (!ConstRHS->isNegative()) + return true; + } + } + + // sext (add/sub nsw A, B) == add/sub nsw (sext A), (sext B) + // zext (add/sub nuw A, B) == add/sub nuw (zext A), (zext B) + if (BO->getOpcode() == Instruction::Add || + BO->getOpcode() == Instruction::Sub) { + if (SignExtended && !BO->hasNoSignedWrap()) + return false; + if (ZeroExtended && !BO->hasNoUnsignedWrap()) + return false; + } + + return true; +} + +APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO, + bool SignExtended, + bool ZeroExtended) { + // Save off the current height of the chain, in case we need to restore it. + size_t ChainLength = UserChain.size(); + + // BO being non-negative does not shed light on whether its operands are + // non-negative. Clear the NonNegative flag here. + APInt ConstantOffset = find(BO->getOperand(0), SignExtended, ZeroExtended, + /* NonNegative */ false); + // If we found a constant offset in the left operand, stop and return that. + // This shortcut might cause us to miss opportunities of combining the + // constant offsets in both operands, e.g., (a + 4) + (b + 5) => (a + b) + 9. + // However, such cases are probably already handled by -instcombine, + // given this pass runs after the standard optimizations. + if (ConstantOffset != 0) + return ConstantOffset; + + // Reset the chain back to where it was when we started exploring this node, + // since visiting the LHS didn't pan out. + UserChain.resize(ChainLength); + + ConstantOffset = find(BO->getOperand(1), SignExtended, ZeroExtended, + /* NonNegative */ false); + // If U is a sub operator, negate the constant offset found in the right + // operand. + if (BO->getOpcode() == Instruction::Sub) + ConstantOffset = -ConstantOffset; + + // If RHS wasn't a suitable candidate either, reset the chain again. + if (ConstantOffset == 0) + UserChain.resize(ChainLength); + + return ConstantOffset; +} + +APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended, + bool ZeroExtended, bool NonNegative) { + // TODO(jingyue): We could trace into integer/pointer casts, such as + // inttoptr, ptrtoint, bitcast, and addrspacecast. We choose to handle only + // integers because it gives good enough results for our benchmarks. + unsigned BitWidth = cast(V->getType())->getBitWidth(); + + // We cannot do much with Values that are not a User, such as an Argument. + User *U = dyn_cast(V); + if (U == nullptr) + return APInt(BitWidth, 0); + + APInt ConstantOffset(BitWidth, 0); + if (ConstantInt *CI = dyn_cast(V)) { + // Hooray, we found it! + ConstantOffset = CI->getValue(); + } else if (BinaryOperator *BO = dyn_cast(V)) { + // Trace into subexpressions for more hoisting opportunities. + if (CanTraceInto(SignExtended, ZeroExtended, BO, NonNegative)) + ConstantOffset = findInEitherOperand(BO, SignExtended, ZeroExtended); + } else if (isa(V)) { + ConstantOffset = + find(U->getOperand(0), SignExtended, ZeroExtended, NonNegative) + .trunc(BitWidth); + } else if (isa(V)) { + ConstantOffset = find(U->getOperand(0), /* SignExtended */ true, + ZeroExtended, NonNegative) + .sext(BitWidth); + } else if (isa(V)) { + // As an optimization, we can clear the SignExtended flag because + // sext(zext(a)) = zext(a). Verified in @sext_zext in split-gep.ll. + // + // Clear the NonNegative flag, because zext(a) >= 0 does not imply a >= 0. + ConstantOffset = find(U->getOperand(0), /* SignExtended */ false, + /* ZeroExtended */ true, /* NonNegative */ false) + .zext(BitWidth); + } + + // If we found a non-zero constant offset, add it to the path for + // rebuildWithoutConstOffset. Zero is a valid constant offset, but doesn't + // help this optimization. + if (ConstantOffset != 0) + UserChain.push_back(U); + return ConstantOffset; +} + +Value *ConstantOffsetExtractor::applyExts(Value *V) { + Value *Current = V; + // ExtInsts is built in the use-def order. Therefore, we apply them to V + // in the reversed order. + for (CastInst *I : llvm::reverse(ExtInsts)) { + if (Constant *C = dyn_cast(Current)) { + // If Current is a constant, apply s/zext using ConstantExpr::getCast. + // ConstantExpr::getCast emits a ConstantInt if C is a ConstantInt. + Current = ConstantExpr::getCast(I->getOpcode(), C, I->getType()); + } else { + Instruction *Ext = I->clone(); + Ext->setOperand(0, Current); + Ext->insertBefore(IP); + Current = Ext; + } + } + return Current; +} + +Value *ConstantOffsetExtractor::rebuildWithoutConstOffset() { + distributeExtsAndCloneChain(UserChain.size() - 1); + // Remove all nullptrs (used to be s/zext) from UserChain. + unsigned NewSize = 0; + for (User *I : UserChain) { + if (I != nullptr) { + UserChain[NewSize] = I; + NewSize++; + } + } + UserChain.resize(NewSize); + return removeConstOffset(UserChain.size() - 1); +} + +Value * +ConstantOffsetExtractor::distributeExtsAndCloneChain(unsigned ChainIndex) { + User *U = UserChain[ChainIndex]; + if (ChainIndex == 0) { + assert(isa(U)); + // If U is a ConstantInt, applyExts will return a ConstantInt as well. + return UserChain[ChainIndex] = cast(applyExts(U)); + } + + if (CastInst *Cast = dyn_cast(U)) { + assert( + (isa(Cast) || isa(Cast) || isa(Cast)) && + "Only following instructions can be traced: sext, zext & trunc"); + ExtInsts.push_back(Cast); + UserChain[ChainIndex] = nullptr; + return distributeExtsAndCloneChain(ChainIndex - 1); + } + + // Function find only trace into BinaryOperator and CastInst. + BinaryOperator *BO = cast(U); + // OpNo = which operand of BO is UserChain[ChainIndex - 1] + unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1); + Value *TheOther = applyExts(BO->getOperand(1 - OpNo)); + Value *NextInChain = distributeExtsAndCloneChain(ChainIndex - 1); + + BinaryOperator *NewBO = nullptr; + if (OpNo == 0) { + NewBO = BinaryOperator::Create(BO->getOpcode(), NextInChain, TheOther, + BO->getName(), IP); + } else { + NewBO = BinaryOperator::Create(BO->getOpcode(), TheOther, NextInChain, + BO->getName(), IP); + } + return UserChain[ChainIndex] = NewBO; +} + +Value *ConstantOffsetExtractor::removeConstOffset(unsigned ChainIndex) { + if (ChainIndex == 0) { + assert(isa(UserChain[ChainIndex])); + return ConstantInt::getNullValue(UserChain[ChainIndex]->getType()); + } + + BinaryOperator *BO = cast(UserChain[ChainIndex]); + assert((BO->use_empty() || BO->hasOneUse()) && + "distributeExtsAndCloneChain clones each BinaryOperator in " + "UserChain, so no one should be used more than " + "once"); + + unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1); + assert(BO->getOperand(OpNo) == UserChain[ChainIndex - 1]); + Value *NextInChain = removeConstOffset(ChainIndex - 1); + Value *TheOther = BO->getOperand(1 - OpNo); + + // If NextInChain is 0 and not the LHS of a sub, we can simplify the + // sub-expression to be just TheOther. + if (ConstantInt *CI = dyn_cast(NextInChain)) { + if (CI->isZero() && !(BO->getOpcode() == Instruction::Sub && OpNo == 0)) + return TheOther; + } + + BinaryOperator::BinaryOps NewOp = BO->getOpcode(); + if (BO->getOpcode() == Instruction::Or) { + // Rebuild "or" as "add", because "or" may be invalid for the new + // expression. + // + // For instance, given + // a | (b + 5) where a and b + 5 have no common bits, + // we can extract 5 as the constant offset. + // + // However, reusing the "or" in the new index would give us + // (a | b) + 5 + // which does not equal a | (b + 5). + // + // Replacing the "or" with "add" is fine, because + // a | (b + 5) = a + (b + 5) = (a + b) + 5 + NewOp = Instruction::Add; + } + + BinaryOperator *NewBO; + if (OpNo == 0) { + NewBO = BinaryOperator::Create(NewOp, NextInChain, TheOther, "", IP); + } else { + NewBO = BinaryOperator::Create(NewOp, TheOther, NextInChain, "", IP); + } + NewBO->takeName(BO); + return NewBO; +} +Value *ConstantOffsetExtractor::Extract(Value *Idx, GetElementPtrInst *GEP, + User *&UserChainTail, + const DominatorTree *DT) { + ConstantOffsetExtractor Extractor(GEP, DT); + // Find a non-zero constant offset first. + APInt ConstantOffset = + Extractor.find(Idx, /* SignExtended */ false, /* ZeroExtended */ false, + GEP->isInBounds()); + if (ConstantOffset == 0) { + UserChainTail = nullptr; + return nullptr; + } + // Separates the constant offset from the GEP index. + Value *IdxWithoutConstOffset = Extractor.rebuildWithoutConstOffset(); + UserChainTail = Extractor.UserChain.back(); + return IdxWithoutConstOffset; +} + +int64_t ConstantOffsetExtractor::Find(Value *Idx, GetElementPtrInst *GEP, + const DominatorTree *DT) { + // If Idx is an index of an inbound GEP, Idx is guaranteed to be non-negative. + return ConstantOffsetExtractor(GEP, DT) + .find(Idx, /* SignExtended */ false, /* ZeroExtended */ false, + GEP->isInBounds()) + .getSExtValue(); +} +} // namespace llvm