Eliminates dead store of an exisiting value

[dmccrevan]

Summary

Related to 16520

This change eliminates writes to variables where the value that is being written is already stored in the variable. This achieves the goal by looping through all memory defintions in the current state & each defintions uses. When there is a use where the write instruction is identical to the original instruction that created the memory definition, it will remove this redundant write.

For example,

void f() {
  x = 1;
  if foo() {
     x = 1;
     g();
  } else {
    h();
  }
}
void g();
void h();

The second x=1 will be eliminated since it is rewriting 1 to x. This pass will produce this:

void f() {
  x = 1;
  if foo() {
     g();
  } else {
    h();
  }
}
void g();
void h();

[dmccrevan]

Added test case for eliminateDeadStoresOfExisitingValues

[lebedev.ri]

When uploading a new diff, make sure that the patch you're uploading is against the git master, not the previously uploaded diff/etc

[dmccrevan]

In D90328#2359884, @lebedev.ri wrote:

When uploading a new diff, make sure that the patch you're uploading is against the git master, not the previously uploaded diff/etc

Sorry, yeah I just realized I did that when uploading the change with the test...is there a way to revert this? Or should I abandon the revision and open a new one?

[dmccrevan]

Disregard the previous comment, fixed the revision.

[fhahn]

Thanks for sharing the patch! Some initial comments inline. It would also be good to explain the approach in a comment and also in the patch description.

It would be interesting to know how often this triggers. For testing, you could try using a build of clang with the patch with https://www.llvm.org/docs/TestSuiteGuide.html

There's a TEST_SUITE_COLLECT_STATS which tells clang to collect statistics in the result.json file. The interesting one would probably be dse.NumFastStores

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2379

Initially it would probably be best to start with just looking at the direct uses of the def and then go from there. One thing to watch out for is compile-time.

llvm/test/Transforms/DeadStoreElimination/MSSA/pr16520.ll

1 ↗

