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.

Ping

Addressed Eli's comments.

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.

Ping

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.

Sink to immediate successors, update memory SSA when sinking.

Ping

Minimized the diff by putting #ifdefs inside the function.

Ping

Ping

Updated comments.

Mark those basic blocks which does not guarantee progress as barriers and use them subsequently while checking for availability during hoisting.

In D30667#702834, @sanjoy wrote:

In D30667#700016, @hfinkel wrote:

There is? We could propagate the unreachableness of this function to its callsites, but I don't see what that has to do with the value of the function argument.

In D30667#701680, @dberlin wrote:

Okay, so to close this out, what would we like to do about isGuaranteedToTransferExecutionToSuccessor?
Continue have it return false?

Past that, it's clear additional bugs should be filed against gvnhoist.

My inclination would be to have it explicitly (with a nice comment) return true. That would make bugs like the GVNHoist one we're talking about here more obviously buggy.

Ping

In D30667#701680, @dberlin wrote:

Okay, so to close this out, what would we like to do about isGuaranteedToTransferExecutionToSuccessor?
Continue have it return false?

Past that, it's clear additional bugs should be filed against gvnhoist.

Removed unreachable from testcases.
Replaced fp* with i64*

pimg

ping

In D30667#694724, @dberlin wrote:

Sure, and if you want to fix that bug, i think it's worth doing. But i think that's not related to fixing any gvnhoist problem :P