Improve linear induction var range creation

We can now detect and remove loops that require an is_taken test e.g.

int a = 0;
for (int i = 0; i < n; i++) {
  a += 1;
}

can be turned into `if (n < 0) then 0 else n`.

Part of this logic can be reused in the future to help eliminate
BoundsCheck instructions.

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

1 files changed, 14 insertions, 3 deletions

diff --git a/compiler/optimizing/induction_var_range.h b/compiler/optimizing/induction_var_range.h
index f908b92282..a81227b41b 100644
--- a/compiler/optimizing/induction_var_range.h
+++ b/compiler/optimizing/induction_var_range.h
@@ -325,7 +325,8 @@ class InductionVarRange {
                                HGraph* graph,
                                HBasicBlock* block,
                                bool is_min,
-                               /*out*/ HInstruction** result) const;
+                               /*out*/ HInstruction** result,
+                               /*inout*/ bool* needs_taken_test) const;
 
   bool GenerateLastValuePolynomial(const HBasicBlock* context,
                                    const HLoopInformation* loop,
@@ -357,8 +358,8 @@ class InductionVarRange {
                                  HInductionVarAnalysis::InductionInfo* trip,
                                  HGraph* graph,
                                  HBasicBlock* block,
-                                 /*out*/HInstruction** result,
-                                 /*out*/ bool* needs_taken_test) const;
+                                 /*out*/ HInstruction** result,
+                                 /*inout*/ bool* needs_taken_test) const;
 
   bool GenerateCode(const HBasicBlock* context,
                     const HLoopInformation* loop,
@@ -386,6 +387,16 @@ class InductionVarRange {
                                      /*in*/ HInstruction* opa,
                                      /*out*/ HInstruction** result) const;
 
+  // Try to guard the taken test with an HSelect instruction. Returns true if it can generate the
+  // code, or false otherwise. The caller is responsible of updating `needs_taken_test`.
+  bool TryGenerateTakenTest(const HBasicBlock* context,
+                            const HLoopInformation* loop,
+                            HInductionVarAnalysis::InductionInfo* info,
+                            HGraph* graph,
+                            HBasicBlock* block,
+                            /*inout*/ HInstruction** result,
+                            /*inout*/ HInstruction* not_taken_result) const;
+
   void ReplaceInduction(HInductionVarAnalysis::InductionInfo* info,
                         HInstruction* fetch,
                         HInstruction* replacement);