Halide  12.0.1
Halide compiler and libraries
Cache.h
Go to the documentation of this file.
1 #ifndef BLOCK_CACHE_H
2 #define BLOCK_CACHE_H
3 
4 #include "ASLog.h"
5 #include "CostModel.h"
6 #include "Featurization.h"
7 #include "FunctionDAG.h"
8 #include "Halide.h"
9 #include "LoopNest.h"
10 #include "PerfectHashMap.h"
11 
12 namespace Halide {
13 namespace Internal {
14 namespace Autoscheduler {
15 
16 /*
17  The adams2019 autoscheduler has two caching implementations within its schedule search:
18 
19  1) Block (or tile) caching: handled by this file and Cache.cpp. If block caching is enabled
20  the below data structure (Cache) is used to save the tilings that have been generated at prior
21  passes of beam search. This allows for faster children generation when tiling is a scheduling
22  option. As noted below, this cache is a mapping of the form: Node -> vector_dim -> vector<tiled LoopNest>.
23 
24  2) Featurization caching: handled within a LoopNest. The featurization of a LoopNest is used at
25  multiple points in beam search (i.e. whenever the featurization of a child LoopNest is computed),
26  so it is useful to not repeatedly calculate featurizations. As noted in LoopNest.h, this mapping
27  is of the form: (structural hash of producers) -> (StageMap of schedule features). Note that not
28  all features can be safely cached (i.e. inlined features), so some must be recomputed (see
29  LoopNest::recompute_inlined_features).
30 
31  Important changes that caching impacts, outside of this file and Cache.cpp:
32 
33  - LoopNest::compute_features
34  If cache_features is enabled (i.e. HL_DISABLE_MEMOIZED_FEATURES!=1) then this function caches
35  the featurizations of its children, and if called again, reuses those cached featurizations.
36  The features are saved in a LoopNest's member, std::map<> features_cache. Some features do not
37  persist, and the FeaturesIntermediates struct (see Featurization.h) is used to cache useful
38  values that aid in recomputing such features.
39 
40  - LoopNest::compute_working_set_from_features
41  Used to re-compute the working_set from cached features.
42 
43  - LoopNest::recompute_inlined_features
44  Recursively recomputes the features of all inlined Funcs based on the cached FeaturesIntermediates
45  struct.
46 
47  - LoopNest::compute_hash_of_producers_stored_at_root
48  Computes a structural hash for use in feature caching in a LoopNest.
49 
50  - LoopNest::collect_producers
51  Collects all producers for a LoopNest for use in calculating the structural hash in
52  LoopNest::compute_hash_of_producers_stored_at_root.
53 
54  - LoopNest::collect_stages
55  Collects all stages referenced by a LoopNest for use in LoopNest::collect_producers.
56 
57  - State::compute_featurization
58  Calculates and stores hash_of_producers_stored_at_root for each child if feature caching
59  is enabled.
60 
61  - State::generate_children
62  If block caching is enabled, and tilings for this States have been cached in the Cache object,
63  then tilings are not generated again, and the cached tilings are used instead. See
64  Cache::add_memoized_blocks below (and in Cache.cpp).
65  Additionally, if a tiling has not been cached, and it is not pruned, then the tiling will be
66  cached using Cache::memoize_blocks (see below and in Cache.cpp).
67 */
68 
69 struct State;
70 
71 // true unless HL_DISABLE_MEMOIZED_FEATURES=1
73 
74 // true unless HL_DISABLE_MEMOIZED_BLOCKS=1
76 
77 /*
78 Object stores caching options for autoscheduling.
79 cache_blocks: decides if tilings are cached for decisions related to parallelizing the loops of a Func.
80 cache_features: decides if LoopNest::compute_features will cache / will use cached featurizations.
81 */
83  bool cache_blocks = false;
84  bool cache_features = false;
85 
87  CachingOptions options;
90  return options;
91  }
92 };
93 
94 // Node -> (vector_dim -> vector<tiled LoopNest>)
96 
97 // Cache for memoizing possible tilings.
98 // Tracks hit/miss statistics for both block caching
99 // and for feature caching (self-contained by LoopNests).
100 struct Cache {
103 
104  mutable size_t cache_hits = 0;
105  mutable size_t cache_misses = 0;
106 
107  Cache() = delete;
108  Cache(const CachingOptions &_options, size_t nodes_size)
109  : options(_options) {
110  if (options.cache_blocks) {
112  }
113  }
114 
115  ~Cache() = default;
116 
117  // check if we generated tilings for the current func on a previous pass
118  // if so, add them and return true.
119  // otherwise, return false (also return false if memoization is turned off).
120  bool add_memoized_blocks(const State *state,
121  std::function<void(IntrusivePtr<State> &&)> &accept_child,
122  const FunctionDAG::Node *node,
123  int &num_children,
124  const FunctionDAG &dag,
125  const MachineParams &params,
126  CostModel *cost_model,
127  int64_t memory_limit) const;
128 
129  // Generate tilings for a specific vector dimension and memoize them.
130  void memoize_blocks(const FunctionDAG::Node *node, LoopNest *new_root);
131 };
132 
133 } // namespace Autoscheduler
134 } // namespace Internal
135 } // namespace Halide
136 
137 #endif // BLOCK_CACHE_H
void make_large(int n)
This file defines the class FunctionDAG, which is our representation of a Halide pipeline,...
@ Internal
Not visible externally, similar to 'static' linkage in C.
signed __INT64_TYPE__ int64_t
bool add_memoized_blocks(const State *state, std::function< void(IntrusivePtr< State > &&)> &accept_child, const FunctionDAG::Node *node, int &num_children, const FunctionDAG &dag, const MachineParams &params, CostModel *cost_model, int64_t memory_limit) const
Cache(const CachingOptions &_options, size_t nodes_size)
Definition: Cache.h:108
void memoize_blocks(const FunctionDAG::Node *node, LoopNest *new_root)
static CachingOptions MakeOptionsFromEnviron()
Definition: Cache.h:86
Intrusive shared pointers have a reference count (a RefCount object) stored in the class itself.
Definition: IntrusivePtr.h:68
A struct representing the machine parameters to generate the auto-scheduled code for.
Definition: Pipeline.h:31