Halide
AutoScheduleUtils.h
Go to the documentation of this file.
1 #ifndef HALIDE_INTERNAL_AUTO_SCHEDULE_UTILS_H
2 #define HALIDE_INTERNAL_AUTO_SCHEDULE_UTILS_H
3 
4 /** \file
5  *
6  * Defines util functions that used by auto scheduler.
7  */
8 
9 #include <limits>
10 #include <set>
11 
12 #include "Bounds.h"
13 #include "Definition.h"
14 #include "IRMutator.h"
15 #include "IRVisitor.h"
16 #include "Interval.h"
17 
18 namespace Halide {
19 namespace Internal {
20 
21 typedef std::map<std::string, Interval> DimBounds;
22 
24 
25 /** Visitor for keeping track of functions that are directly called and the
26  * arguments with which they are called. */
27 class FindAllCalls : public IRVisitor {
28  using IRVisitor::visit;
29 
30  void visit(const Call *call) override {
31  if (call->call_type == Call::Halide || call->call_type == Call::Image) {
32  funcs_called.insert(call->name);
33  call_args.emplace_back(call->name, call->args);
34  }
35  for (size_t i = 0; i < call->args.size(); i++) {
36  call->args[i].accept(this);
37  }
38  }
39 
40 public:
41  std::set<std::string> funcs_called;
42  std::vector<std::pair<std::string, std::vector<Expr>>> call_args;
43 };
44 
45 /** Return an int representation of 's'. Throw an error on failure. */
46 int string_to_int(const std::string &s);
47 
48 /** Substitute every variable in an Expr or a Stmt with its estimate
49  * if specified. */
50 //@{
53 //@}
54 
55 /** Return the size of an interval. Return an undefined expr if the interval
56  * is unbounded. */
57 Expr get_extent(const Interval &i);
58 
59 /** Return the size of an n-d box. */
60 Expr box_size(const Box &b);
61 
62 /** Helper function to print the bounds of a region. */
63 void disp_regions(const std::map<std::string, Box> &regions);
64 
65 /** Return the corresponding definition of a function given the stage. This
66  * will throw an assertion if the function is an extern function (Extern Func
67  * does not have definition). */
68 Definition get_stage_definition(const Function &f, int stage_num);
69 
70 /** Return the corresponding loop dimensions of a function given the stage.
71  * For extern Func, this will return a list of size 1 containing the
72  * dummy __outermost loop dimension. */
73 std::vector<Dim> &get_stage_dims(const Function &f, int stage_num);
74 
75 /** Add partial load costs to the corresponding function in the result costs. */
76 void combine_load_costs(std::map<std::string, Expr> &result,
77  const std::map<std::string, Expr> &partial);
78 
79 /** Return the required bounds of an intermediate stage (f, stage_num) of
80  * function 'f' given the bounds of the pure dimensions. */
81 DimBounds get_stage_bounds(const Function &f, int stage_num, const DimBounds &pure_bounds);
82 
83 /** Return the required bounds for all the stages of the function 'f'. Each entry
84  * in the returned vector corresponds to a stage. */
85 std::vector<DimBounds> get_stage_bounds(const Function &f, const DimBounds &pure_bounds);
86 
87 /** Recursively inline all the functions in the set 'inlines' into the
88  * expression 'e' and return the resulting expression. If 'order' is
89  * passed, inlining will be done in the reverse order of function realization
90  * to avoid extra inlining works. */
91 Expr perform_inline(Expr e, const std::map<std::string, Function> &env,
92  const std::set<std::string> &inlines = std::set<std::string>(),
93  const std::vector<std::string> &order = std::vector<std::string>());
94 
95 /** Return all functions that are directly called by a function stage (f, stage). */
96 std::set<std::string> get_parents(Function f, int stage);
97 
98 /** Return value of element within a map. This will assert if the element is not
99  * in the map. */
100 // @{
101 template<typename K, typename V>
102 V get_element(const std::map<K, V> &m, const K &key) {
103  const auto &iter = m.find(key);
104  internal_assert(iter != m.end());
105  return iter->second;
106 }
107 
108 template<typename K, typename V>
109 V &get_element(std::map<K, V> &m, const K &key) {
110  const auto &iter = m.find(key);
111  internal_assert(iter != m.end());
112  return iter->second;
113 }
114 // @}
115 
116 /** If the cost of computing a Func is about the same as calling the Func,
117  * inline the Func. Return true of any of the Funcs is inlined. */
118 bool inline_all_trivial_functions(const std::vector<Function> &outputs,
119  const std::vector<std::string> &order,
120  const std::map<std::string, Function> &env);
121 
122 /** Determine if a Func (order[index]) is only consumed by another single Func
123  * in element-wise manner. If it is, return the name of the consumer Func;
124  * otherwise, return an empty string. */
125 std::string is_func_called_element_wise(const std::vector<std::string> &order, size_t index,
126  const std::map<std::string, Function> &env);
127 
128 /** Inline a Func if its values are only consumed by another single Func in
129  * element-wise manner. */
130 bool inline_all_element_wise_functions(const std::vector<Function> &outputs,
131  const std::vector<std::string> &order,
132  const std::map<std::string, Function> &env);
133 
135 
136 } // namespace Internal
137 } // namespace Halide
138 
139 #endif
internal_assert
#define internal_assert(c)
Definition: Errors.h:19
Halide::Internal::IRVisitor::visit
virtual void visit(const IntImm *)
Halide::Internal::FindAllCalls::call_args
std::vector< std::pair< std::string, std::vector< Expr > > > call_args
Definition: AutoScheduleUtils.h:42
Definition.h
Halide::Internal::IRVisitor
A base class for algorithms that need to recursively walk over the IR.
Definition: IRVisitor.h:21
Halide::Internal::FindAllCalls
Visitor for keeping track of functions that are directly called and the arguments with which they are...
Definition: AutoScheduleUtils.h:27
Halide::min
Expr min(const FuncRef &a, const FuncRef &b)
Explicit overloads of min and max for FuncRef.
Definition: Func.h:577
Bounds.h
Halide::Internal::substitute_var_estimates
Expr substitute_var_estimates(Expr e)
Substitute every variable in an Expr or a Stmt with its estimate if specified.
Halide::Internal::DimBounds
std::map< std::string, Interval > DimBounds
Definition: AutoScheduleUtils.h:21
IRMutator.h
Halide::Internal::get_parents
std::set< std::string > get_parents(Function f, int stage)
Return all functions that are directly called by a function stage (f, stage).
Halide::Internal::Call::Halide
@ Halide
A call to a Func.
Definition: IR.h:471
Halide::Internal::Definition
A Function definition which can either represent a init or an update definition.
Definition: Definition.h:38
Halide::Internal::FindAllCalls::funcs_called
std::set< std::string > funcs_called
Definition: AutoScheduleUtils.h:41
Halide::Internal::Stmt
A reference-counted handle to a statement node.
Definition: Expr.h:409
Halide::Internal::get_extent
Expr get_extent(const Interval &i)
Return the size of an interval.
Halide
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
Definition: AddAtomicMutex.h:21
Halide::Internal::Call::Image
@ Image
A load from an input image.
Definition: IR.h:467
Halide::LinkageType::Internal
@ Internal
Not visible externally, similar to 'static' linkage in C.
Halide::Internal::is_func_called_element_wise
std::string is_func_called_element_wise(const std::vector< std::string > &order, size_t index, const std::map< std::string, Function > &env)
Determine if a Func (order[index]) is only consumed by another single Func in element-wise manner.
Halide::Internal::get_element
V get_element(const std::map< K, V > &m, const K &key)
Return value of element within a map.
Definition: AutoScheduleUtils.h:102
IRVisitor.h
Halide::Internal::get_stage_dims
std::vector< Dim > & get_stage_dims(const Function &f, int stage_num)
Return the corresponding loop dimensions of a function given the stage.
Halide::Internal::inline_all_trivial_functions
bool inline_all_trivial_functions(const std::vector< Function > &outputs, const std::vector< std::string > &order, const std::map< std::string, Function > &env)
If the cost of computing a Func is about the same as calling the Func, inline the Func.
int64_t
signed __INT64_TYPE__ int64_t
Definition: runtime_internal.h:18
Halide::Internal::box_size
Expr box_size(const Box &b)
Return the size of an n-d box.
Halide::Internal::Call::name
std::string name
Definition: IR.h:465
Halide::Internal::perform_inline
Expr perform_inline(Expr e, const std::map< std::string, Function > &env, const std::set< std::string > &inlines=std::set< std::string >(), const std::vector< std::string > &order=std::vector< std::string >())
Recursively inline all the functions in the set 'inlines' into the expression 'e' and return the resu...
Halide::Internal::Interval
A class to represent ranges of Exprs.
Definition: Interval.h:14
Halide::Internal::unknown
const int64_t unknown
Definition: AutoScheduleUtils.h:23
Halide::Internal::combine_load_costs
void combine_load_costs(std::map< std::string, Expr > &result, const std::map< std::string, Expr > &partial)
Add partial load costs to the corresponding function in the result costs.
Halide::Internal::Call::args
std::vector< Expr > args
Definition: IR.h:466
Halide::Internal::Function
A reference-counted handle to Halide's internal representation of a function.
Definition: Function.h:38
Halide::Internal::Call
A function call.
Definition: IR.h:464
Halide::Internal::get_stage_bounds
DimBounds get_stage_bounds(const Function &f, int stage_num, const DimBounds &pure_bounds)
Return the required bounds of an intermediate stage (f, stage_num) of function 'f' given the bounds o...
Halide::Internal::disp_regions
void disp_regions(const std::map< std::string, Box > &regions)
Helper function to print the bounds of a region.
Halide::Expr
A fragment of Halide syntax.
Definition: Expr.h:256
Interval.h
Halide::Internal::Call::call_type
CallType call_type
Definition: IR.h:475
Halide::Internal::inline_all_element_wise_functions
bool inline_all_element_wise_functions(const std::vector< Function > &outputs, const std::vector< std::string > &order, const std::map< std::string, Function > &env)
Inline a Func if its values are only consumed by another single Func in element-wise manner.
Halide::Internal::propagate_estimate_test
void propagate_estimate_test()
Halide::Internal::string_to_int
int string_to_int(const std::string &s)
Return an int representation of 's'.
Halide::Internal::Box
Represents the bounds of a region of arbitrary dimension.
Definition: Bounds.h:53
Halide::Internal::get_stage_definition
Definition get_stage_definition(const Function &f, int stage_num)
Return the corresponding definition of a function given the stage.