source/glsl/optimize.cpp

   1 #include <msp/core/raii.h>
   2 #include "optimize.h"
   3
   4 using namespace std;
   5
   6 namespace Msp {
   7 namespace GL {
   8 namespace SL {
   9
  10 InlineableFunctionLocator::InlineableFunctionLocator():
  11         in_function(0)
  12 { }
  13
  14 void InlineableFunctionLocator::visit(FunctionCall &call)
  15 {
  16         FunctionDeclaration *def = call.declaration;
  17         if(def && def->definition!=def)
  18                 def = def->definition;
  19
  20         if(def)
  21         {
  22                 unsigned &count = refcounts[def];
  23                 ++count;
  24                 if(count>1 || def==in_function)
  25                         inlineable.erase(def);
  26         }
  27
  28         TraversingVisitor::visit(call);
  29 }
  30
  31 void InlineableFunctionLocator::visit(FunctionDeclaration &func)
  32 {
  33         unsigned &count = refcounts[func.definition];
  34         if(!count && func.parameters.empty())
  35                 inlineable.insert(func.definition);
  36
  37         SetForScope<FunctionDeclaration *> set(in_function, &func);
  38         TraversingVisitor::visit(func);
  39 }
  40
  41
  42 FunctionInliner::FunctionInliner():
  43         extract_result(0)
  44 { }
  45
  46 FunctionInliner::FunctionInliner(const set<FunctionDeclaration *> &in):
  47         inlineable(in),
  48         extract_result(0)
  49 { }
  50
  51 void FunctionInliner::visit_and_inline(RefPtr<Expression> &ptr)
  52 {
  53         inline_result = 0;
  54         ptr->visit(*this);
  55         if(inline_result)
  56                 ptr = inline_result;
  57 }
  58
  59 void FunctionInliner::visit(Block &block)
  60 {
  61         if(extract_result)
  62                 --extract_result;
  63
  64         for(NodeList<Statement>::iterator i=block.body.begin(); i!=block.body.end(); ++i)
  65         {
  66                 (*i)->visit(*this);
  67                 if(extract_result)
  68                         --extract_result;
  69         }
  70 }
  71
  72 void FunctionInliner::visit(UnaryExpression &unary)
  73 {
  74         visit_and_inline(unary.expression);
  75         inline_result = 0;
  76 }
  77
  78 void FunctionInliner::visit(BinaryExpression &binary)
  79 {
  80         visit_and_inline(binary.left);
  81         visit_and_inline(binary.right);
  82         inline_result = 0;
  83 }
  84
  85 void FunctionInliner::visit(MemberAccess &memacc)
  86 {
  87         visit_and_inline(memacc.left);
  88         inline_result = 0;
  89 }
  90
  91 void FunctionInliner::visit(FunctionCall &call)
  92 {
  93         for(NodeArray<Expression>::iterator i=call.arguments.begin(); i!=call.arguments.end(); ++i)
  94                 visit_and_inline(*i);
  95
  96         FunctionDeclaration *def = call.declaration;
  97         if(def && def->definition!=def)
  98                 def = def->definition;
  99
 100         if(def && inlineable.count(def))
 101         {
 102                 extract_result = 2;
 103                 def->visit(*this);
 104         }
 105         else
 106                 inline_result = 0;
 107 }
 108
 109 void FunctionInliner::visit(VariableDeclaration &var)
 110 {
 111         if(var.init_expression)
 112                 visit_and_inline(var.init_expression);
 113         inline_result = 0;
 114 }
 115
 116 void FunctionInliner::visit(Return &ret)
 117 {
 118         TraversingVisitor::visit(ret);
 119
 120         if(extract_result)
 121                 inline_result = ret.expression->clone();
 122 }
 123
 124
 125 ConstantConditionEliminator::ConstantConditionEliminator():
 126         scope_level(0),
 127         record_only(false)
 128 { }
 129
 130 void ConstantConditionEliminator::visit(Block &block)
 131 {
 132         SetForScope<unsigned> set(scope_level, scope_level+1);
 133         BlockModifier::visit(block);
 134
 135         for(map<string, VariableDeclaration *>::const_iterator i=block.variables.begin(); i!=block.variables.end(); ++i)
 136                 variable_values.erase(i->second);
 137 }
 138
 139 void ConstantConditionEliminator::visit(UnaryExpression &unary)
 140 {
 141         if(VariableReference *var = dynamic_cast<VariableReference *>(unary.expression.get()))
 142                 if(unary.oper=="++" || unary.oper=="--")
 143                         variable_values.erase(var->declaration);
 144 }
 145
 146 void ConstantConditionEliminator::visit(Assignment &assign)
 147 {
 148         variable_values.erase(assign.target_declaration);
 149 }
 150
 151 void ConstantConditionEliminator::visit(VariableDeclaration &var)
 152 {
 153         if(var.constant || scope_level>1)
 154                 variable_values[&var] = var.init_expression.get();
 155 }
 156
 157 void ConstantConditionEliminator::visit(Conditional &cond)
 158 {
 159         if(!record_only)
 160         {
 161                 ExpressionEvaluator eval(variable_values);
 162                 cond.condition->visit(eval);
 163                 if(eval.is_result_valid())
 164                 {
 165                         flatten_block(eval.get_result() ? cond.body : cond.else_body);
 166                         return;
 167                 }
 168         }
 169
 170         TraversingVisitor::visit(cond);
 171 }
 172
 173 void ConstantConditionEliminator::visit(Iteration &iter)
 174 {
 175         if(!record_only)
 176         {
 177                 if(iter.condition)
 178                 {
 179                         /* If the loop condition is always false on the first iteration, the
 180                         entire loop can be removed */
 181                         if(iter.init_statement)
 182                                 iter.init_statement->visit(*this);
 183                         ExpressionEvaluator eval(variable_values);
 184                         iter.condition->visit(eval);
 185                         if(eval.is_result_valid() && !eval.get_result())
 186                         {
 187                                 remove_node = true;
 188                                 return;
 189                         }
 190                 }
 191
 192                 /* Record all assignments that occur inside the loop body so those
 193                 variables won't be considered as constant */
 194                 SetFlag set_record(record_only);
 195                 TraversingVisitor::visit(iter);
 196         }
 197
 198         TraversingVisitor::visit(iter);
 199
 200         if(VariableDeclaration *init_decl = dynamic_cast<VariableDeclaration *>(iter.init_statement.get()))
 201                 variable_values.erase(init_decl);
 202 }
 203
 204
 205 UnusedVariableLocator::VariableInfo::VariableInfo():
 206         local(false),
 207         conditionally_assigned(false),
 208         referenced(false)
 209 { }
 210
 211
 212 UnusedVariableLocator::UnusedVariableLocator():
 213         aggregate(0),
 214         assignment(0),
 215         assignment_target(false),
 216         assign_to_subscript(false),
 217         global_scope(true)
 218 { }
 219
 220 const set<Node *> &UnusedVariableLocator::apply(Stage &s)
 221 {
 222         variables.push_back(BlockVariableMap());
 223         visit(s.content);
 224         BlockVariableMap &global_variables = variables.back();
 225         for(BlockVariableMap::iterator i=global_variables.begin(); i!=global_variables.end(); ++i)
 226         {
 227                 if(i->first->interface=="out" && (s.type==Stage::FRAGMENT || i->first->linked_declaration || !i->first->name.compare(0, 3, "gl_")))
 228                         continue;
 229                 if(!i->second.referenced)
 230                 {
 231                         unused_nodes.insert(i->first);
 232                         clear_assignments(i->second, true);
 233                 }
 234         }
 235         variables.pop_back();
 236
 237         return unused_nodes;
 238 }
 239
 240 void UnusedVariableLocator::visit(VariableReference &var)
 241 {
 242         map<VariableDeclaration *, Node *>::iterator i = aggregates.find(var.declaration);
 243         if(i!=aggregates.end())
 244                 unused_nodes.erase(i->second);
 245
 246         if(var.declaration && !assignment_target)
 247         {
 248                 VariableInfo &var_info = variables.back()[var.declaration];
 249                 var_info.assignments.clear();
 250                 var_info.referenced = true;
 251         }
 252 }
 253
 254 void UnusedVariableLocator::visit(MemberAccess &memacc)
 255 {
 256         TraversingVisitor::visit(memacc);
 257         unused_nodes.erase(memacc.declaration);
 258 }
 259
 260 void UnusedVariableLocator::visit(BinaryExpression &binary)
 261 {
 262         if(binary.oper=="[")
 263         {
 264                 if(assignment_target)
 265                         assign_to_subscript = true;
 266                 binary.left->visit(*this);
 267                 SetForScope<bool> set(assignment_target, false);
 268                 binary.right->visit(*this);
 269         }
 270         else
 271                 TraversingVisitor::visit(binary);
 272 }
 273
 274 void UnusedVariableLocator::visit(Assignment &assign)
 275 {
 276         {
 277                 assign_to_subscript = false;
 278                 SetForScope<bool> set(assignment_target, !assign.self_referencing);
 279                 assign.left->visit(*this);
 280         }
 281         assign.right->visit(*this);
 282         assignment = &assign;
 283 }
 284
 285 void UnusedVariableLocator::record_assignment(VariableDeclaration &var, Node &node, bool chained)
 286 {
 287         VariableInfo &var_info = variables.back()[&var];
 288         if(!chained)
 289                 clear_assignments(var_info, true);
 290         var_info.assignments.push_back(&node);
 291         var_info.conditionally_assigned = false;
 292 }
 293
 294 void UnusedVariableLocator::clear_assignments(VariableInfo &var_info, bool mark_unused)
 295 {
 296         if(mark_unused)
 297         {
 298                 for(vector<Node *>::iterator i=var_info.assignments.begin(); i!=var_info.assignments.end(); ++i)
 299                         unused_nodes.insert(*i);
 300         }
 301         var_info.assignments.clear();
 302 }
 303
 304 void UnusedVariableLocator::visit(ExpressionStatement &expr)
 305 {
 306         assignment = 0;
 307         TraversingVisitor::visit(expr);
 308         if(assignment && assignment->target_declaration)
 309                 record_assignment(*assignment->target_declaration, expr, (assignment->self_referencing || assign_to_subscript));
 310 }
 311
 312 void UnusedVariableLocator::visit(StructDeclaration &strct)
 313 {
 314         SetForScope<Node *> set(aggregate, &strct);
 315         unused_nodes.insert(&strct);
 316         TraversingVisitor::visit(strct);
 317 }
 318
 319 void UnusedVariableLocator::visit(VariableDeclaration &var)
 320 {
 321         if(aggregate)
 322                 aggregates[&var] = aggregate;
 323         else
 324         {
 325                 variables.back()[&var].local = true;
 326                 if(var.init_expression)
 327                         record_assignment(var, *var.init_expression, false);
 328         }
 329         unused_nodes.erase(var.type_declaration);
 330         TraversingVisitor::visit(var);
 331 }
 332
 333 void UnusedVariableLocator::visit(InterfaceBlock &iface)
 334 {
 335         SetForScope<Node *> set(aggregate, &iface);
 336         unused_nodes.insert(&iface);
 337         TraversingVisitor::visit(iface);
 338 }
 339
 340 void UnusedVariableLocator::visit(FunctionDeclaration &func)
 341 {
 342         variables.push_back(BlockVariableMap());
 343
 344         {
 345                 SetForScope<bool> set(global_scope, false);
 346                 for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 347                         (*i)->visit(*this);
 348                 func.body.visit(*this);
 349         }
 350
 351         BlockVariableMap &block_variables = variables.back();
 352         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 353                 i->second.conditionally_assigned = true;
 354         for(NodeArray<VariableDeclaration>::iterator i=func.parameters.begin(); i!=func.parameters.end(); ++i)
 355                 block_variables[i->get()].referenced = true;
 356         merge_down_variables();
 357 }
 358
 359 void UnusedVariableLocator::merge_down_variables()
 360 {
 361         BlockVariableMap &parent_variables = variables[variables.size()-2];
 362         BlockVariableMap &block_variables = variables.back();
 363         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 364         {
 365                 if(i->second.local)
 366                 {
 367                         if(!i->second.referenced)
 368                                 unused_nodes.insert(i->first);
 369                         clear_assignments(i->second, i->first->interface!="out");
 370                         continue;
 371                 }
 372
 373                 BlockVariableMap::iterator j = parent_variables.find(i->first);
 374                 if(j==parent_variables.end())
 375                         parent_variables.insert(*i);
 376                 else
 377                 {
 378                         if(i->second.referenced || !i->second.conditionally_assigned)
 379                                 clear_assignments(j->second, !i->second.referenced);
 380                         j->second.conditionally_assigned = i->second.conditionally_assigned;
 381                         j->second.referenced |= i->second.referenced;
 382                         j->second.assignments.insert(j->second.assignments.end(), i->second.assignments.begin(), i->second.assignments.end());
 383                 }
 384         }
 385         variables.pop_back();
 386 }
 387
 388 void UnusedVariableLocator::visit(Conditional &cond)
 389 {
 390         cond.condition->visit(*this);
 391         variables.push_back(BlockVariableMap());
 392         cond.body.visit(*this);
 393
 394         BlockVariableMap if_variables;
 395         swap(variables.back(), if_variables);
 396         cond.else_body.visit(*this);
 397
 398         BlockVariableMap &else_variables = variables.back();
 399         for(BlockVariableMap::iterator i=else_variables.begin(); i!=else_variables.end(); ++i)
 400         {
 401                 BlockVariableMap::iterator j = if_variables.find(i->first);
 402                 if(j!=if_variables.end())
 403                 {
 404                         i->second.assignments.insert(i->second.assignments.end(), j->second.assignments.begin(), j->second.assignments.end());
 405                         i->second.conditionally_assigned |= j->second.conditionally_assigned;
 406                         if_variables.erase(j);
 407                 }
 408                 else
 409                         i->second.conditionally_assigned = true;
 410         }
 411
 412         for(BlockVariableMap::iterator i=if_variables.begin(); i!=if_variables.end(); ++i)
 413         {
 414                 i->second.conditionally_assigned = true;
 415                 else_variables.insert(*i);
 416         }
 417
 418         merge_down_variables();
 419 }
 420
 421 void UnusedVariableLocator::visit(Iteration &iter)
 422 {
 423         variables.push_back(BlockVariableMap());
 424         TraversingVisitor::visit(iter);
 425
 426         BlockVariableMap &block_variables = variables.back();
 427         for(BlockVariableMap::iterator i=block_variables.begin(); i!=block_variables.end(); ++i)
 428                 if(!i->second.local && i->second.referenced)
 429                         i->second.assignments.clear();
 430
 431         merge_down_variables();
 432 }
 433
 434
 435 void UnusedFunctionLocator::visit(FunctionCall &call)
 436 {
 437         TraversingVisitor::visit(call);
 438
 439         unused_nodes.erase(call.declaration);
 440         if(call.declaration && call.declaration->definition!=call.declaration)
 441                 used_definitions.insert(call.declaration->definition);
 442 }
 443
 444 void UnusedFunctionLocator::visit(FunctionDeclaration &func)
 445 {
 446         TraversingVisitor::visit(func);
 447
 448         if((func.name!="main" || func.body.body.empty()) && !used_definitions.count(&func))
 449                 unused_nodes.insert(&func);
 450 }
 451
 452 } // namespace SL
 453 } // namespace GL
 454 } // namespace Msp