Coverage Report

Created: 2017-10-03 07:32

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/lib/Analysis/AssumptionCache.cpp
Line
Count
Source (jump to first uncovered line)
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
15
#include "llvm/Analysis/AssumptionCache.h"
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"
29
#include "llvm/Support/CommandLine.h"
30
#include "llvm/Support/ErrorHandling.h"
31
#include "llvm/Support/raw_ostream.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
44
SmallVector<WeakTrackingVH, 1> &
45
7.85k
AssumptionCache::getOrInsertAffectedValues(Value *V) {
46
7.85k
  // Try using find_as first to avoid creating extra value handles just for the
47
7.85k
  // purpose of doing the lookup.
48
7.85k
  auto AVI = AffectedValues.find_as(V);
49
7.85k
  if (AVI != AffectedValues.end())
50
3.97k
    return AVI->second;
51
3.87k
52
3.87k
  auto AVIP = AffectedValues.insert(
53
3.87k
      {AffectedValueCallbackVH(V, this), SmallVector<WeakTrackingVH, 1>()});
54
3.87k
  return AVIP.first->second;
55
3.87k
}
56
57
3.85k
void AssumptionCache::updateAffectedValues(CallInst *CI) {
58
3.85k
  // Note: This code must be kept in-sync with the code in
59
3.85k
  // computeKnownBitsFromAssume in ValueTracking.
60
3.85k
61
3.85k
  SmallVector<Value *, 16> Affected;
62
11.5k
  auto AddAffected = [&Affected](Value *V) {
63
11.5k
    if (
isa<Argument>(V)11.5k
) {
64
174
      Affected.push_back(V);
65
11.5k
    } else 
if (auto *11.4k
I11.4k
= dyn_cast<Instruction>(V)) {
66
7.56k
      Affected.push_back(I);
67
7.56k
68
7.56k
      // Peek through unary operators to find the source of the condition.
69
7.56k
      Value *Op;
70
7.56k
      if (match(I, m_BitCast(m_Value(Op))) ||
71
7.56k
          match(I, m_PtrToInt(m_Value(Op))) ||
72
7.56k
          
match(I, m_Not(m_Value(Op)))7.47k
) {
73
105
        if (
isa<Instruction>(Op) || 105
isa<Argument>(Op)70
)
74
103
          Affected.push_back(Op);
75
105
      }
76
11.4k
    }
77
11.5k
  };
78
3.85k
79
3.85k
  Value *Cond = CI->getArgOperand(0), *A, *B;
80
3.85k
  AddAffected(Cond);
81
3.85k
82
3.85k
  CmpInst::Predicate Pred;
83
3.85k
  if (
match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))3.85k
) {
84
3.72k
    AddAffected(A);
85
3.72k
    AddAffected(B);
86
3.72k
87
3.72k
    if (
Pred == ICmpInst::ICMP_EQ3.72k
) {
88
476
      // For equality comparisons, we handle the case of bit inversion.
89
952
      auto AddAffectedFromEq = [&AddAffected](Value *V) {
90
952
        Value *A;
91
952
        if (
match(V, m_Not(m_Value(A)))952
) {
92
2
          AddAffected(A);
93
2
          V = A;
94
2
        }
95
952
96
952
        Value *B;
97
952
        ConstantInt *C;
98
952
        // (A & B) or (A | B) or (A ^ B).
99
952
        if (
match(V, m_BitwiseLogic(m_Value(A), m_Value(B)))952
) {
100
134
          AddAffected(A);
101
134
          AddAffected(B);
102
134
        // (A << C) or (A >>_s C) or (A >>_u C) where C is some constant.
103
952
        } else 
if (818
match(V, m_Shift(m_Value(A), m_ConstantInt(C)))818
) {
104
3
          AddAffected(A);
105
3
        }
106
952
      };
107
476
108
476
      AddAffectedFromEq(A);
109
476
      AddAffectedFromEq(B);
110
476
    }
111
3.72k
  }
112
3.85k
113
7.84k
  for (auto &AV : Affected) {
114
7.84k
    auto &AVV = getOrInsertAffectedValues(AV);
115
7.84k
    if (std::find(AVV.begin(), AVV.end(), CI) == AVV.end())
116
7.08k
      AVV.push_back(CI);
117
7.84k
  }
118
3.85k
}
119
120
84
void AssumptionCache::AffectedValueCallbackVH::deleted() {
121
84
  auto AVI = AC->AffectedValues.find(getValPtr());
122
84
  if (AVI != AC->AffectedValues.end())
123
84
    AC->AffectedValues.erase(AVI);
124
84
  // 'this' now dangles!
125
84
}
126
127
15
void AssumptionCache::copyAffectedValuesInCache(Value *OV, Value *NV) {
128
15
  auto &NAVV = getOrInsertAffectedValues(NV);
129
15
  auto AVI = AffectedValues.find(OV);
130
15
  if (AVI == AffectedValues.end())
131
0
    return;
132
15
133
15
  for (auto &A : AVI->second)
134
15
    
if (15
std::find(NAVV.begin(), NAVV.end(), A) == NAVV.end()15
)
135
15
      NAVV.push_back(A);
136
15
}
137
138
29
void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
139
29
  if (
!isa<Instruction>(NV) && 29
!isa<Argument>(NV)14
)
140
14
    return;
141
15
142
15
  // Any assumptions that affected this value now affect the new value.
