contrib/llvm/include/llvm/Transforms/Utils/PredicateInfo.h

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