Merged with https://reviews.llvm.org/D30268

Not required.

ping

return {}.

Comments

My testcase got fixed just with https://reviews.llvm.org/D45926. I'm wondering if this patch is still a good idea.

Comments for enum

This is not in trunk I guess, I borrowed this pass from: https://reviews.llvm.org/D22051

It appears this warning may not be always useful because there will be false positives.

Addressed comments

The bug which motivated this warning is: https://github.com/jemalloc/jemalloc/commit/4df483f0fd76a64e116b1c4f316f8b941078114d#diff-7b26b977303fe92c093a2245b0eaf255

Warn on bool* to bool conversion during a call only.

I'll probably make this warning for function arguments only (when bool* is passed to a function accepting bool). Many conditionals use bool* -> bool conversion as pointed out by @Quuxplusone and @aaron.ballman

If you want to update using DJ-Graphs and merge sets, I have implemented them in the global-scheduler which I thought could be reused: https://reviews.llvm.org/D32140
Please let me know if you find this useful.

In D41453#961313, @efriedma wrote:

There are a bunch of places in GVNHoist which call dominates (as opposed to properlyDominates), and some of them seem dubious. Are you going to audit them?

Added a testcase for irreducible control flow.

use depth_first

added auto to relevant places.

Ping!

use any_of instead of iterating over the successors.

Closed by commit: rL311283

Addressed @dberlin 's comments.

In D36113#849679, @hfinkel wrote:

Two high-level thoughts:

1. Is this transformation always profitable even if we don't later vectorize? I worry that you're taking a stream of accesses that generally appear in order and making them appear out of order. That could have odd effects. Maybe this should all be a utility that the vectorizer uses more directly?

Agreed, we will evaluate if we can this pass as a utility for vectorizer. In the past we tried that but got stuck because we were unable to recompute loop-access-info once the instructions have been reordered. Maybe you can help us here.

In D36113#849679, @hfinkel wrote:

Two high-level thoughts:

1. Is this transformation always profitable even if we don't later vectorize? I worry that you're taking a stream of accesses that generally appear in order and making them appear out of order. That could have odd effects. Maybe this should all be a utility that the vectorizer uses more directly?
2. I don't think a goal of this should be to provide backup handling of things that LICM misses but MemorySSA can prove are loop invariant. We should improve LICM by making it use MemorySSA (see work on this in D35741 - pushing this along might help?). We could run LICM right before we vectorize too.

Updated MemorySSA updates.
Outlined functions from codegen part.

Results with the patch.

Remove dead comments.

Added Comments

Based on suggestions from @dberlin, I have updated the patch:

1. Compute iterated post-dominance frontiers
2. Iterate on post-dominator tree to insert CHIargs more efficiently

@hfinkel , I'd appreciate your feedback, and suggestions for improvement.
Thanks,

In D35918#831091, @kuhar wrote:

In D35918#831066, @hiraditya wrote:

I tried a simple df walk like this, it crashes the compiler for the test cases llvm/test/Transforms/GVNHoist/infinite-loop-indirect.ll, and llvm/test/Transforms/GVNHoist/infinite-loop-direct.ll:

auto PrevBB = PDT->getNode(nullptr);
 for (auto it = df_begin(PrevBB); it != df_end(PrevBB);
      ++it) {
 }

These test cases are added in this patch.

Thanks,

I tried running loop like yours in a couple of my unittests (DominatorTreeTest.cpp) and it seems to work:

auto PrevBB = PDT->getNode(nullptr);
for (auto it = df_begin(PrevBB); it != df_end(PrevBB);
     ++it) {
  auto BB = it->getBlock();
  outs() << (BB ? BB->getName() : "virtual root") << "\n";
}

Could you prepare a reduced repro for the crash you saw?

Thanks,
Kuba

In D35918#830987, @kuhar wrote:

In D35918#830975, @hiraditya wrote:

In D35918#829175, @kuhar wrote:

@dberlin, @hiraditya

In D35918#822192, @dberlin wrote:

The graph always has one root, virtual or not.
Once kuba's latest patch is committed, it will *always* be virtual, actually.

That's actually already the case upstream since r309146 (D35597).
https://github.com/llvm-mirror/llvm/blob/22072158f353cc89a7821b13a7c3e99daa5be464/include/llvm/Support/GenericDomTreeConstruction.h#L263
https://github.com/llvm-mirror/llvm/blob/22072158f353cc89a7821b13a7c3e99daa5be464/include/llvm/Support/GenericDomTreeConstruction.h#L307

Can you illustrate how to perform a DFS walk on a post-dom tree with your patch. Also, how would I get the (virtual) root node of post-dom tree.

Thanks,

You can get the virtual root by calling PDT.getNode(nullptr). Then you can use something like llvm/ADT/DepthFirstIterator.h or llvm/ADT/PostOrderIterator.h to run DFS on it. Implementing a custom DFS should also be easy.

In D35918#829175, @kuhar wrote:

@dberlin, @hiraditya

In D35918#822192, @dberlin wrote:

The graph always has one root, virtual or not.
Once kuba's latest patch is committed, it will *always* be virtual, actually.

That's actually already the case upstream since r309146 (D35597).
https://github.com/llvm-mirror/llvm/blob/22072158f353cc89a7821b13a7c3e99daa5be464/include/llvm/Support/GenericDomTreeConstruction.h#L263
https://github.com/llvm-mirror/llvm/blob/22072158f353cc89a7821b13a7c3e99daa5be464/include/llvm/Support/GenericDomTreeConstruction.h#L307

For some reason phabricator missed the following comments:

Such a mapping is by definition n^2 space, and i'm having trouble seeing why it is necessary.

Here is what you are doing:
For each instruction with the same VN:

find the post-dominance frontier of the block of the instruction
Insert a chi there, with certain arguments.

This is unnecessarily wasteful (you may compute the same pdf again and again).

Here is what SSUPRE (and you), should do:

Collect all the blocks of the instructions with the same VN into defining blocks.
Compute the PDF using IDFCalculator.
Place empty chis in the PDF.

At this point, you have two options:

Walk post-dominator tree top-down and use a stack to store the last value you see.
When you hit a chi from a given edge, the value to use as the argument is at the top of the stack.

This is O(Basic Blocks)

In D35918#822192, @dberlin wrote:

In D35918#822168, @hiraditya wrote:

In D35918#822143, @dberlin wrote:

FYI: IDFCalculator can compute the PostDominanceFrontier in linear time.

I was unable to find how to pass the root node of inverse graph, because there might be more than one root.
Thanks,

No.
The graph always has one root, virtual or not.
Once kuba's latest patch is committed, it will *always* be virtual, actually.

But i'm not sure why that would stop you one way or the other?
The IDF calculator only asks for the defining blocks, not the root.
You can hand it all CFG blocks and it should work fine.

In D35918#822143, @dberlin wrote:

FYI: IDFCalculator can compute the PostDominanceFrontier in linear time.

Addressed comments from Eric.

@mzolotukhin Please let me know if you have any further comments.

Ping

@dberlin
When SSAPRE inserts PHI (expression PHIs), it does so at places where (potentially) multiple expressions may merge. If a PHI has a bottom (⊥) entry, that means the expression is partially available.
The concept may work for GVN-Hoist to help factor out anticipability by working on inverted graph. If we insert an outgoing PHI (if I may), to a basic block with multiple successors, as instructions are hoisted upwards to a nearest common dominator.
And we start walking the CFG to figure out if any outgoing PHI has a ⊥, that means the expression is not anticipable in the basic block having that outgoing PHI.
To minimize the number of outgoing PHIs, we will only insert them for expressions with multiple occurrences.
This will help remove the need to check for reachability.

In D24805#764415, @jmolloy wrote:

Thanks Danny,

I've committed the patch after changing from std::stable_sort to std::sort (I didn't need it, I was being paranoid debugging a heisenbug). This was good timing as today is my last day at ARM and in a couple of hours I will lose access to my development machine! :)

Thanks for your last reply; I now, finally, have got it! I spent yesterday prototyping and have something that conceptually works. It'll need a lot more work though. Watch this space ;)

Cheers,

James

Ping

Ping

Adding ':' for basic block labels in the testcase

Addressed @chandlerc 's comments: Essentially, I've added test cases for cycles due to direct branches, indirect branches and invoke instructions.

In D32614#749269, @chandlerc wrote:

You are continuing to argue that you do not need to add tests because they will pass. That seems to be missing the point. Tests are what verify and validate these kinds of arguments and assumptions, both now and in the future.

I'll add more tests which will reflect different aspects of cyclic control flow. I was trying to explain what program points handle specific cases pointed by you. It will be good if you can suggest any resources which can help create a variety of CFGs.

In D32614#749208, @chandlerc wrote:

I don't see what would have addressed my concerns.

There still is only a single test case for an infinite loop. There are *several different* CFGs that fail to terminate. You should be testing them.

Examples off the top of my head:

• A non-loop cycle in the CFG.

The code checks for cycle, not loops so it can detect all kinds of explicit cycles as different from other three you mentioned.

Addressed comments from @chandlerc and @dberlin

In D32614#740129, @dberlin wrote:

In D32614#740119, @hiraditya wrote:

In D32614#739947, @dberlin wrote:

I'm at a loss to understand why you believe you need to compute joint post-dominance (which is what this is) to compute ANTIC.

If the set of BasicBlocks (WL) do not joint-post-dominate the hoisting point (HoistBB), then the expression to be hoisted (from WL) cannot be ANTIC in HoistBB.

Sure.
That is definitely a way of computing it.
It is a generally slow and unused way of computing it, because there are only certain points in the SSA graph where ANTIC can actually change.

It is a necessary condition what I'm checking here.

It is not necessary to perform graph reachability to do this.

https://pdfs.semanticscholar.org/6d0f/07ff330402b46e83d46142e202069d9aeceb.pdf

Stare at the down-safety step.
With a few bits, it is only actually necessary to compute and check antic at the possible phis you would insert to do your hoisting.