- User Since
- Mar 5 2014, 4:23 PM (193 w, 4 d)
Fri, Nov 10
Thu, Nov 9
Added a testcase for irreducible control flow.
Tue, Nov 7
Fri, Oct 27
Sep 12 2017
Sep 8 2017
added auto to relevant places.
Sep 7 2017
Sep 6 2017
use any_of instead of iterating over the successors.
Aug 23 2017
Addressed @dberlin 's comments.
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.
Aug 21 2017
Updated MemorySSA updates.
Outlined functions from codegen part.
Aug 20 2017
Results with the patch.
Aug 17 2017
Aug 15 2017
Aug 11 2017
Remove dead comments.
Aug 10 2017
Based on suggestions from @dberlin, I have updated the patch:
- Compute iterated post-dominance frontiers
- Iterate on post-dominator tree to insert CHIargs more efficiently
Aug 7 2017
@hfinkel , I'd appreciate your feedback, and suggestions for improvement.
Aug 3 2017
Aug 2 2017
For some reason phabricator missed the following comments:
Aug 1 2017
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)
Jul 27 2017
Jul 26 2017
Jul 6 2017
Jun 30 2017
Jun 28 2017
Jun 14 2017
Addressed comments from Eric.
Jun 12 2017
@mzolotukhin Please let me know if you have any further comments.
Jun 9 2017
Jun 7 2017
May 26 2017
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.
May 23 2017
May 18 2017
May 11 2017
Adding ':' for basic block labels in the testcase
May 10 2017
Addressed @chandlerc 's comments: Essentially, I've added test cases for cycles due to direct branches, indirect branches and invoke instructions.
May 8 2017
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.
The code checks for cycle, not loops so it can detect all kinds of explicit cycles as different from other three you mentioned.
May 5 2017
May 1 2017
Addressed Eli's comments.
Apr 29 2017
Apr 27 2017
Apr 26 2017
Sink to immediate successors, update memory SSA when sinking.
Apr 24 2017
Apr 21 2017
Minimized the diff by putting #ifdefs inside the function.
Apr 17 2017
Apr 3 2017
Mar 20 2017
Mar 17 2017
Mark those basic blocks which does not guarantee progress as barriers and use them subsequently while checking for availability during hoisting.
Mar 16 2017