1/*
2 * Copyright (C) 2015 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_
18#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_
19
20#include "induction_var_analysis.h"
21
22namespace art {
23
24/**
25 * This class implements range analysis on expressions within loops. It takes the results
26 * of induction variable analysis in the constructor and provides a public API to obtain
27 * a conservative lower and upper bound value on each instruction in the HIR.
28 *
29 * The range analysis is done with a combination of symbolic and partial integral evaluation
30 * of expressions. The analysis avoids complications with wrap-around arithmetic on the integral
31 * parts but all clients should be aware that wrap-around may occur on any of the symbolic parts.
32 * For example, given a known range for [0,100] for i, the evaluation yields range [-100,100]
33 * for expression -2*i+100, which is exact, and range [x,x+100] for expression i+x, which may
34 * wrap-around anywhere in the range depending on the actual value of x.
35 */
36class InductionVarRange {
37 public:
38  /*
39   * A value that can be represented as "a * instruction + b" for 32-bit constants, where
40   * Value() denotes an unknown lower and upper bound. Although range analysis could yield
41   * more complex values, the format is sufficiently powerful to represent useful cases
42   * and feeds directly into optimizations like bounds check elimination.
43   */
44  struct Value {
45    Value() : instruction(nullptr), a_constant(0), b_constant(0), is_known(false) {}
46    Value(HInstruction* i, int32_t a, int32_t b)
47        : instruction(a != 0 ? i : nullptr), a_constant(a), b_constant(b), is_known(true) {}
48    explicit Value(int32_t b) : Value(nullptr, 0, b) {}
49    // Representation as: a_constant x instruction + b_constant.
50    HInstruction* instruction;
51    int32_t a_constant;
52    int32_t b_constant;
53    // If true, represented by prior fields. Otherwise unknown value.
54    bool is_known;
55  };
56
57  explicit InductionVarRange(HInductionVarAnalysis* induction);
58
59  /**
60   * Given a context denoted by the first instruction, returns a possibly conservative
61   * lower and upper bound on the instruction's value in the output parameters min_val
62   * and max_val, respectively. The need_finite_test flag denotes if an additional finite-test
63   * is needed to protect the range evaluation inside its loop. Returns false on failure.
64   */
65  bool GetInductionRange(HInstruction* context,
66                         HInstruction* instruction,
67                         /*out*/ Value* min_val,
68                         /*out*/ Value* max_val,
69                         /*out*/ bool* needs_finite_test);
70
71  /** Refines the values with induction of next outer loop. Returns true on change. */
72  bool RefineOuter(/*in-out*/ Value* min_val,
73                   /*in-out*/ Value* max_val) const;
74
75  /**
76   * Returns true if range analysis is able to generate code for the lower and upper
77   * bound expressions on the instruction in the given context. The need_finite_test
78   * and need_taken test flags denote if an additional finite-test and/or taken-test
79   * are needed to protect the range evaluation inside its loop.
80   */
81  bool CanGenerateCode(HInstruction* context,
82                       HInstruction* instruction,
83                       /*out*/ bool* needs_finite_test,
84                       /*out*/ bool* needs_taken_test);
85
86  /**
87   * Generates the actual code in the HIR for the lower and upper bound expressions on the
88   * instruction in the given context. Code for the lower and upper bound expression are
89   * generated in given block and graph and are returned in the output parameters lower and
90   * upper, respectively. For a loop invariant, lower is not set.
91   *
92   * For example, given expression x+i with range [0, 5] for i, calling this method
93   * will generate the following sequence:
94   *
95   * block:
96   *   lower: add x, 0
97   *   upper: add x, 5
98   *
99   * Precondition: CanGenerateCode() returns true.
100   */
101  void GenerateRangeCode(HInstruction* context,
102                         HInstruction* instruction,
103                         HGraph* graph,
104                         HBasicBlock* block,
105                         /*out*/ HInstruction** lower,
106                         /*out*/ HInstruction** upper);
107
108  /**
109   * Generates explicit taken-test for the loop in the given context. Code is generated in
110   * given block and graph. The taken-test is returned in parameter test.
111   *
112   * Precondition: CanGenerateCode() returns true and needs_taken_test is set.
113   */
114  void GenerateTakenTest(HInstruction* context,
115                         HGraph* graph,
116                         HBasicBlock* block,
117                         /*out*/ HInstruction** taken_test);
118
119 private:
120  /*
121   * Enum used in IsConstant() request.
122   */
123  enum ConstantRequest {
124    kExact,
125    kAtMost,
126    kAtLeast
127  };
128
129  /**
130   * Returns true if exact or upper/lower bound on the given induction
131   * information is known as a 64-bit constant, which is returned in value.
132   */
133  bool IsConstant(HInductionVarAnalysis::InductionInfo* info,
134                  ConstantRequest request,
135                  /*out*/ int64_t *value) const;
136
137  bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const;
138  bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
139  bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const;
140
141  Value GetLinear(HInductionVarAnalysis::InductionInfo* info,
142                  HInductionVarAnalysis::InductionInfo* trip,
143                  bool in_body,
144                  bool is_min) const;
145  Value GetFetch(HInstruction* instruction,
146                 HInductionVarAnalysis::InductionInfo* trip,
147                 bool in_body,
148                 bool is_min) const;
149  Value GetVal(HInductionVarAnalysis::InductionInfo* info,
150               HInductionVarAnalysis::InductionInfo* trip,
151               bool in_body,
152               bool is_min) const;
153  Value GetMul(HInductionVarAnalysis::InductionInfo* info1,
154               HInductionVarAnalysis::InductionInfo* info2,
155               HInductionVarAnalysis::InductionInfo* trip,
156               bool in_body,
157               bool is_min) const;
158  Value GetDiv(HInductionVarAnalysis::InductionInfo* info1,
159               HInductionVarAnalysis::InductionInfo* info2,
160               HInductionVarAnalysis::InductionInfo* trip,
161               bool in_body,
162               bool is_min) const;
163
164  Value MulRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const;
165  Value DivRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const;
166
167  Value AddValue(Value v1, Value v2) const;
168  Value SubValue(Value v1, Value v2) const;
169  Value MulValue(Value v1, Value v2) const;
170  Value DivValue(Value v1, Value v2) const;
171  Value MergeVal(Value v1, Value v2, bool is_min) const;
172
173  /**
174   * Returns refined value using induction of next outer loop or the input value if no
175   * further refinement is possible.
176   */
177  Value RefineOuter(Value val, bool is_min) const;
178
179  /**
180   * Generates code for lower/upper/taken-test in the HIR. Returns true on success.
181   * With values nullptr, the method can be used to determine if code generation
182   * would be successful without generating actual code yet.
183   */
184  bool GenerateCode(HInstruction* context,
185                    HInstruction* instruction,
186                    HGraph* graph,
187                    HBasicBlock* block,
188                    /*out*/ HInstruction** lower,
189                    /*out*/ HInstruction** upper,
190                    /*out*/ HInstruction** taken_test,
191                    /*out*/ bool* needs_finite_test,
192                    /*out*/ bool* needs_taken_test) const;
193
194  bool GenerateCode(HInductionVarAnalysis::InductionInfo* info,
195                    HInductionVarAnalysis::InductionInfo* trip,
196                    HGraph* graph,
197                    HBasicBlock* block,
198                    /*out*/ HInstruction** result,
199                    bool in_body,
200                    bool is_min) const;
201
202  /** Results of prior induction variable analysis. */
203  HInductionVarAnalysis *induction_analysis_;
204
205  friend class HInductionVarAnalysis;
206  friend class InductionVarRangeTest;
207
208  DISALLOW_COPY_AND_ASSIGN(InductionVarRange);
209};
210
211}  // namespace art
212
213#endif  // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_
214