LLVM  6.0.0svn
AssumptionCache.cpp
Go to the documentation of this file.
1 //===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===//
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 contains a pass that keeps track of @llvm.assume intrinsics in
11 // the functions of a module.
12 //
13 //===----------------------------------------------------------------------===//
14 
16 #include "llvm/ADT/STLExtras.h"
17 #include "llvm/ADT/SmallPtrSet.h"
18 #include "llvm/ADT/SmallVector.h"
19 #include "llvm/IR/BasicBlock.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/IR/InstrTypes.h"
22 #include "llvm/IR/Instruction.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/Intrinsics.h"
25 #include "llvm/IR/PassManager.h"
26 #include "llvm/IR/PatternMatch.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Support/Casting.h"
32 #include <algorithm>
33 #include <cassert>
34 #include <utility>
35 
36 using namespace llvm;
37 using namespace llvm::PatternMatch;
38 
39 static cl::opt<bool>
40  VerifyAssumptionCache("verify-assumption-cache", cl::Hidden,
41  cl::desc("Enable verification of assumption cache"),
42  cl::init(false));
43 
45 AssumptionCache::getOrInsertAffectedValues(Value *V) {
46  // Try using find_as first to avoid creating extra value handles just for the
47  // purpose of doing the lookup.
48  auto AVI = AffectedValues.find_as(V);
49  if (AVI != AffectedValues.end())
50  return AVI->second;
51 
52  auto AVIP = AffectedValues.insert(
53  {AffectedValueCallbackVH(V, this), SmallVector<WeakTrackingVH, 1>()});
54  return AVIP.first->second;
55 }
56 
58  // Note: This code must be kept in-sync with the code in
59  // computeKnownBitsFromAssume in ValueTracking.
60 
61  SmallVector<Value *, 16> Affected;
62  auto AddAffected = [&Affected](Value *V) {
63  if (isa<Argument>(V)) {
64  Affected.push_back(V);
65  } else if (auto *I = dyn_cast<Instruction>(V)) {
66  Affected.push_back(I);
67 
68  // Peek through unary operators to find the source of the condition.
69  Value *Op;
70  if (match(I, m_BitCast(m_Value(Op))) ||
71  match(I, m_PtrToInt(m_Value(Op))) ||
72  match(I, m_Not(m_Value(Op)))) {
73  if (isa<Instruction>(Op) || isa<Argument>(Op))
74  Affected.push_back(Op);
75  }
76  }
77  };
78 
79  Value *Cond = CI->getArgOperand(0), *A, *B;
80  AddAffected(Cond);
81 
82  CmpInst::Predicate Pred;
83  if (match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
84  AddAffected(A);
85  AddAffected(B);
86 
87  if (Pred == ICmpInst::ICMP_EQ) {
88  // For equality comparisons, we handle the case of bit inversion.
89  auto AddAffectedFromEq = [&AddAffected](Value *V) {
90  Value *A;
91  if (match(V, m_Not(m_Value(A)))) {
92  AddAffected(A);
93  V = A;
94  }
95 
96  Value *B;
97  ConstantInt *C;
98  // (A & B) or (A | B) or (A ^ B).
99  if (match(V, m_BitwiseLogic(m_Value(A), m_Value(B)))) {
100  AddAffected(A);
101  AddAffected(B);
102  // (A << C) or (A >>_s C) or (A >>_u C) where C is some constant.
103  } else if (match(V, m_Shift(m_Value(A), m_ConstantInt(C)))) {
104  AddAffected(A);
105  }
106  };
107 
108  AddAffectedFromEq(A);
109  AddAffectedFromEq(B);
110  }
111  }
112 
113  for (auto &AV : Affected) {
114  auto &AVV = getOrInsertAffectedValues(AV);
115  if (std::find(AVV.begin(), AVV.end(), CI) == AVV.end())
116  AVV.push_back(CI);
117  }
118 }
119 
120 void AssumptionCache::AffectedValueCallbackVH::deleted() {
121  auto AVI = AC->AffectedValues.find(getValPtr());
122  if (AVI != AC->AffectedValues.end())
123  AC->AffectedValues.erase(AVI);
124  // 'this' now dangles!
125 }
126 
127 void AssumptionCache::copyAffectedValuesInCache(Value *OV, Value *NV) {
128  auto &NAVV = getOrInsertAffectedValues(NV);
129  auto AVI = AffectedValues.find(OV);
130  if (AVI == AffectedValues.end())
131  return;
132 
133  for (auto &A : AVI->second)
134  if (std::find(NAVV.begin(), NAVV.end(), A) == NAVV.end())
135  NAVV.push_back(A);
136 }
137 
138 void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
139  if (!isa<Instruction>(NV) && !isa<Argument>(NV))
140  return;
141 
142  // Any assumptions that affected this value now affect the new value.
143 
144  AC->copyAffectedValuesInCache(getValPtr(), NV);
145  // 'this' now might dangle! If the AffectedValues map was resized to add an
146  // entry for NV then this object might have been destroyed in favor of some
147  // copy in the grown map.
148 }
149 
150 void AssumptionCache::scanFunction() {
151  assert(!Scanned && "Tried to scan the function twice!");
152  assert(AssumeHandles.empty() && "Already have assumes when scanning!");
153 
154  // Go through all instructions in all blocks, add all calls to @llvm.assume
155  // to this cache.
156  for (BasicBlock &B : F)
157  for (Instruction &II : B)
158  if (match(&II, m_Intrinsic<Intrinsic::assume>()))
159  AssumeHandles.push_back(&II);
160 
161  // Mark the scan as complete.
162  Scanned = true;
163 
164  // Update affected values.
165  for (auto &A : AssumeHandles)
166  updateAffectedValues(cast<CallInst>(A));
167 }
168 
170  assert(match(CI, m_Intrinsic<Intrinsic::assume>()) &&
171  "Registered call does not call @llvm.assume");
172 
173  // If we haven't scanned the function yet, just drop this assumption. It will
174  // be found when we scan later.
175  if (!Scanned)
176  return;
177 
178  AssumeHandles.push_back(CI);
179 
180 #ifndef NDEBUG
181  assert(CI->getParent() &&
182  "Cannot register @llvm.assume call not in a basic block");
183  assert(&F == CI->getParent()->getParent() &&
184  "Cannot register @llvm.assume call not in this function");
185 
186  // We expect the number of assumptions to be small, so in an asserts build
187  // check that we don't accumulate duplicates and that all assumptions point
188  // to the same function.
189  SmallPtrSet<Value *, 16> AssumptionSet;
190  for (auto &VH : AssumeHandles) {
191  if (!VH)
192  continue;
193 
194  assert(&F == cast<Instruction>(VH)->getParent()->getParent() &&
195  "Cached assumption not inside this function!");
196  assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
197  "Cached something other than a call to @llvm.assume!");
198  assert(AssumptionSet.insert(VH).second &&
199  "Cache contains multiple copies of a call!");
200  }
201 #endif
202 
203  updateAffectedValues(CI);
204 }
205 
206 AnalysisKey AssumptionAnalysis::Key;
207 
211 
212  OS << "Cached assumptions for function: " << F.getName() << "\n";
213  for (auto &VH : AC.assumptions())
214  if (VH)
215  OS << " " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";
216 
217  return PreservedAnalyses::all();
218 }
219 
220 void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
221  auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
222  if (I != ACT->AssumptionCaches.end())
223  ACT->AssumptionCaches.erase(I);
224  // 'this' now dangles!
225 }
226 
228  // We probe the function map twice to try and avoid creating a value handle
229  // around the function in common cases. This makes insertion a bit slower,
230  // but if we have to insert we're going to scan the whole function so that
231  // shouldn't matter.
232  auto I = AssumptionCaches.find_as(&F);
233  if (I != AssumptionCaches.end())
234  return *I->second;
235 
236  // Ok, build a new cache by scanning the function, insert it and the value
237  // handle into our map, and return the newly populated cache.
238  auto IP = AssumptionCaches.insert(std::make_pair(
239  FunctionCallbackVH(&F, this), llvm::make_unique<AssumptionCache>(F)));
240  assert(IP.second && "Scanning function already in the map?");
241  return *IP.first->second;
242 }
243 
245  // FIXME: In the long term the verifier should not be controllable with a
246  // flag. We should either fix all passes to correctly update the assumption
247  // cache and enable the verifier unconditionally or somehow arrange for the
248  // assumption list to be updated automatically by passes.
250  return;
251 
252  SmallPtrSet<const CallInst *, 4> AssumptionSet;
253  for (const auto &I : AssumptionCaches) {
254  for (auto &VH : I.second->assumptions())
255  if (VH)
256  AssumptionSet.insert(cast<CallInst>(VH));
257 
258  for (const BasicBlock &B : cast<Function>(*I.first))
259  for (const Instruction &II : B)
260  if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
261  !AssumptionSet.count(cast<CallInst>(&II)))
262  report_fatal_error("Assumption in scanned function not in cache");
263  }
264 }
265 
268 }
269 
271 
273 
274 INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
275  "Assumption Cache Tracker", false, true)
uint64_t CallInst * C
class_match< Value > m_Value()
Match an arbitrary value and ignore it.
Definition: PatternMatch.h:72
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
DiagnosticInfoOptimizationBase::Argument NV
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:687
LLVM_ATTRIBUTE_NORETURN void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:115
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
This class represents a function call, abstracting a target machine&#39;s calling convention.
An immutable pass that tracks lazily created AssumptionCache objects.
A cache of .assume calls within a function.
F(f)
MutableArrayRef< WeakTrackingVH > assumptions()
Access the list of assumption handles currently tracked for this function.
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
not_match< LHS > m_Not(const LHS &L)
Definition: PatternMatch.h:985
class_match< ConstantInt > m_ConstantInt()
Match an arbitrary ConstantInt and ignore it.
Definition: PatternMatch.h:83
initializer< Ty > init(const Ty &Val)
Definition: CommandLine.h:406
static GCRegistry::Add< OcamlGC > B("ocaml", "ocaml 3.10-compatible GC")
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
CastClass_match< OpTy, Instruction::BitCast > m_BitCast(const OpTy &Op)
Matches BitCast.
Definition: PatternMatch.h:900
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:371
Predicate
This enumeration lists the possible predicates for CmpInst subclasses.
Definition: InstrTypes.h:853
BinOpPred_match< LHS, RHS, is_bitwiselogic_op > m_BitwiseLogic(const LHS &L, const RHS &R)
Matches bitwise logic operations.
Definition: PatternMatch.h:773
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:382
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:34
A function analysis which provides an AssumptionCache.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This is the shared class of boolean and integer constants.
Definition: Constants.h:84
ImmutablePass class - This class is used to provide information that does not need to be run...
Definition: Pass.h:256
auto find(R &&Range, const T &Val) -> decltype(std::begin(Range))
Provide wrappers to std::find which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:788
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:864
void updateAffectedValues(CallInst *CI)
Update the cache of values being affected by this assumption (i.e.
CastClass_match< OpTy, Instruction::PtrToInt > m_PtrToInt(const OpTy &Op)
Matches PtrToInt.
Definition: PatternMatch.h:906
BinOpPred_match< LHS, RHS, is_shift_op > m_Shift(const LHS &L, const RHS &R)
Matches shift operations.
Definition: PatternMatch.h:751
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:482
void registerAssumption(CallInst *CI)
Add an .assume intrinsic to this function&#39;s cache.
Value * getArgOperand(unsigned i) const
getArgOperand/setArgOperand - Return/set the i-th call argument.
StringRef getName() const
Return a constant reference to the value&#39;s name.
Definition: Value.cpp:220
const Function * getParent() const
Return the enclosing method, or null if none.
Definition: BasicBlock.h:108
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
static const Function * getParent(const Value *V)
static cl::opt< bool > VerifyAssumptionCache("verify-assumption-cache", cl::Hidden, cl::desc("Enable verification of assumption cache"), cl::init(false))
AssumptionCache & getAssumptionCache(Function &F)
Get the cached assumptions for a function.
A container for analyses that lazily runs them and caches their results.
void initializeAssumptionCacheTrackerPass(PassRegistry &)
void verifyAnalysis() const override
verifyAnalysis() - This member can be implemented by a analysis pass to check state of analysis infor...
This header defines various interfaces for pass management in LLVM.
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
const BasicBlock * getParent() const
Definition: Instruction.h:66
CmpClass_match< LHS, RHS, ICmpInst, ICmpInst::Predicate > m_ICmp(ICmpInst::Predicate &Pred, const LHS &L, const RHS &R)
Definition: PatternMatch.h:837