[SCEV] Do not cache S -> V if S is not equivalent of V

[skatkov]

Summary

SCEV tracks the correspondence of created SCEV to original instruction.
However during creation of SCEV it is possible that nuw/nsw/exact flags are
lost.

As a result during expansion of the SCEV the instruction with nuw/nsw/exact
will be used where it was expected and we produce poison incorreclty.

[sanjoy]

lgtm!

lib/Analysis/ScalarEvolution.cpp

3773

Why BS?

3776

I think you also need to check for I having the exact bit set.

[skatkov]

lib/Analysis/ScalarEvolution.cpp

3773

BinarySCEV ? :)

[sanjoy]

lib/Analysis/ScalarEvolution.cpp

3773

But it is n-ary SCEV (add / multiply expressions in SCEV can take an arbitrary number of operands).

[skatkov]

NAS is better?

Can I lend it with BS -> NAS?

[skatkov]

oops, I did not update with exact yet... Will be published soon (as soon as testing completes).

[sanjoy]

In D41578#964304, @skatkov wrote:

NAS is better?

I'd just go with NS.

[skatkov]

Thanks! Unfortunately adding check for exact causes the failure of Transforms/LoopStrengthReduce/post-inc-icmpzero.ll. Will take a look into it.

[skatkov]

Hi Sanjoy, I wonder whether SCEV has some equivalent of exact flag?

[sanjoy]

In D41578#964321, @skatkov wrote:

Hi Sanjoy, I wonder whether SCEV has some equivalent of exact flag?

No.

[skatkov]

test/Transforms/LoopStrengthReduce/post-inc-icmpzero.ll

56 ↗

