/*
|
* 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_ANALYSIS_H_
|
#define ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
|
|
#include <string>
|
|
#include "nodes.h"
|
#include "optimization.h"
|
|
namespace art {
|
|
/**
|
* Induction variable analysis. This class does not have a direct public API.
|
* Instead, the results of induction variable analysis can be queried through
|
* friend classes, such as InductionVarRange.
|
*
|
* The analysis implementation is based on the paper by M. Gerlek et al.
|
* "Beyond Induction Variables: Detecting and Classifying Sequences Using a Demand-Driven SSA Form"
|
* (ACM Transactions on Programming Languages and Systems, Volume 17 Issue 1, Jan. 1995).
|
*/
|
class HInductionVarAnalysis : public HOptimization {
|
public:
|
explicit HInductionVarAnalysis(HGraph* graph, const char* name = kInductionPassName);
|
|
bool Run() override;
|
|
static constexpr const char* kInductionPassName = "induction_var_analysis";
|
|
private:
|
struct NodeInfo {
|
explicit NodeInfo(uint32_t d) : depth(d), done(false) {}
|
uint32_t depth;
|
bool done;
|
};
|
|
enum InductionClass {
|
kInvariant,
|
kLinear,
|
kPolynomial,
|
kGeometric,
|
kWrapAround,
|
kPeriodic
|
};
|
|
enum InductionOp {
|
// Operations.
|
kNop,
|
kAdd,
|
kSub,
|
kNeg,
|
kMul,
|
kDiv,
|
kRem,
|
kXor,
|
kFetch,
|
// Trip-counts.
|
kTripCountInLoop, // valid in full loop; loop is finite
|
kTripCountInBody, // valid in body only; loop is finite
|
kTripCountInLoopUnsafe, // valid in full loop; loop may be infinite
|
kTripCountInBodyUnsafe, // valid in body only; loop may be infinite
|
// Comparisons for trip-count tests.
|
kLT,
|
kLE,
|
kGT,
|
kGE
|
};
|
|
/**
|
* Defines a detected induction as:
|
* (1) invariant:
|
* op: a + b, a - b, -b, a * b, a / b, a % b, a ^ b, fetch
|
* (2) linear:
|
* nop: a * i + b
|
* (3) polynomial:
|
* nop: sum_lt(a) + b, for linear a
|
* (4) geometric:
|
* op: a * fetch^i + b, a * fetch^-i + b
|
* (5) wrap-around
|
* nop: a, then defined by b
|
* (6) periodic
|
* nop: a, then defined by b (repeated when exhausted)
|
* (7) trip-count:
|
* tc: defined by a, taken-test in b
|
*/
|
struct InductionInfo : public ArenaObject<kArenaAllocInductionVarAnalysis> {
|
InductionInfo(InductionClass ic,
|
InductionOp op,
|
InductionInfo* a,
|
InductionInfo* b,
|
HInstruction* f,
|
DataType::Type t)
|
: induction_class(ic),
|
operation(op),
|
op_a(a),
|
op_b(b),
|
fetch(f),
|
type(t) {}
|
InductionClass induction_class;
|
InductionOp operation;
|
InductionInfo* op_a;
|
InductionInfo* op_b;
|
HInstruction* fetch;
|
DataType::Type type; // precision of operation
|
};
|
|
bool IsVisitedNode(HInstruction* instruction) const {
|
return map_.find(instruction) != map_.end();
|
}
|
|
InductionInfo* CreateInvariantOp(InductionOp op, InductionInfo* a, InductionInfo* b) {
|
DCHECK(((op != kNeg && a != nullptr) || (op == kNeg && a == nullptr)) && b != nullptr);
|
return CreateSimplifiedInvariant(op, a, b);
|
}
|
|
InductionInfo* CreateInvariantFetch(HInstruction* f) {
|
DCHECK(f != nullptr);
|
return new (graph_->GetAllocator())
|
InductionInfo(kInvariant, kFetch, nullptr, nullptr, f, f->GetType());
|
}
|
|
InductionInfo* CreateTripCount(InductionOp op,
|
InductionInfo* a,
|
InductionInfo* b,
|
DataType::Type type) {
|
DCHECK(a != nullptr && b != nullptr);
|
return new (graph_->GetAllocator()) InductionInfo(kInvariant, op, a, b, nullptr, type);
|
}
|
|
InductionInfo* CreateInduction(InductionClass ic,
|
InductionOp op,
|
InductionInfo* a,
|
InductionInfo* b,
|
HInstruction* f,
|
DataType::Type type) {
|
DCHECK(a != nullptr && b != nullptr);
|
return new (graph_->GetAllocator()) InductionInfo(ic, op, a, b, f, type);
|
}
|
|
// Methods for analysis.
|
void VisitLoop(HLoopInformation* loop);
|
void VisitNode(HLoopInformation* loop, HInstruction* instruction);
|
uint32_t VisitDescendant(HLoopInformation* loop, HInstruction* instruction);
|
void ClassifyTrivial(HLoopInformation* loop, HInstruction* instruction);
|
void ClassifyNonTrivial(HLoopInformation* loop);
|
InductionInfo* RotatePeriodicInduction(InductionInfo* induction, InductionInfo* last);
|
|
// Transfer operations.
|
InductionInfo* TransferPhi(HLoopInformation* loop,
|
HInstruction* phi,
|
size_t input_index,
|
size_t adjust_input_size);
|
InductionInfo* TransferAddSub(InductionInfo* a, InductionInfo* b, InductionOp op);
|
InductionInfo* TransferNeg(InductionInfo* a);
|
InductionInfo* TransferMul(InductionInfo* a, InductionInfo* b);
|
InductionInfo* TransferConversion(InductionInfo* a, DataType::Type from, DataType::Type to);
|
|
// Solvers.
|
InductionInfo* SolvePhi(HInstruction* phi, size_t input_index, size_t adjust_input_size);
|
InductionInfo* SolvePhiAllInputs(HLoopInformation* loop,
|
HInstruction* entry_phi,
|
HInstruction* phi);
|
InductionInfo* SolveAddSub(HLoopInformation* loop,
|
HInstruction* entry_phi,
|
HInstruction* instruction,
|
HInstruction* x,
|
HInstruction* y,
|
InductionOp op,
|
bool is_first_call); // possibly swaps x and y to try again
|
InductionInfo* SolveOp(HLoopInformation* loop,
|
HInstruction* entry_phi,
|
HInstruction* instruction,
|
HInstruction* x,
|
HInstruction* y,
|
InductionOp op);
|
InductionInfo* SolveTest(HLoopInformation* loop,
|
HInstruction* entry_phi,
|
HInstruction* instruction,
|
int64_t oppositive_value);
|
InductionInfo* SolveConversion(HLoopInformation* loop,
|
HInstruction* entry_phi,
|
HTypeConversion* conversion);
|
|
//
|
// Loop trip count analysis methods.
|
//
|
|
// Trip count information.
|
void VisitControl(HLoopInformation* loop);
|
void VisitCondition(HLoopInformation* loop,
|
HBasicBlock* body,
|
InductionInfo* a,
|
InductionInfo* b,
|
DataType::Type type,
|
IfCondition cmp);
|
void VisitTripCount(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,
|
int64_t stride_value,
|
DataType::Type type,
|
IfCondition cmp);
|
bool FitsNarrowerControl(InductionInfo* lower_expr,
|
InductionInfo* upper_expr,
|
int64_t stride_value,
|
DataType::Type type,
|
IfCondition cmp);
|
bool RewriteBreakLoop(HLoopInformation* loop,
|
HBasicBlock* body,
|
int64_t stride_value,
|
DataType::Type type);
|
|
//
|
// Helper methods.
|
//
|
|
// Assign and lookup.
|
void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);
|
InductionInfo* LookupInfo(HLoopInformation* loop, HInstruction* instruction);
|
InductionInfo* CreateConstant(int64_t value, DataType::Type type);
|
InductionInfo* CreateSimplifiedInvariant(InductionOp op, InductionInfo* a, InductionInfo* b);
|
HInstruction* GetShiftConstant(HLoopInformation* loop,
|
HInstruction* instruction,
|
InductionInfo* initial);
|
void AssignCycle(HPhi* phi);
|
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);
|
|
// Helpers.
|
static bool IsNarrowingLinear(InductionInfo* info);
|
static bool InductionEqual(InductionInfo* info1, InductionInfo* info2);
|
static std::string FetchToString(HInstruction* fetch);
|
static std::string InductionToString(InductionInfo* info);
|
|
// TODO: fine tune the following data structures, only keep relevant data.
|
|
// Temporary book-keeping during the analysis.
|
uint32_t global_depth_;
|
ArenaVector<HInstruction*> stack_;
|
ArenaSafeMap<HInstruction*, NodeInfo> map_;
|
ArenaVector<HInstruction*> scc_;
|
ArenaSafeMap<HInstruction*, InductionInfo*> cycle_;
|
DataType::Type type_;
|
|
/**
|
* 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_;
|
|
/**
|
* Preserves induction cycle information for each loop-phi.
|
*/
|
ArenaSafeMap<HPhi*, ArenaSet<HInstruction*>> cycles_;
|
|
friend class InductionVarAnalysisTest;
|
friend class InductionVarRange;
|
friend class InductionVarRangeTest;
|
|
DISALLOW_COPY_AND_ASSIGN(HInductionVarAnalysis);
|
};
|
|
} // namespace art
|
|
#endif // ART_COMPILER_OPTIMIZING_INDUCTION_VAR_ANALYSIS_H_
|
