1 | //===- AggressiveInstCombine.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 | // This file implements the aggressive expression pattern combiner classes. |
10 | // Currently, it handles expression patterns for: |
11 | // * Truncate instruction |
12 | // |
13 | //===----------------------------------------------------------------------===// |
14 | |
15 | #include "llvm/Transforms/AggressiveInstCombine/AggressiveInstCombine.h" |
16 | #include "AggressiveInstCombineInternal.h" |
17 | #include "llvm/ADT/Statistic.h" |
18 | #include "llvm/Analysis/AliasAnalysis.h" |
19 | #include "llvm/Analysis/AssumptionCache.h" |
20 | #include "llvm/Analysis/BasicAliasAnalysis.h" |
21 | #include "llvm/Analysis/ConstantFolding.h" |
22 | #include "llvm/Analysis/GlobalsModRef.h" |
23 | #include "llvm/Analysis/TargetLibraryInfo.h" |
24 | #include "llvm/Analysis/TargetTransformInfo.h" |
25 | #include "llvm/Analysis/ValueTracking.h" |
26 | #include "llvm/IR/DataLayout.h" |
27 | #include "llvm/IR/Dominators.h" |
28 | #include "llvm/IR/Function.h" |
29 | #include "llvm/IR/IRBuilder.h" |
30 | #include "llvm/IR/PatternMatch.h" |
31 | #include "llvm/Transforms/Utils/BuildLibCalls.h" |
32 | #include "llvm/Transforms/Utils/Local.h" |
33 | |
34 | using namespace llvm; |
35 | using namespace PatternMatch; |
36 | |
37 | #define DEBUG_TYPE "aggressive-instcombine" |
38 | |
39 | STATISTIC(NumAnyOrAllBitsSet, "Number of any/all-bits-set patterns folded" ); |
40 | STATISTIC(NumGuardedRotates, |
41 | "Number of guarded rotates transformed into funnel shifts" ); |
42 | STATISTIC(NumGuardedFunnelShifts, |
43 | "Number of guarded funnel shifts transformed into funnel shifts" ); |
44 | STATISTIC(NumPopCountRecognized, "Number of popcount idioms recognized" ); |
45 | |
46 | static cl::opt<unsigned> MaxInstrsToScan( |
47 | "aggressive-instcombine-max-scan-instrs" , cl::init(Val: 64), cl::Hidden, |
48 | cl::desc("Max number of instructions to scan for aggressive instcombine." )); |
49 | |
50 | /// Match a pattern for a bitwise funnel/rotate operation that partially guards |
51 | /// against undefined behavior by branching around the funnel-shift/rotation |
52 | /// when the shift amount is 0. |
53 | static bool foldGuardedFunnelShift(Instruction &I, const DominatorTree &DT) { |
54 | if (I.getOpcode() != Instruction::PHI || I.getNumOperands() != 2) |
55 | return false; |
56 | |
57 | // As with the one-use checks below, this is not strictly necessary, but we |
58 | // are being cautious to avoid potential perf regressions on targets that |
59 | // do not actually have a funnel/rotate instruction (where the funnel shift |
60 | // would be expanded back into math/shift/logic ops). |
61 | if (!isPowerOf2_32(Value: I.getType()->getScalarSizeInBits())) |
62 | return false; |
63 | |
64 | // Match V to funnel shift left/right and capture the source operands and |
65 | // shift amount. |
66 | auto matchFunnelShift = [](Value *V, Value *&ShVal0, Value *&ShVal1, |
67 | Value *&ShAmt) { |
68 | unsigned Width = V->getType()->getScalarSizeInBits(); |
69 | |
70 | // fshl(ShVal0, ShVal1, ShAmt) |
71 | // == (ShVal0 << ShAmt) | (ShVal1 >> (Width -ShAmt)) |
72 | if (match(V, P: m_OneUse(SubPattern: m_c_Or( |
73 | L: m_Shl(L: m_Value(V&: ShVal0), R: m_Value(V&: ShAmt)), |
74 | R: m_LShr(L: m_Value(V&: ShVal1), |
75 | R: m_Sub(L: m_SpecificInt(V: Width), R: m_Deferred(V: ShAmt))))))) { |
76 | return Intrinsic::fshl; |
77 | } |
78 | |
79 | // fshr(ShVal0, ShVal1, ShAmt) |
80 | // == (ShVal0 >> ShAmt) | (ShVal1 << (Width - ShAmt)) |
81 | if (match(V, |
82 | P: m_OneUse(SubPattern: m_c_Or(L: m_Shl(L: m_Value(V&: ShVal0), R: m_Sub(L: m_SpecificInt(V: Width), |
83 | R: m_Value(V&: ShAmt))), |
84 | R: m_LShr(L: m_Value(V&: ShVal1), R: m_Deferred(V: ShAmt)))))) { |
85 | return Intrinsic::fshr; |
86 | } |
87 | |
88 | return Intrinsic::not_intrinsic; |
89 | }; |
90 | |
91 | // One phi operand must be a funnel/rotate operation, and the other phi |
92 | // operand must be the source value of that funnel/rotate operation: |
93 | // phi [ rotate(RotSrc, ShAmt), FunnelBB ], [ RotSrc, GuardBB ] |
94 | // phi [ fshl(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal0, GuardBB ] |
95 | // phi [ fshr(ShVal0, ShVal1, ShAmt), FunnelBB ], [ ShVal1, GuardBB ] |
96 | PHINode &Phi = cast<PHINode>(Val&: I); |
97 | unsigned FunnelOp = 0, GuardOp = 1; |
98 | Value *P0 = Phi.getOperand(i_nocapture: 0), *P1 = Phi.getOperand(i_nocapture: 1); |
99 | Value *ShVal0, *ShVal1, *ShAmt; |
100 | Intrinsic::ID IID = matchFunnelShift(P0, ShVal0, ShVal1, ShAmt); |
101 | if (IID == Intrinsic::not_intrinsic || |
102 | (IID == Intrinsic::fshl && ShVal0 != P1) || |
103 | (IID == Intrinsic::fshr && ShVal1 != P1)) { |
104 | IID = matchFunnelShift(P1, ShVal0, ShVal1, ShAmt); |
105 | if (IID == Intrinsic::not_intrinsic || |
106 | (IID == Intrinsic::fshl && ShVal0 != P0) || |
107 | (IID == Intrinsic::fshr && ShVal1 != P0)) |
108 | return false; |
109 | assert((IID == Intrinsic::fshl || IID == Intrinsic::fshr) && |
110 | "Pattern must match funnel shift left or right" ); |
111 | std::swap(a&: FunnelOp, b&: GuardOp); |
112 | } |
113 | |
114 | // The incoming block with our source operand must be the "guard" block. |
115 | // That must contain a cmp+branch to avoid the funnel/rotate when the shift |
116 | // amount is equal to 0. The other incoming block is the block with the |
117 | // funnel/rotate. |
118 | BasicBlock *GuardBB = Phi.getIncomingBlock(i: GuardOp); |
119 | BasicBlock *FunnelBB = Phi.getIncomingBlock(i: FunnelOp); |
120 | Instruction *TermI = GuardBB->getTerminator(); |
121 | |
122 | // Ensure that the shift values dominate each block. |
123 | if (!DT.dominates(Def: ShVal0, User: TermI) || !DT.dominates(Def: ShVal1, User: TermI)) |
124 | return false; |
125 | |
126 | ICmpInst::Predicate Pred; |
127 | BasicBlock *PhiBB = Phi.getParent(); |
128 | if (!match(V: TermI, P: m_Br(C: m_ICmp(Pred, L: m_Specific(V: ShAmt), R: m_ZeroInt()), |
129 | T: m_SpecificBB(BB: PhiBB), F: m_SpecificBB(BB: FunnelBB)))) |
130 | return false; |
131 | |
132 | if (Pred != CmpInst::ICMP_EQ) |
133 | return false; |
134 | |
135 | IRBuilder<> Builder(PhiBB, PhiBB->getFirstInsertionPt()); |
136 | |
137 | if (ShVal0 == ShVal1) |
138 | ++NumGuardedRotates; |
139 | else |
140 | ++NumGuardedFunnelShifts; |
141 | |
142 | // If this is not a rotate then the select was blocking poison from the |
143 | // 'shift-by-zero' non-TVal, but a funnel shift won't - so freeze it. |
144 | bool IsFshl = IID == Intrinsic::fshl; |
145 | if (ShVal0 != ShVal1) { |
146 | if (IsFshl && !llvm::isGuaranteedNotToBePoison(V: ShVal1)) |
147 | ShVal1 = Builder.CreateFreeze(V: ShVal1); |
148 | else if (!IsFshl && !llvm::isGuaranteedNotToBePoison(V: ShVal0)) |
149 | ShVal0 = Builder.CreateFreeze(V: ShVal0); |
150 | } |
151 | |
152 | // We matched a variation of this IR pattern: |
153 | // GuardBB: |
154 | // %cmp = icmp eq i32 %ShAmt, 0 |
155 | // br i1 %cmp, label %PhiBB, label %FunnelBB |
156 | // FunnelBB: |
157 | // %sub = sub i32 32, %ShAmt |
158 | // %shr = lshr i32 %ShVal1, %sub |
159 | // %shl = shl i32 %ShVal0, %ShAmt |
160 | // %fsh = or i32 %shr, %shl |
161 | // br label %PhiBB |
162 | // PhiBB: |
163 | // %cond = phi i32 [ %fsh, %FunnelBB ], [ %ShVal0, %GuardBB ] |
164 | // --> |
165 | // llvm.fshl.i32(i32 %ShVal0, i32 %ShVal1, i32 %ShAmt) |
166 | Function *F = Intrinsic::getDeclaration(M: Phi.getModule(), id: IID, Tys: Phi.getType()); |
167 | Phi.replaceAllUsesWith(V: Builder.CreateCall(Callee: F, Args: {ShVal0, ShVal1, ShAmt})); |
168 | return true; |
169 | } |
170 | |
171 | /// This is used by foldAnyOrAllBitsSet() to capture a source value (Root) and |
172 | /// the bit indexes (Mask) needed by a masked compare. If we're matching a chain |
173 | /// of 'and' ops, then we also need to capture the fact that we saw an |
174 | /// "and X, 1", so that's an extra return value for that case. |
175 | struct MaskOps { |
176 | Value *Root = nullptr; |
177 | APInt Mask; |
178 | bool MatchAndChain; |
179 | bool FoundAnd1 = false; |
180 | |
181 | MaskOps(unsigned BitWidth, bool MatchAnds) |
182 | : Mask(APInt::getZero(numBits: BitWidth)), MatchAndChain(MatchAnds) {} |
183 | }; |
184 | |
185 | /// This is a recursive helper for foldAnyOrAllBitsSet() that walks through a |
186 | /// chain of 'and' or 'or' instructions looking for shift ops of a common source |
187 | /// value. Examples: |
188 | /// or (or (or X, (X >> 3)), (X >> 5)), (X >> 8) |
189 | /// returns { X, 0x129 } |
190 | /// and (and (X >> 1), 1), (X >> 4) |
191 | /// returns { X, 0x12 } |
192 | static bool matchAndOrChain(Value *V, MaskOps &MOps) { |
193 | Value *Op0, *Op1; |
194 | if (MOps.MatchAndChain) { |
195 | // Recurse through a chain of 'and' operands. This requires an extra check |
196 | // vs. the 'or' matcher: we must find an "and X, 1" instruction somewhere |
197 | // in the chain to know that all of the high bits are cleared. |
198 | if (match(V, P: m_And(L: m_Value(V&: Op0), R: m_One()))) { |
199 | MOps.FoundAnd1 = true; |
200 | return matchAndOrChain(V: Op0, MOps); |
201 | } |
202 | if (match(V, P: m_And(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) |
203 | return matchAndOrChain(V: Op0, MOps) && matchAndOrChain(V: Op1, MOps); |
204 | } else { |
205 | // Recurse through a chain of 'or' operands. |
206 | if (match(V, P: m_Or(L: m_Value(V&: Op0), R: m_Value(V&: Op1)))) |
207 | return matchAndOrChain(V: Op0, MOps) && matchAndOrChain(V: Op1, MOps); |
208 | } |
209 | |
210 | // We need a shift-right or a bare value representing a compare of bit 0 of |
211 | // the original source operand. |
212 | Value *Candidate; |
213 | const APInt *BitIndex = nullptr; |
214 | if (!match(V, P: m_LShr(L: m_Value(V&: Candidate), R: m_APInt(Res&: BitIndex)))) |
215 | Candidate = V; |
216 | |
217 | // Initialize result source operand. |
218 | if (!MOps.Root) |
219 | MOps.Root = Candidate; |
220 | |
221 | // The shift constant is out-of-range? This code hasn't been simplified. |
222 | if (BitIndex && BitIndex->uge(RHS: MOps.Mask.getBitWidth())) |
223 | return false; |
224 | |
225 | // Fill in the mask bit derived from the shift constant. |
226 | MOps.Mask.setBit(BitIndex ? BitIndex->getZExtValue() : 0); |
227 | return MOps.Root == Candidate; |
228 | } |
229 | |
230 | /// Match patterns that correspond to "any-bits-set" and "all-bits-set". |
231 | /// These will include a chain of 'or' or 'and'-shifted bits from a |
232 | /// common source value: |
233 | /// and (or (lshr X, C), ...), 1 --> (X & CMask) != 0 |
234 | /// and (and (lshr X, C), ...), 1 --> (X & CMask) == CMask |
235 | /// Note: "any-bits-clear" and "all-bits-clear" are variations of these patterns |
236 | /// that differ only with a final 'not' of the result. We expect that final |
237 | /// 'not' to be folded with the compare that we create here (invert predicate). |
238 | static bool foldAnyOrAllBitsSet(Instruction &I) { |
239 | // The 'any-bits-set' ('or' chain) pattern is simpler to match because the |
240 | // final "and X, 1" instruction must be the final op in the sequence. |
241 | bool MatchAllBitsSet; |
242 | if (match(V: &I, P: m_c_And(L: m_OneUse(SubPattern: m_And(L: m_Value(), R: m_Value())), R: m_Value()))) |
243 | MatchAllBitsSet = true; |
244 | else if (match(V: &I, P: m_And(L: m_OneUse(SubPattern: m_Or(L: m_Value(), R: m_Value())), R: m_One()))) |
245 | MatchAllBitsSet = false; |
246 | else |
247 | return false; |
248 | |
249 | MaskOps MOps(I.getType()->getScalarSizeInBits(), MatchAllBitsSet); |
250 | if (MatchAllBitsSet) { |
251 | if (!matchAndOrChain(V: cast<BinaryOperator>(Val: &I), MOps) || !MOps.FoundAnd1) |
252 | return false; |
253 | } else { |
254 | if (!matchAndOrChain(V: cast<BinaryOperator>(Val: &I)->getOperand(i_nocapture: 0), MOps)) |
255 | return false; |
256 | } |
257 | |
258 | // The pattern was found. Create a masked compare that replaces all of the |
259 | // shift and logic ops. |
260 | IRBuilder<> Builder(&I); |
261 | Constant *Mask = ConstantInt::get(Ty: I.getType(), V: MOps.Mask); |
262 | Value *And = Builder.CreateAnd(LHS: MOps.Root, RHS: Mask); |
263 | Value *Cmp = MatchAllBitsSet ? Builder.CreateICmpEQ(LHS: And, RHS: Mask) |
264 | : Builder.CreateIsNotNull(Arg: And); |
265 | Value *Zext = Builder.CreateZExt(V: Cmp, DestTy: I.getType()); |
266 | I.replaceAllUsesWith(V: Zext); |
267 | ++NumAnyOrAllBitsSet; |
268 | return true; |
269 | } |
270 | |
271 | // Try to recognize below function as popcount intrinsic. |
272 | // This is the "best" algorithm from |
273 | // http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel |
274 | // Also used in TargetLowering::expandCTPOP(). |
275 | // |
276 | // int popcount(unsigned int i) { |
277 | // i = i - ((i >> 1) & 0x55555555); |
278 | // i = (i & 0x33333333) + ((i >> 2) & 0x33333333); |
279 | // i = ((i + (i >> 4)) & 0x0F0F0F0F); |
280 | // return (i * 0x01010101) >> 24; |
281 | // } |
282 | static bool tryToRecognizePopCount(Instruction &I) { |
283 | if (I.getOpcode() != Instruction::LShr) |
284 | return false; |
285 | |
286 | Type *Ty = I.getType(); |
287 | if (!Ty->isIntOrIntVectorTy()) |
288 | return false; |
289 | |
290 | unsigned Len = Ty->getScalarSizeInBits(); |
291 | // FIXME: fix Len == 8 and other irregular type lengths. |
292 | if (!(Len <= 128 && Len > 8 && Len % 8 == 0)) |
293 | return false; |
294 | |
295 | APInt Mask55 = APInt::getSplat(NewLen: Len, V: APInt(8, 0x55)); |
296 | APInt Mask33 = APInt::getSplat(NewLen: Len, V: APInt(8, 0x33)); |
297 | APInt Mask0F = APInt::getSplat(NewLen: Len, V: APInt(8, 0x0F)); |
298 | APInt Mask01 = APInt::getSplat(NewLen: Len, V: APInt(8, 0x01)); |
299 | APInt MaskShift = APInt(Len, Len - 8); |
300 | |
301 | Value *Op0 = I.getOperand(i: 0); |
302 | Value *Op1 = I.getOperand(i: 1); |
303 | Value *MulOp0; |
304 | // Matching "(i * 0x01010101...) >> 24". |
305 | if ((match(V: Op0, P: m_Mul(L: m_Value(V&: MulOp0), R: m_SpecificInt(V: Mask01)))) && |
306 | match(V: Op1, P: m_SpecificInt(V: MaskShift))) { |
307 | Value *ShiftOp0; |
308 | // Matching "((i + (i >> 4)) & 0x0F0F0F0F...)". |
309 | if (match(V: MulOp0, P: m_And(L: m_c_Add(L: m_LShr(L: m_Value(V&: ShiftOp0), R: m_SpecificInt(V: 4)), |
310 | R: m_Deferred(V: ShiftOp0)), |
311 | R: m_SpecificInt(V: Mask0F)))) { |
312 | Value *AndOp0; |
313 | // Matching "(i & 0x33333333...) + ((i >> 2) & 0x33333333...)". |
314 | if (match(V: ShiftOp0, |
315 | P: m_c_Add(L: m_And(L: m_Value(V&: AndOp0), R: m_SpecificInt(V: Mask33)), |
316 | R: m_And(L: m_LShr(L: m_Deferred(V: AndOp0), R: m_SpecificInt(V: 2)), |
317 | R: m_SpecificInt(V: Mask33))))) { |
318 | Value *Root, *SubOp1; |
319 | // Matching "i - ((i >> 1) & 0x55555555...)". |
320 | if (match(V: AndOp0, P: m_Sub(L: m_Value(V&: Root), R: m_Value(V&: SubOp1))) && |
321 | match(V: SubOp1, P: m_And(L: m_LShr(L: m_Specific(V: Root), R: m_SpecificInt(V: 1)), |
322 | R: m_SpecificInt(V: Mask55)))) { |
323 | LLVM_DEBUG(dbgs() << "Recognized popcount intrinsic\n" ); |
324 | IRBuilder<> Builder(&I); |
325 | Function *Func = Intrinsic::getDeclaration( |
326 | M: I.getModule(), Intrinsic::id: ctpop, Tys: I.getType()); |
327 | I.replaceAllUsesWith(V: Builder.CreateCall(Callee: Func, Args: {Root})); |
328 | ++NumPopCountRecognized; |
329 | return true; |
330 | } |
331 | } |
332 | } |
333 | } |
334 | |
335 | return false; |
336 | } |
337 | |
338 | /// Fold smin(smax(fptosi(x), C1), C2) to llvm.fptosi.sat(x), providing C1 and |
339 | /// C2 saturate the value of the fp conversion. The transform is not reversable |
340 | /// as the fptosi.sat is more defined than the input - all values produce a |
341 | /// valid value for the fptosi.sat, where as some produce poison for original |
342 | /// that were out of range of the integer conversion. The reversed pattern may |
343 | /// use fmax and fmin instead. As we cannot directly reverse the transform, and |
344 | /// it is not always profitable, we make it conditional on the cost being |
345 | /// reported as lower by TTI. |
346 | static bool tryToFPToSat(Instruction &I, TargetTransformInfo &TTI) { |
347 | // Look for min(max(fptosi, converting to fptosi_sat. |
348 | Value *In; |
349 | const APInt *MinC, *MaxC; |
350 | if (!match(V: &I, P: m_SMax(L: m_OneUse(SubPattern: m_SMin(L: m_OneUse(SubPattern: m_FPToSI(Op: m_Value(V&: In))), |
351 | R: m_APInt(Res&: MinC))), |
352 | R: m_APInt(Res&: MaxC))) && |
353 | !match(V: &I, P: m_SMin(L: m_OneUse(SubPattern: m_SMax(L: m_OneUse(SubPattern: m_FPToSI(Op: m_Value(V&: In))), |
354 | R: m_APInt(Res&: MaxC))), |
355 | R: m_APInt(Res&: MinC)))) |
356 | return false; |
357 | |
358 | // Check that the constants clamp a saturate. |
359 | if (!(*MinC + 1).isPowerOf2() || -*MaxC != *MinC + 1) |
360 | return false; |
361 | |
362 | Type *IntTy = I.getType(); |
363 | Type *FpTy = In->getType(); |
364 | Type *SatTy = |
365 | IntegerType::get(C&: IntTy->getContext(), NumBits: (*MinC + 1).exactLogBase2() + 1); |
366 | if (auto *VecTy = dyn_cast<VectorType>(Val: IntTy)) |
367 | SatTy = VectorType::get(ElementType: SatTy, EC: VecTy->getElementCount()); |
368 | |
369 | // Get the cost of the intrinsic, and check that against the cost of |
370 | // fptosi+smin+smax |
371 | InstructionCost SatCost = TTI.getIntrinsicInstrCost( |
372 | IntrinsicCostAttributes(Intrinsic::fptosi_sat, SatTy, {In}, {FpTy}), |
373 | TTI::TCK_RecipThroughput); |
374 | SatCost += TTI.getCastInstrCost(Opcode: Instruction::SExt, Dst: IntTy, Src: SatTy, |
375 | CCH: TTI::CastContextHint::None, |
376 | CostKind: TTI::TCK_RecipThroughput); |
377 | |
378 | InstructionCost MinMaxCost = TTI.getCastInstrCost( |
379 | Opcode: Instruction::FPToSI, Dst: IntTy, Src: FpTy, CCH: TTI::CastContextHint::None, |
380 | CostKind: TTI::TCK_RecipThroughput); |
381 | MinMaxCost += TTI.getIntrinsicInstrCost( |
382 | IntrinsicCostAttributes(Intrinsic::smin, IntTy, {IntTy}), |
383 | TTI::TCK_RecipThroughput); |
384 | MinMaxCost += TTI.getIntrinsicInstrCost( |
385 | IntrinsicCostAttributes(Intrinsic::smax, IntTy, {IntTy}), |
386 | TTI::TCK_RecipThroughput); |
387 | |
388 | if (SatCost >= MinMaxCost) |
389 | return false; |
390 | |
391 | IRBuilder<> Builder(&I); |
392 | Function *Fn = Intrinsic::getDeclaration(M: I.getModule(), Intrinsic::id: fptosi_sat, |
393 | Tys: {SatTy, FpTy}); |
394 | Value *Sat = Builder.CreateCall(Callee: Fn, Args: In); |
395 | I.replaceAllUsesWith(V: Builder.CreateSExt(V: Sat, DestTy: IntTy)); |
396 | return true; |
397 | } |
398 | |
399 | /// Try to replace a mathlib call to sqrt with the LLVM intrinsic. This avoids |
400 | /// pessimistic codegen that has to account for setting errno and can enable |
401 | /// vectorization. |
402 | static bool foldSqrt(Instruction &I, TargetTransformInfo &TTI, |
403 | TargetLibraryInfo &TLI, AssumptionCache &AC, |
404 | DominatorTree &DT) { |
405 | // Match a call to sqrt mathlib function. |
406 | auto *Call = dyn_cast<CallInst>(Val: &I); |
407 | if (!Call) |
408 | return false; |
409 | |
410 | Module *M = Call->getModule(); |
411 | LibFunc Func; |
412 | if (!TLI.getLibFunc(CB: *Call, F&: Func) || !isLibFuncEmittable(M, TLI: &TLI, TheLibFunc: Func)) |
413 | return false; |
414 | |
415 | if (Func != LibFunc_sqrt && Func != LibFunc_sqrtf && Func != LibFunc_sqrtl) |
416 | return false; |
417 | |
418 | // If (1) this is a sqrt libcall, (2) we can assume that NAN is not created |
419 | // (because NNAN or the operand arg must not be less than -0.0) and (2) we |
420 | // would not end up lowering to a libcall anyway (which could change the value |
421 | // of errno), then: |
422 | // (1) errno won't be set. |
423 | // (2) it is safe to convert this to an intrinsic call. |
424 | Type *Ty = Call->getType(); |
425 | Value *Arg = Call->getArgOperand(i: 0); |
426 | if (TTI.haveFastSqrt(Ty) && |
427 | (Call->hasNoNaNs() || |
428 | cannotBeOrderedLessThanZero( |
429 | V: Arg, Depth: 0, SQ: SimplifyQuery(M->getDataLayout(), &TLI, &DT, &AC, &I)))) { |
430 | IRBuilder<> Builder(&I); |
431 | IRBuilderBase::FastMathFlagGuard Guard(Builder); |
432 | Builder.setFastMathFlags(Call->getFastMathFlags()); |
433 | |
434 | Function *Sqrt = Intrinsic::getDeclaration(M, Intrinsic::id: sqrt, Tys: Ty); |
435 | Value *NewSqrt = Builder.CreateCall(Callee: Sqrt, Args: Arg, Name: "sqrt" ); |
436 | I.replaceAllUsesWith(V: NewSqrt); |
437 | |
438 | // Explicitly erase the old call because a call with side effects is not |
439 | // trivially dead. |
440 | I.eraseFromParent(); |
441 | return true; |
442 | } |
443 | |
444 | return false; |
445 | } |
446 | |
447 | // Check if this array of constants represents a cttz table. |
448 | // Iterate over the elements from \p Table by trying to find/match all |
449 | // the numbers from 0 to \p InputBits that should represent cttz results. |
450 | static bool isCTTZTable(const ConstantDataArray &Table, uint64_t Mul, |
451 | uint64_t Shift, uint64_t InputBits) { |
452 | unsigned Length = Table.getNumElements(); |
453 | if (Length < InputBits || Length > InputBits * 2) |
454 | return false; |
455 | |
456 | APInt Mask = APInt::getBitsSetFrom(numBits: InputBits, loBit: Shift); |
457 | unsigned Matched = 0; |
458 | |
459 | for (unsigned i = 0; i < Length; i++) { |
460 | uint64_t Element = Table.getElementAsInteger(i); |
461 | if (Element >= InputBits) |
462 | continue; |
463 | |
464 | // Check if \p Element matches a concrete answer. It could fail for some |
465 | // elements that are never accessed, so we keep iterating over each element |
466 | // from the table. The number of matched elements should be equal to the |
467 | // number of potential right answers which is \p InputBits actually. |
468 | if ((((Mul << Element) & Mask.getZExtValue()) >> Shift) == i) |
469 | Matched++; |
470 | } |
471 | |
472 | return Matched == InputBits; |
473 | } |
474 | |
475 | // Try to recognize table-based ctz implementation. |
476 | // E.g., an example in C (for more cases please see the llvm/tests): |
477 | // int f(unsigned x) { |
478 | // static const char table[32] = |
479 | // {0, 1, 28, 2, 29, 14, 24, 3, 30, |
480 | // 22, 20, 15, 25, 17, 4, 8, 31, 27, |
481 | // 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9}; |
482 | // return table[((unsigned)((x & -x) * 0x077CB531U)) >> 27]; |
483 | // } |
484 | // this can be lowered to `cttz` instruction. |
485 | // There is also a special case when the element is 0. |
486 | // |
487 | // Here are some examples or LLVM IR for a 64-bit target: |
488 | // |
489 | // CASE 1: |
490 | // %sub = sub i32 0, %x |
491 | // %and = and i32 %sub, %x |
492 | // %mul = mul i32 %and, 125613361 |
493 | // %shr = lshr i32 %mul, 27 |
494 | // %idxprom = zext i32 %shr to i64 |
495 | // %arrayidx = getelementptr inbounds [32 x i8], [32 x i8]* @ctz1.table, i64 0, |
496 | // i64 %idxprom |
497 | // %0 = load i8, i8* %arrayidx, align 1, !tbaa !8 |
498 | // |
499 | // CASE 2: |
500 | // %sub = sub i32 0, %x |
501 | // %and = and i32 %sub, %x |
502 | // %mul = mul i32 %and, 72416175 |
503 | // %shr = lshr i32 %mul, 26 |
504 | // %idxprom = zext i32 %shr to i64 |
505 | // %arrayidx = getelementptr inbounds [64 x i16], [64 x i16]* @ctz2.table, |
506 | // i64 0, i64 %idxprom |
507 | // %0 = load i16, i16* %arrayidx, align 2, !tbaa !8 |
508 | // |
509 | // CASE 3: |
510 | // %sub = sub i32 0, %x |
511 | // %and = and i32 %sub, %x |
512 | // %mul = mul i32 %and, 81224991 |
513 | // %shr = lshr i32 %mul, 27 |
514 | // %idxprom = zext i32 %shr to i64 |
515 | // %arrayidx = getelementptr inbounds [32 x i32], [32 x i32]* @ctz3.table, |
516 | // i64 0, i64 %idxprom |
517 | // %0 = load i32, i32* %arrayidx, align 4, !tbaa !8 |
518 | // |
519 | // CASE 4: |
520 | // %sub = sub i64 0, %x |
521 | // %and = and i64 %sub, %x |
522 | // %mul = mul i64 %and, 283881067100198605 |
523 | // %shr = lshr i64 %mul, 58 |
524 | // %arrayidx = getelementptr inbounds [64 x i8], [64 x i8]* @table, i64 0, |
525 | // i64 %shr |
526 | // %0 = load i8, i8* %arrayidx, align 1, !tbaa !8 |
527 | // |
528 | // All this can be lowered to @llvm.cttz.i32/64 intrinsic. |
529 | static bool tryToRecognizeTableBasedCttz(Instruction &I) { |
530 | LoadInst *LI = dyn_cast<LoadInst>(Val: &I); |
531 | if (!LI) |
532 | return false; |
533 | |
534 | Type *AccessType = LI->getType(); |
535 | if (!AccessType->isIntegerTy()) |
536 | return false; |
537 | |
538 | GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Val: LI->getPointerOperand()); |
539 | if (!GEP || !GEP->isInBounds() || GEP->getNumIndices() != 2) |
540 | return false; |
541 | |
542 | if (!GEP->getSourceElementType()->isArrayTy()) |
543 | return false; |
544 | |
545 | uint64_t ArraySize = GEP->getSourceElementType()->getArrayNumElements(); |
546 | if (ArraySize != 32 && ArraySize != 64) |
547 | return false; |
548 | |
549 | GlobalVariable *GVTable = dyn_cast<GlobalVariable>(Val: GEP->getPointerOperand()); |
550 | if (!GVTable || !GVTable->hasInitializer() || !GVTable->isConstant()) |
551 | return false; |
552 | |
553 | ConstantDataArray *ConstData = |
554 | dyn_cast<ConstantDataArray>(Val: GVTable->getInitializer()); |
555 | if (!ConstData) |
556 | return false; |
557 | |
558 | if (!match(V: GEP->idx_begin()->get(), P: m_ZeroInt())) |
559 | return false; |
560 | |
561 | Value *Idx2 = std::next(x: GEP->idx_begin())->get(); |
562 | Value *X1; |
563 | uint64_t MulConst, ShiftConst; |
564 | // FIXME: 64-bit targets have `i64` type for the GEP index, so this match will |
565 | // probably fail for other (e.g. 32-bit) targets. |
566 | if (!match(V: Idx2, P: m_ZExtOrSelf( |
567 | Op: m_LShr(L: m_Mul(L: m_c_And(L: m_Neg(V: m_Value(V&: X1)), R: m_Deferred(V: X1)), |
568 | R: m_ConstantInt(V&: MulConst)), |
569 | R: m_ConstantInt(V&: ShiftConst))))) |
570 | return false; |
571 | |
572 | unsigned InputBits = X1->getType()->getScalarSizeInBits(); |
573 | if (InputBits != 32 && InputBits != 64) |
574 | return false; |
575 | |
576 | // Shift should extract top 5..7 bits. |
577 | if (InputBits - Log2_32(Value: InputBits) != ShiftConst && |
578 | InputBits - Log2_32(Value: InputBits) - 1 != ShiftConst) |
579 | return false; |
580 | |
581 | if (!isCTTZTable(Table: *ConstData, Mul: MulConst, Shift: ShiftConst, InputBits)) |
582 | return false; |
583 | |
584 | auto ZeroTableElem = ConstData->getElementAsInteger(i: 0); |
585 | bool DefinedForZero = ZeroTableElem == InputBits; |
586 | |
587 | IRBuilder<> B(LI); |
588 | ConstantInt *BoolConst = B.getInt1(V: !DefinedForZero); |
589 | Type *XType = X1->getType(); |
590 | auto Cttz = B.CreateIntrinsic(Intrinsic::cttz, {XType}, {X1, BoolConst}); |
591 | Value *ZExtOrTrunc = nullptr; |
592 | |
593 | if (DefinedForZero) { |
594 | ZExtOrTrunc = B.CreateZExtOrTrunc(V: Cttz, DestTy: AccessType); |
595 | } else { |
596 | // If the value in elem 0 isn't the same as InputBits, we still want to |
597 | // produce the value from the table. |
598 | auto Cmp = B.CreateICmpEQ(LHS: X1, RHS: ConstantInt::get(Ty: XType, V: 0)); |
599 | auto Select = |
600 | B.CreateSelect(C: Cmp, True: ConstantInt::get(Ty: XType, V: ZeroTableElem), False: Cttz); |
601 | |
602 | // NOTE: If the table[0] is 0, but the cttz(0) is defined by the Target |
603 | // it should be handled as: `cttz(x) & (typeSize - 1)`. |
604 | |
605 | ZExtOrTrunc = B.CreateZExtOrTrunc(V: Select, DestTy: AccessType); |
606 | } |
607 | |
608 | LI->replaceAllUsesWith(V: ZExtOrTrunc); |
609 | |
610 | return true; |
611 | } |
612 | |
613 | /// This is used by foldLoadsRecursive() to capture a Root Load node which is |
614 | /// of type or(load, load) and recursively build the wide load. Also capture the |
615 | /// shift amount, zero extend type and loadSize. |
616 | struct LoadOps { |
617 | LoadInst *Root = nullptr; |
618 | LoadInst *RootInsert = nullptr; |
619 | bool FoundRoot = false; |
620 | uint64_t LoadSize = 0; |
621 | const APInt *Shift = nullptr; |
622 | Type *ZextType; |
623 | AAMDNodes AATags; |
624 | }; |
625 | |
626 | // Identify and Merge consecutive loads recursively which is of the form |
627 | // (ZExt(L1) << shift1) | (ZExt(L2) << shift2) -> ZExt(L3) << shift1 |
628 | // (ZExt(L1) << shift1) | ZExt(L2) -> ZExt(L3) |
629 | static bool foldLoadsRecursive(Value *V, LoadOps &LOps, const DataLayout &DL, |
630 | AliasAnalysis &AA) { |
631 | const APInt *ShAmt2 = nullptr; |
632 | Value *X; |
633 | Instruction *L1, *L2; |
634 | |
635 | // Go to the last node with loads. |
636 | if (match(V, P: m_OneUse(SubPattern: m_c_Or( |
637 | L: m_Value(V&: X), |
638 | R: m_OneUse(SubPattern: m_Shl(L: m_OneUse(SubPattern: m_ZExt(Op: m_OneUse(SubPattern: m_Instruction(I&: L2)))), |
639 | R: m_APInt(Res&: ShAmt2)))))) || |
640 | match(V, P: m_OneUse(SubPattern: m_Or(L: m_Value(V&: X), |
641 | R: m_OneUse(SubPattern: m_ZExt(Op: m_OneUse(SubPattern: m_Instruction(I&: L2)))))))) { |
642 | if (!foldLoadsRecursive(V: X, LOps, DL, AA) && LOps.FoundRoot) |
643 | // Avoid Partial chain merge. |
644 | return false; |
645 | } else |
646 | return false; |
647 | |
648 | // Check if the pattern has loads |
649 | LoadInst *LI1 = LOps.Root; |
650 | const APInt *ShAmt1 = LOps.Shift; |
651 | if (LOps.FoundRoot == false && |
652 | (match(V: X, P: m_OneUse(SubPattern: m_ZExt(Op: m_Instruction(I&: L1)))) || |
653 | match(V: X, P: m_OneUse(SubPattern: m_Shl(L: m_OneUse(SubPattern: m_ZExt(Op: m_OneUse(SubPattern: m_Instruction(I&: L1)))), |
654 | R: m_APInt(Res&: ShAmt1)))))) { |
655 | LI1 = dyn_cast<LoadInst>(Val: L1); |
656 | } |
657 | LoadInst *LI2 = dyn_cast<LoadInst>(Val: L2); |
658 | |
659 | // Check if loads are same, atomic, volatile and having same address space. |
660 | if (LI1 == LI2 || !LI1 || !LI2 || !LI1->isSimple() || !LI2->isSimple() || |
661 | LI1->getPointerAddressSpace() != LI2->getPointerAddressSpace()) |
662 | return false; |
663 | |
664 | // Check if Loads come from same BB. |
665 | if (LI1->getParent() != LI2->getParent()) |
666 | return false; |
667 | |
668 | // Find the data layout |
669 | bool IsBigEndian = DL.isBigEndian(); |
670 | |
671 | // Check if loads are consecutive and same size. |
672 | Value *Load1Ptr = LI1->getPointerOperand(); |
673 | APInt Offset1(DL.getIndexTypeSizeInBits(Ty: Load1Ptr->getType()), 0); |
674 | Load1Ptr = |
675 | Load1Ptr->stripAndAccumulateConstantOffsets(DL, Offset&: Offset1, |
676 | /* AllowNonInbounds */ true); |
677 | |
678 | Value *Load2Ptr = LI2->getPointerOperand(); |
679 | APInt Offset2(DL.getIndexTypeSizeInBits(Ty: Load2Ptr->getType()), 0); |
680 | Load2Ptr = |
681 | Load2Ptr->stripAndAccumulateConstantOffsets(DL, Offset&: Offset2, |
682 | /* AllowNonInbounds */ true); |
683 | |
684 | // Verify if both loads have same base pointers and load sizes are same. |
685 | uint64_t LoadSize1 = LI1->getType()->getPrimitiveSizeInBits(); |
686 | uint64_t LoadSize2 = LI2->getType()->getPrimitiveSizeInBits(); |
687 | if (Load1Ptr != Load2Ptr || LoadSize1 != LoadSize2) |
688 | return false; |
689 | |
690 | // Support Loadsizes greater or equal to 8bits and only power of 2. |
691 | if (LoadSize1 < 8 || !isPowerOf2_64(Value: LoadSize1)) |
692 | return false; |
693 | |
694 | // Alias Analysis to check for stores b/w the loads. |
695 | LoadInst *Start = LOps.FoundRoot ? LOps.RootInsert : LI1, *End = LI2; |
696 | MemoryLocation Loc; |
697 | if (!Start->comesBefore(Other: End)) { |
698 | std::swap(a&: Start, b&: End); |
699 | Loc = MemoryLocation::get(LI: End); |
700 | if (LOps.FoundRoot) |
701 | Loc = Loc.getWithNewSize(NewSize: LOps.LoadSize); |
702 | } else |
703 | Loc = MemoryLocation::get(LI: End); |
704 | unsigned NumScanned = 0; |
705 | for (Instruction &Inst : |
706 | make_range(x: Start->getIterator(), y: End->getIterator())) { |
707 | if (Inst.mayWriteToMemory() && isModSet(MRI: AA.getModRefInfo(I: &Inst, OptLoc: Loc))) |
708 | return false; |
709 | |
710 | // Ignore debug info so that's not counted against MaxInstrsToScan. |
711 | // Otherwise debug info could affect codegen. |
712 | if (!isa<DbgInfoIntrinsic>(Val: Inst) && ++NumScanned > MaxInstrsToScan) |
713 | return false; |
714 | } |
715 | |
716 | // Make sure Load with lower Offset is at LI1 |
717 | bool Reverse = false; |
718 | if (Offset2.slt(RHS: Offset1)) { |
719 | std::swap(a&: LI1, b&: LI2); |
720 | std::swap(a&: ShAmt1, b&: ShAmt2); |
721 | std::swap(a&: Offset1, b&: Offset2); |
722 | std::swap(a&: Load1Ptr, b&: Load2Ptr); |
723 | std::swap(a&: LoadSize1, b&: LoadSize2); |
724 | Reverse = true; |
725 | } |
726 | |
727 | // Big endian swap the shifts |
728 | if (IsBigEndian) |
729 | std::swap(a&: ShAmt1, b&: ShAmt2); |
730 | |
731 | // Find Shifts values. |
732 | uint64_t Shift1 = 0, Shift2 = 0; |
733 | if (ShAmt1) |
734 | Shift1 = ShAmt1->getZExtValue(); |
735 | if (ShAmt2) |
736 | Shift2 = ShAmt2->getZExtValue(); |
737 | |
738 | // First load is always LI1. This is where we put the new load. |
739 | // Use the merged load size available from LI1 for forward loads. |
740 | if (LOps.FoundRoot) { |
741 | if (!Reverse) |
742 | LoadSize1 = LOps.LoadSize; |
743 | else |
744 | LoadSize2 = LOps.LoadSize; |
745 | } |
746 | |
747 | // Verify if shift amount and load index aligns and verifies that loads |
748 | // are consecutive. |
749 | uint64_t ShiftDiff = IsBigEndian ? LoadSize2 : LoadSize1; |
750 | uint64_t PrevSize = |
751 | DL.getTypeStoreSize(Ty: IntegerType::get(C&: LI1->getContext(), NumBits: LoadSize1)); |
752 | if ((Shift2 - Shift1) != ShiftDiff || (Offset2 - Offset1) != PrevSize) |
753 | return false; |
754 | |
755 | // Update LOps |
756 | AAMDNodes AATags1 = LOps.AATags; |
757 | AAMDNodes AATags2 = LI2->getAAMetadata(); |
758 | if (LOps.FoundRoot == false) { |
759 | LOps.FoundRoot = true; |
760 | AATags1 = LI1->getAAMetadata(); |
761 | } |
762 | LOps.LoadSize = LoadSize1 + LoadSize2; |
763 | LOps.RootInsert = Start; |
764 | |
765 | // Concatenate the AATags of the Merged Loads. |
766 | LOps.AATags = AATags1.concat(Other: AATags2); |
767 | |
768 | LOps.Root = LI1; |
769 | LOps.Shift = ShAmt1; |
770 | LOps.ZextType = X->getType(); |
771 | return true; |
772 | } |
773 | |
774 | // For a given BB instruction, evaluate all loads in the chain that form a |
775 | // pattern which suggests that the loads can be combined. The one and only use |
776 | // of the loads is to form a wider load. |
777 | static bool foldConsecutiveLoads(Instruction &I, const DataLayout &DL, |
778 | TargetTransformInfo &TTI, AliasAnalysis &AA, |
779 | const DominatorTree &DT) { |
780 | // Only consider load chains of scalar values. |
781 | if (isa<VectorType>(Val: I.getType())) |
782 | return false; |
783 | |
784 | LoadOps LOps; |
785 | if (!foldLoadsRecursive(V: &I, LOps, DL, AA) || !LOps.FoundRoot) |
786 | return false; |
787 | |
788 | IRBuilder<> Builder(&I); |
789 | LoadInst *NewLoad = nullptr, *LI1 = LOps.Root; |
790 | |
791 | IntegerType *WiderType = IntegerType::get(C&: I.getContext(), NumBits: LOps.LoadSize); |
792 | // TTI based checks if we want to proceed with wider load |
793 | bool Allowed = TTI.isTypeLegal(Ty: WiderType); |
794 | if (!Allowed) |
795 | return false; |
796 | |
797 | unsigned AS = LI1->getPointerAddressSpace(); |
798 | unsigned Fast = 0; |
799 | Allowed = TTI.allowsMisalignedMemoryAccesses(Context&: I.getContext(), BitWidth: LOps.LoadSize, |
800 | AddressSpace: AS, Alignment: LI1->getAlign(), Fast: &Fast); |
801 | if (!Allowed || !Fast) |
802 | return false; |
803 | |
804 | // Get the Index and Ptr for the new GEP. |
805 | Value *Load1Ptr = LI1->getPointerOperand(); |
806 | Builder.SetInsertPoint(LOps.RootInsert); |
807 | if (!DT.dominates(Def: Load1Ptr, User: LOps.RootInsert)) { |
808 | APInt Offset1(DL.getIndexTypeSizeInBits(Ty: Load1Ptr->getType()), 0); |
809 | Load1Ptr = Load1Ptr->stripAndAccumulateConstantOffsets( |
810 | DL, Offset&: Offset1, /* AllowNonInbounds */ true); |
811 | Load1Ptr = Builder.CreatePtrAdd(Ptr: Load1Ptr, |
812 | Offset: Builder.getInt32(C: Offset1.getZExtValue())); |
813 | } |
814 | // Generate wider load. |
815 | NewLoad = Builder.CreateAlignedLoad(Ty: WiderType, Ptr: Load1Ptr, Align: LI1->getAlign(), |
816 | isVolatile: LI1->isVolatile(), Name: "" ); |
817 | NewLoad->takeName(V: LI1); |
818 | // Set the New Load AATags Metadata. |
819 | if (LOps.AATags) |
820 | NewLoad->setAAMetadata(LOps.AATags); |
821 | |
822 | Value *NewOp = NewLoad; |
823 | // Check if zero extend needed. |
824 | if (LOps.ZextType) |
825 | NewOp = Builder.CreateZExt(V: NewOp, DestTy: LOps.ZextType); |
826 | |
827 | // Check if shift needed. We need to shift with the amount of load1 |
828 | // shift if not zero. |
829 | if (LOps.Shift) |
830 | NewOp = Builder.CreateShl(LHS: NewOp, RHS: ConstantInt::get(Context&: I.getContext(), V: *LOps.Shift)); |
831 | I.replaceAllUsesWith(V: NewOp); |
832 | |
833 | return true; |
834 | } |
835 | |
836 | // Calculate GEP Stride and accumulated const ModOffset. Return Stride and |
837 | // ModOffset |
838 | static std::pair<APInt, APInt> |
839 | getStrideAndModOffsetOfGEP(Value *PtrOp, const DataLayout &DL) { |
840 | unsigned BW = DL.getIndexTypeSizeInBits(Ty: PtrOp->getType()); |
841 | std::optional<APInt> Stride; |
842 | APInt ModOffset(BW, 0); |
843 | // Return a minimum gep stride, greatest common divisor of consective gep |
844 | // index scales(c.f. Bézout's identity). |
845 | while (auto *GEP = dyn_cast<GEPOperator>(Val: PtrOp)) { |
846 | MapVector<Value *, APInt> VarOffsets; |
847 | if (!GEP->collectOffset(DL, BitWidth: BW, VariableOffsets&: VarOffsets, ConstantOffset&: ModOffset)) |
848 | break; |
849 | |
850 | for (auto [V, Scale] : VarOffsets) { |
851 | // Only keep a power of two factor for non-inbounds |
852 | if (!GEP->isInBounds()) |
853 | Scale = APInt::getOneBitSet(numBits: Scale.getBitWidth(), BitNo: Scale.countr_zero()); |
854 | |
855 | if (!Stride) |
856 | Stride = Scale; |
857 | else |
858 | Stride = APIntOps::GreatestCommonDivisor(A: *Stride, B: Scale); |
859 | } |
860 | |
861 | PtrOp = GEP->getPointerOperand(); |
862 | } |
863 | |
864 | // Check whether pointer arrives back at Global Variable via at least one GEP. |
865 | // Even if it doesn't, we can check by alignment. |
866 | if (!isa<GlobalVariable>(Val: PtrOp) || !Stride) |
867 | return {APInt(BW, 1), APInt(BW, 0)}; |
868 | |
869 | // In consideration of signed GEP indices, non-negligible offset become |
870 | // remainder of division by minimum GEP stride. |
871 | ModOffset = ModOffset.srem(RHS: *Stride); |
872 | if (ModOffset.isNegative()) |
873 | ModOffset += *Stride; |
874 | |
875 | return {*Stride, ModOffset}; |
876 | } |
877 | |
878 | /// If C is a constant patterned array and all valid loaded results for given |
879 | /// alignment are same to a constant, return that constant. |
880 | static bool foldPatternedLoads(Instruction &I, const DataLayout &DL) { |
881 | auto *LI = dyn_cast<LoadInst>(Val: &I); |
882 | if (!LI || LI->isVolatile()) |
883 | return false; |
884 | |
885 | // We can only fold the load if it is from a constant global with definitive |
886 | // initializer. Skip expensive logic if this is not the case. |
887 | auto *PtrOp = LI->getPointerOperand(); |
888 | auto *GV = dyn_cast<GlobalVariable>(Val: getUnderlyingObject(V: PtrOp)); |
889 | if (!GV || !GV->isConstant() || !GV->hasDefinitiveInitializer()) |
890 | return false; |
891 | |
892 | // Bail for large initializers in excess of 4K to avoid too many scans. |
893 | Constant *C = GV->getInitializer(); |
894 | uint64_t GVSize = DL.getTypeAllocSize(Ty: C->getType()); |
895 | if (!GVSize || 4096 < GVSize) |
896 | return false; |
897 | |
898 | Type *LoadTy = LI->getType(); |
899 | unsigned BW = DL.getIndexTypeSizeInBits(Ty: PtrOp->getType()); |
900 | auto [Stride, ConstOffset] = getStrideAndModOffsetOfGEP(PtrOp, DL); |
901 | |
902 | // Any possible offset could be multiple of GEP stride. And any valid |
903 | // offset is multiple of load alignment, so checking only multiples of bigger |
904 | // one is sufficient to say results' equality. |
905 | if (auto LA = LI->getAlign(); |
906 | LA <= GV->getAlign().valueOrOne() && Stride.getZExtValue() < LA.value()) { |
907 | ConstOffset = APInt(BW, 0); |
908 | Stride = APInt(BW, LA.value()); |
909 | } |
910 | |
911 | Constant *Ca = ConstantFoldLoadFromConst(C, Ty: LoadTy, Offset: ConstOffset, DL); |
912 | if (!Ca) |
913 | return false; |
914 | |
915 | unsigned E = GVSize - DL.getTypeStoreSize(Ty: LoadTy); |
916 | for (; ConstOffset.getZExtValue() <= E; ConstOffset += Stride) |
917 | if (Ca != ConstantFoldLoadFromConst(C, Ty: LoadTy, Offset: ConstOffset, DL)) |
918 | return false; |
919 | |
920 | I.replaceAllUsesWith(V: Ca); |
921 | |
922 | return true; |
923 | } |
924 | |
925 | /// This is the entry point for folds that could be implemented in regular |
926 | /// InstCombine, but they are separated because they are not expected to |
927 | /// occur frequently and/or have more than a constant-length pattern match. |
928 | static bool foldUnusualPatterns(Function &F, DominatorTree &DT, |
929 | TargetTransformInfo &TTI, |
930 | TargetLibraryInfo &TLI, AliasAnalysis &AA, |
931 | AssumptionCache &AC) { |
932 | bool MadeChange = false; |
933 | for (BasicBlock &BB : F) { |
934 | // Ignore unreachable basic blocks. |
935 | if (!DT.isReachableFromEntry(A: &BB)) |
936 | continue; |
937 | |
938 | const DataLayout &DL = F.getParent()->getDataLayout(); |
939 | |
940 | // Walk the block backwards for efficiency. We're matching a chain of |
941 | // use->defs, so we're more likely to succeed by starting from the bottom. |
942 | // Also, we want to avoid matching partial patterns. |
943 | // TODO: It would be more efficient if we removed dead instructions |
944 | // iteratively in this loop rather than waiting until the end. |
945 | for (Instruction &I : make_early_inc_range(Range: llvm::reverse(C&: BB))) { |
946 | MadeChange |= foldAnyOrAllBitsSet(I); |
947 | MadeChange |= foldGuardedFunnelShift(I, DT); |
948 | MadeChange |= tryToRecognizePopCount(I); |
949 | MadeChange |= tryToFPToSat(I, TTI); |
950 | MadeChange |= tryToRecognizeTableBasedCttz(I); |
951 | MadeChange |= foldConsecutiveLoads(I, DL, TTI, AA, DT); |
952 | MadeChange |= foldPatternedLoads(I, DL); |
953 | // NOTE: This function introduces erasing of the instruction `I`, so it |
954 | // needs to be called at the end of this sequence, otherwise we may make |
955 | // bugs. |
956 | MadeChange |= foldSqrt(I, TTI, TLI, AC, DT); |
957 | } |
958 | } |
959 | |
960 | // We're done with transforms, so remove dead instructions. |
961 | if (MadeChange) |
962 | for (BasicBlock &BB : F) |
963 | SimplifyInstructionsInBlock(BB: &BB); |
964 | |
965 | return MadeChange; |
966 | } |
967 | |
968 | /// This is the entry point for all transforms. Pass manager differences are |
969 | /// handled in the callers of this function. |
970 | static bool runImpl(Function &F, AssumptionCache &AC, TargetTransformInfo &TTI, |
971 | TargetLibraryInfo &TLI, DominatorTree &DT, |
972 | AliasAnalysis &AA) { |
973 | bool MadeChange = false; |
974 | const DataLayout &DL = F.getParent()->getDataLayout(); |
975 | TruncInstCombine TIC(AC, TLI, DL, DT); |
976 | MadeChange |= TIC.run(F); |
977 | MadeChange |= foldUnusualPatterns(F, DT, TTI, TLI, AA, AC); |
978 | return MadeChange; |
979 | } |
980 | |
981 | PreservedAnalyses AggressiveInstCombinePass::run(Function &F, |
982 | FunctionAnalysisManager &AM) { |
983 | auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F); |
984 | auto &TLI = AM.getResult<TargetLibraryAnalysis>(IR&: F); |
985 | auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F); |
986 | auto &TTI = AM.getResult<TargetIRAnalysis>(IR&: F); |
987 | auto &AA = AM.getResult<AAManager>(IR&: F); |
988 | if (!runImpl(F, AC, TTI, TLI, DT, AA)) { |
989 | // No changes, all analyses are preserved. |
990 | return PreservedAnalyses::all(); |
991 | } |
992 | // Mark all the analyses that instcombine updates as preserved. |
993 | PreservedAnalyses PA; |
994 | PA.preserveSet<CFGAnalyses>(); |
995 | return PA; |
996 | } |
997 | |