Halide
Schedule.h
Go to the documentation of this file.
1 #ifndef HALIDE_SCHEDULE_H
2 #define HALIDE_SCHEDULE_H
3 
4 /** \file
5  * Defines the internal representation of the schedule for a function
6  */
7 
8 #include "Expr.h"
9 #include "Parameter.h"
10 #include "FunctionPtr.h"
11 
12 #include <map>
13 
14 namespace Halide {
15 
16 class Func;
17 template <typename T> class ScheduleParam;
18 struct VarOrRVar;
19 
20 namespace Internal {
21 class Function;
22 struct FunctionContents;
23 struct LoopLevelContents;
24 class ScheduleParamBase;
25 } // namespace Internal
26 
27 /** Different ways to handle a tail case in a split when the
28  * factor does not provably divide the extent. */
29 enum class TailStrategy {
30  /** Round up the extent to be a multiple of the split
31  * factor. Not legal for RVars, as it would change the meaning
32  * of the algorithm. Pros: generates the simplest, fastest
33  * code. Cons: if used on a stage that reads from the input or
34  * writes to the output, constrains the input or output size
35  * to be a multiple of the split factor. */
36  RoundUp,
37 
38  /** Guard the inner loop with an if statement that prevents
39  * evaluation beyond the original extent. Always legal. The if
40  * statement is treated like a boundary condition, and
41  * factored out into a loop epilogue if possible. Pros: no
42  * redundant re-evaluation; does not constrain input our
43  * output sizes. Cons: increases code size due to separate
44  * tail-case handling; vectorization will scalarize in the tail
45  * case to handle the if statement. */
47 
48  /** Prevent evaluation beyond the original extent by shifting
49  * the tail case inwards, re-evaluating some points near the
50  * end. Only legal for pure variables in pure definitions. If
51  * the inner loop is very simple, the tail case is treated
52  * like a boundary condition and factored out into an
53  * epilogue.
54  *
55  * This is a good trade-off between several factors. Like
56  * RoundUp, it supports vectorization well, because the inner
57  * loop is always a fixed size with no data-dependent
58  * branching. It increases code size slightly for inner loops
59  * due to the epilogue handling, but not for outer loops
60  * (e.g. loops over tiles). If used on a stage that reads from
61  * an input or writes to an output, this stategy only requires
62  * that the input/output extent be at least the split factor,
63  * instead of a multiple of the split factor as with RoundUp. */
65 
66  /** For pure definitions use ShiftInwards. For pure vars in
67  * update definitions use RoundUp. For RVars in update
68  * definitions use GuardWithIf. */
69  Auto
70 };
71 
72 /** Different ways to handle accesses outside the original extents in a prefetch. */
74  /** Clamp the prefetched exprs by intersecting the prefetched region with
75  * the original extents. This may make the exprs of the prefetched region
76  * more complicated. */
77  Clamp,
78 
79  /** Guard the prefetch with if-guards that ignores the prefetch if
80  * any of the prefetched region ever goes beyond the original extents
81  * (i.e. all or nothing). */
83 
84  /** Leave the prefetched exprs as are (no if-guards around the prefetch
85  * and no intersecting with the original extents). This makes the prefetch
86  * exprs simpler but this may cause prefetching of region outside the original
87  * extents. This is good if prefetch won't fault when accessing region
88  * outside the original extents. */
90 };
91 
92 /** A reference to a site in a Halide statement at the top of the
93  * body of a particular for loop. Evaluating a region of a halide
94  * function is done by generating a loop nest that spans its
95  * dimensions. We schedule the inputs to that function by
96  * recursively injecting realizations for them at particular sites
97  * in this loop nest. A LoopLevel identifies such a site. */
98 class LoopLevel {
99  template <typename T> friend class ScheduleParam;
100  friend class ::Halide::Internal::ScheduleParamBase;
101 
103 
105  EXPORT LoopLevel(const std::string &func_name, const std::string &var_name, bool is_rvar);
106 
107  /** Mutate our contents to match the contents of 'other'. This is a potentially
108  * dangerous operation to do if you aren't careful, and exists solely to make
109  * ScheduleParam<LoopLevel> easy to implement; hence its private status. */
110  EXPORT void copy_from(const LoopLevel &other);
111 
112 public:
113  /** Identify the loop nest corresponding to some dimension of some function */
114  // @{
115  EXPORT LoopLevel(Internal::Function f, VarOrRVar v);
116  EXPORT LoopLevel(Func f, VarOrRVar v);
117  // @}
118 
119  /** Construct an undefined LoopLevel. Calling any method on an undefined
120  * LoopLevel (other than defined() or operator==) will assert. */
121  LoopLevel() = default;
122 
123  /** Return true iff the LoopLevel is defined. */
124  EXPORT bool defined() const;
125 
126  /** Return the Func name. Asserts if the LoopLevel is_root() or is_inline(). */
127  EXPORT std::string func() const;
128 
129  /** Return the VarOrRVar. Asserts if the LoopLevel is_root() or is_inline(). */
130  EXPORT VarOrRVar var() const;
131 
132  /** inlined is a special LoopLevel value that implies
133  * that a function should be inlined away. */
134  EXPORT static LoopLevel inlined();
135 
136  /** Test if a loop level corresponds to inlining the function */
137  EXPORT bool is_inline() const;
138 
139  /** root is a special LoopLevel value which represents the
140  * location outside of all for loops */
141  EXPORT static LoopLevel root();
142 
143  /** Test if a loop level is 'root', which describes the site
144  * outside of all for loops */
145  EXPORT bool is_root() const;
146 
147  /** Return a string of the form func.var -- note that this is safe
148  * to call for root or inline LoopLevels. */
149  EXPORT std::string to_string() const;
150 
151  /** Compare this loop level against the variable name of a for
152  * loop, to see if this loop level refers to the site
153  * immediately inside this loop. */
154  EXPORT bool match(const std::string &loop) const;
155 
156  EXPORT bool match(const LoopLevel &other) const;
157 
158  /** Check if two loop levels are exactly the same. */
159  EXPORT bool operator==(const LoopLevel &other) const;
160 
161  bool operator!=(const LoopLevel &other) const { return !(*this == other); }
162 };
163 
164 namespace Internal {
165 
166 class IRMutator2;
167 struct ReductionVariable;
168 
169 struct Split {
170  std::string old_var, outer, inner;
172  bool exact; // Is it required that the factor divides the extent
173  // of the old var. True for splits of RVars. Forces
174  // tail strategy to be GuardWithIf.
176 
177  enum SplitType {SplitVar = 0, RenameVar, FuseVars, PurifyRVar};
178 
179  // If split_type is Rename, then this is just a renaming of the
180  // old_var to the outer and not a split. The inner var should
181  // be ignored, and factor should be one. Renames are kept in
182  // the same list as splits so that ordering between them is
183  // respected.
184 
185  // If split type is Purify, this replaces the old_var RVar to
186  // the outer Var. The inner var should be ignored, and factor
187  // should be one.
188 
189  // If split_type is Fuse, then this does the opposite of a
190  // split, it joins the outer and inner into the old_var.
192 
193  bool is_rename() const {return split_type == RenameVar;}
194  bool is_split() const {return split_type == SplitVar;}
195  bool is_fuse() const {return split_type == FuseVars;}
196  bool is_purify() const {return split_type == PurifyRVar;}
197 };
198 
199 struct Dim {
200  std::string var;
203 
204  enum Type {PureVar = 0, PureRVar, ImpureRVar};
206 
207  bool is_pure() const {return (dim_type == PureVar) || (dim_type == PureRVar);}
208  bool is_rvar() const {return (dim_type == PureRVar) || (dim_type == ImpureRVar);}
209  bool is_parallel() const {
210  return (for_type == ForType::Parallel ||
211  for_type == ForType::GPUBlock ||
212  for_type == ForType::GPUThread);
213  }
214 };
215 
216 struct Bound {
217  std::string var;
218  Expr min, extent, modulus, remainder;
219 };
220 
221 struct StorageDim {
222  std::string var;
226 };
227 
229  std::string name;
230  std::string var;
233  // If it's a prefetch load from an image parameter, this points to that.
235 };
236 
237 struct FuncScheduleContents;
238 struct StageScheduleContents;
239 struct FunctionContents;
240 
241 /** A schedule for a Function of a Halide pipeline. This schedule is
242  * applied to all stages of the Function. Right now this interface is
243  * basically a struct, offering mutable access to its innards.
244  * In the future it may become more encapsulated. */
247 
248 public:
249 
251  FuncSchedule(const FuncSchedule &other) : contents(other.contents) {}
253 
254  /** Return a deep copy of this FuncSchedule. It recursively deep copies all
255  * called functions, schedules, specializations, and reduction domains. This
256  * method takes a map of <old FunctionContents, deep-copied version> as input
257  * and would use the deep-copied FunctionContents from the map if exists
258  * instead of creating a new deep-copy to avoid creating deep-copies of the
259  * same FunctionContents multiple times.
260  */
261  EXPORT FuncSchedule deep_copy(
262  std::map<FunctionPtr, FunctionPtr> &copied_map) const;
263 
264  /** This flag is set to true if the schedule is memoized. */
265  // @{
266  bool &memoized();
267  bool memoized() const;
268  // @}
269 
270  /** The list and order of dimensions used to store this
271  * function. The first dimension in the vector corresponds to the
272  * innermost dimension for storage (i.e. which dimension is
273  * tightly packed in memory) */
274  // @{
275  const std::vector<StorageDim> &storage_dims() const;
276  std::vector<StorageDim> &storage_dims();
277  // @}
278 
279  /** You may explicitly bound some of the dimensions of a function,
280  * or constrain them to lie on multiples of a given factor. See
281  * \ref Func::bound and \ref Func::align_bounds */
282  // @{
283  const std::vector<Bound> &bounds() const;
284  std::vector<Bound> &bounds();
285  // @}
286 
287  /** You may explicitly specify an estimate of some of the function
288  * dimensions. See \ref Func::estimate */
289  // @{
290  const std::vector<Bound> &estimates() const;
291  std::vector<Bound> &estimates();
292  // @}
293 
294  /** Mark calls of a function by 'f' to be replaced with its identity
295  * wrapper or clone during the lowering stage. If the string 'f' is empty,
296  * it means replace all calls to the function by all other functions
297  * (excluding itself) in the pipeline with the global identity wrapper.
298  * See \ref Func::in and \ref Func::clone for more details. */
299  // @{
300  const std::map<std::string, Internal::FunctionPtr> &wrappers() const;
301  std::map<std::string, Internal::FunctionPtr> &wrappers();
302  EXPORT void add_wrapper(const std::string &f,
303  const Internal::FunctionPtr &wrapper);
304  // @}
305 
306  /** At what sites should we inject the allocation and the
307  * computation of this function? The store_level must be outside
308  * of or equal to the compute_level. If the compute_level is
309  * inline, the store_level is meaningless. See \ref Func::store_at
310  * and \ref Func::compute_at */
311  // @{
312  const LoopLevel &store_level() const;
313  const LoopLevel &compute_level() const;
314  LoopLevel &store_level();
315  LoopLevel &compute_level();
316  // @}
317 
318  /** Pass an IRVisitor through to all Exprs referenced in the
319  * Schedule. */
320  void accept(IRVisitor *) const;
321 
322  /** Pass an IRMutator2 through to all Exprs referenced in the
323  * Schedule. */
324  void mutate(IRMutator2 *);
325 };
326 
327 
328 /** A schedule for a single stage of a Halide pipeline. Right now this
329  * interface is basically a struct, offering mutable access to its
330  * innards. In the future it may become more encapsulated. */
333 
334 public:
335 
337  StageSchedule(const StageSchedule &other) : contents(other.contents) {}
339 
340  /** Return a copy of this StageSchedule. */
341  EXPORT StageSchedule get_copy() const;
342 
343  /** This flag is set to true if the dims list has been manipulated
344  * by the user (or if a ScheduleHandle was created that could have
345  * been used to manipulate it). It controls the warning that
346  * occurs if you schedule the vars of the pure step but not the
347  * update steps. */
348  // @{
349  bool &touched();
350  bool touched() const;
351  // @}
352 
353  /** RVars of reduction domain associated with this schedule if there is any. */
354  // @{
355  EXPORT const std::vector<ReductionVariable> &rvars() const;
356  std::vector<ReductionVariable> &rvars();
357  // @}
358 
359  /** The traversal of the domain of a function can have some of its
360  * dimensions split into sub-dimensions. See \ref Func::split */
361  // @{
362  const std::vector<Split> &splits() const;
363  std::vector<Split> &splits();
364  // @}
365 
366  /** The list and ordering of dimensions used to evaluate this
367  * function, after all splits have taken place. The first
368  * dimension in the vector corresponds to the innermost for loop,
369  * and the last is the outermost. Also specifies what type of for
370  * loop to use for each dimension. Does not specify the bounds on
371  * each dimension. These get inferred from how the function is
372  * used, what the splits are, and any optional bounds in the list below. */
373  // @{
374  const std::vector<Dim> &dims() const;
375  std::vector<Dim> &dims();
376  // @}
377 
378  /** You may perform prefetching in some of the dimensions of a
379  * function. See \ref Func::prefetch */
380  // @{
381  const std::vector<PrefetchDirective> &prefetches() const;
382  std::vector<PrefetchDirective> &prefetches();
383  // @}
384 
385  /** Are race conditions permitted? */
386  // @{
387  bool allow_race_conditions() const;
388  bool &allow_race_conditions();
389  // @}
390 
391  /** Pass an IRVisitor through to all Exprs referenced in the
392  * Schedule. */
393  void accept(IRVisitor *) const;
394 
395  /** Pass an IRMutator2 through to all Exprs referenced in the
396  * Schedule. */
397  void mutate(IRMutator2 *);
398 };
399 
400 }
401 }
402 
403 #endif
Guard the inner loop with an if statement that prevents evaluation beyond the original extent...
bool is_rename() const
Definition: Schedule.h:193
A reference to a site in a Halide statement at the top of the body of a particular for loop...
Definition: Schedule.h:98
A base class for algorithms that need to recursively walk over the IR.
Definition: IRVisitor.h:22
A schedule for a single stage of a Halide pipeline.
Definition: Schedule.h:331
A fragment of Halide syntax.
Definition: Expr.h:276
Prevent evaluation beyond the original extent by shifting the tail case inwards, re-evaluating some p...
decltype((Other) 0==(T) 1) operator==(const Other &a, const GeneratorParam< T > &b)
Equality comparison between GeneratorParam<T> and any type that supports operator== with T...
Definition: Generator.h:899
A base class for passes over the IR which modify it (e.g.
Definition: IRMutator.h:124
bool is_fuse() const
Definition: Schedule.h:195
For pure definitions use ShiftInwards.
A halide function.
Definition: Func.h:502
A possibly-weak pointer to a Halide function.
Definition: FunctionPtr.h:27
TailStrategy
Different ways to handle a tail case in a split when the factor does not provably divide the extent...
Definition: Schedule.h:29
Round up the extent to be a multiple of the split factor.
StageSchedule(IntrusivePtr< StageScheduleContents > c)
Definition: Schedule.h:336
std::string var
Definition: Schedule.h:200
StageSchedule(const StageSchedule &other)
Definition: Schedule.h:337
DeviceAPI device_api
Definition: Schedule.h:202
Defines methods for manipulating and analyzing boolean expressions.
A class that can represent Vars or RVars.
Definition: Func.h:29
bool is_parallel() const
Definition: Schedule.h:209
TailStrategy tail
Definition: Schedule.h:175
Expr min(FuncRef a, FuncRef b)
Explicit overloads of min and max for FuncRef.
Definition: Func.h:418
bool is_split() const
Definition: Schedule.h:194
A schedule for a Function of a Halide pipeline.
Definition: Schedule.h:245
Base classes for Halide expressions (Halide::Expr) and statements (Halide::Internal::Stmt) ...
bool is_purify() const
Definition: Schedule.h:196
std::pair< std::vector< Function >, std::map< std::string, Function > > deep_copy(const std::vector< Function > &outputs, const std::map< std::string, Function > &env)
Deep copy an entire Function DAG.
bool is_rvar() const
Definition: Schedule.h:208
Defines the internal representation of parameters to halide piplines.
PrefetchBoundStrategy
Different ways to handle accesses outside the original extents in a prefetch.
Definition: Schedule.h:73
ForType
An enum describing a type of loop traversal.
Definition: Expr.h:345
A reference-counted handle to a parameter to a halide pipeline.
Definition: Parameter.h:21
A reference-counted handle to Halide&#39;s internal representation of a function.
Definition: Function.h:67
FuncSchedule(IntrusivePtr< FuncScheduleContents > c)
Definition: Schedule.h:250
Leave the prefetched exprs as are (no if-guards around the prefetch and no intersecting with the orig...
A ScheduleParam is a "Param" that can contain a scalar Expr or a LoopLevel; unlike Param<>...
Definition: Schedule.h:17
#define EXPORT
Definition: Util.h:30
Clamp the prefetched exprs by intersecting the prefetched region with the original extents...
FuncSchedule(const FuncSchedule &other)
Definition: Schedule.h:251
bool is_pure() const
Definition: Schedule.h:207
DeviceAPI
An enum describing a type of device API.
Definition: Expr.h:317
PrefetchBoundStrategy strategy
Definition: Schedule.h:232
bool operator!=(const LoopLevel &other) const
Definition: Schedule.h:161