ART: Refactor scalar loop optimizations.
Refactor scalar loop peeling and unrolling to eliminate repeated
checks and graph traversals, to make the code more readable and
to make it easier to add new scalar loop opts.
This is a prerequisite for full unrolling patch.
Test: 530-checker-peel-unroll.
Test: test-art-target, test-art-host.
Change-Id: If824a95f304033555085eefac7524e59ed540322
diff --git a/compiler/optimizing/loop_analysis.h b/compiler/optimizing/loop_analysis.h
index 7f321b7..bcb7b70 100644
--- a/compiler/optimizing/loop_analysis.h
+++ b/compiler/optimizing/loop_analysis.h
@@ -21,26 +21,33 @@
namespace art {
+class InductionVarRange;
class LoopAnalysis;
-// No loop unrolling factor (just one copy of the loop-body).
-static constexpr uint32_t kNoUnrollingFactor = 1;
-
// Class to hold cached information on properties of the loop.
class LoopAnalysisInfo : public ValueObject {
public:
+ // No loop unrolling factor (just one copy of the loop-body).
+ static constexpr uint32_t kNoUnrollingFactor = 1;
+ // Used for unknown and non-constant trip counts (see InductionVarRange::HasKnownTripCount).
+ static constexpr int64_t kUnknownTripCount = -1;
+
explicit LoopAnalysisInfo(HLoopInformation* loop_info)
- : bb_num_(0),
+ : trip_count_(kUnknownTripCount),
+ bb_num_(0),
instr_num_(0),
exits_num_(0),
+ invariant_exits_num_(0),
has_instructions_preventing_scalar_peeling_(false),
has_instructions_preventing_scalar_unrolling_(false),
has_long_type_instructions_(false),
loop_info_(loop_info) {}
+ int64_t GetTripCount() const { return trip_count_; }
size_t GetNumberOfBasicBlocks() const { return bb_num_; }
size_t GetNumberOfInstructions() const { return instr_num_; }
size_t GetNumberOfExits() const { return exits_num_; }
+ size_t GetNumberOfInvariantExits() const { return invariant_exits_num_; }
bool HasInstructionsPreventingScalarPeeling() const {
return has_instructions_preventing_scalar_peeling_;
@@ -50,19 +57,27 @@
return has_instructions_preventing_scalar_unrolling_;
}
+ bool HasInstructionsPreventingScalarOpts() const {
+ return HasInstructionsPreventingScalarPeeling() || HasInstructionsPreventingScalarUnrolling();
+ }
+
bool HasLongTypeInstructions() const {
return has_long_type_instructions_;
}
- const HLoopInformation* GetLoopInfo() const { return loop_info_; }
+ HLoopInformation* GetLoopInfo() const { return loop_info_; }
private:
+ // Trip count of the loop if known, kUnknownTripCount otherwise.
+ int64_t trip_count_;
// Number of basic blocks in the loop body.
size_t bb_num_;
// Number of instructions in the loop body.
size_t instr_num_;
// Number of loop's exits.
size_t exits_num_;
+ // Number of "if" loop exits (with HIf instruction) whose condition is loop-invariant.
+ size_t invariant_exits_num_;
// Whether the loop has instructions which make scalar loop peeling non-beneficial.
bool has_instructions_preventing_scalar_peeling_;
// Whether the loop has instructions which make scalar loop unrolling non-beneficial.
@@ -72,7 +87,7 @@
bool has_long_type_instructions_;
// Corresponding HLoopInformation.
- const HLoopInformation* loop_info_;
+ HLoopInformation* loop_info_;
friend class LoopAnalysis;
};
@@ -84,20 +99,12 @@
// Calculates loops basic properties like body size, exits number, etc. and fills
// 'analysis_results' with this information.
static void CalculateLoopBasicProperties(HLoopInformation* loop_info,
- LoopAnalysisInfo* analysis_results);
+ LoopAnalysisInfo* analysis_results,
+ int64_t trip_count);
- // Returns whether the loop has at least one loop invariant exit.
- static bool HasLoopAtLeastOneInvariantExit(HLoopInformation* loop_info);
-
- // Returns whether HIf's true or false successor is outside the specified loop.
- //
- // Prerequisite: HIf must be in the specified loop.
- static bool IsLoopExit(HLoopInformation* loop_info, const HIf* hif) {
- DCHECK(loop_info->Contains(*hif->GetBlock()));
- HBasicBlock* true_succ = hif->IfTrueSuccessor();
- HBasicBlock* false_succ = hif->IfFalseSuccessor();
- return (!loop_info->Contains(*true_succ) || !loop_info->Contains(*false_succ));
- }
+ // Returns the trip count of the loop if it is known and kUnknownTripCount otherwise.
+ static int64_t GetLoopTripCount(HLoopInformation* loop_info,
+ const InductionVarRange* induction_range);
private:
// Returns whether an instruction makes scalar loop peeling/unrolling non-beneficial.
@@ -143,9 +150,9 @@
// Returns optimal scalar unrolling factor for the loop.
//
// Returns kNoUnrollingFactor by default, should be overridden by particular target loop helper.
- virtual uint32_t GetScalarUnrollingFactor(HLoopInformation* loop_info ATTRIBUTE_UNUSED,
- uint64_t trip_count ATTRIBUTE_UNUSED) const {
- return kNoUnrollingFactor;
+ virtual uint32_t GetScalarUnrollingFactor(
+ const LoopAnalysisInfo* analysis_info ATTRIBUTE_UNUSED) const {
+ return LoopAnalysisInfo::kNoUnrollingFactor;
}
// Returns whether scalar loop peeling is enabled,
@@ -160,7 +167,7 @@
int64_t trip_count ATTRIBUTE_UNUSED,
uint32_t max_peel ATTRIBUTE_UNUSED,
uint32_t vector_length ATTRIBUTE_UNUSED) const {
- return kNoUnrollingFactor;
+ return LoopAnalysisInfo::kNoUnrollingFactor;
}
};