[SCEV] Replace IsAvailableOnEntry with block disposition

[nikic]

Summary

As far as I understand, the IsAvailableOnEntry() function basically implements the same functionality as the properlyDominates() block disposition. The primary difference (apart from a weaker implementation) seems to be in this comment at the top:

// Checks if the SCEV S is available at BB.  S is considered available at BB
// if S can be materialized at BB without introducing a fault.

However, I don't really understand why there would be such a requirement. It's my understanding that SCEV explicitly does not care about trapping udiv instructions itself, and it's the job of SCEVExpander's isSafeToExpand() to make sure these don't get expanded if they may trap.

[mkazantsev]

I agree that these two things should be the same.

[fhahn]

However, I don't really understand why there would be such a requirement.

Yeah, IIUC this should be fine. LG

[manojgupta]

This patch is causing a clang crash in ChromeOS builds.

Reproducer:

clang -cc1 -O2 -x c++ -emit-llvm crash.cc

typedef int a;
namespace b {
class c;
}
namespace e {
namespace {
template <bool, class d = void> struct g { typedef d f; };
template <bool i, class d> using h = g<i, d>::f;
template <class d, d k> struct j { static const d m = k; };
typedef j<bool, false> l;
template <bool, class q, class> struct aa { using f = q; };
} // namespace
inline namespace n {
template <class d> struct ab : j<bool, __is_assignable(d, d)> {};
template <class d> using o = g<ab<d>::m>::f;
template <class d> o<d> ac(d &p, d x) { p = x; }
struct r;
template <class s, class ad> struct ae {
  s af;
  struct ag {
    template <class, class> static bool ah();
    template <class, class ai> static constexpr bool aj() { return ah<a, ai>; }
  };
  template <bool ak> using al = aa<ak, ag, r>::f;
  template <bool am = true, g<al<am>::template aj<s, ad>()> * = nullptr>
  ae(s, ad);
};
template <class an, class ao> void ap(an aq, ao ar) { ac(*aq, *ar); }
struct as {};
template <class> struct at { typedef as au; };
template <class> struct av;
struct aw;
template <> struct av<aw> { template <class ax> using ay = at<ax>::au; };
template <class, class an, class az, class ao, class ba>
ae<an, ao> bb(an bc, az, ao bd, ba be) {
  while (bd != be) {
    ap(bc, bd);
    ++bc;
    ++bd;
  }
  return ae(bc, bd);
}
template <class t, typename bf> bf bh(bf bj, bf bk, bf bi) {
  bb<t>(bj, bk, bk, bi);
  return bk;
}
template <class t, class bf> bf bl(bf bj, bf bk, bf bi, as) {
  return bh<t>(bj, bk, bi);
}
template <class t, class bg, class bm> ae<bg, bg> bn(bg bj, bg bk, bm bi) {
  using bo = ae<bg, bg>;
  bg bp(bi);
  using bq = av<t>::template ay<bg>;
  auto br = bl<t>(bj, bk, bp, bq());
  return bo(br, bp);
}
template <class bs> bs bt(bs bj, bs bk, bs bi) { return bn<aw>(bj, bk, bi).af; }
} // namespace n
} // namespace e
void bu(void *, void *, a);
namespace e {
namespace {
template <class d, a bv> d *ci(d (&bw)[bv]) { return bw + bv; }
} // namespace
} // namespace e
namespace b {
template <typename, typename> struct bx;
class by {};
namespace bz {
namespace ca {
template <typename> struct cb : e::j<bool, 0> {};
template <typename cc> e::h<cb<c>::m, a> cd(cc);
template <typename cc> bool ce(char *&cf, char *cg, cc m) {
  a ch = sizeof(m);
  if (cf > cg)
    return false;
  char *cj = reinterpret_cast<char *>(&m);
  bu(cf, cj, ch);
  cf += ch;
  return true;
}
template <typename ck> by cl(ck af, ck cw) {
  char buffer[64], *cf;
  char *cg = e::ci(buffer);
  while (af != cw) {
    cf = buffer;
    while (af != cw && ce(cf, cg, cd(af)))
      ++af;
    e::bt(buffer, cf, cg);
  }
}
} // namespace ca
} // namespace bz
template <typename ck> by cm(ck af, ck cw) { bz::ca::cl(af, cw); }
template <typename> class cn;
template <typename> class co;
} // namespace b
namespace {
using b::c;
using b::cn;
template <typename cc, typename da = void> using bx = b::bx<cc, da>;
template <typename cp> using co = b::co<cp>;
} // namespace
namespace b {
template <typename, typename = void> struct bx;
template <typename cc, typename cq> struct bx<e::ae<cc, cq>> {
  using cr = e::ae<cc, cq>;
  using cs = bx<cc>;
  static unsigned ct(cr cu) { cs::ct(cu.af); }
};
template <typename cc> class cn {
public:
  using cv = cc;
  using di = cv *;
  using cx = di;
  cx begin();
  cx ci();
};
template <typename cc> by cy(cc cz) { cm(cz.begin(), cz.ci()); }
template <typename cc> struct bx<cn<cc>> {
  static unsigned ct(cn<cc> de) { cy(de); }
};
template <typename db, typename... u> class co<db(u...)> {};
namespace ca {
template <class, template <class> class> struct dc { using dd = e::l; };
} // namespace ca
template <template <class> class v> using w = ca::dc<void, v>::dd;
} // namespace b
namespace mlir {
namespace ca {
template <typename df> using y = decltype(df::z);
template <typename df> using dg = decltype(df::dh);
} // namespace ca
class dm {
public:
  template <typename dj> dj dk(co<void(dj *)>) {
    auto dl = getKey<dj>();
    dn<dj>(dl);
  }
  template <typename df> e::h<b::w<ca::y>::m, typename df::KeyTy> getKey();
  template <typename, typename DerivedKey>
  e::h<b::w<ca::dg>::m, b::by> dn(DerivedKey dl) {
    bx<DerivedKey>::ct(dl);
  }
};
namespace pdll {
namespace ast {
class Context;
namespace ca {
struct TupleTypeStorage;
}
class Type {
public:
  struct dj;
  template <typename ImplT> class TypeBase {
  public:
    using df = ImplT;
  };
  dj *impl;
};
class TupleType : Type::TypeBase<ca::TupleTypeStorage> {
  TupleType dk(Context &, cn<Type>, cn<c>);
};
namespace ca {
template <typename, typename KeyT> struct TypeStorageBase {
  using KeyTy = KeyT;
};
struct TupleTypeStorage
    : TypeStorageBase<TupleTypeStorage, e::ae<cn<Type>, c>> {};
} // namespace ca
class Context {
public:
  dm getTypeUniquer();
};
} // namespace ast
} // namespace pdll
} // namespace mlir
using namespace mlir::pdll::ast;
TupleType TupleType::dk(Context &context, cn<Type>, cn<c>) {
  context.getTypeUniquer().dk(co<void(df *)>());
}