(On Diff #128202)

Actually I realized that this test shows that my solution is not complete. This is better than nothing and fixes the bug I'm working on but it is not a full solution.

The problem is that poison is transitive. Specifically within this patch it will to set SCEV->%sub.ptr.div39 mapping but will set SCEV->%idx.ext21.

And that is not correct.

I tend to land this patch and add TODO into SCEVLostPoisonFlags that we must consider not exactly instruction but really answer to the question whether I can lead to poison...

What do you think?

[eastig]

Hi Sergey,

The patch caused 4% regression in one of our benchmarks. It affected LoopStrength Reduction. I don't have a full reproducer yet but maybe the following will be enough to figure out the issue:

IR before the patch

while.end83.i:                                    ; preds = %while.end83.isplit, %while.body76.3.i.while.end83.i_crit_edge
  ...
  %mul86.i = mul nuw nsw i32 %phitmp280.i, %phitmp.i
  %sub.ptr.lhs.cast.i = ptrtoint i8* %incdec.ptr70.lcssa.i to i32
  %mul88.i = mul i32 %mul86.i, 3
  %sub.ptr.sub.i = add i32 %mul88.i, %sub.ptr.lhs.cast.i
  %add89.i = sub i32 %sub.ptr.sub.i, ptrtoint (...)
  %cmp90.i = icmp eq i32 %add89.i, 230416
  br i1 %cmp90.i, label %if.end94.i, label %if.then92.i


if.end94.i:                                       ; preds = %while.end83.i
  ...
  %cmp97.i = icmp eq i8* %call96.i, null
  br i1 %cmp97.i, label %if.then99.i, label %if.end100.i

if.then99.i:                                      ; preds = %if.end94.i
  ...
  br label %if.end100.i

if.end100.i:                                      ; preds = %if.then99.i, %if.end94.i
  ...
  %cmp101247.i = icmp eq i32 %13, 0
  br i1 %cmp101247.i, label %for.end147.i, label %for.body.lr.ph.i

for.body.lr.ph.i:                                 ; preds = %if.end100.i
  %cmp104243.i = icmp eq i32 %mul86.i, 0
  br i1 %cmp104243.i, label %for.body.preheader.i, label %for.body.us.preheader.i

for.body.us.preheader.i:                          ; preds = %for.body.lr.ph.i
  %14 = add nsw i32 %mul86.i, -1
  %xtraiter289.i = and i32 %mul86.i, 3
  %15 = icmp ult i32 %14, 3
  %lcmp.mod292.i = icmp eq i32 %xtraiter289.i, 0
  %epil.iter.cmp291.i = icmp eq i32 %xtraiter289.i, 1
  %epil.iter.cmp291.1.i = icmp eq i32 %xtraiter289.i, 2
  %16 = sub i32 %xtraiter289.i, %mul86.i

IR after the patch

while.end83.i:                                    ; preds = %while.end83.isplit, %while.body76.3.i.while.end83.i_crit_edge
  ...
  %mul86.i = mul nuw nsw i32 %phitmp280.i, %phitmp.i
  %sub.ptr.lhs.cast.i = ptrtoint i8* %incdec.ptr70.lcssa.i to i32
  %mul88.i = mul i32 %mul86.i, 3
  %sub.ptr.sub.i = add i32 %mul88.i, %sub.ptr.lhs.cast.i
  %add89.i = sub i32 %sub.ptr.sub.i, ptrtoint (...)
  %cmp90.i = icmp eq i32 %add89.i, 230416
  br i1 %cmp90.i, label %if.end94.i, label %if.then92.i

if.end94.i:                                       ; preds = %while.end83.i
  ...
  %cmp97.i = icmp eq i8* %call96.i, null
  br i1 %cmp97.i, label %if.then99.i, label %if.end100.i

if.then99.i:                                      ; preds = %if.end94.i
  ...
  br label %if.end100.i

if.end100.i:                                      ; preds = %if.then99.i, %if.end94.i
  ...
  %cmp101247.i = icmp eq i32 %13, 0
  br i1 %cmp101247.i, label %for.end147.i, label %for.body.lr.ph.i

for.body.lr.ph.i:                                 ; preds = %if.end100.i
  %cmp104243.i = icmp eq i32 %mul86.i, 0
  br i1 %cmp104243.i, label %for.body.preheader.i, label %for.body.us.preheader.i

for.body.us.preheader.i:                          ; preds = %for.body.lr.ph.i
  %14 = add nsw i32 %mul86.i, -1
  %xtraiter289.i = and i32 %mul86.i, 3
  %15 = icmp ult i32 %14, 3
  %lcmp.mod292.i = icmp eq i32 %xtraiter289.i, 0
  %epil.iter.cmp291.i = icmp eq i32 %xtraiter289.i, 1
  %epil.iter.cmp291.1.i = icmp eq i32 %xtraiter289.i, 2
  %16 = mul i32 %phitmp280.i, %phitmp.i
  %17 = sub i32 %xtraiter289.i, %16

The patch caused '%16 = mul i32 %phitmp280.i, %phitmp.i' to appear in the loop.

Any idea what to look at?

Thanks,
Evgeny Astigeevich

[skatkov]

Hi Evgeny, thank you for reporting the problem.

According to IR you posted the patch did what it expected to do.
Specifically, there is an instruction
%mul86.i = mul nuw nsw i32 %phitmp280.i, %phitmp.i
which most probably used in SCEV creation. Somehow SCEV lost nuw/nsw flags.

Before the patch, the matching S -> %mul86.i has been saved for later re-use.
Within this patch It does not keep this matching because SCEV without nuw/nsw should not correspond to instruction with nuw/nsw.

Later when someone expanded this SCEV S at point
sub i32 %xtraiter289.i, ...

Before the patch it was able to re-use %mul86.i (as soon matching is present) and after the patch it could do so due to no matching.
Instead it literally expanded this SCEV to new mul instruction.

What I see can be done here (any of):

1. Try to analyze why SCEV lost nuw/nsw information and possible fix/extend that place to preserve nuw/nsw in SCEV. In this case matching will still in place and new mul instruction will not be generated.
2. Potentially "%mul86.i = mul nuw nsw i32 %phitmp280.i, %phitmp.i" can be replaced with "%16 = mul i32 %phitmp280.i, %phitmp.i". It can be done by some other pass but I'm not sure who should be responsible for that. I guess GVN can do this but not sure that it works after LSR in your pipeline.
3. We can update this code to clean poison flags from instruction if built SCEV lost information about these flags. To my understanding cleaning of poison flags is a safe operation from correctness point of view but it can prohibit some optimization opportunities because we loose some valuable information.

To be honest I'm not sure what approach is a best here. I'd like to get a feedback from Sanjoy and others...

[eastig]

Sergey,
Thank you for the initial analysis. I'll try to debug SCEV.

[sanjoy]

In D41578#973016, @skatkov wrote:

What I see can be done here (any of):

1. Try to analyze why SCEV lost nuw/nsw information and possible fix/extend that place to preserve nuw/nsw in SCEV. In this case matching will still in place and new mul instruction will not be generated.
2. Potentially "%mul86.i = mul nuw nsw i32 %phitmp280.i, %phitmp.i" can be replaced with "%16 = mul i32 %phitmp280.i, %phitmp.i". It can be done by some other pass but I'm not sure who should be responsible for that. I guess GVN can do this but not sure that it works after LSR in your pipeline.
3. We can update this code to clean poison flags from instruction if built SCEV lost information about these flags. To my understanding cleaning of poison flags is a safe operation from correctness point of view but it can prohibit some optimization opportunities because we loose some valuable information.

To be honest I'm not sure what approach is a best here. I'd like to get a feedback from Sanjoy and others...

Given that this pessimization is happening in LSR which runs pretty late, I would be okay with (3) -- most of the nsw/nuw flag specific optimizations would have already happened by now so there is no big reason to keep the flags anymore.

[skatkov]

In D41578#973699, @sanjoy wrote:

In D41578#973016, @skatkov wrote:

What I see can be done here (any of):

1. Try to analyze why SCEV lost nuw/nsw information and possible fix/extend that place to preserve nuw/nsw in SCEV. In this case matching will still in place and new mul instruction will not be generated.
2. Potentially "%mul86.i = mul nuw nsw i32 %phitmp280.i, %phitmp.i" can be replaced with "%16 = mul i32 %phitmp280.i, %phitmp.i". It can be done by some other pass but I'm not sure who should be responsible for that. I guess GVN can do this but not sure that it works after LSR in your pipeline.
3. We can update this code to clean poison flags from instruction if built SCEV lost information about these flags. To my understanding cleaning of poison flags is a safe operation from correctness point of view but it can prohibit some optimization opportunities because we loose some valuable information.

To be honest I'm not sure what approach is a best here. I'd like to get a feedback from Sanjoy and others...

Given that this pessimization is happening in LSR which runs pretty late, I would be okay with (3) -- most of the nsw/nuw flag specific optimizations would have already happened by now so there is no big reason to keep the flags anymore.

Hi Sanjoy, I guess this piece of code is common one and will be executed SCEV is created each time whenever it is a LSR or earlier passes. Do you propose to introduce some flag and use it in LSR?
This seems to me very intrusive fix.

I also thought about clearing of nuw/nsw at moment of expansion. Specifically when we check whether there is a instruction for SCEV, first we can give a priority for the instruction without nuw/nsw and second even if we decide to use instruction with nuw/nsw we can clean these flags at that moment. At least it should reduce the cases when we clean up these flags (only when expansion happens). I think the better fix would be really to understand why SCEV looses these flags and fix/extend that place and as I understand Evgeny looks in this direction.

[sanjoy]

In D41578#974249, @skatkov wrote:

Hi Sanjoy, I guess this piece of code is common one and will be executed SCEV is created each time whenever it is a LSR or earlier passes. Do you propose to introduce some flag and use it in LSR?
This seems to me very intrusive fix.

There is already a SCEVExpander::LSRMode.

I think the better fix would be really to understand why SCEV looses these flags and fix/extend that place and as I understand Evgeny looks in this direction.

Agreed.

[eastig]

I have found that the patch also caused 7.31% regression in SPEC2k6 401.bzip2 on Cortex-A57 (AArch64).

[skatkov]

Hi Evgeny, please let me know if you need some more deep explanation about workaround Sanjoy and I mentioned in terms of stripping nuw/nsw for instruction in case you are in LSR.

This is for the case: the regressions are urgent for you and you need some quick workaround while you are investigating why SCEV lost the poison flags.

[eastig]

In D41578#975919, @skatkov wrote:

Hi Evgeny, please let me know if you need some more deep explanation about workaround Sanjoy and I mentioned in terms of stripping nuw/nsw for instruction in case you are in LSR.

This is for the case: the regressions are urgent for you and you need some quick workaround while you are investigating why SCEV lost the poison flags.

I am working on a reproducer. The IR causing the issue is a result of LTO. It's huge and has a lot of loops. As soon as I reduce it to something small I'll start debugging.

Thanks,
Evgeny

[eastig]

A reproducer:

test.ll2 KBDownload

$ opt.patch.off -loop-reduce -S -o test.patch.off.ll test.ll
$ opt -loop-reduce -S -o test.patch.on.ll test.ll
$ diff test.patch.off.ll test.patch.on.ll
26c26,27
<   %0 = sub i32 %xtraiter289.i, %mul86.i
---
>   %0 = mul i32 %p281, %p280
>   %1 = sub i32 %xtraiter289.i, %0
37c38
<   %lsr.iv = phi i32 [ %0, %for.body106.us.i.preheader ], [ %lsr.iv.next, %for.body106.us.i ]
---
>   %lsr.iv = phi i32 [ %1, %for.body106.us.i.preheader ], [ %lsr.iv.next, %for.body106.us.i ]

[eastig]

Hi Sergey and Sanjoy,

To set flags ScalarEvolution::createSCEV calls:

SCEV::NoWrapFlags ScalarEvolution::getNoWrapFlagsFromUB(const Value *V) {
  if (isa<ConstantExpr>(V)) return SCEV::FlagAnyWrap;
  const BinaryOperator *BinOp = cast<BinaryOperator>(V);

  // Return early if there are no flags to propagate to the SCEV.
  SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
  if (BinOp->hasNoUnsignedWrap())
    Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
  if (BinOp->hasNoSignedWrap())
    Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
  if (Flags == SCEV::FlagAnyWrap)
    return SCEV::FlagAnyWrap;

  return isSCEVExprNeverPoison(BinOp) ? Flags : SCEV::FlagAnyWrap;
}

For "%mul86.i = mul nuw nsw i32 %p280, %p281" isSCEVExprNeverPoison return false which causes the SCEV '(%p280 * %p281)' to have SCEV::FlagAnyWrap instead of a combination of SCEV::FlagNUW and Flags, SCEV::FlagNSW.

Am I correct SCEV::FlagAnyWrap means no poisoned values? If so, this looks strange. Shouldn't it be:

return isSCEVExprNeverPoison(BinOp) ? SCEV::FlagAnyWrap : Flags;

[skatkov]

In D41578#978975, @eastig wrote:

Hi Sergey and Sanjoy,

To set flags ScalarEvolution::createSCEV calls:

SCEV::NoWrapFlags ScalarEvolution::getNoWrapFlagsFromUB(const Value *V) {
  if (isa<ConstantExpr>(V)) return SCEV::FlagAnyWrap;
  const BinaryOperator *BinOp = cast<BinaryOperator>(V);

  // Return early if there are no flags to propagate to the SCEV.
  SCEV::NoWrapFlags Flags = SCEV::FlagAnyWrap;
  if (BinOp->hasNoUnsignedWrap())
    Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNUW);
  if (BinOp->hasNoSignedWrap())
    Flags = ScalarEvolution::setFlags(Flags, SCEV::FlagNSW);
  if (Flags == SCEV::FlagAnyWrap)
    return SCEV::FlagAnyWrap;

  return isSCEVExprNeverPoison(BinOp) ? Flags : SCEV::FlagAnyWrap;
}