(On Diff #301403)

this test needs RUN & CHECK lines. You should be able to get some inspiration from other files in the directory.

[dmccrevan]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2379

I've been trying to figure out how to get the uses of each def, but for some reason, I keep running into an error being thrown.

This is a snippet I am using to get the uses, but for some reason, getUser() is throwing an error.

MemoryAccess *DefAccess = dyn_cast<MemoryAccess>(Def);
if (isa<MemoryPhi>(DefAccess))
    continue;
for(Use &U : DefAccess->uses()) {
    MemoryAccess * UseAccess = cast<MemoryAccess>(U.getUser());

Any ideas how to get all of the uses from a Def?

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2379

Any ideas how to get all of the uses from a Def?

That should be the way to do it.

What's the error?

One thing that looks suspicious is that you are using *DefAccess without checking if it is not null? (dyn_cast will return nullptr if the value does not have the requested type).

[dmccrevan]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2379

Ah that must be why! I will try this, sorry about the late reply previously, I realized I never submitted my comment and it sat as a draft.

[dmccrevan]

So I fixed up the implementation by removing the worklist & just looped through the uses. For some reason, I had to add a lot of NULL checks to ensure that each variable I used wasn't NULL, but I feel like there may be another way to do this using separate functions I may not be aware of.

I also changed up the test case file, but I am unsure if this works yet. I ran into a build issue when following the instructions for the test-suite. I am rebuilding my LLVM build again to see if there was some issue with my clang build, and I will see if this works. If not, I will post the error message if I cannot debug it myself. Sadly, building LLVM on my laptop takes a while since I do not have powerful hardware.

[fhahn]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2373

It is common to avoid compares with NULL/nullptr and instead use if (!DefAccess). Also, the condition can be combined with the one below?

2385

Style guide suggest to not use {} for single line bodies.

2388

You need to check if UseDefAccess is actually a use or def. It could be a MemoryPhi.

You could use something like MemoryAccess *UseDefAccess = dyn_cast_or_null<MemoryUseOrDef>(UseDef->getDefiningAccess())

Test case

define void @main(i32* %a, i32* %b, i1 %c) {
entry:
  br label %for.body

for.body:                                         ; preds = %if.end8, %entry
  br i1 %c, label %exit, label %loop.latch

loop.latch:                                          ; preds = %for.body
  store i32 0 , i32* %a
  store i32 1, i32* %b
  br label %for.body

exit:                                         ; preds = %for.body
  call void @foo()
  ret void
}

declare void @foo()

[fhahn]

A few more comments inline. I think before checking the patch with Clang on C/C++ code, it would be good to make sure that all unit tests pass ( check-llvm-transforms-deadstoreelimination target)

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2371

It is possible that memory defs in MemDefs get deleted. You need to skip defs in SkipStores.

2381

If we change below to remove the UseInst, we need to use iterators with early increment here, to avoid iterator invalidation.

2384

Why are we getting get defining access here? Shouldn't we just look at the uses?

2393

This seems off, shouldn't we remove DefInst? Also, we need to make sure we only remove defs that do not also read memory I think.

[dmccrevan]

So actually I just realized that my current implementation I have on this revision isn't correct. For some reason, I must've not noticed the test result is different.

I began to adapt my code to fix it, but I am running into an error. When I use the WorkList/Visited approach, this works and it seems to not increase the amount of time it loops through the code.

This implementation works:

SmallVector<MemoryAccess *, 4> WorkList;
SmallPtrSet<MemoryAccess *, 8> Visited;
auto PushMemUses = [&WorkList, &Visited](MemoryAccess *Acc) {
  if (!Visited.insert(Acc).second)
    return;
  for (Use &U : Acc->uses())
    WorkList.push_back(cast<MemoryAccess>(U.getUser()));
};
PushMemUses(Def);
for(auto x : WorkList) {
  if(MemoryDef *UseDef = dyn_cast_or_null<MemoryDef>(x)) {
    Instruction *UseInst = UseDef->getMemoryInst();
    if (!UseInst)
      continue;
    if (UseInst->isIdenticalTo(DefInst)) {
      deleteDeadInstruction(UseInst);
      MadeChange = true;
    }
  }
}

This implementation throws the error below

for (Use &U : DefAccess->uses()) {
  if(!U) 
    continue;
  MemoryAccess *UseAccess = dyn_cast_or_null<MemoryAccess>(U.getUser());
  if(!UseAccess)
    continue;
  if (MemoryDef *UseDef = dyn_cast_or_null<MemoryDef>(UseAccess)) {
    Instruction *UseInst = UseDef->getMemoryInst();
    if (!UseInst)
      continue;
    if (UseInst->isIdenticalTo(DefInst)) {
      deleteDeadInstruction(UseInst);
      MadeChange = true;
    }
  }
}

Stack dump:
0.	Program arguments: ./opt -dse -S -debug pr16520.ll 
1.	Running pass 'Function Pass Manager' on module 'pr16520.ll'.
2.	Running pass 'Dead Store Elimination' on function '@_Z1fbRb'
 #0 0x000000000366d017 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/Support/Unix/Signals.inc:563:22
 #1 0x000000000366d0ce PrintStackTraceSignalHandler(void*) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/Support/Unix/Signals.inc:630:1
 #2 0x000000000366b0ea llvm::sys::RunSignalHandlers() /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/Support/Signals.cpp:71:20
 #3 0x000000000366ca6a SignalHandler(int) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/Support/Unix/Signals.inc:405:1
 #4 0x00007fd893bd0a20 __restore_rt (/lib64/libpthread.so.0+0x13a20)
 #5 0x00000000008b1b4e llvm::Value::getValueID() const /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/include/llvm/IR/Value.h:529:12
 #6 0x000000000222aa83 llvm::MemoryAccess::classof(llvm::Value const*) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/include/llvm/Analysis/MemorySSA.h:157:32
 #7 0x000000000223d163 llvm::isa_impl<llvm::MemoryAccess, llvm::User, void>::doit(llvm::User const&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/include/llvm/Support/Casting.h:59:3
 #8 0x000000000223bcd2 llvm::isa_impl_cl<llvm::MemoryAccess, llvm::User const*>::doit(llvm::User const*) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/include/llvm/Support/Casting.h:106:3
 #9 0x000000000223a649 llvm::isa_impl_wrap<llvm::MemoryAccess, llvm::User const*, llvm::User const*>::doit(llvm::User const* const&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/include/llvm/Support/Casting.h:132:3
#10 0x0000000002237ef7 llvm::isa_impl_wrap<llvm::MemoryAccess, llvm::User* const, llvm::User const*>::doit(llvm::User* const&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/include/llvm/Support/Casting.h:124:3
#11 0x0000000002235518 bool llvm::isa<llvm::MemoryAccess, llvm::User*>(llvm::User* const&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/include/llvm/Support/Casting.h:144:1
#12 0x00000000032ab97d llvm::cast_retty<llvm::MemoryAccess, llvm::User*>::ret_type llvm::dyn_cast_or_null<llvm::MemoryAccess, llvm::User>(llvm::User*) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/include/llvm/Support/Casting.h:368:15
#13 0x00000000032a365a (anonymous namespace)::DSEState::eliminateDeadStoresOfExisitingValues() /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp:2431:65
#14 0x00000000032a4e14 (anonymous namespace)::eliminateDeadStoresMemorySSA(llvm::Function&, llvm::AAResults&, llvm::MemorySSA&, llvm::DominatorTree&, llvm::PostDominatorTree&, llvm::TargetLibraryInfo const&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp:2719:14
#15 0x00000000032a533b (anonymous namespace)::DSELegacyPass::runOnFunction(llvm::Function&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp:2795:45
#16 0x0000000002c28b1b llvm::FPPassManager::runOnFunction(llvm::Function&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1519:20
#17 0x0000000002c28d84 llvm::FPPassManager::runOnModule(llvm::Module&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1565:13
#18 0x0000000002c291ae (anonymous namespace)::MPPassManager::runOnModule(llvm::Module&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1634:20
#19 0x0000000002c247ba llvm::legacy::PassManagerImpl::run(llvm::Module&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:615:13
#20 0x0000000002c29995 llvm::legacy::PassManager::run(llvm::Module&) /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/lib/IR/LegacyPassManager.cpp:1762:1
#21 0x00000000008e9914 main /home/daniel/Projects/recurse/llvm-stuff/llvm-project/llvm/tools/opt/opt.cpp:973:15
#22 0x00007fd893683e0a __libc_start_main (/lib64/libc.so.6+0x27e0a)
#23 0x00000000008b144a _start /home/abuild/rpmbuild/BUILD/glibc-2.32/csu/../sysdeps/x86_64/start.S:122:0
fish: “./opt -dse -S -debug pr16520.ll” terminated by signal SIGSEGV (Address boundary error)

The line it is throwing the error on is MemoryAccess *UseAccess = dyn_cast_or_null<MemoryAccess>(U.getUser()); I tried debugging this, but got no luck, should I stick with the worklist idea? I think it doesn't break because of the visited set, but is this something that i could adapt to the other impl?

[fhahn]

In D90328#2379727, @dmccrevan wrote:

The line it is throwing the error on is MemoryAccess *UseAccess = dyn_cast_or_null<MemoryAccess>(U.getUser()); I tried debugging this, but got no luck, should I stick with the worklist idea? I think it doesn't break because of the visited set, but is this something that i could adapt to the other impl?

By deleting a memory access, you are modifying the use list you are iterating over, which can invalidate the iterator. Yo need to increment the iterator before removing the memory access, e.g.

for (auto UI = DefAccess->use_begin(), IE = DefAccess->use_end(); UI != IE;) {
  MemoryAccess *UseAccess = cast<MemoryAccess>((UI++)->getUser());

[fhahn]

reverse ping. Any progress? :)

[dmccrevan]

In D90328#2414775, @fhahn wrote:

reverse ping. Any progress? :)

Sorry, the past couple of weeks have been quite busy for me (just started a new software engineering job ( first one! :-) ). Going to work on the testing this weekend!

[dmccrevan]

So I tried to build the check-llvm-transforms-deadstoreelimination target, but it seems that 4 tests are failing:

********************
********************
Failed Tests (4):
  LLVM :: Transforms/DeadStoreElimination/MSSA/multiblock-loops.ll
  LLVM :: Transforms/DeadStoreElimination/MSSA/multiblock-memoryphis.ll
  LLVM :: Transforms/DeadStoreElimination/MSSA/multiblock-simple.ll
  LLVM :: Transforms/DeadStoreElimination/MSSA/simple.ll

I am not too sure how to interpret the test results, but I am attaching a file to this comment with the build output.

I also have my current implementation below incase you want to comment on anything you see to have issues

/// Eliminates writes to variables where the value that is being written
/// is already stored in the variable
bool eliminateDeadStoresOfExisitingValues() {
  bool MadeChange = false;
  LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs that write the "
                       "already exisiting value\n");
  for (int I = MemDefs.size() - 1; I >= 0; I--) {
    MemoryDef *Def = MemDefs[I];
    if (SkipStores.find(Def) != SkipStores.end() ||
        !isRemovable(Def->getMemoryInst()))
      continue;
    MemoryAccess *DefAccess = dyn_cast<MemoryAccess>(Def);
    if (!DefAccess || isa<MemoryPhi>(DefAccess))
      continue;
    Instruction *DefInst = cast<MemoryUseOrDef>(DefAccess)->getMemoryInst();
    if (!DefInst)
      continue;
    for (auto UI = DefAccess->use_begin(), IE = DefAccess->use_end();
         UI != IE;) {
      MemoryAccess *UseAccess = cast<MemoryAccess>((UI++)->getUser());
      if (MemoryDef *UseDef = dyn_cast_or_null<MemoryDef>(UseAccess)) {
        Instruction *UseInst = UseDef->getMemoryInst();
        if (!UseInst)
          continue;
        if (UseInst->isIdenticalTo(DefInst)) {
          deleteDeadInstruction(UseInst);
          MadeChange = true;
        }
      }
    }
  }
  return MadeChange;
}

