Implemented trip-count safety information.
As shown in the induction analysis presentation, trip-counts need to
deal with potential taken/not-taken situations (so that trip-count
is either valid in the full loop or just in the loop-body proper)
and potential finite/infinite situations (the latter can still be
analyzed but may need to run-time test later to guard against the
infinite conditions). This CL provides that information.
Change-Id: I0445d8e836b80a3614af217ce3e39d766e77b986
diff --git a/compiler/optimizing/induction_var_analysis.h b/compiler/optimizing/induction_var_analysis.h
index 190a0db..9669bcc 100644
--- a/compiler/optimizing/induction_var_analysis.h
+++ b/compiler/optimizing/induction_var_analysis.h
@@ -56,13 +56,20 @@
};
enum InductionOp {
- kNop, // no-operation: a true induction
+ // No-operation: a true induction.
+ kNop,
+ // Various invariant operations.
kAdd,
kSub,
kNeg,
kMul,
kDiv,
- kFetch
+ kFetch,
+ // Trip counts (valid in full loop or only body proper; unsafe implies loop may be infinite).
+ kTripCountInLoop,
+ kTripCountInBody,
+ kTripCountInLoopUnsafe,
+ kTripCountInBodyUnsafe
};
/**
@@ -77,6 +84,8 @@
* nop: a, then defined by b
* (4) periodic
* nop: a, then defined by b (repeated when exhausted)
+ * (5) trip-count:
+ * tc: defined by b
*/
struct InductionInfo : public ArenaObject<kArenaAllocMisc> {
InductionInfo(InductionClass ic,
@@ -110,6 +119,10 @@
return new (graph_->GetArena()) InductionInfo(kInvariant, kFetch, nullptr, nullptr, f);
}
+ InductionInfo* CreateTripCount(InductionOp op, InductionInfo* b) {
+ return new (graph_->GetArena()) InductionInfo(kInvariant, op, nullptr, b, nullptr);
+ }
+
InductionInfo* CreateInduction(InductionClass ic, InductionInfo* a, InductionInfo* b) {
DCHECK(a != nullptr && b != nullptr);
return new (graph_->GetArena()) InductionInfo(ic, kNop, a, b, nullptr);
@@ -151,12 +164,17 @@
Primitive::Type type,
IfCondition cmp);
void VisitTripCount(HLoopInformation* loop,
- InductionInfo* lo_val,
- InductionInfo* hi_val,
+ InductionInfo* lower_expr,
+ InductionInfo* upper_expr,
InductionInfo* stride,
- int32_t stride_value,
+ int64_t stride_value,
Primitive::Type type,
IfCondition cmp);
+ bool IsTaken(InductionInfo* lower_expr, InductionInfo* upper_expr, IfCondition cmp);
+ bool IsFinite(InductionInfo* upper_expr,
+ int64_t stride_value,
+ Primitive::Type type,
+ IfCondition cmp);
// Assign and lookup.
void AssignInfo(HLoopInformation* loop, HInstruction* instruction, InductionInfo* info);