In D72885#1834094, @jdoerfert wrote:

In D72885#1832612, @Tyker wrote:

In D72885#1827778, @jdoerfert wrote:

I won't review this properly till next week. Generally looks good so you can work on the next patch if you want to.

i started working on ignoring or dropping uses in llvm.assume when a transformation is use sensitive.

Great! Can you share it on phab so I can reference it in my email (see below).

In D72885#1827778, @jdoerfert wrote:

I won't review this properly till next week. Generally looks good so you can work on the next patch if you want to.

fixed.

addressed comments.

minor improvements.

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.

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 ?

i renamed the files to KnowledgeRetention.* to be more general. we can put other related utilities like the query API in the same files. i had a hard time finding a good name and i am not sure i succeeded what do you think ?

In D72475#1817423, @jdoerfert wrote:

`bool getAttributeFromAssume(Value &Base, CallInst &AssumeCI, Attribute::Kind Kind, int &Value)`

and similar for string attributes. Alternatively we could return a map from WhatOn values to attributes.

something like that seem fine.

@rsmith friendly reminder

fixed comments.

fixed comments.

i changed the pass and the test to actually perform the transformation. it is less confusing this way.

rebased

Yes, PostDominators is the second thing we need to get better at preserving. IIRC all places where we already use DomTreeUpdater we basically preserve PDT as well without any additional work, besides passing in the PDT to the updater. There's getAnalysisIfAvailable (legacy pass manager)/getCachedResult (new PM) to get an analysis, only if it is already computed. The only caveat is that the legacy pass manager cannot preserve function analysis if it is followed by a function pass (IIUC).

In D72146#1804134, @fhahn wrote:

In D72146#1804102, @Tyker wrote:

In D72146#1803859, @fhahn wrote:

Do you think it would make sense to use D72146 (this patch) as foundation and port the improvements from your patch? It would be great if you could have a look and let me know what you think!

I took a look at this patch and D72148(the patch adding MemPhi traversal). they have many good ideas i haven't thought about.
but i have one major concern.
how to you plan to dealing with store being killed by multiple stores which together post-dominate the "dead" store ?
like the store in the entry block of the following:

define void @test5A(i32* %P) {
  store i32 1, i32* %P ; this is dead
  br i1 true, label %bb1, label %bb2
bb1:
  store i32 0, i32* %P
  br label %bb3
bb2:
  store i32 1, i32* %P
  br label %bb3
bb3:
  ret void
}

the design around getNextMemoryDef seems to me like it is too restrictive for the above example.

Yes as it is it does not cover that case. But I think it would be relatively straight forward to extend it to return a list of MemoryDefs encountered along multiple paths. Those can then be checked for legality separately. If some of the found Defs do not eliminate the original store, we can continue walking just those Defs. To support that, it probably also makes sense to re-write getNextMemoryDef to work iteratively, like in your patch.

Ok seems reasonable, so we will change the core loop for each store will have to change in a following patch.

IMO the most productive way forward would be to get in a patch with limited but solid support as a baseline and once that is in we can work on adding missing functionality in parallel. What do you think about this approach?

you are right. i probably went a bit to far for a first patch.

Besides extending the functionality, I think we will also have to spend a fair amount of work on making sure that preceding and succeeding passes in the pipeline preserve MemorySSA, to avoid computing it from scratch just for DSE.

yeah. and we may have to do the same thing for the post dominator tree.
is there a way to have a pass preserve an analysis if it is still valid without depending on it but not updating it if it is not valid ?

improved the test suite.

In D70638#1804138, @aaron.ballman wrote:

In D70638#1803364, @xbolva00 wrote:

(re-ping; I think this false positive for goto label case is important to be fixed before 10 release)

I agree -- @Tyker, are you planning to work on that fix?

ping @rsmith

In D72146#1803859, @fhahn wrote:

Do you think it would make sense to use D72146 (this patch) as foundation and port the improvements from your patch? It would be great if you could have a look and let me know what you think!

In D71037#1803704, @mstorsjo wrote:

In D71037#1803574, @Tyker wrote:

In D71037#1803361, @xbolva00 wrote:

Can you add a test case for that crash? Otherwise OK.

as i said. the bug can only occur for one line files. so we can't have a run line and a the crashing line. so i wasn't able to make a test for it.

Is it possible to have the RUN bit at the end of the line in a comment, after the test code itself?

i haven't looked in details at your patch but i was working on something similar D72182.

In D71037#1803361, @xbolva00 wrote:

Can you add a test case for that crash? Otherwise OK.

This update should fixes the issue.
the assert was incorrect. because file offsets are 0-based where as column numbers are 1-based.

fixed comments.

i agree that it is the best solution.

my intent was not necessarily to create a generic solution but to get a solution that is sufficient to not have false positives on the Wmisleading-indentation warning for code base that have mixes of tabs and spaces.

ping @rsmith

now that the issue with uniqueness of expressions is solved. we should be able to keep going on that review @rsmith.
https://reviews.llvm.org/D63960 should be i think close to completion. so maybe for testing i could use immediate invocation as a source for ConstantExpr instead of the code i added to make constexpr variables emit ConstantExpr ?

comments were fixed.

i have not tested the performance impact. but i tried to do the heavier checks last to minimize the impact.
i added your tests file to the improvement commit.

fixed aaron's comment

i ran a build of the linux kernel using the stage1 compiler, about 30% of files crashed the compiler in the optimizer. everything was building fine 2 weeks ago with the same configuration but a previous compiler.
but aside from that from that file that complied fine, there was only one warning left. this warning is exactly the same case we had in llvm's source code.

the warning was not affected by -ftabstop. i made a patch that fix this.

i did a few test on the linux kernel on prior version of this patchs and the mix of spaces and tabs caused some false positives. but i do believe there is still a bug here.
for the mix of space and tabs. gcc has a -ftabstop=X to specify how large tabs should be counted as.
clang has it as well i am going to check that it is taken in account.

improved based on aaron's comment.