From 7a0b7f5996cbce5a204754a60d5cb12df69a28fe Mon Sep 17 00:00:00 2001 From: Sanjoy Das Date: Tue, 17 Mar 2015 00:42:16 +0000 Subject: [PATCH] [IRCE] Add comments, NFC. This change adds some comments that justify why a potentially overflowing operation is safe. llvm-svn: 232445 --- .../Scalar/InductiveRangeCheckElimination.cpp | 31 +++++++++++++++++++--- 1 file changed, 27 insertions(+), 4 deletions(-) diff --git a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp index 0429aee..22ce711 100644 --- a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -845,12 +845,35 @@ LoopConstrainer::calculateSubRanges() const { const SCEV *End = SE.getSCEV(MainLoopStructure.LoopExitAt); bool Increasing = MainLoopStructure.IndVarIncreasing; + // We compute `Smallest` and `Greatest` such that [Smallest, Greatest) is the // range of values the induction variable takes. - const SCEV *Smallest = - Increasing ? Start : SE.getAddExpr(End, SE.getSCEV(One)); - const SCEV *Greatest = - Increasing ? End : SE.getAddExpr(Start, SE.getSCEV(One)); + + const SCEV *Smallest = nullptr, *Greatest = nullptr; + + if (Increasing) { + Smallest = Start; + Greatest = End; + } else { + // These two computations may sign-overflow. Here is why that is okay: + // + // We know that the induction variable does not sign-overflow on any + // iteration except the last one, and it starts at `Start` and ends at + // `End`, decrementing by one every time. + // + // * if `Smallest` sign-overflows we know `End` is `INT_SMAX`. Since the + // induction variable is decreasing we know that that the smallest value + // the loop body is actually executed with is `INT_SMIN` == `Smallest`. + // + // * if `Greatest` sign-overflows, we know it can only be `INT_SMIN`. In + // that case, `Clamp` will always return `Smallest` and + // [`Result.LowLimit`, `Result.HighLimit`) = [`Smallest`, `Smallest`) + // will be an empty range. Returning an empty range is always safe. + // + + Smallest = SE.getAddExpr(End, SE.getSCEV(One)); + Greatest = SE.getAddExpr(Start, SE.getSCEV(One)); + } auto Clamp = [this, Smallest, Greatest](const SCEV *S) { return SE.getSMaxExpr(Smallest, SE.getSMinExpr(Greatest, S)); -- 2.7.4