Handle some cases of mismatched types in IRCE

[sanjoy]

Summary

There are places where the inductive range check elimination pass depends on two llvm::Values or llvm::SCEVs to be of the same llvm::Type when they do not need to be. This patch relaxes those restrictions, and adds test cases to trigger those paths.

Three things to note:

• These issues were found by bootstrapping clang with IRCE running in the -O3 pass ordering.
• I will follow up with a change that factors out an independent Range construct -- things like Range.first->getType() are ugly.
• I have not added a test case that exercises the CIVComparedToSCEV->getType() != LatchCount->getType()) part of the change. That part of the change is needed when -indvars widens the induction variable, but leaves behind the old cached value for a loop's backedge taken count in scalar evolution (so the types mismatch but the actual value of the backedge-taken-count is still accurate). So far I have not managed to reproduce this problem outside of clang.

[reames]

LGTM once comments are addressed.

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

666 ↗

(On Diff #18486)

Given these are non obvious, can you comment how such a scenario arises? Doesn't have to be repeated at each place, but some hint somewhere?

1136 ↗

(On Diff #18486)

Maybe add a TODO:?

test/Transforms/IRCE/bug-mismatched-types.ll

5 ↗

(On Diff #18486)

Add check lines and/or comments.

[hfinkel]

I have not added a test case that exercises the CIVComparedToSCEV->getType() != LatchCount->getType()) part of the change. That part of the change is needed when -indvars widens the induction variable, but leaves behind the old cached value for a loop's backedge taken count in scalar evolution (so the types mismatch but the actual value of the backedge-taken-count is still accurate). So far I have not managed to reproduce this problem outside of clang.

This sounds like a bug in indvars. Is it obvious how to fix it there?

[sanjoy]

This sounds like a bug in indvars. Is it obvious how to fix it there?

I think this is intentional -- IndVarSimplify has code to deal with this when verifying that the loop-backedge counts have not changed:

https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/IndVarSimplify.cpp#L2026

[hfinkel]

In D7082#112586, @sanjoy wrote:

This sounds like a bug in indvars. Is it obvious how to fix it there?

I think this is intentional -- IndVarSimplify has code to deal with this when verifying that the loop-backedge counts have not changed:

https://github.com/llvm-mirror/llvm/blob/master/lib/Transforms/Scalar/IndVarSimplify.cpp#L2026

Intentional or not, I think this is a bad idea. The results of an analysis should not depend on what transformations were run previously, but only on the current state of the IR. Do you agree?

If nothing else, there should at least be a loud warning about it on the interface to getBackedgeTakenCount in ScalarEvolution.h. I'd rather fix this so that we can get the backedge count of the proper size (maybe we need a better updating interface in SE? -- IndVars seems to *have* the correct updated BETC).

[sanjoy]

Intentional or not, I think this is a bad idea. The results of an analysis should not depend on what transformations were run previously, but only on the current state of the IR. Do you agree?

Agreed. It was mildly confusing when I could not reproduce the issue
with an IR dump taken before the pass was run in clang.

If nothing else, there should at least be a loud warning about it on the interface to getBackedgeTakenCount in ScalarEvolution.h. I'd rather fix this so that we can get the backedge count of the proper size (maybe we need a better updating interface in SE? -- IndVars seems to *have* the correct updated BETC).

Currently the only precedent for updating cached information in a
ScalarEvolution object are the forget.* family of functions. Will
adding anything more fine grained than these
("widenLoopBackedgeTakenCount") be a layering violation?

• Sanjoy

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7082

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[hfinkel]

In D7082#112917, @sanjoy wrote:

Intentional or not, I think this is a bad idea. The results of an analysis should not depend on what transformations were run previously, but only on the current state of the IR. Do you agree?

Agreed. It was mildly confusing when I could not reproduce the issue
with an IR dump taken before the pass was run in clang.

Alright, let's fix this then ;)

If nothing else, there should at least be a loud warning about it on the interface to getBackedgeTakenCount in ScalarEvolution.h. I'd rather fix this so that we can get the backedge count of the proper size (maybe we need a better updating interface in SE? -- IndVars seems to *have* the correct updated BETC).

Currently the only precedent for updating cached information in a
ScalarEvolution object are the forget.* family of functions. Will
adding anything more fine grained than these
("widenLoopBackedgeTakenCount") be a layering violation?

Why does calling SE->forgetLoop(L) (as is done on line 2024), not clear the cache used to answer the SE->getBackedgeTakenCount(L) query (on line 2025)? Or am I misunderstanding something?

• Sanjoy

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7082

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

[sanjoy]

Alright, let's fix this then ;)

Sure, I'll try to send in a fix soon.

Why does calling SE->forgetLoop(L) (as is done on line 2024), not clear the cache used to answer the SE->getBackedgeTakenCount(L) query (on line 2025)? Or am I misunderstanding something?

That bit of code runs under NDEBUG and VerifyIndVars to check that
widening the induction variable does not change the backedge taken
counts computed by scalar evolution. The reason I brought it up is
that it too has to compensate for the fact that the backedge taken
count computed by SCEV before and after running indvars have different
types (so what I faced is not an unknown issue).

• Sanjoy

• Sanjoy

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7082

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

REPOSITORY

rL LLVM

http://reviews.llvm.org/D7082

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

llvm/trunk/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

class LoopConstrainer {
   //
   bool recognizeLoop(LoopStructure &LoopStructureOut,
                      const SCEV *&LatchCountOut, BasicBlock *&PreHeaderOut,
                      const char *&FailureReasonOut) const;
 
   // Compute a safe set of limits for the main loop to run in -- effectively the
   // intersection of `Range' and the iteration space of the original loop.
   // Return the header count (1 + the latch taken count) in `HeaderCount'.
+  // Return None if unable to compute the set of subranges.
   //
-  SubRanges calculateSubRanges(Value *&HeaderCount) const;
+  Optional<SubRanges> calculateSubRanges(Value *&HeaderCount) const;
 
   // Clone `OriginalLoop' and return the result in CLResult.  The IR after
   // running `cloneLoop' is well formed except for the PHI nodes in CLResult --
   // the PHI nodes say that there is an incoming edge from `OriginalPreheader`
   // but there is no such edge.
   //
   void cloneLoop(ClonedLoop &CLResult, const char *Tag) const;
 
bool LoopConstrainer::recognizeLoop(LoopStructure &LoopStructureOut,
   ICmpInst::Predicate Pred = ICmpInst::BAD_ICMP_PREDICATE;
   if (!(match(LatchBr->getCondition(),
               m_ICmp(Pred, m_Specific(CIVNext), m_Value(CIVComparedTo))) &&
         Pred == ICmpInst::ICMP_SLT)) {
     FailureReason = "unknown latch form (not slt)";
     return false;
   }
 
+  // IndVarSimplify will sometimes leave behind (in SCEV's cache) backedge-taken
+  // counts that are narrower than the canonical induction variable.  These
+  // values are still accurate, and we could probably use them after sign/zero
+  // extension; but for now we just bail out of the transformation to keep
+  // things simple.
   const SCEV *CIVComparedToSCEV = SE.getSCEV(CIVComparedTo);
-  if (isa<SCEVCouldNotCompute>(CIVComparedToSCEV)) {
+  if (isa<SCEVCouldNotCompute>(CIVComparedToSCEV) ||
+      CIVComparedToSCEV->getType() != LatchCount->getType()) {
     FailureReason = "could not relate CIV to latch expression";
     return false;
   }
 
   const SCEV *ShouldBeOne = SE.getMinusSCEV(CIVComparedToSCEV, LatchCount);
   const SCEVConstant *SCEVOne = dyn_cast<SCEVConstant>(ShouldBeOne);
   if (!SCEVOne || SCEVOne->getValue()->getValue() != 1) {
     FailureReason = "unexpected header count in latch";
bool LoopConstrainer::recognizeLoop(LoopStructure &LoopStructureOut,
 
   LatchCountOut = LatchCount;
   PreheaderOut = Preheader;
   FailureReason = nullptr;
 
   return true;
 }
 
-LoopConstrainer::SubRanges
+Optional<LoopConstrainer::SubRanges>
 LoopConstrainer::calculateSubRanges(Value *&HeaderCountOut) const {
   IntegerType *Ty = cast<IntegerType>(LatchTakenCount->getType());
 
+  assert(Range.first->getType() == Range.second->getType() &&
+         "ill-typed range!");
+  if (Range.first->getType() != Ty)
+    return None;
+
   SCEVExpander Expander(SE, "irce");
   Instruction *InsertPt = OriginalPreheader->getTerminator();
 
   Value *LatchCountV =
       MaybeSimplify(Expander.expandCodeFor(LatchTakenCount, Ty, InsertPt));
 
   IRBuilder<> B(InsertPt);
 
if (!recognizeLoop(MainLoopStructure, LatchTakenCount, Preheader,
     DEBUG(dbgs() << "irce: could not recognize loop, " << CouldNotProceedBecause
                  << "\n";);
     return false;
   }
 
   OriginalPreheader = Preheader;
   MainLoopPreheader = Preheader;
 
-  SubRanges SR = calculateSubRanges(OriginalHeaderCount);
+  Optional<SubRanges> MaybeSR = calculateSubRanges(OriginalHeaderCount);
+  if (!MaybeSR.hasValue()) {
+    DEBUG(dbgs() << "irce: could not compute subranges\n");
+    return false;
+  }
+  SubRanges SR = MaybeSR.getValue();
 
   // It would have been better to make `PreLoop' and `PostLoop'
   // `Optional<ClonedLoop>'s, but `ValueToValueMapTy' does not have a copy
   // constructor.
   ClonedLoop PreLoop, PostLoop;
   bool NeedsPreLoop = SR.ExitPreLoopAt.hasValue();
   bool NeedsPostLoop = SR.ExitMainLoopAt.hasValue();
 
InductiveRangeCheck::computeSafeIterationSpace(ScalarEvolution &SE,
   OffsetV = MaybeSimplify(OffsetV);
 
   Value *Begin = MaybeSimplify(B.CreateNeg(OffsetV));
   Value *End = MaybeSimplify(B.CreateSub(getLength(), OffsetV));
 
   return std::make_pair(Begin, End);
 }
 
-static InductiveRangeCheck::Range
+static Optional<InductiveRangeCheck::Range>
 IntersectRange(const Optional<InductiveRangeCheck::Range> &R1,
                const InductiveRangeCheck::Range &R2, IRBuilder<> &B) {
+  assert(R2.first->getType() == R2.second->getType() && "ill-typed range!");
+
   if (!R1.hasValue())
     return R2;
   auto &R1Value = R1.getValue();
 
+  // TODO: we could widen the smaller range and have this work; but for now we
+  // bail out to keep things simple.
+  if (R1Value.first->getType() != R2.first->getType())
+    return None;
+
   Value *NewMin = ConstructSMaxOf(R1Value.first, R2.first, B);
   Value *NewMax = ConstructSMinOf(R1Value.second, R2.second, B);
   return std::make_pair(NewMin, NewMax);
 }
 
 bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (L->getBlocks().size() >= LoopSizeCutoff) {
     DEBUG(dbgs() << "irce: giving up constraining loop, too large\n";);
bool InductiveRangeCheckElimination::runOnLoop(Loop *L, LPPassManager &LPM) {
   Instruction *ExprInsertPt = Preheader->getTerminator();
 
   SmallVector<InductiveRangeCheck *, 4> RangeChecksToEliminate;
 
   IRBuilder<> B(ExprInsertPt);
   for (InductiveRangeCheck *IRC : RangeChecks) {
     auto Result = IRC->computeSafeIterationSpace(SE, B);
     if (Result.hasValue()) {
-      SafeIterRange = IntersectRange(SafeIterRange, Result.getValue(), B);
+      auto MaybeSafeIterRange =
+        IntersectRange(SafeIterRange, Result.getValue(), B);
+      if (MaybeSafeIterRange.hasValue()) {
         RangeChecksToEliminate.push_back(IRC);
+        SafeIterRange = MaybeSafeIterRange.getValue();
+      }
     }
   }
 
   if (!SafeIterRange.hasValue())
     return false;
 
   LoopConstrainer LC(*L, getAnalysis<LoopInfoWrapperPass>().getLoopInfo(), SE,
                      SafeIterRange.getValue());

llvm/trunk/test/Transforms/IRCE/bug-mismatched-types.ll

+; RUN: opt -irce -S < %s
+
+; These test cases don't check the correctness of the transform, but
+; that the -irce does not crash in the presence of certain things in
+; the IR:
+
+define void @mismatched_types_1() {
+; In this test case, the safe range for the only range check in the
+; loop is of type [i32, i32) while the backedge taken count is of type
+; i64.
+
+; CHECK-LABEL: mismatched_types_1
+entry:
+  br label %for.body
+
+for.body:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.inc ]
+  %0 = trunc i64 %indvars.iv to i32
+  %1 = icmp ult i32 %0, 7
+  br i1 %1, label %switch.lookup, label %for.inc
+
+switch.lookup:
+  br label %for.inc
+
+for.inc:
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cmp55 = icmp slt i64 %indvars.iv.next, 11
+  br i1 %cmp55, label %for.body, label %for.end
+
+for.end:
+  unreachable
+}
+
+define void @mismatched_types_2() {
+; In this test case, there are two range check in the loop, one with a
+; safe range of type [i32, i32) and one with a safe range of type
+; [i64, i64).
+
+; CHECK-LABEL: mismatched_types_2
+entry:
+  br label %for.body.a
+
+for.body.a:
+  %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.inc ]
+  %cond.a = icmp ult i64 %indvars.iv, 7
+  br i1 %cond.a, label %switch.lookup.a, label %for.body.b
+
+switch.lookup.a:
+  br label %for.body.b
+
+for.body.b:
+  %truncated = trunc i64 %indvars.iv to i32
+  %cond.b = icmp ult i32 %truncated, 7
+  br i1 %cond.b, label %switch.lookup.b, label %for.inc
+
+switch.lookup.b:
+  br label %for.inc
+
+for.inc:
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  %cmp55 = icmp slt i64 %indvars.iv.next, 11
+  br i1 %cmp55, label %for.body.a, label %for.end
+
+for.end:
+  unreachable
+}