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
28namespace 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 */
133template<class T, class C>
134class brw_analysis {
135public:
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    */
141   brw_analysis(const C *c) : c(c), p(NULL) {}
142
143   /**
144    * Destroy a program analysis.
145    */
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 &
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 &
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
179   invalidate(brw::analysis_dependency_class c)
180   {
181      if (p && (c & p->dependency_class())) {
182         delete p;
183         p = NULL;
184      }
185   }
186
187private:
188   const C *c;
189   T *p;
190};
191
192#endif
193