For "%mul86.i = mul nuw nsw i32 %p280, %p281" isSCEVExprNeverPoison return false which causes the SCEV '(%p280 * %p281)' to have SCEV::FlagAnyWrap instead of a combination of SCEV::FlagNUW and Flags, SCEV::FlagNSW.

Am I correct SCEV::FlagAnyWrap means no poisoned values? If so, this looks strange. Shouldn't it be:

As I understand this flag means have no idea, in other words may overflow.

return isSCEVExprNeverPoison(BinOp) ? SCEV::FlagAnyWrap : Flags;

No, I read this code as if isSCEVExprNeverPoison(BinOp) is true then we can trust the flags otherwise we cannot...

But it would be better to hear Sanjoy's opinion here.

[eastig]

In D41578#979947, @skatkov wrote:

For "%mul86.i = mul nuw nsw i32 %p280, %p281" isSCEVExprNeverPoison return false which causes the SCEV '(%p280 * %p281)' to have SCEV::FlagAnyWrap instead of a combination of SCEV::FlagNUW and Flags, SCEV::FlagNSW.

Am I correct SCEV::FlagAnyWrap means no poisoned values? If so, this looks strange. Shouldn't it be:

As I understand this flag means have no idea, in other words may overflow.

When SCEV::FlagAnyWrap is set SCEVNAryExpr::hasNoUnsignedWrap and SCEVNAryExpr::hasNoSignedWrap return false:

bool hasNoUnsignedWrap() const {
  return getNoWrapFlags(FlagNUW) != FlagAnyWrap;
}

bool hasNoSignedWrap() const {
  return getNoWrapFlags(FlagNSW) != FlagAnyWrap;
}

From this I can conclude SCEV::FlagAnyWrap mean no poisoned values.

return isSCEVExprNeverPoison(BinOp) ? SCEV::FlagAnyWrap : Flags;

No, I read this code as if isSCEVExprNeverPoison(BinOp) is true then we can trust the flags otherwise we cannot...

But it would be better to hear Sanjoy's opinion here.

Sergey, it looks like your patch does not take into account that nsw and nuw have not been set because of additional analysis, e.g. isSCEVExprNeverPoison. So SCEVLostPoisonFlags thinks flags are lost but they were not set intentionally. Where the issue your patch fixes come from? I don't see any IR test.

[skatkov]

In D41578#980133, @eastig wrote:

In D41578#979947, @skatkov wrote:

For "%mul86.i = mul nuw nsw i32 %p280, %p281" isSCEVExprNeverPoison return false which causes the SCEV '(%p280 * %p281)' to have SCEV::FlagAnyWrap instead of a combination of SCEV::FlagNUW and Flags, SCEV::FlagNSW.

Am I correct SCEV::FlagAnyWrap means no poisoned values? If so, this looks strange. Shouldn't it be:

