Needs rebase after bottom-up walk changes/

In D72700#1824724, @Tyker wrote:

In D72700#1822594, @asbirlea wrote:

Regarding handling the branching example, the solution fhahn proposes sounds reasonable to me.
I was thinking something similar, along the lines of: do the checks bottom-up from both second and third stores during the main algorithm, both find the dead store but do not postdominate it; don't abandon them, but keep this info (include the checks for no intervening reads) for after the main search. The data structure could be a Hashmap<PotentialDeadStore, ListOfDefsOrBlocksWhoFoundThisPotentialDeadStore>. If all paths are covered in the List for a PotentialDeadStore, then it's truly dead.

this seems like it should work.

Needs updating to work bottom-up.

Needs updating to work bottom-up.

Could you describe why the changes to run the tests via the pass managers is required? Wouldn't it be sufficient to use initialize the required analysis for the function and use that with getLoopEstimatedTripCount?

rebase, use += OpInfoTy operator.

Replace OpInfoTy::add with a += operator implementation.

ping

ping

ping

In D68814#1815837, @Ayal wrote:

Agree that it's better to merge the new conditional assume tests with the existing unconditional assume tests in the same file.

LGTM, thanks. Please wait a day or so with committing, in case there are additional comments.

In D69069#1812947, @ekatz wrote:

In D69069#1768576, @fhahn wrote:

Would it be possible to also add some of the test cases for the linked bugs?

This patch fixes a crash. Maybe just add a .ll file that shouldn't crash (with the fix)?!

Fix test failures, caused by checking fn attribute ids and now memset creates a new attribute combo.

In D72666#1820906, @jdoerfert wrote:

In D72666#1820862, @fhahn wrote:

In D72666#1818532, @jdoerfert wrote:

In D72666#1818407, @efriedma wrote:

I'd prefer to just add writeonly markings in places where they're missing. For llvm.memset in particular, can we mark it IntrWriteMem?

Yes we should probably just mark llvm.memset as IntrWriteMem.

Agreed.

In D72700#1821571, @Tyker wrote:

I did a few experiment with bottom-up algorithm before the patch i showed on phabricator. my implementation of the bottom-up had similar average complie-time to the current pass on the test-suite but it was only barely removing more stores than the current pass.
i gave up on it because i didn't found a good way forward to make it deal with cases like to the following:

   store i32 0, i32* %Ptr.  ; DEAD
   br i1 %cond, label %a, label %b
a:
  store i32 2, i32* %Ptr
   br label %c
b: 
  store i32 2, i32* %Ptr
  br label %c

which is IMO definitely something we want to do. by the way gcc does this optimization. https://godbolt.org/z/VFBf-c
maybe there is a bottom-up way to deal with this that i didn't thought about. any thought ?

In D72631#1820660, @asbirlea wrote:

Just a general comment here: DSE shouldn't necessarily make all optimizations possible. This one looks like it should be caught by DCE. If it's not, perhaps it would be good to improve DCE. Alternatively, if it's cheap enough, add a comment that it's still worth adding it to DSE.

In D72666#1818532, @jdoerfert wrote:

In D72666#1818407, @efriedma wrote:

I'd prefer to just add writeonly markings in places where they're missing. For llvm.memset in particular, can we mark it IntrWriteMem?

ping. Eli, do you think the updated approach makes more sense?

ping :)

I've revert rG192cce10f67e for now.

After thinking about it a bit more, I think this patch makes things too brittle with the legacy pass manager (e.g. we might end up with invalid DTs, if they are not used by GlobalOpt, but removeUnreachableBlocks makes changes. I'll revert D68298 for now.

In D72146#1818425, @asbirlea wrote:

Some comments inline.

Re-adding the inline comment: downwards walks are inefficient. This also currently misses optimization opportunities. In order to not miss anything, all Defs need to be looked at, not only uses, adding more overhead. So it's possible replacing MemDepAnalysis with MemorySSA may not get many benefits.
Maybe do some preliminary performance testing to check trade-offs between this recursive approach, the iterative approach in Tyker's patch, or consider a bottom-up approach?

In D72524#1815499, @merge_guards_bot wrote:

clang-tidy: fail. Please fix clang-tidy findings.

I think the latest version should be in quite good shape for review. I've linked the follow-on patches which together give a nice improvement in dead stores eliminated. I'll post a patch for partial overwrite tracking tomorrow and I am also working on exploring multiple memory defs.

rebase

Rebase

Updated to use AA::getModRefInfo and AA::callCapturesBefore similar to DependenceAnalysis. Remove unnecessary getLocForReadEx.

In D72524#1814826, @RKSimon wrote:

Not sure if its reusable but we already have signExtendBitcastSrcVector which we use for the (i16 bitcast (v16i1 x)) combine

Use SelectionDAG::MaxRecursionDepth, add example to comment.

The diff just includes the changes for the newly added tests (which I'll pre-commit before landing this)

Handle re-used expressions.

Handle re-used ops.

In D72214#1814399, @ekatz wrote:

The old PassManager has the function getAnalysisIfAvailable that should be used in case you only need to update an analysis (equivalent to getCachedResult of the new PassManager). You should probably switch to use this function, instead of the SmallPtrSet<> DTRequested technique.

In D72214#1810202, @nikic wrote:

Do you plan to pursue this patch? It would be great to resolve this one way or the other before LLVM 10 branches.

IIUC this is only needed after the flang merge, right? It will break things before the merge. The change is fine, after flang gets merged. IIUC this is not required as preparation for the merge, rather a follow up. Unless I am missing something, it would be good to clarify the title/commit message.

In D72392#1811735, @foad wrote:

The diff in llvm/test/CodeGen/X86/testb-je-fusion.ll is:

        movl    %edi, %eax
-       addl    $-512, %eax             # imm = 0xFE00
        movb    $1, (%rsi)
+       addl    $-512, %eax             # imm = 0xFE00
        je      .LBB2_2
...
        movl    %edi, %eax
-       decl    %eax
        movb    $1, (%rsi)
+       decl    %eax
        je      .LBB3_2

The scheduler prefers not to put the addl/decl immediately after the first movl because of the register dependency on eax with latency 1.

I think this breaks http://lab.llvm.org:8011/builders/clang-ppc64le-rhel/builds/425/steps/build%20stage%201/logs/stdio

There's a lot of small test changes (expected), but IMO I would be good to have an isolated test only tests the new behavior and shows an improvement (probably best as MIR machine-scheduler only test).

Remove unnecessary ResultNumElementsFlattened, add doc-comments.