Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/lib/Analysis/AssumptionCache.cpp
Line
Count
Source (jump to first uncovered line)
1
//===- AssumptionCache.cpp - Cache finding @llvm.assume calls -------------===//
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
// This file contains a pass that keeps track of @llvm.assume intrinsics in
10
// the functions of a module.
11
//
12
//===----------------------------------------------------------------------===//
13
14
#include "llvm/Analysis/AssumptionCache.h"
15
#include "llvm/ADT/STLExtras.h"
16
#include "llvm/ADT/SmallPtrSet.h"
17
#include "llvm/ADT/SmallVector.h"
18
#include "llvm/IR/BasicBlock.h"
19
#include "llvm/IR/Function.h"
20
#include "llvm/IR/InstrTypes.h"
21
#include "llvm/IR/Instruction.h"
22
#include "llvm/IR/Instructions.h"
23
#include "llvm/IR/Intrinsics.h"
24
#include "llvm/IR/PassManager.h"
25
#include "llvm/IR/PatternMatch.h"
26
#include "llvm/Pass.h"
27
#include "llvm/Support/Casting.h"
28
#include "llvm/Support/CommandLine.h"
29
#include "llvm/Support/ErrorHandling.h"
30
#include "llvm/Support/raw_ostream.h"
31
#include <algorithm>
32
#include <cassert>
33
#include <utility>
34
35
using namespace llvm;
36
using namespace llvm::PatternMatch;
37
38
static cl::opt<bool>
39
    VerifyAssumptionCache("verify-assumption-cache", cl::Hidden,
40
                          cl::desc("Enable verification of assumption cache"),
41
                          cl::init(false));
