lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp

   1 //===-- SeparateConstOffsetFromGEP.cpp - ------------------------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // Loop unrolling may create many similar GEPs for array accesses.
  11 // e.g., a 2-level loop
  12 //
  13 // float a[32][32]; // global variable
  14 //
  15 // for (int i = 0; i < 2; ++i) {
  16 //   for (int j = 0; j < 2; ++j) {
  17 //     ...
  18 //     ... = a[x + i][y + j];
  19 //     ...
  20 //   }
  21 // }
  22 //
  23 // will probably be unrolled to:
  24 //
  25 // gep %a, 0, %x, %y; load
  26 // gep %a, 0, %x, %y + 1; load
  27 // gep %a, 0, %x + 1, %y; load
  28 // gep %a, 0, %x + 1, %y + 1; load
  29 //
  30 // LLVM's GVN does not use partial redundancy elimination yet, and is thus
  31 // unable to reuse (gep %a, 0, %x, %y). As a result, this misoptimization incurs
  32 // significant slowdown in targets with limited addressing modes. For instance,
  33 // because the PTX target does not support the reg+reg addressing mode, the
  34 // NVPTX backend emits PTX code that literally computes the pointer address of
  35 // each GEP, wasting tons of registers. It emits the following PTX for the
  36 // first load and similar PTX for other loads.
  37 //
  38 // mov.u32         %r1, %x;
  39 // mov.u32         %r2, %y;
  40 // mul.wide.u32    %rl2, %r1, 128;
  41 // mov.u64         %rl3, a;
  42 // add.s64         %rl4, %rl3, %rl2;
  43 // mul.wide.u32    %rl5, %r2, 4;
  44 // add.s64         %rl6, %rl4, %rl5;
  45 // ld.global.f32   %f1, [%rl6];
  46 //
  47 // To reduce the register pressure, the optimization implemented in this file
  48 // merges the common part of a group of GEPs, so we can compute each pointer
  49 // address by adding a simple offset to the common part, saving many registers.
  50 //
  51 // It works by splitting each GEP into a variadic base and a constant offset.
  52 // The variadic base can be computed once and reused by multiple GEPs, and the
  53 // constant offsets can be nicely folded into the reg+immediate addressing mode
  54 // (supported by most targets) without using any extra register.
  55 //
  56 // For instance, we transform the four GEPs and four loads in the above example
  57 // into:
  58 //
  59 // base = gep a, 0, x, y
  60 // load base
  61 // laod base + 1  * sizeof(float)
  62 // load base + 32 * sizeof(float)
  63 // load base + 33 * sizeof(float)
  64 //
  65 // Given the transformed IR, a backend that supports the reg+immediate
  66 // addressing mode can easily fold the pointer arithmetics into the loads. For
  67 // example, the NVPTX backend can easily fold the pointer arithmetics into the
  68 // ld.global.f32 instructions, and the resultant PTX uses much fewer registers.
  69 //
  70 // mov.u32         %r1, %tid.x;
  71 // mov.u32         %r2, %tid.y;
  72 // mul.wide.u32    %rl2, %r1, 128;
  73 // mov.u64         %rl3, a;
  74 // add.s64         %rl4, %rl3, %rl2;
  75 // mul.wide.u32    %rl5, %r2, 4;
  76 // add.s64         %rl6, %rl4, %rl5;
  77 // ld.global.f32   %f1, [%rl6]; // so far the same as unoptimized PTX
  78 // ld.global.f32   %f2, [%rl6+4]; // much better
  79 // ld.global.f32   %f3, [%rl6+128]; // much better
  80 // ld.global.f32   %f4, [%rl6+132]; // much better
  81 //
  82 //===----------------------------------------------------------------------===//
  83
  84 #include "llvm/Analysis/TargetTransformInfo.h"
  85 #include "llvm/Analysis/ValueTracking.h"
  86 #include "llvm/IR/Constants.h"
  87 #include "llvm/IR/DataLayout.h"
  88 #include "llvm/IR/Instructions.h"
  89 #include "llvm/IR/LLVMContext.h"
  90 #include "llvm/IR/Module.h"
  91 #include "llvm/IR/Operator.h"
  92 #include "llvm/Support/CommandLine.h"
  93 #include "llvm/Support/raw_ostream.h"
  94 #include "llvm/Transforms/Scalar.h"
  95
  96 using namespace llvm;
  97
  98 static cl::opt<bool> DisableSeparateConstOffsetFromGEP(
  99     "disable-separate-const-offset-from-gep", cl::init(false),
 100     cl::desc("Do not separate the constant offset from a GEP instruction"),
 101     cl::Hidden);
 102
 103 namespace {
 104
 105 /// \brief A helper class for separating a constant offset from a GEP index.
 106 ///
 107 /// In real programs, a GEP index may be more complicated than a simple addition
 108 /// of something and a constant integer which can be trivially splitted. For
 109 /// example, to split ((a << 3) | 5) + b, we need to search deeper for the
 110 /// constant offset, so that we can separate the index to (a << 3) + b and 5.
 111 ///
 112 /// Therefore, this class looks into the expression that computes a given GEP
 113 /// index, and tries to find a constant integer that can be hoisted to the
 114 /// outermost level of the expression as an addition. Not every constant in an
 115 /// expression can jump out. e.g., we cannot transform (b * (a + 5)) to (b * a +
 116 /// 5); nor can we transform (3 * (a + 5)) to (3 * a + 5), however in this case,
 117 /// -instcombine probably already optimized (3 * (a + 5)) to (3 * a + 15).
 118 class ConstantOffsetExtractor {
 119  public:
 120   /// Extracts a constant offset from the given GEP index. It outputs the
 121   /// numeric value of the extracted constant offset (0 if failed), and a
 122   /// new index representing the remainder (equal to the original index minus
 123   /// the constant offset).
 124   /// \p Idx    The given GEP index
 125   /// \p NewIdx The new index to replace (output)
 126   /// \p DL     The datalayout of the module
 127   /// \p GEP    The given GEP
 128   static int64_t Extract(Value *Idx, Value *&NewIdx, const DataLayout *DL,
 129                          GetElementPtrInst *GEP);
 130   /// Looks for a constant offset without extracting it. The meaning of the
 131   /// arguments and the return value are the same as Extract.
 132   static int64_t Find(Value *Idx, const DataLayout *DL, GetElementPtrInst *GEP);
 133
 134  private:
 135   ConstantOffsetExtractor(const DataLayout *Layout, Instruction *InsertionPt)
 136       : DL(Layout), IP(InsertionPt) {}
 137   /// Searches the expression that computes V for a non-zero constant C s.t.
 138   /// V can be reassociated into the form V' + C. If the searching is
 139   /// successful, returns C and update UserChain as a def-use chain from C to V;
 140   /// otherwise, UserChain is empty.
 141   ///
 142   /// \p V            The given expression
 143   /// \p SignExtended Whether V will be sign-extended in the computation of the
 144   ///                 GEP index
 145   /// \p ZeroExtended Whether V will be zero-extended in the computation of the
 146   ///                 GEP index
 147   /// \p NonNegative  Whether V is guaranteed to be non-negative. For example,
 148   ///                 an index of an inbounds GEP is guaranteed to be
 149   ///                 non-negative. Levaraging this, we can better split
 150   ///                 inbounds GEPs.
 151   APInt find(Value *V, bool SignExtended, bool ZeroExtended, bool NonNegative);
 152   /// A helper function to look into both operands of a binary operator.
 153   APInt findInEitherOperand(BinaryOperator *BO, bool SignExtended,
 154                             bool ZeroExtended);
 155   /// After finding the constant offset C from the GEP index I, we build a new
 156   /// index I' s.t. I' + C = I. This function builds and returns the new
 157   /// index I' according to UserChain produced by function "find".
 158   ///
 159   /// The building conceptually takes two steps:
 160   /// 1) iteratively distribute s/zext towards the leaves of the expression tree
 161   /// that computes I
 162   /// 2) reassociate the expression tree to the form I' + C.
 163   ///
 164   /// For example, to extract the 5 from sext(a + (b + 5)), we first distribute
 165   /// sext to a, b and 5 so that we have
 166   ///   sext(a) + (sext(b) + 5).
 167   /// Then, we reassociate it to
 168   ///   (sext(a) + sext(b)) + 5.
 169   /// Given this form, we know I' is sext(a) + sext(b).
 170   Value *rebuildWithoutConstOffset();
 171   /// After the first step of rebuilding the GEP index without the constant
 172   /// offset, distribute s/zext to the operands of all operators in UserChain.
 173   /// e.g., zext(sext(a + (b + 5)) (assuming no overflow) =>
 174   /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5))).
 175   ///
 176   /// The function also updates UserChain to point to new subexpressions after
 177   /// distributing s/zext. e.g., the old UserChain of the above example is
 178   /// 5 -> b + 5 -> a + (b + 5) -> sext(...) -> zext(sext(...)),
 179   /// and the new UserChain is
 180   /// zext(sext(5)) -> zext(sext(b)) + zext(sext(5)) ->
 181   ///   zext(sext(a)) + (zext(sext(b)) + zext(sext(5))
 182   ///
 183   /// \p ChainIndex The index to UserChain. ChainIndex is initially
 184   ///               UserChain.size() - 1, and is decremented during
 185   ///               the recursion.
 186   Value *distributeExtsAndCloneChain(unsigned ChainIndex);
 187   /// Reassociates the GEP index to the form I' + C and returns I'.
 188   Value *removeConstOffset(unsigned ChainIndex);
 189   /// A helper function to apply ExtInsts, a list of s/zext, to value V.
 190   /// e.g., if ExtInsts = [sext i32 to i64, zext i16 to i32], this function
 191   /// returns "sext i32 (zext i16 V to i32) to i64".
 192   Value *applyExts(Value *V);
 193
 194   /// Returns true if LHS and RHS have no bits in common, i.e., LHS | RHS == 0.
 195   bool NoCommonBits(Value *LHS, Value *RHS) const;
 196   /// Computes which bits are known to be one or zero.
 197   /// \p KnownOne Mask of all bits that are known to be one.
 198   /// \p KnownZero Mask of all bits that are known to be zero.
 199   void ComputeKnownBits(Value *V, APInt &KnownOne, APInt &KnownZero) const;
 200   /// A helper function that returns whether we can trace into the operands
 201   /// of binary operator BO for a constant offset.
 202   ///
 203   /// \p SignExtended Whether BO is surrounded by sext
 204   /// \p ZeroExtended Whether BO is surrounded by zext
 205   /// \p NonNegative Whether BO is known to be non-negative, e.g., an in-bound
 206   ///                array index.
 207   bool CanTraceInto(bool SignExtended, bool ZeroExtended, BinaryOperator *BO,
 208                     bool NonNegative);
 209
 210   /// The path from the constant offset to the old GEP index. e.g., if the GEP
 211   /// index is "a * b + (c + 5)". After running function find, UserChain[0] will
 212   /// be the constant 5, UserChain[1] will be the subexpression "c + 5", and
 213   /// UserChain[2] will be the entire expression "a * b + (c + 5)".
 214   ///
 215   /// This path helps to rebuild the new GEP index.
 216   SmallVector<User *, 8> UserChain;
 217   /// A data structure used in rebuildWithoutConstOffset. Contains all
 218   /// sext/zext instructions along UserChain.
 219   SmallVector<CastInst *, 16> ExtInsts;
 220   /// The data layout of the module. Used in ComputeKnownBits.
 221   const DataLayout *DL;
 222   Instruction *IP;  /// Insertion position of cloned instructions.
 223 };
 224
 225 /// \brief A pass that tries to split every GEP in the function into a variadic
 226 /// base and a constant offset. It is a FunctionPass because searching for the
 227 /// constant offset may inspect other basic blocks.
 228 class SeparateConstOffsetFromGEP : public FunctionPass {
 229  public:
 230   static char ID;
 231   SeparateConstOffsetFromGEP() : FunctionPass(ID) {
 232     initializeSeparateConstOffsetFromGEPPass(*PassRegistry::getPassRegistry());
 233   }
 234
 235   void getAnalysisUsage(AnalysisUsage &AU) const override {
 236     AU.addRequired<DataLayoutPass>();
 237     AU.addRequired<TargetTransformInfo>();
 238   }
 239
 240   bool doInitialization(Module &M) override {
 241     DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>();
 242     if (DLP == nullptr)
 243       report_fatal_error("data layout missing");
 244     DL = &DLP->getDataLayout();
 245     return false;
 246   }
 247
 248   bool runOnFunction(Function &F) override;
 249
 250  private:
 251   /// Tries to split the given GEP into a variadic base and a constant offset,
 252   /// and returns true if the splitting succeeds.
 253   bool splitGEP(GetElementPtrInst *GEP);
 254   /// Finds the constant offset within each index, and accumulates them. This
 255   /// function only inspects the GEP without changing it. The output
 256   /// NeedsExtraction indicates whether we can extract a non-zero constant
 257   /// offset from any index.
 258   int64_t accumulateByteOffset(GetElementPtrInst *GEP, bool &NeedsExtraction);
 259   /// Canonicalize array indices to pointer-size integers. This helps to
 260   /// simplify the logic of splitting a GEP. For example, if a + b is a
 261   /// pointer-size integer, we have
 262   ///   gep base, a + b = gep (gep base, a), b
 263   /// However, this equality may not hold if the size of a + b is smaller than
 264   /// the pointer size, because LLVM conceptually sign-extends GEP indices to
 265   /// pointer size before computing the address
 266   /// (http://llvm.org/docs/LangRef.html#id181).
 267   ///
 268   /// This canonicalization is very likely already done in clang and
 269   /// instcombine. Therefore, the program will probably remain the same.
 270   ///
 271   /// Verified in @i32_add in split-gep.ll
 272   bool canonicalizeArrayIndicesToPointerSize(GetElementPtrInst *GEP);
 273
 274   const DataLayout *DL;
 275 };
 276 }  // anonymous namespace
 277
 278 char SeparateConstOffsetFromGEP::ID = 0;
 279 INITIALIZE_PASS_BEGIN(
 280     SeparateConstOffsetFromGEP, "separate-const-offset-from-gep",
 281     "Split GEPs to a variadic base and a constant offset for better CSE", false,
 282     false)
 283 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
 284 INITIALIZE_PASS_DEPENDENCY(DataLayoutPass)
 285 INITIALIZE_PASS_END(
 286     SeparateConstOffsetFromGEP, "separate-const-offset-from-gep",
 287     "Split GEPs to a variadic base and a constant offset for better CSE", false,
 288     false)
 289
 290 FunctionPass *llvm::createSeparateConstOffsetFromGEPPass() {
 291   return new SeparateConstOffsetFromGEP();
 292 }
 293
 294 bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended,
 295                                             bool ZeroExtended,
 296                                             BinaryOperator *BO,
 297                                             bool NonNegative) {
 298   // We only consider ADD, SUB and OR, because a non-zero constant found in
 299   // expressions composed of these operations can be easily hoisted as a
 300   // constant offset by reassociation.
 301   if (BO->getOpcode() != Instruction::Add &&
 302       BO->getOpcode() != Instruction::Sub &&
 303       BO->getOpcode() != Instruction::Or) {
 304     return false;
 305   }
 306
 307   Value *LHS = BO->getOperand(0), *RHS = BO->getOperand(1);
 308   // Do not trace into "or" unless it is equivalent to "add". If LHS and RHS
 309   // don't have common bits, (LHS | RHS) is equivalent to (LHS + RHS).
 310   if (BO->getOpcode() == Instruction::Or && !NoCommonBits(LHS, RHS))
 311     return false;
 312
 313   // In addition, tracing into BO requires that its surrounding s/zext (if
 314   // any) is distributable to both operands.
 315   //
 316   // Suppose BO = A op B.
 317   //  SignExtended | ZeroExtended | Distributable?
 318   // --------------+--------------+----------------------------------
 319   //       0       |      0       | true because no s/zext exists
 320   //       0       |      1       | zext(BO) == zext(A) op zext(B)
 321   //       1       |      0       | sext(BO) == sext(A) op sext(B)
 322   //       1       |      1       | zext(sext(BO)) ==
 323   //               |              |     zext(sext(A)) op zext(sext(B))
 324   if (BO->getOpcode() == Instruction::Add && !ZeroExtended && NonNegative) {
 325     // If a + b >= 0 and (a >= 0 or b >= 0), then
 326     //   sext(a + b) = sext(a) + sext(b)
 327     // even if the addition is not marked nsw.
 328     //
 329     // Leveraging this invarient, we can trace into an sext'ed inbound GEP
 330     // index if the constant offset is non-negative.
 331     //
 332     // Verified in @sext_add in split-gep.ll.
 333     if (ConstantInt *ConstLHS = dyn_cast<ConstantInt>(LHS)) {
 334       if (!ConstLHS->isNegative())
 335         return true;
 336     }
 337     if (ConstantInt *ConstRHS = dyn_cast<ConstantInt>(RHS)) {
 338       if (!ConstRHS->isNegative())
 339         return true;
 340     }
 341   }
 342
 343   // sext (add/sub nsw A, B) == add/sub nsw (sext A), (sext B)
 344   // zext (add/sub nuw A, B) == add/sub nuw (zext A), (zext B)
 345   if (BO->getOpcode() == Instruction::Add ||
 346       BO->getOpcode() == Instruction::Sub) {
 347     if (SignExtended && !BO->hasNoSignedWrap())
 348       return false;
 349     if (ZeroExtended && !BO->hasNoUnsignedWrap())
 350       return false;
 351   }
 352
 353   return true;
 354 }
 355
 356 APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO,
 357                                                    bool SignExtended,
 358                                                    bool ZeroExtended) {
 359   // BO being non-negative does not shed light on whether its operands are
 360   // non-negative. Clear the NonNegative flag here.
 361   APInt ConstantOffset = find(BO->getOperand(0), SignExtended, ZeroExtended,
 362                               /* NonNegative */ false);
 363   // If we found a constant offset in the left operand, stop and return that.
 364   // This shortcut might cause us to miss opportunities of combining the
 365   // constant offsets in both operands, e.g., (a + 4) + (b + 5) => (a + b) + 9.
 366   // However, such cases are probably already handled by -instcombine,
 367   // given this pass runs after the standard optimizations.
 368   if (ConstantOffset != 0) return ConstantOffset;
 369   ConstantOffset = find(BO->getOperand(1), SignExtended, ZeroExtended,
 370                         /* NonNegative */ false);
 371   // If U is a sub operator, negate the constant offset found in the right
 372   // operand.
 373   if (BO->getOpcode() == Instruction::Sub)
 374     ConstantOffset = -ConstantOffset;
 375   return ConstantOffset;
 376 }
 377
 378 APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended,
 379                                     bool ZeroExtended, bool NonNegative) {
 380   // TODO(jingyue): We could trace into integer/pointer casts, such as
 381   // inttoptr, ptrtoint, bitcast, and addrspacecast. We choose to handle only
 382   // integers because it gives good enough results for our benchmarks.
 383   unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth();
 384
 385   // We cannot do much with Values that are not a User, such as an Argument.
 386   User *U = dyn_cast<User>(V);
 387   if (U == nullptr) return APInt(BitWidth, 0);
 388
 389   APInt ConstantOffset(BitWidth, 0);
 390   if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) {
 391     // Hooray, we found it!
 392     ConstantOffset = CI->getValue();
 393   } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) {
 394     // Trace into subexpressions for more hoisting opportunities.
 395     if (CanTraceInto(SignExtended, ZeroExtended, BO, NonNegative)) {
 396       ConstantOffset = findInEitherOperand(BO, SignExtended, ZeroExtended);
 397     }
 398   } else if (isa<SExtInst>(V)) {
 399     ConstantOffset = find(U->getOperand(0), /* SignExtended */ true,
 400                           ZeroExtended, NonNegative).sext(BitWidth);
 401   } else if (isa<ZExtInst>(V)) {
 402     // As an optimization, we can clear the SignExtended flag because
 403     // sext(zext(a)) = zext(a). Verified in @sext_zext in split-gep.ll.
 404     //
 405     // Clear the NonNegative flag, because zext(a) >= 0 does not imply a >= 0.
 406     // TODO: if zext(a) < 2 ^ (bitwidth(a) - 1), we can prove a >= 0.
 407     ConstantOffset =
 408         find(U->getOperand(0), /* SignExtended */ false,
 409              /* ZeroExtended */ true, /* NonNegative */ false).zext(BitWidth);
 410   }
 411
 412   // If we found a non-zero constant offset, add it to the path for
 413   // rebuildWithoutConstOffset. Zero is a valid constant offset, but doesn't
 414   // help this optimization.
 415   if (ConstantOffset != 0)
 416     UserChain.push_back(U);
 417   return ConstantOffset;
 418 }
 419
 420 Value *ConstantOffsetExtractor::applyExts(Value *V) {
 421   Value *Current = V;
 422   // ExtInsts is built in the use-def order. Therefore, we apply them to V
 423   // in the reversed order.
 424   for (auto I = ExtInsts.rbegin(), E = ExtInsts.rend(); I != E; ++I) {
 425     if (Constant *C = dyn_cast<Constant>(Current)) {
 426       // If Current is a constant, apply s/zext using ConstantExpr::getCast.
 427       // ConstantExpr::getCast emits a ConstantInt if C is a ConstantInt.
 428       Current = ConstantExpr::getCast((*I)->getOpcode(), C, (*I)->getType());
 429     } else {
 430       Instruction *Ext = (*I)->clone();
 431       Ext->setOperand(0, Current);
 432       Ext->insertBefore(IP);
 433       Current = Ext;
 434     }
 435   }
 436   return Current;
 437 }
 438
 439 Value *ConstantOffsetExtractor::rebuildWithoutConstOffset() {
 440   distributeExtsAndCloneChain(UserChain.size() - 1);
 441   // Remove all nullptrs (used to be s/zext) from UserChain.
 442   unsigned NewSize = 0;
 443   for (auto I = UserChain.begin(), E = UserChain.end(); I != E; ++I) {
 444     if (*I != nullptr) {
 445       UserChain[NewSize] = *I;
 446       NewSize++;
 447     }
 448   }
 449   UserChain.resize(NewSize);
 450   return removeConstOffset(UserChain.size() - 1);
 451 }
 452
 453 Value *
 454 ConstantOffsetExtractor::distributeExtsAndCloneChain(unsigned ChainIndex) {
 455   User *U = UserChain[ChainIndex];
 456   if (ChainIndex == 0) {
 457     assert(isa<ConstantInt>(U));
 458     // If U is a ConstantInt, applyExts will return a ConstantInt as well.
 459     return UserChain[ChainIndex] = cast<ConstantInt>(applyExts(U));
 460   }
 461
 462   if (CastInst *Cast = dyn_cast<CastInst>(U)) {
 463     assert((isa<SExtInst>(Cast) || isa<ZExtInst>(Cast)) &&
 464            "We only traced into two types of CastInst: sext and zext");
 465     ExtInsts.push_back(Cast);
 466     UserChain[ChainIndex] = nullptr;
 467     return distributeExtsAndCloneChain(ChainIndex - 1);
 468   }
 469
 470   // Function find only trace into BinaryOperator and CastInst.
 471   BinaryOperator *BO = cast<BinaryOperator>(U);
 472   // OpNo = which operand of BO is UserChain[ChainIndex - 1]
 473   unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);
 474   Value *TheOther = applyExts(BO->getOperand(1 - OpNo));
 475   Value *NextInChain = distributeExtsAndCloneChain(ChainIndex - 1);
 476
 477   BinaryOperator *NewBO = nullptr;
 478   if (OpNo == 0) {
 479     NewBO = BinaryOperator::Create(BO->getOpcode(), NextInChain, TheOther,
 480                                    BO->getName(), IP);
 481   } else {
 482     NewBO = BinaryOperator::Create(BO->getOpcode(), TheOther, NextInChain,
 483                                    BO->getName(), IP);
 484   }
 485   return UserChain[ChainIndex] = NewBO;
 486 }
 487
 488 Value *ConstantOffsetExtractor::removeConstOffset(unsigned ChainIndex) {
 489   if (ChainIndex == 0) {
 490     assert(isa<ConstantInt>(UserChain[ChainIndex]));
 491     return ConstantInt::getNullValue(UserChain[ChainIndex]->getType());
 492   }
 493
 494   BinaryOperator *BO = cast<BinaryOperator>(UserChain[ChainIndex]);
 495   unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1);
 496   assert(BO->getOperand(OpNo) == UserChain[ChainIndex - 1]);
 497   Value *NextInChain = removeConstOffset(ChainIndex - 1);
 498   Value *TheOther = BO->getOperand(1 - OpNo);
 499
 500   // If NextInChain is 0 and not the LHS of a sub, we can simplify the
 501   // sub-expression to be just TheOther.
 502   if (ConstantInt *CI = dyn_cast<ConstantInt>(NextInChain)) {
 503     if (CI->isZero() && !(BO->getOpcode() == Instruction::Sub && OpNo == 0))
 504       return TheOther;
 505   }
 506
 507   if (BO->getOpcode() == Instruction::Or) {
 508     // Rebuild "or" as "add", because "or" may be invalid for the new
 509     // epxression.
 510     //
 511     // For instance, given
 512     //   a | (b + 5) where a and b + 5 have no common bits,
 513     // we can extract 5 as the constant offset.
 514     //
 515     // However, reusing the "or" in the new index would give us
 516     //   (a | b) + 5
 517     // which does not equal a | (b + 5).
 518     //
 519     // Replacing the "or" with "add" is fine, because
 520     //   a | (b + 5) = a + (b + 5) = (a + b) + 5
 521     return BinaryOperator::CreateAdd(BO->getOperand(0), BO->getOperand(1),
 522                                      BO->getName(), IP);
 523   }
 524
 525   // We can reuse BO in this case, because the new expression shares the same
 526   // instruction type and BO is used at most once.
 527   assert(BO->getNumUses() <= 1 &&
 528          "distributeExtsAndCloneChain clones each BinaryOperator in "
 529          "UserChain, so no one should be used more than "
 530          "once");
 531   BO->setOperand(OpNo, NextInChain);
 532   BO->setHasNoSignedWrap(false);
 533   BO->setHasNoUnsignedWrap(false);
 534   // Make sure it appears after all instructions we've inserted so far.
 535   BO->moveBefore(IP);
 536   return BO;
 537 }
 538
 539 int64_t ConstantOffsetExtractor::Extract(Value *Idx, Value *&NewIdx,
 540                                          const DataLayout *DL,
 541                                          GetElementPtrInst *GEP) {
 542   ConstantOffsetExtractor Extractor(DL, GEP);
 543   // Find a non-zero constant offset first.
 544   APInt ConstantOffset =
 545       Extractor.find(Idx, /* SignExtended */ false, /* ZeroExtended */ false,
 546                      GEP->isInBounds());
 547   if (ConstantOffset != 0) {
 548     // Separates the constant offset from the GEP index.
 549     NewIdx = Extractor.rebuildWithoutConstOffset();
 550   }
 551   return ConstantOffset.getSExtValue();
 552 }
 553
 554 int64_t ConstantOffsetExtractor::Find(Value *Idx, const DataLayout *DL,
 555       GetElementPtrInst *GEP) {
 556   // If Idx is an index of an inbound GEP, Idx is guaranteed to be non-negative.
 557   return ConstantOffsetExtractor(DL, GEP)
 558       .find(Idx, /* SignExtended */ false, /* ZeroExtended */ false,
 559             GEP->isInBounds())
 560       .getSExtValue();
 561 }
 562
 563 void ConstantOffsetExtractor::ComputeKnownBits(Value *V, APInt &KnownOne,
 564                                                APInt &KnownZero) const {
 565   IntegerType *IT = cast<IntegerType>(V->getType());
 566   KnownOne = APInt(IT->getBitWidth(), 0);
 567   KnownZero = APInt(IT->getBitWidth(), 0);
 568   llvm::computeKnownBits(V, KnownZero, KnownOne, DL, 0);
 569 }
 570
 571 bool ConstantOffsetExtractor::NoCommonBits(Value *LHS, Value *RHS) const {
 572   assert(LHS->getType() == RHS->getType() &&
 573          "LHS and RHS should have the same type");
 574   APInt LHSKnownOne, LHSKnownZero, RHSKnownOne, RHSKnownZero;
 575   ComputeKnownBits(LHS, LHSKnownOne, LHSKnownZero);
 576   ComputeKnownBits(RHS, RHSKnownOne, RHSKnownZero);
 577   return (LHSKnownZero | RHSKnownZero).isAllOnesValue();
 578 }
 579
 580 bool SeparateConstOffsetFromGEP::canonicalizeArrayIndicesToPointerSize(
 581     GetElementPtrInst *GEP) {
 582   bool Changed = false;
 583   Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
 584   gep_type_iterator GTI = gep_type_begin(*GEP);
 585   for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end();
 586        I != E; ++I, ++GTI) {
 587     // Skip struct member indices which must be i32.
 588     if (isa<SequentialType>(*GTI)) {
 589       if ((*I)->getType() != IntPtrTy) {
 590         *I = CastInst::CreateIntegerCast(*I, IntPtrTy, true, "idxprom", GEP);
 591         Changed = true;
 592       }
 593     }
 594   }
 595   return Changed;
 596 }
 597
 598 int64_t
 599 SeparateConstOffsetFromGEP::accumulateByteOffset(GetElementPtrInst *GEP,
 600                                                  bool &NeedsExtraction) {
 601   NeedsExtraction = false;
 602   int64_t AccumulativeByteOffset = 0;
 603   gep_type_iterator GTI = gep_type_begin(*GEP);
 604   for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
 605     if (isa<SequentialType>(*GTI)) {
 606       // Tries to extract a constant offset from this GEP index.
 607       int64_t ConstantOffset =
 608           ConstantOffsetExtractor::Find(GEP->getOperand(I), DL, GEP);
 609       if (ConstantOffset != 0) {
 610         NeedsExtraction = true;
 611         // A GEP may have multiple indices.  We accumulate the extracted
 612         // constant offset to a byte offset, and later offset the remainder of
 613         // the original GEP with this byte offset.
 614         AccumulativeByteOffset +=
 615             ConstantOffset * DL->getTypeAllocSize(GTI.getIndexedType());
 616       }
 617     }
 618   }
 619   return AccumulativeByteOffset;
 620 }
 621
 622 bool SeparateConstOffsetFromGEP::splitGEP(GetElementPtrInst *GEP) {
 623   // Skip vector GEPs.
 624   if (GEP->getType()->isVectorTy())
 625     return false;
 626
 627   // The backend can already nicely handle the case where all indices are
 628   // constant.
 629   if (GEP->hasAllConstantIndices())
 630     return false;
 631
 632   bool Changed = false;
 633   Changed |= canonicalizeArrayIndicesToPointerSize(GEP);
 634
 635   bool NeedsExtraction;
 636   int64_t AccumulativeByteOffset = accumulateByteOffset(GEP, NeedsExtraction);
 637
 638   if (!NeedsExtraction)
 639     return Changed;
 640   // Before really splitting the GEP, check whether the backend supports the
 641   // addressing mode we are about to produce. If no, this splitting probably
 642   // won't be beneficial.
 643   TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>();
 644   if (!TTI.isLegalAddressingMode(GEP->getType()->getElementType(),
 645                                  /*BaseGV=*/nullptr, AccumulativeByteOffset,
 646                                  /*HasBaseReg=*/true, /*Scale=*/0)) {
 647     return Changed;
 648   }
 649
 650   // Remove the constant offset in each GEP index. The resultant GEP computes
 651   // the variadic base.
 652   gep_type_iterator GTI = gep_type_begin(*GEP);
 653   for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
 654     if (isa<SequentialType>(*GTI)) {
 655       Value *NewIdx = nullptr;
 656       // Tries to extract a constant offset from this GEP index.
 657       int64_t ConstantOffset =
 658           ConstantOffsetExtractor::Extract(GEP->getOperand(I), NewIdx, DL, GEP);
 659       if (ConstantOffset != 0) {
 660         assert(NewIdx != nullptr &&
 661                "ConstantOffset != 0 implies NewIdx is set");
 662         GEP->setOperand(I, NewIdx);
 663       }
 664     }
 665   }
 666   // Clear the inbounds attribute because the new index may be off-bound.
 667   // e.g.,
 668   //
 669   // b = add i64 a, 5
 670   // addr = gep inbounds float* p, i64 b
 671   //
 672   // is transformed to:
 673   //
 674   // addr2 = gep float* p, i64 a
 675   // addr = gep float* addr2, i64 5
 676   //
 677   // If a is -4, although the old index b is in bounds, the new index a is
 678   // off-bound. http://llvm.org/docs/LangRef.html#id181 says "if the
 679   // inbounds keyword is not present, the offsets are added to the base
 680   // address with silently-wrapping two's complement arithmetic".
 681   // Therefore, the final code will be a semantically equivalent.
 682   //
 683   // TODO(jingyue): do some range analysis to keep as many inbounds as
 684   // possible. GEPs with inbounds are more friendly to alias analysis.
 685   GEP->setIsInBounds(false);
 686
 687   // Offsets the base with the accumulative byte offset.
 688   //
 689   //   %gep                        ; the base
 690   //   ... %gep ...
 691   //
 692   // => add the offset
 693   //
 694   //   %gep2                       ; clone of %gep
 695   //   %new.gep = gep %gep2, <offset / sizeof(*%gep)>
 696   //   %gep                        ; will be removed
 697   //   ... %gep ...
 698   //
 699   // => replace all uses of %gep with %new.gep and remove %gep
 700   //
 701   //   %gep2                       ; clone of %gep
 702   //   %new.gep = gep %gep2, <offset / sizeof(*%gep)>
 703   //   ... %new.gep ...
 704   //
 705   // If AccumulativeByteOffset is not a multiple of sizeof(*%gep), we emit an
 706   // uglygep (http://llvm.org/docs/GetElementPtr.html#what-s-an-uglygep):
 707   // bitcast %gep2 to i8*, add the offset, and bitcast the result back to the
 708   // type of %gep.
 709   //
 710   //   %gep2                       ; clone of %gep
 711   //   %0       = bitcast %gep2 to i8*
 712   //   %uglygep = gep %0, <offset>
 713   //   %new.gep = bitcast %uglygep to <type of %gep>
 714   //   ... %new.gep ...
 715   Instruction *NewGEP = GEP->clone();
 716   NewGEP->insertBefore(GEP);
 717
 718   uint64_t ElementTypeSizeOfGEP =
 719       DL->getTypeAllocSize(GEP->getType()->getElementType());
 720   Type *IntPtrTy = DL->getIntPtrType(GEP->getType());
 721   if (AccumulativeByteOffset % ElementTypeSizeOfGEP == 0) {
 722     // Very likely. As long as %gep is natually aligned, the byte offset we
 723     // extracted should be a multiple of sizeof(*%gep).
 724     // Per ANSI C standard, signed / unsigned = unsigned. Therefore, we
 725     // cast ElementTypeSizeOfGEP to signed.
 726     int64_t Index =
 727         AccumulativeByteOffset / static_cast<int64_t>(ElementTypeSizeOfGEP);
 728     NewGEP = GetElementPtrInst::Create(
 729         NewGEP, ConstantInt::get(IntPtrTy, Index, true), GEP->getName(), GEP);
 730   } else {
 731     // Unlikely but possible. For example,
 732     // #pragma pack(1)
 733     // struct S {
 734     //   int a[3];
 735     //   int64 b[8];
 736     // };
 737     // #pragma pack()
 738     //
 739     // Suppose the gep before extraction is &s[i + 1].b[j + 3]. After
 740     // extraction, it becomes &s[i].b[j] and AccumulativeByteOffset is
 741     // sizeof(S) + 3 * sizeof(int64) = 100, which is not a multiple of
 742     // sizeof(int64).
 743     //
 744     // Emit an uglygep in this case.
 745     Type *I8PtrTy = Type::getInt8PtrTy(GEP->getContext(),
 746                                        GEP->getPointerAddressSpace());
 747     NewGEP = new BitCastInst(NewGEP, I8PtrTy, "", GEP);
 748     NewGEP = GetElementPtrInst::Create(
 749         NewGEP, ConstantInt::get(IntPtrTy, AccumulativeByteOffset, true),
 750         "uglygep", GEP);
 751     if (GEP->getType() != I8PtrTy)
 752       NewGEP = new BitCastInst(NewGEP, GEP->getType(), GEP->getName(), GEP);
 753   }
 754
 755   GEP->replaceAllUsesWith(NewGEP);
 756   GEP->eraseFromParent();
 757
 758   return true;
 759 }
 760
 761 bool SeparateConstOffsetFromGEP::runOnFunction(Function &F) {
 762   if (DisableSeparateConstOffsetFromGEP)
 763     return false;
 764
 765   bool Changed = false;
 766   for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B) {
 767     for (BasicBlock::iterator I = B->begin(), IE = B->end(); I != IE; ) {
 768       if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I++)) {
 769         Changed |= splitGEP(GEP);
 770       }
 771       // No need to split GEP ConstantExprs because all its indices are constant
 772       // already.
 773     }
 774   }
 775   return Changed;
 776 }