As I understand this flag means have no idea, in other words may overflow.

When SCEV::FlagAnyWrap is set SCEVNAryExpr::hasNoUnsignedWrap and SCEVNAryExpr::hasNoSignedWrap return false:

bool hasNoUnsignedWrap() const {
  return getNoWrapFlags(FlagNUW) != FlagAnyWrap;
}

bool hasNoSignedWrap() const {
  return getNoWrapFlags(FlagNSW) != FlagAnyWrap;
}

From this I can conclude SCEV::FlagAnyWrap mean no poisoned values.

return isSCEVExprNeverPoison(BinOp) ? SCEV::FlagAnyWrap : Flags;

No, I read this code as if isSCEVExprNeverPoison(BinOp) is true then we can trust the flags otherwise we cannot...

But it would be better to hear Sanjoy's opinion here.

Sergey, it looks like your patch does not take into account that nsw and nuw have not been set because of additional analysis, e.g. isSCEVExprNeverPoison. So SCEVLostPoisonFlags thinks flags are lost but they were not set intentionally. Where the issue your patch fixes come from? I don't see any IR test.

I understand what you mean, however the patch does a right thing in general. SCEV without nuw/nsw should not correspond to instruction within these flags.
The functional bug I had looked as follows:
there were two instructions, say:
%a = add nuw nsw %c, -1
%b = add %c, -1

First for instruction %a the SCEV S has been built.
Then for instruction %b SCEV S' has been build. Due to loosing the nuw/nsw flags S == S'.
Later SCEV expander has been used to expand S'. But as soon as we mapped S'==S => %a, %a has been used as expansion of S'.
So in reality it resulted in %a with nuw/nsw has been used where %b should be used and it introduces usage of nuw/nsw instruction where it was not expected.
The later backend did a wrong code generation for -1 due to present of nuw/nsw flags in an instruction.

Let me try to add a clearance of nuw/nsw flags in expander as I explained before...

[skatkov]

