Subzero: Add branch optimization.

Subzero: Add branch optimization.

1. Unconditional branch to the next basic block is removed.

2. For a conditional branch with a "false" edge to the next basic block, remove the unconditional branch to the fallthrough block.

3. For a conditional branch with a "true" edge to the next basic block, invert the condition and do like #2.

This is enabled only for O2, particularly because inverting the branch condition is a marginally risky operation.

This decreases the instruction count by about 5-6%.

Also, --stats prints a final tally to make it easier to post-process the output.

BUG= none
R=jvoung@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=ff9c7063c674aaf2c96a75155c64f4331e30cecc

[Jim Stichnoth, 2014-09-17 23:14:38]

stichnot@chromium.org changed reviewers:
+ jvoung@chromium.org

[jvoung (off chromium), 2014-09-18 03:56:02]

otherwise LGTM

https://codereview.chromium.org/580903005/diff/20001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/580903005/diff/20001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:464: Target->doBranchOpt(*I, NextNode);
I wonder if it makes sense to search backward and bail once the terminating
branch is found. I guess this is complicated by switch statements which can have
> 1 branch.

https://codereview.chromium.org/580903005/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/580903005/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:403: // Branch optimization.  This needs to be
done just before code
Should this be before nop insertion? I don't think that will reorder or insert
CfgNodes, but if before then you will at least not need to iterate over the nops
to find the branches.

[Jim Stichnoth, 2014-09-18 11:45:51]

https://codereview.chromium.org/580903005/diff/20001/src/IceCfgNode.cpp
File src/IceCfgNode.cpp (right):

https://codereview.chromium.org/580903005/diff/20001/src/IceCfgNode.cpp#newco...
src/IceCfgNode.cpp:464: Target->doBranchOpt(*I, NextNode);
On 2014/09/18 03:56:02, jvoung wrote:
> I wonder if it makes sense to search backward and bail once the terminating
> branch is found. I guess this is complicated by switch statements which can
have
> > 1 branch.

I thought about this a bit, but I think that would make too strong an assumption
in the target-neutral CfgNode class about the properties of the target-specific
lowering, namely that there is only one branch optimization opportunity per
block (though it happens to be true in the current x86 lowering).  I added a
comment about this potential opportunity though.  Also, I changed the
instruction-level doBranchOpt() methods to return bool based on whether an
optimization was actually done.

BTW, the current switch lowering still only leaves one opportunity for
optimization, namely the last branch for the default case.  The other cases
lower to conditional branches with no fallthrough target, which aren't
optimized.

https://codereview.chromium.org/580903005/diff/20001/src/IceTargetLoweringX86...
File src/IceTargetLoweringX8632.cpp (right):

https://codereview.chromium.org/580903005/diff/20001/src/IceTargetLoweringX86...
src/IceTargetLoweringX8632.cpp:403: // Branch optimization.  This needs to be
done just before code
On 2014/09/18 03:56:02, jvoung wrote:
> Should this be before nop insertion? I don't think that will reorder or insert
> CfgNodes, but if before then you will at least not need to iterate over the
nops
> to find the branches.

Good point, done.

[Jim Stichnoth, 2014-09-18 11:50:54]

Committed patchset #3 (id:40001) manually as ff9c706 (tree was closed).