1//===- NaryReassociate.cpp - Reassociate n-ary expressions ----------------===//
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 pass reassociates n-ary add expressions and eliminates the redundancy
10// exposed by the reassociation.
11//
12// A motivating example:
13//
14// void foo(int a, int b) {
15// bar(a + b);
16// bar((a + 2) + b);
17// }
18//
19// An ideal compiler should reassociate (a + 2) + b to (a + b) + 2 and simplify
20// the above code to
21//
22// int t = a + b;
23// bar(t);
24// bar(t + 2);
25//
26// However, the Reassociate pass is unable to do that because it processes each
27// instruction individually and believes (a + 2) + b is the best form according
28// to its rank system.
29//
30// To address this limitation, NaryReassociate reassociates an expression in a
31// form that reuses existing instructions. As a result, NaryReassociate can
32// reassociate (a + 2) + b in the example to (a + b) + 2 because it detects that
33// (a + b) is computed before.
34//
35// NaryReassociate works as follows. For every instruction in the form of (a +
36// b) + c, it checks whether a + c or b + c is already computed by a dominating
37// instruction. If so, it then reassociates (a + b) + c into (a + c) + b or (b +
38// c) + a and removes the redundancy accordingly. To efficiently look up whether
39// an expression is computed before, we store each instruction seen and its SCEV
40// into an SCEV-to-instruction map.
41//
42// Although the algorithm pattern-matches only ternary additions, it
43// automatically handles many >3-ary expressions by walking through the function
44// in the depth-first order. For example, given
45//
46// (a + c) + d
47// ((a + b) + c) + d
48//
49// NaryReassociate first rewrites (a + b) + c to (a + c) + b, and then rewrites
50// ((a + c) + b) + d into ((a + c) + d) + b.
51//
52// Finally, the above dominator-based algorithm may need to be run multiple
53// iterations before emitting optimal code. One source of this need is that we
54// only split an operand when it is used only once. The above algorithm can
55// eliminate an instruction and decrease the usage count of its operands. As a
56// result, an instruction that previously had multiple uses may become a
57// single-use instruction and thus eligible for split consideration. For
58// example,
59//
60// ac = a + c
61// ab = a + b
62// abc = ab + c
63// ab2 = ab + b
64// ab2c = ab2 + c
65//
66// In the first iteration, we cannot reassociate abc to ac+b because ab is used
67// twice. However, we can reassociate ab2c to abc+b in the first iteration. As a
68// result, ab2 becomes dead and ab will be used only once in the second
69// iteration.
70//
71// Limitations and TODO items:
72//
73// 1) We only considers n-ary adds and muls for now. This should be extended
74// and generalized.
75//
76//===----------------------------------------------------------------------===//
77
78#include "llvm/Transforms/Scalar/NaryReassociate.h"
79#include "llvm/ADT/DepthFirstIterator.h"
80#include "llvm/ADT/SmallVector.h"
81#include "llvm/Analysis/AssumptionCache.h"
82#include "llvm/Analysis/ScalarEvolution.h"
83#include "llvm/Analysis/ScalarEvolutionExpressions.h"
84#include "llvm/Analysis/TargetLibraryInfo.h"
85#include "llvm/Analysis/TargetTransformInfo.h"
86#include "llvm/Analysis/ValueTracking.h"
87#include "llvm/IR/BasicBlock.h"
88#include "llvm/IR/Constants.h"
89#include "llvm/IR/DataLayout.h"
90#include "llvm/IR/DerivedTypes.h"
91#include "llvm/IR/Dominators.h"
92#include "llvm/IR/Function.h"
93#include "llvm/IR/GetElementPtrTypeIterator.h"
94#include "llvm/IR/IRBuilder.h"
95#include "llvm/IR/InstrTypes.h"
96#include "llvm/IR/Instruction.h"
97#include "llvm/IR/Instructions.h"
98#include "llvm/IR/Module.h"
99#include "llvm/IR/Operator.h"
100#include "llvm/IR/PatternMatch.h"
101#include "llvm/IR/Type.h"
102#include "llvm/IR/Value.h"
103#include "llvm/IR/ValueHandle.h"
104#include "llvm/InitializePasses.h"
105#include "llvm/Pass.h"
106#include "llvm/Support/Casting.h"
107#include "llvm/Support/ErrorHandling.h"
108#include "llvm/Transforms/Scalar.h"
109#include "llvm/Transforms/Utils/Local.h"
110#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
111#include <cassert>
112#include <cstdint>
113
114using namespace llvm;
115using namespace PatternMatch;
116
117#define DEBUG_TYPE "nary-reassociate"
118
119namespace {
120
121class NaryReassociateLegacyPass : public FunctionPass {
122public:
123 static char ID;
124
125 NaryReassociateLegacyPass() : FunctionPass(ID) {
126 initializeNaryReassociateLegacyPassPass(*PassRegistry::getPassRegistry());
127 }
128
129 bool doInitialization(Module &M) override {
130 return false;
131 }
132
133 bool runOnFunction(Function &F) override;
134
135 void getAnalysisUsage(AnalysisUsage &AU) const override {
136 AU.addPreserved<DominatorTreeWrapperPass>();
137 AU.addPreserved<ScalarEvolutionWrapperPass>();
138 AU.addPreserved<TargetLibraryInfoWrapperPass>();
139 AU.addRequired<AssumptionCacheTracker>();
140 AU.addRequired<DominatorTreeWrapperPass>();
141 AU.addRequired<ScalarEvolutionWrapperPass>();
142 AU.addRequired<TargetLibraryInfoWrapperPass>();
143 AU.addRequired<TargetTransformInfoWrapperPass>();
144 AU.setPreservesCFG();
145 }
146
147private:
148 NaryReassociatePass Impl;
149};
150
151} // end anonymous namespace
152
153char NaryReassociateLegacyPass::ID = 0;
154
155INITIALIZE_PASS_BEGIN(NaryReassociateLegacyPass, "nary-reassociate",
156 "Nary reassociation", false, false)
157INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
158INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
159INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
160INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
161INITIALIZE_PASS_DEPENDENCY(TargetTransformInfoWrapperPass)
162INITIALIZE_PASS_END(NaryReassociateLegacyPass, "nary-reassociate",
163 "Nary reassociation", false, false)
164
165FunctionPass *llvm::createNaryReassociatePass() {
166 return new NaryReassociateLegacyPass();
167}
168
169bool NaryReassociateLegacyPass::runOnFunction(Function &F) {
170 if (skipFunction(F))
171 return false;
172
173 auto *AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
174 auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
175 auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
176 auto *TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(F);
177 auto *TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
178
179 return Impl.runImpl(F, AC_: AC, DT_: DT, SE_: SE, TLI_: TLI, TTI_: TTI);
180}
181
182PreservedAnalyses NaryReassociatePass::run(Function &F,
183 FunctionAnalysisManager &AM) {
184 auto *AC = &AM.getResult<AssumptionAnalysis>(IR&: F);
185 auto *DT = &AM.getResult<DominatorTreeAnalysis>(IR&: F);
186 auto *SE = &AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
187 auto *TLI = &AM.getResult<TargetLibraryAnalysis>(IR&: F);
188 auto *TTI = &AM.getResult<TargetIRAnalysis>(IR&: F);
189
190 if (!runImpl(F, AC_: AC, DT_: DT, SE_: SE, TLI_: TLI, TTI_: TTI))
191 return PreservedAnalyses::all();
192
193 PreservedAnalyses PA;
194 PA.preserveSet<CFGAnalyses>();
195 PA.preserve<ScalarEvolutionAnalysis>();
196 return PA;
197}
198
199bool NaryReassociatePass::runImpl(Function &F, AssumptionCache *AC_,
200 DominatorTree *DT_, ScalarEvolution *SE_,
201 TargetLibraryInfo *TLI_,
202 TargetTransformInfo *TTI_) {
203 AC = AC_;
204 DT = DT_;
205 SE = SE_;
206 TLI = TLI_;
207 TTI = TTI_;
208 DL = &F.getDataLayout();
209
210 bool Changed = false, ChangedInThisIteration;
211 do {
212 ChangedInThisIteration = doOneIteration(F);
213 Changed |= ChangedInThisIteration;
214 } while (ChangedInThisIteration);
215 return Changed;
216}
217
218bool NaryReassociatePass::doOneIteration(Function &F) {
219 bool Changed = false;
220 SeenExprs.clear();
221 // Process the basic blocks in a depth first traversal of the dominator
222 // tree. This order ensures that all bases of a candidate are in Candidates
223 // when we process it.
224 SmallVector<WeakTrackingVH, 16> DeadInsts;
225 for (const auto Node : depth_first(G: DT)) {
226 BasicBlock *BB = Node->getBlock();
227 for (Instruction &OrigI : *BB) {
228 const SCEV *OrigSCEV = nullptr;
229 if (Instruction *NewI = tryReassociate(I: &OrigI, OrigSCEV)) {
230 Changed = true;
231 OrigI.replaceAllUsesWith(V: NewI);
232
233 // Add 'OrigI' to the list of dead instructions.
234 DeadInsts.push_back(Elt: WeakTrackingVH(&OrigI));
235 // Add the rewritten instruction to SeenExprs; the original
236 // instruction is deleted.
237 const SCEV *NewSCEV = SE->getSCEV(V: NewI);
238 SeenExprs[NewSCEV].push_back(Elt: WeakTrackingVH(NewI));
239
240 // Ideally, NewSCEV should equal OldSCEV because tryReassociate(I)
241 // is equivalent to I. However, ScalarEvolution::getSCEV may
242 // weaken nsw causing NewSCEV not to equal OldSCEV. For example,
243 // suppose we reassociate
244 // I = &a[sext(i +nsw j)] // assuming sizeof(a[0]) = 4
245 // to
246 // NewI = &a[sext(i)] + sext(j).
247 //
248 // ScalarEvolution computes
249 // getSCEV(I) = a + 4 * sext(i + j)
250 // getSCEV(newI) = a + 4 * sext(i) + 4 * sext(j)
251 // which are different SCEVs.
252 //
253 // To alleviate this issue of ScalarEvolution not always capturing
254 // equivalence, we add I to SeenExprs[OldSCEV] as well so that we can
255 // map both SCEV before and after tryReassociate(I) to I.
256 //
257 // This improvement is exercised in @reassociate_gep_nsw in
258 // nary-gep.ll.
259 if (NewSCEV != OrigSCEV)
260 SeenExprs[OrigSCEV].push_back(Elt: WeakTrackingVH(NewI));
261 } else if (OrigSCEV)
262 SeenExprs[OrigSCEV].push_back(Elt: WeakTrackingVH(&OrigI));
263 }
264 }
265 // Delete all dead instructions from 'DeadInsts'.
266 // Please note ScalarEvolution is updated along the way.
267 RecursivelyDeleteTriviallyDeadInstructionsPermissive(
268 DeadInsts, TLI, MSSAU: nullptr, AboutToDeleteCallback: [this](Value *V) { SE->forgetValue(V); });
269
270 return Changed;
271}
272
273template <typename PredT>
274Instruction *
275NaryReassociatePass::matchAndReassociateMinOrMax(Instruction *I,
276 const SCEV *&OrigSCEV) {
277 Value *LHS = nullptr;
278 Value *RHS = nullptr;
279
280 auto MinMaxMatcher =
281 MaxMin_match<ICmpInst, bind_ty<Value>, bind_ty<Value>, PredT>(
282 m_Value(V&: LHS), m_Value(V&: RHS));
283 if (match(I, MinMaxMatcher)) {
284 OrigSCEV = SE->getSCEV(V: I);
285 if (auto *NewMinMax = dyn_cast_or_null<Instruction>(
286 tryReassociateMinOrMax(I, MinMaxMatcher, LHS, RHS)))
287 return NewMinMax;
288 if (auto *NewMinMax = dyn_cast_or_null<Instruction>(
289 tryReassociateMinOrMax(I, MinMaxMatcher, RHS, LHS)))
290 return NewMinMax;
291 }
292 return nullptr;
293}
294
295Instruction *NaryReassociatePass::tryReassociate(Instruction * I,
296 const SCEV *&OrigSCEV) {
297
298 if (!SE->isSCEVable(Ty: I->getType()))
299 return nullptr;
300
301 switch (I->getOpcode()) {
302 case Instruction::Add:
303 case Instruction::Mul:
304 OrigSCEV = SE->getSCEV(V: I);
305 return tryReassociateBinaryOp(I: cast<BinaryOperator>(Val: I));
306 case Instruction::GetElementPtr:
307 OrigSCEV = SE->getSCEV(V: I);
308 return tryReassociateGEP(GEP: cast<GetElementPtrInst>(Val: I));
309 default:
310 break;
311 }
312
313 // Try to match signed/unsigned Min/Max.
314 Instruction *ResI = nullptr;
315 // TODO: Currently min/max reassociation is restricted to integer types only
316 // due to use of SCEVExpander which my introduce incompatible forms of min/max
317 // for pointer types.
318 if (I->getType()->isIntegerTy())
319 if ((ResI = matchAndReassociateMinOrMax<umin_pred_ty>(I, OrigSCEV)) ||
320 (ResI = matchAndReassociateMinOrMax<smin_pred_ty>(I, OrigSCEV)) ||
321 (ResI = matchAndReassociateMinOrMax<umax_pred_ty>(I, OrigSCEV)) ||
322 (ResI = matchAndReassociateMinOrMax<smax_pred_ty>(I, OrigSCEV)))
323 return ResI;
324
325 return nullptr;
326}
327
328static bool isGEPFoldable(GetElementPtrInst *GEP,
329 const TargetTransformInfo *TTI) {
330 SmallVector<const Value *, 4> Indices(GEP->indices());
331 return TTI->getGEPCost(PointeeType: GEP->getSourceElementType(), Ptr: GEP->getPointerOperand(),
332 Operands: Indices) == TargetTransformInfo::TCC_Free;
333}
334
335Instruction *NaryReassociatePass::tryReassociateGEP(GetElementPtrInst *GEP) {
336 // Not worth reassociating GEP if it is foldable.
337 if (isGEPFoldable(GEP, TTI))
338 return nullptr;
339
340 gep_type_iterator GTI = gep_type_begin(GEP: *GEP);
341 for (unsigned I = 1, E = GEP->getNumOperands(); I != E; ++I, ++GTI) {
342 if (GTI.isSequential()) {
343 if (auto *NewGEP = tryReassociateGEPAtIndex(GEP, I: I - 1,
344 IndexedType: GTI.getIndexedType())) {
345 return NewGEP;
346 }
347 }
348 }
349 return nullptr;
350}
351
352bool NaryReassociatePass::requiresSignExtension(Value *Index,
353 GetElementPtrInst *GEP) {
354 unsigned IndexSizeInBits =
355 DL->getIndexSizeInBits(AS: GEP->getType()->getPointerAddressSpace());
356 return cast<IntegerType>(Val: Index->getType())->getBitWidth() < IndexSizeInBits;
357}
358
359GetElementPtrInst *
360NaryReassociatePass::tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
361 unsigned I, Type *IndexedType) {
362 SimplifyQuery SQ(*DL, DT, AC, GEP);
363 Value *IndexToSplit = GEP->getOperand(i_nocapture: I + 1);
364 if (SExtInst *SExt = dyn_cast<SExtInst>(Val: IndexToSplit)) {
365 IndexToSplit = SExt->getOperand(i_nocapture: 0);
366 } else if (ZExtInst *ZExt = dyn_cast<ZExtInst>(Val: IndexToSplit)) {
367 // zext can be treated as sext if the source is non-negative.
368 if (isKnownNonNegative(V: ZExt->getOperand(i_nocapture: 0), SQ))
369 IndexToSplit = ZExt->getOperand(i_nocapture: 0);
370 }
371
372 if (AddOperator *AO = dyn_cast<AddOperator>(Val: IndexToSplit)) {
373 // If the I-th index needs sext and the underlying add is not equipped with
374 // nsw, we cannot split the add because
375 // sext(LHS + RHS) != sext(LHS) + sext(RHS).
376 if (requiresSignExtension(Index: IndexToSplit, GEP) &&
377 computeOverflowForSignedAdd(Add: AO, SQ) != OverflowResult::NeverOverflows)
378 return nullptr;
379
380 Value *LHS = AO->getOperand(i_nocapture: 0), *RHS = AO->getOperand(i_nocapture: 1);
381 // IndexToSplit = LHS + RHS.
382 if (auto *NewGEP = tryReassociateGEPAtIndex(GEP, I, LHS, RHS, IndexedType))
383 return NewGEP;
384 // Symmetrically, try IndexToSplit = RHS + LHS.
385 if (LHS != RHS) {
386 if (auto *NewGEP =
387 tryReassociateGEPAtIndex(GEP, I, LHS: RHS, RHS: LHS, IndexedType))
388 return NewGEP;
389 }
390 }
391 return nullptr;
392}
393
394GetElementPtrInst *
395NaryReassociatePass::tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
396 unsigned I, Value *LHS,
397 Value *RHS, Type *IndexedType) {
398 // Look for GEP's closest dominator that has the same SCEV as GEP except that
399 // the I-th index is replaced with LHS.
400 SmallVector<const SCEV *, 4> IndexExprs;
401 for (Use &Index : GEP->indices())
402 IndexExprs.push_back(Elt: SE->getSCEV(V: Index));
403 // Replace the I-th index with LHS.
404 IndexExprs[I] = SE->getSCEV(V: LHS);
405 Type *GEPArgType = SE->getEffectiveSCEVType(Ty: GEP->getOperand(i_nocapture: I)->getType());
406 Type *LHSType = SE->getEffectiveSCEVType(Ty: LHS->getType());
407 size_t LHSSize = DL->getTypeSizeInBits(Ty: LHSType).getFixedValue();
408 size_t GEPArgSize = DL->getTypeSizeInBits(Ty: GEPArgType).getFixedValue();
409 if (isKnownNonNegative(V: LHS, SQ: SimplifyQuery(*DL, DT, AC, GEP)) &&
410 LHSSize < GEPArgSize) {
411 // Zero-extend LHS if it is non-negative. InstCombine canonicalizes sext to
412 // zext if the source operand is proved non-negative. We should do that
413 // consistently so that CandidateExpr more likely appears before. See
414 // @reassociate_gep_assume for an example of this canonicalization.
415 IndexExprs[I] = SE->getZeroExtendExpr(Op: IndexExprs[I], Ty: GEPArgType);
416 }
417 const SCEV *CandidateExpr = SE->getGEPExpr(GEP: cast<GEPOperator>(Val: GEP),
418 IndexExprs);
419
420 Value *Candidate = findClosestMatchingDominator(CandidateExpr, Dominatee: GEP);
421 if (Candidate == nullptr)
422 return nullptr;
423
424 IRBuilder<> Builder(GEP);
425 // Candidate should have the same pointer type as GEP.
426 assert(Candidate->getType() == GEP->getType());
427
428 // NewGEP = (char *)Candidate + RHS * sizeof(IndexedType)
429 uint64_t IndexedSize = DL->getTypeAllocSize(Ty: IndexedType);
430 Type *ElementType = GEP->getResultElementType();
431 uint64_t ElementSize = DL->getTypeAllocSize(Ty: ElementType);
432 // Another less rare case: because I is not necessarily the last index of the
433 // GEP, the size of the type at the I-th index (IndexedSize) is not
434 // necessarily divisible by ElementSize. For example,
435 //
436 // #pragma pack(1)
437 // struct S {
438 // int a[3];
439 // int64 b[8];
440 // };
441 // #pragma pack()
442 //
443 // sizeof(S) = 100 is indivisible by sizeof(int64) = 8.
444 //
445 // TODO: bail out on this case for now. We could emit uglygep.
446 if (IndexedSize % ElementSize != 0)
447 return nullptr;
448
449 // NewGEP = &Candidate[RHS * (sizeof(IndexedType) / sizeof(Candidate[0])));
450 Type *PtrIdxTy = DL->getIndexType(PtrTy: GEP->getType());
451 if (RHS->getType() != PtrIdxTy)
452 RHS = Builder.CreateSExtOrTrunc(V: RHS, DestTy: PtrIdxTy);
453 if (IndexedSize != ElementSize) {
454 RHS = Builder.CreateMul(
455 LHS: RHS, RHS: ConstantInt::get(Ty: PtrIdxTy, V: IndexedSize / ElementSize));
456 }
457 GetElementPtrInst *NewGEP = cast<GetElementPtrInst>(
458 Val: Builder.CreateGEP(Ty: GEP->getResultElementType(), Ptr: Candidate, IdxList: RHS));
459 NewGEP->setIsInBounds(GEP->isInBounds());
460 NewGEP->takeName(V: GEP);
461 return NewGEP;
462}
463
464Instruction *NaryReassociatePass::tryReassociateBinaryOp(BinaryOperator *I) {
465 Value *LHS = I->getOperand(i_nocapture: 0), *RHS = I->getOperand(i_nocapture: 1);
466 // There is no need to reassociate 0.
467 if (SE->getSCEV(V: I)->isZero())
468 return nullptr;
469 if (auto *NewI = tryReassociateBinaryOp(LHS, RHS, I))
470 return NewI;
471 if (auto *NewI = tryReassociateBinaryOp(LHS: RHS, RHS: LHS, I))
472 return NewI;
473 return nullptr;
474}
475
476Instruction *NaryReassociatePass::tryReassociateBinaryOp(Value *LHS, Value *RHS,
477 BinaryOperator *I) {
478 Value *A = nullptr, *B = nullptr;
479 // To be conservative, we reassociate I only when it is the only user of (A op
480 // B).
481 if (LHS->hasOneUse() && matchTernaryOp(I, V: LHS, Op1&: A, Op2&: B)) {
482 // I = (A op B) op RHS
483 // = (A op RHS) op B or (B op RHS) op A
484 const SCEV *AExpr = SE->getSCEV(V: A), *BExpr = SE->getSCEV(V: B);
485 const SCEV *RHSExpr = SE->getSCEV(V: RHS);
486 if (BExpr != RHSExpr) {
487 if (auto *NewI =
488 tryReassociatedBinaryOp(LHS: getBinarySCEV(I, LHS: AExpr, RHS: RHSExpr), RHS: B, I))
489 return NewI;
490 }
491 if (AExpr != RHSExpr) {
492 if (auto *NewI =
493 tryReassociatedBinaryOp(LHS: getBinarySCEV(I, LHS: BExpr, RHS: RHSExpr), RHS: A, I))
494 return NewI;
495 }
496 }
497 return nullptr;
498}
499
500Instruction *NaryReassociatePass::tryReassociatedBinaryOp(const SCEV *LHSExpr,
501 Value *RHS,
502 BinaryOperator *I) {
503 // Look for the closest dominator LHS of I that computes LHSExpr, and replace
504 // I with LHS op RHS.
505 auto *LHS = findClosestMatchingDominator(CandidateExpr: LHSExpr, Dominatee: I);
506 if (LHS == nullptr)
507 return nullptr;
508
509 Instruction *NewI = nullptr;
510 switch (I->getOpcode()) {
511 case Instruction::Add:
512 NewI = BinaryOperator::CreateAdd(V1: LHS, V2: RHS, Name: "", InsertBefore: I->getIterator());
513 break;
514 case Instruction::Mul:
515 NewI = BinaryOperator::CreateMul(V1: LHS, V2: RHS, Name: "", InsertBefore: I->getIterator());
516 break;
517 default:
518 llvm_unreachable("Unexpected instruction.");
519 }
520 NewI->setDebugLoc(I->getDebugLoc());
521 NewI->takeName(V: I);
522 return NewI;
523}
524
525bool NaryReassociatePass::matchTernaryOp(BinaryOperator *I, Value *V,
526 Value *&Op1, Value *&Op2) {
527 switch (I->getOpcode()) {
528 case Instruction::Add:
529 return match(V, P: m_Add(L: m_Value(V&: Op1), R: m_Value(V&: Op2)));
530 case Instruction::Mul:
531 return match(V, P: m_Mul(L: m_Value(V&: Op1), R: m_Value(V&: Op2)));
532 default:
533 llvm_unreachable("Unexpected instruction.");
534 }
535 return false;
536}
537
538const SCEV *NaryReassociatePass::getBinarySCEV(BinaryOperator *I,
539 const SCEV *LHS,
540 const SCEV *RHS) {
541 switch (I->getOpcode()) {
542 case Instruction::Add:
543 return SE->getAddExpr(LHS, RHS);
544 case Instruction::Mul:
545 return SE->getMulExpr(LHS, RHS);
546 default:
547 llvm_unreachable("Unexpected instruction.");
548 }
549 return nullptr;
550}
551
552Instruction *
553NaryReassociatePass::findClosestMatchingDominator(const SCEV *CandidateExpr,
554 Instruction *Dominatee) {
555 auto Pos = SeenExprs.find(Val: CandidateExpr);
556 if (Pos == SeenExprs.end())
557 return nullptr;
558
559 auto &Candidates = Pos->second;
560 // Because we process the basic blocks in pre-order of the dominator tree, a
561 // candidate that doesn't dominate the current instruction won't dominate any
562 // future instruction either. Therefore, we pop it out of the stack. This
563 // optimization makes the algorithm O(n).
564 while (!Candidates.empty()) {
565 // Candidates stores WeakTrackingVHs, so a candidate can be nullptr if it's
566 // removed during rewriting.
567 if (Value *Candidate = Candidates.pop_back_val()) {
568 Instruction *CandidateInstruction = cast<Instruction>(Val: Candidate);
569 if (!DT->dominates(Def: CandidateInstruction, User: Dominatee))
570 continue;
571
572 // Make sure that the instruction is safe to reuse without introducing
573 // poison.
574 SmallVector<Instruction *> DropPoisonGeneratingInsts;
575 if (!SE->canReuseInstruction(S: CandidateExpr, I: CandidateInstruction,
576 DropPoisonGeneratingInsts))
577 continue;
578
579 for (Instruction *I : DropPoisonGeneratingInsts)
580 I->dropPoisonGeneratingAnnotations();
581
582 return CandidateInstruction;
583 }
584 }
585 return nullptr;
586}
587
588template <typename MaxMinT> static SCEVTypes convertToSCEVype(MaxMinT &MM) {
589 if (std::is_same_v<smax_pred_ty, typename MaxMinT::PredType>)
590 return scSMaxExpr;
591 else if (std::is_same_v<umax_pred_ty, typename MaxMinT::PredType>)
592 return scUMaxExpr;
593 else if (std::is_same_v<smin_pred_ty, typename MaxMinT::PredType>)
594 return scSMinExpr;
595 else if (std::is_same_v<umin_pred_ty, typename MaxMinT::PredType>)
596 return scUMinExpr;
597
598 llvm_unreachable("Can't convert MinMax pattern to SCEV type");
599 return scUnknown;
600}
601
602// Parameters:
603// I - instruction matched by MaxMinMatch matcher
604// MaxMinMatch - min/max idiom matcher
605// LHS - first operand of I
606// RHS - second operand of I
607template <typename MaxMinT>
608Value *NaryReassociatePass::tryReassociateMinOrMax(Instruction *I,
609 MaxMinT MaxMinMatch,
610 Value *LHS, Value *RHS) {
611 Value *A = nullptr, *B = nullptr;
612 MaxMinT m_MaxMin(m_Value(V&: A), m_Value(V&: B));
613
614 if (!match(LHS, m_MaxMin))
615 return nullptr;
616
617 if (LHS->hasNUsesOrMore(N: 3) ||
618 // The optimization is profitable only if LHS can be removed in the end.
619 // In other words LHS should be used (directly or indirectly) by I only.
620 llvm::any_of(LHS->users(), [&](auto *U) {
621 return U != I && !(U->hasOneUser() && *U->users().begin() == I);
622 }))
623 return nullptr;
624
625 auto tryCombination = [&](Value *A, const SCEV *AExpr, Value *B,
626 const SCEV *BExpr, Value *C,
627 const SCEV *CExpr) -> Value * {
628 SmallVector<const SCEV *, 2> Ops1{BExpr, AExpr};
629 const SCEVTypes SCEVType = convertToSCEVype(m_MaxMin);
630 const SCEV *R1Expr = SE->getMinMaxExpr(Kind: SCEVType, Operands&: Ops1);
631
632 Instruction *R1MinMax = findClosestMatchingDominator(CandidateExpr: R1Expr, Dominatee: I);
633
634 if (!R1MinMax)
635 return nullptr;
636
637 LLVM_DEBUG(dbgs() << "NARY: Found common sub-expr: " << *R1MinMax << "\n");
638
639 SmallVector<const SCEV *, 2> Ops2{SE->getUnknown(V: C),
640 SE->getUnknown(V: R1MinMax)};
641 const SCEV *R2Expr = SE->getMinMaxExpr(Kind: SCEVType, Operands&: Ops2);
642
643 SCEVExpander Expander(*SE, *DL, "nary-reassociate");
644 Value *NewMinMax = Expander.expandCodeFor(SH: R2Expr, Ty: I->getType(), I);
645 NewMinMax->setName(Twine(I->getName()).concat(Suffix: ".nary"));
646
647 LLVM_DEBUG(dbgs() << "NARY: Deleting: " << *I << "\n"
648 << "NARY: Inserting: " << *NewMinMax << "\n");
649 return NewMinMax;
650 };
651
652 const SCEV *AExpr = SE->getSCEV(V: A);
653 const SCEV *BExpr = SE->getSCEV(V: B);
654 const SCEV *RHSExpr = SE->getSCEV(V: RHS);
655
656 if (BExpr != RHSExpr) {
657 // Try (A op RHS) op B
658 if (auto *NewMinMax = tryCombination(A, AExpr, RHS, RHSExpr, B, BExpr))
659 return NewMinMax;
660 }
661
662 if (AExpr != RHSExpr) {
663 // Try (RHS op B) op A
664 if (auto *NewMinMax = tryCombination(RHS, RHSExpr, B, BExpr, A, AExpr))
665 return NewMinMax;
666 }
667
668 return nullptr;
669}
670