1// Copyright (c) 2018, the Dart project authors. Please see the AUTHORS file
2// for details. All rights reserved. Use of this source code is governed by a
3// BSD-style license that can be found in the LICENSE file.
4
5#ifndef RUNTIME_VM_COMPILER_BACKEND_LOOPS_H_
6#define RUNTIME_VM_COMPILER_BACKEND_LOOPS_H_
7
8#if defined(DART_PRECOMPILED_RUNTIME)
9#error "AOT runtime should not use compiler sources (including header files)"
10#endif // defined(DART_PRECOMPILED_RUNTIME)
11
12#include <utility>
13
14#include "vm/allocation.h"
15#include "vm/compiler/backend/il.h"
16
17namespace dart {
18
19// Information on an induction variable in a particular loop.
20//
21// Invariant:
22// offset + mult * def
23// Linear:
24// initial + next * i, for invariant initial and next,
25// and a "normalized" loop index i
26// Wrap-around:
27// initial then next, for invariant initial and any next
28// Periodic:
29// alternate initial and next, for invariant initial and next
30//
31class InductionVar : public ZoneAllocated {
32 public:
33 enum Kind {
34 kInvariant,
35 kLinear,
36 kWrapAround,
37 kPeriodic,
38 };
39
40 // Strict (exclusive) upper or lower bound on unit stride linear induction:
41 // i < U (i++)
42 // i > L (i--)
43 struct Bound {
44 Bound(BranchInstr* b, InductionVar* l) : branch_(b), limit_(l) {}
45 BranchInstr* branch_;
46 InductionVar* limit_;
47 };
48
49 // Constructor for an invariant.
50 InductionVar(int64_t offset, int64_t mult, Definition* def)
51 : kind_(kInvariant), offset_(offset), mult_(mult), def_(def), bounds_() {
52 ASSERT(mult_ == 0 || def != nullptr);
53 }
54
55 // Constructor for a constant.
56 explicit InductionVar(int64_t offset) : InductionVar(offset, 0, nullptr) {}
57
58 // Constructor for an induction.
59 InductionVar(Kind kind, InductionVar* initial, InductionVar* next)
60 : kind_(kind), initial_(initial), next_(next), bounds_() {
61 ASSERT(IsInvariant(initial));
62 switch (kind) {
63 case kLinear:
64 case kPeriodic:
65 ASSERT(IsInvariant(next));
66 break;
67 case kWrapAround:
68 ASSERT(next != nullptr);
69 break;
70 default:
71 UNREACHABLE();
72 }
73 }
74
75 // Returns true if the other induction is structually equivalent.
76 bool IsEqual(const InductionVar* other) const {
77 ASSERT(other != nullptr);
78 if (kind_ == other->kind_) {
79 switch (kind_) {
80 case kInvariant:
81 return offset_ == other->offset_ && mult_ == other->mult_ &&
82 (mult_ == 0 || def_ == other->def_);
83 case kLinear:
84 case kWrapAround:
85 case kPeriodic:
86 return initial_->IsEqual(other->initial_) &&
87 next_->IsEqual(other->next_);
88 }
89 }
90 return false;
91 }
92
93 // Returns true if a fixed difference between this and the other induction
94 // can be computed. Sets the output parameter diff on success.
95 bool CanComputeDifferenceWith(const InductionVar* other, int64_t* diff) const;
96
97 // Returns true if this induction in the given loop can be bounded as
98 // min <= this <= max by using bounds of more outer loops. On success
99 // the output parameters min and max are set, which are always loop
100 // invariant expressions inside the given loop.
101 bool CanComputeBounds(LoopInfo* loop,
102 Instruction* pos,
103 InductionVar** min,
104 InductionVar** max);
105
106 // Getters.
107 Kind kind() const { return kind_; }
108 int64_t offset() const {
109 ASSERT(kind_ == kInvariant);
110 return offset_;
111 }
112 int64_t mult() const {
113 ASSERT(kind_ == kInvariant);
114 return mult_;
115 }
116 Definition* def() const {
117 ASSERT(kind_ == kInvariant);
118 return def_;
119 }
120 InductionVar* initial() const {
121 ASSERT(kind_ != kInvariant);
122 return initial_;
123 }
124 InductionVar* next() const {
125 ASSERT(kind_ != kInvariant);
126 return next_;
127 }
128 const GrowableArray<Bound>& bounds() { return bounds_; }
129
130 // For debugging.
131 void PrintTo(BaseTextBuffer* f) const;
132 const char* ToCString() const;
133
134 // Returns true if x is invariant.
135 static bool IsInvariant(const InductionVar* x) {
136 return x != nullptr && x->kind_ == kInvariant;
137 }
138
139 // Returns true if x is a constant (and invariant).
140 static bool IsConstant(const InductionVar* x) {
141 return x != nullptr && x->kind_ == kInvariant && x->mult_ == 0;
142 }
143
144 // Returns true if x is a constant. Sets the value.
145 static bool IsConstant(const InductionVar* x, int64_t* c) {
146 if (IsConstant(x)) {
147 *c = x->offset_;
148 return true;
149 }
150 return false;
151 }
152
153 // Returns true if x is linear.
154 static bool IsLinear(const InductionVar* x) {
155 return x != nullptr && x->kind_ == kLinear;
156 }
157
158 // Returns true if x is linear with constant stride. Sets the stride.
159 static bool IsLinear(const InductionVar* x, int64_t* s) {
160 if (IsLinear(x)) {
161 return IsConstant(x->next_, s);
162 }
163 return false;
164 }
165
166 // Returns true if x is wrap-around.
167 static bool IsWrapAround(const InductionVar* x) {
168 return x != nullptr && x->kind_ == kWrapAround;
169 }
170
171 // Returns true if x is periodic.
172 static bool IsPeriodic(const InductionVar* x) {
173 return x != nullptr && x->kind_ == kPeriodic;
174 }
175
176 // Returns true if x is any induction.
177 static bool IsInduction(const InductionVar* x) {
178 return x != nullptr && x->kind_ != kInvariant;
179 }
180
181 private:
182 friend class InductionVarAnalysis;
183
184 // Induction classification.
185 const Kind kind_;
186 union {
187 struct {
188 int64_t offset_;
189 int64_t mult_;
190 Definition* def_;
191 };
192 struct {
193 InductionVar* initial_;
194 InductionVar* next_;
195 };
196 };
197
198 bool CanComputeBoundsImpl(LoopInfo* loop,
199 Instruction* pos,
200 InductionVar** min,
201 InductionVar** max);
202
203 // Bounds on induction.
204 GrowableArray<Bound> bounds_;
205
206 DISALLOW_COPY_AND_ASSIGN(InductionVar);
207};
208
209// Information on a "natural loop" in the flow graph.
210class LoopInfo : public ZoneAllocated {
211 public:
212 LoopInfo(intptr_t id, BlockEntryInstr* header, BitVector* blocks);
213
214 // Merges given blocks to this loop.
215 void AddBlocks(BitVector* blocks);
216
217 // Adds back edge to this loop.
218 void AddBackEdge(BlockEntryInstr* block);
219
220 // Returns true if given block is backedge of this loop.
221 bool IsBackEdge(BlockEntryInstr* block) const;
222
223 // Returns true if given block is alway taken in this loop.
224 bool IsAlwaysTaken(BlockEntryInstr* block) const;
225
226 // Returns true if given definition is a header phi for this loop.
227 bool IsHeaderPhi(Definition* def) const;
228
229 // Returns true if this loop is nested inside given loop.
230 bool IsIn(LoopInfo* loop) const;
231
232 // Returns true if this loop contains given block.
233 bool Contains(BlockEntryInstr* block) const;
234
235 // Returns the nesting depth of this loop.
236 intptr_t NestingDepth() const;
237
238 // Resets induction.
239 void ResetInduction();
240
241 // Assigns induction to a definition.
242 void AddInduction(Definition* def, InductionVar* induc);
243
244 // Looks up induction.
245 InductionVar* LookupInduction(Definition* def) const;
246
247 // Tests if index stays in [0,length) range in this loop at given position.
248 bool IsInRange(Instruction* pos, Value* index, Value* length);
249
250 // Getters.
251 intptr_t id() const { return id_; }
252 BlockEntryInstr* header() const { return header_; }
253 BitVector* blocks() const { return blocks_; }
254 const GrowableArray<BlockEntryInstr*>& back_edges() { return back_edges_; }
255 ConstraintInstr* limit() const { return limit_; }
256 InductionVar* control() const { return control_; }
257 LoopInfo* outer() const { return outer_; }
258 LoopInfo* inner() const { return inner_; }
259 LoopInfo* next() const { return next_; }
260
261 // For debugging.
262 void PrintTo(BaseTextBuffer* f) const;
263 const char* ToCString() const;
264
265 private:
266 friend class InductionVar;
267 friend class InductionVarAnalysis;
268 friend class LoopHierarchy;
269
270 // Mapping from definition to induction.
271 typedef RawPointerKeyValueTrait<Definition, InductionVar*> InductionKV;
272
273 // Mapping from induction to mapping from instruction to induction pair.
274 class MemoVal : public ZoneAllocated {
275 public:
276 typedef RawPointerKeyValueTrait<Instruction,
277 std::pair<InductionVar*, InductionVar*>>
278 PosKV;
279 MemoVal() : memo_() {}
280 DirectChainedHashMap<PosKV> memo_;
281 };
282 typedef RawPointerKeyValueTrait<InductionVar, MemoVal*> MemoKV;
283
284 // Unique id of loop. We use its index in the
285 // loop header array for this.
286 const intptr_t id_;
287
288 // Header of loop.
289 BlockEntryInstr* header_;
290
291 // Compact represention of every block in the loop,
292 // indexed by its "preorder_number".
293 BitVector* blocks_;
294
295 // Back edges of loop (usually one).
296 GrowableArray<BlockEntryInstr*> back_edges_;
297
298 // Map definition -> induction for this loop.
299 DirectChainedHashMap<InductionKV> induction_;
300
301 // A small, per-loop memoization cache, to avoid costly
302 // recomputations while traversing very deeply nested loops.
303 DirectChainedHashMap<MemoKV> memo_cache_;
304
305 // Constraint on a header phi.
306 // TODO(ajcbik): very specific to smi range analysis,
307 // should we really store it here?
308 ConstraintInstr* limit_;
309
310 // Control induction.
311 InductionVar* control_;
312
313 // Loop hierarchy.
314 LoopInfo* outer_;
315 LoopInfo* inner_;
316 LoopInfo* next_;
317
318 DISALLOW_COPY_AND_ASSIGN(LoopInfo);
319};
320
321// Information on the loop hierarchy in the flow graph.
322class LoopHierarchy : public ZoneAllocated {
323 public:
324 LoopHierarchy(ZoneGrowableArray<BlockEntryInstr*>* headers,
325 const GrowableArray<BlockEntryInstr*>& preorder);
326
327 // Getters.
328 const ZoneGrowableArray<BlockEntryInstr*>& headers() const {
329 return *headers_;
330 }
331 LoopInfo* top() const { return top_; }
332
333 // Returns total number of loops in the hierarchy.
334 intptr_t num_loops() const { return headers_->length(); }
335
336 // Performs induction variable analysis on all loops.
337 void ComputeInduction() const;
338
339 private:
340 void Build();
341 void Print(LoopInfo* loop) const;
342
343 ZoneGrowableArray<BlockEntryInstr*>* headers_;
344 const GrowableArray<BlockEntryInstr*>& preorder_;
345 LoopInfo* top_;
346
347 DISALLOW_COPY_AND_ASSIGN(LoopHierarchy);
348};
349
350} // namespace dart
351
352#endif // RUNTIME_VM_COMPILER_BACKEND_LOOPS_H_
353