LCOV - code coverage report
Current view: top level - include/llvm/Analysis - SparsePropagation.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 0 16 0.0 %
Date: 2017-09-14 15:23:50 Functions: 0 10 0.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- SparsePropagation.h - Sparse Conditional Property Propagation ------===//
       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 file implements an abstract sparse conditional propagation algorithm,
      11             : // modeled after SCCP, but with a customizable lattice function.
      12             : //
      13             : //===----------------------------------------------------------------------===//
      14             : 
      15             : #ifndef LLVM_ANALYSIS_SPARSEPROPAGATION_H
      16             : #define LLVM_ANALYSIS_SPARSEPROPAGATION_H
      17             : 
      18             : #include "llvm/ADT/DenseMap.h"
      19             : #include "llvm/ADT/SmallPtrSet.h"
      20             : #include <set>
      21             : #include <utility>
      22             : #include <vector>
      23             : 
      24             : namespace llvm {
      25             : 
      26             : class Argument;
      27             : class BasicBlock;
      28             : class Constant;
      29             : class Function;
      30             : class Instruction;
      31             : class PHINode;
      32             : class raw_ostream;
      33             : class SparseSolver;
      34             : class TerminatorInst;
      35             : class Value;
      36             : template <typename T> class SmallVectorImpl;
      37             : 
      38             : /// AbstractLatticeFunction - This class is implemented by the dataflow instance
      39             : /// to specify what the lattice values are and how they handle merges etc.
      40             : /// This gives the client the power to compute lattice values from instructions,
      41             : /// constants, etc.  The requirement is that lattice values must all fit into
      42             : /// a void*.  If a void* is not sufficient, the implementation should use this
      43             : /// pointer to be a pointer into a uniquing set or something.
      44             : ///
      45           0 : class AbstractLatticeFunction {
      46             : public:
      47             :   using LatticeVal = void *;
      48             : 
      49             : private:
      50             :   LatticeVal UndefVal, OverdefinedVal, UntrackedVal;
      51             : 
      52             : public:
      53             :   AbstractLatticeFunction(LatticeVal undefVal, LatticeVal overdefinedVal,
      54             :                           LatticeVal untrackedVal) {
      55             :     UndefVal = undefVal;
      56             :     OverdefinedVal = overdefinedVal;
      57             :     UntrackedVal = untrackedVal;
      58             :   }
      59             : 
      60             :   virtual ~AbstractLatticeFunction();
      61             : 
      62             :   LatticeVal getUndefVal()       const { return UndefVal; }
      63             :   LatticeVal getOverdefinedVal() const { return OverdefinedVal; }
      64             :   LatticeVal getUntrackedVal()   const { return UntrackedVal; }
      65             : 
      66             :   /// IsUntrackedValue - If the specified Value is something that is obviously
      67             :   /// uninteresting to the analysis (and would always return UntrackedVal),
      68             :   /// this function can return true to avoid pointless work.
      69           0 :   virtual bool IsUntrackedValue(Value *V) { return false; }
      70             : 
      71             :   /// ComputeConstant - Given a constant value, compute and return a lattice
      72             :   /// value corresponding to the specified constant.
      73           0 :   virtual LatticeVal ComputeConstant(Constant *C) {
      74           0 :     return getOverdefinedVal(); // always safe
      75             :   }
      76             : 
      77             :   /// IsSpecialCasedPHI - Given a PHI node, determine whether this PHI node is
      78             :   /// one that the we want to handle through ComputeInstructionState.
      79           0 :   virtual bool IsSpecialCasedPHI(PHINode *PN) { return false; }
      80             : 
      81             :   /// GetConstant - If the specified lattice value is representable as an LLVM
      82             :   /// constant value, return it.  Otherwise return null.  The returned value
      83             :   /// must be in the same LLVM type as Val.
      84           0 :   virtual Constant *GetConstant(LatticeVal LV, Value *Val, SparseSolver &SS) {
      85           0 :     return nullptr;
      86             :   }
      87             : 
      88             :   /// ComputeArgument - Given a formal argument value, compute and return a
      89             :   /// lattice value corresponding to the specified argument.
      90           0 :   virtual LatticeVal ComputeArgument(Argument *I) {
      91           0 :     return getOverdefinedVal(); // always safe
      92             :   }
      93             : 
      94             :   /// MergeValues - Compute and return the merge of the two specified lattice
      95             :   /// values.  Merging should only move one direction down the lattice to
      96             :   /// guarantee convergence (toward overdefined).
      97           0 :   virtual LatticeVal MergeValues(LatticeVal X, LatticeVal Y) {
      98           0 :     return getOverdefinedVal(); // always safe, never useful.
      99             :   }
     100             : 
     101             :   /// ComputeInstructionState - Given an instruction and a vector of its operand
     102             :   /// values, compute the result value of the instruction.
     103           0 :   virtual LatticeVal ComputeInstructionState(Instruction &I, SparseSolver &SS) {
     104           0 :     return getOverdefinedVal(); // always safe, never useful.
     105             :   }
     106             : 
     107             :   /// PrintValue - Render the specified lattice value to the specified stream.
     108             :   virtual void PrintValue(LatticeVal V, raw_ostream &OS);
     109             : };
     110             : 
     111             : /// SparseSolver - This class is a general purpose solver for Sparse Conditional
     112             : /// Propagation with a programmable lattice function.
     113             : class SparseSolver {
     114             :   using LatticeVal = AbstractLatticeFunction::LatticeVal;
     115             : 
     116             :   /// LatticeFunc - This is the object that knows the lattice and how to do
     117             :   /// compute transfer functions.
     118             :   AbstractLatticeFunction *LatticeFunc;
     119             : 
     120             :   DenseMap<Value *, LatticeVal> ValueState;   // The state each value is in.
     121             :   SmallPtrSet<BasicBlock *, 16> BBExecutable; // The bbs that are executable.
     122             : 
     123             :   std::vector<Instruction *> InstWorkList; // Worklist of insts to process.
     124             : 
     125             :   std::vector<BasicBlock *> BBWorkList; // The BasicBlock work list
     126             : 
     127             :   /// KnownFeasibleEdges - Entries in this set are edges which have already had
     128             :   /// PHI nodes retriggered.
     129             :   using Edge = std::pair<BasicBlock *, BasicBlock *>;
     130             :   std::set<Edge> KnownFeasibleEdges;
     131             : 
     132             : public:
     133             :   explicit SparseSolver(AbstractLatticeFunction *Lattice)
     134             :       : LatticeFunc(Lattice) {}
     135             :   SparseSolver(const SparseSolver &) = delete;
     136             :   SparseSolver &operator=(const SparseSolver &) = delete;
     137             :   ~SparseSolver() { delete LatticeFunc; }
     138             : 
     139             :   /// Solve - Solve for constants and executable blocks.
     140             :   void Solve(Function &F);
     141             : 
     142             :   void Print(Function &F, raw_ostream &OS) const;
     143             : 
     144             :   /// getLatticeState - Return the LatticeVal object that corresponds to the
     145             :   /// value.  If an value is not in the map, it is returned as untracked,
     146             :   /// unlike the getOrInitValueState method.
     147           0 :   LatticeVal getLatticeState(Value *V) const {
     148           0 :     DenseMap<Value*, LatticeVal>::const_iterator I = ValueState.find(V);
     149           0 :     return I != ValueState.end() ? I->second : LatticeFunc->getUntrackedVal();
     150             :   }
     151             : 
     152             :   /// getOrInitValueState - Return the LatticeVal object that corresponds to the
     153             :   /// value, initializing the value's state if it hasn't been entered into the
     154             :   /// map yet.   This function is necessary because not all values should start
     155             :   /// out in the underdefined state... Arguments should be overdefined, and
     156             :   /// constants should be marked as constants.
     157             :   LatticeVal getOrInitValueState(Value *V);
     158             : 
     159             :   /// isEdgeFeasible - Return true if the control flow edge from the 'From'
     160             :   /// basic block to the 'To' basic block is currently feasible.  If
     161             :   /// AggressiveUndef is true, then this treats values with unknown lattice
     162             :   /// values as undefined.  This is generally only useful when solving the
     163             :   /// lattice, not when querying it.
     164             :   bool isEdgeFeasible(BasicBlock *From, BasicBlock *To,
     165             :                       bool AggressiveUndef = false);
     166             : 
     167             :   /// isBlockExecutable - Return true if there are any known feasible
     168             :   /// edges into the basic block.  This is generally only useful when
     169             :   /// querying the lattice.
     170             :   bool isBlockExecutable(BasicBlock *BB) const {
     171             :     return BBExecutable.count(BB);
     172             :   }
     173             : 
     174             : private:
     175             :   /// UpdateState - When the state for some instruction is potentially updated,
     176             :   /// this function notices and adds I to the worklist if needed.
     177             :   void UpdateState(Instruction &Inst, LatticeVal V);
     178             : 
     179             :   /// MarkBlockExecutable - This method can be used by clients to mark all of
     180             :   /// the blocks that are known to be intrinsically live in the processed unit.
     181             :   void MarkBlockExecutable(BasicBlock *BB);
     182             : 
     183             :   /// markEdgeExecutable - Mark a basic block as executable, adding it to the BB
     184             :   /// work list if it is not already executable.
     185             :   void markEdgeExecutable(BasicBlock *Source, BasicBlock *Dest);
     186             : 
     187             :   /// getFeasibleSuccessors - Return a vector of booleans to indicate which
     188             :   /// successors are reachable from a given terminator instruction.
     189             :   void getFeasibleSuccessors(TerminatorInst &TI, SmallVectorImpl<bool> &Succs,
     190             :                              bool AggressiveUndef);
     191             : 
     192             :   void visitInst(Instruction &I);
     193             :   void visitPHINode(PHINode &I);
     194             :   void visitTerminatorInst(TerminatorInst &TI);
     195             : };
     196             : 
     197             : } // end namespace llvm
     198             : 
     199             : #endif // LLVM_ANALYSIS_SPARSEPROPAGATION_H

Generated by: LCOV version 1.13