1 //===- SeparateConstOffsetFromGEP.cpp -------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // Loop unrolling may create many similar GEPs for array accesses. 10 // e.g., a 2-level loop 11 // 12 // float a[32][32]; // global variable 13 // 14 // for (int i = 0; i < 2; ++i) { 15 // for (int j = 0; j < 2; ++j) { 16 // ... 17 // ... = a[x + i][y + j]; 18 // ... 19 // } 20 // } 21 // 22 // will probably be unrolled to: 23 // 24 // gep %a, 0, %x, %y; load 25 // gep %a, 0, %x, %y + 1; load 26 // gep %a, 0, %x + 1, %y; load 27 // gep %a, 0, %x + 1, %y + 1; load 28 // 29 // LLVM's GVN does not use partial redundancy elimination yet, and is thus 30 // unable to reuse (gep %a, 0, %x, %y). As a result, this misoptimization incurs 31 // significant slowdown in targets with limited addressing modes. For instance, 32 // because the PTX target does not support the reg+reg addressing mode, the 33 // NVPTX backend emits PTX code that literally computes the pointer address of 34 // each GEP, wasting tons of registers. It emits the following PTX for the 35 // first load and similar PTX for other loads. 36 // 37 // mov.u32 %r1, %x; 38 // mov.u32 %r2, %y; 39 // mul.wide.u32 %rl2, %r1, 128; 40 // mov.u64 %rl3, a; 41 // add.s64 %rl4, %rl3, %rl2; 42 // mul.wide.u32 %rl5, %r2, 4; 43 // add.s64 %rl6, %rl4, %rl5; 44 // ld.global.f32 %f1, [%rl6]; 45 // 46 // To reduce the register pressure, the optimization implemented in this file 47 // merges the common part of a group of GEPs, so we can compute each pointer 48 // address by adding a simple offset to the common part, saving many registers. 49 // 50 // It works by splitting each GEP into a variadic base and a constant offset. 51 // The variadic base can be computed once and reused by multiple GEPs, and the 52 // constant offsets can be nicely folded into the reg+immediate addressing mode 53 // (supported by most targets) without using any extra register. 54 // 55 // For instance, we transform the four GEPs and four loads in the above example 56 // into: 57 // 58 // base = gep a, 0, x, y 59 // load base 60 // laod base + 1 * sizeof(float) 61 // load base + 32 * sizeof(float) 62 // load base + 33 * sizeof(float) 63 // 64 // Given the transformed IR, a backend that supports the reg+immediate 65 // addressing mode can easily fold the pointer arithmetics into the loads. For 66 // example, the NVPTX backend can easily fold the pointer arithmetics into the 67 // ld.global.f32 instructions, and the resultant PTX uses much fewer registers. 68 // 69 // mov.u32 %r1, %tid.x; 70 // mov.u32 %r2, %tid.y; 71 // mul.wide.u32 %rl2, %r1, 128; 72 // mov.u64 %rl3, a; 73 // add.s64 %rl4, %rl3, %rl2; 74 // mul.wide.u32 %rl5, %r2, 4; 75 // add.s64 %rl6, %rl4, %rl5; 76 // ld.global.f32 %f1, [%rl6]; // so far the same as unoptimized PTX 77 // ld.global.f32 %f2, [%rl6+4]; // much better 78 // ld.global.f32 %f3, [%rl6+128]; // much better 79 // ld.global.f32 %f4, [%rl6+132]; // much better 80 // 81 // Another improvement enabled by the LowerGEP flag is to lower a GEP with 82 // multiple indices to either multiple GEPs with a single index or arithmetic 83 // operations (depending on whether the target uses alias analysis in codegen). 84 // Such transformation can have following benefits: 85 // (1) It can always extract constants in the indices of structure type. 86 // (2) After such Lowering, there are more optimization opportunities such as 87 // CSE, LICM and CGP. 88 // 89 // E.g. The following GEPs have multiple indices: 90 // BB1: 91 // %p = getelementptr [10 x %struct]* %ptr, i64 %i, i64 %j1, i32 3 92 // load %p 93 // ... 94 // BB2: 95 // %p2 = getelementptr [10 x %struct]* %ptr, i64 %i, i64 %j1, i32 2 96 // load %p2 97 // ... 98 // 99 // We can not do CSE to the common part related to index "i64 %i". Lowering 100 // GEPs can achieve such goals. 101 // If the target does not use alias analysis in codegen, this pass will 102 // lower a GEP with multiple indices into arithmetic operations: 103 // BB1: 104 // %1 = ptrtoint [10 x %struct]* %ptr to i64 ; CSE opportunity 105 // %2 = mul i64 %i, length_of_10xstruct ; CSE opportunity 106 // %3 = add i64 %1, %2 ; CSE opportunity 107 // %4 = mul i64 %j1, length_of_struct 108 // %5 = add i64 %3, %4 109 // %6 = add i64 %3, struct_field_3 ; Constant offset 110 // %p = inttoptr i64 %6 to i32* 111 // load %p 112 // ... 113 // BB2: 114 // %7 = ptrtoint [10 x %struct]* %ptr to i64 ; CSE opportunity 115 // %8 = mul i64 %i, length_of_10xstruct ; CSE opportunity 116 // %9 = add i64 %7, %8 ; CSE opportunity 117 // %10 = mul i64 %j2, length_of_struct 118 // %11 = add i64 %9, %10 119 // %12 = add i64 %11, struct_field_2 ; Constant offset 120 // %p = inttoptr i64 %12 to i32* 121 // load %p2 122 // ... 123 // 124 // If the target uses alias analysis in codegen, this pass will lower a GEP 125 // with multiple indices into multiple GEPs with a single index: 126 // BB1: 127 // %1 = bitcast [10 x %struct]* %ptr to i8* ; CSE opportunity 128 // %2 = mul i64 %i, length_of_10xstruct ; CSE opportunity 129 // %3 = getelementptr i8* %1, i64 %2 ; CSE opportunity 130 // %4 = mul i64 %j1, length_of_struct 131 // %5 = getelementptr i8* %3, i64 %4 132 // %6 = getelementptr i8* %5, struct_field_3 ; Constant offset 133 // %p = bitcast i8* %6 to i32* 134 // load %p 135 // ... 136 // BB2: 137 // %7 = bitcast [10 x %struct]* %ptr to i8* ; CSE opportunity 138 // %8 = mul i64 %i, length_of_10xstruct ; CSE opportunity 139 // %9 = getelementptr i8* %7, i64 %8 ; CSE opportunity 140 // %10 = mul i64 %j2, length_of_struct 141 // %11 = getelementptr i8* %9, i64 %10 142 // %12 = getelementptr i8* %11, struct_field_2 ; Constant offset 143 // %p2 = bitcast i8* %12 to i32* 144 // load %p2 145 // ... 146 // 147 // Lowering GEPs can also benefit other passes such as LICM and CGP. 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 150 // parts and variant parts, LICM can hoist/sink those invariant parts. 151 // CGP (CodeGen Prepare) tries to sink address calculations that match the 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 154 // them. So we end up with a better addressing mode. 155 // 156 //===----------------------------------------------------------------------===// 157 158 #include "llvm/Transforms/Scalar/SeparateConstOffsetFromGEP.h" 159 #include "llvm/ADT/APInt.h" 160 #include "llvm/ADT/DenseMap.h" 161 #include "llvm/ADT/DepthFirstIterator.h" 162 #include "llvm/ADT/SmallVector.h" 163 #include "llvm/Analysis/LoopInfo.h" 164 #include "llvm/Analysis/MemoryBuiltins.h" 165 #include "llvm/Analysis/TargetLibraryInfo.h" 166 #include "llvm/Analysis/TargetTransformInfo.h" 167 #include "llvm/Analysis/ValueTracking.h" 168 #include "llvm/IR/BasicBlock.h" 169 #include "llvm/IR/Constant.h" 170 #include "llvm/IR/Constants.h" 171 #include "llvm/IR/DataLayout.h" 172 #include "llvm/IR/DerivedTypes.h" 173 #include "llvm/IR/Dominators.h" 174 #include "llvm/IR/Function.h" 175 #include "llvm/IR/GetElementPtrTypeIterator.h" 176 #include "llvm/IR/IRBuilder.h" 177 #include "llvm/IR/Instruction.h" 178 #include "llvm/IR/Instructions.h" 179 #include "llvm/IR/Module.h" 180 #include "llvm/IR/PassManager.h" 181 #include "llvm/IR/PatternMatch.h" 182 #include "llvm/IR/Type.h" 183 #include "llvm/IR/User.h" 184 #include "llvm/IR/Value.h" 185 #include "llvm/InitializePasses.h" 186 #include "llvm/Pass.h" 187 #include "llvm/Support/Casting.h" 188 #include "llvm/Support/CommandLine.h" 189 #include "llvm/Support/ErrorHandling.h" 190 #include "llvm/Support/raw_ostream.h" 191 #include "llvm/Transforms/Scalar.h" 192 #include "llvm/Transforms/Utils/Local.h" 193 #include <cassert> 194 #include <cstdint> 195 #include <string> 196 197 using namespace llvm; 198 using namespace llvm::PatternMatch; 199 200 static cl::opt<bool> DisableSeparateConstOffsetFromGEP( 201 "disable-separate-const-offset-from-gep", cl::init(false), 202 cl::desc("Do not separate the constant offset from a GEP instruction"), 203 cl::Hidden); 204 205 // Setting this flag may emit false positives when the input module already 206 // contains dead instructions. Therefore, we set it only in unit tests that are 207 // free of dead code. 208 static cl::opt<bool> 209 VerifyNoDeadCode("reassociate-geps-verify-no-dead-code", cl::init(false), 210 cl::desc("Verify this pass produces no dead code"), 211 cl::Hidden); 212 213 namespace { 214 215 /// A helper class for separating a constant offset from a GEP index. 216 /// 217 /// In real programs, a GEP index may be more complicated than a simple addition 218 /// of something and a constant integer which can be trivially splitted. For 219 /// example, to split ((a << 3) | 5) + b, we need to search deeper for the 220 /// constant offset, so that we can separate the index to (a << 3) + b and 5. 221 /// 222 /// Therefore, this class looks into the expression that computes a given GEP 223 /// index, and tries to find a constant integer that can be hoisted to the 224 /// outermost level of the expression as an addition. Not every constant in an 225 /// expression can jump out. e.g., we cannot transform (b * (a + 5)) to (b * a + 226 /// 5); nor can we transform (3 * (a + 5)) to (3 * a + 5), however in this case, 227 /// -instcombine probably already optimized (3 * (a + 5)) to (3 * a + 15). 228 class ConstantOffsetExtractor { 229 public: 230 /// Extracts a constant offset from the given GEP index. It returns the 231 /// new index representing the remainder (equal to the original index minus 232 /// the constant offset), or nullptr if we cannot extract a constant offset. 233 /// \p Idx The given GEP index 234 /// \p GEP The given GEP 235 /// \p UserChainTail Outputs the tail of UserChain so that we can 236 /// garbage-collect unused instructions in UserChain. 237 static Value *Extract(Value *Idx, GetElementPtrInst *GEP, 238 User *&UserChainTail, const DominatorTree *DT); 239 240 /// Looks for a constant offset from the given GEP index without extracting 241 /// it. It returns the numeric value of the extracted constant offset (0 if 242 /// failed). The meaning of the arguments are the same as Extract. 243 static int64_t Find(Value *Idx, GetElementPtrInst *GEP, 244 const DominatorTree *DT); 245 246 private: 247 ConstantOffsetExtractor(Instruction *InsertionPt, const DominatorTree *DT) 248 : IP(InsertionPt), DL(InsertionPt->getModule()->getDataLayout()), DT(DT) { 249 } 250 251 /// Searches the expression that computes V for a non-zero constant C s.t. 252 /// V can be reassociated into the form V' + C. If the searching is 253 /// successful, returns C and update UserChain as a def-use chain from C to V; 254 /// otherwise, UserChain is empty. 255 /// 256 /// \p V The given expression 257 /// \p SignExtended Whether V will be sign-extended in the computation of the 258 /// GEP index 259 /// \p ZeroExtended Whether V will be zero-extended in the computation of the 260 /// GEP index 261 /// \p NonNegative Whether V is guaranteed to be non-negative. For example, 262 /// an index of an inbounds GEP is guaranteed to be 263 /// non-negative. Levaraging this, we can better split 264 /// inbounds GEPs. 265 APInt find(Value *V, bool SignExtended, bool ZeroExtended, bool NonNegative); 266 267 /// A helper function to look into both operands of a binary operator. 268 APInt findInEitherOperand(BinaryOperator *BO, bool SignExtended, 269 bool ZeroExtended); 270 271 /// After finding the constant offset C from the GEP index I, we build a new 272 /// index I' s.t. I' + C = I. This function builds and returns the new 273 /// index I' according to UserChain produced by function "find". 274 /// 275 /// The building conceptually takes two steps: 276 /// 1) iteratively distribute s/zext towards the leaves of the expression tree 277 /// that computes I 278 /// 2) reassociate the expression tree to the form I' + C. 279 /// 280 /// For example, to extract the 5 from sext(a + (b + 5)), we first distribute 281 /// sext to a, b and 5 so that we have 282 /// sext(a) + (sext(b) + 5). 283 /// Then, we reassociate it to 284 /// (sext(a) + sext(b)) + 5. 285 /// Given this form, we know I' is sext(a) + sext(b). 286 Value *rebuildWithoutConstOffset(); 287 288 /// After the first step of rebuilding the GEP index without the constant 289 /// offset, distribute s/zext to the operands of all operators in UserChain. 290 /// e.g., zext(sext(a + (b + 5)) (assuming no overflow) => 291 /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5))). 292 /// 293 /// The function also updates UserChain to point to new subexpressions after 294 /// distributing s/zext. e.g., the old UserChain of the above example is 295 /// 5 -> b + 5 -> a + (b + 5) -> sext(...) -> zext(sext(...)), 296 /// and the new UserChain is 297 /// zext(sext(5)) -> zext(sext(b)) + zext(sext(5)) -> 298 /// zext(sext(a)) + (zext(sext(b)) + zext(sext(5)) 299 /// 300 /// \p ChainIndex The index to UserChain. ChainIndex is initially 301 /// UserChain.size() - 1, and is decremented during 302 /// the recursion. 303 Value *distributeExtsAndCloneChain(unsigned ChainIndex); 304 305 /// Reassociates the GEP index to the form I' + C and returns I'. 306 Value *removeConstOffset(unsigned ChainIndex); 307 308 /// A helper function to apply ExtInsts, a list of s/zext, to value V. 309 /// e.g., if ExtInsts = [sext i32 to i64, zext i16 to i32], this function 310 /// returns "sext i32 (zext i16 V to i32) to i64". 311 Value *applyExts(Value *V); 312 313 /// A helper function that returns whether we can trace into the operands 314 /// of binary operator BO for a constant offset. 315 /// 316 /// \p SignExtended Whether BO is surrounded by sext 317 /// \p ZeroExtended Whether BO is surrounded by zext 318 /// \p NonNegative Whether BO is known to be non-negative, e.g., an in-bound 319 /// array index. 320 bool CanTraceInto(bool SignExtended, bool ZeroExtended, BinaryOperator *BO, 321 bool NonNegative); 322 323 /// The path from the constant offset to the old GEP index. e.g., if the GEP 324 /// index is "a * b + (c + 5)". After running function find, UserChain[0] will 325 /// be the constant 5, UserChain[1] will be the subexpression "c + 5", and 326 /// UserChain[2] will be the entire expression "a * b + (c + 5)". 327 /// 328 /// This path helps to rebuild the new GEP index. 329 SmallVector<User *, 8> UserChain; 330 331 /// A data structure used in rebuildWithoutConstOffset. Contains all 332 /// sext/zext instructions along UserChain. 333 SmallVector<CastInst *, 16> ExtInsts; 334 335 /// Insertion position of cloned instructions. 336 Instruction *IP; 337 338 const DataLayout &DL; 339 const DominatorTree *DT; 340 }; 341 342 /// A pass that tries to split every GEP in the function into a variadic 343 /// base and a constant offset. It is a FunctionPass because searching for the 344 /// constant offset may inspect other basic blocks. 345 class SeparateConstOffsetFromGEPLegacyPass : public FunctionPass { 346 public: 347 static char ID; 348 349 SeparateConstOffsetFromGEPLegacyPass(bool LowerGEP = false) 350 : FunctionPass(ID), LowerGEP(LowerGEP) { 351 initializeSeparateConstOffsetFromGEPLegacyPassPass( 352 *PassRegistry::getPassRegistry()); 353 } 354 355 void getAnalysisUsage(AnalysisUsage &AU) const override { 356 AU.addRequired<DominatorTreeWrapperPass>(); 357 AU.addRequired<TargetTransformInfoWrapperPass>(); 358 AU.addRequired<LoopInfoWrapperPass>(); 359 AU.setPreservesCFG(); 360 AU.addRequired<TargetLibraryInfoWrapperPass>(); 361 } 362 363 bool runOnFunction(Function &F) override; 364 365 private: 366 bool LowerGEP; 367 }; 368 369 /// A pass that tries to split every GEP in the function into a variadic 370 /// base and a constant offset. It is a FunctionPass because searching for the 371 /// constant offset may inspect other basic blocks. 372 class SeparateConstOffsetFromGEP { 373 public: 374 SeparateConstOffsetFromGEP( 375 DominatorTree *DT, LoopInfo *LI, TargetLibraryInfo *TLI, 376 function_ref<TargetTransformInfo &(Function &)> GetTTI, bool LowerGEP) 377 : DT(DT), LI(LI), TLI(TLI), GetTTI(GetTTI), LowerGEP(LowerGEP) {} 378 379 bool run(Function &F); 380 381 private: 382 /// Track the operands of an add or sub. 383 using ExprKey = std::pair<Value *, Value *>; 384 385 /// Create a pair for use as a map key for a commutable operation. 386 static ExprKey createNormalizedCommutablePair(Value *A, Value *B) { 387 if (A < B) 388 return {A, B}; 389 return {B, A}; 390 } 391 392 /// Tries to split the given GEP into a variadic base and a constant offset, 393 /// and returns true if the splitting succeeds. 394 bool splitGEP(GetElementPtrInst *GEP); 395 396 /// Lower a GEP with multiple indices into multiple GEPs with a single index. 397 /// Function splitGEP already split the original GEP into a variadic part and 398 /// a constant offset (i.e., AccumulativeByteOffset). This function lowers the 399 /// variadic part into a set of GEPs with a single index and applies 400 /// AccumulativeByteOffset to it. 401 /// \p Variadic The variadic part of the original GEP. 402 /// \p AccumulativeByteOffset The constant offset. 403 void lowerToSingleIndexGEPs(GetElementPtrInst *Variadic, 404 int64_t AccumulativeByteOffset); 405 406 /// Lower a GEP with multiple indices into ptrtoint+arithmetics+inttoptr form. 407 /// Function splitGEP already split the original GEP into a variadic part and 408 /// a constant offset (i.e., AccumulativeByteOffset). This function lowers the 409 /// variadic part into a set of arithmetic operations and applies 410 /// AccumulativeByteOffset to it. 411 /// \p Variadic The variadic part of the original GEP. 412 /// \p AccumulativeByteOffset The constant offset. 413 void lowerToArithmetics(GetElementPtrInst *Variadic, 414 int64_t AccumulativeByteOffset); 415 416 /// Finds the constant offset within each index and accumulates them. If 417 /// LowerGEP is true, it finds in indices of both sequential and structure 418 /// types, otherwise it only finds in sequential indices. The output 419 /// NeedsExtraction indicates whether we successfully find a non-zero constant 420 /// offset. 421 int64_t accumulateByteOffset(GetElementPtrInst *GEP, bool &NeedsExtraction); 422 423 /// Canonicalize array indices to pointer-size integers. This helps to 424 /// simplify the logic of splitting a GEP. For example, if a + b is a 425 /// pointer-size integer, we have 426 /// gep base, a + b = gep (gep base, a), b 427 /// However, this equality may not hold if the size of a + b is smaller than 428 /// the pointer size, because LLVM conceptually sign-extends GEP indices to 429 /// pointer size before computing the address 430 /// (http://llvm.org/docs/LangRef.html#id181). 431 /// 432 /// This canonicalization is very likely already done in clang and 433 /// instcombine. Therefore, the program will probably remain the same. 434 /// 435 /// Returns true if the module changes. 436 /// 437 /// Verified in @i32_add in split-gep.ll 438 bool canonicalizeArrayIndicesToIndexSize(GetElementPtrInst *GEP); 439 440 /// Optimize sext(a)+sext(b) to sext(a+b) when a+b can't sign overflow. 441 /// SeparateConstOffsetFromGEP distributes a sext to leaves before extracting 442 /// the constant offset. After extraction, it becomes desirable to reunion the 443 /// distributed sexts. For example, 444 /// 445 /// &a[sext(i +nsw (j +nsw 5)] 446 /// => distribute &a[sext(i) +nsw (sext(j) +nsw 5)] 447 /// => constant extraction &a[sext(i) + sext(j)] + 5 448 /// => reunion &a[sext(i +nsw j)] + 5 449 bool reuniteExts(Function &F); 450 451 /// A helper that reunites sexts in an instruction. 452 bool reuniteExts(Instruction *I); 453 454 /// Find the closest dominator of <Dominatee> that is equivalent to <Key>. 455 Instruction *findClosestMatchingDominator( 456 ExprKey Key, Instruction *Dominatee, 457 DenseMap<ExprKey, SmallVector<Instruction *, 2>> &DominatingExprs); 458 459 /// Verify F is free of dead code. 460 void verifyNoDeadCode(Function &F); 461 462 bool hasMoreThanOneUseInLoop(Value *v, Loop *L); 463 464 // Swap the index operand of two GEP. 465 void swapGEPOperand(GetElementPtrInst *First, GetElementPtrInst *Second); 466 467 // Check if it is safe to swap operand of two GEP. 468 bool isLegalToSwapOperand(GetElementPtrInst *First, GetElementPtrInst *Second, 469 Loop *CurLoop); 470 471 const DataLayout *DL = nullptr; 472 DominatorTree *DT = nullptr; 473 LoopInfo *LI; 474 TargetLibraryInfo *TLI; 475 // Retrieved lazily since not always used. 476 function_ref<TargetTransformInfo &(Function &)> GetTTI; 477 478 /// Whether to lower a GEP with multiple indices into arithmetic operations or 479 /// multiple GEPs with a single index. 480 bool LowerGEP; 481 482 DenseMap<ExprKey, SmallVector<Instruction *, 2>> DominatingAdds; 483 DenseMap<ExprKey, SmallVector<Instruction *, 2>> DominatingSubs; 484 }; 485 486 } // end anonymous namespace 487 488 char SeparateConstOffsetFromGEPLegacyPass::ID = 0; 489 490 INITIALIZE_PASS_BEGIN( 491 SeparateConstOffsetFromGEPLegacyPass, "separate-const-offset-from-gep", 492 "Split GEPs to a variadic base and a constant offset for better CSE", false, 493 false) 494 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 495 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass) 496 INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass) 497 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 498 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass) 499 INITIALIZE_PASS_END( 500 SeparateConstOffsetFromGEPLegacyPass, "separate-const-offset-from-gep", 501 "Split GEPs to a variadic base and a constant offset for better CSE", false, 502 false) 503 504 FunctionPass *llvm::createSeparateConstOffsetFromGEPPass(bool LowerGEP) { 505 return new SeparateConstOffsetFromGEPLegacyPass(LowerGEP); 506 } 507 508 bool ConstantOffsetExtractor::CanTraceInto(bool SignExtended, 509 bool ZeroExtended, 510 BinaryOperator *BO, 511 bool NonNegative) { 512 // We only consider ADD, SUB and OR, because a non-zero constant found in 513 // expressions composed of these operations can be easily hoisted as a 514 // constant offset by reassociation. 515 if (BO->getOpcode() != Instruction::Add && 516 BO->getOpcode() != Instruction::Sub && 517 BO->getOpcode() != Instruction::Or) { 518 return false; 519 } 520 521 Value *LHS = BO->getOperand(0), *RHS = BO->getOperand(1); 522 // Do not trace into "or" unless it is equivalent to "add". If LHS and RHS 523 // don't have common bits, (LHS | RHS) is equivalent to (LHS + RHS). 524 // FIXME: this does not appear to be covered by any tests 525 // (with x86/aarch64 backends at least) 526 if (BO->getOpcode() == Instruction::Or && 527 !haveNoCommonBitsSet(LHS, RHS, SimplifyQuery(DL, DT, /*AC*/ nullptr, BO))) 528 return false; 529 530 // FIXME: We don't currently support constants from the RHS of subs, 531 // when we are zero-extended, because we need a way to zero-extended 532 // them before they are negated. 533 if (ZeroExtended && !SignExtended && BO->getOpcode() == Instruction::Sub) 534 return false; 535 536 // In addition, tracing into BO requires that its surrounding s/zext (if 537 // any) is distributable to both operands. 538 // 539 // Suppose BO = A op B. 540 // SignExtended | ZeroExtended | Distributable? 541 // --------------+--------------+---------------------------------- 542 // 0 | 0 | true because no s/zext exists 543 // 0 | 1 | zext(BO) == zext(A) op zext(B) 544 // 1 | 0 | sext(BO) == sext(A) op sext(B) 545 // 1 | 1 | zext(sext(BO)) == 546 // | | zext(sext(A)) op zext(sext(B)) 547 if (BO->getOpcode() == Instruction::Add && !ZeroExtended && NonNegative) { 548 // If a + b >= 0 and (a >= 0 or b >= 0), then 549 // sext(a + b) = sext(a) + sext(b) 550 // even if the addition is not marked nsw. 551 // 552 // Leveraging this invariant, we can trace into an sext'ed inbound GEP 553 // index if the constant offset is non-negative. 554 // 555 // Verified in @sext_add in split-gep.ll. 556 if (ConstantInt *ConstLHS = dyn_cast<ConstantInt>(LHS)) { 557 if (!ConstLHS->isNegative()) 558 return true; 559 } 560 if (ConstantInt *ConstRHS = dyn_cast<ConstantInt>(RHS)) { 561 if (!ConstRHS->isNegative()) 562 return true; 563 } 564 } 565 566 // sext (add/sub nsw A, B) == add/sub nsw (sext A), (sext B) 567 // zext (add/sub nuw A, B) == add/sub nuw (zext A), (zext B) 568 if (BO->getOpcode() == Instruction::Add || 569 BO->getOpcode() == Instruction::Sub) { 570 if (SignExtended && !BO->hasNoSignedWrap()) 571 return false; 572 if (ZeroExtended && !BO->hasNoUnsignedWrap()) 573 return false; 574 } 575 576 return true; 577 } 578 579 APInt ConstantOffsetExtractor::findInEitherOperand(BinaryOperator *BO, 580 bool SignExtended, 581 bool ZeroExtended) { 582 // Save off the current height of the chain, in case we need to restore it. 583 size_t ChainLength = UserChain.size(); 584 585 // BO being non-negative does not shed light on whether its operands are 586 // non-negative. Clear the NonNegative flag here. 587 APInt ConstantOffset = find(BO->getOperand(0), SignExtended, ZeroExtended, 588 /* NonNegative */ false); 589 // If we found a constant offset in the left operand, stop and return that. 590 // This shortcut might cause us to miss opportunities of combining the 591 // constant offsets in both operands, e.g., (a + 4) + (b + 5) => (a + b) + 9. 592 // However, such cases are probably already handled by -instcombine, 593 // given this pass runs after the standard optimizations. 594 if (ConstantOffset != 0) return ConstantOffset; 595 596 // Reset the chain back to where it was when we started exploring this node, 597 // since visiting the LHS didn't pan out. 598 UserChain.resize(ChainLength); 599 600 ConstantOffset = find(BO->getOperand(1), SignExtended, ZeroExtended, 601 /* NonNegative */ false); 602 // If U is a sub operator, negate the constant offset found in the right 603 // operand. 604 if (BO->getOpcode() == Instruction::Sub) 605 ConstantOffset = -ConstantOffset; 606 607 // If RHS wasn't a suitable candidate either, reset the chain again. 608 if (ConstantOffset == 0) 609 UserChain.resize(ChainLength); 610 611 return ConstantOffset; 612 } 613 614 APInt ConstantOffsetExtractor::find(Value *V, bool SignExtended, 615 bool ZeroExtended, bool NonNegative) { 616 // TODO(jingyue): We could trace into integer/pointer casts, such as 617 // inttoptr, ptrtoint, bitcast, and addrspacecast. We choose to handle only 618 // integers because it gives good enough results for our benchmarks. 619 unsigned BitWidth = cast<IntegerType>(V->getType())->getBitWidth(); 620 621 // We cannot do much with Values that are not a User, such as an Argument. 622 User *U = dyn_cast<User>(V); 623 if (U == nullptr) return APInt(BitWidth, 0); 624 625 APInt ConstantOffset(BitWidth, 0); 626 if (ConstantInt *CI = dyn_cast<ConstantInt>(V)) { 627 // Hooray, we found it! 628 ConstantOffset = CI->getValue(); 629 } else if (BinaryOperator *BO = dyn_cast<BinaryOperator>(V)) { 630 // Trace into subexpressions for more hoisting opportunities. 631 if (CanTraceInto(SignExtended, ZeroExtended, BO, NonNegative)) 632 ConstantOffset = findInEitherOperand(BO, SignExtended, ZeroExtended); 633 } else if (isa<TruncInst>(V)) { 634 ConstantOffset = 635 find(U->getOperand(0), SignExtended, ZeroExtended, NonNegative) 636 .trunc(BitWidth); 637 } else if (isa<SExtInst>(V)) { 638 ConstantOffset = find(U->getOperand(0), /* SignExtended */ true, 639 ZeroExtended, NonNegative).sext(BitWidth); 640 } else if (isa<ZExtInst>(V)) { 641 // As an optimization, we can clear the SignExtended flag because 642 // sext(zext(a)) = zext(a). Verified in @sext_zext in split-gep.ll. 643 // 644 // Clear the NonNegative flag, because zext(a) >= 0 does not imply a >= 0. 645 ConstantOffset = 646 find(U->getOperand(0), /* SignExtended */ false, 647 /* ZeroExtended */ true, /* NonNegative */ false).zext(BitWidth); 648 } 649 650 // If we found a non-zero constant offset, add it to the path for 651 // rebuildWithoutConstOffset. Zero is a valid constant offset, but doesn't 652 // help this optimization. 653 if (ConstantOffset != 0) 654 UserChain.push_back(U); 655 return ConstantOffset; 656 } 657 658 Value *ConstantOffsetExtractor::applyExts(Value *V) { 659 Value *Current = V; 660 // ExtInsts is built in the use-def order. Therefore, we apply them to V 661 // in the reversed order. 662 for (CastInst *I : llvm::reverse(ExtInsts)) { 663 if (Constant *C = dyn_cast<Constant>(Current)) { 664 // Try to constant fold the cast. 665 Current = ConstantFoldCastOperand(I->getOpcode(), C, I->getType(), DL); 666 if (Current) 667 continue; 668 } 669 670 Instruction *Ext = I->clone(); 671 Ext->setOperand(0, Current); 672 Ext->insertBefore(IP); 673 Current = Ext; 674 } 675 return Current; 676 } 677 678 Value *ConstantOffsetExtractor::rebuildWithoutConstOffset() { 679 distributeExtsAndCloneChain(UserChain.size() - 1); 680 // Remove all nullptrs (used to be s/zext) from UserChain. 681 unsigned NewSize = 0; 682 for (User *I : UserChain) { 683 if (I != nullptr) { 684 UserChain[NewSize] = I; 685 NewSize++; 686 } 687 } 688 UserChain.resize(NewSize); 689 return removeConstOffset(UserChain.size() - 1); 690 } 691 692 Value * 693 ConstantOffsetExtractor::distributeExtsAndCloneChain(unsigned ChainIndex) { 694 User *U = UserChain[ChainIndex]; 695 if (ChainIndex == 0) { 696 assert(isa<ConstantInt>(U)); 697 // If U is a ConstantInt, applyExts will return a ConstantInt as well. 698 return UserChain[ChainIndex] = cast<ConstantInt>(applyExts(U)); 699 } 700 701 if (CastInst *Cast = dyn_cast<CastInst>(U)) { 702 assert( 703 (isa<SExtInst>(Cast) || isa<ZExtInst>(Cast) || isa<TruncInst>(Cast)) && 704 "Only following instructions can be traced: sext, zext & trunc"); 705 ExtInsts.push_back(Cast); 706 UserChain[ChainIndex] = nullptr; 707 return distributeExtsAndCloneChain(ChainIndex - 1); 708 } 709 710 // Function find only trace into BinaryOperator and CastInst. 711 BinaryOperator *BO = cast<BinaryOperator>(U); 712 // OpNo = which operand of BO is UserChain[ChainIndex - 1] 713 unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1); 714 Value *TheOther = applyExts(BO->getOperand(1 - OpNo)); 715 Value *NextInChain = distributeExtsAndCloneChain(ChainIndex - 1); 716 717 BinaryOperator *NewBO = nullptr; 718 if (OpNo == 0) { 719 NewBO = BinaryOperator::Create(BO->getOpcode(), NextInChain, TheOther, 720 BO->getName(), IP); 721 } else { 722 NewBO = BinaryOperator::Create(BO->getOpcode(), TheOther, NextInChain, 723 BO->getName(), IP); 724 } 725 return UserChain[ChainIndex] = NewBO; 726 } 727 728 Value *ConstantOffsetExtractor::removeConstOffset(unsigned ChainIndex) { 729 if (ChainIndex == 0) { 730 assert(isa<ConstantInt>(UserChain[ChainIndex])); 731 return ConstantInt::getNullValue(UserChain[ChainIndex]->getType()); 732 } 733 734 BinaryOperator *BO = cast<BinaryOperator>(UserChain[ChainIndex]); 735 assert((BO->use_empty() || BO->hasOneUse()) && 736 "distributeExtsAndCloneChain clones each BinaryOperator in " 737 "UserChain, so no one should be used more than " 738 "once"); 739 740 unsigned OpNo = (BO->getOperand(0) == UserChain[ChainIndex - 1] ? 0 : 1); 741 assert(BO->getOperand(OpNo) == UserChain[ChainIndex - 1]); 742 Value *NextInChain = removeConstOffset(ChainIndex - 1); 743 Value *TheOther = BO->getOperand(1 - OpNo); 744 745 // If NextInChain is 0 and not the LHS of a sub, we can simplify the 746 // sub-expression to be just TheOther. 747 if (ConstantInt *CI = dyn_cast<ConstantInt>(NextInChain)) { 748 if (CI->isZero() && !(BO->getOpcode() == Instruction::Sub && OpNo == 0)) 749 return TheOther; 750 } 751 752 BinaryOperator::BinaryOps NewOp = BO->getOpcode(); 753 if (BO->getOpcode() == Instruction::Or) { 754 // Rebuild "or" as "add", because "or" may be invalid for the new 755 // expression. 756 // 757 // For instance, given 758 // a | (b + 5) where a and b + 5 have no common bits, 759 // we can extract 5 as the constant offset. 760 // 761 // However, reusing the "or" in the new index would give us 762 // (a | b) + 5 763 // which does not equal a | (b + 5). 764 // 765 // Replacing the "or" with "add" is fine, because 766 // a | (b + 5) = a + (b + 5) = (a + b) + 5 767 NewOp = Instruction::Add; 768 } 769 770 BinaryOperator *NewBO; 771 if (OpNo == 0) { 772 NewBO = BinaryOperator::Create(NewOp, NextInChain, TheOther, "", IP); 773 } else { 774 NewBO = BinaryOperator::Create(NewOp, TheOther, NextInChain, "", IP); 775 } 776 NewBO->takeName(BO); 777 return NewBO; 778 } 779 780 Value *ConstantOffsetExtractor::Extract(Value *Idx, GetElementPtrInst *GEP, 781 User *&UserChainTail, 782 const DominatorTree *DT) { 783 ConstantOffsetExtractor Extractor(GEP, DT); 784 // Find a non-zero constant offset first. 785 APInt ConstantOffset = 786 Extractor.find(Idx, /* SignExtended */ false, /* ZeroExtended */ false, 787 GEP->isInBounds()); 788 if (ConstantOffset == 0) { 789 UserChainTail = nullptr; 790 return nullptr; 791 } 792 // Separates the constant offset from the GEP index. 793 Value *IdxWithoutConstOffset = Extractor.rebuildWithoutConstOffset(); 794 UserChainTail = Extractor.UserChain.back(); 795 return IdxWithoutConstOffset; 796 } 797 798 int64_t ConstantOffsetExtractor::Find(Value *Idx, GetElementPtrInst *GEP, 799 const DominatorTree *DT) { 800 // If Idx is an index of an inbound GEP, Idx is guaranteed to be non-negative. 801 return ConstantOffsetExtractor(GEP, DT) 802 .find(Idx, /* SignExtended */ false, /* ZeroExtended */ false, 803 GEP->isInBounds()) 804 .getSExtValue(); 805 } 806 807 bool SeparateConstOffsetFromGEP::canonicalizeArrayIndicesToIndexSize( 808 GetElementPtrInst *GEP) { 809 bool Changed = false; 810 Type *PtrIdxTy = DL->getIndexType(GEP->getType()); 811 gep_type_iterator GTI = gep_type_begin(*GEP); 812 for (User::op_iterator I = GEP->op_begin() + 1, E = GEP->op_end(); 813 I != E; ++I, ++GTI) { 814 // Skip struct member indices which must be i32. 815 if (GTI.isSequential()) { 816 if ((*I)->getType() != PtrIdxTy) { 817 *I = CastInst::CreateIntegerCast(*I, PtrIdxTy, true, "idxprom", GEP); 818 Changed = true; 819 } 820 } 821 } 822 return Changed; 823 } 824 825 int64_t 826 SeparateConstOffsetFromGEP::accumulateByteOffset(GetElementPtrInst *GEP, 827 bool &NeedsExtraction) { 828 NeedsExtraction = false; 829 int64_t AccumulativeByteOffset = 0; 830 gep_type_iterator GTI = gep_type_begin(*GEP); 831 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) { 832 if (GTI.isSequential()) { 833 // Constant offsets of scalable types are not really constant. 834 if (GTI.getIndexedType()->isScalableTy()) 835 continue; 836 837 // Tries to extract a constant offset from this GEP index. 838 int64_t ConstantOffset = 839 ConstantOffsetExtractor::Find(GEP->getOperand(I), GEP, DT); 840 if (ConstantOffset != 0) { 841 NeedsExtraction = true; 842 // A GEP may have multiple indices. We accumulate the extracted 843 // constant offset to a byte offset, and later offset the remainder of 844 // the original GEP with this byte offset. 845 AccumulativeByteOffset += 846 ConstantOffset * GTI.getSequentialElementStride(*DL); 847 } 848 } else if (LowerGEP) { 849 StructType *StTy = GTI.getStructType(); 850 uint64_t Field = cast<ConstantInt>(GEP->getOperand(I))->getZExtValue(); 851 // Skip field 0 as the offset is always 0. 852 if (Field != 0) { 853 NeedsExtraction = true; 854 AccumulativeByteOffset += 855 DL->getStructLayout(StTy)->getElementOffset(Field); 856 } 857 } 858 } 859 return AccumulativeByteOffset; 860 } 861 862 void SeparateConstOffsetFromGEP::lowerToSingleIndexGEPs( 863 GetElementPtrInst *Variadic, int64_t AccumulativeByteOffset) { 864 IRBuilder<> Builder(Variadic); 865 Type *PtrIndexTy = DL->getIndexType(Variadic->getType()); 866 867 Value *ResultPtr = Variadic->getOperand(0); 868 Loop *L = LI->getLoopFor(Variadic->getParent()); 869 // Check if the base is not loop invariant or used more than once. 870 bool isSwapCandidate = 871 L && L->isLoopInvariant(ResultPtr) && 872 !hasMoreThanOneUseInLoop(ResultPtr, L); 873 Value *FirstResult = nullptr; 874 875 gep_type_iterator GTI = gep_type_begin(*Variadic); 876 // Create an ugly GEP for each sequential index. We don't create GEPs for 877 // structure indices, as they are accumulated in the constant offset index. 878 for (unsigned I = 1, E = Variadic->getNumOperands(); I != E; ++I, ++GTI) { 879 if (GTI.isSequential()) { 880 Value *Idx = Variadic->getOperand(I); 881 // Skip zero indices. 882 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) 883 if (CI->isZero()) 884 continue; 885 886 APInt ElementSize = APInt(PtrIndexTy->getIntegerBitWidth(), 887 GTI.getSequentialElementStride(*DL)); 888 // Scale the index by element size. 889 if (ElementSize != 1) { 890 if (ElementSize.isPowerOf2()) { 891 Idx = Builder.CreateShl( 892 Idx, ConstantInt::get(PtrIndexTy, ElementSize.logBase2())); 893 } else { 894 Idx = 895 Builder.CreateMul(Idx, ConstantInt::get(PtrIndexTy, ElementSize)); 896 } 897 } 898 // Create an ugly GEP with a single index for each index. 899 ResultPtr = 900 Builder.CreateGEP(Builder.getInt8Ty(), ResultPtr, Idx, "uglygep"); 901 if (FirstResult == nullptr) 902 FirstResult = ResultPtr; 903 } 904 } 905 906 // Create a GEP with the constant offset index. 907 if (AccumulativeByteOffset != 0) { 908 Value *Offset = ConstantInt::get(PtrIndexTy, AccumulativeByteOffset); 909 ResultPtr = 910 Builder.CreateGEP(Builder.getInt8Ty(), ResultPtr, Offset, "uglygep"); 911 } else 912 isSwapCandidate = false; 913 914 // If we created a GEP with constant index, and the base is loop invariant, 915 // then we swap the first one with it, so LICM can move constant GEP out 916 // later. 917 auto *FirstGEP = dyn_cast_or_null<GetElementPtrInst>(FirstResult); 918 auto *SecondGEP = dyn_cast<GetElementPtrInst>(ResultPtr); 919 if (isSwapCandidate && isLegalToSwapOperand(FirstGEP, SecondGEP, L)) 920 swapGEPOperand(FirstGEP, SecondGEP); 921 922 Variadic->replaceAllUsesWith(ResultPtr); 923 Variadic->eraseFromParent(); 924 } 925 926 void 927 SeparateConstOffsetFromGEP::lowerToArithmetics(GetElementPtrInst *Variadic, 928 int64_t AccumulativeByteOffset) { 929 IRBuilder<> Builder(Variadic); 930 Type *IntPtrTy = DL->getIntPtrType(Variadic->getType()); 931 assert(IntPtrTy == DL->getIndexType(Variadic->getType()) && 932 "Pointer type must match index type for arithmetic-based lowering of " 933 "split GEPs"); 934 935 Value *ResultPtr = Builder.CreatePtrToInt(Variadic->getOperand(0), IntPtrTy); 936 gep_type_iterator GTI = gep_type_begin(*Variadic); 937 // Create ADD/SHL/MUL arithmetic operations for each sequential indices. We 938 // don't create arithmetics for structure indices, as they are accumulated 939 // in the constant offset index. 940 for (unsigned I = 1, E = Variadic->getNumOperands(); I != E; ++I, ++GTI) { 941 if (GTI.isSequential()) { 942 Value *Idx = Variadic->getOperand(I); 943 // Skip zero indices. 944 if (ConstantInt *CI = dyn_cast<ConstantInt>(Idx)) 945 if (CI->isZero()) 946 continue; 947 948 APInt ElementSize = APInt(IntPtrTy->getIntegerBitWidth(), 949 GTI.getSequentialElementStride(*DL)); 950 // Scale the index by element size. 951 if (ElementSize != 1) { 952 if (ElementSize.isPowerOf2()) { 953 Idx = Builder.CreateShl( 954 Idx, ConstantInt::get(IntPtrTy, ElementSize.logBase2())); 955 } else { 956 Idx = Builder.CreateMul(Idx, ConstantInt::get(IntPtrTy, ElementSize)); 957 } 958 } 959 // Create an ADD for each index. 960 ResultPtr = Builder.CreateAdd(ResultPtr, Idx); 961 } 962 } 963 964 // Create an ADD for the constant offset index. 965 if (AccumulativeByteOffset != 0) { 966 ResultPtr = Builder.CreateAdd( 967 ResultPtr, ConstantInt::get(IntPtrTy, AccumulativeByteOffset)); 968 } 969 970 ResultPtr = Builder.CreateIntToPtr(ResultPtr, Variadic->getType()); 971 Variadic->replaceAllUsesWith(ResultPtr); 972 Variadic->eraseFromParent(); 973 } 974 975 bool SeparateConstOffsetFromGEP::splitGEP(GetElementPtrInst *GEP) { 976 // Skip vector GEPs. 977 if (GEP->getType()->isVectorTy()) 978 return false; 979 980 // The backend can already nicely handle the case where all indices are 981 // constant. 982 if (GEP->hasAllConstantIndices()) 983 return false; 984 985 bool Changed = canonicalizeArrayIndicesToIndexSize(GEP); 986 987 bool NeedsExtraction; 988 int64_t AccumulativeByteOffset = accumulateByteOffset(GEP, NeedsExtraction); 989 990 if (!NeedsExtraction) 991 return Changed; 992 993 TargetTransformInfo &TTI = GetTTI(*GEP->getFunction()); 994 995 // If LowerGEP is disabled, before really splitting the GEP, check whether the 996 // backend supports the addressing mode we are about to produce. If no, this 997 // splitting probably won't be beneficial. 998 // If LowerGEP is enabled, even the extracted constant offset can not match 999 // the addressing mode, we can still do optimizations to other lowered parts 1000 // of variable indices. Therefore, we don't check for addressing modes in that 1001 // case. 1002 if (!LowerGEP) { 1003 unsigned AddrSpace = GEP->getPointerAddressSpace(); 1004 if (!TTI.isLegalAddressingMode(GEP->getResultElementType(), 1005 /*BaseGV=*/nullptr, AccumulativeByteOffset, 1006 /*HasBaseReg=*/true, /*Scale=*/0, 1007 AddrSpace)) { 1008 return Changed; 1009 } 1010 } 1011 1012 // Remove the constant offset in each sequential index. The resultant GEP 1013 // computes the variadic base. 1014 // Notice that we don't remove struct field indices here. If LowerGEP is 1015 // disabled, a structure index is not accumulated and we still use the old 1016 // one. If LowerGEP is enabled, a structure index is accumulated in the 1017 // constant offset. LowerToSingleIndexGEPs or lowerToArithmetics will later 1018 // handle the constant offset and won't need a new structure index. 1019 gep_type_iterator GTI = gep_type_begin(*GEP); 1020 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) { 1021 if (GTI.isSequential()) { 1022 // Constant offsets of scalable types are not really constant. 1023 if (GTI.getIndexedType()->isScalableTy()) 1024 continue; 1025 1026 // Splits this GEP index into a variadic part and a constant offset, and 1027 // uses the variadic part as the new index. 1028 Value *OldIdx = GEP->getOperand(I); 1029 User *UserChainTail; 1030 Value *NewIdx = 1031 ConstantOffsetExtractor::Extract(OldIdx, GEP, UserChainTail, DT); 1032 if (NewIdx != nullptr) { 1033 // Switches to the index with the constant offset removed. 1034 GEP->setOperand(I, NewIdx); 1035 // After switching to the new index, we can garbage-collect UserChain 1036 // and the old index if they are not used. 1037 RecursivelyDeleteTriviallyDeadInstructions(UserChainTail); 1038 RecursivelyDeleteTriviallyDeadInstructions(OldIdx); 1039 } 1040 } 1041 } 1042 1043 // Clear the inbounds attribute because the new index may be off-bound. 1044 // e.g., 1045 // 1046 // b = add i64 a, 5 1047 // addr = gep inbounds float, float* p, i64 b 1048 // 1049 // is transformed to: 1050 // 1051 // addr2 = gep float, float* p, i64 a ; inbounds removed 1052 // addr = gep inbounds float, float* addr2, i64 5 1053 // 1054 // If a is -4, although the old index b is in bounds, the new index a is 1055 // off-bound. http://llvm.org/docs/LangRef.html#id181 says "if the 1056 // inbounds keyword is not present, the offsets are added to the base 1057 // address with silently-wrapping two's complement arithmetic". 1058 // Therefore, the final code will be a semantically equivalent. 1059 // 1060 // TODO(jingyue): do some range analysis to keep as many inbounds as 1061 // possible. GEPs with inbounds are more friendly to alias analysis. 1062 bool GEPWasInBounds = GEP->isInBounds(); 1063 GEP->setIsInBounds(false); 1064 1065 // Lowers a GEP to either GEPs with a single index or arithmetic operations. 1066 if (LowerGEP) { 1067 // As currently BasicAA does not analyze ptrtoint/inttoptr, do not lower to 1068 // arithmetic operations if the target uses alias analysis in codegen. 1069 // Additionally, pointers that aren't integral (and so can't be safely 1070 // converted to integers) or those whose offset size is different from their 1071 // pointer size (which means that doing integer arithmetic on them could 1072 // affect that data) can't be lowered in this way. 1073 unsigned AddrSpace = GEP->getPointerAddressSpace(); 1074 bool PointerHasExtraData = DL->getPointerSizeInBits(AddrSpace) != 1075 DL->getIndexSizeInBits(AddrSpace); 1076 if (TTI.useAA() || DL->isNonIntegralAddressSpace(AddrSpace) || 1077 PointerHasExtraData) 1078 lowerToSingleIndexGEPs(GEP, AccumulativeByteOffset); 1079 else 1080 lowerToArithmetics(GEP, AccumulativeByteOffset); 1081 return true; 1082 } 1083 1084 // No need to create another GEP if the accumulative byte offset is 0. 1085 if (AccumulativeByteOffset == 0) 1086 return true; 1087 1088 // Offsets the base with the accumulative byte offset. 1089 // 1090 // %gep ; the base 1091 // ... %gep ... 1092 // 1093 // => add the offset 1094 // 1095 // %gep2 ; clone of %gep 1096 // %new.gep = gep %gep2, <offset / sizeof(*%gep)> 1097 // %gep ; will be removed 1098 // ... %gep ... 1099 // 1100 // => replace all uses of %gep with %new.gep and remove %gep 1101 // 1102 // %gep2 ; clone of %gep 1103 // %new.gep = gep %gep2, <offset / sizeof(*%gep)> 1104 // ... %new.gep ... 1105 // 1106 // If AccumulativeByteOffset is not a multiple of sizeof(*%gep), we emit an 1107 // uglygep (http://llvm.org/docs/GetElementPtr.html#what-s-an-uglygep): 1108 // bitcast %gep2 to i8*, add the offset, and bitcast the result back to the 1109 // type of %gep. 1110 // 1111 // %gep2 ; clone of %gep 1112 // %0 = bitcast %gep2 to i8* 1113 // %uglygep = gep %0, <offset> 1114 // %new.gep = bitcast %uglygep to <type of %gep> 1115 // ... %new.gep ... 1116 Instruction *NewGEP = GEP->clone(); 1117 NewGEP->insertBefore(GEP); 1118 1119 // Per ANSI C standard, signed / unsigned = unsigned and signed % unsigned = 1120 // unsigned.. Therefore, we cast ElementTypeSizeOfGEP to signed because it is 1121 // used with unsigned integers later. 1122 int64_t ElementTypeSizeOfGEP = static_cast<int64_t>( 1123 DL->getTypeAllocSize(GEP->getResultElementType())); 1124 Type *PtrIdxTy = DL->getIndexType(GEP->getType()); 1125 if (AccumulativeByteOffset % ElementTypeSizeOfGEP == 0) { 1126 // Very likely. As long as %gep is naturally aligned, the byte offset we 1127 // extracted should be a multiple of sizeof(*%gep). 1128 int64_t Index = AccumulativeByteOffset / ElementTypeSizeOfGEP; 1129 NewGEP = GetElementPtrInst::Create(GEP->getResultElementType(), NewGEP, 1130 ConstantInt::get(PtrIdxTy, Index, true), 1131 GEP->getName(), GEP); 1132 NewGEP->copyMetadata(*GEP); 1133 // Inherit the inbounds attribute of the original GEP. 1134 cast<GetElementPtrInst>(NewGEP)->setIsInBounds(GEPWasInBounds); 1135 } else { 1136 // Unlikely but possible. For example, 1137 // #pragma pack(1) 1138 // struct S { 1139 // int a[3]; 1140 // int64 b[8]; 1141 // }; 1142 // #pragma pack() 1143 // 1144 // Suppose the gep before extraction is &s[i + 1].b[j + 3]. After 1145 // extraction, it becomes &s[i].b[j] and AccumulativeByteOffset is 1146 // sizeof(S) + 3 * sizeof(int64) = 100, which is not a multiple of 1147 // sizeof(int64). 1148 // 1149 // Emit an uglygep in this case. 1150 IRBuilder<> Builder(GEP); 1151 NewGEP = cast<Instruction>(Builder.CreateGEP( 1152 Builder.getInt8Ty(), NewGEP, 1153 {ConstantInt::get(PtrIdxTy, AccumulativeByteOffset, true)}, "uglygep", 1154 GEPWasInBounds)); 1155 NewGEP->copyMetadata(*GEP); 1156 } 1157 1158 GEP->replaceAllUsesWith(NewGEP); 1159 GEP->eraseFromParent(); 1160 1161 return true; 1162 } 1163 1164 bool SeparateConstOffsetFromGEPLegacyPass::runOnFunction(Function &F) { 1165 if (skipFunction(F)) 1166 return false; 1167 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 1168 auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 1169 auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F); 1170 auto GetTTI = [this](Function &F) -> TargetTransformInfo & { 1171 return this->getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F); 1172 }; 1173 SeparateConstOffsetFromGEP Impl(DT, LI, TLI, GetTTI, LowerGEP); 1174 return Impl.run(F); 1175 } 1176 1177 bool SeparateConstOffsetFromGEP::run(Function &F) { 1178 if (DisableSeparateConstOffsetFromGEP) 1179 return false; 1180 1181 DL = &F.getParent()->getDataLayout(); 1182 bool Changed = false; 1183 for (BasicBlock &B : F) { 1184 if (!DT->isReachableFromEntry(&B)) 1185 continue; 1186 1187 for (Instruction &I : llvm::make_early_inc_range(B)) 1188 if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(&I)) 1189 Changed |= splitGEP(GEP); 1190 // No need to split GEP ConstantExprs because all its indices are constant 1191 // already. 1192 } 1193 1194 Changed |= reuniteExts(F); 1195 1196 if (VerifyNoDeadCode) 1197 verifyNoDeadCode(F); 1198 1199 return Changed; 1200 } 1201 1202 Instruction *SeparateConstOffsetFromGEP::findClosestMatchingDominator( 1203 ExprKey Key, Instruction *Dominatee, 1204 DenseMap<ExprKey, SmallVector<Instruction *, 2>> &DominatingExprs) { 1205 auto Pos = DominatingExprs.find(Key); 1206 if (Pos == DominatingExprs.end()) 1207 return nullptr; 1208 1209 auto &Candidates = Pos->second; 1210 // Because we process the basic blocks in pre-order of the dominator tree, a 1211 // candidate that doesn't dominate the current instruction won't dominate any 1212 // future instruction either. Therefore, we pop it out of the stack. This 1213 // optimization makes the algorithm O(n). 1214 while (!Candidates.empty()) { 1215 Instruction *Candidate = Candidates.back(); 1216 if (DT->dominates(Candidate, Dominatee)) 1217 return Candidate; 1218 Candidates.pop_back(); 1219 } 1220 return nullptr; 1221 } 1222 1223 bool SeparateConstOffsetFromGEP::reuniteExts(Instruction *I) { 1224 if (!I->getType()->isIntOrIntVectorTy()) 1225 return false; 1226 1227 // Dom: LHS+RHS 1228 // I: sext(LHS)+sext(RHS) 1229 // If Dom can't sign overflow and Dom dominates I, optimize I to sext(Dom). 1230 // TODO: handle zext 1231 Value *LHS = nullptr, *RHS = nullptr; 1232 if (match(I, m_Add(m_SExt(m_Value(LHS)), m_SExt(m_Value(RHS))))) { 1233 if (LHS->getType() == RHS->getType()) { 1234 ExprKey Key = createNormalizedCommutablePair(LHS, RHS); 1235 if (auto *Dom = findClosestMatchingDominator(Key, I, DominatingAdds)) { 1236 Instruction *NewSExt = new SExtInst(Dom, I->getType(), "", I); 1237 NewSExt->takeName(I); 1238 I->replaceAllUsesWith(NewSExt); 1239 RecursivelyDeleteTriviallyDeadInstructions(I); 1240 return true; 1241 } 1242 } 1243 } else if (match(I, m_Sub(m_SExt(m_Value(LHS)), m_SExt(m_Value(RHS))))) { 1244 if (LHS->getType() == RHS->getType()) { 1245 if (auto *Dom = 1246 findClosestMatchingDominator({LHS, RHS}, I, DominatingSubs)) { 1247 Instruction *NewSExt = new SExtInst(Dom, I->getType(), "", I); 1248 NewSExt->takeName(I); 1249 I->replaceAllUsesWith(NewSExt); 1250 RecursivelyDeleteTriviallyDeadInstructions(I); 1251 return true; 1252 } 1253 } 1254 } 1255 1256 // Add I to DominatingExprs if it's an add/sub that can't sign overflow. 1257 if (match(I, m_NSWAdd(m_Value(LHS), m_Value(RHS)))) { 1258 if (programUndefinedIfPoison(I)) { 1259 ExprKey Key = createNormalizedCommutablePair(LHS, RHS); 1260 DominatingAdds[Key].push_back(I); 1261 } 1262 } else if (match(I, m_NSWSub(m_Value(LHS), m_Value(RHS)))) { 1263 if (programUndefinedIfPoison(I)) 1264 DominatingSubs[{LHS, RHS}].push_back(I); 1265 } 1266 return false; 1267 } 1268 1269 bool SeparateConstOffsetFromGEP::reuniteExts(Function &F) { 1270 bool Changed = false; 1271 DominatingAdds.clear(); 1272 DominatingSubs.clear(); 1273 for (const auto Node : depth_first(DT)) { 1274 BasicBlock *BB = Node->getBlock(); 1275 for (Instruction &I : llvm::make_early_inc_range(*BB)) 1276 Changed |= reuniteExts(&I); 1277 } 1278 return Changed; 1279 } 1280 1281 void SeparateConstOffsetFromGEP::verifyNoDeadCode(Function &F) { 1282 for (BasicBlock &B : F) { 1283 for (Instruction &I : B) { 1284 if (isInstructionTriviallyDead(&I)) { 1285 std::string ErrMessage; 1286 raw_string_ostream RSO(ErrMessage); 1287 RSO << "Dead instruction detected!\n" << I << "\n"; 1288 llvm_unreachable(RSO.str().c_str()); 1289 } 1290 } 1291 } 1292 } 1293 1294 bool SeparateConstOffsetFromGEP::isLegalToSwapOperand( 1295 GetElementPtrInst *FirstGEP, GetElementPtrInst *SecondGEP, Loop *CurLoop) { 1296 if (!FirstGEP || !FirstGEP->hasOneUse()) 1297 return false; 1298 1299 if (!SecondGEP || FirstGEP->getParent() != SecondGEP->getParent()) 1300 return false; 1301 1302 if (FirstGEP == SecondGEP) 1303 return false; 1304 1305 unsigned FirstNum = FirstGEP->getNumOperands(); 1306 unsigned SecondNum = SecondGEP->getNumOperands(); 1307 // Give up if the number of operands are not 2. 1308 if (FirstNum != SecondNum || FirstNum != 2) 1309 return false; 1310 1311 Value *FirstBase = FirstGEP->getOperand(0); 1312 Value *SecondBase = SecondGEP->getOperand(0); 1313 Value *FirstOffset = FirstGEP->getOperand(1); 1314 // Give up if the index of the first GEP is loop invariant. 1315 if (CurLoop->isLoopInvariant(FirstOffset)) 1316 return false; 1317 1318 // Give up if base doesn't have same type. 1319 if (FirstBase->getType() != SecondBase->getType()) 1320 return false; 1321 1322 Instruction *FirstOffsetDef = dyn_cast<Instruction>(FirstOffset); 1323 1324 // Check if the second operand of first GEP has constant coefficient. 1325 // For an example, for the following code, we won't gain anything by 1326 // hoisting the second GEP out because the second GEP can be folded away. 1327 // %scevgep.sum.ur159 = add i64 %idxprom48.ur, 256 1328 // %67 = shl i64 %scevgep.sum.ur159, 2 1329 // %uglygep160 = getelementptr i8* %65, i64 %67 1330 // %uglygep161 = getelementptr i8* %uglygep160, i64 -1024 1331 1332 // Skip constant shift instruction which may be generated by Splitting GEPs. 1333 if (FirstOffsetDef && FirstOffsetDef->isShift() && 1334 isa<ConstantInt>(FirstOffsetDef->getOperand(1))) 1335 FirstOffsetDef = dyn_cast<Instruction>(FirstOffsetDef->getOperand(0)); 1336 1337 // Give up if FirstOffsetDef is an Add or Sub with constant. 1338 // Because it may not profitable at all due to constant folding. 1339 if (FirstOffsetDef) 1340 if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FirstOffsetDef)) { 1341 unsigned opc = BO->getOpcode(); 1342 if ((opc == Instruction::Add || opc == Instruction::Sub) && 1343 (isa<ConstantInt>(BO->getOperand(0)) || 1344 isa<ConstantInt>(BO->getOperand(1)))) 1345 return false; 1346 } 1347 return true; 1348 } 1349 1350 bool SeparateConstOffsetFromGEP::hasMoreThanOneUseInLoop(Value *V, Loop *L) { 1351 int UsesInLoop = 0; 1352 for (User *U : V->users()) { 1353 if (Instruction *User = dyn_cast<Instruction>(U)) 1354 if (L->contains(User)) 1355 if (++UsesInLoop > 1) 1356 return true; 1357 } 1358 return false; 1359 } 1360 1361 void SeparateConstOffsetFromGEP::swapGEPOperand(GetElementPtrInst *First, 1362 GetElementPtrInst *Second) { 1363 Value *Offset1 = First->getOperand(1); 1364 Value *Offset2 = Second->getOperand(1); 1365 First->setOperand(1, Offset2); 1366 Second->setOperand(1, Offset1); 1367 1368 // We changed p+o+c to p+c+o, p+c may not be inbound anymore. 1369 const DataLayout &DAL = First->getModule()->getDataLayout(); 1370 APInt Offset(DAL.getIndexSizeInBits( 1371 cast<PointerType>(First->getType())->getAddressSpace()), 1372 0); 1373 Value *NewBase = 1374 First->stripAndAccumulateInBoundsConstantOffsets(DAL, Offset); 1375 uint64_t ObjectSize; 1376 if (!getObjectSize(NewBase, ObjectSize, DAL, TLI) || 1377 Offset.ugt(ObjectSize)) { 1378 First->setIsInBounds(false); 1379 Second->setIsInBounds(false); 1380 } else 1381 First->setIsInBounds(true); 1382 } 1383 1384 void SeparateConstOffsetFromGEPPass::printPipeline( 1385 raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) { 1386 static_cast<PassInfoMixin<SeparateConstOffsetFromGEPPass> *>(this) 1387 ->printPipeline(OS, MapClassName2PassName); 1388 OS << '<'; 1389 if (LowerGEP) 1390 OS << "lower-gep"; 1391 OS << '>'; 1392 } 1393 1394 PreservedAnalyses 1395 SeparateConstOffsetFromGEPPass::run(Function &F, FunctionAnalysisManager &AM) { 1396 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F); 1397 auto *LI = &AM.getResult<LoopAnalysis>(F); 1398 auto *TLI = &AM.getResult<TargetLibraryAnalysis>(F); 1399 auto GetTTI = [&AM](Function &F) -> TargetTransformInfo & { 1400 return AM.getResult<TargetIRAnalysis>(F); 1401 }; 1402 SeparateConstOffsetFromGEP Impl(DT, LI, TLI, GetTTI, LowerGEP); 1403 if (!Impl.run(F)) 1404 return PreservedAnalyses::all(); 1405 PreservedAnalyses PA; 1406 PA.preserveSet<CFGAnalyses>(); 1407 return PA; 1408 } 1409