EIC code displayed by LXR master/​include/​llvm/​Transforms/​Scalar/​NaryReassociate.h	Source navigation Diff markup Identifier search General search
	Version: master test Revert   Change

File indexing completed on 2026-05-10 08:44:42

 //===- NaryReassociate.h - Reassociate n-ary expressions --------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass reassociates n-ary add expressions and eliminates the redundancy
 // exposed by the reassociation.
 //
 // A motivating example:
 //
 //   void foo(int a, int b) {
 //     bar(a + b);
 //     bar((a + 2) + b);
 //   }
 //
 // An ideal compiler should reassociate (a + 2) + b to (a + b) + 2 and simplify
 // the above code to
 //
 //   int t = a + b;
 //   bar(t);
 //   bar(t + 2);
 //
 // However, the Reassociate pass is unable to do that because it processes each
 // instruction individually and believes (a + 2) + b is the best form according
 // to its rank system.
 //
 // To address this limitation, NaryReassociate reassociates an expression in a
 // form that reuses existing instructions. As a result, NaryReassociate can
 // reassociate (a + 2) + b in the example to (a + b) + 2 because it detects that
 // (a + b) is computed before.
 //
 // NaryReassociate works as follows. For every instruction in the form of (a +
 // b) + c, it checks whether a + c or b + c is already computed by a dominating
 // instruction. If so, it then reassociates (a + b) + c into (a + c) + b or (b +
 // c) + a and removes the redundancy accordingly. To efficiently look up whether
 // an expression is computed before, we store each instruction seen and its SCEV
 // into an SCEV-to-instruction map.
 //
 // Although the algorithm pattern-matches only ternary additions, it
 // automatically handles many >3-ary expressions by walking through the function
 // in the depth-first order. For example, given
 //
 //   (a + c) + d
 //   ((a + b) + c) + d
 //
 // NaryReassociate first rewrites (a + b) + c to (a + c) + b, and then rewrites
 // ((a + c) + b) + d into ((a + c) + d) + b.
 //
 // Finally, the above dominator-based algorithm may need to be run multiple
 // iterations before emitting optimal code. One source of this need is that we
 // only split an operand when it is used only once. The above algorithm can
 // eliminate an instruction and decrease the usage count of its operands. As a
 // result, an instruction that previously had multiple uses may become a
 // single-use instruction and thus eligible for split consideration. For
 // example,
 //
 //   ac = a + c
 //   ab = a + b
 //   abc = ab + c
 //   ab2 = ab + b
 //   ab2c = ab2 + c
 //
 // In the first iteration, we cannot reassociate abc to ac+b because ab is used
 // twice. However, we can reassociate ab2c to abc+b in the first iteration. As a
 // result, ab2 becomes dead and ab will be used only once in the second
 // iteration.
 //
 // Limitations and TODO items:
 //
 // 1) We only considers n-ary adds and muls for now. This should be extended
 // and generalized.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H
 #define LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
 #include "llvm/IR/ValueHandle.h"
 
 namespace llvm {
 
 class AssumptionCache;
 class BinaryOperator;
 class DataLayout;
 class DominatorTree;
 class Function;
 class GetElementPtrInst;
 class Instruction;
 class ScalarEvolution;
 class SCEV;
 class TargetLibraryInfo;
 class TargetTransformInfo;
 class Type;
 class Value;
 
 class NaryReassociatePass : public PassInfoMixin<NaryReassociatePass> {
 public:
   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
 
   // Glue for old PM.
   bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_,
                ScalarEvolution *SE_, TargetLibraryInfo *TLI_,
                TargetTransformInfo *TTI_);
 
 private:
   // Runs only one iteration of the dominator-based algorithm. See the header
   // comments for why we need multiple iterations.
   bool doOneIteration(Function &F);
 
   // Reassociates I for better CSE.
   Instruction *tryReassociate(Instruction *I, const SCEV *&OrigSCEV);
 
   // Reassociate GEP for better CSE.
   Instruction *tryReassociateGEP(GetElementPtrInst *GEP);
 
   // Try splitting GEP at the I-th index and see whether either part can be
   // CSE'ed. This is a helper function for tryReassociateGEP.
   //
   // \p IndexedType The element type indexed by GEP's I-th index. This is
   //                equivalent to
   //                  GEP->getIndexedType(GEP->getPointerOperand(), 0-th index,
   //                                      ..., i-th index).
   GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
                                               unsigned I, Type *IndexedType);
 
   // Given GEP's I-th index = LHS + RHS, see whether &Base[..][LHS][..] or
   // &Base[..][RHS][..] can be CSE'ed and rewrite GEP accordingly.
   GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
                                               unsigned I, Value *LHS,
                                               Value *RHS, Type *IndexedType);
 
   // Reassociate binary operators for better CSE.
   Instruction *tryReassociateBinaryOp(BinaryOperator *I);
 
   // A helper function for tryReassociateBinaryOp. LHS and RHS are explicitly
   // passed.
   Instruction *tryReassociateBinaryOp(Value *LHS, Value *RHS,
                                       BinaryOperator *I);
   // Rewrites I to (LHS op RHS) if LHS is computed already.
   Instruction *tryReassociatedBinaryOp(const SCEV *LHS, Value *RHS,
                                        BinaryOperator *I);
 
   // Tries to match Op1 and Op2 by using V.
   bool matchTernaryOp(BinaryOperator *I, Value *V, Value *&Op1, Value *&Op2);
 
   // Gets SCEV for (LHS op RHS).
   const SCEV *getBinarySCEV(BinaryOperator *I, const SCEV *LHS,
                             const SCEV *RHS);
 
   // Returns the closest dominator of \c Dominatee that computes
   // \c CandidateExpr. Returns null if not found.
   Instruction *findClosestMatchingDominator(const SCEV *CandidateExpr,
                                             Instruction *Dominatee);
 
   // Try to match \p I as signed/unsigned Min/Max and reassociate it. \p
   // OrigSCEV is set if \I matches Min/Max regardless whether resassociation is
   // done or not. If reassociation was successful newly generated instruction is
   // returned, otherwise nullptr.
   template <typename PredT>
   Instruction *matchAndReassociateMinOrMax(Instruction *I,
                                            const SCEV *&OrigSCEV);
 
   // Reassociate Min/Max.
   template <typename MaxMinT>
   Value *tryReassociateMinOrMax(Instruction *I, MaxMinT MaxMinMatch, Value *LHS,
                                 Value *RHS);
 
   // GetElementPtrInst implicitly sign-extends an index if the index is shorter
   // than the pointer size. This function returns whether Index is shorter than
   // GEP's pointer size, i.e., whether Index needs to be sign-extended in order
   // to be an index of GEP.
   bool requiresSignExtension(Value *Index, GetElementPtrInst *GEP);
 
   AssumptionCache *AC;
   const DataLayout *DL;
   DominatorTree *DT;
   ScalarEvolution *SE;
   TargetLibraryInfo *TLI;
   TargetTransformInfo *TTI;
 
   // A lookup table quickly telling which instructions compute the given SCEV.
   // Note that there can be multiple instructions at different locations
   // computing to the same SCEV, so we map a SCEV to an instruction list.  For
   // example,
   //
   //   if (p1)
   //     foo(a + b);
   //   if (p2)
   //     bar(a + b);
   DenseMap<const SCEV *, SmallVector<WeakTrackingVH, 2>> SeenExprs;
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H

This page was automatically generated by the 2.3.7 LXR engine. The LXR team