[ValueTracking] Add a isIVNeverPoison helper

[sanjoy]

Summary

NFC right now (since the only user is the unit test), but will be used
in a future change.

[reames]

include/llvm/Analysis/ValueTracking.h

455

Hm, this interface seems likely problematic. How does this handle the case where poison can be introduced by two different sources? Do we need an iterator abstraction? Or can we reliably just return null for those?

(If the later, please clarify in the comment.)

lib/Analysis/ValueTracking.cpp

3900

What prevents this induction variable from being part of a longer phi cycle? i.e. a indvar with conditional increments for instance? i.e. this shouldn't be an assert of the documentation needs updated.

[sanjoy]

include/llvm/Analysis/ValueTracking.h

455

It is the latter, will fix the comment.

lib/Analysis/ValueTracking.cpp

3900

Good point -- at this layer it is probably best to just bail out in that case.

[sanjoy]

• Address review for D30445

[reames]

LGTM

include/llvm/Analysis/ValueTracking.h

template <typename T> class ArrayRef;
   /// Return true if this function can prove that if PoisonI is executed
   /// and yields a full-poison value (all bits poison), then that will
   /// trigger undefined behavior.
   ///
   /// Note that this currently only considers the basic block that is
   /// the parent of I.
   bool programUndefinedIfFullPoison(const Instruction *PoisonI);
 
+  /// Return true (in the first component) if \p IV can statically be
+  /// proved to never be poison.  \p IV has to be a pre-inc or
+  /// post-inc induction variable in the loop \p L.
+  ///
+  /// The second component of the return value may be non-null only if
+  /// the first component is false.  If non-null, it is the *only*
+  /// poison generating instruction causing \p I to (potentially) be
+  /// poison; and calling \c dropPoisonGeneratingFlags on it will make
+  /// \p I be non-poison.  If there are more than one such poison
+  /// generating instructions, then the second component is null,
+  /// making {false, nullptr} the maximally conservative result
+  /// returned by this routine.
+  std::pair<bool, const Instruction *> isIVNeverPoison(const Instruction *IV,
+                                                       const Loop *L);
+
   /// Starting with the assumption that \p I is not poison, fill \p
   /// NonPoison with a set of values that are also known to not be
   /// poison.  Internally this is a simple worklist algorithm around
   /// \p propagatesFullPoison.
   ///
   /// The worklist algorithm does not follow values for which \p
   /// FollowPred returns false.
   void propagateKnownNonPoison(const Value *I,

lib/Analysis/ValueTracking.cpp

case Instruction::ICmp:
     // instance, x s< (x +nsw 1) can be folded to true.
     return true;
 
   default:
     return false;
   }
 }
 
