Fix last value generation in loop optimization.

Instead of `in_body`, propagate the context block and loop
information to make better decisions for trip count if the
context is outside the loop.

In particular, fix `InductionVarRange::IsConstant()` to take
and use this information instead of assuming that we are
asking about values in the loop body.

For trip count with context outside the loop, we know that
the value shall be the maximum trip count if the context
is dominated by the loop control exit block.

Test: Enable run-test 835-b216762268.
Test: m test-art-host-gtest
Test: testrunner.py --host --optimizing
Bug: 216762268
Change-Id: Id564ba75c812d54abdd9b229e643cc8ab4701c52

1 files changed, 67 insertions, 30 deletions

diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 616100b068..09417722da 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -119,9 +119,13 @@ class HInductionVarAnalysis : public HOptimization {
   };
 
 
-  InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
+  InductionInfo* CreateInvariantOp(const HBasicBlock* context,
+                                   const HLoopInformation* loop,
+                                   InductionOp op,
+                                   InductionInfo* a,
+                                   InductionInfo* b) {
     DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
-    return CreateSimplifiedInvariant(op, a, b);
+    return CreateSimplifiedInvariant(context, loop, op, a, b);
   }
 
   InductionInfo* CreateInvariantFetch(HInstruction* f) {
@@ -149,29 +153,38 @@ class HInductionVarAnalysis : public HOptimization {
   }
 
   // Methods for analysis.
-  void VisitLoop(HLoopInformation* loop);
-  size_t TryVisitNodes(HLoopInformation* loop,
+  void VisitLoop(const HLoopInformation* loop);
+  size_t TryVisitNodes(const HLoopInformation* loop,
                        HInstruction* start_instruction,
                        size_t global_depth,
                        /*inout*/ ScopedArenaSafeMap<HInstruction*, NodeInfo>* visited_instructions);
   void ExtractScc(ArrayRef<const StackEntry> stack_tail, ScopedArenaVector<HInstruction*>* scc);
-  void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
-  void ClassifyNonTrivial(HLoopInformation* loop, ArrayRef<const StackEntry> stack_tail);
+  void ClassifyTrivial(const HLoopInformation* loop, HInstruction* instruction);
+  void ClassifyNonTrivial(const HLoopInformation* loop, ArrayRef<const StackEntry> stack_tail);
   InductionInfo* RotatePeriodicInduction(InductionInfo* induction,
                                          InductionInfo* last,
                                          DataType::Type type);
 
   // Transfer operations.
-  InductionInfo* TransferPhi(HLoopInformation* loop,
+  InductionInfo* TransferPhi(const HLoopInformation* loop,
                              HInstruction* phi,
                              size_t input_index,
                              size_t adjust_input_size);
-  InductionInfo* TransferAddSub(InductionInfo* a,
+  InductionInfo* TransferAddSub(const HBasicBlock* context,
+                                const HLoopInformation* loop,
+                                InductionInfo* a,
                                 InductionInfo* b,
                                 InductionOp op,
                                 DataType::Type type);
-  InductionInfo* TransferNeg(InductionInfo* a, DataType::Type type);
-  InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b, DataType::Type type);
+  InductionInfo* TransferNeg(const HBasicBlock* context,
+                             const HLoopInformation* loop,
+                             InductionInfo* a,
+                             DataType::Type type);
+  InductionInfo* TransferMul(const HBasicBlock* context,
+                             const HLoopInformation* loop,
+                             InductionInfo* a,
+                             InductionInfo* b,
+                             DataType::Type type);
   InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to);
 
   // Solvers.
@@ -179,12 +192,12 @@ class HInductionVarAnalysis : public HOptimization {
                           size_t input_index,
                           size_t adjust_input_size,
                           const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle);
-  InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
+  InductionInfo* SolvePhiAllInputs(const HLoopInformation* loop,
                                    HInstruction* entry_phi,
                                    HInstruction* phi,
                                    const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
                                    DataType::Type type);
-  InductionInfo* SolveAddSub(HLoopInformation* loop,
+  InductionInfo* SolveAddSub(const HLoopInformation* loop,
                              HInstruction* entry_phi,
                              HInstruction* instruction,
                              HInstruction* x,
@@ -192,19 +205,19 @@ class HInductionVarAnalysis : public HOptimization {
                              InductionOp op,
                              const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
                              DataType::Type type);
-  InductionInfo* SolveOp(HLoopInformation* loop,
+  InductionInfo* SolveOp(const HLoopInformation* loop,
                          HInstruction* entry_phi,
                          HInstruction* instruction,
                          HInstruction* x,
                          HInstruction* y,
                          InductionOp op,
                          DataType::Type type);
-  InductionInfo* SolveTest(HLoopInformation* loop,
+  InductionInfo* SolveTest(const HLoopInformation* loop,
                            HInstruction* entry_phi,
                            HInstruction* instruction,
                            int64_t opposite_value,
                            DataType::Type type);
-  InductionInfo* SolveConversion(HLoopInformation* loop,
+  InductionInfo* SolveConversion(const HLoopInformation* loop,
                                  HInstruction* entry_phi,
                                  HTypeConversion* conversion,
                                  const ScopedArenaSafeMap<HInstruction*, InductionInfo*>& cycle,
@@ -215,31 +228,42 @@ class HInductionVarAnalysis : public HOptimization {
   //
 
   // Trip count information.
-  void VisitControl(HLoopInformation* loop);
-  void VisitCondition(HLoopInformation* loop,
+  void VisitControl(const HLoopInformation* loop);
+  void VisitCondition(const HBasicBlock* context,
+                      const HLoopInformation* loop,
                       HBasicBlock* body,
                       InductionInfo* a,
                       InductionInfo* b,
                       DataType::Type type,
                       IfCondition cmp);
-  void VisitTripCount(HLoopInformation* loop,
+  void VisitTripCount(const HBasicBlock* context,
+                      const HLoopInformation* loop,
                       InductionInfo* lower_expr,
                       InductionInfo* upper_expr,
                       InductionInfo* stride,
                       int64_t stride_value,
                       DataType::Type type,
                       IfCondition cmp);
-  bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp);
-  bool IsFinite(InductionInfo* upper_expr,
+  bool IsTaken(const HBasicBlock* context,
+               const HLoopInformation* loop,
+               InductionInfo* lower_expr,
+               InductionInfo* upper_expr,
+               IfCondition cmp);
+  bool IsFinite(const HBasicBlock* context,
+                const HLoopInformation* loop,
+                InductionInfo* upper_expr,
                 int64_t stride_value,
                 DataType::Type type,
                 IfCondition cmp);
-  bool FitsNarrowerControl(InductionInfo* lower_expr,
+  bool FitsNarrowerControl(const HBasicBlock* context,
+                           const HLoopInformation* loop,
+                           InductionInfo* lower_expr,
                            InductionInfo* upper_expr,
                            int64_t stride_value,
                            DataType::Type type,
                            IfCondition cmp);
-  bool RewriteBreakLoop(HLoopInformation* loop,
+  bool RewriteBreakLoop(const HBasicBlock* context,
+                        const HLoopInformation* loop,
                         HBasicBlock* body,
                         int64_t stride_value,
                         DataType::Type type);
@@ -249,20 +273,33 @@ class HInductionVarAnalysis : public HOptimization {
   //
 
   // Assign and lookup.
-  void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
-  InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
+  void AssignInfo(const HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
+  InductionInfo* LookupInfo(const HLoopInformation* loop, HInstruction* instruction);
   InductionInfo* CreateConstant(int64_t value, DataType::Type type);
-  InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
-  HInstruction* GetShiftConstant(HLoopInformation* loop,
+  InductionInfo* CreateSimplifiedInvariant(const HBasicBlock* context,
+                                           const HLoopInformation* loop,
+                                           InductionOp op,
+                                           InductionInfo* a,
+                                           InductionInfo* b);
+  HInstruction* GetShiftConstant(const HLoopInformation* loop,
                                  HInstruction* instruction,
                                  InductionInfo* initial);
   void AssignCycle(HPhi* phi, ArrayRef<HInstruction* const> scc);
   ArenaSet<HInstruction*>* LookupCycle(HPhi* phi);
 
   // Constants.
-  bool IsExact(InductionInfo* info, /*out*/ int64_t* value);
-  bool IsAtMost(InductionInfo* info, /*out*/ int64_t* value);
-  bool IsAtLeast(InductionInfo* info, /*out*/ int64_t* value);
+  bool IsExact(const HBasicBlock* context,
+               const HLoopInformation* loop,
+               InductionInfo* info,
+               /*out*/int64_t* value);
+  bool IsAtMost(const HBasicBlock* context,
+                const HLoopInformation* loop,
+                InductionInfo* info,
+                /*out*/int64_t* value);
+  bool IsAtLeast(const HBasicBlock* context,
+                 const HLoopInformation* loop,
+                 InductionInfo* info,
+                 /*out*/int64_t* value);
 
   // Helpers.
   static bool IsNarrowingLinear(InductionInfo* info);
@@ -274,7 +311,7 @@ class HInductionVarAnalysis : public HOptimization {
    * Maintains the results of the analysis as a mapping from loops to a mapping from instructions
    * to the induction information for that instruction in that loop.
    */
-  ArenaSafeMap<HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
+  ArenaSafeMap<const HLoopInformation*, ArenaSafeMap<HInstruction*, InductionInfo*>> induction_;
 
   /**
    * Preserves induction cycle information for each loop-phi.