optimize.h

   1 #ifndef MSP_GL_SL_OPTIMIZE_H_
   2 #define MSP_GL_SL_OPTIMIZE_H_
   3
   4 #include <map>
   5 #include <set>
   6 #include "visitor.h"
   7
   8 namespace Msp {
   9 namespace GL {
  10 namespace SL {
  11
  12 /** Assigns values to specialization constants, turning them into normal
  13 constants. */
  14 class ConstantSpecializer: private TraversingVisitor
  15 {
  16 private:
  17         const std::map<std::string, int> *values;
  18
  19 public:
  20         ConstantSpecializer();
  21
  22         void apply(Stage &, const std::map<std::string, int> &);
  23
  24 private:
  25         virtual void visit(VariableDeclaration &);
  26 };
  27
  28 /** Finds functions which are candidates for inlining.  Currently this means
  29 functions which have no flow control statements, no more than one return
  30 statement, and are either builtins or only called once. */
  31 class InlineableFunctionLocator: private TraversingVisitor
  32 {
  33 private:
  34         std::map<FunctionDeclaration *, unsigned> refcounts;
  35         std::set<FunctionDeclaration *> inlineable;
  36         FunctionDeclaration *current_function;
  37         unsigned return_count;
  38
  39 public:
  40         InlineableFunctionLocator();
  41
  42         std::set<FunctionDeclaration *> apply(Stage &s) { s.content.visit(*this); return inlineable; }
  43
  44 private:
  45         virtual void visit(FunctionCall &);
  46         virtual void visit(FunctionDeclaration &);
  47         virtual void visit(Conditional &);
  48         virtual void visit(Iteration &);
  49         virtual void visit(Return &);
  50 };
  51
  52 /** Injects statements from one function into another.  Local variables are
  53 renamed to avoid conflicts.  After inlining, uses NodeReorderer to cause
  54 dependencies of the inlined statements to appear before the target function. */
  55 class InlineContentInjector: private TraversingVisitor
  56 {
  57 private:
  58         enum Pass
  59         {
  60                 REFERENCED,
  61                 INLINE,
  62                 RENAME
  63         };
  64
  65         FunctionDeclaration *source_func;
  66         Block staging_block;
  67         Pass pass;
  68         RefPtr<Statement> r_inlined_statement;
  69         std::set<Node *> dependencies;
  70         std::set<std::string> referenced_names;
  71         std::string r_result_name;
  72
  73 public:
  74         InlineContentInjector();
  75
  76         std::string apply(Stage &, FunctionDeclaration &, Block &, const NodeList<Statement>::iterator &, FunctionCall &);
  77
  78 private:
  79         virtual void visit(VariableReference &);
  80         virtual void visit(InterfaceBlockReference &);
  81         virtual void visit(FunctionCall &);
  82         virtual void visit(VariableDeclaration &);
  83         virtual void visit(Return &);
  84 };
  85
  86 /** Inlines functions.  Internally uses InlineableFunctionLocator to find
  87 candidate functions.  Only functions which consist of a single return statement
  88 are inlined. */
  89 class FunctionInliner: private TraversingVisitor
  90 {
  91 private:
  92         Stage *stage;
  93         std::set<FunctionDeclaration *> inlineable;
  94         FunctionDeclaration *current_function;
  95         NodeList<Statement>::iterator insert_point;
  96         RefPtr<Expression> r_inline_result;
  97         bool r_any_inlined;
  98         bool r_inlined_here;
  99
 100 public:
 101         FunctionInliner();
 102
 103         bool apply(Stage &);
 104
 105 private:
 106         virtual void visit(RefPtr<Expression> &);
 107         virtual void visit(Block &);
 108         virtual void visit(FunctionCall &);
 109         virtual void visit(FunctionDeclaration &);
 110         virtual void visit(Iteration &);
 111 };
 112
 113 /** Inlines variables into expressions.  Variables with trivial values (those
 114 consisting of a single literal or variable reference) are always inlined.
 115 Variables which are only referenced once are also inlined. */
 116 class ExpressionInliner: private TraversingVisitor
 117 {
 118 private:
 119         struct ExpressionUse
 120         {
 121                 RefPtr<Expression> *reference;
 122                 Block *ref_scope;
 123                 bool blocked;
 124
 125                 ExpressionUse(): reference(0), ref_scope(0), blocked(false) { }
 126         };
 127
 128         struct ExpressionInfo
 129         {
 130                 Assignment::Target target;
 131                 RefPtr<Expression> expression;
 132                 Block *assign_scope;
 133                 std::vector<ExpressionUse> uses;
 134                 bool trivial;
 135
 136                 ExpressionInfo(): expression(0), assign_scope(0), trivial(false) { }
 137         };
 138
 139         std::list<ExpressionInfo> expressions;
 140         std::map<Assignment::Target, ExpressionInfo *> assignments;
 141         ExpressionInfo *r_ref_info;
 142         bool r_trivial;
 143         bool access_read;
 144         bool access_write;
 145         bool iteration_init;
 146         Block *iteration_body;
 147         const Operator *r_oper;
 148
 149 public:
 150         ExpressionInliner();
 151
 152         bool apply(Stage &);
 153
 154 private:
 155         virtual void visit(RefPtr<Expression> &);
 156         virtual void visit(VariableReference &);
 157         virtual void visit(MemberAccess &);
 158         virtual void visit(Swizzle &);
 159         virtual void visit(UnaryExpression &);
 160         virtual void visit(BinaryExpression &);
 161         virtual void visit(Assignment &);
 162         virtual void visit(TernaryExpression &);
 163         virtual void visit(FunctionCall &);
 164         virtual void visit(VariableDeclaration &);
 165         virtual void visit(Iteration &);
 166 };
 167
 168 /** Replaces expressions consisting entirely of literals with the results of
 169 evaluating the expression.*/
 170 class ConstantFolder: private TraversingVisitor
 171 {
 172 private:
 173         VariableDeclaration *iteration_var;
 174         Variant iter_init_value;
 175         Variant r_constant_value;
 176         bool iteration_init;
 177         bool r_constant;
 178         bool r_literal;
 179         bool r_uses_iter_var;
 180         bool r_any_folded;
 181
 182 public:
 183         bool apply(Stage &s) { s.content.visit(*this); return r_any_folded; }
 184
 185 private:
 186         template<typename T>
 187         static T evaluate_logical(char, T, T);
 188         template<typename T>
 189         static bool evaluate_relation(const char *, T, T);
 190         template<typename T>
 191         static T evaluate_arithmetic(char, T, T);
 192         template<typename T>
 193         static T evaluate_int_special_op(char, T, T);
 194         template<typename T>
 195         void convert_to_result(const Variant &);
 196         void set_result(const Variant &, bool = false);
 197
 198         virtual void visit(RefPtr<Expression> &);
 199         virtual void visit(Literal &);
 200         virtual void visit(VariableReference &);
 201         virtual void visit(MemberAccess &);
 202         virtual void visit(Swizzle &);
 203         virtual void visit(UnaryExpression &);
 204         virtual void visit(BinaryExpression &);
 205         virtual void visit(Assignment &);
 206         virtual void visit(TernaryExpression &);
 207         virtual void visit(FunctionCall &);
 208         virtual void visit(VariableDeclaration &);
 209         virtual void visit(Iteration &);
 210 };
 211
 212 /** Removes conditional statements and loops where the condition can be
 213 determined as constant at compile time. */
 214 class ConstantConditionEliminator: private TraversingVisitor
 215 {
 216 private:
 217         enum ConstantStatus
 218         {
 219                 CONSTANT_FALSE,
 220                 CONSTANT_TRUE,
 221                 NOT_CONSTANT
 222         };
 223
 224         NodeList<Statement>::iterator insert_point;
 225         std::set<Node *> nodes_to_remove;
 226         RefPtr<Expression> r_ternary_result;
 227
 228 public:
 229         void apply(Stage &);
 230
 231 private:
 232         ConstantStatus check_constant_condition(const Expression &);
 233
 234         virtual void visit(Block &);
 235         virtual void visit(RefPtr<Expression> &);
 236         virtual void visit(TernaryExpression &);
 237         virtual void visit(Conditional &);
 238         virtual void visit(Iteration &);
 239 };
 240
 241 class UnreachableCodeRemover: private TraversingVisitor
 242 {
 243 private:
 244         bool reachable;
 245         std::set<Node *> unreachable_nodes;
 246
 247 public:
 248         UnreachableCodeRemover();
 249
 250         virtual bool apply(Stage &);
 251
 252 private:
 253         virtual void visit(Block &);
 254         virtual void visit(FunctionDeclaration &);
 255         virtual void visit(Conditional &);
 256         virtual void visit(Iteration &);
 257         virtual void visit(Return &) { reachable = false; }
 258         virtual void visit(Jump &) { reachable = false; }
 259 };
 260
 261 /** Removes types which are not used anywhere. */
 262 class UnusedTypeRemover: private TraversingVisitor
 263 {
 264 private:
 265         std::set<Node *> unused_nodes;
 266
 267 public:
 268         bool apply(Stage &);
 269
 270 private:
 271         virtual void visit(RefPtr<Expression> &);
 272         virtual void visit(BasicTypeDeclaration &);
 273         virtual void visit(ImageTypeDeclaration &);
 274         virtual void visit(StructDeclaration &);
 275         virtual void visit(VariableDeclaration &);
 276         virtual void visit(InterfaceBlock &);
 277         virtual void visit(FunctionDeclaration &);
 278 };
 279
 280 /** Removes variable declarations with no references to them.  Assignment
 281 statements where the result is not used are also removed. */
 282 class UnusedVariableRemover: private TraversingVisitor
 283 {
 284 private:
 285         struct AssignmentInfo
 286         {
 287                 Node *node;
 288                 Assignment::Target target;
 289                 std::vector<Node *> used_by;
 290                 unsigned in_loop;
 291
 292                 AssignmentInfo(): node(0) { }
 293         };
 294
 295         struct VariableInfo
 296         {
 297                 InterfaceBlock *interface_block;
 298                 std::vector<AssignmentInfo *> assignments;
 299                 bool initialized;
 300                 bool output;
 301                 bool referenced;
 302
 303                 VariableInfo(): interface_block(0), initialized(false), output(false), referenced(false) { }
 304         };
 305
 306         typedef std::map<Statement *, VariableInfo> BlockVariableMap;
 307
 308         Stage *stage;
 309         BlockVariableMap variables;
 310         std::list<AssignmentInfo> assignments;
 311         InterfaceBlock *interface_block;
 312         Assignment *r_assignment;
 313         bool assignment_target;
 314         bool r_side_effects;
 315         bool in_struct;
 316         bool composite_reference;
 317         unsigned in_loop;
 318         std::vector<Node *> loop_ext_refs;
 319         Assignment::Target r_reference;
 320         std::set<Node *> unused_nodes;
 321
 322 public:
 323         UnusedVariableRemover();
 324
 325         bool apply(Stage &);
 326
 327 private:
 328         void referenced(const Assignment::Target &, Node &);
 329         virtual void visit(VariableReference &);
 330         virtual void visit(InterfaceBlockReference &);
 331         void visit_composite(Expression &);
 332         virtual void visit(MemberAccess &);
 333         virtual void visit(Swizzle &);
 334         virtual void visit(UnaryExpression &);
 335         virtual void visit(BinaryExpression &);
 336         virtual void visit(Assignment &);
 337         virtual void visit(TernaryExpression &);
 338         virtual void visit(FunctionCall &);
 339         void record_assignment(const Assignment::Target &, Node &);
 340         virtual void visit(ExpressionStatement &);
 341         virtual void visit(StructDeclaration &);
 342         virtual void visit(VariableDeclaration &);
 343         virtual void visit(InterfaceBlock &);
 344         void merge_variables(const BlockVariableMap &);
 345         virtual void visit(FunctionDeclaration &);
 346         virtual void visit(Conditional &);
 347         virtual void visit(Iteration &);
 348 };
 349
 350 /** Removes function declarations with no references to them. */
 351 class UnusedFunctionRemover: private TraversingVisitor
 352 {
 353 private:
 354         std::set<Node *> unused_nodes;
 355         std::set<FunctionDeclaration *> used_definitions;
 356
 357 public:
 358         bool apply(Stage &s);
 359
 360 private:
 361         virtual void visit(FunctionCall &);
 362         virtual void visit(FunctionDeclaration &);
 363 };
 364
 365 } // namespace SL
 366 } // namespace GL
 367 } // namespace Msp
 368
 369 #endif