+static bool isTriviallyNotPoison(const Value *V) {
+  auto IsNonPoisonConstant = [](const Value *C) {
+    return isa<ConstantInt>(C) || isa<GlobalValue>(C) ||
+           isa<ConstantPointerNull>(C);
+  };
+
+  if (IsNonPoisonConstant(V))
+    return true;
+
+  auto *ConstGEP = dyn_cast_or_null<GEPOperator>(dyn_cast<ConstantExpr>(V));
+  if (!ConstGEP || !IsNonPoisonConstant(ConstGEP->getPointerOperand()) ||
+      ConstGEP->getInRangeIndex())
+    return false;
+
+  return !ConstGEP->isInBounds() || ConstGEP->hasAllConstantIndices();
+}
+
+static std::pair<bool, const Instruction *>
+isIVPHINeverPoisonImpl(const PHINode *IV, const Loop *L) {
+  assert(IV->getParent() == L->getHeader() && "Invalid IV!");
+  assert(IV->getNumIncomingValues() == 2 && "Invalid IV!");
+
+  if (!isTriviallyNotPoison(
+          IV->getIncomingValueForBlock(L->getLoopPreheader())))
+    return {false, nullptr};
+
+  auto *BEVal =
+      cast<Instruction>(IV->getIncomingValueForBlock(L->getLoopLatch()));
+
+  if (!all_of(BEVal->operands(),
+              [&](Value *I) { return I == IV || isa<ConstantInt>(I); }))
+    return {false, nullptr};
+
+  if (auto *OBO = dyn_cast<OverflowingBinaryOperator>(BEVal))
+    return (OBO->hasNoUnsignedWrap() || OBO->hasNoSignedWrap())
+               ? std::make_pair(false, BEVal)
+               : std::make_pair(true, nullptr);
+
+  if (auto *GEP = dyn_cast<GetElementPtrInst>(BEVal))
+    return GEP->isInBounds() ? std::make_pair(false, BEVal)
+                             : std::make_pair(true, nullptr);
+
+  return {false, nullptr};
+}
+
+static std::pair<bool, const Instruction *>
+isIVNeverPoisonImpl(const Instruction *I, const Loop *L) {
+  if (auto *PN = dyn_cast<PHINode>(I))
+    return isIVPHINeverPoisonImpl(PN, L);
+
+  auto IsHeaderPHI = [&](const Value *V) {
+    if (auto *PN = dyn_cast<PHINode>(V))
+      return PN->getParent() == L->getHeader();
+    return false;
+  };
+
+  auto PHIOpItr = find_if(I->operands(), IsHeaderPHI);
+  if (PHIOpItr == I->op_end())
+    return {false, nullptr};
+
+  auto *PN = cast<PHINode>(*PHIOpItr);
+  assert(PN->getParent() == L->getHeader() && "Precondition violated!");
+  if (PN->getIncomingValueForBlock(L->getLoopLatch()) != I)
+    return {false, nullptr};
+
+  return isIVPHINeverPoisonImpl(PN, L);
+}
+
+std::pair<bool, const Instruction *>
+llvm::isIVNeverPoison(const Instruction *IV, const Loop *L) {
+  auto Result = isIVNeverPoisonImpl(IV, L);
+  assert((!Result.second || !Result.first) &&
+         "Broken invarariant on return value!");
+  return Result;
+}
+
 void llvm::propagateKnownNonPoison(
     const Value *I, SmallVectorImpl<const Value *> &NonPoison,
     function_ref<bool(const Value *)> FollowPred) {
   SmallPtrSet<const Value *, 8> Visited;
   Visited.insert(I);
   NonPoison.push_back(I);
   unsigned Idx = 0;
   do {

unittests/Analysis/ValueTrackingTest.cpp

 //===- ValueTrackingTest.cpp - ValueTracking tests ------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
+#include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstIterator.h"
 #include "llvm/IR/LLVMContext.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/SourceMgr.h"
 #include "gtest/gtest.h"
 
auto *ArgA = cast<Argument>(AddI->getOperand(0));
     propagateKnownNonPoison(CmpI, NonPoison,
                             [&](const Value *V) { return V != AddI; });
     EXPECT_TRUE(is_contained(NonPoison, CmpI));
     EXPECT_TRUE(is_contained(NonPoison, SubI));
     EXPECT_FALSE(is_contained(NonPoison, AddI));
     EXPECT_FALSE(is_contained(NonPoison, ArgA));
   }
 }
