LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Scalar - NaryReassociate.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 1 1 100.0 %
Date: 2017-09-14 15:23:50 Functions: 0 0 -
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- NaryReassociate.h - Reassociate n-ary expressions ------------------===//
       2             : //
       3             : //                     The LLVM Compiler Infrastructure
       4             : //
       5             : // This file is distributed under the University of Illinois Open Source
       6             : // License. See LICENSE.TXT for details.
       7             : //
       8             : //===----------------------------------------------------------------------===//
       9             : //
      10             : // This pass reassociates n-ary add expressions and eliminates the redundancy
      11             : // exposed by the reassociation.
      12             : //
      13             : // A motivating example:
      14             : //
      15             : //   void foo(int a, int b) {
      16             : //     bar(a + b);
      17             : //     bar((a + 2) + b);
      18             : //   }
      19             : //
      20             : // An ideal compiler should reassociate (a + 2) + b to (a + b) + 2 and simplify
      21             : // the above code to
      22             : //
      23             : //   int t = a + b;
      24             : //   bar(t);
      25             : //   bar(t + 2);
      26             : //
      27             : // However, the Reassociate pass is unable to do that because it processes each
      28             : // instruction individually and believes (a + 2) + b is the best form according
      29             : // to its rank system.
      30             : //
      31             : // To address this limitation, NaryReassociate reassociates an expression in a
      32             : // form that reuses existing instructions. As a result, NaryReassociate can
      33             : // reassociate (a + 2) + b in the example to (a + b) + 2 because it detects that
      34             : // (a + b) is computed before.
      35             : //
      36             : // NaryReassociate works as follows. For every instruction in the form of (a +
      37             : // b) + c, it checks whether a + c or b + c is already computed by a dominating
      38             : // instruction. If so, it then reassociates (a + b) + c into (a + c) + b or (b +
      39             : // c) + a and removes the redundancy accordingly. To efficiently look up whether
      40             : // an expression is computed before, we store each instruction seen and its SCEV
      41             : // into an SCEV-to-instruction map.
      42             : //
      43             : // Although the algorithm pattern-matches only ternary additions, it
      44             : // automatically handles many >3-ary expressions by walking through the function
      45             : // in the depth-first order. For example, given
      46             : //
      47             : //   (a + c) + d
      48             : //   ((a + b) + c) + d
      49             : //
      50             : // NaryReassociate first rewrites (a + b) + c to (a + c) + b, and then rewrites
      51             : // ((a + c) + b) + d into ((a + c) + d) + b.
      52             : //
      53             : // Finally, the above dominator-based algorithm may need to be run multiple
      54             : // iterations before emitting optimal code. One source of this need is that we
      55             : // only split an operand when it is used only once. The above algorithm can
      56             : // eliminate an instruction and decrease the usage count of its operands. As a
      57             : // result, an instruction that previously had multiple uses may become a
      58             : // single-use instruction and thus eligible for split consideration. For
      59             : // example,
      60             : //
      61             : //   ac = a + c
      62             : //   ab = a + b
      63             : //   abc = ab + c
      64             : //   ab2 = ab + b
      65             : //   ab2c = ab2 + c
      66             : //
      67             : // In the first iteration, we cannot reassociate abc to ac+b because ab is used
      68             : // twice. However, we can reassociate ab2c to abc+b in the first iteration. As a
      69             : // result, ab2 becomes dead and ab will be used only once in the second
      70             : // iteration.
      71             : //
      72             : // Limitations and TODO items:
      73             : //
      74             : // 1) We only considers n-ary adds and muls for now. This should be extended
      75             : // and generalized.
      76             : //
      77             : //===----------------------------------------------------------------------===//
      78             : 
      79             : #ifndef LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H
      80             : #define LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H
      81             : 
      82             : #include "llvm/ADT/DenseMap.h"
      83             : #include "llvm/ADT/SmallVector.h"
      84             : #include "llvm/Analysis/AssumptionCache.h"
      85             : #include "llvm/Analysis/ScalarEvolution.h"
      86             : #include "llvm/Analysis/TargetLibraryInfo.h"
      87             : #include "llvm/Analysis/TargetTransformInfo.h"
      88             : #include "llvm/IR/Dominators.h"
      89             : #include "llvm/IR/Function.h"
      90             : #include "llvm/IR/PassManager.h"
      91             : 
      92             : namespace llvm {
      93        5667 : class NaryReassociatePass : public PassInfoMixin<NaryReassociatePass> {
      94             : public:
      95             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
      96             : 
      97             :   // Glue for old PM.
      98             :   bool runImpl(Function &F, AssumptionCache *AC_, DominatorTree *DT_,
      99             :                ScalarEvolution *SE_, TargetLibraryInfo *TLI_,
     100             :                TargetTransformInfo *TTI_);
     101             : 
     102             : private:
     103             :   // Runs only one iteration of the dominator-based algorithm. See the header
     104             :   // comments for why we need multiple iterations.
     105             :   bool doOneIteration(Function &F);
     106             : 
     107             :   // Reassociates I for better CSE.
     108             :   Instruction *tryReassociate(Instruction *I);
     109             : 
     110             :   // Reassociate GEP for better CSE.
     111             :   Instruction *tryReassociateGEP(GetElementPtrInst *GEP);
     112             :   // Try splitting GEP at the I-th index and see whether either part can be
     113             :   // CSE'ed. This is a helper function for tryReassociateGEP.
     114             :   //
     115             :   // \p IndexedType The element type indexed by GEP's I-th index. This is
     116             :   //                equivalent to
     117             :   //                  GEP->getIndexedType(GEP->getPointerOperand(), 0-th index,
     118             :   //                                      ..., i-th index).
     119             :   GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
     120             :                                               unsigned I, Type *IndexedType);
     121             :   // Given GEP's I-th index = LHS + RHS, see whether &Base[..][LHS][..] or
     122             :   // &Base[..][RHS][..] can be CSE'ed and rewrite GEP accordingly.
     123             :   GetElementPtrInst *tryReassociateGEPAtIndex(GetElementPtrInst *GEP,
     124             :                                               unsigned I, Value *LHS,
     125             :                                               Value *RHS, Type *IndexedType);
     126             : 
     127             :   // Reassociate binary operators for better CSE.
     128             :   Instruction *tryReassociateBinaryOp(BinaryOperator *I);
     129             : 
     130             :   // A helper function for tryReassociateBinaryOp. LHS and RHS are explicitly
     131             :   // passed.
     132             :   Instruction *tryReassociateBinaryOp(Value *LHS, Value *RHS,
     133             :                                       BinaryOperator *I);
     134             :   // Rewrites I to (LHS op RHS) if LHS is computed already.
     135             :   Instruction *tryReassociatedBinaryOp(const SCEV *LHS, Value *RHS,
     136             :                                        BinaryOperator *I);
     137             : 
     138             :   // Tries to match Op1 and Op2 by using V.
     139             :   bool matchTernaryOp(BinaryOperator *I, Value *V, Value *&Op1, Value *&Op2);
     140             : 
     141             :   // Gets SCEV for (LHS op RHS).
     142             :   const SCEV *getBinarySCEV(BinaryOperator *I, const SCEV *LHS,
     143             :                             const SCEV *RHS);
     144             : 
     145             :   // Returns the closest dominator of \c Dominatee that computes
     146             :   // \c CandidateExpr. Returns null if not found.
     147             :   Instruction *findClosestMatchingDominator(const SCEV *CandidateExpr,
     148             :                                             Instruction *Dominatee);
     149             :   // GetElementPtrInst implicitly sign-extends an index if the index is shorter
     150             :   // than the pointer size. This function returns whether Index is shorter than
     151             :   // GEP's pointer size, i.e., whether Index needs to be sign-extended in order
     152             :   // to be an index of GEP.
     153             :   bool requiresSignExtension(Value *Index, GetElementPtrInst *GEP);
     154             : 
     155             :   AssumptionCache *AC;
     156             :   const DataLayout *DL;
     157             :   DominatorTree *DT;
     158             :   ScalarEvolution *SE;
     159             :   TargetLibraryInfo *TLI;
     160             :   TargetTransformInfo *TTI;
     161             :   // A lookup table quickly telling which instructions compute the given SCEV.
     162             :   // Note that there can be multiple instructions at different locations
     163             :   // computing to the same SCEV, so we map a SCEV to an instruction list.  For
     164             :   // example,
     165             :   //
     166             :   //   if (p1)
     167             :   //     foo(a + b);
     168             :   //   if (p2)
     169             :   //     bar(a + b);
     170             :   DenseMap<const SCEV *, SmallVector<WeakTrackingVH, 2>> SeenExprs;
     171             : };
     172             : } // namespace llvm
     173             : 
     174             : #endif // LLVM_TRANSFORMS_SCALAR_NARYREASSOCIATE_H

Generated by: LCOV version 1.13