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: 2018-02-23 15:42:53 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/DenseMap.h"
      27             : #include "llvm/ADT/PostOrderIterator.h"
      28             : #include "llvm/ADT/SetVector.h"
      29             : #include "llvm/IR/IRBuilder.h"
      30             : #include "llvm/IR/PassManager.h"
      31             : #include "llvm/IR/ValueHandle.h"
      32             : 
      33             : namespace llvm {
      34             : 
      35             : class APInt;
      36             : class BasicBlock;
      37             : class BinaryOperator;
      38             : class Function;
      39             : class Instruction;
      40             : class Value;
      41             : 
      42             : /// A private "module" namespace for types and utilities used by Reassociate.
      43             : /// These are implementation details and should not be used by clients.
      44             : namespace reassociate {
      45             : 
      46             : struct ValueEntry {
      47             :   unsigned Rank;
      48             :   Value *Op;
      49             : 
      50     1163522 :   ValueEntry(unsigned R, Value *O) : Rank(R), Op(O) {}
      51             : };
      52             : 
      53             : inline bool operator<(const ValueEntry &LHS, const ValueEntry &RHS) {
      54             :   return LHS.Rank > RHS.Rank; // Sort so that highest rank goes to start.
      55             : }
      56             : 
      57             : /// \brief Utility class representing a base and exponent pair which form one
      58             : /// factor of some product.
      59             : struct Factor {
      60             :   Value *Base;
      61             :   unsigned Power;
      62             : 
      63          20 :   Factor(Value *Base, unsigned Power) : Base(Base), Power(Power) {}
      64             : };
      65             : 
      66             : class XorOpnd;
      67             : 
      68             : } // end namespace reassociate
      69             : 
      70             : /// Reassociate commutative expressions.
      71       28530 : class ReassociatePass : public PassInfoMixin<ReassociatePass> {
      72             :   DenseMap<BasicBlock *, unsigned> RankMap;
      73             :   DenseMap<AssertingVH<Value>, unsigned> ValueRankMap;
      74             :   SetVector<AssertingVH<Instruction>> RedoInsts;
      75             : 
      76             :   // Arbitrary, but prevents quadratic behavior.
      77             :   static const unsigned GlobalReassociateLimit = 10;
      78             :   static const unsigned NumBinaryOps =
      79             :       Instruction::BinaryOpsEnd - Instruction::BinaryOpsBegin;
      80             :   DenseMap<std::pair<Value *, Value *>, unsigned> PairMap[NumBinaryOps];
      81             : 
      82             :   bool MadeChange;
      83             : 
      84             : public:
      85             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &);
      86             : 
      87             : private:
      88             :   void BuildRankMap(Function &F, ReversePostOrderTraversal<Function *> &RPOT);
      89             :   unsigned getRank(Value *V);
      90             :   void canonicalizeOperands(Instruction *I);
      91             :   void ReassociateExpression(BinaryOperator *I);
      92             :   void RewriteExprTree(BinaryOperator *I,
      93             :                        SmallVectorImpl<reassociate::ValueEntry> &Ops);
      94             :   Value *OptimizeExpression(BinaryOperator *I,
      95             :                             SmallVectorImpl<reassociate::ValueEntry> &Ops);
      96             :   Value *OptimizeAdd(Instruction *I,
      97             :                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
      98             :   Value *OptimizeXor(Instruction *I,
      99             :                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
     100             :   bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
     101             :                       APInt &ConstOpnd, Value *&Res);
     102             :   bool CombineXorOpnd(Instruction *I, reassociate::XorOpnd *Opnd1,
     103             :                       reassociate::XorOpnd *Opnd2, APInt &ConstOpnd,
     104             :                       Value *&Res);
     105             :   Value *buildMinimalMultiplyDAG(IRBuilder<> &Builder,
     106             :                                  SmallVectorImpl<reassociate::Factor> &Factors);
     107             :   Value *OptimizeMul(BinaryOperator *I,
     108             :                      SmallVectorImpl<reassociate::ValueEntry> &Ops);
     109             :   Value *RemoveFactorFromExpression(Value *V, Value *Factor);
     110             :   void EraseInst(Instruction *I);
     111             :   void RecursivelyEraseDeadInsts(Instruction *I,
     112             :                                  SetVector<AssertingVH<Instruction>> &Insts);
     113             :   void OptimizeInst(Instruction *I);
     114             :   Instruction *canonicalizeNegConstExpr(Instruction *I);
     115             :   void BuildPairMap(ReversePostOrderTraversal<Function *> &RPOT);
     116             : };
     117             : 
     118             : } // end namespace llvm
     119             : 
     120             : #endif // LLVM_TRANSFORMS_SCALAR_REASSOCIATE_H

Generated by: LCOV version 1.13