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

          Line data    Source code
       1             : //===- Reassociate.h - Reassociate binary expressions -----------*- C++ -*-===//
       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 commutative expressions in an order that is designed
      11             : // to promote better constant propagation, GCSE, LICM, PRE, etc.
      12             : //
      13             : // For example: 4 + (x + 5) -> x + (4 + 5)
      14             : //
      15             : // In the implementation of this algorithm, constants are assigned rank = 0,
      16             : // function arguments are rank = 1, and other values are assigned ranks
      17             : // corresponding to the reverse post order traversal of current function
      18             : // (starting at 2), which effectively gives values in deep loops higher rank
      19             : // than values not in loops.
      20             : //
      21             : //===----------------------------------------------------------------------===//
      22             : 
      23             : #ifndef LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
      24             : #define LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H
      25             : 
      26             : #include "llvm/ADT/PostOrderIterator.h"
      27             : #include "llvm/ADT/SetVector.h"
      28             : #include "llvm/IR/IRBuilder.h"
      29             : #include "llvm/IR/Operator.h"
      30             : #include "llvm/IR/PassManager.h"
      31             : 
      32             : namespace llvm {
      33             : 
      34             : /// A private "module" namespace for types and utilities used by Reassociate.
      35             : /// These are implementation details and should not be used by clients.
      36             : namespace reassociate {
      37             : struct ValueEntry {
      38             :   unsigned Rank;
      39             :   Value *Op;
      40     1105019 :   ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
      41             : };
      42             : inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
      43             :   return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start.
      44             : }
      45             : 
      46             : /// \brief Utility class representing a base and exponent pair which form one
      47             : /// factor of some product.
      48             : struct Factor {
      49             :   Value *Base;
      50             :   unsigned Power;
      51          20 :   Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {}
      52             : };
      53             : 
      54             : class XorOpnd;
      55             : }
      56             : 
      57             : /// Reassociate commutative expressions.
      58        7728 : class ReassociatePass : public PassInfoMixin<ReassociatePass> {
      59             :   DenseMap<BasicBlock *, unsigned> RankMap;
      60             :   DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
      61             :   SetVector<AssertingVH<Instruction>> RedoInsts;
      62             :   bool MadeChange;
      63             : 
      64             : public:
      65             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
      66             : 
      67             : private:
      68             :   void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
      69             :   unsigned getRank(Value *V);
      70             :   void canonicalizeOperands(Instruction *I);
      71             :   void ReassociateExpression(BinaryOperator *I);
      72             :   void RewriteExprTree(BinaryOperator *I,
      73             :                        SmallVectorImpl<reassociate::ValueEntry> &Ops);
      74             :   Value *OptimizeExpression(BinaryOperator *I,
      75             :                             SmallVectorImpl<reassociate::ValueEntry> &Ops);
      76             :   Value *OptimizeAdd(Instruction *I,
      77             :                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
      78             :   Value *OptimizeXor(Instruction *I,
      79             :                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
      80             :   bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
      81             :                       APInt &ConstOpnd, Value *&Res);
      82             :   bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
      83             :                       reassociate::XorOpnd *Opnd2, APInt &ConstOpnd,
      84             :                       Value *&Res);
      85             :   Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder,
      86             :                                  SmallVectorImpl<reassociate::Factor> &Factors);
      87             :   Value *OptimizeMul(BinaryOperator *I,
      88             :                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
      89             :   Value *RemoveFactorFromExpression(Value *V, Value *Factor);
      90             :   void EraseInst(Instruction *I);
      91             :   void RecursivelyEraseDeadInsts(Instruction *I,
      92             :                                  SetVector<AssertingVH<Instruction>> &Insts);
      93             :   void OptimizeInst(Instruction *I);
      94             :   Instruction *canonicalizeNegConstExpr(Instruction *I);
      95             : };
      96             : }
      97             : 
      98             : #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H

Generated by: LCOV version 1.13