xref: /freebsd/contrib/llvm-project/llvm/lib/Transforms/Scalar/SeparateConstOffsetFromGEP.cpp (revision 1db9f3b21e39176dd5b67cf8ac378633b172463e)
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