Evgeny, I posted an alternate solution https://reviews.llvm.org/D42290. Could you please check whether it fixes your regression and do not introduce others?

[eastig]

In D41578#981582, @skatkov wrote:

Evgeny, I posted an alternate solution https://reviews.llvm.org/D42290. Could you please check whether it fixes your regression and do not introduce others?

Hi Sergey,
I checked it fixes regressions. Could the test I posted here be added as a regression test to D42290?

Thanks,
Evgeny

[skatkov]

In D41578#984351, @eastig wrote:

In D41578#981582, @skatkov wrote:

Evgeny, I posted an alternate solution https://reviews.llvm.org/D42290. Could you please check whether it fixes your regression and do not introduce others?

Hi Sergey,
I checked it fixes regressions. Could the test I posted here be added as a regression test to D42290?

Did you check whether it introduces new regressions?
I will add. Anyway I will wait for review from Sanjoy...

Thanks,
Evgeny

[eastig]

In D41578#984613, @skatkov wrote:

In D41578#984351, @eastig wrote:

In D41578#981582, @skatkov wrote:

Evgeny, I posted an alternate solution https://reviews.llvm.org/D42290. Could you please check whether it fixes your regression and do not introduce others?

Hi Sergey,
I checked it fixes regressions. Could the test I posted here be added as a regression test to D42290?

Did you check whether it introduces new regressions?
I will add. Anyway I will wait for review from Sanjoy...

I have not seen new regressions.

lib/Analysis/ScalarEvolution.cpp

if (I != ValueExprMap.end()) {
     if (Offset != nullptr) {
       if (SetVector<ValueOffsetPair> *SV = getSCEVValues(Stripped))
         SV->remove({V, Offset});
     }
     ValueExprMap.erase(V);
   }
 }
 
