compiler/optimizing/induction_var_range.h - platform/art - Gitiles

 /*
  * 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_
	/*
	* 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_