1 /* -*- c++ -*- */
2 /*
3  * Copyright © 2016 Intel Corporation
4  *
5  * Permission is hereby granted, free of charge, to any person obtaining a
6  * copy of this software and associated documentation files (the "Software"),
7  * to deal in the Software without restriction, including without limitation
8  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
9  * and/or sell copies of the Software, and to permit persons to whom the
10  * Software is furnished to do so, subject to the following conditions:
11  *
12  * The above copyright notice and this permission notice (including the next
13  * paragraph) shall be included in all copies or substantial portions of the
14  * Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
19  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
22  * IN THE SOFTWARE.
23  */
24 
25 #ifndef BRW_IR_ANALYSIS_H
26 #define BRW_IR_ANALYSIS_H
27 
28 namespace brw {
29    /**
30     * Bitset of state categories that can influence the result of IR analysis
31     * passes.
32     */
33    enum analysis_dependency_class {
34       /**
35        * The analysis doesn't depend on the IR, its result is effectively a
36        * constant during the compilation.
37        */
38       DEPENDENCY_NOTHING = 0,
39       /**
40        * The analysis depends on the set of instructions in the program and
41        * their naming.  Note that because instructions are named sequentially
42        * by IP this implies a dependency on the control flow edges between
43        * instructions.  This will be signaled whenever instructions are
44        * inserted, removed or reordered in the program.
45        */
46       DEPENDENCY_INSTRUCTION_IDENTITY = 0x1,
47       /**
48        * The analysis is sensitive to the detailed semantics of instructions
49        * in the program, where "detailed" means any change in the instruction
50        * data structures other than the linked-list pointers (which are
51        * already covered by DEPENDENCY_INSTRUCTION_IDENTITY).  E.g. changing
52        * the negate or abs flags of an instruction source would signal this
53        * flag alone because it would preserve all other instruction dependency
54        * classes.
55        */
56       DEPENDENCY_INSTRUCTION_DETAIL = 0x2,
57       /**
58        * The analysis depends on the set of data flow edges between
59        * instructions.  This will be signaled whenever the dataflow relation
60        * between instructions has potentially changed, e.g. when the VGRF
61        * index of an instruction source or destination changes (in which case
62        * it will appear in combination with DEPENDENCY_INSTRUCTION_DETAIL), or
63        * when data-dependent instructions are reordered (in which case it will
64        * appear in combination with DEPENDENCY_INSTRUCTION_IDENTITY).
65        */
66       DEPENDENCY_INSTRUCTION_DATA_FLOW = 0x4,
67       /**
68        * The analysis depends on all instruction dependency classes.  These
69        * will typically be signaled simultaneously when inserting or removing
70        * instructions in the program (or if you're feeling too lazy to read
71        * through your optimization pass to figure out which of the instruction
72        * dependency classes above it invalidates).
73        */
74       DEPENDENCY_INSTRUCTIONS = 0x7,
75       /**
76        * The analysis depends on the set of VGRFs in the program and their
77        * naming.  This will be signaled when VGRFs are allocated or released.
78        */
79       DEPENDENCY_VARIABLES = 0x8,
80       /**
81        * The analysis depends on the set of basic blocks in the program, their
82        * control flow edges and naming.
83        */
84       DEPENDENCY_BLOCKS = 0x10,
85       /**
86        * The analysis depends on the program being literally the same (good
87        * luck...), any change in the input invalidates previous analysis
88        * computations.
89        */
90       DEPENDENCY_EVERYTHING = ~0
91    };
92 
93    inline analysis_dependency_class
94    operator|(analysis_dependency_class x, analysis_dependency_class y)
95    {
96       return static_cast<analysis_dependency_class>(
97          static_cast<unsigned>(x) | static_cast<unsigned>(y));
98    }
99 }
100 
101 /**
102  * Instantiate a program analysis class \p L which can calculate an object of
103  * type \p T as result.  \p C is a closure that encapsulates whatever
104  * information is required as argument to run the analysis pass.  The purpose
105  * of this class is to make sure that:
106  *
107  *  - The analysis pass is executed lazily whenever it's needed and multiple
108  *    executions are optimized out as long as the cached result remains marked
109  *    up-to-date.
110  *
111  *  - There is no way to access the cached analysis result without first
112  *    calling L::require(), which makes sure that the analysis pass is rerun
113  *    if necessary.
114  *
115  *  - The cached result doesn't become inconsistent with the program for as
116  *    long as it remains marked up-to-date. (This is only enforced in debug
117  *    builds for performance reasons)
118  *
119  * The requirements on \p T are the following:
120  *
121  *  - Constructible with a single argument, as in 'x = T(c)' for \p c of type
122  *    \p C.
123  *
124  *  - 'x.dependency_class()' on const \p x returns a bitset of
125  *    brw::analysis_dependency_class specifying the set of IR objects that are
126  *    required to remain invariant for the cached analysis result to be
127  *    considered valid.
128  *
129  *  - 'x.validate(c)' on const \p x returns a boolean result specifying
130  *    whether the analysis result \p x is consistent with the input IR.  This
131  *    is currently only used for validation in debug builds.
132  */
133 template<class T, class C>
134 class brw_analysis {
135 public:
136    /**
137     * Construct a program analysis.  \p c is an arbitrary object
138     * passed as argument to the constructor of the analysis result
139     * object of type \p T.
140     */
brw_analysis(const C * c)141    brw_analysis(const C *c) : c(c), p(NULL) {}
142 
143    /**
144     * Destroy a program analysis.
145     */
~brw_analysis()146    ~brw_analysis()
147    {
148       delete p;
149    }
150 
151    /**
152     * Obtain the result of a program analysis.  This gives a
153     * guaranteed up-to-date result, the analysis pass will be
154     * rerun implicitly if it has become stale.
155     */
156    T &
require()157    require()
158    {
159       if (p)
160          assert(p->validate(c));
161       else
162          p = new T(c);
163 
164       return *p;
165    }
166 
167    const T &
require()168    require() const
169    {
170       return const_cast<brw_analysis<T, C> *>(this)->require();
171    }
172 
173    /**
174     * Report that dependencies of the analysis pass may have changed
175     * since the last calculation and the cached analysis result may
176     * have to be discarded.
177     */
178    void
invalidate(brw::analysis_dependency_class c)179    invalidate(brw::analysis_dependency_class c)
180    {
181       if (p && (c & p->dependency_class())) {
182          delete p;
183          p = NULL;
184       }
185    }
186 
187 private:
188    const C *c;
189    T *p;
190 };
191 
192 #endif
193