+
+TEST(ValueTracking, isIVNeverPoison) {
+  StringRef Assembly =
+      "@data = external global [240 x i8]  "
+      "  "
+      "define void @f() {  "
+      "entry:  "
+      "  br label %for.cond  "
+      "  "
+      "for.cond:  "
+      "  %iv_bad = phi i32 [ 0, %entry ], [ %iv_0.inc, %for.cond ]  "
+      "  %iv_0 = phi i32 [ 0, %entry ], [ %iv_0.inc, %for.cond ]  "
+      "  %iv_1 = phi i32 [ 0, %entry ], [ %iv_1.inc, %for.cond ]  "
+      "  %iv_2 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* "
+      "        @data, i64 0, i64 0), %entry ], [ %iv_2.inc, %for.cond ]  "
+      "  %iv_3 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* "
+      "        @data, i64 0, i64 0), %entry ], [ %iv_3.inc, %for.cond ]  "
+      "  %iv_4 = phi i8* [ getelementptr inbounds ([240 x i8], [240 x i8]* "
+      "        @data, i64 0, i64 2), %entry ], [ %iv_2.inc, %for.cond ]  "
+      "  %iv_0.inc = add i32 %iv_0, 1  "
+      "  %iv_1.inc = add nsw i32 %iv_1, 1  "
+      "  %iv_2.inc = getelementptr i8, i8* %iv_2, i64 1  "
+      "  %iv_3.inc = getelementptr inbounds i8, i8* %iv_3, i64 1  "
+      "  %iv_4.inc = getelementptr inbounds i8, i8* %iv_4, i64 1  "
+      "  %iv_0.offset.0 = add i32 %iv_0, 30  "
+      "  %iv_0.offset.1 = add nsw i32 %iv_0, 1  "
+      "  br i1 undef, label %for.cond, label %for.end  "
+      "  "
+      "for.end:  "
+      "  ret void  "
+      "}  ";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  assert(M && "Bad assembly?");
+
+  auto *F = M->getFunction("f");
+  assert(F && "Bad assembly?");
+
+  auto Itr = std::next(F->begin())->begin();
+
+  Instruction &iv_bad = *Itr++;
+  Instruction &iv_0 = *Itr++;
+  Instruction &iv_1 = *Itr++;
+  Instruction &iv_2 = *Itr++;
+  Instruction &iv_3 = *Itr++;
+  Instruction &iv_4 = *Itr++;
+  Instruction &iv_0_inc = *Itr++;
+  Instruction &iv_1_inc = *Itr++;
+  Instruction &iv_2_inc = *Itr++;
+  Instruction &iv_3_inc = *Itr++;
+  Instruction &iv_4_inc = *Itr++;
+  Instruction &iv_0_offset_0 = *Itr++;
+  Instruction &iv_0_offset_1 = *Itr++;
+
+  DominatorTree DT(*F);
+  LoopInfo LI(DT);
+  Loop *L = LI.getLoopFor(iv_0.getParent());
+
+  typedef std::pair<bool, const Instruction *> ResultTy;
+
+  EXPECT_EQ(isIVNeverPoison(&iv_bad, L), ResultTy(false, nullptr));
+
+  EXPECT_EQ(isIVNeverPoison(&iv_0, L), ResultTy(true, nullptr));
+  EXPECT_EQ(isIVNeverPoison(&iv_1, L), ResultTy(false, &iv_1_inc));
+  EXPECT_EQ(isIVNeverPoison(&iv_2, L), ResultTy(true, nullptr));
+  EXPECT_EQ(isIVNeverPoison(&iv_3, L), ResultTy(false, &iv_3_inc));
+  EXPECT_EQ(isIVNeverPoison(&iv_4, L), ResultTy(false, nullptr));
+
+  EXPECT_EQ(isIVNeverPoison(&iv_0_inc, L), ResultTy(true, nullptr));
+  EXPECT_EQ(isIVNeverPoison(&iv_1_inc, L), ResultTy(false, &iv_1_inc));
+  EXPECT_EQ(isIVNeverPoison(&iv_2_inc, L), ResultTy(true, nullptr));
+  EXPECT_EQ(isIVNeverPoison(&iv_3_inc, L), ResultTy(false, &iv_3_inc));
+  EXPECT_EQ(isIVNeverPoison(&iv_4_inc, L), ResultTy(false, nullptr));
+
+  EXPECT_EQ(isIVNeverPoison(&iv_0_offset_0, L), ResultTy(false, nullptr));
+  EXPECT_EQ(isIVNeverPoison(&iv_0_offset_1, L), ResultTy(false, nullptr));
+}
+
+TEST(ValueTracking, isIVNeverPoisonWithIntermediatePHI) {
+  StringRef Assembly =
+      "@data = external global [240 x i8]  "
+      "  "
+      "define void @f(i1 %c) {  "
+      "entry:  "
+      "  br label %for.cond  "
+      "  "
+      "for.cond:  "
+      "  %iv_0 = phi i32 [ 0, %entry ], [ %iv_0.inc, %merge ]  "
+      "  br i1 %c, label %then, label %merge "
+      "then: "
+      "  br label %merge "
+      "merge: "
+      "  %increment_amt = phi i32 [ 0, %for.cond ], [ 5, %merge ] "
+      "  %iv_0.inc = add i32 %increment_amt, %iv_0 "
+      "  br i1 %c, label %for.cond, label %for.end  "
+      "  "
+      "for.end:  "
+      "  ret void  "
+      "}  ";
+
+  LLVMContext Context;
+  SMDiagnostic Error;
+  auto M = parseAssemblyString(Assembly, Error, Context);
+  assert(M && "Bad assembly?");
+
+  auto *F = M->getFunction("f");
+  assert(F && "Bad assembly?");
+
+  auto Itr = std::next(F->begin(), 3)->begin();
+  const auto &iv_0_inc = *std::next(Itr);
+
+  DominatorTree DT(*F);
+  LoopInfo LI(DT);
+  Loop *L = LI.getLoopFor(iv_0_inc.getParent());
+
+  typedef std::pair<bool, const Instruction *> ResultTy;
+
+  EXPECT_EQ(isIVNeverPoison(&iv_0_inc, L), ResultTy(false, nullptr));
+}