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 96using namespace llvm; 97 98static 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 103namespace { 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). 118class 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. 228class 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 /// Returns true if the module changes. 272 /// 273 /// Verified in @i32_add in split-gep.ll 274 bool canonicalizeArrayIndicesToPointerSize(GetElementPtrInst *GEP); 275 /// For each array index that is in the form of zext(a), convert it to sext(a) 276 /// if we can prove zext(a) <= max signed value of typeof(a). We prefer 277 /// sext(a) to zext(a), because in the special case where x + y >= 0 and 278 /// (x >= 0 or y >= 0), function CanTraceInto can split sext(x + y), 279 /// while no such case exists for zext(x + y). 280 /// 281 /// Note that 282 /// zext(x + y) = zext(x) + zext(y) 283 /// is wrong, e.g., 284 /// zext i32(UINT_MAX + 1) to i64 != 285 /// (zext i32 UINT_MAX to i64) + (zext i32 1 to i64) 286 /// 287 /// Returns true if the module changes. 288 /// 289 /// Verified in @inbounds_zext_add in split-gep.ll and @sum_of_array3 in 290 /// split-gep-and-gvn.ll 291 bool convertInBoundsZExtToSExt(GetElementPtrInst *GEP); 292 293 const DataLayout *DL; 294}; 295} // anonymous namespace 296 297char SeparateConstOffsetFromGEP::ID = 0; 298INITIALIZE_PASS_BEGIN( 299 SeparateConstOffsetFromGEP, "separate-const-offset-from-gep", 300 "Split GEPs to a variadic base and a constant offset for better CSE", false, 301 false) 302INITIALIZE_AG_DEPENDENCY(TargetTransformInfo) 303INITIALIZE_PASS_DEPENDENCY(DataLayoutPass) 304INITIALIZE_PASS_END( 305 SeparateConstOffsetFromGEP, "separate-const-offset-from-gep", 306 "Split GEPs to a variadic base and a constant offset for better CSE", false, 307 false) 308 309FunctionPass *llvm::createSeparateConstOffsetFromGEPPass() { 310 return new SeparateConstOffsetFromGEP(); 311} 312 313bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended, 314 bool ZeroExtended, 315 BinaryOperator *BO, 316 bool NonNegative) { 317 // We only consider ADD, SUB and OR, because a non-zero constant found in 318 // expressions composed of these operations can be easily hoisted as a 319 // constant offset by reassociation. 320 if (BO->getOpcode() != Instruction::Add && 321 BO->getOpcode() != Instruction::Sub && 322 BO->getOpcode() != Instruction::Or) { 323 return false; 324 } 325 326 Value *LHS = BO->getOperand(0), *RHS = BO->getOperand(1); 327 // Do not trace into "or" unless it is equivalent to "add". If LHS and RHS 328 // don't have common bits, (LHS | RHS) is equivalent to (LHS + RHS). 329 if (BO->getOpcode() == Instruction::Or && !NoCommonBits(LHS, RHS)) 330 return false; 331 332 // In addition, tracing into BO requires that its surrounding s/zext (if 333 // any) is distributable to both operands. 334 // 335 // Suppose BO = A op B. 336 // SignExtended | ZeroExtended | Distributable? 337 // --------------+--------------+---------------------------------- 338 // 0 | 0 | true because no s/zext exists 339 // 0 | 1 | zext(BO) == zext(A) op zext(B) 340 // 1 | 0 | sext(BO) == sext(A) op sext(B) 341 // 1 | 1 | zext(sext(BO)) == 342 // | | zext(sext(A)) op zext(sext(B)) 343 if (BO->getOpcode() == Instruction::Add && !ZeroExtended && NonNegative) { 344 // If a + b >= 0 and (a >= 0 or b >= 0), then 345 // sext(a + b) = sext(a) + sext(b) 346 // even if the addition is not marked nsw. 347 // 348 // Leveraging this invarient, we can trace into an sext'ed inbound GEP 349 // index if the constant offset is non-negative. 350 // 351 // Verified in @sext_add in split-gep.ll. 352 if (ConstantInt *ConstLHS = dyn_cast<ConstantInt>(LHS)) { 353 if (!ConstLHS->isNegative()) 354 return true; 355 } 356 if (ConstantInt *ConstRHS = dyn_cast<ConstantInt>(RHS)) { 357 if (!ConstRHS->isNegative()) 358 return true; 359 } 360 } 361 362 // sext (add/sub nsw A, B) == add/sub nsw (sext A), (sext B) 363 // zext (add/sub nuw A, B) == add/sub nuw (zext A), (zext B) 364 if (BO->getOpcode() == Instruction::Add || 365 BO->getOpcode() == Instruction::Sub) { 366 if (SignExtended && !BO->hasNoSignedWrap()) 367 return false; 368 if (ZeroExtended && !BO->hasNoUnsignedWrap()) 369 return false; 370 } 371 372 return true; 373} 374 375APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO, 376 bool SignExtended, 377 bool ZeroExtended) { 378 // BO being non-negative does not shed light on whether its operands are 379 // non-negative. Clear the NonNegative flag here. 380 APInt ConstantOffset = find(BO->getOperand(0), SignExtended, ZeroExtended, 381 /* NonNegative */ false); 382 // If we found a constant offset in the left operand, stop and return that. 383 // This shortcut might cause us to miss opportunities of combining the 384 // constant offsets in both operands, e.g., (a + 4) + (b + 5) => (a + b) + 9. 385 // However, such cases are probably already handled by -instcombine, 386 // given this pass runs after the standard optimizations. 387 if (ConstantOffset != 0) return ConstantOffset; 388 ConstantOffset = find(BO->getOperand(1), SignExtended, ZeroExtended, 389 /* NonNegative */ false); 390 // If U is a sub operator, negate the constant offset found in the right 391 // operand. 392 if (BO->getOpcode() == Instruction::Sub) 393 ConstantOffset = -ConstantOffset; 394 return ConstantOffset; 395} 396 397APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended, 398 bool ZeroExtended, bool NonNegative) { 399 // TODO(jingyue): We could trace into integer/pointer casts, such as 400 // inttoptr, ptrtoint, bitcast, and addrspacecast. We choose to handle only 401 // integers because it gives good enough results for our benchmarks. 402 unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 403 404 // We cannot do much with Values that are not a User, such as an Argument. 405 User *U = dyn_cast<User>(V); 406 if (U == nullptr) return APInt(BitWidth, 0); 407 408 APInt ConstantOffset(BitWidth, 0); 409 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 410 // Hooray, we found it! 411 ConstantOffset = CI->getValue(); 412 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) { 413 // Trace into subexpressions for more hoisting opportunities. 414 if (CanTraceInto(SignExtended, ZeroExtended, BO, NonNegative)) { 415 ConstantOffset = findInEitherOperand(BO, SignExtended, ZeroExtended); 416 } 417 } else if (isa<SExtInst>(V)) { 418 ConstantOffset = find(U->getOperand(0), /* SignExtended */ true, 419 ZeroExtended, NonNegative).sext(BitWidth); 420 } else if (isa<ZExtInst>(V)) { 421 // As an optimization, we can clear the SignExtended flag because 422 // sext(zext(a)) = zext(a). Verified in @sext_zext in split-gep.ll. 423 // 424 // Clear the NonNegative flag, because zext(a) >= 0 does not imply a >= 0. 425 ConstantOffset = 426 find(U->getOperand(0), /* SignExtended */ false, 427 /* ZeroExtended */ true, /* NonNegative */ false).zext(BitWidth); 428 } 429 430 // If we found a non-zero constant offset, add it to the path for 431 // rebuildWithoutConstOffset. Zero is a valid constant offset, but doesn't 432 // help this optimization. 433 if (ConstantOffset != 0) 434 UserChain.push_back(U); 435 return ConstantOffset; 436} 437 438Value *ConstantOffsetExtractor::applyExts(Value *V) { 439 Value *Current = V; 440 // ExtInsts is built in the use-def order. Therefore, we apply them to V 441 // in the reversed order. 442 for (auto I = ExtInsts.rbegin(), E = ExtInsts.rend(); I != E; ++I) { 443 if (Constant *C = dyn_cast<Constant>(Current)) { 444 // If Current is a constant, apply s/zext using ConstantExpr::getCast. 445 // ConstantExpr::getCast emits a ConstantInt if C is a ConstantInt. 446 Current = ConstantExpr::getCast((*I)->getOpcode(), C, (*I)->getType()); 447 } else { 448 Instruction *Ext = (*I)->clone(); 449 Ext->setOperand(0, Current); 450 Ext->insertBefore(IP); 451 Current = Ext; 452 } 453 } 454 return Current; 455} 456 457Value *ConstantOffsetExtractor::rebuildWithoutConstOffset() { 458 distributeExtsAndCloneChain(UserChain.size() - 1); 459 // Remove all nullptrs (used to be s/zext) from UserChain. 460 unsigned NewSize = 0; 461 for (auto I = UserChain.begin(), E = UserChain.end(); I != E; ++I) { 462 if (*I != nullptr) { 463 UserChain[NewSize] = *I; 464 NewSize++; 465 } 466 } 467 UserChain.resize(NewSize); 468 return removeConstOffset(UserChain.size() - 1); 469} 470 471Value * 472ConstantOffsetExtractor::distributeExtsAndCloneChain(unsigned ChainIndex) { 473 User *U = UserChain[ChainIndex]; 474 if (ChainIndex == 0) { 475 assert(isa<ConstantInt>(U)); 476 // If U is a ConstantInt, applyExts will return a ConstantInt as well. 477 return UserChain[ChainIndex] = cast<ConstantInt>(applyExts(U)); 478 } 479 480 if (CastInst *Cast = dyn_cast<CastInst>(U)) { 481 assert((isa<SExtInst>(Cast) || isa<ZExtInst>(Cast)) && 482 "We only traced into two types of CastInst: sext and zext"); 483 ExtInsts.push_back(Cast); 484 UserChain[ChainIndex] = nullptr; 485 return distributeExtsAndCloneChain(ChainIndex - 1); 486 } 487 488 // Function find only trace into BinaryOperator and CastInst. 489 BinaryOperator *BO = cast<BinaryOperator>(U); 490 // OpNo = which operand of BO is UserChain[ChainIndex - 1] 491 unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1); 492 Value *TheOther = applyExts(BO->getOperand(1 - OpNo)); 493 Value *NextInChain = distributeExtsAndCloneChain(ChainIndex - 1); 494 495 BinaryOperator *NewBO = nullptr; 496 if (OpNo == 0) { 497 NewBO = BinaryOperator::Create(BO->getOpcode(), NextInChain, TheOther, 498 BO->getName(), IP); 499 } else { 500 NewBO = BinaryOperator::Create(BO->getOpcode(), TheOther, NextInChain, 501 BO->getName(), IP); 502 } 503 return UserChain[ChainIndex] = NewBO; 504} 505 506Value *ConstantOffsetExtractor::removeConstOffset(unsigned ChainIndex) { 507 if (ChainIndex == 0) { 508 assert(isa<ConstantInt>(UserChain[ChainIndex])); 509 return ConstantInt::getNullValue(UserChain[ChainIndex]->getType()); 510 } 511 512 BinaryOperator *BO = cast<BinaryOperator>(UserChain[ChainIndex]); 513 unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1); 514 assert(BO->getOperand(OpNo) == UserChain[ChainIndex - 1]); 515 Value *NextInChain = removeConstOffset(ChainIndex - 1); 516 Value *TheOther = BO->getOperand(1 - OpNo); 517 518 // If NextInChain is 0 and not the LHS of a sub, we can simplify the 519 // sub-expression to be just TheOther. 520 if (ConstantInt *CI = dyn_cast<ConstantInt>(NextInChain)) { 521 if (CI->isZero() && !(BO->getOpcode() == Instruction::Sub && OpNo == 0)) 522 return TheOther; 523 } 524 525 if (BO->getOpcode() == Instruction::Or) { 526 // Rebuild "or" as "add", because "or" may be invalid for the new 527 // epxression. 528 // 529 // For instance, given 530 // a | (b + 5) where a and b + 5 have no common bits, 531 // we can extract 5 as the constant offset. 532 // 533 // However, reusing the "or" in the new index would give us 534 // (a | b) + 5 535 // which does not equal a | (b + 5). 536 // 537 // Replacing the "or" with "add" is fine, because 538 // a | (b + 5) = a + (b + 5) = (a + b) + 5 539 return BinaryOperator::CreateAdd(BO->getOperand(0), BO->getOperand(1), 540 BO->getName(), IP); 541 } 542 543 // We can reuse BO in this case, because the new expression shares the same 544 // instruction type and BO is used at most once. 545 assert(BO->getNumUses() <= 1 && 546 "distributeExtsAndCloneChain clones each BinaryOperator in " 547 "UserChain, so no one should be used more than " 548 "once"); 549 BO->setOperand(OpNo, NextInChain); 550 BO->setHasNoSignedWrap(false); 551 BO->setHasNoUnsignedWrap(false); 552 // Make sure it appears after all instructions we've inserted so far. 553 BO->moveBefore(IP); 554 return BO; 555} 556 557int64_t ConstantOffsetExtractor::Extract(Value *Idx, Value *&NewIdx, 558 const DataLayout *DL, 559 GetElementPtrInst *GEP) { 560 ConstantOffsetExtractor Extractor(DL, GEP); 561 // Find a non-zero constant offset first. 562 APInt ConstantOffset = 563 Extractor.find(Idx, /* SignExtended */ false, /* ZeroExtended */ false, 564 GEP->isInBounds()); 565 if (ConstantOffset != 0) { 566 // Separates the constant offset from the GEP index. 567 NewIdx = Extractor.rebuildWithoutConstOffset(); 568 } 569 return ConstantOffset.getSExtValue(); 570} 571 572int64_t ConstantOffsetExtractor::Find(Value *Idx, const DataLayout *DL, 573 GetElementPtrInst *GEP) { 574 // If Idx is an index of an inbound GEP, Idx is guaranteed to be non-negative. 575 return ConstantOffsetExtractor(DL, GEP) 576 .find(Idx, /* SignExtended */ false, /* ZeroExtended */ false, 577 GEP->isInBounds()) 578 .getSExtValue(); 579} 580 581void ConstantOffsetExtractor::ComputeKnownBits(Value *V, APInt &KnownOne, 582 APInt &KnownZero) const { 583 IntegerType *IT = cast<IntegerType>(V->getType()); 584 KnownOne = APInt(IT->getBitWidth(), 0); 585 KnownZero = APInt(IT->getBitWidth(), 0); 586 llvm::computeKnownBits(V, KnownZero, KnownOne, DL, 0); 587} 588 589bool ConstantOffsetExtractor::NoCommonBits(Value *LHS, Value *RHS) const { 590 assert(LHS->getType() == RHS->getType() && 591 "LHS and RHS should have the same type"); 592 APInt LHSKnownOne, LHSKnownZero, RHSKnownOne, RHSKnownZero; 593 ComputeKnownBits(LHS, LHSKnownOne, LHSKnownZero); 594 ComputeKnownBits(RHS, RHSKnownOne, RHSKnownZero); 595 return (LHSKnownZero | RHSKnownZero).isAllOnesValue(); 596} 597 598bool SeparateConstOffsetFromGEP::canonicalizeArrayIndicesToPointerSize( 599 GetElementPtrInst *GEP) { 600 bool Changed = false; 601 Type *IntPtrTy = DL->getIntPtrType(GEP->getType()); 602 gep_type_iterator GTI = gep_type_begin(*GEP); 603 for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end(); 604 I != E; ++I, ++GTI) { 605 // Skip struct member indices which must be i32. 606 if (isa<SequentialType>(*GTI)) { 607 if ((*I)->getType() != IntPtrTy) { 608 *I = CastInst::CreateIntegerCast(*I, IntPtrTy, true, "idxprom", GEP); 609 Changed = true; 610 } 611 } 612 } 613 return Changed; 614} 615 616bool 617SeparateConstOffsetFromGEP::convertInBoundsZExtToSExt(GetElementPtrInst *GEP) { 618 if (!GEP->isInBounds()) 619 return false; 620 621 // TODO: consider alloca 622 GlobalVariable *UnderlyingObject = 623 dyn_cast<GlobalVariable>(GEP->getPointerOperand()); 624 if (UnderlyingObject == nullptr) 625 return false; 626 627 uint64_t ObjectSize = 628 DL->getTypeAllocSize(UnderlyingObject->getType()->getElementType()); 629 gep_type_iterator GTI = gep_type_begin(*GEP); 630 bool Changed = false; 631 for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end(); I != E; 632 ++I, ++GTI) { 633 if (isa<SequentialType>(*GTI)) { 634 if (ZExtInst *Extended = dyn_cast<ZExtInst>(*I)) { 635 unsigned SrcBitWidth = 636 cast<IntegerType>(Extended->getSrcTy())->getBitWidth(); 637 // For GEP operand zext(a), if a <= max signed value of typeof(a), then 638 // the sign bit of a is zero and sext(a) = zext(a). Because the GEP is 639 // in bounds, we know a <= ObjectSize, so the condition can be reduced 640 // to ObjectSize <= max signed value of typeof(a). 641 if (ObjectSize <= 642 APInt::getSignedMaxValue(SrcBitWidth).getZExtValue()) { 643 *I = new SExtInst(Extended->getOperand(0), Extended->getType(), 644 Extended->getName(), GEP); 645 Changed = true; 646 } 647 } 648 } 649 } 650 return Changed; 651} 652 653int64_t 654SeparateConstOffsetFromGEP::accumulateByteOffset(GetElementPtrInst *GEP, 655 bool &NeedsExtraction) { 656 NeedsExtraction = false; 657 int64_t AccumulativeByteOffset = 0; 658 gep_type_iterator GTI = gep_type_begin(*GEP); 659 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) { 660 if (isa<SequentialType>(*GTI)) { 661 // Tries to extract a constant offset from this GEP index. 662 int64_t ConstantOffset = 663 ConstantOffsetExtractor::Find(GEP->getOperand(I), DL, GEP); 664 if (ConstantOffset != 0) { 665 NeedsExtraction = true; 666 // A GEP may have multiple indices. We accumulate the extracted 667 // constant offset to a byte offset, and later offset the remainder of 668 // the original GEP with this byte offset. 669 AccumulativeByteOffset += 670 ConstantOffset * DL->getTypeAllocSize(GTI.getIndexedType()); 671 } 672 } 673 } 674 return AccumulativeByteOffset; 675} 676 677bool SeparateConstOffsetFromGEP::splitGEP(GetElementPtrInst *GEP) { 678 // Skip vector GEPs. 679 if (GEP->getType()->isVectorTy()) 680 return false; 681 682 // The backend can already nicely handle the case where all indices are 683 // constant. 684 if (GEP->hasAllConstantIndices()) 685 return false; 686 687 bool Changed = false; 688 Changed |= canonicalizeArrayIndicesToPointerSize(GEP); 689 Changed |= convertInBoundsZExtToSExt(GEP); 690 691 bool NeedsExtraction; 692 int64_t AccumulativeByteOffset = accumulateByteOffset(GEP, NeedsExtraction); 693 694 if (!NeedsExtraction) 695 return Changed; 696 // Before really splitting the GEP, check whether the backend supports the 697 // addressing mode we are about to produce. If no, this splitting probably 698 // won't be beneficial. 699 TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>(); 700 if (!TTI.isLegalAddressingMode(GEP->getType()->getElementType(), 701 /*BaseGV=*/nullptr, AccumulativeByteOffset, 702 /*HasBaseReg=*/true, /*Scale=*/0)) { 703 return Changed; 704 } 705 706 // Remove the constant offset in each GEP index. The resultant GEP computes 707 // the variadic base. 708 gep_type_iterator GTI = gep_type_begin(*GEP); 709 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) { 710 if (isa<SequentialType>(*GTI)) { 711 Value *NewIdx = nullptr; 712 // Tries to extract a constant offset from this GEP index. 713 int64_t ConstantOffset = 714 ConstantOffsetExtractor::Extract(GEP->getOperand(I), NewIdx, DL, GEP); 715 if (ConstantOffset != 0) { 716 assert(NewIdx != nullptr && 717 "ConstantOffset != 0 implies NewIdx is set"); 718 GEP->setOperand(I, NewIdx); 719 } 720 } 721 } 722 // Clear the inbounds attribute because the new index may be off-bound. 723 // e.g., 724 // 725 // b = add i64 a, 5 726 // addr = gep inbounds float* p, i64 b 727 // 728 // is transformed to: 729 // 730 // addr2 = gep float* p, i64 a 731 // addr = gep float* addr2, i64 5 732 // 733 // If a is -4, although the old index b is in bounds, the new index a is 734 // off-bound. http://llvm.org/docs/LangRef.html#id181 says "if the 735 // inbounds keyword is not present, the offsets are added to the base 736 // address with silently-wrapping two's complement arithmetic". 737 // Therefore, the final code will be a semantically equivalent. 738 // 739 // TODO(jingyue): do some range analysis to keep as many inbounds as 740 // possible. GEPs with inbounds are more friendly to alias analysis. 741 GEP->setIsInBounds(false); 742 743 // Offsets the base with the accumulative byte offset. 744 // 745 // %gep ; the base 746 // ... %gep ... 747 // 748 // => add the offset 749 // 750 // %gep2 ; clone of %gep 751 // %new.gep = gep %gep2, <offset / sizeof(*%gep)> 752 // %gep ; will be removed 753 // ... %gep ... 754 // 755 // => replace all uses of %gep with %new.gep and remove %gep 756 // 757 // %gep2 ; clone of %gep 758 // %new.gep = gep %gep2, <offset / sizeof(*%gep)> 759 // ... %new.gep ... 760 // 761 // If AccumulativeByteOffset is not a multiple of sizeof(*%gep), we emit an 762 // uglygep (http://llvm.org/docs/GetElementPtr.html#what-s-an-uglygep): 763 // bitcast %gep2 to i8*, add the offset, and bitcast the result back to the 764 // type of %gep. 765 // 766 // %gep2 ; clone of %gep 767 // %0 = bitcast %gep2 to i8* 768 // %uglygep = gep %0, <offset> 769 // %new.gep = bitcast %uglygep to <type of %gep> 770 // ... %new.gep ... 771 Instruction *NewGEP = GEP->clone(); 772 NewGEP->insertBefore(GEP); 773 774 uint64_t ElementTypeSizeOfGEP = 775 DL->getTypeAllocSize(GEP->getType()->getElementType()); 776 Type *IntPtrTy = DL->getIntPtrType(GEP->getType()); 777 if (AccumulativeByteOffset % ElementTypeSizeOfGEP == 0) { 778 // Very likely. As long as %gep is natually aligned, the byte offset we 779 // extracted should be a multiple of sizeof(*%gep). 780 // Per ANSI C standard, signed / unsigned = unsigned. Therefore, we 781 // cast ElementTypeSizeOfGEP to signed. 782 int64_t Index = 783 AccumulativeByteOffset / static_cast<int64_t>(ElementTypeSizeOfGEP); 784 NewGEP = GetElementPtrInst::Create( 785 NewGEP, ConstantInt::get(IntPtrTy, Index, true), GEP->getName(), GEP); 786 } else { 787 // Unlikely but possible. For example, 788 // #pragma pack(1) 789 // struct S { 790 // int a[3]; 791 // int64 b[8]; 792 // }; 793 // #pragma pack() 794 // 795 // Suppose the gep before extraction is &s[i + 1].b[j + 3]. After 796 // extraction, it becomes &s[i].b[j] and AccumulativeByteOffset is 797 // sizeof(S) + 3 * sizeof(int64) = 100, which is not a multiple of 798 // sizeof(int64). 799 // 800 // Emit an uglygep in this case. 801 Type *I8PtrTy = Type::getInt8PtrTy(GEP->getContext(), 802 GEP->getPointerAddressSpace()); 803 NewGEP = new BitCastInst(NewGEP, I8PtrTy, "", GEP); 804 NewGEP = GetElementPtrInst::Create( 805 NewGEP, ConstantInt::get(IntPtrTy, AccumulativeByteOffset, true), 806 "uglygep", GEP); 807 if (GEP->getType() != I8PtrTy) 808 NewGEP = new BitCastInst(NewGEP, GEP->getType(), GEP->getName(), GEP); 809 } 810 811 GEP->replaceAllUsesWith(NewGEP); 812 GEP->eraseFromParent(); 813 814 return true; 815} 816 817bool SeparateConstOffsetFromGEP::runOnFunction(Function &F) { 818 if (DisableSeparateConstOffsetFromGEP) 819 return false; 820 821 bool Changed = false; 822 for (Function::iterator B = F.begin(), BE = F.end(); B != BE; ++B) { 823 for (BasicBlock::iterator I = B->begin(), IE = B->end(); I != IE; ) { 824 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(I++)) { 825 Changed |= splitGEP(GEP); 826 } 827 // No need to split GEP ConstantExprs because all its indices are constant 828 // already. 829 } 830 } 831 return Changed; 832} 833