LCOV - code coverage report
Current view: top level - include/llvm/Transforms/Utils - PredicateInfo.h (source / functions) Hit Total Coverage
Test: llvm-toolchain.info Lines: 18 19 94.7 %
Date: 2017-09-14 15:23:50 Functions: 5 16 31.2 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : //===- PredicateInfo.h - Build PredicateInfo ----------------------*-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             : /// \file
      11             : /// \brief  This file implements the PredicateInfo analysis, which creates an Extended
      12             : /// SSA form for operations used in branch comparisons and llvm.assume
      13             : /// comparisons.
      14             : ///
      15             : /// Copies of these operations are inserted into the true/false edge (and after
      16             : /// assumes), and information attached to the copies.  All uses of the original
      17             : /// operation in blocks dominated by the true/false edge (and assume), are
      18             : /// replaced with uses of the copies.  This enables passes to easily and sparsely
      19             : /// propagate condition based info into the operations that may be affected.
      20             : ///
      21             : /// Example:
      22             : /// %cmp = icmp eq i32 %x, 50
      23             : /// br i1 %cmp, label %true, label %false
      24             : /// true:
      25             : /// ret i32 %x
      26             : /// false:
      27             : /// ret i32 1
      28             : ///
      29             : /// will become
      30             : ///
      31             : /// %cmp = icmp eq i32, %x, 50
      32             : /// br i1 %cmp, label %true, label %false
      33             : /// true:
      34             : /// %x.0 = call @llvm.ssa_copy.i32(i32 %x)
      35             : /// ret i32 %x.0
      36             : /// false:
      37             : /// ret i32 1
      38             : ///
      39             : /// Using getPredicateInfoFor on x.0 will give you the comparison it is
      40             : /// dominated by (the icmp), and that you are located in the true edge of that
      41             : /// comparison, which tells you x.0 is 50.
      42             : ///
      43             : /// In order to reduce the number of copies inserted, predicateinfo is only
      44             : /// inserted where it would actually be live.  This means if there are no uses of
      45             : /// an operation dominated by the branch edges, or by an assume, the associated
      46             : /// predicate info is never inserted.
      47             : ///
      48             : ///
      49             : //===----------------------------------------------------------------------===//
      50             : 
      51             : #ifndef LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
      52             : #define LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H
      53             : 
      54             : #include "llvm/ADT/DenseMap.h"
      55             : #include "llvm/ADT/DenseSet.h"
      56             : #include "llvm/ADT/SmallPtrSet.h"
      57             : #include "llvm/ADT/SmallVector.h"
      58             : #include "llvm/ADT/ilist.h"
      59             : #include "llvm/ADT/ilist_node.h"
      60             : #include "llvm/ADT/iterator.h"
      61             : #include "llvm/Analysis/AssumptionCache.h"
      62             : #include "llvm/IR/BasicBlock.h"
      63             : #include "llvm/IR/Dominators.h"
      64             : #include "llvm/IR/Instructions.h"
      65             : #include "llvm/IR/IntrinsicInst.h"
      66             : #include "llvm/IR/Module.h"
      67             : #include "llvm/IR/OperandTraits.h"
      68             : #include "llvm/IR/Type.h"
      69             : #include "llvm/IR/Use.h"
      70             : #include "llvm/IR/User.h"
      71             : #include "llvm/IR/Value.h"
      72             : #include "llvm/Pass.h"
      73             : #include "llvm/PassAnalysisSupport.h"
      74             : #include "llvm/Support/Casting.h"
      75             : #include "llvm/Support/Compiler.h"
      76             : #include "llvm/Support/ErrorHandling.h"
      77             : #include "llvm/Transforms/Utils/OrderedInstructions.h"
      78             : #include <algorithm>
      79             : #include <cassert>
      80             : #include <cstddef>
      81             : #include <iterator>
      82             : #include <memory>
      83             : #include <utility>
      84             : 
      85             : namespace llvm {
      86             : 
      87             : class DominatorTree;
      88             : class Function;
      89             : class Instruction;
      90             : class MemoryAccess;
      91             : class LLVMContext;
      92             : class raw_ostream;
      93             : 
      94             : enum PredicateType { PT_Branch, PT_Assume, PT_Switch };
      95             : 
      96             : // Base class for all predicate information we provide.
      97             : // All of our predicate information has at least a comparison.
      98             : class PredicateBase : public ilist_node<PredicateBase> {
      99             : public:
     100             :   PredicateType Type;
     101             :   // The original operand before we renamed it.
     102             :   // This can be use by passes, when destroying predicateinfo, to know
     103             :   // whether they can just drop the intrinsic, or have to merge metadata.
     104             :   Value *OriginalOp;
     105             :   PredicateBase(const PredicateBase &) = delete;
     106             :   PredicateBase &operator=(const PredicateBase &) = delete;
     107             :   PredicateBase() = delete;
     108           0 :   virtual ~PredicateBase() = default;
     109             : 
     110             : protected:
     111        1412 :   PredicateBase(PredicateType PT, Value *Op) : Type(PT), OriginalOp(Op) {}
     112             : };
     113             : 
     114         706 : class PredicateWithCondition : public PredicateBase {
     115             : public:
     116             :   Value *Condition;
     117             :   static bool classof(const PredicateBase *PB) {
     118             :     return PB->Type == PT_Assume || PB->Type == PT_Branch ||
     119             :            PB->Type == PT_Switch;
     120             :   }
     121             : 
     122             : protected:
     123             :   PredicateWithCondition(PredicateType PT, Value *Op, Value *Condition)
     124        1412 :       : PredicateBase(PT, Op), Condition(Condition) {}
     125             : };
     126             : 
     127             : // Provides predicate information for assumes.  Since assumes are always true,
     128             : // we simply provide the assume instruction, so you can tell your relative
     129             : // position to it.
     130          56 : class PredicateAssume : public PredicateWithCondition {
     131             : public:
     132             :   IntrinsicInst *AssumeInst;
     133             :   PredicateAssume(Value *Op, IntrinsicInst *AssumeInst, Value *Condition)
     134          28 :       : PredicateWithCondition(PT_Assume, Op, Condition),
     135          56 :         AssumeInst(AssumeInst) {}
     136             :   PredicateAssume() = delete;
     137             :   static bool classof(const PredicateBase *PB) {
     138             :     return PB->Type == PT_Assume;
     139             :   }
     140             : };
     141             : 
     142             : // Mixin class for edge predicates.  The FROM block is the block where the
     143             : // predicate originates, and the TO block is the block where the predicate is
     144             : // valid.
     145        1356 : class PredicateWithEdge : public PredicateWithCondition {
     146             : public:
     147             :   BasicBlock *From;
     148             :   BasicBlock *To;
     149             :   PredicateWithEdge() = delete;
     150             :   static bool classof(const PredicateBase *PB) {
     151         847 :     return PB->Type == PT_Branch || PB->Type == PT_Switch;
     152             :   }
     153             : 
     154             : protected:
     155             :   PredicateWithEdge(PredicateType PType, Value *Op, BasicBlock *From,
     156             :                     BasicBlock *To, Value *Cond)
     157        1356 :       : PredicateWithCondition(PType, Op, Cond), From(From), To(To) {}
     158             : };
     159             : 
     160             : // Provides predicate information for branches.
     161        1340 : class PredicateBranch : public PredicateWithEdge {
     162             : public:
     163             :   // If true, SplitBB is the true successor, otherwise it's the false successor.
     164             :   bool TrueEdge;
     165             :   PredicateBranch(Value *Op, BasicBlock *BranchBB, BasicBlock *SplitBB,
     166             :                   Value *Condition, bool TakenEdge)
     167         670 :       : PredicateWithEdge(PT_Branch, Op, BranchBB, SplitBB, Condition),
     168        1340 :         TrueEdge(TakenEdge) {}
     169             :   PredicateBranch() = delete;
     170             :   static bool classof(const PredicateBase *PB) {
     171             :     return PB->Type == PT_Branch;
     172             :   }
     173             : };
     174             : 
     175          16 : class PredicateSwitch : public PredicateWithEdge {
     176             : public:
     177             :   Value *CaseValue;
     178             :   // This is the switch instruction.
     179             :   SwitchInst *Switch;
     180             :   PredicateSwitch(Value *Op, BasicBlock *SwitchBB, BasicBlock *TargetBB,
     181             :                   Value *CaseValue, SwitchInst *SI)
     182           8 :       : PredicateWithEdge(PT_Switch, Op, SwitchBB, TargetBB,
     183             :                           SI->getCondition()),
     184          24 :         CaseValue(CaseValue), Switch(SI) {}
     185             :   PredicateSwitch() = delete;
     186             :   static bool classof(const PredicateBase *PB) {
     187             :     return PB->Type == PT_Switch;
     188             :   }
     189             : };
     190             : 
     191             : // This name is used in a few places, so kick it into their own namespace
     192             : namespace PredicateInfoClasses {
     193             : struct ValueDFS;
     194             : }
     195             : 
     196             : /// \brief Encapsulates PredicateInfo, including all data associated with memory
     197             : /// accesses.
     198             : class PredicateInfo {
     199             : private:
     200             :   // Used to store information about each value we might rename.
     201        4188 :   struct ValueInfo {
     202             :     // Information about each possible copy. During processing, this is each
     203             :     // inserted info. After processing, we move the uninserted ones to the
     204             :     // uninserted vector.
     205             :     SmallVector<PredicateBase *, 4> Infos;
     206             :     SmallVector<PredicateBase *, 4> UninsertedInfos;
     207             :   };
     208             :   // This owns the all the predicate infos in the function, placed or not.
     209             :   iplist<PredicateBase> AllInfos;
     210             : 
     211             : public:
     212             :   PredicateInfo(Function &, DominatorTree &, AssumptionCache &);
     213             :   ~PredicateInfo();
     214             : 
     215             :   void verifyPredicateInfo() const;
     216             : 
     217             :   void dump() const;
     218             :   void print(raw_ostream &) const;
     219             : 
     220             :   const PredicateBase *getPredicateInfoFor(const Value *V) const {
     221        3270 :     return PredicateMap.lookup(V);
     222             :   }
     223             : 
     224             : protected:
     225             :   // Used by PredicateInfo annotater, dumpers, and wrapper pass.
     226             :   friend class PredicateInfoAnnotatedWriter;
     227             :   friend class PredicateInfoPrinterLegacyPass;
     228             : 
     229             : private:
     230             :   void buildPredicateInfo();
     231             :   void processAssume(IntrinsicInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
     232             :   void processBranch(BranchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
     233             :   void processSwitch(SwitchInst *, BasicBlock *, SmallPtrSetImpl<Value *> &);
     234             :   void renameUses(SmallPtrSetImpl<Value *> &);
     235             :   using ValueDFS = PredicateInfoClasses::ValueDFS;
     236             :   typedef SmallVectorImpl<ValueDFS> ValueDFSStack;
     237             :   void convertUsesToDFSOrdered(Value *, SmallVectorImpl<ValueDFS> &);
     238             :   Value *materializeStack(unsigned int &, ValueDFSStack &, Value *);
     239             :   bool stackIsInScope(const ValueDFSStack &, const ValueDFS &) const;
     240             :   void popStackUntilDFSScope(ValueDFSStack &, const ValueDFS &);
     241             :   ValueInfo &getOrCreateValueInfo(Value *);
     242             :   void addInfoFor(SmallPtrSetImpl<Value *> &OpsToRename, Value *Op,
     243             :                   PredicateBase *PB);
     244             :   const ValueInfo &getValueInfo(Value *) const;
     245             :   Function &F;
     246             :   DominatorTree &DT;
     247             :   AssumptionCache &AC;
     248             :   OrderedInstructions OI;
     249             :   // This maps from copy operands to Predicate Info. Note that it does not own
     250             :   // the Predicate Info, they belong to the ValueInfo structs in the ValueInfos
     251             :   // vector.
     252             :   DenseMap<const Value *, const PredicateBase *> PredicateMap;
     253             :   // This stores info about each operand or comparison result we make copies
     254             :   // of.  The real ValueInfos start at index 1, index 0 is unused so that we can
     255             :   // more easily detect invalid indexing.
     256             :   SmallVector<ValueInfo, 32> ValueInfos;
     257             :   // This gives the index into the ValueInfos array for a given Value.  Because
     258             :   // 0 is not a valid Value Info index, you can use DenseMap::lookup and tell
     259             :   // whether it returned a valid result.
     260             :   DenseMap<Value *, unsigned int> ValueInfoNums;
     261             :   // The set of edges along which we can only handle phi uses, due to critical
     262             :   // edges.
     263             :   DenseSet<std::pair<BasicBlock *, BasicBlock *>> EdgeUsesOnly;
     264             : };
     265             : 
     266             : // This pass does eager building and then printing of PredicateInfo. It is used
     267             : // by
     268             : // the tests to be able to build, dump, and verify PredicateInfo.
     269          12 : class PredicateInfoPrinterLegacyPass : public FunctionPass {
     270             : public:
     271             :   PredicateInfoPrinterLegacyPass();
     272             : 
     273             :   static char ID;
     274             :   bool runOnFunction(Function &) override;
     275             :   void getAnalysisUsage(AnalysisUsage &AU) const override;
     276             : };
     277             : 
     278             : /// \brief Printer pass for \c PredicateInfo.
     279             : class PredicateInfoPrinterPass
     280             :     : public PassInfoMixin<PredicateInfoPrinterPass> {
     281             :   raw_ostream &OS;
     282             : 
     283             : public:
     284             :   explicit PredicateInfoPrinterPass(raw_ostream &OS) : OS(OS) {}
     285             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     286             : };
     287             : 
     288             : /// \brief Verifier pass for \c PredicateInfo.
     289             : struct PredicateInfoVerifierPass : PassInfoMixin<PredicateInfoVerifierPass> {
     290             :   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
     291             : };
     292             : 
     293             : } // end namespace llvm
     294             : 
     295             : #endif // LLVM_TRANSFORMS_UTILS_PREDICATEINFO_H

Generated by: LCOV version 1.13