include/llvm/Transforms/Utils/PredicateInfo.h

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