Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

34 // each GEP, wasting tons of registers. It emits the following PTX for the
50 // It works by splitting each GEP into a variadic base and a constant offset.
81 // Another improvement enabled by the LowerGEP flag is to lower a GEP with
102 // lower a GEP with multiple indices into arithmetic operations:
124 // If the target uses alias analysis in codegen, this pass will lower a GEP
148 // LICM (Loop Invariant Code Motion) can not hoist/sink a GEP of multiple
149 // indices if one of the index is variant. If we lower such GEP into invariant
152 // target's addressing modes. A GEP with multiple indices may not match and will
153 // not be sunk. If we lower such GEP into smaller parts, CGP may sink some of
202     cl::desc("Do not separate the constant offset from a GEP instruction"),
215 /// A helper class for separating a constant offset from a GEP index.
217 /// In real programs, a GEP index may be more complicated than a simple addition
222 /// Therefore, this class looks into the expression that computes a given GEP
230   /// Extracts a constant offset from the given GEP index. It returns the
233   /// \p Idx The given GEP index
234   /// \p GEP The given GEP
237   static Value *Extract(Value *Idx, GetElementPtrInst *GEP,
240   /// Looks for a constant offset from the given GEP index without extracting
243   static int64_t Find(Value *Idx, GetElementPtrInst *GEP,
258   ///                 GEP index
260   ///                 GEP index
262   ///                 an index of an inbounds GEP is guaranteed to be
271   /// After finding the constant offset C from the GEP index I, we build a new
288   /// After the first step of rebuilding the GEP index without the constant
305   /// Reassociates the GEP index to the form I' + C and returns I'.
323   /// The path from the constant offset to the old GEP index. e.g., if the GEP
328   /// This path helps to rebuild the new GEP index.
342 /// A pass that tries to split every GEP in the function into a variadic
371   /// Tries to split the given GEP into a variadic base and a constant offset,
373   bool splitGEP(GetElementPtrInst *GEP);
375   /// Lower a GEP with multiple indices into multiple GEPs with a single index.
376   /// Function splitGEP already split the original GEP into a variadic part and
380   /// \p Variadic                  The variadic part of the original GEP.
385   /// Lower a GEP with multiple indices into ptrtoint+arithmetics+inttoptr form.
386   /// Function splitGEP already split the original GEP into a variadic part and
390   /// \p Variadic                  The variadic part of the original GEP.
400   int64_t accumulateByteOffset(GetElementPtrInst *GEP, bool &NeedsExtraction);
403   /// simplify the logic of splitting a GEP. For example, if a + b is a
407   /// the pointer size, because LLVM conceptually sign-extends GEP indices to
417   bool canonicalizeArrayIndicesToPointerSize(GetElementPtrInst *GEP);
441   // Swap the index operand of two GEP.
444   // Check if it is safe to swap operand of two GEP.
455   /// Whether to lower a GEP with multiple indices into arithmetic operations or
522     // Leveraging this invarient, we can trace into an sext'ed inbound GEP
736 Value *ConstantOffsetExtractor::Extract(Value *Idx, GetElementPtrInst *GEP,
739   ConstantOffsetExtractor Extractor(GEP, DT);
743                      GEP->isInBounds());
748   // Separates the constant offset from the GEP index.
754 int64_t ConstantOffsetExtractor::Find(Value *Idx, GetElementPtrInst *GEP,
756   // If Idx is an index of an inbound GEP, Idx is guaranteed to be non-negative.
757   return ConstantOffsetExtractor(GEP, DT)
759             GEP->isInBounds())
764     GetElementPtrInst *GEP) {
766   Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
767   gep_type_iterator GTI = gep_type_begin(*GEP);
768   for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end();
773         *I = CastInst::CreateIntegerCast(*I, IntPtrTy, true, "idxprom", GEP);
782 SeparateConstOffsetFromGEP::accumulateByteOffset(GetElementPtrInst *GEP,
786   gep_type_iterator GTI = gep_type_begin(*GEP);
787   for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
789       // Tries to extract a constant offset from this GEP index.
791           ConstantOffsetExtractor::Find(GEP->getOperand(I), GEP, DT);
794         // A GEP may have multiple indices.  We accumulate the extracted
796         // the original GEP with this byte offset.
802       uint64_t Field = cast<ConstantInt>(GEP->getOperand(I))->getZExtValue();
833   // Create an ugly GEP for each sequential index. We don't create GEPs for
854       // Create an ugly GEP with a single index for each index.
862   // Create a GEP with the constant offset index.
870   // If we created a GEP with constant index, and the base is loop invariant,
871   // then we swap the first one with it, so LICM can move constant GEP out
931 bool SeparateConstOffsetFromGEP::splitGEP(GetElementPtrInst *GEP) {
933   if (GEP->getType()->isVectorTy())
938   if (GEP->hasAllConstantIndices())
941   bool Changed = canonicalizeArrayIndicesToPointerSize(GEP);
944   int64_t AccumulativeByteOffset = accumulateByteOffset(GEP, NeedsExtraction);
950       getAnalysis<TargetTransformInfoWrapperPass>().getTTI(*GEP->getFunction());
952   // If LowerGEP is disabled, before really splitting the GEP, check whether the
960     unsigned AddrSpace = GEP->getPointerAddressSpace();
961     if (!TTI.isLegalAddressingMode(GEP->getResultElementType(),
969   // Remove the constant offset in each sequential index. The resultant GEP
976   gep_type_iterator GTI = gep_type_begin(*GEP);
977   for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
979       // Splits this GEP index into a variadic part and a constant offset, and
981       Value *OldIdx = GEP->getOperand(I);
984           ConstantOffsetExtractor::Extract(OldIdx, GEP, UserChainTail, DT);
987         GEP->setOperand(I, NewIdx);
1015   bool GEPWasInBounds = GEP->isInBounds();
1016   GEP->setIsInBounds(false);
1018   // Lowers a GEP to either GEPs with a single index or arithmetic operations.
1023       lowerToSingleIndexGEPs(GEP, AccumulativeByteOffset);
1025       lowerToArithmetics(GEP, AccumulativeByteOffset);
1029   // No need to create another GEP if the accumulative byte offset is 0.
1061   Instruction *NewGEP = GEP->clone();
1062   NewGEP->insertBefore(GEP);
1068       DL->getTypeAllocSize(GEP->getResultElementType()));
1069   Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
1074     NewGEP = GetElementPtrInst::Create(GEP->getResultElementType(), NewGEP,
1076                                        GEP->getName(), GEP);
1077     NewGEP->copyMetadata(*GEP);
1078     // Inherit the inbounds attribute of the original GEP.
1095     Type *I8PtrTy = Type::getInt8PtrTy(GEP->getContext(),
1096                                        GEP->getPointerAddressSpace());
1097     NewGEP = new BitCastInst(NewGEP, I8PtrTy, "", GEP);
1099         Type::getInt8Ty(GEP->getContext()), NewGEP,
1101         GEP);
1102     NewGEP->copyMetadata(*GEP);
1103     // Inherit the inbounds attribute of the original GEP.
1105     if (GEP->getType() != I8PtrTy)
1106       NewGEP = new BitCastInst(NewGEP, GEP->getType(), GEP->getName(), GEP);
1109   GEP->replaceAllUsesWith(NewGEP);
1110   GEP->eraseFromParent();
1129       if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I++))
1130         Changed |= splitGEP(GEP);
1131     // No need to split GEP ConstantExprs because all its indices are constant
1245   // Give up if the index of the first GEP is loop invariant.
1255   // Check if the second operand of first GEP has constant coefficient.
1257   // hoisting the second GEP out because the second GEP can be folded away.