Halide 14.0.0
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
12namespace Halide {
13namespace Internal {
14namespace 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
69struct State;
70
71// true unless HL_DISABLE_MEMOIZED_FEATURES=1
73
74// true unless HL_DISABLE_MEMOIZED_BLOCKS=1
76
77/*
78Object stores caching options for autoscheduling.
79cache_blocks: decides if tilings are cached for decisions related to parallelizing the loops of a Func.
80cache_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).
100struct 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:33