Halide
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 <map>
10 #include <stdint.h>
11 #include <string>
12 #include <vector>
13 
14 #include "Errors.h"
15 #include "Featurization.h"
16 #include "Halide.h"
17 
18 namespace Halide {
19 namespace Internal {
20 namespace Autoscheduler {
21 
22 using std::map;
23 using std::pair;
24 using std::string;
25 using std::unique_ptr;
26 using std::vector;
27 
28 // First we have various utility classes.
29 
30 // An optional rational type used when analyzing memory dependencies.
32  bool exists = false;
34 
35  OptionalRational() = default;
37  : exists(e), numerator(n), denominator(d) {
38  }
39 
40  void operator+=(const OptionalRational &other) {
41  if (!exists || !other.exists) {
42  exists = false;
43  return;
44  }
45  if (denominator == other.denominator) {
46  numerator += other.numerator;
47  return;
48  }
49 
50  int64_t l = lcm(denominator, other.denominator);
51  numerator *= l / denominator;
52  denominator = l;
53  numerator += other.numerator * (l / other.denominator);
55  numerator /= g;
56  denominator /= g;
57  }
58 
60  if ((*this) == 0) return *this;
61  if (other == 0) return other;
62  int64_t num = numerator * other.numerator;
63  int64_t den = denominator * other.denominator;
64  bool e = exists && other.exists;
65  return OptionalRational{e, num, den};
66  }
67 
68  // Because this type is optional (exists may be false), we don't
69  // have a total ordering. These methods all return false when the
70  // operators are not comparable, so a < b is not the same as !(a
71  // >= b).
72  bool operator<(int x) const {
73  if (!exists) return false;
74  if (denominator > 0) {
75  return numerator < x * denominator;
76  } else {
77  return numerator > x * denominator;
78  }
79  }
80 
81  bool operator<=(int x) const {
82  if (!exists) return false;
83  if (denominator > 0) {
84  return numerator <= x * denominator;
85  } else {
86  return numerator >= x * denominator;
87  }
88  }
89 
90  bool operator>(int x) const {
91  if (!exists) return false;
92  return !((*this) <= x);
93  }
94 
95  bool operator>=(int x) const {
96  if (!exists) return false;
97  return !((*this) < x);
98  }
99 
100  bool operator==(int x) const {
101  return exists && (numerator == (x * denominator));
102  }
103 
104  bool operator==(const OptionalRational &other) const {
105  return (exists == other.exists) && (numerator * other.denominator == denominator * other.numerator);
106  }
107 };
108 
109 // A LoadJacobian records the derivative of the coordinate accessed in
110 // some producer w.r.t the loops of the consumer.
112  vector<vector<OptionalRational>> coeffs;
113  int64_t c;
114 
115 public:
116  LoadJacobian(vector<vector<OptionalRational>> &&matrix, int64_t c = 1)
117  : coeffs(matrix), c(c) {
118  }
119 
120  size_t producer_storage_dims() const {
121  return coeffs.size();
122  }
123 
124  size_t consumer_loop_dims() const {
125  if (coeffs.empty() || coeffs[0].empty()) {
126  // The producer is scalar, and we don't know how
127  // many consumer loops there are.
128  return 0;
129  }
130  return coeffs[0].size();
131  }
132 
133  OptionalRational operator()(int producer_storage_dim, int consumer_loop_dim) const {
134  if (coeffs.empty()) {
135  // The producer is scalar, so all strides are zero.
136  return {true, 0, 1};
137  }
138  internal_assert(producer_storage_dim < (int)coeffs.size());
139  const auto &p = coeffs[producer_storage_dim];
140  if (p.empty()) {
141  // The consumer is scalar, so all strides are zero.
142  return {true, 0, 1};
143  }
144  internal_assert(consumer_loop_dim < (int)p.size());
145  return p[consumer_loop_dim];
146  }
147 
148  // To avoid redundantly re-recording copies of the same
149  // load Jacobian, we keep a count of how many times a
150  // load with this Jacobian occurs.
151  int64_t count() const {
152  return c;
153  }
154 
155  // Try to merge another LoadJacobian into this one, increasing the
156  // count if the coefficients match.
157  bool merge(const LoadJacobian &other) {
158  if (other.coeffs.size() != coeffs.size()) return false;
159  for (size_t i = 0; i < coeffs.size(); i++) {
160  if (other.coeffs[i].size() != coeffs[i].size()) return false;
161  for (size_t j = 0; j < coeffs[i].size(); j++) {
162  if (!(other.coeffs[i][j] == coeffs[i][j])) return false;
163  }
164  }
165  c += other.count();
166  return true;
167  }
168 
169  // Multiply Jacobians, used to look at memory dependencies through
170  // inlined functions.
171  LoadJacobian operator*(const LoadJacobian &other) const {
172  vector<vector<OptionalRational>> matrix;
174  matrix.resize(producer_storage_dims());
175  for (size_t i = 0; i < producer_storage_dims(); i++) {
176  matrix[i].resize(other.consumer_loop_dims());
177  for (size_t j = 0; j < other.consumer_loop_dims(); j++) {
178  matrix[i][j] = OptionalRational{true, 0, 1};
179  for (size_t k = 0; k < consumer_loop_dims(); k++) {
180  matrix[i][j] += (*this)(i, k) * other(k, j);
181  }
182  }
183  }
184  LoadJacobian result(std::move(matrix), count() * other.count());
185  return result;
186  }
187 
188  void dump(const char *prefix) const;
189 };
190 
191 // Classes to represent a concrete set of bounds for a Func. A Span is
192 // single-dimensional, and a Bound is a multi-dimensional box. For
193 // each dimension we track the estimated size, and also whether or not
194 // the size is known to be constant at compile-time. For each Func we
195 // track three different types of bounds:
196 
197 // 1) The region required by consumers of the Func, which determines
198 // 2) The region actually computed, which in turn determines
199 // 3) The min and max of all loops in the loop next.
200 
201 // 3 in turn determines the region required of the inputs to a Func,
202 // which determines their region computed, and hence their loop nest,
203 // and so on back up the Function DAG from outputs back to inputs.
204 
205 class Span {
206  int64_t min_, max_;
207  bool constant_extent_;
208 
209 public:
210  int64_t min() const {
211  return min_;
212  }
213  int64_t max() const {
214  return max_;
215  }
216  int64_t extent() const {
217  return max_ - min_ + 1;
218  }
219  bool constant_extent() const {
220  return constant_extent_;
221  }
222 
223  void union_with(const Span &other) {
224  min_ = std::min(min_, other.min());
225  max_ = std::max(max_, other.max());
226  constant_extent_ = constant_extent_ && other.constant_extent();
227  }
228 
229  void set_extent(int64_t e) {
230  max_ = min_ + e - 1;
231  }
232 
233  void translate(int64_t x) {
234  min_ += x;
235  max_ += x;
236  }
237 
238  Span(int64_t a, int64_t b, bool c)
239  : min_(a), max_(b), constant_extent_(c) {
240  }
241  Span() = default;
242  Span(const Span &other) = default;
243  static Span empty_span() {
244  return Span(INT64_MAX, INT64_MIN, true);
245  }
246 };
247 
248 // Bounds objects are created and destroyed very frequently while
249 // exploring scheduling options, so we have a custom allocator and
250 // memory pool. Much like IR nodes, we treat them as immutable once
251 // created and wrapped in a Bound object so that they can be shared
252 // safely across scheduling alternatives.
255 
256  class Layout;
257  const Layout *layout = nullptr;
258 
259  Span *data() const {
260  // This struct is a header
261  return (Span *)(const_cast<BoundContents *>(this) + 1);
262  }
263 
265  return data()[i];
266  }
267 
269  return data()[i + layout->computed_offset];
270  }
271 
272  Span &loops(int i, int j) {
273  return data()[j + layout->loop_offset[i]];
274  }
275 
276  const Span &region_required(int i) const {
277  return data()[i];
278  }
279 
280  const Span &region_computed(int i) const {
281  return data()[i + layout->computed_offset];
282  }
283 
284  const Span &loops(int i, int j) const {
285  return data()[j + layout->loop_offset[i]];
286  }
287 
289  auto b = layout->make();
290  size_t bytes = sizeof(data()[0]) * layout->total_size;
291  memcpy(b->data(), data(), bytes);
292  return b;
293  }
294 
295  void validate() const;
296 
297  // We're frequently going to need to make these concrete bounds
298  // arrays. It makes things more efficient if we figure out the
299  // memory layout of those data structures once ahead of time, and
300  // make each individual instance just use that. Note that this is
301  // not thread-safe.
302  class Layout {
303  // A memory pool of free BoundContent objects with this layout
304  mutable std::vector<BoundContents *> pool;
305 
306  // All the blocks of memory allocated
307  mutable std::vector<void *> blocks;
308 
309  mutable size_t num_live = 0;
310 
311  void allocate_some_more() const;
312 
313  public:
314  // number of Span to allocate
316 
317  // region_required has size func->dimensions() and comes first in the memory layout
318 
319  // region_computed comes next at the following index
321 
322  // the loop for each stage starts at the following index
323  std::vector<int> loop_offset;
324 
325  Layout() = default;
326  ~Layout();
327 
328  Layout(const Layout &) = delete;
329  void operator=(const Layout &) = delete;
330  Layout(Layout &&) = delete;
331  void operator=(Layout &&) = delete;
332 
333  // Make a BoundContents object with this layout
334  BoundContents *make() const;
335 
336  // Release a BoundContents object with this layout back to the pool
337  void release(const BoundContents *b) const;
338  };
339 };
340 
342 
343 // A representation of the function DAG. The nodes and edges are both
344 // in reverse realization order, so if you want to walk backwards up
345 // the DAG, just iterate the nodes or edges in-order.
346 struct FunctionDAG {
347 
348  // An edge is a producer-consumer relationship
349  struct Edge;
350 
354  };
355 
356  // A Node represents a single Func
357  struct Node {
358  // A pointer back to the owning DAG
360 
361  // The Halide Func this represents
363 
364  // The number of bytes per point stored.
366 
367  // The min/max variables used to denote a symbolic region of
368  // this Func. Used in the cost above, and in the Edges below.
369  vector<SymbolicInterval> region_required;
370 
371  // A concrete region required from a bounds estimate. Only
372  // defined for outputs.
374 
375  // The region computed of a Func, in terms of the region
376  // required. For simple Funcs this is identical to the
377  // region_required. However, in some Funcs computing one
378  // output requires computing other outputs too. You can't
379  // really ask for a single output pixel from something blurred
380  // with an IIR without computing the others, for example.
382  // The min and max in their full symbolic glory. We use
383  // these in the general case.
385 
386  // Analysis used to accelerate common cases
388  int64_t c_min = 0, c_max = 0;
389  };
390  vector<RegionComputedInfo> region_computed;
392 
393  // Expand a region required into a region computed, using the
394  // symbolic intervals above.
395  void required_to_computed(const Span *required, Span *computed) const;
396 
397  // Metadata about one symbolic loop in a Func's default loop nest.
398  struct Loop {
399  string var;
400  bool pure, rvar;
402 
403  // Which pure dimension does this loop correspond to? Invalid if it's an rvar
404  int pure_dim;
405 
406  // Precomputed metadata to accelerate common cases:
407 
408  // If true, the loop bounds are just the region computed in the given dimension
411 
412  // If true, the loop bounds are a constant with the given min and max
413  bool bounds_are_constant = false;
414  int64_t c_min = 0, c_max = 0;
415 
416  // A persistent fragment of source for getting this Var
417  // from its owner Func. Used for printing source code
418  // equivalent to a computed schedule.
419  string accessor;
420  };
421 
422  // Get the loop nest shape as a function of the region computed
423  void loop_nest_for_region(int stage_idx, const Span *computed, Span *loop) const;
424 
425  // One stage of a Func
426  struct Stage {
427  // The owning Node
429 
430  // Which stage of the Func is this. 0 = pure.
431  int index;
432 
433  // The loop nest that computes this stage, from innermost out.
434  vector<Loop> loop;
436 
437  // The vectorization width that will be used for
438  // compute. Corresponds to the natural width for the
439  // narrowest type used.
441 
442  // The featurization of the compute done
444 
445  // The actual Halide front-end stage object
447 
448  // The name for scheduling (e.g. "foo.update(3)")
449  string name;
450 
451  // Ids for perfect hashing on stages.
452  int id, max_id;
453 
454  vector<Edge *> incoming_edges;
455 
456  vector<bool> dependencies;
457  bool downstream_of(const Node &n) const {
458  return dependencies[n.id];
459  };
460 
462  : stage(s) {
463  }
464  };
465  vector<Stage> stages;
466 
467  vector<Edge *> outgoing_edges;
468 
469  // Max vector size across the stages
471 
472  // A unique ID for this node, allocated consecutively starting
473  // at zero for each pipeline.
474  int id, max_id;
475 
476  // Just func->dimensions(), but we ask for it so many times
477  // that's it's worth avoiding the function call into
478  // libHalide.
480 
481  // Is a single pointwise call to another Func
483 
484  // We represent the input buffers as node, though we do not attempt to schedule them.
485  bool is_input;
486 
487  // Is one of the pipeline outputs
488  bool is_output;
489 
490  // Only uses pointwise calls
492 
493  // Only uses pointwise calls + clamping on all indices
495 
496  std::unique_ptr<BoundContents::Layout> bounds_memory_layout;
497 
499  return bounds_memory_layout->make();
500  }
501  };
502 
503  // A representation of a producer-consumer relationship
504  struct Edge {
505  struct BoundInfo {
506  // The symbolic expression for the bound in this dimension
508 
509  // Fields below are the results of additional analysis
510  // used to evaluate this bound more quickly.
514 
515  BoundInfo(const Expr &e, const Node::Stage &consumer);
516  };
517 
518  // Memory footprint on producer required by consumer.
519  vector<pair<BoundInfo, BoundInfo>> bounds;
520 
523 
524  // The number of calls the consumer makes to the producer, per
525  // point in the loop nest of the consumer.
526  int calls;
527 
529 
530  vector<LoadJacobian> load_jacobians;
531 
533 
534  // Given a loop nest of the consumer stage, expand a region
535  // required of the producer to be large enough to include all
536  // points required.
537  void expand_footprint(const Span *consumer_loop, Span *producer_required) const;
538  };
539 
540  vector<Node> nodes;
541  vector<Edge> edges;
542 
543  // Create the function DAG, and do all the dependency and cost
544  // analysis. This is done once up-front before the tree search.
545  FunctionDAG(const vector<Function> &outputs, const MachineParams &params, const Target &target);
546 
547  void dump() const;
548  std::ostream &dump(std::ostream &os) const;
549 
550 private:
551  // Compute the featurization for the entire DAG
552  void featurize();
553 
554  // This class uses a lot of internal pointers, so we'll hide the copy constructor.
555  FunctionDAG(const FunctionDAG &other) = delete;
556  void operator=(const FunctionDAG &other) = delete;
557 
558  template<typename OS>
559  void dump_internal(OS &os) const;
560 };
561 
562 } // namespace Autoscheduler
563 } // namespace Internal
564 } // namespace Halide
565 
566 #endif // FUNCTION_DAG_H
Halide::Internal::Autoscheduler::LoadJacobian::LoadJacobian
LoadJacobian(vector< vector< OptionalRational >> &&matrix, int64_t c=1)
Definition: FunctionDAG.h:116
Halide::Internal::Autoscheduler::LoadJacobian::count
int64_t count() const
Definition: FunctionDAG.h:151
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::coeff
int64_t coeff
Definition: FunctionDAG.h:511
Halide::MachineParams
A struct representing the machine parameters to generate the auto-scheduled code for.
Definition: Pipeline.h:31
Halide::Internal::Autoscheduler::BoundContents::Layout
Definition: FunctionDAG.h:302
Halide::Internal::Autoscheduler::OptionalRational::operator>
bool operator>(int x) const
Definition: FunctionDAG.h:90
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::index
int index
Definition: FunctionDAG.h:431
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::node
Node * node
Definition: FunctionDAG.h:428
Halide::Internal::Autoscheduler::BoundContents
Definition: FunctionDAG.h:253
internal_assert
#define internal_assert(c)
Definition: Errors.h:19
Errors.h
Halide::Var
A Halide variable, to be used when defining functions.
Definition: Var.h:19
Halide::Internal::Autoscheduler::FunctionDAG::Node::region_computed_all_common_cases
bool region_computed_all_common_cases
Definition: FunctionDAG.h:391
Halide::Internal::Autoscheduler::FunctionDAG::Node::vector_size
int vector_size
Definition: FunctionDAG.h:470
Halide::Internal::Autoscheduler::FunctionDAG::SymbolicInterval::min
Halide::Var min
Definition: FunctionDAG.h:352
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::loop
vector< Loop > loop
Definition: FunctionDAG.h:434
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::features
PipelineFeatures features
Definition: FunctionDAG.h:443
Halide::Internal::Autoscheduler::FunctionDAG::Node::bytes_per_point
double bytes_per_point
Definition: FunctionDAG.h:365
Halide::Internal::Autoscheduler::BoundContents::make_copy
BoundContents * make_copy() const
Definition: FunctionDAG.h:288
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::accessor
string accessor
Definition: FunctionDAG.h:419
Halide::Internal::Autoscheduler::LoadJacobian::dump
void dump(const char *prefix) const
Halide::Internal::Autoscheduler::BoundContents::Layout::Layout
Layout()=default
Halide::Internal::Autoscheduler::OptionalRational::numerator
int64_t numerator
Definition: FunctionDAG.h:33
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::affine
bool affine
Definition: FunctionDAG.h:513
Halide::Internal::Autoscheduler::FunctionDAG::nodes
vector< Node > nodes
Definition: FunctionDAG.h:540
Halide::min
Expr min(const FuncRef &a, const FuncRef &b)
Explicit overloads of min and max for FuncRef.
Definition: Func.h:577
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::pure_dim
int pure_dim
Definition: FunctionDAG.h:404
Halide::Internal::Autoscheduler::FunctionDAG
Definition: FunctionDAG.h:346
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::BoundInfo
BoundInfo(const Expr &e, const Node::Stage &consumer)
Halide::Internal::Autoscheduler::OptionalRational::operator+=
void operator+=(const OptionalRational &other)
Definition: FunctionDAG.h:40
Halide::Internal::Autoscheduler::FunctionDAG::Node::dag
FunctionDAG * dag
Definition: FunctionDAG.h:359
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::rvar
bool rvar
Definition: FunctionDAG.h:400
Halide::Internal::Autoscheduler::LoadJacobian::consumer_loop_dims
size_t consumer_loop_dims() const
Definition: FunctionDAG.h:124
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::RegionComputedInfo::equals_union_of_required_with_constants
bool equals_union_of_required_with_constants
Definition: FunctionDAG.h:387
Halide::Internal::Autoscheduler::FunctionDAG::dump
void dump() const
Halide::Internal::Autoscheduler::Span
Definition: FunctionDAG.h:205
Halide::Internal::Autoscheduler::BoundContents::region_computed
Span & region_computed(int i)
Definition: FunctionDAG.h:268
Halide::Internal::Autoscheduler::Span::max
int64_t max() const
Definition: FunctionDAG.h:213
Halide::Internal::PipelineFeatures
Definition: Featurization.h:15
Halide::Internal::Autoscheduler::BoundContents::Layout::make
BoundContents * make() const
Halide::Internal::Autoscheduler::Span::min
int64_t min() const
Definition: FunctionDAG.h:210
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::bounds_are_constant
bool bounds_are_constant
Definition: FunctionDAG.h:413
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::max
Expr max
Definition: FunctionDAG.h:401
Halide::Internal::Autoscheduler::BoundContents::validate
void validate() const
Halide::Internal::IntrusivePtr
Intrusive shared pointers have a reference count (a RefCount object) stored in the class itself.
Definition: IntrusivePtr.h:68
Halide::Internal::Autoscheduler::FunctionDAG::Node::estimated_region_required
vector< Span > estimated_region_required
Definition: FunctionDAG.h:373
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::max_id
int max_id
Definition: FunctionDAG.h:452
Halide::Internal::Autoscheduler::Span::translate
void translate(int64_t x)
Definition: FunctionDAG.h:233
Halide::Internal::gcd
int64_t gcd(int64_t, int64_t)
The greatest common divisor of two integers.
Halide::Internal::Autoscheduler::Span::empty_span
static Span empty_span()
Definition: FunctionDAG.h:243
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_input
bool is_input
Definition: FunctionDAG.h:485
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::min
Expr min
Definition: FunctionDAG.h:401
Halide::Internal::Autoscheduler::FunctionDAG::Node::region_required
vector< SymbolicInterval > region_required
Definition: FunctionDAG.h:369
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AddAtomicMutex.h:21
Halide::Internal::Autoscheduler::Span::Span
Span()=default
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::consumer_dim
int64_t consumer_dim
Definition: FunctionDAG.h:512
Halide::Internal::Autoscheduler::OptionalRational::operator<=
bool operator<=(int x) const
Definition: FunctionDAG.h:81
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::Internal::Autoscheduler::LoadJacobian::operator()
OptionalRational operator()(int producer_storage_dim, int consumer_loop_dim) const
Definition: FunctionDAG.h:133
Halide::Internal::Autoscheduler::BoundContents::region_required
Span & region_required(int i)
Definition: FunctionDAG.h:264
Halide::Internal::Autoscheduler::BoundContents::Layout::operator=
void operator=(const Layout &)=delete
Halide::Internal::Autoscheduler::LoadJacobian::producer_storage_dims
size_t producer_storage_dims() const
Definition: FunctionDAG.h:120
Halide::Internal::Autoscheduler::FunctionDAG::Node::make_bound
BoundContents * make_bound() const
Definition: FunctionDAG.h:498
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_wrapper
bool is_wrapper
Definition: FunctionDAG.h:482
Halide::Internal::Autoscheduler::FunctionDAG::SymbolicInterval::max
Halide::Var max
Definition: FunctionDAG.h:353
Halide::Internal::Autoscheduler::FunctionDAG::Edge::consumer
FunctionDAG::Node::Stage * consumer
Definition: FunctionDAG.h:522
Halide::Internal::Autoscheduler::Span::extent
int64_t extent() const
Definition: FunctionDAG.h:216
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::pure
bool pure
Definition: FunctionDAG.h:400
Halide::Internal::Autoscheduler::OptionalRational::operator>=
bool operator>=(int x) const
Definition: FunctionDAG.h:95
Halide::Internal::Autoscheduler::BoundContents::layout
const Layout * layout
Definition: FunctionDAG.h:257
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::Stage
Stage(Halide::Stage s)
Definition: FunctionDAG.h:461
Halide::Internal::Autoscheduler::BoundContents::Layout::loop_offset
std::vector< int > loop_offset
Definition: FunctionDAG.h:323
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::expr
Expr expr
Definition: FunctionDAG.h:507
Halide::Internal::Autoscheduler::BoundContents::Layout::total_size
int total_size
Definition: FunctionDAG.h:315
Halide::Internal::Autoscheduler::FunctionDAG::Node::stages
vector< Stage > stages
Definition: FunctionDAG.h:465
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::stage
Halide::Stage stage
Definition: FunctionDAG.h:446
Halide::Internal::Autoscheduler::OptionalRational::OptionalRational
OptionalRational(bool e, int64_t n, int64_t d)
Definition: FunctionDAG.h:36
Halide::Internal::Autoscheduler::LoadJacobian::operator*
LoadJacobian operator*(const LoadJacobian &other) const
Definition: FunctionDAG.h:171
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo::c_min
int64_t c_min
Definition: FunctionDAG.h:388
int64_t
signed __INT64_TYPE__ int64_t
Definition: runtime_internal.h:18
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::uses_max
bool uses_max
Definition: FunctionDAG.h:513
Halide::Internal::Autoscheduler::FunctionDAG::Edge::expand_footprint
void expand_footprint(const Span *consumer_loop, Span *producer_required) const
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage
Definition: FunctionDAG.h:426
Halide::Internal::Autoscheduler::BoundContents::data
Span * data() const
Definition: FunctionDAG.h:259
Halide::Internal::Autoscheduler::FunctionDAG::Edge::producer
FunctionDAG::Node * producer
Definition: FunctionDAG.h:521
Halide::Internal::Autoscheduler::BoundContents::region_computed
const Span & region_computed(int i) const
Definition: FunctionDAG.h:280
Halide::Internal::Autoscheduler::FunctionDAG::edges
vector< Edge > edges
Definition: FunctionDAG.h:541
Halide::Internal::Autoscheduler::OptionalRational::operator==
bool operator==(const OptionalRational &other) const
Definition: FunctionDAG.h:104
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo
Definition: FunctionDAG.h:381
Halide::Internal::Autoscheduler::FunctionDAG::Node::max_id
int max_id
Definition: FunctionDAG.h:474
Halide::Internal::Autoscheduler::BoundContents::Layout::~Layout
~Layout()
Halide::Internal::Autoscheduler::FunctionDAG::Edge::bounds
vector< pair< BoundInfo, BoundInfo > > bounds
Definition: FunctionDAG.h:519
Halide::Internal::Autoscheduler::FunctionDAG::Node::outgoing_edges
vector< Edge * > outgoing_edges
Definition: FunctionDAG.h:467
Halide::Internal::Interval
A class to represent ranges of Exprs.
Definition: Interval.h:14
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::equals_region_computed
bool equals_region_computed
Definition: FunctionDAG.h:409
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::c_max
int64_t c_max
Definition: FunctionDAG.h:414
Halide::Internal::Autoscheduler::FunctionDAG::Edge::add_load_jacobian
void add_load_jacobian(LoadJacobian j1)
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo::constant
int64_t constant
Definition: FunctionDAG.h:511
Halide::Internal::Autoscheduler::Span::constant_extent
bool constant_extent() const
Definition: FunctionDAG.h:219
Halide::Internal::Function
A reference-counted handle to Halide's internal representation of a function.
Definition: Function.h:38
Halide::Internal::Autoscheduler::OptionalRational::operator*
OptionalRational operator*(const OptionalRational &other) const
Definition: FunctionDAG.h:59
Halide::Internal::Autoscheduler::FunctionDAG::Node::bounds_memory_layout
std::unique_ptr< BoundContents::Layout > bounds_memory_layout
Definition: FunctionDAG.h:496
Halide::Internal::Autoscheduler::LoadJacobian
Definition: FunctionDAG.h:111
Featurization.h
Halide::Internal::lcm
int64_t lcm(int64_t, int64_t)
The least common multiple of two integers.
Halide::Internal::Autoscheduler::FunctionDAG::Edge::load_jacobians
vector< LoadJacobian > load_jacobians
Definition: FunctionDAG.h:530
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::loop_nest_all_common_cases
bool loop_nest_all_common_cases
Definition: FunctionDAG.h:435
Halide::Internal::Autoscheduler::Span::Span
Span(int64_t a, int64_t b, bool c)
Definition: FunctionDAG.h:238
Halide::Internal::Autoscheduler::FunctionDAG::Node::region_computed
vector< RegionComputedInfo > region_computed
Definition: FunctionDAG.h:390
Halide::Internal::Autoscheduler::FunctionDAG::SymbolicInterval
Definition: FunctionDAG.h:351
memcpy
void * memcpy(void *s1, const void *s2, size_t n)
Halide::Internal::Autoscheduler::FunctionDAG::Node::dimensions
int dimensions
Definition: FunctionDAG.h:479
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_boundary_condition
bool is_boundary_condition
Definition: FunctionDAG.h:494
Halide::Internal::Autoscheduler::BoundContents::ref_count
RefCount ref_count
Definition: FunctionDAG.h:254
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::incoming_edges
vector< Edge * > incoming_edges
Definition: FunctionDAG.h:454
Halide::Internal::Autoscheduler::OptionalRational::operator<
bool operator<(int x) const
Definition: FunctionDAG.h:72
Halide::Internal::Autoscheduler::OptionalRational::exists
bool exists
Definition: FunctionDAG.h:32
Halide::Internal::Autoscheduler::BoundContents::Layout::computed_offset
int computed_offset
Definition: FunctionDAG.h:320
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop
Definition: FunctionDAG.h:398
Halide::Internal::Autoscheduler::OptionalRational
Definition: FunctionDAG.h:31
Halide::Internal::RefCount
A class representing a reference count to be used with IntrusivePtr.
Definition: IntrusivePtr.h:19
Halide::Internal::Autoscheduler::FunctionDAG::Node::func
Function func
Definition: FunctionDAG.h:362
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::dependencies
vector< bool > dependencies
Definition: FunctionDAG.h:456
Halide::Internal::Autoscheduler::FunctionDAG::FunctionDAG
FunctionDAG(const vector< Function > &outputs, const MachineParams &params, const Target &target)
Halide::Expr
A fragment of Halide syntax.
Definition: Expr.h:256
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo::c_max
int64_t c_max
Definition: FunctionDAG.h:388
Halide::Internal::Autoscheduler::BoundContents::region_required
const Span & region_required(int i) const
Definition: FunctionDAG.h:276
Halide::Internal::Autoscheduler::FunctionDAG::Edge::calls
int calls
Definition: FunctionDAG.h:526
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::var
string var
Definition: FunctionDAG.h:399
Halide::Internal::Autoscheduler::BoundContents::loops
Span & loops(int i, int j)
Definition: FunctionDAG.h:272
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::c_min
int64_t c_min
Definition: FunctionDAG.h:414
Halide::Internal::Autoscheduler::FunctionDAG::Node::required_to_computed
void required_to_computed(const Span *required, Span *computed) const
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo::equals_required
bool equals_required
Definition: FunctionDAG.h:387
Halide::Internal::Autoscheduler::Span::set_extent
void set_extent(int64_t e)
Definition: FunctionDAG.h:229
Halide::Internal::Autoscheduler::FunctionDAG::Node
Definition: FunctionDAG.h:357
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_pointwise
bool is_pointwise
Definition: FunctionDAG.h:491
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::id
int id
Definition: FunctionDAG.h:452
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::vector_size
int vector_size
Definition: FunctionDAG.h:440
Halide::max
Expr max(const FuncRef &a, const FuncRef &b)
Definition: Func.h:580
Halide::Internal::Autoscheduler::FunctionDAG::Edge
Definition: FunctionDAG.h:504
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::name
string name
Definition: FunctionDAG.h:449
Halide::Stage
A single definition of a Func.
Definition: Func.h:69
Halide::Internal::Autoscheduler::LoadJacobian::merge
bool merge(const LoadJacobian &other)
Definition: FunctionDAG.h:157
Halide::Internal::Autoscheduler::OptionalRational::operator==
bool operator==(int x) const
Definition: FunctionDAG.h:100
Halide::Internal::Autoscheduler::OptionalRational::denominator
int64_t denominator
Definition: FunctionDAG.h:33
Halide::Internal::Autoscheduler::Span::union_with
void union_with(const Span &other)
Definition: FunctionDAG.h:223
Halide::Internal::Autoscheduler::FunctionDAG::Edge::BoundInfo
Definition: FunctionDAG.h:505
Halide::Target
A struct representing a target machine and os to generate code for.
Definition: Target.h:19
Halide::Internal::Autoscheduler::OptionalRational::OptionalRational
OptionalRational()=default
Halide::Internal::Autoscheduler::FunctionDAG::Node::Stage::downstream_of
bool downstream_of(const Node &n) const
Definition: FunctionDAG.h:457
Halide::Internal::Autoscheduler::BoundContents::loops
const Span & loops(int i, int j) const
Definition: FunctionDAG.h:284
Halide::Internal::Autoscheduler::FunctionDAG::Node::id
int id
Definition: FunctionDAG.h:474
Halide::Internal::Autoscheduler::BoundContents::Layout::release
void release(const BoundContents *b) const
Halide::Internal::Autoscheduler::FunctionDAG::Node::is_output
bool is_output
Definition: FunctionDAG.h:488
Halide::Internal::Autoscheduler::FunctionDAG::Node::Loop::region_computed_dim
int region_computed_dim
Definition: FunctionDAG.h:410
Halide::Internal::Autoscheduler::FunctionDAG::Node::RegionComputedInfo::in
Interval in
Definition: FunctionDAG.h:384
Halide::Internal::Autoscheduler::FunctionDAG::Edge::all_bounds_affine
bool all_bounds_affine
Definition: FunctionDAG.h:528