lib/Analysis/AssumptionCache.cpp

   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 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
  57 void AssumptionCache::updateAffectedValues(CallInst *CI) {
  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
 169 void AssumptionCache::registerAssumption(CallInst *CI) {
 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
 208 PreservedAnalyses AssumptionPrinterPass::run(Function &F,
 209                                              FunctionAnalysisManager &AM) {
 210   AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
 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
 227 AssumptionCache &AssumptionCacheTracker::getAssumptionCache(Function &F) {
 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
 244 void AssumptionCacheTracker::verifyAnalysis() const {
 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.
 249   if (!VerifyAssumptionCache)
 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
 266 AssumptionCacheTracker::AssumptionCacheTracker() : ImmutablePass(ID) {
 267   initializeAssumptionCacheTrackerPass(*PassRegistry::getPassRegistry());
 268 }
 269
 270 AssumptionCacheTracker::~AssumptionCacheTracker() = default;
 271
 272 char AssumptionCacheTracker::ID = 0;
 273
 274 INITIALIZE_PASS(AssumptionCacheTracker, "assumption-cache-tracker",
 275                 "Assumption Cache Tracker", false, true)