[nikic]

@manojgupta Thanks! Here's a somewhat reduced test case for -passes=loop-idiom:

define void @test() {
entry:
  %alloca = alloca [64 x i8], align 16
  br label %loop

loop:
  %phi = phi i64 [ 0, %entry ], [ 1, %loop.latch ]
  br i1 false, label %loop.exit2, label %loop.latch

loop.latch:
  %or = or i64 %phi, 4
  br i1 false, label %loop.exit, label %loop

loop.exit:
  br label %loop2.preheader

loop.exit2:
  br label %loop2.preheader

loop2.preheader:
  %phi5.ph = phi ptr [ null, %loop.exit2 ], [ %alloca, %loop.exit ]
  %phi6.ph = phi i64 [ 0, %loop.exit2 ], [ %or, %loop.exit ]
  br label %loop2

loop2:
  %phi5 = phi ptr [ %getelementptr7, %loop2 ], [ %phi5.ph, %loop2.preheader ]
  %phi6 = phi i64 [ %add, %loop2 ], [ %phi6.ph, %loop2.preheader ]
  %getelementptr = getelementptr i8, ptr %alloca, i64 %phi6
  %load = load i8, ptr %getelementptr, align 1
  store i8 %load, ptr %phi5, align 1
  %getelementptr7 = getelementptr i8, ptr %phi5, i64 1
  %add = add i64 %phi6, 1
  %icmp = icmp eq i64 %phi6, 0
  br i1 %icmp, label %loop2.exit, label %loop2

loop2.exit:
  ret void
}

Triggers this assertion:

