android / platform / art / 748438ed62dbd130c2f52f2f0ede1ce75b6c28f0 / . / compiler / optimizing / induction_var_range.h

/* | |

* Copyright (C) 2015 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. | |

*/ | |

#ifndef ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ | |

#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ | |

#include "induction_var_analysis.h" | |

namespace art { | |

/** | |

* This class implements range analysis on expressions within loops. It takes the results | |

* of induction variable analysis in the constructor and provides a public API to obtain | |

* a conservative lower and upper bound value on each instruction in the HIR. | |

* | |

* The range analysis is done with a combination of symbolic and partial integral evaluation | |

* of expressions. The analysis avoids complications with wrap-around arithmetic on the integral | |

* parts but all clients should be aware that wrap-around may occur on any of the symbolic parts. | |

* For example, given a known range for [0,100] for i, the evaluation yields range [-100,100] | |

* for expression -2*i+100, which is exact, and range [x,x+100] for expression i+x, which may | |

* wrap-around anywhere in the range depending on the actual value of x. | |

*/ | |

class InductionVarRange { | |

public: | |

/* | |

* A value that can be represented as "a * instruction + b" for 32-bit constants, where | |

* Value() denotes an unknown lower and upper bound. Although range analysis could yield | |

* more complex values, the format is sufficiently powerful to represent useful cases | |

* and feeds directly into optimizations like bounds check elimination. | |

*/ | |

struct Value { | |

Value() : instruction(nullptr), a_constant(0), b_constant(0), is_known(false) {} | |

Value(HInstruction* i, int32_t a, int32_t b) | |

: instruction(a != 0 ? i : nullptr), a_constant(a), b_constant(b), is_known(true) {} | |

explicit Value(int32_t b) : Value(nullptr, 0, b) {} | |

// Representation as: a_constant x instruction + b_constant. | |

HInstruction* instruction; | |

int32_t a_constant; | |

int32_t b_constant; | |

// If true, represented by prior fields. Otherwise unknown value. | |

bool is_known; | |

}; | |

explicit InductionVarRange(HInductionVarAnalysis* induction); | |

/** | |

* Given a context denoted by the first instruction, returns a possibly conservative | |

* lower and upper bound on the instruction's value in the output parameters min_val | |

* and max_val, respectively. The need_finite_test flag denotes if an additional finite-test | |

* is needed to protect the range evaluation inside its loop. Returns false on failure. | |

*/ | |

bool GetInductionRange(HInstruction* context, | |

HInstruction* instruction, | |

/*out*/ Value* min_val, | |

/*out*/ Value* max_val, | |

/*out*/ bool* needs_finite_test); | |

/** Refines the values with induction of next outer loop. Returns true on change. */ | |

bool RefineOuter(/*in-out*/ Value* min_val, | |

/*in-out*/ Value* max_val) const; | |

/** | |

* Returns true if range analysis is able to generate code for the lower and upper | |

* bound expressions on the instruction in the given context. The need_finite_test | |

* and need_taken test flags denote if an additional finite-test and/or taken-test | |

* are needed to protect the range evaluation inside its loop. | |

*/ | |

bool CanGenerateCode(HInstruction* context, | |

HInstruction* instruction, | |

/*out*/ bool* needs_finite_test, | |

/*out*/ bool* needs_taken_test); | |

/** | |

* Generates the actual code in the HIR for the lower and upper bound expressions on the | |

* instruction in the given context. Code for the lower and upper bound expression are | |

* generated in given block and graph and are returned in the output parameters lower and | |

* upper, respectively. For a loop invariant, lower is not set. | |

* | |

* For example, given expression x+i with range [0, 5] for i, calling this method | |

* will generate the following sequence: | |

* | |

* block: | |

* lower: add x, 0 | |

* upper: add x, 5 | |

* | |

* Precondition: CanGenerateCode() returns true. | |

*/ | |

void GenerateRangeCode(HInstruction* context, | |

HInstruction* instruction, | |

HGraph* graph, | |

HBasicBlock* block, | |

/*out*/ HInstruction** lower, | |

/*out*/ HInstruction** upper); | |

/** | |

* Generates explicit taken-test for the loop in the given context. Code is generated in | |

* given block and graph. The taken-test is returned in parameter test. | |

* | |

* Precondition: CanGenerateCode() returns true and needs_taken_test is set. | |

*/ | |

void GenerateTakenTest(HInstruction* context, | |

HGraph* graph, | |

HBasicBlock* block, | |

/*out*/ HInstruction** taken_test); | |

private: | |

/* | |

* Enum used in IsConstant() request. | |

*/ | |

enum ConstantRequest { | |

kExact, | |

kAtMost, | |

kAtLeast | |

}; | |

/** | |

* Returns true if exact or upper/lower bound on the given induction | |

* information is known as a 64-bit constant, which is returned in value. | |

*/ | |

bool IsConstant(HInductionVarAnalysis::InductionInfo* info, | |

ConstantRequest request, | |

/*out*/ int64_t *value) const; | |

bool NeedsTripCount(HInductionVarAnalysis::InductionInfo* info) const; | |

bool IsBodyTripCount(HInductionVarAnalysis::InductionInfo* trip) const; | |

bool IsUnsafeTripCount(HInductionVarAnalysis::InductionInfo* trip) const; | |

Value GetLinear(HInductionVarAnalysis::InductionInfo* info, | |

HInductionVarAnalysis::InductionInfo* trip, | |

bool in_body, | |

bool is_min) const; | |

Value GetFetch(HInstruction* instruction, | |

HInductionVarAnalysis::InductionInfo* trip, | |

bool in_body, | |

bool is_min) const; | |

Value GetVal(HInductionVarAnalysis::InductionInfo* info, | |

HInductionVarAnalysis::InductionInfo* trip, | |

bool in_body, | |

bool is_min) const; | |

Value GetMul(HInductionVarAnalysis::InductionInfo* info1, | |

HInductionVarAnalysis::InductionInfo* info2, | |

HInductionVarAnalysis::InductionInfo* trip, | |

bool in_body, | |

bool is_min) const; | |

Value GetDiv(HInductionVarAnalysis::InductionInfo* info1, | |

HInductionVarAnalysis::InductionInfo* info2, | |

HInductionVarAnalysis::InductionInfo* trip, | |

bool in_body, | |

bool is_min) const; | |

Value MulRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const; | |

Value DivRangeAndConstant(Value v1, Value v2, Value c, bool is_min) const; | |

Value AddValue(Value v1, Value v2) const; | |

Value SubValue(Value v1, Value v2) const; | |

Value MulValue(Value v1, Value v2) const; | |

Value DivValue(Value v1, Value v2) const; | |

Value MergeVal(Value v1, Value v2, bool is_min) const; | |

/** | |

* Returns refined value using induction of next outer loop or the input value if no | |

* further refinement is possible. | |

*/ | |

Value RefineOuter(Value val, bool is_min) const; | |

/** | |

* Generates code for lower/upper/taken-test in the HIR. Returns true on success. | |

* With values nullptr, the method can be used to determine if code generation | |

* would be successful without generating actual code yet. | |

*/ | |

bool GenerateCode(HInstruction* context, | |

HInstruction* instruction, | |

HGraph* graph, | |

HBasicBlock* block, | |

/*out*/ HInstruction** lower, | |

/*out*/ HInstruction** upper, | |

/*out*/ HInstruction** taken_test, | |

/*out*/ bool* needs_finite_test, | |

/*out*/ bool* needs_taken_test) const; | |

bool GenerateCode(HInductionVarAnalysis::InductionInfo* info, | |

HInductionVarAnalysis::InductionInfo* trip, | |

HGraph* graph, | |

HBasicBlock* block, | |

/*out*/ HInstruction** result, | |

bool in_body, | |

bool is_min) const; | |

/** Results of prior induction variable analysis. */ | |

HInductionVarAnalysis *induction_analysis_; | |

friend class HInductionVarAnalysis; | |

friend class InductionVarRangeTest; | |

DISALLOW_COPY_AND_ASSIGN(InductionVarRange); | |

}; | |

} // namespace art | |

#endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_RANGE_H_ |