42
43
SmallVector<WeakTrackingVH, 1> &
44
8.19k
AssumptionCache::getOrInsertAffectedValues(Value *V) {
45
8.19k
  // Try using find_as first to avoid creating extra value handles just for the
46
8.19k
  // purpose of doing the lookup.
47
8.19k
  auto AVI = AffectedValues.find_as(V);
48
8.19k
  if (AVI != AffectedValues.end())
49
4.01k
    return AVI->second;
50
4.17k
51
4.17k
  auto AVIP = AffectedValues.insert(
52
4.17k
      {AffectedValueCallbackVH(V, this), SmallVector<WeakTrackingVH, 1>()});
53
4.17k
  return AVIP.first->second;
54
4.17k
}
55
56
static void findAffectedValues(CallInst *CI,
57
4.01k
                               SmallVectorImpl<Value *> &Affected) {
58
4.01k
  // Note: This code must be kept in-sync with the code in
59
4.01k
  // computeKnownBitsFromAssume in ValueTracking.
60
4.01k
61
11.9k
  auto AddAffected = [&Affected](Value *V) {
62
11.9k
    if (isa<Argument>(V)) {
63
233
      Affected.push_back(V);
64
11.7k
    } else if (auto *I = dyn_cast<Instruction>(V)) {
65
7.76k
      Affected.push_back(I);
66
7.76k
67
7.76k
      // Peek through unary operators to find the source of the condition.
68
7.76k
      Value *Op;
69
7.76k
      if (match(I, m_BitCast(m_Value(Op))) ||
70
7.76k
          
match(I, m_PtrToInt(m_Value(Op)))7.76k
||
71
7.76k
          
match(I, m_Not(m_Value(Op)))7.66k
) {
72
165
        if (isa<Instruction>(Op) || 
isa<Argument>(Op)75
)
73
163
          Affected.push_back(Op);
74
165
      }
75
7.76k
    }
76
11.9k
  };
77
4.01k
78
4.01k
  Value *Cond = CI->getArgOperand(0), *A, *B;
79
4.01k
  AddAffected(Cond);
80
4.01k
81
4.01k
  CmpInst::Predicate Pred;
82
4.01k
  if (match(Cond, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
83
3.81k
    AddAffected(A);
84
3.81k
    AddAffected(B);
85
3.81k
86
3.81k
    if (Pred == ICmpInst::ICMP_EQ) {
87
470
      // For equality comparisons, we handle the case of bit inversion.
88
940
      auto AddAffectedFromEq = [&AddAffected](Value *V) {
89
940
        Value *A;
90
940
        if (match(V, m_Not(m_Value(A)))) {
91
2
          AddAffected(A);
92
2
          V = A;
93
2
        }
94
940
95
940
        Value *B;
96
940
        ConstantInt *C;
97
940
        // (A & B) or (A | B) or (A ^ B).
98
940
        if (match(V, m_BitwiseLogic(m_Value(A), m_Value(B)))) {
99
141
          AddAffected(A);
100
141
          AddAffected(B);
101
141
        // (A << C) or (A >>_s C) or (A >>_u C) where C is some constant.
102
799
        } else if (match(V, m_Shift(m_Value(A), m_ConstantInt(C)))) {
103
7
          AddAffected(A);
104
7
        }
105
940
      };
106
470
107
470
      AddAffectedFromEq(A);
108
470
      AddAffectedFromEq(B);
109
470
    }
110
3.81k
  }
111
4.01k
}
112
113
4.01k
void AssumptionCache::updateAffectedValues(CallInst *CI) {
114
4.01k
  SmallVector<Value *, 16> Affected;
115
4.01k
  findAffectedValues(CI, Affected);
116
4.01k
117
8.15k
  for (auto &AV : Affected) {
118
8.15k
    auto &AVV = getOrInsertAffectedValues(AV);
119
8.15k
    if (std::find(AVV.begin(), AVV.end(), CI) == AVV.end())
120
7.38k
      AVV.push_back(CI);
121
8.15k
  }
122
4.01k
}
123
124
1
void AssumptionCache::unregisterAssumption(CallInst *CI) {
125
1
  SmallVector<Value *, 16> Affected;
126
1
  findAffectedValues(CI, Affected);
127
1
128
2
  for (auto &AV : Affected) {
129
2
    auto AVI = AffectedValues.find_as(AV);
130
2
    if (AVI != AffectedValues.end())
131
1
      AffectedValues.erase(AVI);
132
2
  }
133
1
  remove_if(AssumeHandles, [CI](WeakTrackingVH &VH) { return CI == VH; });
134
1
}
135
136
212
void AssumptionCache::AffectedValueCallbackVH::deleted() {
137
212
  auto AVI = AC->AffectedValues.find(getValPtr());
138
212
  if (AVI != AC->AffectedValues.end())
139
212
    AC->AffectedValues.erase(AVI);
140
212
  // 'this' now dangles!
141
212
}
142
143
32
void AssumptionCache::copyAffectedValuesInCache(Value *OV, Value *NV) {
144
32
  auto &NAVV = getOrInsertAffectedValues(NV);
145
32
  auto AVI = AffectedValues.find(OV);
146
32
  if (AVI == AffectedValues.end())
147
0
    return;
148
32
149
32
  for (auto &A : AVI->second)
150
33
    if (std::find(NAVV.begin(), NAVV.end(), A) == NAVV.end())
151
30
      NAVV.push_back(A);
152
32
}
153
154
157
void AssumptionCache::AffectedValueCallbackVH::allUsesReplacedWith(Value *NV) {
155
157
  if (!isa<Instruction>(NV) && 
!isa<Argument>(NV)125
)
156
125
    return;
157
32
158
32
  // Any assumptions that affected this value now affect the new value.
159
32
160
32
  AC->copyAffectedValuesInCache(getValPtr(), NV);
161
32
  // 'this' now might dangle! If the AffectedValues map was resized to add an
162
32
  // entry for NV then this object might have been destroyed in favor of some
163
32
  // copy in the grown map.
164
32
}
165
166
1.03M
void AssumptionCache::scanFunction() {
167
1.03M
  assert(!Scanned && "Tried to scan the function twice!");
168
1.03M
  assert(AssumeHandles.empty() && "Already have assumes when scanning!");
169
1.03M
170
1.03M
  // Go through all instructions in all blocks, add all calls to @llvm.assume
171
1.03M
  // to this cache.
172
1.03M
  for (BasicBlock &B : F)
173
6.22M
    for (Instruction &II : B)
174
37.1M
      if (match(&II, m_Intrinsic<Intrinsic::assume>()))
175
3.52k
        AssumeHandles.push_back(&II);
176
1.03M
177
1.03M
  // Mark the scan as complete.
178
1.03M
  Scanned = true;
179
1.03M
180
1.03M
  // Update affected values.
181
1.03M
  for (auto &A : AssumeHandles)
182
3.52k
    updateAffectedValues(cast<CallInst>(A));
183
1.03M
}
184
185
7.11k
void AssumptionCache::registerAssumption(CallInst *CI) {
186
7.11k
  assert(match(CI, m_Intrinsic<Intrinsic::assume>()) &&
187
7.11k
         "Registered call does not call @llvm.assume");
188
7.11k
189
7.11k
  // If we haven't scanned the function yet, just drop this assumption. It will
190
7.11k
  // be found when we scan later.
191
7.11k
  if (!Scanned)
192
7.03k
    return;
193
86
194
86
  AssumeHandles.push_back(CI);
195
86
196
#ifndef NDEBUG
197
  assert(CI->getParent() &&
198
         "Cannot register @llvm.assume call not in a basic block");
199
  assert(&F == CI->getParent()->getParent() &&
200
         "Cannot register @llvm.assume call not in this function");
201
202
  // We expect the number of assumptions to be small, so in an asserts build
203
  // check that we don't accumulate duplicates and that all assumptions point
204
  // to the same function.
205
  SmallPtrSet<Value *, 16> AssumptionSet;
206
  for (auto &VH : AssumeHandles) {
207
    if (!VH)
208
      continue;
209
210
    assert(&F == cast<Instruction>(VH)->getParent()->getParent() &&
211
           "Cached assumption not inside this function!");
212
    assert(match(cast<CallInst>(VH), m_Intrinsic<Intrinsic::assume>()) &&
213
           "Cached something other than a call to @llvm.assume!");
214
    assert(AssumptionSet.insert(VH).second &&
215
           "Cache contains multiple copies of a call!");
216
  }
217
#endif
218
219
86
  updateAffectedValues(CI);
220
86
}
221
222
AnalysisKey AssumptionAnalysis::Key;
223
224
PreservedAnalyses AssumptionPrinterPass::run(Function &F,
225
3
                                             FunctionAnalysisManager &AM) {
226
3
  AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
227
3
228
3
  OS << "Cached assumptions for function: " << F.getName() << "\n";
229
3
  for (auto &VH : AC.assumptions())
230
4
    if (VH)
231
4
      OS << "  " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";
232
3
233
3
  return PreservedAnalyses::all();
234
3
}
235
236
649k
void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
237
649k
  auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
238
649k
  if (I != ACT->AssumptionCaches.end())
239
649k
    ACT->AssumptionCaches.erase(I);
240
649k
  // 'this' now dangles!
241
649k
}
242
243
37.8M
AssumptionCache &AssumptionCacheTracker::getAssumptionCache(Function &F) {
244
37.8M
  // We probe the function map twice to try and avoid creating a value handle
245
37.8M
  // around the function in common cases. This makes insertion a bit slower,
246
37.8M
  // but if we have to insert we're going to scan the whole function so that
247
37.8M
  // shouldn't matter.
248
37.8M
  auto I = AssumptionCaches.find_as(&F);
249
37.8M
  if (I != AssumptionCaches.end())
250
35.9M
    return *I->second;
251
1.93M
252
1.93M
  // Ok, build a new cache by scanning the function, insert it and the value
253
1.93M
  // handle into our map, and return the newly populated cache.
254
1.93M
  auto IP = AssumptionCaches.insert(std::make_pair(
255
1.93M
      FunctionCallbackVH(&F, this), llvm::make_unique<AssumptionCache>(F)));
256
1.93M
  assert(IP.second && "Scanning function already in the map?");
257
1.93M
  return *IP.first->second;
258
1.93M
}
259
260
66
AssumptionCache *AssumptionCacheTracker::lookupAssumptionCache(Function &F) {
261
66
  auto I = AssumptionCaches.find_as(&F);
262
66
  if (I != AssumptionCaches.end())
263
10
    return I->second.get();
264
56
  return nullptr;
265
56
}
266
267
187k
void AssumptionCacheTracker::verifyAnalysis() const {
268
187k
  // FIXME: In the long term the verifier should not be controllable with a
269
187k
  // flag. We should either fix all passes to correctly update the assumption
270
187k
  // cache and enable the verifier unconditionally or somehow arrange for the
271
187k
  // assumption list to be updated automatically by passes.
272
187k
  if (!VerifyAssumptionCache)
273
187k
    return;
274
18.4E
275
18.4E
  SmallPtrSet<const CallInst *, 4> AssumptionSet;
276
18.4E
  for (const auto &I : AssumptionCaches) {
277
1
    for (auto &VH : I.second->assumptions())
278
2
      if (VH)
279
2
        AssumptionSet.insert(cast<CallInst>(VH));
280
1
281
1
    for (const BasicBlock &B : cast<Function>(*I.first))
282
5
      for (const Instruction &II : B)
283
21
        if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
284
21
            
!AssumptionSet.count(cast<CallInst>(&II))2
)
285
0
          report_fatal_error("Assumption in scanned function not in cache");
286
1
  }
287
18.4E
}
288
289
78.0k
AssumptionCacheTracker::AssumptionCacheTracker() : ImmutablePass(ID) {
290
78.0k
  initializeAssumptionCacheTrackerPass(*PassRegistry::getPassRegistry());
291
78.0k
}
292
293
77.8k
AssumptionCacheTracker::~AssumptionCacheTracker() = default;
294
295
char AssumptionCacheTracker::ID = 0;
296
297
INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
298
                "Assumption Cache Tracker", false, true)