Improve bce so that more bounds checks can be eliminated.
For pattern like "int[] array = new int[size+1]", we record this range
for size:
[-1, array.length-1]
This can eliminate more bounds checks.
Also simplify overflow/underflow handling and make it more solid.
Enhance instruction simplifier such that if array is a result of
NewArray with a constant size, replace array.length with that constant.
Plan to move all bce gtests to checker in another change.
Change-Id: Ibe7cc7940b68fb6465dc3e0ff3ebdb0fd6487aa9
diff --git a/compiler/optimizing/bounds_check_elimination_test.cc b/compiler/optimizing/bounds_check_elimination_test.cc
index 3dcb08d..662834a 100644
--- a/compiler/optimizing/bounds_check_elimination_test.cc
+++ b/compiler/optimizing/bounds_check_elimination_test.cc
@@ -17,6 +17,7 @@
#include "bounds_check_elimination.h"
#include "builder.h"
#include "gvn.h"
+#include "instruction_simplifier.h"
#include "nodes.h"
#include "optimizing_unit_test.h"
#include "side_effects_analysis.h"
@@ -26,7 +27,9 @@
namespace art {
-static void RunGvn(HGraph* graph) {
+static void RunSimplifierAndGvn(HGraph* graph) {
+ InstructionSimplifier simplify(graph);
+ simplify.Run();
SideEffectsAnalysis side_effects(graph);
side_effects.Run();
GVNOptimization(graph, side_effects).Run();
@@ -127,7 +130,7 @@
block3->AddSuccessor(block4); // False successor
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
ASSERT_FALSE(IsRemoved(bounds_check2));
@@ -202,7 +205,7 @@
block3->AddSuccessor(exit);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -277,7 +280,7 @@
block3->AddSuccessor(exit);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -351,7 +354,7 @@
exit->AddInstruction(new (&allocator) HExit());
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination(graph);
bounds_check_elimination.Run();
ASSERT_FALSE(IsRemoved(bounds_check5));
@@ -450,7 +453,7 @@
// HArrayLength which uses the null check as its input.
graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -458,7 +461,7 @@
// for (int i=1; i<array.length; i++) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -466,7 +469,7 @@
// for (int i=-1; i<array.length; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, -1, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
bounds_check_elimination_with_initial_minus_1.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -474,7 +477,7 @@
// for (int i=0; i<=array.length; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 1, kCondGT);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
bounds_check_elimination_with_greater_than.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -483,7 +486,7 @@
// array[i] = 10; // Can't eliminate due to overflow concern. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 0, 2);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_increment_2(graph);
bounds_check_elimination_with_increment_2.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -491,7 +494,7 @@
// for (int i=1; i<array.length; i += 2) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph1(&allocator, &bounds_check, 1, 2);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_increment_2_from_1(graph);
bounds_check_elimination_with_increment_2_from_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -591,7 +594,7 @@
// HArrayLength which uses the null check as its input.
graph = BuildSSAGraph2(&allocator, &bounds_check, 0);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -599,7 +602,7 @@
// for (int i=array.length; i>1; i--) { array[i-1] = 10; // Can eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -607,7 +610,7 @@
// for (int i=array.length; i>-1; i--) { array[i-1] = 10; // Can't eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, -1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_minus_1(graph);
bounds_check_elimination_with_initial_minus_1.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -615,7 +618,7 @@
// for (int i=array.length; i>=0; i--) { array[i-1] = 10; // Can't eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -1, kCondLT);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_less_than(graph);
bounds_check_elimination_with_less_than.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -623,7 +626,7 @@
// for (int i=array.length; i>0; i-=2) { array[i-1] = 10; // Can eliminate. }
graph = BuildSSAGraph2(&allocator, &bounds_check, 0, -2);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_increment_minus_2(graph);
bounds_check_elimination_increment_minus_2.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -710,7 +713,7 @@
HInstruction* bounds_check = nullptr;
HGraph* graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGE);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -719,7 +722,7 @@
// for (int i=1; i<10; i++) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 1, kCondGE);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -728,7 +731,7 @@
// for (int i=0; i<=10; i++) { array[i] = 10; // Can't eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 0, 1, kCondGT);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
bounds_check_elimination_with_greater_than.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -737,7 +740,7 @@
// for (int i=1; i<10; i+=8) { array[i] = 10; // Can eliminate. }
graph = BuildSSAGraph3(&allocator, &bounds_check, 1, 8, kCondGE);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_increment_8(graph);
bounds_check_elimination_increment_8.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -838,7 +841,7 @@
// HArrayLength which uses the null check as its input.
graph = BuildSSAGraph4(&allocator, &bounds_check, 0);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_after_gvn(graph);
bounds_check_elimination_after_gvn.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -846,7 +849,7 @@
// for (int i=1; i<array.length; i++) { array[array.length-i-1] = 10; // Can eliminate. }
graph = BuildSSAGraph4(&allocator, &bounds_check, 1);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_initial_1(graph);
bounds_check_elimination_with_initial_1.Run();
ASSERT_TRUE(IsRemoved(bounds_check));
@@ -854,7 +857,7 @@
// for (int i=0; i<=array.length; i++) { array[array.length-i] = 10; // Can't eliminate. }
graph = BuildSSAGraph4(&allocator, &bounds_check, 0, kCondGT);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
BoundsCheckElimination bounds_check_elimination_with_greater_than(graph);
bounds_check_elimination_with_greater_than.Run();
ASSERT_FALSE(IsRemoved(bounds_check));
@@ -1030,7 +1033,7 @@
outer_body_add->AddSuccessor(outer_header);
graph->BuildDominatorTree();
- RunGvn(graph);
+ RunSimplifierAndGvn(graph);
// gvn should remove the same bounds check.
ASSERT_FALSE(IsRemoved(bounds_check1));
ASSERT_FALSE(IsRemoved(bounds_check2));