143
15
144
15
  AC->copyAffectedValuesInCache(getValPtr(), NV);
145
15
  // 'this' now might dangle! If the AffectedValues map was resized to add an
146
15
  // entry for NV then this object might have been destroyed in favor of some
147
15
  // copy in the grown map.
148
15
}
149
150
1.10M
void AssumptionCache::scanFunction() {
151
1.10M
  assert(!Scanned && "Tried to scan the function twice!");
152
1.10M
  assert(AssumeHandles.empty() && "Already have assumes when scanning!");
153
1.10M
154
1.10M
  // Go through all instructions in all blocks, add all calls to @llvm.assume
155
1.10M
  // to this cache.
156
1.10M
  for (BasicBlock &B : F)
157
9.56M
    for (Instruction &II : B)
158
54.9M
      
if (54.9M
match(&II, m_Intrinsic<Intrinsic::assume>())54.9M
)
159
3.39k
        AssumeHandles.push_back(&II);
160
1.10M
161
1.10M
  // Mark the scan as complete.
162
1.10M
  Scanned = true;
163
1.10M
164
1.10M
  // Update affected values.
165
1.10M
  for (auto &A : AssumeHandles)
166
3.39k
    updateAffectedValues(cast<CallInst>(A));
167
1.10M
}
168
169
7.10k
void AssumptionCache::registerAssumption(CallInst *CI) {
170
7.10k
  assert(match(CI, m_Intrinsic<Intrinsic::assume>()) &&
171
7.10k
         "Registered call does not call @llvm.assume");
172
7.10k
173
7.10k
  // If we haven't scanned the function yet, just drop this assumption. It will
174
7.10k
  // be found when we scan later.
175
7.10k
  if (!Scanned)
176
7.03k
    return;
177
77
178
77
  AssumeHandles.push_back(CI);
179
77
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
7.10k
  updateAffectedValues(CI);
204
7.10k
}
205
206
AnalysisKey AssumptionAnalysis::Key;
207
208
PreservedAnalyses AssumptionPrinterPass::run(Function &F,
209
1
                                             FunctionAnalysisManager &AM) {
210
1
  AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
211
1
212
1
  OS << "Cached assumptions for function: " << F.getName() << "\n";
213
1
  for (auto &VH : AC.assumptions())
214
3
    
if (3
VH3
)
215
3
      OS << "  " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";
216
1
217
1
  return PreservedAnalyses::all();
218
1
}
219
220
383k
void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
221
383k
  auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
222
383k
  if (I != ACT->AssumptionCaches.end())
223
383k
    ACT->AssumptionCaches.erase(I);
224
383k
  // 'this' now dangles!
225
383k
}
226
227
43.9M
AssumptionCache &AssumptionCacheTracker::getAssumptionCache(Function &F) {
228
43.9M
  // We probe the function map twice to try and avoid creating a value handle
229
43.9M
  // around the function in common cases. This makes insertion a bit slower,
230
43.9M
  // but if we have to insert we're going to scan the whole function so that
231
43.9M
  // shouldn't matter.
232
43.9M
  auto I = AssumptionCaches.find_as(&F);
233
43.9M
  if (I != AssumptionCaches.end())
234
41.8M
    return *I->second;
235
2.15M
236
2.15M
  // Ok, build a new cache by scanning the function, insert it and the value
237
2.15M
  // handle into our map, and return the newly populated cache.
238
2.15M
  auto IP = AssumptionCaches.insert(std::make_pair(
239
2.15M
      FunctionCallbackVH(&F, this), llvm::make_unique<AssumptionCache>(F)));
240
2.15M
  assert(IP.second && "Scanning function already in the map?");
241
2.15M
  return *IP.first->second;
242
2.15M
}
243
244
157k
void AssumptionCacheTracker::verifyAnalysis() const {
245
157k
  // FIXME: In the long term the verifier should not be controllable with a
246
157k
  // flag. We should either fix all passes to correctly update the assumption
247
157k
  // cache and enable the verifier unconditionally or somehow arrange for the
248
157k
  // assumption list to be updated automatically by passes.
249
157k
  if (!VerifyAssumptionCache)
250
157k
    return;
251
1
252
1
  SmallPtrSet<const CallInst *, 4> AssumptionSet;
253
1
  for (const auto &I : AssumptionCaches) {
254
1
    for (auto &VH : I.second->assumptions())
255
2
      
if (2
VH2
)
256
2
        AssumptionSet.insert(cast<CallInst>(VH));
257
1
258
1
    for (const BasicBlock &B : cast<Function>(*I.first))
259
6
      for (const Instruction &II : B)
260
22
        
if (22
match(&II, m_Intrinsic<Intrinsic::assume>()) &&
261
2
            !AssumptionSet.count(cast<CallInst>(&II)))
262
0
          report_fatal_error("Assumption in scanned function not in cache");
263
1
  }
264
157k
}
265
266
78.2k
AssumptionCacheTracker::AssumptionCacheTracker() : ImmutablePass(ID) {
267
78.2k
  initializeAssumptionCacheTrackerPass(*PassRegistry::getPassRegistry());
268
78.2k
}
269
270
78.1k
AssumptionCacheTracker::~AssumptionCacheTracker() = default;
271
272
char AssumptionCacheTracker::ID = 0;
273
274
INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
275
                "Assumption Cache Tracker", false, true)