opt: /home/npopov/repos/llvm-project/llvm/lib/Transforms/Utils/ScalarEvolutionExpander.cpp:2673: void llvm::SCEVExpanderCleaner::cleanup(): Assertion `all_of(I->users(), [&InsertedSet](Value *U) { return InsertedSet.contains(cast<Instruction>(U)); }) && "removed instruction should only be used by instructions inserted " "during expansion"' failed.

[nikic]

I think the problem here is that when we form LCSSA in SCEVExpander, we only add the phi nodes in the exits to the inserted instructions, but not the ones created by SSAUpdater.

[uabelho]

Hi,

The following starts failing with this patch (sorry for the ugly command line, utils/reduce_pipeline.py doesn't get any further):

opt -passes="cgscc(devirt<4>(function(loop(loop-unroll-full),gvn<>,jump-threading))),function(simplifycfg<no-keep-loops>),cgscc(devirt<4>(function(loop-mssa(loop-rotate),simplifycfg,instcombine,loop(indvars,loop-unroll-full))))" -verify-scev bbi-84034.ll -o /dev/null

It fails with

Cached disposition of %.pre for block %cleanup.loopexit is incorrect! 
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace.
Stack dump:
0.	Program arguments: ../../main-github/llvm/build-all/bin/opt -passes=cgscc(devirt<4>(function(loop(loop-unroll-full),gvn<>,jump-threading))),function(simplifycfg<no-keep-loops>),cgscc(devirt<4>(function(loop-mssa(loop-rotate),simplifycfg,instcombine,loop(indvars,loop-unroll-full)))) -verify-scev bbi-84034.ll -o /dev/null
 #0 0x0000556cf9083487 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (../../main-github/llvm/build-all/bin/opt+0x2dcd487)
 #1 0x0000556cf90811ae llvm::sys::RunSignalHandlers() (../../main-github/llvm/build-all/bin/opt+0x2dcb1ae)
 #2 0x0000556cf9083b1f SignalHandler(int) Signals.cpp:0:0
 #3 0x00007f77ef000630 __restore_rt sigaction.c:0:0
 #4 0x00007f77ec747387 raise (/lib64/libc.so.6+0x36387)
 #5 0x00007f77ec748a78 abort (/lib64/libc.so.6+0x37a78)
 #6 0x0000556cf827564e llvm::ScalarEvolution::verify() const (../../main-github/llvm/build-all/bin/opt+0x1fbf64e)
 #7 0x0000556cf9bb2f56 llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x38fcf56)
 #8 0x0000556cf929977d llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x2fe377d)
 #9 0x0000556cf8aa6634 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0x27f0634)
#10 0x0000556cf6f4ef7d llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (../../main-github/llvm/build-all/bin/opt+0xc98f7d)
#11 0x0000556cf807a61f llvm::CGSCCToFunctionPassAdaptor::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (../../main-github/llvm/build-all/bin/opt+0x1dc461f)
#12 0x0000556cf6f508bd llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::CGSCCToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (../../main-github/llvm/build-all/bin/opt+0xc9a8bd)
#13 0x0000556cf8074ece llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (../../main-github/llvm/build-all/bin/opt+0x1dbeece)
#14 0x0000556cf92824fd llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (../../main-github/llvm/build-all/bin/opt+0x2fcc4fd)
#15 0x0000556cf80787e5 llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (../../main-github/llvm/build-all/bin/opt+0x1dc27e5)
#16 0x0000556cf929b72d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::DevirtSCCRepeatedPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (../../main-github/llvm/build-all/bin/opt+0x2fe572d)
#17 0x0000556cf8074ece llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (../../main-github/llvm/build-all/bin/opt+0x1dbeece)
#18 0x0000556cf92824fd llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (../../main-github/llvm/build-all/bin/opt+0x2fcc4fd)
#19 0x0000556cf8076eda llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x1dc0eda)
#20 0x0000556cf928279d llvm::detail::PassModel<llvm::Module, llvm::ModuleToPostOrderCGSCCPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x2fcc79d)
#21 0x0000556cf8aa57c4 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module>>::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (../../main-github/llvm/build-all/bin/opt+0x27ef7c4)
#22 0x0000556cf6b8701e llvm::runPassPipeline(llvm::StringRef, llvm::Module&, llvm::TargetMachine*, llvm::TargetLibraryInfoImpl*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::ToolOutputFile*, llvm::StringRef, llvm::ArrayRef<llvm::PassPlugin>, llvm::opt_tool::OutputKind, llvm::opt_tool::VerifierKind, bool, bool, bool, bool, bool, bool) (../../main-github/llvm/build-all/bin/opt+0x8d101e)
#23 0x0000556cf6b956de main (../../main-github/llvm/build-all/bin/opt+0x8df6de)
#24 0x00007f77ec733555 __libc_start_main (/lib64/libc.so.6+0x22555)
#25 0x0000556cf6b81770 _start (../../main-github/llvm/build-all/bin/opt+0x8cb770)
Abort (core dumped)

bbi-84034.ll1 KBDownload

[nikic]

@uabelho Thanks for the report! Here's a reduced test case:

; RUN: opt -S -passes='print<scalar-evolution>,loop(loop-unroll-full)' < %s
define i32 @test(ptr %arg) {
entry:
  br label %loop

loop:
  %iv = phi ptr [ %arg, %loop.latch ], [ null, %entry ]
  %load = load i32, ptr null, align 4
  br i1 false, label %loop.exit, label %loop.latch

loop.latch:
  br i1 false, label %loop.exit, label %loop

loop.exit:
  %exitval = phi i32 [ 0, %loop.latch ], [ %load, %loop ]
  ret i32 %exitval
}

I expect the only relation this patch has to the issue is that we now calculate a disposition that we previously didn't, so it now gets verified.

[nikic]

@uabelho Should be fixed by https://reviews.llvm.org/D153762.

llvm/lib/Analysis/ScalarEvolution.cpp

const SCEV *ScalarEvolution::createAddRecFromPHI(PHINode *PN) {
   // to create an AddRecExpr for this PHI node. We can not keep this temporary
   // as it will prevent later (possibly simpler) SCEV expressions to be added
   // to the ValueExprMap.
   eraseValueFromMap(PN);
 
   return nullptr;
 }
 
-// Checks if the SCEV S is available at BB.  S is considered available at BB
-// if S can be materialized at BB without introducing a fault.
-static bool IsAvailableOnEntry(const Loop *L, DominatorTree &DT, const SCEV *S,
-                               BasicBlock *BB) {
-  struct CheckAvailable {
-    bool TraversalDone = false;
-    bool Available = true;
-
-    const Loop *L = nullptr;  // The loop BB is in (can be nullptr)
-    BasicBlock *BB = nullptr;
-    DominatorTree &DT;
-
-    CheckAvailable(const Loop *L, BasicBlock *BB, DominatorTree &DT)
-      : L(L), BB(BB), DT(DT) {}
-
-    bool setUnavailable() {
-      TraversalDone = true;
-      Available = false;
-      return false;
-    }
-
-    bool follow(const SCEV *S) {
-      switch (S->getSCEVType()) {
-      case scConstant:
-      case scVScale:
-      case scPtrToInt:
-      case scTruncate:
-      case scZeroExtend:
-      case scSignExtend:
-      case scAddExpr:
-      case scMulExpr:
-      case scUMaxExpr:
-      case scSMaxExpr:
-      case scUMinExpr:
-      case scSMinExpr:
-      case scSequentialUMinExpr:
-        // These expressions are available if their operand(s) is/are.
-        return true;
-
-      case scAddRecExpr: {
-        // We allow add recurrences that are on the loop BB is in, or some
-        // outer loop.  This guarantees availability because the value of the
-        // add recurrence at BB is simply the "current" value of the induction
-        // variable.  We can relax this in the future; for instance an add
-        // recurrence on a sibling dominating loop is also available at BB.
-        const auto *ARLoop = cast<SCEVAddRecExpr>(S)->getLoop();
-        if (L && (ARLoop == L || ARLoop->contains(L)))
-          return true;
-
-        return setUnavailable();
-      }
-
-      case scUnknown: {
-        // For SCEVUnknown, we check for simple dominance.
-        const auto *SU = cast<SCEVUnknown>(S);
-        Value *V = SU->getValue();
-
-        if (isa<Argument>(V))
-          return false;
-
-        if (isa<Instruction>(V) && DT.dominates(cast<Instruction>(V), BB))
-          return false;
-
-        return setUnavailable();
-      }
-
-      case scUDivExpr:
-      case scCouldNotCompute:
-        // We do not try to smart about these at all.
-        return setUnavailable();
-      }
-      llvm_unreachable("Unknown SCEV kind!");
-    }
-
-    bool isDone() { return TraversalDone; }
-  };
-
-  CheckAvailable CA(L, BB, DT);
-  SCEVTraversal<CheckAvailable> ST(CA);
-
-  ST.visitAll(S);
-  return CA.Available;
-}
-
 // Try to match a control flow sequence that branches out at BI and merges back
 // at Merge into a "C ? LHS : RHS" select pattern.  Return true on a successful
 // match.
 static bool BrPHIToSelect(DominatorTree &DT, BranchInst *BI, PHINode *Merge,
                           Value *&C, Value *&LHS, Value *&RHS) {
   C = BI->getCondition();
 
   BasicBlockEdge LeftEdge(BI->getParent(), BI->getSuccessor(0));
static bool BrPHIToSelect(DominatorTree &DT, BranchInst *BI, PHINode *Merge,
 
   return false;
 }
 
 const SCEV *ScalarEvolution::createNodeFromSelectLikePHI(PHINode *PN) {
   auto IsReachable =
       [&](BasicBlock *BB) { return DT.isReachableFromEntry(BB); };
   if (PN->getNumIncomingValues() == 2 && all_of(PN->blocks(), IsReachable)) {
-    const Loop *L = LI.getLoopFor(PN->getParent());
-
     // Try to match
     //
     //  br %cond, label %left, label %right
     // left:
     //  br label %merge
     // right:
     //  br label %merge
     // merge:
     //  V = phi [ %x, %left ], [ %y, %right ]
     //
     // as "select %cond, %x, %y"
 
     BasicBlock *IDom = DT[PN->getParent()]->getIDom()->getBlock();
     assert(IDom && "At least the entry block should dominate PN");
 
     auto *BI = dyn_cast<BranchInst>(IDom->getTerminator());
     Value *Cond = nullptr, *LHS = nullptr, *RHS = nullptr;
 
     if (BI && BI->isConditional() &&
         BrPHIToSelect(DT, BI, PN, Cond, LHS, RHS) &&
-        IsAvailableOnEntry(L, DT, getSCEV(LHS), PN->getParent()) &&
-        IsAvailableOnEntry(L, DT, getSCEV(RHS), PN->getParent()))
+        properlyDominates(getSCEV(LHS), PN->getParent()) &&
+        properlyDominates(getSCEV(RHS), PN->getParent()))
       return createNodeForSelectOrPHI(PN, Cond, LHS, RHS);
   }
 
   return nullptr;
 }
 
 const SCEV *ScalarEvolution::createNodeForPHI(PHINode *PN) {
   if (const SCEV *S = createAddRecFromPHI(PN))

llvm/test/Analysis/ScalarEvolution/logical-operations.ll

 }
 
 define ptr @tautological_select_like_phi(i32 %tc) {
 ; CHECK-LABEL: 'tautological_select_like_phi'
 ; CHECK-NEXT:  Classifying expressions for: @tautological_select_like_phi
 ; CHECK-NEXT:    %iv = phi i32 [ 0, %entry ], [ %iv.next, %latch ]
 ; CHECK-NEXT:    --> {0,+,1}<nuw><nsw><%loop> U: [0,101) S: [0,101) Exits: 100 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:    %r = phi ptr [ @constant, %truebb ], [ @another_constant, %falsebb ]
-; CHECK-NEXT:    --> %r U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: <<Unknown>> LoopDispositions: { %loop: Variant }
+; CHECK-NEXT:    --> @constant U: [0,-3) S: [-9223372036854775808,9223372036854775805) Exits: @constant LoopDispositions: { %loop: Invariant }
 ; CHECK-NEXT:    %iv.next = add i32 %iv, 1
 ; CHECK-NEXT:    --> {1,+,1}<nuw><nsw><%loop> U: [1,102) S: [1,102) Exits: 101 LoopDispositions: { %loop: Computable }
 ; CHECK-NEXT:  Determining loop execution counts for: @tautological_select_like_phi
 ; CHECK-NEXT:  Loop %loop: backedge-taken count is 100
 ; CHECK-NEXT:  Loop %loop: constant max backedge-taken count is 100
 ; CHECK-NEXT:  Loop %loop: symbolic max backedge-taken count is 100
 ; CHECK-NEXT:  Loop %loop: Predicated backedge-taken count is 100
 ; CHECK-NEXT:   Predicates: