Remove empty ifs

If we had an HIf where both branches were empty, we wouldn't emit
any code generation for the HIf. However, this still emits other
instructions e.g. outer ifs, instructions used in the if guard.

This CL detects when an HIf is empty and can be eliminated during
DCE.

Bug: 305225992
Fixes: 305225992
Test: art/test/testrunner/testrunner.py --host --64 -b --optimizing
Change-Id: I81ff5ee1326b6a27480b1af88d41955f1ca2b823

6 files changed, 252 insertions, 0 deletions

diff --git a/compiler/optimizing/dead_code_elimination.cc b/compiler/optimizing/dead_code_elimination.cc
index 5a7b83603f..922ca209cc 100644
--- a/compiler/optimizing/dead_code_elimination.cc
+++ b/compiler/optimizing/dead_code_elimination.cc
@@ -770,6 +770,93 @@ bool HDeadCodeElimination::RemoveUnneededTries() {
   }
 }
 
+bool HDeadCodeElimination::RemoveEmptyIfs() {
+  bool did_opt = false;
+  for (HBasicBlock* block : graph_->GetPostOrder()) {
+    if (!block->EndsWithIf()) {
+      continue;
+    }
+
+    HIf* if_instr = block->GetLastInstruction()->AsIf();
+    HBasicBlock* true_block = if_instr->IfTrueSuccessor();
+    HBasicBlock* false_block = if_instr->IfFalseSuccessor();
+
+    // We can use `visited_blocks` to detect cases like
+    //    1
+    //   / \
+    //  2  3
+    //  \ /
+    //   4  ...
+    //   | /
+    //   5
+    // where 2, 3, and 4 are single HGoto blocks, and block 5 has Phis.
+    ScopedArenaAllocator allocator(graph_->GetArenaStack());
+    ScopedArenaHashSet<HBasicBlock*> visited_blocks(allocator.Adapter(kArenaAllocDCE));
+    HBasicBlock* merge_true = true_block;
+    visited_blocks.insert(merge_true);
+    while (merge_true->IsSingleGoto()) {
+      merge_true = merge_true->GetSuccessors()[0];
+      visited_blocks.insert(merge_true);
+    }
+
+    HBasicBlock* merge_false = false_block;
+    while (visited_blocks.find(merge_false) == visited_blocks.end() &&
+           merge_false->IsSingleGoto()) {
+      merge_false = merge_false->GetSuccessors()[0];
+    }
+
+    if (visited_blocks.find(merge_false) == visited_blocks.end() ||
+        !merge_false->GetPhis().IsEmpty()) {
+      // TODO(solanes): We could allow Phis iff both branches have the same value for all Phis. This
+      // may not be covered by SsaRedundantPhiElimination in cases like `HPhi[A,A,B]` where the Phi
+      // itself is not redundant for the general case but it is for a pair of branches.
+      continue;
+    }
+
+    // Data structures to help remove now-dead instructions.
+    ScopedArenaQueue<HInstruction*> maybe_remove(allocator.Adapter(kArenaAllocDCE));
+    ScopedArenaHashSet<HInstruction*> visited(allocator.Adapter(kArenaAllocDCE));
+    maybe_remove.push(if_instr->InputAt(0));
+
+    // Swap HIf with HGoto
+    block->ReplaceAndRemoveInstructionWith(
+        if_instr, new (graph_->GetAllocator()) HGoto(if_instr->GetDexPc()));
+
+    // Reconnect blocks
+    block->RemoveSuccessor(true_block);
+    block->RemoveSuccessor(false_block);
+    true_block->RemovePredecessor(block);
+    false_block->RemovePredecessor(block);
+    block->AddSuccessor(merge_false);
+
+    // Remove now dead instructions e.g. comparisons that are only used as input to the if
+    // instruction. This can allow for further removal of other empty ifs.
+    while (!maybe_remove.empty()) {
+      HInstruction* instr = maybe_remove.front();
+      maybe_remove.pop();
+      if (visited.find(instr) != visited.end()) {
+        continue;
+      }
+      visited.insert(instr);
+      if (instr->IsDeadAndRemovable()) {
+        for (HInstruction* input : instr->GetInputs()) {
+          maybe_remove.push(input);
+        }
+        instr->GetBlock()->RemoveInstructionOrPhi(instr);
+        MaybeRecordStat(stats_, MethodCompilationStat::kRemovedDeadInstruction);
+      }
+    }
+  }
+
+  if (did_opt) {
+    graph_->ClearLoopInformation();
+    graph_->ClearDominanceInformation();
+    graph_->BuildDominatorTree();
+  }
+
+  return did_opt;
+}
+
 bool HDeadCodeElimination::RemoveDeadBlocks(bool force_recomputation,
                                             bool force_loop_recomputation) {
   DCHECK_IMPLIES(force_loop_recomputation, force_recomputation);
@@ -879,6 +966,7 @@ bool HDeadCodeElimination::Run() {
     bool did_any_simplification = false;
     did_any_simplification |= SimplifyAlwaysThrows();
     did_any_simplification |= SimplifyIfs();
+    did_any_simplification |= RemoveEmptyIfs();
     did_any_simplification |= RemoveDeadBlocks();
     // We call RemoveDeadBlocks before RemoveUnneededTries to remove the dead blocks from the
     // previous optimizations. Otherwise, we might detect that a try has throwing instructions but
diff --git a/compiler/optimizing/dead_code_elimination.h b/compiler/optimizing/dead_code_elimination.h
index ddd01f7103..789962f93c 100644
--- a/compiler/optimizing/dead_code_elimination.h
+++ b/compiler/optimizing/dead_code_elimination.h
@@ -40,6 +40,17 @@ class HDeadCodeElimination : public HOptimization {
  private:
   void MaybeRecordDeadBlock(HBasicBlock* block);
   void MaybeRecordSimplifyIf();
+  // Detects and remove ifs that are empty e.g. it turns
+  //     1
+  //    / \
+  //   2   3
+  //   \  /
+  //    4
+  // where 2 and 3 are single goto blocks and 4 doesn't contain a Phi into:
+  //    1
+  //    |
+  //    4
+  bool RemoveEmptyIfs();
   // If `force_recomputation` is true, we will recompute the dominance information even when we
   // didn't delete any blocks. `force_loop_recomputation` is similar but it also forces the loop
   // information recomputation.
diff --git a/test/2266-checker-remove-empty-ifs/expected-stderr.txt b/test/2266-checker-remove-empty-ifs/expected-stderr.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/2266-checker-remove-empty-ifs/expected-stderr.txt
diff --git a/test/2266-checker-remove-empty-ifs/expected-stdout.txt b/test/2266-checker-remove-empty-ifs/expected-stdout.txt
new file mode 100644
index 0000000000..e69de29bb2
--- /dev/null
+++ b/test/2266-checker-remove-empty-ifs/expected-stdout.txt
diff --git a/test/2266-checker-remove-empty-ifs/info.txt b/test/2266-checker-remove-empty-ifs/info.txt
new file mode 100644
index 0000000000..2ada78fc0e
--- /dev/null
+++ b/test/2266-checker-remove-empty-ifs/info.txt
@@ -0,0 +1 @@
+Tests that DCE deletes HIfs with empty blocks.
diff --git a/test/2266-checker-remove-empty-ifs/src/Main.java b/test/2266-checker-remove-empty-ifs/src/Main.java
new file mode 100644
index 0000000000..975b6b1775
--- /dev/null
+++ b/test/2266-checker-remove-empty-ifs/src/Main.java
@@ -0,0 +1,152 @@
+/*
+ * Copyright (C) 2023 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+public class Main {
+    public static void main(String[] args) {}
+    public static void $inline$empty() {}
+    public static void $inline$empty2() {}
+
+    /// CHECK-START: void Main.andBoolean2(boolean, boolean) dead_code_elimination$after_inlining (before)
+    /// CHECK: If
+    /// CHECK: If
+
+    /// CHECK-START: void Main.andBoolean2(boolean, boolean) dead_code_elimination$after_inlining (after)
+    /// CHECK-NOT: If
+    public static void andBoolean2(boolean a, boolean b) {
+        if (a && b) {
+            $inline$empty();
+        } else {
+            $inline$empty2();
+        }
+    }
+
+    /// CHECK-START: void Main.andBoolean3(boolean, boolean, boolean) dead_code_elimination$after_inlining (before)
+    /// CHECK: If
+    /// CHECK: If
+    /// CHECK: If
+
+    /// CHECK-START: void Main.andBoolean3(boolean, boolean, boolean) dead_code_elimination$after_inlining (after)
+    /// CHECK-NOT: If
+    public static void andBoolean3(boolean a, boolean b, boolean c) {
+        if (a && b && c) {
+            $inline$empty();
+        } else {
+            $inline$empty2();
+        }
+    }
+
+    /// CHECK-START: void Main.andBoolean4(boolean, boolean, boolean, boolean) dead_code_elimination$after_inlining (before)
+    /// CHECK: If
+    /// CHECK: If
+    /// CHECK: If
+    /// CHECK: If
+
+    /// CHECK-START: void Main.andBoolean4(boolean, boolean, boolean, boolean) dead_code_elimination$after_inlining (after)
+    /// CHECK-NOT: If
+    public static void andBoolean4(boolean a, boolean b, boolean c, boolean d) {
+        if (a && b && c && d) {
+            $inline$empty();
+        } else {
+            $inline$empty2();
+        }
+    }
+
+    /// CHECK-START: void Main.orBoolean2(boolean, boolean) dead_code_elimination$after_inlining (before)
+    /// CHECK: If
+    /// CHECK: If
+
+    /// CHECK-START: void Main.orBoolean2(boolean, boolean) dead_code_elimination$after_inlining (after)
+    /// CHECK-NOT: If
+    public static void orBoolean2(boolean a, boolean b) {
+        if (a || b) {
+            $inline$empty();
+        } else {
+            $inline$empty2();
+        }
+    }
+
+    /// CHECK-START: void Main.orBoolean3(boolean, boolean, boolean) dead_code_elimination$after_inlining (before)
+    /// CHECK: If
+    /// CHECK: If
+    /// CHECK: If
+
+    /// CHECK-START: void Main.orBoolean3(boolean, boolean, boolean) dead_code_elimination$after_inlining (after)
+    /// CHECK-NOT: If
+    public static void orBoolean3(boolean a, boolean b, boolean c) {
+        if (a || b || c) {
+            $inline$empty();
+        } else {
+            $inline$empty2();
+        }
+    }
+
+    /// CHECK-START: void Main.orBoolean4(boolean, boolean, boolean, boolean) dead_code_elimination$after_inlining (before)
+    /// CHECK: If
+    /// CHECK: If
+    /// CHECK: If
+    /// CHECK: If
+
+    /// CHECK-START: void Main.orBoolean4(boolean, boolean, boolean, boolean) dead_code_elimination$after_inlining (after)
+    /// CHECK-NOT: If
+    public static void orBoolean4(boolean a, boolean b, boolean c, boolean d) {
+        if (a || b || c || d) {
+            $inline$empty();
+        } else {
+            $inline$empty2();
+        }
+    }
+
+    /// CHECK-START: void Main.andInt(int, int, int, int) dead_code_elimination$after_inlining (before)
+    /// CHECK: If
+    /// CHECK: If
+    /// CHECK: If
+    /// CHECK: If
+    /// CHECK: If
+
+    /// CHECK-START: void Main.andInt(int, int, int, int) dead_code_elimination$after_inlining (after)
+    /// CHECK-NOT: If
+    public static void andInt(int a, int b, int c, int d) {
+        if (a <= b && c <= d && a >= 20 && b <= 78 && c >= 50 && d <= 70) {
+            $inline$empty();
+        } else {
+            $inline$empty2();
+        }
+    }
+
+    class MyObject {
+        boolean inner;
+        boolean inner2;
+    }
+
+    /// CHECK-START: void Main.andObject(Main$MyObject) dead_code_elimination$after_inlining (before)
+    /// CHECK: If
+    /// CHECK: If
+
+    /// CHECK-START: void Main.andObject(Main$MyObject) dead_code_elimination$after_inlining (before)
+    /// CHECK: InstanceFieldGet
+    /// CHECK: InstanceFieldGet
+
+    /// CHECK-START: void Main.andObject(Main$MyObject) dead_code_elimination$after_inlining (after)
+    /// CHECK-NOT: If
+    /// CHECK-NOT: InstanceFieldGet
+    public static void andObject(MyObject o) {
+        if (o != null && o.inner && o.inner2) {
+            $inline$empty();
+        } else {
+            $inline$empty2();
+        }
+    }
+}