[turbofan] Redundant branch elimination.

[turbofan] Redundant branch elimination.

Removes a branch that checks for a condition that has been checked on dominators of the branch.

This introduces a new reducer that propagates the list of checked conditions (and their boolean values) through the control flow graph. If it encounters a branch checking a condition with a known value, the branch is eliminated.

The analysis relies on loops being reducible: if a condition has been checked on all paths to loop entry, then it is checked in the loop (regardless what of the conditions checked inside the loop).

The implementation is fairly naive and could be improved:

- all the operation on the condition lists could be made allocation-free when revisited.

- we could try to use a map structure rather than a linked list (to make
lookups faster).

- the merging of control flow could be changed to take into account
  conditions from non-dominating paths (as long as all paths check
  the condition).

Committed: https://crrev.com/106aecf26200188647ea22c2d142067113d496b8
Cr-Commit-Position: refs/heads/master@{#31347}

[Jarin, 2015-10-08 15:00:00]

jarin@chromium.org changed reviewers:
+ bmeurer@chromium.org

[titzer, 2015-10-08 18:01:07]

titzer@chromium.org changed reviewers:
+ titzer@chromium.org

[titzer, 2015-10-08 18:01:08]

https://codereview.chromium.org/1376293005/diff/120001/src/compiler/branch-co...
File src/compiler/branch-condition-elimination.h (right):

https://codereview.chromium.org/1376293005/diff/120001/src/compiler/branch-co...
src/compiler/branch-condition-elimination.h:47: class ControlPathConditions {
The number of control path conditions is proportional to the dominator tree
height, so O(small). What about just using a simple unsorted list? That can be
immutable and therefore appended to by just cons'ing, allowing sharing
underneath. Merging can be a simple as finding the common prefix.

[Jarin, 2015-10-09 05:28:08]

https://codereview.chromium.org/1376293005/diff/120001/src/compiler/branch-co...
File src/compiler/branch-condition-elimination.h (right):

https://codereview.chromium.org/1376293005/diff/120001/src/compiler/branch-co...
src/compiler/branch-condition-elimination.h:47: class ControlPathConditions {
On 2015/10/08 18:01:07, titzer wrote:
> The number of control path conditions is proportional to the dominator tree
> height, so O(small). What about just using a simple unsorted list? That can be
> immutable and therefore appended to by just cons'ing, allowing sharing
> underneath. Merging can be a simple as finding the common prefix.

Yeah, that's a good idea. The code might be even simpler. I was a bit worried
about the quadratic merge, but if we just do common prefix, it will stay linear.
However, we will lose a bit of precision, if we have the same conditions on all
paths but not on a dominator. Example:

while (true) { if (x) break; ... if (y) { if (x) break; } }
if (x) {...} // Redundant if.

The if statement should be eliminated by the current version, but not if we just
do common prefix for merges. I agree that this is rare, so it should be fine.

[Jarin, 2015-10-17 14:18:21]

I have changed to unsorted lists and renamed to BranchElimination.

https://codereview.chromium.org/1376293005/diff/120001/src/compiler/branch-co...
File src/compiler/branch-condition-elimination.h (right):

https://codereview.chromium.org/1376293005/diff/120001/src/compiler/branch-co...
src/compiler/branch-condition-elimination.h:47: class ControlPathConditions {
On 2015/10/08 18:01:07, titzer wrote:
> The number of control path conditions is proportional to the dominator tree
> height, so O(small). What about just using a simple unsorted list? That can be
> immutable and therefore appended to by just cons'ing, allowing sharing
> underneath. Merging can be a simple as finding the common prefix.

Changed now, and it is indeed a bit faster (~10%) with unsorted lists.

[titzer, 2015-10-17 15:38:00]

On 2015/10/17 14:18:21, Jarin wrote:
> I have changed to unsorted lists and renamed to BranchElimination.
> 
>
https://codereview.chromium.org/1376293005/diff/120001/src/compiler/branch-co...
> File src/compiler/branch-condition-elimination.h (right):
> 
>
https://codereview.chromium.org/1376293005/diff/120001/src/compiler/branch-co...
> src/compiler/branch-condition-elimination.h:47: class ControlPathConditions {
> On 2015/10/08 18:01:07, titzer wrote:
> > The number of control path conditions is proportional to the dominator tree
> > height, so O(small). What about just using a simple unsorted list? That can
be
> > immutable and therefore appended to by just cons'ing, allowing sharing
> > underneath. Merging can be a simple as finding the common prefix.
> 
> Changed now, and it is indeed a bit faster (~10%) with unsorted lists.

lgtm nice!

[Jarin, 2015-10-17 17:49:02]

The CQ bit was checked by jarin@chromium.org

[commit-bot: I haz the power, 2015-10-17 17:49:05]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1376293005/180001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1376293005/180001

[commit-bot: I haz the power, 2015-10-17 17:50:17]

Committed patchset #10 (id:180001)

[commit-bot: I haz the power, 2015-10-17 17:50:40]

Patchset 10 (id:??) landed as
https://crrev.com/106aecf26200188647ea22c2d142067113d496b8
Cr-Commit-Position: refs/heads/master@{#31347}