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 ELK_IR_ANALYSIS_H 26 #define ELK_IR_ANALYSIS_H 27 28 namespace elk { 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 * elk::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 elk_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 */ elk_analysis(const C * c)141 elk_analysis(const C *c) : c(c), p(NULL) {} 142 elk_analysis(const elk_analysis &) = delete; 143 144 /** 145 * Destroy a program analysis. 146 */ ~elk_analysis()147 ~elk_analysis() 148 { 149 delete p; 150 } 151 152 elk_analysis & operator=(const elk_analysis &) = delete; 153 154 /** 155 * Obtain the result of a program analysis. This gives a 156 * guaranteed up-to-date result, the analysis pass will be 157 * rerun implicitly if it has become stale. 158 */ 159 T & require()160 require() 161 { 162 if (p) 163 assert(p->validate(c)); 164 else 165 p = new T(c); 166 167 return *p; 168 } 169 170 const T & require()171 require() const 172 { 173 return const_cast<elk_analysis<T, C> *>(this)->require(); 174 } 175 176 /** 177 * Report that dependencies of the analysis pass may have changed 178 * since the last calculation and the cached analysis result may 179 * have to be discarded. 180 */ 181 void invalidate(elk::analysis_dependency_class c)182 invalidate(elk::analysis_dependency_class c) 183 { 184 if (p && (c & p->dependency_class())) { 185 delete p; 186 p = NULL; 187 } 188 } 189 190 private: 191 const C *c; 192 T *p; 193 }; 194 195 #endif 196