Add phis in SimplifyIfs to enable branch redirection

For example it turns:
if(cond)
  /  \
 B1  B2
  \ /
if(cond)
  /  \
 B3  B4

into:
if(cond)
  /  \
 B1  B2
  \ /
if(Phi(1, 0))
  /  \
 B3  B4

Following this, SimplifyIfs is able to connect B1->B3
and B2->B4 effectively skipping an if.

Locally, speed compiling on a Pixel 5:
 * system server: -4.0KB (-0.01%)
 * SystemUIGoogle: -8.0KB (-0.03%)
 * AGSA: -17.75KB (-0.01%)

Test: art/test/testrunner/testrunner.py --host --64 --optimizing -b
Change-Id: I3b2e6a986b4d5e162bec28d72e9b0e2a3de1a4c3

1 files changed, 47 insertions, 0 deletions

diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h
index b91006be0d..ddd01f7103 100644
--- a/compiler/optimizing/dead_code_elimination.h
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -46,6 +46,31 @@ class HDeadCodeElimination : public HOptimization {
   bool RemoveDeadBlocks(bool force_recomputation = false, bool force_loop_recomputation = false);
   void RemoveDeadInstructions();
   bool SimplifyAlwaysThrows();
+  // Simplify the pattern:
+  //
+  //        B1    B2    ...
+  //       goto  goto  goto
+  //         \    |    /
+  //          \   |   /
+  //             B3
+  //     i1 = phi(input, input)
+  //     (i2 = condition on i1)
+  //        if i1 (or i2)
+  //          /     \
+  //         /       \
+  //        B4       B5
+  //
+  // Into:
+  //
+  //       B1      B2    ...
+  //        |      |      |
+  //       B4      B5    B?
+  //
+  // Note that individual edges can be redirected (for example B2->B3
+  // can be redirected as B2->B5) without applying this optimization
+  // to other incoming edges.
+  //
+  // Note that we rely on the dead code elimination to get rid of B3.
   bool SimplifyIfs();
   void ConnectSuccessiveBlocks();
   // Updates the graph flags related to instructions (e.g. HasSIMD()) since we may have eliminated
@@ -75,6 +100,28 @@ class HDeadCodeElimination : public HOptimization {
   // instructions.
   bool RemoveUnneededTries();
 
+  // Adds a phi in `block`, if `block` and its dominator have the same (or opposite) condition.
+  // For example it turns:
+  // if(cond)
+  //   /  \
+  //  B1  B2
+  //   \ /
+  // if(cond)
+  //   /  \
+  //  B3  B4
+  //
+  // into:
+  // if(cond)
+  //   /  \
+  //  B1  B2
+  //   \ /
+  // if(Phi(1, 0))
+  //   /  \
+  //  B3  B4
+  //
+  // Following this, SimplifyIfs is able to connect B1->B3 and B2->B4 effectively skipping an if.
+  void MaybeAddPhi(HBasicBlock* block);
+
   DISALLOW_COPY_AND_ASSIGN(HDeadCodeElimination);
 };