Make AssumptionCache's interface return a range of Values

[yabash]

Summary

Instead of returning a range of WeakVHs,
forcing every user of the interface to check the WeakVH before using it,
return a range which filters out the null WeakVHs and dereferences it.

This is a fix for a FIXME by @djasper.

[yabash]

Fix comments and rebase.
Also, ping for reviews.

[yabash]

Ping

[hfinkel]

include/llvm/Analysis/AssumptionCache.h

125

Our general convention for variables is that they start with a capital letter (for acronyms, this sometimes means we have variable names in all caps, but that's okay). So:

wvh -> WVH

lib/Transforms/InstCombine/InstCombineSelect.cpp

1479

This line is more than 80 characters; please wrap.

[yabash]

Fixed and rebased.

[yabash]

Ping

[yabash]

Can someone review this please?

include/llvm/Analysis/AssumptionCache.h

public:
   ///
   /// It will be re-scanned the next time it is requested.
   void clear() {
     AssumeHandles.clear();
     AffectedValues.clear();
     Scanned = false;
   }
 
+  struct NullVHFilter {
+    bool operator()(const WeakVH& wvh) const {
+      return wvh;
+    }
+  };
+
+  using AssumptionRange = 
+      iterator_range<pointee_iterator<filter_iterator<WeakVH*, NullVHFilter>>>;
+
   /// \brief Access the list of assumption handles currently tracked for this
   /// function.
-  ///
-  /// Note that these produce weak handles that may be null. The caller must
-  /// handle that case.
-  /// FIXME: We should replace this with pointee_iterator<filter_iterator<...>>
-  /// when we can write that to filter out the null values. Then caller code
-  /// will become simpler.
-  MutableArrayRef<WeakVH> assumptions() {
+  AssumptionRange assumptions() {
     if (!Scanned)
       scanFunction();
-    return AssumeHandles;
+    return make_pointee_range(make_filter_range(AssumeHandles, 
+                                                NullVHFilter()));
   }
 
   /// \brief Access the list of assumptions which affect this value.
-  MutableArrayRef<WeakVH> assumptionsFor(const Value *V) {
+  AssumptionRange assumptionsFor(const Value *V) {
     if (!Scanned)
       scanFunction();
 
     auto AVI = AffectedValues.find_as(const_cast<Value *>(V));
     if (AVI == AffectedValues.end())
-      return MutableArrayRef<WeakVH>();
+      return make_pointee_range(make_filter_range(MutableArrayRef<WeakVH>(), 
+                                                  NullVHFilter()));
 
-    return AVI->second;
+    return make_pointee_range(make_filter_range(AVI->second, 
+                                                NullVHFilter()));
   }
 };
 
 /// \brief A function analysis which provides an \c AssumptionCache.
 ///
 /// This analysis is intended for use with the new pass manager and will vend
 /// assumption caches for a given function.
 class AssumptionAnalysis : public AnalysisInfoMixin<AssumptionAnalysis> {

lib/Analysis/AssumptionCache.cpp

 
 AnalysisKey AssumptionAnalysis::Key;
 
 PreservedAnalyses AssumptionPrinterPass::run(Function &F,
                                              FunctionAnalysisManager &AM) {
   AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);
 
   OS << "Cached assumptions for function: " << F.getName() << "\n";
-  for (auto &VH : AC.assumptions())
-    if (VH)
-      OS << "  " << *cast<CallInst>(VH)->getArgOperand(0) << "\n";
+  for (auto &V : AC.assumptions())
+    OS << "  " << *cast<CallInst>(V).getArgOperand(0) << "\n";
 
   return PreservedAnalyses::all();
 }
 
 void AssumptionCacheTracker::FunctionCallbackVH::deleted() {
   auto I = ACT->AssumptionCaches.find_as(cast<Function>(getValPtr()));
   if (I != ACT->AssumptionCaches.end())
     ACT->AssumptionCaches.erase(I);
void AssumptionCacheTracker::verifyAnalysis() const {
   // flag. We should either fix all passes to correctly update the assumption
   // cache and enable the verifier unconditionally or somehow arrange for the
   // assumption list to be updated automatically by passes.
   if (!VerifyAssumptionCache)
     return;
 
   SmallPtrSet<const CallInst *, 4> AssumptionSet;
   for (const auto &I : AssumptionCaches) {
-    for (auto &VH : I.second->assumptions())
-      if (VH)
-        AssumptionSet.insert(cast<CallInst>(VH));
+    for (auto &V : I.second->assumptions())
+      AssumptionSet.insert(cast<CallInst>(&V));
 
     for (const BasicBlock &B : cast<Function>(*I.first))
       for (const Instruction &II : B)
         if (match(&II, m_Intrinsic<Intrinsic::assume>()) &&
             !AssumptionSet.count(cast<CallInst>(&II)))
           report_fatal_error("Assumption in scanned function not in cache");
   }
 }

lib/Analysis/CodeMetrics.cpp

 
 // Find all ephemeral values.
 void CodeMetrics::collectEphemeralValues(
     const Loop *L, AssumptionCache *AC,
     SmallPtrSetImpl<const Value *> &EphValues) {
   SmallPtrSet<const Value *, 32> Visited;
   SmallVector<const Value *, 16> Worklist;
 
-  for (auto &AssumeVH : AC->assumptions()) {
-    if (!AssumeVH)
-      continue;
-    Instruction *I = cast<Instruction>(AssumeVH);
+  for (auto &AssumeV : AC->assumptions()) {
+    Instruction *I = cast<Instruction>(&AssumeV);
 
     // Filter out call sites outside of the loop so we don't do a function's
     // worth of work for each of its loops (and, in the common case, ephemeral
     // values in the loop are likely due to @llvm.assume calls in the loop).
     if (!L->contains(I->getParent()))
       continue;
 
     if (EphValues.insert(I).second)
       appendSpeculatableOperands(I, Visited, Worklist);
   }
 
   completeEphemeralValues(Visited, Worklist, EphValues);
 }
 
 void CodeMetrics::collectEphemeralValues(
     const Function *F, AssumptionCache *AC,
     SmallPtrSetImpl<const Value *> &EphValues) {
   SmallPtrSet<const Value *, 32> Visited;
   SmallVector<const Value *, 16> Worklist;
 
-  for (auto &AssumeVH : AC->assumptions()) {
-    if (!AssumeVH)
-      continue;
-    Instruction *I = cast<Instruction>(AssumeVH);
+  for (auto &AssumeV : AC->assumptions()) {
+    Instruction *I = cast<Instruction>(&AssumeV);
     assert(I->getParent()->getParent() == F &&
            "Found assumption for the wrong function!");
 
     if (EphValues.insert(I).second)
       appendSpeculatableOperands(I, Visited, Worklist);
   }
 
   completeEphemeralValues(Visited, Worklist, EphValues);

lib/Analysis/LazyValueInfo.cpp

 // If we can determine a constraint on the value given conditions assumed by
 // the program, intersect those constraints with BBLV
 void LazyValueInfoImpl::intersectAssumeOrGuardBlockValueConstantRange(
         Value *Val, LVILatticeVal &BBLV, Instruction *BBI) {
   BBI = BBI ? BBI : dyn_cast<Instruction>(Val);
   if (!BBI)
     return;
 
-  for (auto &AssumeVH : AC->assumptionsFor(Val)) {
-    if (!AssumeVH)
-      continue;
-    auto *I = cast<CallInst>(AssumeVH);
+  for (auto &AssumeV : AC->assumptionsFor(Val)) {
+    auto *I = cast<CallInst>(&AssumeV);
     if (!isValidAssumeForContext(I, BBI, DT))
       continue;
 
     BBLV = intersect(BBLV, getValueFromCondition(Val, I->getArgOperand(0)));
   }
 
   // If guards are not used in the module, don't spend time looking for them
   auto *GuardDecl = BBI->getModule()->getFunction(

lib/Analysis/ScalarEvolution.cpp

if (AR->isAffine()) {
 
       // Normally, in the cases we can prove no-overflow via a
       // backedge guarding condition, we can also compute a backedge
       // taken count for the loop.  The exceptions are assumptions and
       // guards present in the loop -- SCEV is not great at exploiting
       // these to compute max backedge taken counts, but can still use
       // these to prove lack of overflow.  Use this fact to avoid
       // doing extra work that may not pay off.
+      auto assumptions = AC.assumptions();
       if (!isa<SCEVCouldNotCompute>(MaxBECount) || HasGuards ||
-          !AC.assumptions().empty()) {
+          assumptions.begin() != assumptions.end()) {
         // If the backedge is guarded by a comparison with the pre-inc
         // value the addrec is safe. Also, if the entry is guarded by
         // a comparison with the start value and the backedge is
         // guarded by a comparison with the post-inc value, the addrec
         // is safe.
         if (isKnownPositive(Step)) {
           const SCEV *N = getConstant(APInt::getMinValue(BitWidth) -
                                       getUnsignedRange(Step).getUnsignedMax());
if (AR->isAffine()) {
 
       // Normally, in the cases we can prove no-overflow via a
       // backedge guarding condition, we can also compute a backedge
       // taken count for the loop.  The exceptions are assumptions and
       // guards present in the loop -- SCEV is not great at exploiting
       // these to compute max backedge taken counts, but can still use
       // these to prove lack of overflow.  Use this fact to avoid
       // doing extra work that may not pay off.
-
+      auto assumptions = AC.assumptions();
       if (!isa<SCEVCouldNotCompute>(MaxBECount) || HasGuards ||
-          !AC.assumptions().empty()) {
+          assumptions.begin() != assumptions.end()) {
         // If the backedge is guarded by a comparison with the pre-inc
         // value the addrec is safe. Also, if the entry is guarded by
         // a comparison with the start value and the backedge is
         // guarded by a comparison with the post-inc value, the addrec
         // is safe.
         ICmpInst::Predicate Pred;
         const SCEV *OverflowLimit =
             getSignedOverflowLimitForStep(Step, &Pred, this);
if (LatchBECount != getCouldNotCompute()) {
     const SCEV *LoopCounter =
       getAddRecExpr(getZero(Ty), getOne(Ty), L, NoWrapFlags);
     if (isImpliedCond(Pred, LHS, RHS, ICmpInst::ICMP_ULT, LoopCounter,
                       LatchBECount))
       return true;
   }
 
   // Check conditions due to any @llvm.assume intrinsics.
-  for (auto &AssumeVH : AC.assumptions()) {
-    if (!AssumeVH)
-      continue;
-    auto *CI = cast<CallInst>(AssumeVH);
+  for (auto &AssumeV : AC.assumptions()) {
+    auto *CI = cast<CallInst>(&AssumeV);
     if (!DT.dominates(CI, Latch->getTerminator()))
       continue;
 
     if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
       return true;
   }
 
   // If the loop is not reachable from the entry block, we risk running into an
for (std::pair<BasicBlock *, BasicBlock *>
 
     if (isImpliedCond(Pred, LHS, RHS,
                       LoopEntryPredicate->getCondition(),
                       LoopEntryPredicate->getSuccessor(0) != Pair.second))
       return true;
   }
 
   // Check conditions due to any @llvm.assume intrinsics.
-  for (auto &AssumeVH : AC.assumptions()) {
-    if (!AssumeVH)
-      continue;
-    auto *CI = cast<CallInst>(AssumeVH);
+  for (auto &AssumeV : AC.assumptions()) {
+    auto *CI = cast<CallInst>(&AssumeV);
     if (!DT.dominates(CI, L->getHeader()))
       continue;
 
     if (isImpliedCond(Pred, LHS, RHS, CI->getArgOperand(0), false))
       return true;
   }
 
   return false;

lib/Analysis/ValueTracking.cpp

static void computeKnownBitsFromAssume(const Value *V, APInt &KnownZero,
   if (!Q.AC || !Q.CxtI)
     return;
 
   unsigned BitWidth = KnownZero.getBitWidth();
 
   // Note that the patterns below need to be kept in sync with the code
   // in AssumptionCache::updateAffectedValues.
 
-  for (auto &AssumeVH : Q.AC->assumptionsFor(V)) {
-    if (!AssumeVH)
-      continue;
-    CallInst *I = cast<CallInst>(AssumeVH);
+  for (auto &AssumeV : Q.AC->assumptionsFor(V)) {
+    CallInst *I = cast<CallInst>(&AssumeV);
     assert(I->getParent()->getParent() == Q.CxtI->getParent()->getParent() &&
            "Got assumption for the wrong function!");
     if (Q.isExcluded(I))
       continue;
 
     // Warning: This loop can end up being somewhat performance sensetive.
     // We're running this loop for once for each value queried resulting in a
     // runtime of ~O(#assumes * #values).

lib/Transforms/InstCombine/InstCombineSelect.cpp

if (BasicBlock *Dom = Parent->getSinglePredecessor()) {
     }
   }
 
   // If we can compute the condition, there's no need for a select.
   // Like the above fold, we are attempting to reduce compile-time cost by
   // putting this fold here with limitations rather than in InstSimplify.
   // The motivation for this call into value tracking is to take advantage of
   // the assumption cache, so make sure that is populated.
-  if (!CondVal->getType()->isVectorTy() && !AC.assumptions().empty()) {
+  auto assumptions = AC.assumptions();
+  if (!CondVal->getType()->isVectorTy() && assumptions.begin() != assumptions.end()) {
     APInt KnownOne(1, 0), KnownZero(1, 0);
     computeKnownBits(CondVal, KnownZero, KnownOne, 0, &SI);
     if (KnownOne == 1)
       return replaceInstUsesWith(SI, TrueVal);
     if (KnownZero == 1)
       return replaceInstUsesWith(SI, FalseVal);
   }
 
   if (Instruction *BitCastSel = foldSelectCmpBitcasts(SI, *Builder))
     return BitCastSel;
 
   return nullptr;
 }

lib/Transforms/Scalar/AlignmentFromAssumptions.cpp

bool AlignmentFromAssumptionsPass::runImpl(Function &F, AssumptionCache &AC,
                                            DominatorTree *DT_) {
   SE = SE_;
   DT = DT_;
 
   NewDestAlignments.clear();
   NewSrcAlignments.clear();
 
   bool Changed = false;
-  for (auto &AssumeVH : AC.assumptions())
-    if (AssumeVH)
-      Changed |= processAssumption(cast<CallInst>(AssumeVH));
+  for (auto &AssumeV : AC.assumptions())
+    Changed |= processAssumption(cast<CallInst>(&AssumeV));
 
   return Changed;
 }
 
 PreservedAnalyses
 AlignmentFromAssumptionsPass::run(Function &F, FunctionAnalysisManager &AM) {
 
   AssumptionCache &AC = AM.getResult<AssumptionAnalysis>(F);

lib/Transforms/Utils/PredicateInfo.cpp

for (auto DTN : depth_first(DT.getRootNode())) {
     if (auto *BI = dyn_cast<BranchInst>(BranchBB->getTerminator())) {
       if (!BI->isConditional())
         continue;
       processBranch(BI, BranchBB, OpsToRename);
     } else if (auto *SI = dyn_cast<SwitchInst>(BranchBB->getTerminator())) {
       processSwitch(SI, BranchBB, OpsToRename);
     }
   }
-  for (auto &Assume : AC.assumptions()) {
-    if (auto *II = dyn_cast_or_null<IntrinsicInst>(Assume))
+  for (auto &AssumeV : AC.assumptions()) {
+    if (auto *II = dyn_cast<IntrinsicInst>(&AssumeV))
       processAssume(II, II->getParent(), OpsToRename);
   }
   // Now rename all our operations.
   renameUses(OpsToRename);
 }
 
 // Given the renaming stack, make all the operands currently on the stack real
 // by inserting them into the IR.  Return the last operation's value.