Halide 22.0.0 Halide compiler and libraries

FunctionDAG.h
Go to the documentation of this file.
1/** This file defines the class FunctionDAG, which is our
2 * representation of a Halide pipeline, and contains methods to using
3 * Halide's bounds tools to query properties of it. */
4
5#ifndef FUNCTION_DAG_H
6#define FUNCTION_DAG_H
7
8#include <algorithm>
9#include <cstdint>
10#include <map>
11#include <string>
12#include <utility>
13#include <vector>
14
15#include "Featurization.h"
16#include "HalidePlugin.h"
17#include "PerfectHashMap.h"
18
19 namespace Halide {
20 namespace Internal {
21 namespace Autoscheduler {
22
23 using std::map;
24 using std::pair;
25 using std::string;
26 using std::unique_ptr;
27 using std::vector;
28
29// First we have various utility classes.
30
31// An optional rational type used when analyzing memory dependencies.
32 struct OptionalRational {
33 int32_t numerator = 0, denominator = 0;
34
35 bool exists() const {
36 return denominator != 0;
37 }
38
39 OptionalRational() = default;
40 OptionalRational(int64_t n, int64_t d)
41 : numerator(n),
42 denominator(d) {
43 }
44
45 void operator+=(const OptionalRational &other) {
46 if ((denominator & other.denominator) == 0) {
47 numerator = denominator = 0;
48 return;
49 }
50 if (denominator == other.denominator) {
51 numerator += other.numerator;
52 return;
53 }
54
55 int64_t l = lcm(denominator, other.denominator);
56 numerator *= l / denominator;
57 denominator = l;
58 numerator += other.numerator * (l / other.denominator);
59 int64_t g = gcd(numerator, denominator);
60 numerator /= g;
61 denominator /= g;
62 }
63
64 OptionalRational operator*(int64_t factor) const {
65 if ((*this) == 0) {
66 return *this;
67 }
68 int64_t num = numerator * factor;
69 return OptionalRational{num, denominator};
70 }
71
72 OptionalRational operator*(const OptionalRational &other) const {
73 if ((*this) == 0) {
74 return *this;
75 }
76 if (other == 0) {
77 return other;
78 }
79 int64_t num = numerator * other.numerator;
80 int64_t den = denominator * other.denominator;
81 return OptionalRational{num, den};
82 }
83
84 // Because this type is optional (exists may be false), we don't
85 // have a total ordering. These methods all return false when the
86 // operators are not comparable, so a < b is not the same as !(a
87 // >= b).
88 bool operator<(int x) const {
89 if (denominator == 0) {
90 return false;
91 } else if (denominator > 0) {
92 return numerator < x * denominator;
93 } else {
94 return numerator > x * denominator;
95 }
96 }
97
98 bool operator<=(int x) const {
99 if (denominator == 0) {
100 return false;
101 } else if (denominator > 0) {
102 return numerator <= x * denominator;
103 } else {
104 return numerator >= x * denominator;
105 }
106 }
107
108 bool operator>(int x) const {
109 if (!exists()) {
110 return false;
111 }
112 return !((*this) <= x);
113 }
114
115 bool operator>=(int x) const {
116 if (!exists()) {
117 return false;
118 }
119 return !((*this) < x);
120 }
121
122 bool operator==(int x) const {
123 return exists() && (numerator == (x * denominator));
124 }
125
126 bool operator==(const OptionalRational &other) const {
127 return (exists() == other.exists()) && (numerator * other.denominator == denominator * other.numerator);
128 }
129};
130
131// A LoadJacobian records the derivative of the coordinate accessed in
132// some producer w.r.t the loops of the consumer.
133 class LoadJacobian {
134 std::vector<OptionalRational> coeffs;
135 int64_t c;
136 size_t rows, cols;
137
138 public:
139 LoadJacobian(size_t producer_storage_dims, size_t consumer_loop_dims, int64_t count)
140 : c(count),
141 rows(producer_storage_dims),
142 cols(consumer_loop_dims) {
143 coeffs.resize(rows * cols);
144 }
145
146 bool all_coeffs_exist() const {
147 for (const auto &coeff : coeffs) {
148 if (!coeff.exists()) {
149 return false;
150 }
151 }
152 return true;
153 }
154
155 bool empty() const {
156 return rows == 0;
157 }
158
159 size_t producer_storage_dims() const {
160 return rows;
161 }
162
163 size_t consumer_loop_dims() const {
164 return cols;
165 }
166
167 bool is_constant() const {
168 for (const auto &c : coeffs) {
169 if (!c.exists() || !(c == 0)) {
170 return false;
171 }
172 }
173
174 return true;
175 }
176
177 OptionalRational operator()(int producer_storage_dim, int consumer_loop_dim) const {
178 if (producer_storage_dims() == 0 || consumer_loop_dims() == 0) {
179 // The producer or consumer is scalar, so all strides are zero.
180 return {0, 1};
181 }
182 return coeffs[producer_storage_dim * cols + consumer_loop_dim];
183 }
184
185 OptionalRational &operator()(int producer_storage_dim, int consumer_loop_dim) {
186 return coeffs[producer_storage_dim * cols + consumer_loop_dim];
187 }
188
189 // To avoid redundantly re-recording copies of the same
190 // load Jacobian, we keep a count of how many times a
191 // load with this Jacobian occurs.
192 int64_t count() const {
193 return c;
194 }
195
196 // Try to merge another LoadJacobian into this one, increasing the
197 // count if the coefficients match.
198 bool merge(const LoadJacobian &other) {
199 if (other.rows != rows || other.cols != cols) {
200 return false;
201 }
202 for (size_t i = 0; i < rows * cols; i++) {
203 if (!(other.coeffs[i] == coeffs[i])) {
204 return false;
205 }
206 }
207 c += other.count();
208 return true;
209 }
210
211 // Scale the matrix coefficients by the given factors
212 LoadJacobian operator*(const std::vector<int64_t> &factors) const {
213 LoadJacobian result(rows, cols, c);
214 for (size_t i = 0; i < producer_storage_dims(); i++) {
215 for (size_t j = 0; j < consumer_loop_dims(); j++) {
216 result(i, j) = (*this)(i, j) * factors[j];
217 }
218 }
219 return result;
220 }
221
222 // Multiply Jacobians, used to look at memory dependencies through
223 // inlined functions.
224 LoadJacobian operator*(const LoadJacobian &other) const {
225 LoadJacobian result(producer_storage_dims(), other.consumer_loop_dims(), count() * other.count());
226 for (size_t i = 0; i < producer_storage_dims(); i++) {
227 for (size_t j = 0; j < other.consumer_loop_dims(); j++) {
228 result(i, j) = OptionalRational{0, 1};
229 for (size_t k = 0; k < consumer_loop_dims(); k++) {
230 result(i, j) += (*this)(i, k) * other(k, j);
231 }
232 }
233 }
234 return result;
235 }
236
237 void dump(const char *prefix) const;
238};
239
240// Classes to represent a concrete set of bounds for a Func. A Span is
241// single-dimensional, and a Bound is a multi-dimensional box. For
242// each dimension we track the estimated size, and also whether or not
243// the size is known to be constant at compile-time. For each Func we
244// track three different types of bounds:
245
246// 1) The region required by consumers of the Func, which determines
247// 2) The region actually computed, which in turn determines
248// 3) The min and max of all loops in the loop next.
249
250// 3 in turn determines the region required of the inputs to a Func,
251// which determines their region computed, and hence their loop nest,
252// and so on back up the Function DAG from outputs back to inputs.
253
254 class Span {
255 int64_t min_, max_;
256 bool constant_extent_;
257
258 public:
259 int64_t min() const {
260 return min_;
261 }
262 int64_t max() const {
263 return max_;
264 }
265 int64_t extent() const {
266 return max_ - min_ + 1;
267 }
268 bool constant_extent() const {
269 return constant_extent_;
270 }
271
272 void union_with(const Span &other) {
273 min_ = std::min(min_, other.min());
274 max_ = std::max(max_, other.max());
275 constant_extent_ = constant_extent_ && other.constant_extent();
276 }
277
278 void set_extent(int64_t e) {
279 max_ = min_ + e - 1;
280 }
281
282 void translate(int64_t x) {
283 min_ += x;
284 max_ += x;
285 }
286
287 Span(int64_t a, int64_t b, bool c)
288 : min_(a),
289 max_(b),
290 constant_extent_(c) {
291 }
292 Span() = default;
293 Span(const Span &other) = default;
294 static Span empty_span() {
295 return Span(INT64_MAX, INT64_MIN, true);
296 }
297};
298
299// Bounds objects are created and destroyed very frequently while
300// exploring scheduling options, so we have a custom allocator and
301// memory pool. Much like IR nodes, we treat them as immutable once
302// created and wrapped in a Bound object so that they can be shared
303// safely across scheduling alternatives.
304 struct BoundContents {
305 mutable RefCount ref_count;
306
307 class Layout;
308 const Layout *layout = nullptr;
309
310 Span *data() const {
311 // This struct is a header
312 return (Span *)(const_cast<BoundContents *>(this) + 1);
313 }
314
315 Span &region_required(int i) {
316 return data()[i];
317 }
318
319 Span &region_computed(int i) {
320 return data()[i + layout->computed_offset];
321 }
322
323 Span &loops(int i, int j) {
324 return data()[j + layout->loop_offset[i]];
325 }
326
327 const Span &region_required(int i) const {
328 return data()[i];
329 }
330
331 const Span &region_computed(int i) const {
332 return data()[i + layout->computed_offset];
333 }
334
335 const Span &loops(int i, int j) const {
336 return data()[j + layout->loop_offset[i]];
337 }
338
339 BoundContents *make_copy() const {
340 auto *b = layout->make();
341 size_t bytes = sizeof(data()[0]) * layout->total_size;
342 memcpy(b->data(), data(), bytes);
343 return b;
344 }
345
346 void validate() const;
347
348 // We're frequently going to need to make these concrete bounds
349 // arrays. It makes things more efficient if we figure out the
350 // memory layout of those data structures once ahead of time, and
351 // make each individual instance just use that. Note that this is
352 // not thread-safe.
353 class Layout {
354 // A memory pool of free BoundContent objects with this layout
355 mutable std::vector<BoundContents *> pool;
356
357 // All the blocks of memory allocated
358 mutable std::vector<void *> blocks;
359
360 mutable size_t num_live = 0;
361
362 void allocate_some_more() const;
363
364 public:
365 // number of Span to allocate
366 int total_size;
367
368 // region_computed comes next at the following index
369 int computed_offset;
370
371 // the loop for each stage starts at the following index
372 std::vector<int> loop_offset;
373
374 Layout() = default;
375 ~Layout();
376
377 Layout(const Layout &) = delete;
378 void operator=(const Layout &) = delete;
379 Layout(Layout &&) = delete;
380 void operator=(Layout &&) = delete;
381
382 // Make a BoundContents object with this layout
383 BoundContents *make() const;
384
385 // Release a BoundContents object with this layout back to the pool
386 void release(const BoundContents *b) const;
387 };
388};
389
390 using Bound = IntrusivePtr<const BoundContents>;
391
392// A representation of the function DAG. The nodes and edges are both
393// in reverse realization order, so if you want to walk backwards up
394// the DAG, just iterate the nodes or edges in-order.
395 struct FunctionDAG {
396
397 // An edge is a producer-consumer relationship
398 struct Edge;
399
400 struct SymbolicInterval {
401 Halide::Var min;
402 Halide::Var max;
403 };
404
405 // A Node represents a single Func
406 struct Node {
407 // A pointer back to the owning DAG
408 FunctionDAG *dag;
409
410 // The Halide Func this represents
411 Function func;
412
413 // The number of bytes per point stored.
414 double bytes_per_point;
415
416 // The min/max variables used to denote a symbolic region of
417 // this Func. Used in the cost above, and in the Edges below.
418 vector<SymbolicInterval> region_required;
419
420 // A concrete region required from a bounds estimate. Only
421 // defined for outputs.
422 vector<Span> estimated_region_required;
423
424 // The region computed of a Func, in terms of the region
425 // required. For simple Funcs this is identical to the
426 // region_required. However, in some Funcs computing one
427 // output requires computing other outputs too. You can't
428 // really ask for a single output pixel from something blurred
429 // with an IIR without computing the others, for example.
430 struct RegionComputedInfo {
431 // The min and max in their full symbolic glory. We use
432 // these in the general case.
433 Interval in;
434
435 // Analysis used to accelerate common cases
436 bool equals_required = false, equals_union_of_required_with_constants = false;
437 int64_t c_min = 0, c_max = 0;
438 };
439 vector<RegionComputedInfo> region_computed;
440 bool region_computed_all_common_cases = false;
441
442 // Expand a region required into a region computed, using the
443 // symbolic intervals above.
444 void required_to_computed(const Span *required, Span *computed) const;
445
446 // Metadata about one symbolic loop in a Func's default loop nest.
447 struct Loop {
448 string var;
449 bool pure, rvar;
450 Expr min, max;
451
452 // Which pure dimension does this loop correspond to? Invalid if it's an rvar
453 int pure_dim;
454
455 // Precomputed metadata to accelerate common cases:
456
457 // If true, the loop bounds are just the region computed in the given dimension
458 bool equals_region_computed = false;
459 int region_computed_dim = 0;
460
461 // If true, the loop bounds are a constant with the given min and max
462 bool bounds_are_constant = false;
463 int64_t c_min = 0, c_max = 0;
464
465 // A persistent fragment of source for getting this Var
466 // from its owner Func. Used for printing source code
467 // equivalent to a computed schedule.
468 string accessor;
469 };
470
471 // Get the loop nest shape as a function of the region computed
472 void loop_nest_for_region(int stage_idx, const Span *computed, Span *loop) const;
473
474 // One stage of a Func
475 struct Stage {
476 // The owning Node
477 Node *node;
478
479 // Which stage of the Func is this. 0 = pure.
480 int index;
481
482 // The loop nest that computes this stage, from innermost out.
483 vector<Loop> loop;
484 bool loop_nest_all_common_cases = false;
485
486 // The vectorization width that will be used for
487 // compute. Corresponds to the natural width for the
488 // narrowest type used.
489 int vector_size;
490
491 // The featurization of the compute done
492 PipelineFeatures features;
493
494 // The actual Halide front-end stage object
495 Halide::Stage stage;
496
497 // The name for scheduling (e.g. "foo.update(3)")
498 string name;
499
500 string sanitized_name;
501
502 // Ids for perfect hashing on stages.
503 int id, max_id;
504
505 std::unique_ptr<LoadJacobian> store_jacobian;
506
507 vector<Edge *> incoming_edges;
508
509 vector<bool> dependencies;
510 bool downstream_of(const Node &n) const {
511 return dependencies[n.id];
512 };
513
514 explicit Stage(Halide::Stage s)
515 : stage(std::move(s)) {
516 }
517
518 int get_loop_index_from_var(const std::string &var) const {
519 int i = 0;
520 for (const auto &l : loop) {
521 if (l.var == var) {
522 return i;
523 }
524
525 ++i;
526 }
527
528 return -1;
529 }
530 };
531 vector<Stage> stages;
532
533 vector<Edge *> outgoing_edges;
534
535 // Max vector size across the stages
536 int vector_size;
537
538 // A unique ID for this node, allocated consecutively starting
539 // at zero for each pipeline.
540 int id, max_id;
541
542 // Just func->dimensions(), but we ask for it so many times
543 // that's it's worth avoiding the function call into
544 // libHalide.
545 int dimensions;
546
547 // Is a single pointwise call to another Func
548 bool is_wrapper;
549
550 // We represent the input buffers as node, though we do not attempt to schedule them.
551 bool is_input;
552
553 // Is one of the pipeline outputs
554 bool is_output;
555
556 // Only uses pointwise calls
557 bool is_pointwise;
558
559 // Only uses pointwise calls + clamping on all indices
560 bool is_boundary_condition;
561
562 std::unique_ptr<BoundContents::Layout> bounds_memory_layout;
563
564 BoundContents *make_bound() const {
565 return bounds_memory_layout->make();
566 }
567 };
568
569 // A representation of a producer-consumer relationship
570 struct Edge {
571 struct BoundInfo {
572 // The symbolic expression for the bound in this dimension
573 Expr expr;
574
575 // Fields below are the results of additional analysis
576 // used to evaluate this bound more quickly.
577 int64_t coeff, constant;
578 int64_t consumer_dim;
579 bool affine, uses_max;
580
581 BoundInfo(const Expr &e, const Node::Stage &consumer);
582 };
583
584 // Memory footprint on producer required by consumer.
585 vector<pair<BoundInfo, BoundInfo>> bounds;
586
587 FunctionDAG::Node *producer;
588 FunctionDAG::Node::Stage *consumer;
589
590 // The number of calls the consumer makes to the producer, per
591 // point in the loop nest of the consumer.
592 int calls;
593
594 bool all_bounds_affine;
595
596 vector<LoadJacobian> load_jacobians;
597
598 bool all_load_jacobian_coeffs_exist() const;
599
600 void add_load_jacobian(LoadJacobian j1);
601
602 // Given a loop nest of the consumer stage, expand a region
603 // required of the producer to be large enough to include all
604 // points required.
605 void expand_footprint(const Span *consumer_loop, Span *producer_required) const;
606 };
607
608 vector<Node> nodes;
609 vector<Edge> edges;
610
611 int num_non_input_nodes{0};
612
613 // We're going to be querying this DAG a lot while searching for
614 // an optimal schedule, so we'll also create a variety of
615 // auxiliary data structures.
616 map<int, const Node *> stage_id_to_node_map;
617
618 // Create the function DAG, and do all the dependency and cost
619 // analysis. This is done once up-front before the tree search.
620 FunctionDAG(const vector<Function> &outputs, const Target &target);
621
622 void dump() const;
623 std::ostream &dump(std::ostream &os) const;
624
625 // This class uses a lot of internal pointers, so we'll hide the copy constructor.
626 FunctionDAG(const FunctionDAG &other) = delete;
627 void operator=(const FunctionDAG &other) = delete;
628
629 private:
630 // Compute the featurization for the entire DAG
631 void featurize();
632
633 template<typename OS>
634 void dump_internal(OS &os) const;
635};
636
637 template<typename T>
638 using NodeMap = PerfectHashMap<FunctionDAG::Node, T>;
639
640 class ExprBranching : public VariadicVisitor<ExprBranching, int, int> {
641 using Super = VariadicVisitor<ExprBranching, int, int>;
642
643 private:
644 const NodeMap<int64_t> &inlined;
645
646 public:
647 int visit(const Reinterpret *op);
648 int visit(const IntImm *op);
649 int visit(const UIntImm *op);
650 int visit(const FloatImm *op);
651 int visit(const StringImm *op);
652 int visit(const Broadcast *op);
653 int visit(const Cast *op);
654 int visit(const Variable *op);
655 int visit(const Add *op);
656 int visit(const Sub *op);
657 int visit(const Mul *op);
658 int visit(const Div *op);
659 int visit(const Mod *op);
660 int visit(const Min *op);
661 int visit(const Max *op);
662 int visit(const EQ *op);
663 int visit(const NE *op);
664 int visit(const LT *op);
665 int visit(const LE *op);
666 int visit(const GT *op);
667 int visit(const GE *op);
668 int visit(const And *op);
669 int visit(const Or *op);
670 int visit(const Not *op);
671 int visit(const Select *op);
672 int visit(const Ramp *op);
673 int visit(const Load *op);
674 int visit(const Call *op);
675 int visit(const Shuffle *op);
676 int visit(const Let *op);
677 int visit(const VectorReduce *op);
678 int visit_binary(const Expr &a, const Expr &b);
679 int visit_nary(const std::vector<Expr> &exprs);
680
681 explicit ExprBranching(const NodeMap<int64_t> &inlined)
682 : inlined{inlined} {
683 }
684
685 int compute(const Function &f);
686};
687
688 void sanitize_names(std::string &str);
689
690} // namespace Autoscheduler
691} // namespace Internal
692} // namespace Halide
693
694#endif // FUNCTION_DAG_H
HalidePlugin.h
PerfectHashMap.h
Featurization.h
Halide::Internal::Autoscheduler::BoundContents::Layout
Definition: FunctionDAG.h:323
Halide::Internal::Autoscheduler::BoundContents::Layout::~Layout
~Layout()
Halide::Internal::Autoscheduler::BoundContents::Layout::release
void release(const BoundContents *b) const
Halide::Internal::Autoscheduler::BoundContents::Layout::Layout
Layout(Layout &&)=delete
Halide::Internal::Autoscheduler::BoundContents::Layout::operator=
void operator=(Layout &&)=delete
Halide::Internal::Autoscheduler::BoundContents::Layout::computed_offset
int computed_offset
Definition: FunctionDAG.h:341
Halide::Internal::Autoscheduler::BoundContents::Layout::Layout
Layout()=default
Halide::Internal::Autoscheduler::BoundContents::Layout::Layout
Layout(const Layout &)=delete
Halide::Internal::Autoscheduler::BoundContents::Layout::loop_offset
std::vector< int > loop_offset
Definition: FunctionDAG.h:344
Halide::Internal::Autoscheduler::BoundContents::Layout::make
BoundContents * make() const
Halide::Internal::Autoscheduler::BoundContents::Layout::total_size
int total_size
Definition: FunctionDAG.h:336
Halide::Internal::Autoscheduler::BoundContents::Layout::operator=
void operator=(const Layout &)=delete
Halide::Internal::Autoscheduler::ExprBranching
Definition: FunctionDAG.h:640
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const VectorReduce *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const StringImm *op)
Halide::Internal::Autoscheduler::ExprBranching::visit_binary
int visit_binary(const Expr &a, const Expr &b)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Sub *op)
Halide::Internal::Autoscheduler::ExprBranching::ExprBranching
ExprBranching(const NodeMap< int64_t > &inlined)
Definition: FunctionDAG.h:681
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const IntImm *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Select *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Mul *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Shuffle *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Load *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const EQ *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Add *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Cast *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Or *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Not *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Let *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Broadcast *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Max *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Reinterpret *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const NE *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Mod *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Call *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Div *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const LE *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const UIntImm *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Ramp *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const GE *op)
Halide::Internal::Autoscheduler::ExprBranching::visit_nary
int visit_nary(const std::vector< Expr > &exprs)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const And *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const LT *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Min *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const Variable *op)
Halide::Internal::Autoscheduler::ExprBranching::compute
int compute(const Function &f)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const FloatImm *op)
Halide::Internal::Autoscheduler::ExprBranching::visit
int visit(const GT *op)
Halide::Internal::Autoscheduler::LoadJacobian
Definition: FunctionDAG.h:126
Halide::Internal::Autoscheduler::LoadJacobian::operator()
OptionalRational operator()(int producer_storage_dim, int consumer_loop_dim) const
Definition: FunctionDAG.h:177
Halide::Internal::Autoscheduler::LoadJacobian::operator*
LoadJacobian operator*(const LoadJacobian &other) const
Definition: FunctionDAG.h:224
Halide::Internal::Autoscheduler::LoadJacobian::consumer_loop_dims
size_t consumer_loop_dims() const
Definition: FunctionDAG.h:139
Halide::Internal::Autoscheduler::LoadJacobian::LoadJacobian
LoadJacobian(size_t producer_storage_dims, size_t consumer_loop_dims, int64_t count)
Definition: FunctionDAG.h:139
Halide::Internal::Autoscheduler::LoadJacobian::operator()
OptionalRational & operator()(int producer_storage_dim, int consumer_loop_dim)
Definition: FunctionDAG.h:185
Halide::Internal::Autoscheduler::LoadJacobian::count
int64_t count() const
Definition: FunctionDAG.h:166
Halide::Internal::Autoscheduler::LoadJacobian::merge
bool merge(const LoadJacobian &other)
Definition: FunctionDAG.h:198
Halide::Internal::Autoscheduler::LoadJacobian::is_constant
bool is_constant() const
Definition: FunctionDAG.h:167
Halide::Internal::Autoscheduler::LoadJacobian::empty
bool empty() const
Definition: FunctionDAG.h:155
Halide::Internal::Autoscheduler::LoadJacobian::dump
void dump(const char *prefix) const
Halide::Internal::Autoscheduler::LoadJacobian::producer_storage_dims
size_t producer_storage_dims() const
Definition: FunctionDAG.h:135
Halide::Internal::Autoscheduler::LoadJacobian::all_coeffs_exist
bool all_coeffs_exist() const
Definition: FunctionDAG.h:146
Halide::Internal::Autoscheduler::LoadJacobian::operator*
LoadJacobian operator*(const std::vector< int64_t > &factors) const
Definition: FunctionDAG.h:212
Halide::Internal::Autoscheduler::Span
Definition: FunctionDAG.h:226
Halide::Internal::Autoscheduler::Span::max
int64_t max() const
Definition: FunctionDAG.h:262
Halide::Internal::Autoscheduler::Span::constant_extent
bool constant_extent() const
Definition: FunctionDAG.h:268
Halide::Internal::Autoscheduler::Span::Span
Span()=default
Halide::Internal::Autoscheduler::Span::set_extent
void set_extent(int64_t e)
Definition: FunctionDAG.h:278
Halide::Internal::Autoscheduler::Span::extent
int64_t extent() const
Definition: FunctionDAG.h:265
Halide::Internal::Autoscheduler::Span::Span
Span(int64_t a, int64_t b, bool c)
Definition: FunctionDAG.h:287
Halide::Internal::Autoscheduler::Span::translate
void translate(int64_t x)
Definition: FunctionDAG.h:282
Halide::Internal::Autoscheduler::Span::min
int64_t min() const
Definition: FunctionDAG.h:259
Halide::Internal::Autoscheduler::Span::empty_span
static Span empty_span()
Definition: FunctionDAG.h:294
Halide::Internal::Autoscheduler::Span::Span
Span(const Span &other)=default
Halide::Internal::Autoscheduler::Span::union_with
void union_with(const Span &other)
Definition: FunctionDAG.h:272
Halide::Internal::Function
A reference-counted handle to Halide's internal representation of a function.
Definition: Function.h:39
Halide::Internal::RefCount
A class representing a reference count to be used with IntrusivePtr.
Definition: IntrusivePtr.h:19
Halide::Internal::VariadicVisitor
A visitor/mutator capable of passing arbitrary arguments to the visit methods using CRTP and returnin...
Definition: IRVisitor.h:342
Halide::Stage
A single definition of a Func.
Definition: Func.h:70
Halide::Var
A Halide variable, to be used when defining functions.
Definition: Var.h:19
PerfectHashMap
Definition: PerfectHashMap.h:38
Halide::Internal::Autoscheduler::sanitize_names
void sanitize_names(std::string &str)
Halide::Internal::gcd
int64_t gcd(int64_t, int64_t)
The greatest common divisor of two integers.
Halide::Internal::min
ConstantInterval min(const ConstantInterval &a, const ConstantInterval &b)
Halide::Internal::max
ConstantInterval max(const ConstantInterval &a, const ConstantInterval &b)
Halide::Internal::lcm
int64_t lcm(int64_t, int64_t)
The least common multiple of two integers.
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AbstractGenerator.h:19
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
int64_t
signed __INT64_TYPE__ int64_t
Definition: runtime_internal.h:22
int32_t
signed __INT32_TYPE__ int32_t
Definition: runtime_internal.h:24
memcpy
void * memcpy(void *s1, const void *s2, size_t n)
Halide::Expr
A fragment of Halide syntax.
Definition: Expr.h:258
Halide::Internal::Add
The sum of two expressions.
Definition: IR.h:66
Halide::Internal::And
Logical and - are both expressions true.
Definition: IR.h:185
Halide::Internal::Autoscheduler::BoundContents
Definition: FunctionDAG.h:274
Halide::Internal::Autoscheduler::BoundContents::region_computed
Span & region_computed(int i)
Definition: FunctionDAG.h:319
Halide::Internal::Autoscheduler::BoundContents::region_required
Span & region_required(int i)
Definition: FunctionDAG.h:315
Halide::Internal::Autoscheduler::BoundContents::data
Span * data() const
Definition: FunctionDAG.h:310
Halide::Internal::Autoscheduler::BoundContents::loops
Span & loops(int i, int j)
Definition: FunctionDAG.h:323
Halide::Internal::Autoscheduler::BoundContents::validate
void validate() const
Halide::Internal::Autoscheduler::BoundContents::make_copy
BoundContents * make_copy() const
Definition: FunctionDAG.h:339
Halide::Internal::Autoscheduler::BoundContents::layout
const Layout * layout
Definition: FunctionDAG.h:278
Halide::Internal::Autoscheduler::BoundContents::region_required
const Span & region_required(int i) const
Definition: FunctionDAG.h:327
Halide::Internal::Autoscheduler::BoundContents::region_computed
const Span & region_computed(int i) const
Definition: FunctionDAG.h:331
Halide::Internal::Autoscheduler::BoundContents::ref_count
RefCount ref_count
Definition: FunctionDAG.h:275
Halide::Internal::Autoscheduler::BoundContents::loops
const Span & loops(int i, int j) const
Definition: FunctionDAG.h:335
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::BoundInfo
BoundInfo(const Expr &e, const Node::Stage &consumer)
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::affine
bool affine
Definition: FunctionDAG.h:535
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::uses_max
bool uses_max
Definition: FunctionDAG.h:535
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::consumer_dim
int64_t consumer_dim
Definition: FunctionDAG.h:534
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::coeff
int64_t coeff
Definition: FunctionDAG.h:533
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::constant
int64_t constant
Definition: FunctionDAG.h:533
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::expr
Expr expr
Definition: FunctionDAG.h:529
Halide::Internal::Autoscheduler::FunctionDAG::Edge::producer
FunctionDAG::Node * producer
Definition: FunctionDAG.h:543
Halide::Internal::Autoscheduler::FunctionDAG::Edge::load_jacobians
vector< LoadJacobian > load_jacobians
Definition: FunctionDAG.h:552
Halide::Internal::Autoscheduler::FunctionDAG::Edge::calls
int calls
Definition: FunctionDAG.h:548
Halide::Internal::Autoscheduler::FunctionDAG::Edge::expand_footprint
void expand_footprint(const Span *consumer_loop, Span *producer_required) const
Halide::Internal::Autoscheduler::FunctionDAG::Edge::add_load_jacobian
void add_load_jacobian(LoadJacobian j1)
Halide::Internal::Autoscheduler::FunctionDAG::Edge::consumer
FunctionDAG::Node::Stage * consumer
Definition: FunctionDAG.h:544
Halide::Internal::Autoscheduler::FunctionDAG::Edge::all_bounds_affine
bool all_bounds_affine
Definition: FunctionDAG.h:550
Halide::Internal::Autoscheduler::FunctionDAG::Edge::bounds
vector< pair< BoundInfo, BoundInfo > > bounds
Definition: FunctionDAG.h:541
Halide::Internal::Autoscheduler::FunctionDAG::Edge::all_load_jacobian_coeffs_exist
bool all_load_jacobian_coeffs_exist() const
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop
Definition: FunctionDAG.h:420
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::min
Expr min
Definition: FunctionDAG.h:423
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::pure_dim
int pure_dim
Definition: FunctionDAG.h:426
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::c_max
int64_t c_max
Definition: FunctionDAG.h:436
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::region_computed_dim
int region_computed_dim
Definition: FunctionDAG.h:432
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::rvar
bool rvar
Definition: FunctionDAG.h:422
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::pure
bool pure
Definition: FunctionDAG.h:422
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::var
string var
Definition: FunctionDAG.h:421
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::max
Expr max
Definition: FunctionDAG.h:423
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::accessor
string accessor
Definition: FunctionDAG.h:441
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::equals_region_computed
bool equals_region_computed
Definition: FunctionDAG.h:431
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::c_min
int64_t c_min
Definition: FunctionDAG.h:436
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::bounds_are_constant
bool bounds_are_constant
Definition: FunctionDAG.h:435
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo::in
Interval in
Definition: FunctionDAG.h:405
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo::c_max
int64_t c_max
Definition: FunctionDAG.h:410
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo::c_min
int64_t c_min
Definition: FunctionDAG.h:410
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo::equals_union_of_required_with_constants
bool equals_union_of_required_with_constants
Definition: FunctionDAG.h:409
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo::equals_required
bool equals_required
Definition: FunctionDAG.h:409
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage
Definition: FunctionDAG.h:448
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::index
int index
Definition: FunctionDAG.h:453
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::Stage
Stage(Halide::Stage s)
Definition: FunctionDAG.h:514
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::features
PipelineFeatures features
Definition: FunctionDAG.h:465
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::id
int id
Definition: FunctionDAG.h:474
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::store_jacobian
std::unique_ptr< LoadJacobian > store_jacobian
Definition: FunctionDAG.h:505
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::loop_nest_all_common_cases
bool loop_nest_all_common_cases
Definition: FunctionDAG.h:457
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::loop
vector< Loop > loop
Definition: FunctionDAG.h:456
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::max_id
int max_id
Definition: FunctionDAG.h:474
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::downstream_of
bool downstream_of(const Node &n) const
Definition: FunctionDAG.h:510
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::vector_size
int vector_size
Definition: FunctionDAG.h:462
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::sanitized_name
string sanitized_name
Definition: FunctionDAG.h:500
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::node
Node * node
Definition: FunctionDAG.h:450
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::name
string name
Definition: FunctionDAG.h:471
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::dependencies
vector< bool > dependencies
Definition: FunctionDAG.h:478
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::get_loop_index_from_var
int get_loop_index_from_var(const std::string &var) const
Definition: FunctionDAG.h:518
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::stage
Halide::Stage stage
Definition: FunctionDAG.h:468
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::incoming_edges
vector< Edge * > incoming_edges
Definition: FunctionDAG.h:476
Halide::Internal::Autoscheduler::FunctionDAG::Node
Definition: FunctionDAG.h:378
Halide::Internal::Autoscheduler::FunctionDAG::Node::id
int id
Definition: FunctionDAG.h:496
Halide::Internal::Autoscheduler::FunctionDAG::Node::outgoing_edges
vector< Edge * > outgoing_edges
Definition: FunctionDAG.h:489
Halide::Internal::Autoscheduler::FunctionDAG::Node::make_bound
BoundContents * make_bound() const
Definition: FunctionDAG.h:564
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_input
bool is_input
Definition: FunctionDAG.h:507
Halide::Internal::Autoscheduler::FunctionDAG::Node::region_required
vector< SymbolicInterval > region_required
Definition: FunctionDAG.h:390
Halide::Internal::Autoscheduler::FunctionDAG::Node::func
Function func
Definition: FunctionDAG.h:383
Halide::Internal::Autoscheduler::FunctionDAG::Node::loop_nest_for_region
void loop_nest_for_region(int stage_idx, const Span *computed, Span *loop) const
Halide::Internal::Autoscheduler::FunctionDAG::Node::dimensions
int dimensions
Definition: FunctionDAG.h:501
Halide::Internal::Autoscheduler::FunctionDAG::Node::dag
FunctionDAG * dag
Definition: FunctionDAG.h:380
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_boundary_condition
bool is_boundary_condition
Definition: FunctionDAG.h:516
Halide::Internal::Autoscheduler::FunctionDAG::Node::region_computed
vector< RegionComputedInfo > region_computed
Definition: FunctionDAG.h:412
Halide::Internal::Autoscheduler::FunctionDAG::Node::region_computed_all_common_cases
bool region_computed_all_common_cases
Definition: FunctionDAG.h:413
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_wrapper
bool is_wrapper
Definition: FunctionDAG.h:504
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_pointwise
bool is_pointwise
Definition: FunctionDAG.h:513
Halide::Internal::Autoscheduler::FunctionDAG::Node::max_id
int max_id
Definition: FunctionDAG.h:496
Halide::Internal::Autoscheduler::FunctionDAG::Node::estimated_region_required
vector< Span > estimated_region_required
Definition: FunctionDAG.h:394
Halide::Internal::Autoscheduler::FunctionDAG::Node::stages
vector< Stage > stages
Definition: FunctionDAG.h:487
Halide::Internal::Autoscheduler::FunctionDAG::Node::bytes_per_point
double bytes_per_point
Definition: FunctionDAG.h:386
Halide::Internal::Autoscheduler::FunctionDAG::Node::vector_size
int vector_size
Definition: FunctionDAG.h:492
Halide::Internal::Autoscheduler::FunctionDAG::Node::bounds_memory_layout
std::unique_ptr< BoundContents::Layout > bounds_memory_layout
Definition: FunctionDAG.h:518
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_output
bool is_output
Definition: FunctionDAG.h:510
Halide::Internal::Autoscheduler::FunctionDAG::Node::required_to_computed
void required_to_computed(const Span *required, Span *computed) const
Halide::Internal::Autoscheduler::FunctionDAG::SymbolicInterval::max
Halide::Var max
Definition: FunctionDAG.h:374
Halide::Internal::Autoscheduler::FunctionDAG::SymbolicInterval::min
Halide::Var min
Definition: FunctionDAG.h:373
Halide::Internal::Autoscheduler::FunctionDAG
Definition: FunctionDAG.h:367
Halide::Internal::Autoscheduler::FunctionDAG::num_non_input_nodes
int num_non_input_nodes
Definition: FunctionDAG.h:611
Halide::Internal::Autoscheduler::FunctionDAG::nodes
vector< Node > nodes
Definition: FunctionDAG.h:562
Halide::Internal::Autoscheduler::FunctionDAG::operator=
void operator=(const FunctionDAG &other)=delete
Halide::Internal::Autoscheduler::FunctionDAG::FunctionDAG
FunctionDAG(const FunctionDAG &other)=delete
Halide::Internal::Autoscheduler::FunctionDAG::stage_id_to_node_map
map< int, const Node * > stage_id_to_node_map
Definition: FunctionDAG.h:616
Halide::Internal::Autoscheduler::FunctionDAG::dump
std::ostream & dump(std::ostream &os) const
Halide::Internal::Autoscheduler::FunctionDAG::dump
void dump() const
Halide::Internal::Autoscheduler::FunctionDAG::FunctionDAG
FunctionDAG(const vector< Function > &outputs, const Target &target)
Halide::Internal::Autoscheduler::FunctionDAG::edges
vector< Edge > edges
Definition: FunctionDAG.h:563
Halide::Internal::Autoscheduler::OptionalRational
Definition: FunctionDAG.h:34
Halide::Internal::Autoscheduler::OptionalRational::operator+=
void operator+=(const OptionalRational &other)
Definition: FunctionDAG.h:45
Halide::Internal::Autoscheduler::OptionalRational::numerator
int64_t numerator
Definition: FunctionDAG.h:36
Halide::Internal::Autoscheduler::OptionalRational::operator>=
bool operator>=(int x) const
Definition: FunctionDAG.h:115
Halide::Internal::Autoscheduler::OptionalRational::operator==
bool operator==(const OptionalRational &other) const
Definition: FunctionDAG.h:126
Halide::Internal::Autoscheduler::OptionalRational::operator>
bool operator>(int x) const
Definition: FunctionDAG.h:108
Halide::Internal::Autoscheduler::OptionalRational::OptionalRational
OptionalRational()=default
Halide::Internal::Autoscheduler::OptionalRational::denominator
int64_t denominator
Definition: FunctionDAG.h:36
Halide::Internal::Autoscheduler::OptionalRational::operator*
OptionalRational operator*(int64_t factor) const
Definition: FunctionDAG.h:64
Halide::Internal::Autoscheduler::OptionalRational::OptionalRational
OptionalRational(int64_t n, int64_t d)
Definition: FunctionDAG.h:40
Halide::Internal::Autoscheduler::OptionalRational::operator*
OptionalRational operator*(const OptionalRational &other) const
Definition: FunctionDAG.h:72
Halide::Internal::Autoscheduler::OptionalRational::exists
bool exists() const
Definition: FunctionDAG.h:35
Halide::Internal::Autoscheduler::OptionalRational::operator==
bool operator==(int x) const
Definition: FunctionDAG.h:122
Halide::Internal::Autoscheduler::OptionalRational::operator<
bool operator<(int x) const
Definition: FunctionDAG.h:88
Halide::Internal::Autoscheduler::OptionalRational::operator<=
bool operator<=(int x) const
Definition: FunctionDAG.h:98
Halide::Internal::Autoscheduler::OptionalRational::exists
bool exists
Definition: FunctionDAG.h:35
Halide::Internal::Broadcast
A vector with 'lanes' elements, in which every element is 'value'.
Definition: IR.h:269
Halide::Internal::Call
A function call.
Definition: IR.h:500
Halide::Internal::Cast
The actual IR nodes begin here.
Definition: IR.h:40
Halide::Internal::Div
The ratio of two expressions.
Definition: IR.h:93
Halide::Internal::EQ
Is the first expression equal to the second.
Definition: IR.h:131
Halide::Internal::FloatImm
Floating point constants.
Definition: Expr.h:236
Halide::Internal::GE
Is the first expression greater than or equal to the second.
Definition: IR.h:176
Halide::Internal::GT
Is the first expression greater than the second.
Definition: IR.h:167
Halide::Internal::IntImm
Integer constants.
Definition: Expr.h:218
Halide::Internal::Interval
A class to represent ranges of Exprs.
Definition: Interval.h:14
Halide::Internal::IntrusivePtr
Intrusive shared pointers have a reference count (a RefCount object) stored in the class itself.
Definition: IntrusivePtr.h:71
Halide::Internal::LE
Is the first expression less than or equal to the second.
Definition: IR.h:158
Halide::Internal::LT
Is the first expression less than the second.
Definition: IR.h:149
Halide::Internal::Let
A let expression, like you might find in a functional language.
Definition: IR.h:281
Halide::Internal::Load
Load a value from a named symbol if predicate is true.
Definition: IR.h:227
Halide::Internal::Max
The greater of two values.
Definition: IR.h:122
Halide::Internal::Min
The lesser of two values.
Definition: IR.h:113
Halide::Internal::Mod
The remainder of a / b.
Definition: IR.h:104
Halide::Internal::Mul
The product of two expressions.
Definition: IR.h:84
Halide::Internal::NE
Is the first expression not equal to the second.
Definition: IR.h:140
Halide::Internal::Not
Logical not - true if the expression false.
Definition: IR.h:203
Halide::Internal::Or
Logical or - is at least one of the expression true.
Definition: IR.h:194
Halide::Internal::PipelineFeatures
Definition: Featurization.h:13
Halide::Internal::Ramp
A linear ramp vector node.
Definition: IR.h:257
Halide::Internal::Reinterpret
Reinterpret value as another type, without affecting any of the bits (on little-endian systems).
Definition: IR.h:57
Halide::Internal::Select
A ternary operator.
Definition: IR.h:214
Halide::Internal::Shuffle
Construct a new vector by taking elements from another sequence of vectors.
Definition: IR.h:894
Halide::Internal::StringImm
String constants.
Definition: Expr.h:245
Halide::Internal::Sub
The difference of two expressions.
Definition: IR.h:75
Halide::Internal::UIntImm
Unsigned integer constants.
Definition: Expr.h:227
Halide::Internal::Variable
A named variable.
Definition: IR.h:811
Halide::Internal::VectorReduce
Horizontally reduce a vector to a scalar or narrower vector using the given commutative and associati...
Definition: IR.h:1022
Halide::Target
A struct representing a target machine and os to generate code for.
Definition: Target.h:19