buildoutput.txt13 KBDownload

[xbolva00]

Please use llvm/utils/update_test_checks.py to update them. Then please upload all changed files.

[dmccrevan]

In D90328#2427203, @xbolva00 wrote:

Please use llvm/utils/update_test_checks.py to update them. Then please upload all changed files.

I just tried to run this, but it is expecting a test pattern. Is there a specific pattern I should use? Both MSSA & check-llvm-transforms-deadstoreelimination didn't match anything

[xbolva00]

The script will update “check patterns” - then we can say if new changes are fine.

[dmccrevan]

Got it, I ran it like ./utils/update_test_checks.py --opt=../build/bin/opt test/Transforms/DeadStoreElimination/MSSA/simple.ll for each failed test.

[xbolva00]

Right. Please update this patch now.

[xbolva00]

Nice!

llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll

507 ↗

(On Diff #308826)

Would be good to update this comment somehow.

[dmccrevan]

So I just confirmed that the new test case runs & passes, and every other test passed (except the 3 that "expectedly fail").

Is there anything else needed for this to be merged in?

[lebedev.ri]

Terminology check: the store being eliminated isn't so much dead,
it's that the stored value is identical to the currently-stored value,
i.e. the store is effectively a no-op.

Just to check, there is a test for the following:

int data;
data = 0; // keep
data = 0; // eliminate
data = 1; // keep
data = 0; // DON'T eliminate, since last stored value is 1.
data = 0; // eliminate
data = 1; // keep
data = 1; // eliminate

?

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2370–2371

2381–2383

[fhahn]

Thanks for the update! I think it would be best to adjust the existing tests so that this optimization does not trigger, because they test different things. You can use some of those tests in a new file (something like MSSA/redundant-stores.ll), together with the one for PR16520.

In D90328#2428525, @lebedev.ri wrote:

Terminology check: the store being eliminated isn't so much dead,
it's that the stored value is identical to the currently-stored value,
i.e. the store is effectively a no-op.

Yep, it would be better to refer to redundant or no-op stores.

Just to check, there is a test for the following:

int data;
data = 0; // keep
data = 0; // eliminate
data = 1; // keep
data = 0; // DON'T eliminate, since last stored value is 1.
data = 0; // eliminate
data = 1; // keep
data = 1; // eliminate

?

I think in this particular case, the last store kills all other stores regardless of the value, so this transform wouldn't trigger. But we need more unit tests specifically for the transform in the patch.

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2366

Instead of talking about dead stores, I think using the term 'redundant' would be better.

2388

Could you add this case as unit tests?

2389

Could you add a debug message and increment NumRedundantStores similar to the code around line 2682?

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-loops.ll

186 ↗

(On Diff #308826)

I think here it would be better to change the test to make sure the optimization does not trigger, to preserve the original spirit of the test.

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-memoryphis.ll

17 ↗

(On Diff #308826)

I think here it would be better to change the test to make sure the optimization does not trigger, to preserve the original spirit of the test.

llvm/test/Transforms/DeadStoreElimination/MSSA/multiblock-simple.ll

41 ↗

(On Diff #308826)

I think here it would be better to change the test to make sure the optimization does not trigger, to preserve the original spirit of the test.

102 ↗

(On Diff #308826)

I think here it would be better to change the test to make sure the optimization does not trigger, to preserve the original spirit of the test.

156 ↗

(On Diff #308826)

I think here it would be better to change the test to make sure the optimization does not trigger, to preserve the original spirit of the test.

llvm/test/Transforms/DeadStoreElimination/MSSA/pr16520.ll

5 ↗

(On Diff #308826)

this should not be required for DSE.

7 ↗

(On Diff #308826)

Could you also add some more variants of the scenarios from the other tests?

[fhahn]

reverse ping.

I think this is almost ready, it would be great to get the last remaining comments with respect to wording & tests wrapped up.

If you won't be able to follow up on this, it would be great if you could let us know, so potentially someone else could pick it up.

[dmccrevan]

In D90328#2484275, @fhahn wrote:

reverse ping.

I think this is almost ready, it would be great to get the last remaining comments with respect to wording & tests wrapped up.

If you won't be able to follow up on this, it would be great if you could let us know, so potentially someone else could pick it up.

Sorry, still in a busy time.

I switched the name of the function to eliminateRedundantStoresOfExisitingValues. When I reverted my changes in some of the test files, one test now fails unexpectedly. The only reason those changed was because I ran that python script to update the tests.

For the additional tests, if someone else would like to pick that up, I am more than happy to go with that. I am not as well versed with my LLVM IR as many of you are :-).

Sorry about the slowness of this. I was planning on having it wrapped up weeks ago.

[fhahn]

In D90328#2489933, @dmccrevan wrote:

In D90328#2484275, @fhahn wrote:

reverse ping.

I think this is almost ready, it would be great to get the last remaining comments with respect to wording & tests wrapped up.

If you won't be able to follow up on this, it would be great if you could let us know, so potentially someone else could pick it up.

Sorry, still in a busy time.

I switched the name of the function to eliminateRedundantStoresOfExisitingValues. When I reverted my changes in some of the test files, one test now fails unexpectedly. The only reason those changed was because I ran that python script to update the tests.

For the additional tests, if someone else would like to pick that up, I am more than happy to go with that. I am not as well versed with my LLVM IR as many of you are :-).

I precommitted additional tests in 6077d55381a6aa3e947ef7abdc36a7515c598c8a, including changes to update some of the existing tests so the new optimization does not trigger.

Sorry about the slowness of this. I was planning on having it wrapped up weeks ago.

No worries, thanks for all the work on this so far. I think this needs an additional check for self-reads; I think the memmoves in llvm/test/Transforms/DeadStoreElimination/MSSA/simple.ll should not be removed. I'll take a look at that tomorrow.

[fhahn]

Updated to skip self-reads and simplified the code a bit.

[fhahn]

I think this looks good now. I am planning to submit the patch tomorrow or so, unless there are further comments.

[nikic]

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

2371

SkipStores.contains(Def)

2372

This isRemovable checks is performed not on the store we'll try to remove. I think this is mostly okay because isIdenticalTo makes sure that if DefI is removable, so is UseI. The only part that doesn't directly follow is the CB->use_empty() part. Could it be that we first have a libcall with an unused return, and then a libcall with a used return, but otherwise identical?

[nikic]

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=a3904cc77f181cff7355357688edfc392a236f5d&to=b5ccbbb5b1d8fc76e2291a860e4cf0a4787b77d4&stat=instructions Seems mostly fine, only outlier is kimwitu++ in NewPM-O3 configuration (k.cc has 1.25% regression).

Something I don't understand about the general approach here is why we start at the Def store and walk all uses to find a Use store to eliminate. Wouldn't it be more efficient to start at the Use store, and check the defining access? With the current approach, I think we'll only find the cases where Def is the defining access of Use, as everything else would be an indirect use. This approach should also be much easier to make more powerful (by using getClobberingMemoryAccess()) without running into compile-time issues from visiting indirect uses.

[fhahn]

In D90328#2499373, @nikic wrote:

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=a3904cc77f181cff7355357688edfc392a236f5d&to=b5ccbbb5b1d8fc76e2291a860e4cf0a4787b77d4&stat=instructions Seems mostly fine, only outlier is kimwitu++ in NewPM-O3 configuration (k.cc has 1.25% regression).

Something I don't understand about the general approach here is why we start at the Def store and walk all uses to find a Use store to eliminate. Wouldn't it be more efficient to start at the Use store, and check the defining access? With the current approach, I think we'll only find the cases where Def is the defining access of Use, as everything else would be an indirect use. This approach should also be much easier to make more powerful (by using getClobberingMemoryAccess()) without running into compile-time issues from visiting indirect uses.

I don't remember if there was any particular reason to choose this approach to start with. I can't think of anything right now. Let me see if there are any cases that we would miss if we flip things.

[fhahn]

In D90328#2499556, @fhahn wrote:

In D90328#2499373, @nikic wrote:

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=a3904cc77f181cff7355357688edfc392a236f5d&to=b5ccbbb5b1d8fc76e2291a860e4cf0a4787b77d4&stat=instructions Seems mostly fine, only outlier is kimwitu++ in NewPM-O3 configuration (k.cc has 1.25% regression).

Something I don't understand about the general approach here is why we start at the Def store and walk all uses to find a Use store to eliminate. Wouldn't it be more efficient to start at the Use store, and check the defining access? With the current approach, I think we'll only find the cases where Def is the defining access of Use, as everything else would be an indirect use. This approach should also be much easier to make more powerful (by using getClobberingMemoryAccess()) without running into compile-time issues from visiting indirect uses.

I don't remember if there was any particular reason to choose this approach to start with. I can't think of anything right now. Let me see if there are any cases that we would miss if we flip things.

Ah I think I remember now. I think I had an extension in mind that also looked at the uses that are loads to remove any redundant loads read the same location. Not sure how relevant this is in practice. I'll check.

[xbolva00]

In D90328#2499595, @fhahn wrote:

In D90328#2499556, @fhahn wrote:

In D90328#2499373, @nikic wrote:

Compile-time: https://llvm-compile-time-tracker.com/compare.php?from=a3904cc77f181cff7355357688edfc392a236f5d&to=b5ccbbb5b1d8fc76e2291a860e4cf0a4787b77d4&stat=instructions Seems mostly fine, only outlier is kimwitu++ in NewPM-O3 configuration (k.cc has 1.25% regression).

Something I don't understand about the general approach here is why we start at the Def store and walk all uses to find a Use store to eliminate. Wouldn't it be more efficient to start at the Use store, and check the defining access? With the current approach, I think we'll only find the cases where Def is the defining access of Use, as everything else would be an indirect use. This approach should also be much easier to make more powerful (by using getClobberingMemoryAccess()) without running into compile-time issues from visiting indirect uses.

I don't remember if there was any particular reason to choose this approach to start with. I can't think of anything right now. Let me see if there are any cases that we would miss if we flip things.

Ah I think I remember now. I think I had an extension in mind that also looked at the uses that are loads to remove any redundant loads read the same location. Not sure how relevant this is in practice. I'll check.

Looking at llvm tracker + “remove noop loads” it looks fine, maybe lencod regressed in CT a bit more than expected (0,5% - ReleaseLTO)

[xbolva00]

Re-ping

[nikic]

I still think that this is not the right way to do it. Even if we want to perform store to load forwarding as well (which is not really the job of DSE, but even so) then it would still make more sense to iterate over all memory accesses (rather than over all defs) and look at the defining access for each.

[xbolva00]

Also solves PR49927?
https://bugs.llvm.org/show_bug.cgi?id=49927

[yurai007]

Hi, is there anybody actively working on this? It looks like "almost" done. @dmccrevan: are you going to move on with patch and address last @nikic comment? If not I'd like to give it a shot.

[xbolva00]

Precommited tests for PR50339 and PR49927, so please rebase.

[dmccrevan]

In D90328#3060699, @yurai007 wrote:

Hi, is there anybody actively working on this? It looks like "almost" done. @dmccrevan: are you going to move on with patch and address last @nikic comment? If not I'd like to give it a shot.

Please feel free to take this.

[yurai007]

Precommited tests for PR50339 and PR49927, so please rebase.

Sure.

Please feel free to take this.

Ok. Thanks.

[yurai007]

Opened new review since I couldn't figure out how to push it here (different authors): https://reviews.llvm.org/D111727

llvm/lib/Transforms/Scalar/DeadStoreElimination.cpp

if (NI->isAtomic()) {
       if (auto *CmpXchg = dyn_cast<AtomicCmpXchgInst>(NI))
         return isStrongerThanMonotonic(CmpXchg->getSuccessOrdering()) ||
                isStrongerThanMonotonic(CmpXchg->getFailureOrdering());
       llvm_unreachable("other instructions should be skipped in MemorySSA");
     }
     return false;
   }
 
+  /// Eliminates writes to locations where the value that is being written
+  /// is already stored at the same location.
+  bool eliminateRedundantStoresOfExisitingValues() {
+    bool MadeChange = false;
+    LLVM_DEBUG(dbgs() << "Trying to eliminate MemoryDefs that write the "
+                         "already exisiting value\n");
+    for (MemoryDef *Def : reverse(MemDefs)) {
+      if (SkipStores.find(Def) != SkipStores.end() ||
+          !isRemovable(Def->getMemoryInst()))
+        continue;
+
+      Instruction *DefI = Def->getMemoryInst();
+      Optional<MemoryLocation> MaybeDefLoc = getLocForWriteEx(DefI);
+      if (!MaybeDefLoc)
+        continue;
+
+      // Remove any uses of Def, that are MemoryDefs that write the same value
+      // to the same location as Def.
+      for (Use &U : make_early_inc_range(Def->uses())) {
+        MemoryAccess *UseAccess = cast<MemoryAccess>(U.getUser());
+        MemoryDef *UseDef = dyn_cast_or_null<MemoryDef>(UseAccess);
+        if (!UseDef)
+          continue;
+        Instruction *UseI = UseDef->getMemoryInst();
+
+        // Skip self-reads.
+        if (isReadClobber(*MaybeDefLoc, UseI))
+          continue;
+
+        if (UseI->isIdenticalTo(DefI)) {
+          deleteDeadInstruction(UseI);
+          NumRedundantStores++;
+          MadeChange = true;
+        }
+      }
+    }
+    return MadeChange;
+  }
+
   /// Eliminate writes to objects that are not visible in the caller and are not
   /// accessed before returning from the function.
   bool eliminateDeadWritesAtEndOfFunction() {
     bool MadeChange = false;
     LLVM_DEBUG(
         dbgs()
         << "Trying to eliminate MemoryDefs at the end of the function\n");
     for (int I = MemDefs.size() - 1; I >= 0; I--) {
if (!Shortend && isRemovable(SI) &&
       LLVM_DEBUG(dbgs() << "DSE: Remove No-Op Store:\n  DEAD: " << *SI << '\n');
       State.deleteDeadInstruction(SI);
       NumRedundantStores++;
       MadeChange = true;
       continue;
     }
   }
 
+  MadeChange |= State.eliminateRedundantStoresOfExisitingValues();
+
   if (EnablePartialOverwriteTracking)
     for (auto &KV : State.IOLs)
       MadeChange |= removePartiallyOverlappedStores(State.DL, KV.second, TLI);
 
   MadeChange |= State.eliminateDeadWritesAtEndOfFunction();
   return MadeChange;
 }
 } // end anonymous namespace

llvm/test/Transforms/DeadStoreElimination/MSSA/stores-of-existing-values.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -basic-aa -dse -S %s | FileCheck %s
 
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; Test case for PR16520. The store in %if.then is dead, because the same value
 ; has been stored earlier to the same location.
 define void @test1_pr16520(i1 %b, i8* nocapture %r) {
 ; CHECK-LABEL: @test1_pr16520(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i8 1, i8* [[R:%.*]], align 1
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
-; CHECK-NEXT:    store i8 1, i8* [[R]], align 1
 ; CHECK-NEXT:    tail call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    tail call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
 ; CHECK-NEXT:    ret void
 ;

 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @fn_readonly()
 ; CHECK-NEXT:    br label [[IF_END:%.*]]
 ; CHECK:       if.else:
 ; CHECK-NEXT:    tail call void @fn_readonly()
 ; CHECK-NEXT:    br label [[IF_END]]
 ; CHECK:       if.end:
-; CHECK-NEXT:    store i8 1, i8* [[R]], align 1
 ; CHECK-NEXT:    ret void
 ;
 entry:
   store i8 1, i8* %r, align 1
   br i1 %b, label %if.then, label %if.else
 
 if.then:                                          ; preds = %entry
   tail call void @fn_readonly()
   br label %if.end
 
 if.else:                                          ; preds = %entry
   tail call void @fn_readonly()
   br label %if.end
 
 if.end:                                           ; preds = %if.else, %if.then
   store i8 1, i8* %r, align 1
   ret void
 }
 
+; Make sure volatile stores are not removed.
+define void @test2_volatile(i1 %b, i8* nocapture %r) {
+; CHECK-LABEL: @test2_volatile(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    store volatile i8 1, i8* [[R:%.*]], align 1
+; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    tail call void @fn_readonly()
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    tail call void @fn_readonly()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    store volatile i8 1, i8* [[R]], align 1
+; CHECK-NEXT:    ret void
+;
+entry:
+  store volatile i8 1, i8* %r, align 1
+  br i1 %b, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  tail call void @fn_readonly()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  tail call void @fn_readonly()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  store volatile i8 1, i8* %r, align 1
+  ret void
+}
+
 define void @test3(i1 %b, i8* nocapture %r) {
 ; CHECK-LABEL: @test3(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    store i8 1, i8* [[R:%.*]], align 1
 ; CHECK-NEXT:    br i1 [[B:%.*]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
 ; CHECK:       if.then:
 ; CHECK-NEXT:    tail call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    br label [[IF_END:%.*]]

 ; CHECK-LABEL: @test6(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[FOR_HEADER:%.*]]
 ; CHECK:       for.header:
 ; CHECK-NEXT:    store i32 1, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    [[C1:%.*]] = call i1 @cond()
 ; CHECK-NEXT:    br i1 [[C1]], label [[FOR_BODY:%.*]], label [[END:%.*]]
 ; CHECK:       for.body:
-; CHECK-NEXT:    store i32 1, i32* [[P]], align 4
 ; CHECK-NEXT:    [[LV:%.*]] = load i32, i32* [[P]], align 4
 ; CHECK-NEXT:    br label [[FOR_HEADER]]
 ; CHECK:       end:
 ; CHECK-NEXT:    store i32 3, i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
 entry:
   br label %for.header

 ; CHECK-LABEL: @test7(
 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:
   ret void

 ; CHECK-NEXT:    store i32 0, i32* [[P:%.*]], align 4
 ; CHECK-NEXT:    br i1 true, label [[BB1:%.*]], label [[BB2:%.*]]
 ; CHECK:       bb1:
 ; CHECK-NEXT:    br label [[BB3:%.*]]
 ; CHECK:       bb2:
 ; CHECK-NEXT:    call void @fn_mayread_or_clobber()
 ; CHECK-NEXT:    ret void
 ; CHECK:       bb3:
-; CHECK-NEXT:    store i32 0, i32* [[P]], align 4
 ; CHECK-NEXT:    ret void
 ;
   store i32 0, i32* %P
   br i1 true, label %bb1, label %bb2
 bb1:
   br label %bb3
 bb2:
   call void @fn_mayread_or_clobber()
   ret void
 bb3:
   store i32 0, i32* %P
   ret void
 }