+/// Check whether value has nuw/nsw set but SCEV does not.
+static bool SCEVLostWrapFlags(const SCEV *S, const Value *V) {
+  if (auto *I = dyn_cast<Instruction>(V))
+    if (isa<OverflowingBinaryOperator>(I))
+      if (auto *BS = dyn_cast<SCEVNAryExpr>(S)) {
+        if (I->hasNoSignedWrap() && !BS->hasNoSignedWrap())
+          return true;
+        if (I->hasNoUnsignedWrap() && !BS->hasNoUnsignedWrap())
+          return true;
+      }
+  return false;
+}
+
 /// Return an existing SCEV if it exists, otherwise analyze the expression and
 /// create a new one.
 const SCEV *ScalarEvolution::getSCEV(Value *V) {
   assert(isSCEVable(V->getType()) && "Value is not SCEVable!");
 
   const SCEV *S = getExistingSCEV(V);
   if (S == nullptr) {
     S = createSCEV(V);
     // During PHI resolution, it is possible to create two SCEVs for the same
     // V, so it is needed to double check whether V->S is inserted into
     // ValueExprMap before insert S->{V, 0} into ExprValueMap.
     std::pair<ValueExprMapType::iterator, bool> Pair =
         ValueExprMap.insert({SCEVCallbackVH(V, this), S});
-    if (Pair.second) {
+    if (Pair.second && !SCEVLostWrapFlags(S, V)) {
       ExprValueMap[S].insert({V, nullptr});
 
       // If S == Stripped + Offset, add Stripped -> {V, Offset} into
       // ExprValueMap.
       const SCEV *Stripped = S;
       ConstantInt *Offset = nullptr;
       std::tie(Stripped, Offset) = splitAddExpr(S);
       // If stripped is SCEVUnknown, don't bother to save

unittests/Analysis/ScalarEvolutionTest.cpp

TEST_F(ScalarEvolutionsTest, SCEVExpanderIsSafeToExpandAt) {
   const SCEVAddRecExpr *AR = cast<SCEVAddRecExpr>(S);
   EXPECT_TRUE(AR->isAffine());
   EXPECT_FALSE(isSafeToExpandAt(AR, Top->getTerminator(), SE));
   EXPECT_FALSE(isSafeToExpandAt(AR, LPh->getTerminator(), SE));
   EXPECT_TRUE(isSafeToExpandAt(AR, L->getTerminator(), SE));
   EXPECT_TRUE(isSafeToExpandAt(AR, Post->getTerminator(), SE));
 }
 
+// Check that SCEV does not save the SCEV -> V
+// mapping of SCEV differ from V in NUW flag.
+TEST_F(ScalarEvolutionsTest, SCEVCacheNUW) {
+  /*
+   * Create the following code:
+   * func(i64 %a)
+   * entry:
+   *  %s1 = add i64 %a, -1
+   *  %s2 = add nuw i64 %a, -1
+   *  br label %exit
+   * exit:
+   *  ret %s
+   */
+
+  // Create a module.
+  Module M("SCEVCacheNUW", Context);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false);
+  Function *F = cast<Function>(M.getOrInsertFunction("func", FTy));
+  Argument *Arg = &*F->arg_begin();
+  ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));
+
+  BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
+  BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
+
+  IRBuilder<> Builder(Entry);
+  auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
+  auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
+  S2->setHasNoUnsignedWrap(true);
+  Builder.CreateBr(Exit);
+
+  Builder.SetInsertPoint(Exit);
+  auto *R = cast<Instruction>(Builder.CreateRetVoid());
+
+  ScalarEvolution SE = buildSE(*F);
+  // Get S2 first to move it to cache.
+  const SCEV *SC2 = SE.getSCEV(S2);
+  EXPECT_TRUE(isa<SCEVAddExpr>(SC2));
+  // Now get S1.
+  const SCEV *SC1 = SE.getSCEV(S1);
+  EXPECT_TRUE(isa<SCEVAddExpr>(SC1));
+  // Expand for S1, it should use S1 not S2 in spite S2
+  // first in the cache.
+  SCEVExpander Exp(SE, M.getDataLayout(), "expander");
+  auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));
+  EXPECT_FALSE(I->hasNoUnsignedWrap());
+}
+
+// Check that SCEV does not save the SCEV -> V
+// mapping of SCEV differ from V in NSW flag.
+TEST_F(ScalarEvolutionsTest, SCEVCacheNSW) {
+  /*
+   * Create the following code:
+   * func(i64 %a)
+   * entry:
+   *  %s1 = add i64 %a, -1
+   *  %s2 = add nsw i64 %a, -1
+   *  br label %exit
+   * exit:
+   *  ret %s
+   */
+
+  // Create a module.
+  Module M("SCEVCacheNUW", Context);
+
+  Type *T_int64 = Type::getInt64Ty(Context);
+
+  FunctionType *FTy =
+      FunctionType::get(Type::getVoidTy(Context), { T_int64 }, false);
+  Function *F = cast<Function>(M.getOrInsertFunction("func", FTy));
+  Argument *Arg = &*F->arg_begin();
+  ConstantInt *C = ConstantInt::get(Context, APInt(64, -1));
+
+  BasicBlock *Entry = BasicBlock::Create(Context, "entry", F);
+  BasicBlock *Exit = BasicBlock::Create(Context, "exit", F);
+
+  IRBuilder<> Builder(Entry);
+  auto *S1 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
+  auto *S2 = cast<Instruction>(Builder.CreateAdd(Arg, C, "add"));
+  S2->setHasNoSignedWrap(true);
+  Builder.CreateBr(Exit);
+
+  Builder.SetInsertPoint(Exit);
+  auto *R = cast<Instruction>(Builder.CreateRetVoid());
+
+  ScalarEvolution SE = buildSE(*F);
+  // Get S2 first to move it to cache.
+  const SCEV *SC2 = SE.getSCEV(S2);
+  EXPECT_TRUE(isa<SCEVAddExpr>(SC2));
+  // Now get S1.
+  const SCEV *SC1 = SE.getSCEV(S1);
+  EXPECT_TRUE(isa<SCEVAddExpr>(SC1));
+  // Expand for S1, it should use S1 not S2 in spite S2
+  // first in the cache.
+  SCEVExpander Exp(SE, M.getDataLayout(), "expander");
+  auto *I = cast<Instruction>(Exp.expandCodeFor(SC1, nullptr, R));
+  EXPECT_FALSE(I->hasNoSignedWrap());
+}
+
 }  // end anonymous namespace
 }  // end namespace llvm