[Mesa-dev] [PATCH] Initial Common Subexpression Elimination implementation.
vljn
vljn at ovi.com
Sun Jul 17 12:29:32 PDT 2011
From: Vincent Lejeune <vljn at ovi.com>
The algorithm can spot non adjacent operands.
Limitations :
- only works on basic block
- only works on binary expressions
---
src/glsl/Makefile | 1 +
src/glsl/glsl_parser_extras.cpp | 7 +-
src/glsl/ir_optimization.h | 1 +
src/glsl/list.h | 4 +-
src/glsl/opt_common_subexpression_elimination.cpp | 665 +++++++++++++++++++++
5 files changed, 674 insertions(+), 4 deletions(-)
create mode 100644 src/glsl/opt_common_subexpression_elimination.cpp
diff --git a/src/glsl/Makefile b/src/glsl/Makefile
index 4100414..68b98b2 100644
--- a/src/glsl/Makefile
+++ b/src/glsl/Makefile
@@ -83,6 +83,7 @@ CXX_SOURCES = \
opt_structure_splitting.cpp \
opt_swizzle_swizzle.cpp \
opt_tree_grafting.cpp \
+ opt_common_subexpression_elimination.cpp \
s_expression.cpp
LIBS = \
diff --git a/src/glsl/glsl_parser_extras.cpp b/src/glsl/glsl_parser_extras.cpp
index d9aa300..0a57386 100644
--- a/src/glsl/glsl_parser_extras.cpp
+++ b/src/glsl/glsl_parser_extras.cpp
@@ -776,7 +776,9 @@ do_common_optimization(exec_list *ir, bool linked, unsigned max_unroll_iteration
{
GLboolean progress = GL_FALSE;
- progress = lower_instructions(ir, SUB_TO_ADD_NEG) || progress;
+
+ progress = do_common_subexpression_elimination(ir) || progress;
+ /*progress = lower_instructions(ir, SUB_TO_ADD_NEG) || progress;
if (linked) {
progress = do_function_inlining(ir) || progress;
@@ -807,12 +809,13 @@ do_common_optimization(exec_list *ir, bool linked, unsigned max_unroll_iteration
progress = optimize_redundant_jumps(ir) || progress;
+
loop_state *ls = analyze_loop_variables(ir);
if (ls->loop_found) {
progress = set_loop_controls(ir, ls) || progress;
progress = unroll_loops(ir, ls, max_unroll_iterations) || progress;
}
- delete ls;
+ delete ls;*/
return progress;
}
diff --git a/src/glsl/ir_optimization.h b/src/glsl/ir_optimization.h
index dd26567..3604e4e 100644
--- a/src/glsl/ir_optimization.h
+++ b/src/glsl/ir_optimization.h
@@ -71,3 +71,4 @@ bool lower_variable_index_to_cond_assign(exec_list *instructions,
bool lower_input, bool lower_output, bool lower_temp, bool lower_uniform);
bool lower_quadop_vector(exec_list *instructions, bool dont_lower_swz);
bool optimize_redundant_jumps(exec_list *instructions);
+bool do_common_subexpression_elimination(exec_list *instructions);
diff --git a/src/glsl/list.h b/src/glsl/list.h
index 1d46365..2478ab3 100644
--- a/src/glsl/list.h
+++ b/src/glsl/list.h
@@ -122,8 +122,8 @@ struct exec_node {
void remove()
{
- next->prev = prev;
- prev->next = next;
+ next->prev = prev;
+ prev->next = next;
next = NULL;
prev = NULL;
}
diff --git a/src/glsl/opt_common_subexpression_elimination.cpp b/src/glsl/opt_common_subexpression_elimination.cpp
new file mode 100644
index 0000000..a360ecf
--- /dev/null
+++ b/src/glsl/opt_common_subexpression_elimination.cpp
@@ -0,0 +1,665 @@
+#include "ir.h"
+#include "ir_visitor.h"
+#include "ir_hierarchical_visitor.h"
+#include "ir_basic_block.h"
+#include "ir_optimization.h"
+#include "glsl_types.h"
+
+#include <iostream>
+#include <cstring>
+using namespace std;
+
+/*
+ * Do local CSE at the moment
+ */
+
+typedef struct _pattern
+{
+ ir_variable* operand1;
+ ir_expression_operation operation;
+ ir_variable* operand2;
+} pattern;
+
+void display_pattern(const pattern& p)
+{
+ cout<<p.operand1->name << p.operation<< p.operand2->name <<endl;
+}
+
+int list_size(const exec_list* lst)
+{
+ int result=0;
+ foreach_list_const(tmp,lst)
+ {
+ result++;
+ }
+ return result;
+}
+
+class element : public exec_node
+{
+public:
+ pattern element_pattern;
+ exec_list* dereferences;
+
+ element(pattern p,void* mem_ctx):element_pattern(p)
+ {
+ dereferences = new (mem_ctx) exec_list();
+ }
+
+ ~element()
+ {
+
+ }
+};
+
+class box:public exec_node
+{
+public:
+ void* content;
+
+ box(void* c):content(c)
+ {
+
+ }
+};
+
+bool find(exec_list* lst,void* ptr)
+{
+ foreach_list_const(tmp,lst)
+ {
+ if(tmp == ptr)
+ return true;
+ }
+ return false;
+}
+
+class list_pattern
+{
+ friend class expressions_recorder;
+protected:
+ void* mem_ctx;
+ exec_list* inner_list; // element* list
+
+ bool equal_pattern(pattern p1, pattern p2) const
+ {
+ return p1.operation == p2.operation && p1.operand1 == p2.operand1 && p1.operand2 == p2.operand2;
+ }
+
+ element* select_by_pattern(pattern p)
+ {
+ foreach_list(iterator,inner_list)
+ {
+ element* current_node = (element*) iterator;
+ if(equal_pattern(p,current_node->element_pattern))
+ return current_node;
+ }
+ element* new_item = new (mem_ctx) element(p,mem_ctx);
+ inner_list->push_head(new_item);
+ return new_item;
+ }
+
+public:
+
+ bool is_present(pattern p) const
+ {
+ foreach_list_const(iterator,inner_list)
+ {
+ element* current_node = (element*) iterator;
+ if(equal_pattern(p,current_node->element_pattern))
+ return true;
+ }
+ return false;
+ }
+
+ exec_list* get_dereferences_discarded(ir_variable* var)
+ {
+ exec_list* extracted_list_pattern = new(mem_ctx) exec_list();
+ foreach_list_safe(iterator,inner_list)
+ {
+ element* current_node = (element*) iterator;
+ pattern &p = current_node->element_pattern;
+
+ if(p.operand1->name == var->name || p.operand2->name == var->name)
+ {
+ cout<<var->name <<" against ";
+ display_pattern(p);
+ extracted_list_pattern->push_tail(new (mem_ctx) box(current_node));
+ current_node->remove();
+ }
+ }
+
+ return extracted_list_pattern;
+ }
+
+ exec_list* at(pattern p)
+ {
+ return select_by_pattern(p)->dereferences;
+ }
+
+ void init()
+ {
+ inner_list = new (this) exec_list();
+ }
+
+};
+
+class expressions_recorder
+{
+ friend class ir_cse_visitor;
+
+private:
+ list_pattern* binop_container;
+
+ inline
+ pattern get_pattern(ir_expression_operation op,ir_variable* var1,ir_variable* var2) const
+ {
+ char* c1 = const_cast<char*>(var1->name);
+ char* c2 = const_cast<char*>(var2->name);
+ int res = strcmp(c1,c2);
+ if(res>0)
+ {
+ pattern result = {var1,op,var2};
+ return result;
+ }
+ else
+ {
+ pattern result = {var2,op,var1};
+ return result;
+ }
+ }
+
+public:
+ bool expression_already_seen( ir_variable* var1,ir_expression_operation op, ir_variable* var2) const
+ {
+ pattern p = get_pattern(op,var1,var2);
+ return binop_container->is_present(p);
+ }
+
+ bool add_expression(ir_dereference_variable *& var1,ir_expression_operation op, ir_dereference_variable *& var2)
+ {
+ pattern p = get_pattern(op,var1->var,var2->var);
+ exec_list* dref_for_pattern = binop_container->at(p);
+ foreach_list_const(it,dref_for_pattern)
+ {
+ ir_dereference_variable* itref = (ir_dereference_variable*) ((box*)it)->content;
+ if(itref==var1 || itref==var2)
+ {
+ return false;
+ }
+ }
+ dref_for_pattern->push_tail(new (var1) box(var1));
+ dref_for_pattern->push_tail(new (var2) box(var2));
+
+ return true;
+ }
+
+ exec_list* kill_variable(ir_variable* var)
+ {
+ return binop_container->get_dereferences_discarded(var);
+ }
+
+ exec_list* flush()
+ {
+ return binop_container->inner_list;
+ }
+
+ void init()
+ {
+ binop_container = (list_pattern*) ralloc_size(this,sizeof(list_pattern));
+ binop_container->init();
+ }
+
+
+};
+
+class ir_flattened_expression : public ir_expression
+{
+protected:
+
+ ir_rvalue* recursive_deep_parse(ir_rvalue* ir) const
+ {
+ if(ir_expression* expr = ir->as_expression())
+ {
+ return new(expr) ir_flattened_expression(expr);
+ }
+ return ir;
+ }
+
+ void recursive_breadth_parse(ir_expression* ir)
+ {
+ if(operation == ir->operation)
+ {
+ for(unsigned i=0;i<ir->get_num_operands();i++)
+ {
+ ir_expression* expr = ir->operands[i]->as_expression();
+ if(expr)
+ {
+ recursive_breadth_parse(expr);
+ }
+ else
+ {
+ box* boxed_rvalue = new (ir) box (recursive_deep_parse(ir->operands[i]));
+ operators->push_tail( boxed_rvalue );
+ }
+ }
+ }
+ else
+ {
+ box* boxed_rvalue = new (ir) box (recursive_deep_parse(ir));
+ operators->push_tail(boxed_rvalue);
+ }
+ }
+
+ ir_rvalue* to_classic_expr(ir_rvalue* ir) const
+ {
+ if(ir_expression* expr = ir->as_expression())
+ {
+ ir_flattened_expression* fexpr = dynamic_cast<ir_flattened_expression*>(expr);
+ return fexpr->to_classic_expression();
+ }
+ else
+ return ir;
+ }
+
+
+ bool find(element* el,ir_dereference_variable* vard1,ir_dereference_variable* vard2) const
+ {
+ exec_list* derefs = el->dereferences;
+ bool has_v1 = false,has_v2 = false;
+ foreach_list_const(it,derefs)
+ {
+ ir_dereference_variable* itref = (ir_dereference_variable*)((box*)it)->content;
+ if(itref==vard1)
+ has_v1=true;
+ if(itref==vard2)
+ has_v2=true;
+ }
+ return has_v1 && has_v2;
+ }
+
+ bool remove(ir_variable* newvar,element* el,exec_node*& ndi,exec_node*& ndj)
+ {
+ foreach_list_safe(node_i,operators)
+ {
+ foreach_list_safe(node_j,operators)
+ {
+ ir_rvalue* it_i = (ir_rvalue*) ((box*)node_i)->content;
+ ir_rvalue* it_j = (ir_rvalue*) ((box*)node_j)->content;
+ ir_dereference_variable* var1 = it_i->as_dereference_variable();
+ ir_dereference_variable* var2 = it_j->as_dereference_variable();
+ if(!var1 || !var2 || it_i==it_j)
+ continue;
+
+ if( find(el,var1,var2) )
+ {
+ ir_dereference_variable* newvar_ref = new(newvar) ir_dereference_variable(newvar);
+ box* boxed_value = new (newvar_ref) box(newvar_ref);
+ operators->push_tail(boxed_value);
+ ndi = node_i;
+ ndj = node_j;
+ return true;
+ }
+ }
+ }
+ return false;
+ }
+
+
+ void eliminate_expr_flatten(ir_variable* newvar,element* el,bool& is_modified)
+ {
+ bool boolflag;
+ is_modified = false;
+ if(operation != el->element_pattern.operation)
+ return;
+
+ exec_node *node_i,*node_j;
+ boolflag = remove(newvar,el,node_i,node_j);
+ is_modified = boolflag;
+ while(boolflag)
+ {
+ node_i->remove();
+ node_j->remove();
+ boolflag = remove(newvar,el,node_i,node_j);
+ }
+ }
+
+public:
+ exec_list* operators;
+ ir_flattened_expression(ir_expression* expr):ir_expression(*expr)
+ {
+ operators = new (expr) exec_list();
+ recursive_breadth_parse(expr);
+ }
+
+ virtual ~ir_flattened_expression()
+ {
+
+ }
+
+ exec_list* get_dereference_variable() const
+ {
+ exec_list* result = new (operators) exec_list();
+
+ foreach_list_const(node,operators)
+ {
+ ir_rvalue* it = (ir_rvalue*) ((box*)node)->content;
+ if(ir_dereference_variable* var=it->as_dereference_variable())
+ {
+ result->push_tail(new (result) box(var));
+ }
+ }
+ return result;
+ }
+
+ exec_list* get_expressions() const
+ {
+ exec_list* result = new (operators) exec_list();
+ foreach_list_const(node,operators)
+ {
+ ir_rvalue* it = (ir_rvalue*)((box*)node)->content;
+ if(ir_expression* expr = it->as_expression())
+ {
+ ir_flattened_expression* fexpr = dynamic_cast<ir_flattened_expression*>(expr);
+ result->push_tail(new (result) box(fexpr));
+ }
+ }
+ return result;
+
+ }
+
+ ir_rvalue* to_classic_expression() const
+ {
+ int step=-1;
+ box* tmp = (box*)operators->get_head();
+ ir_rvalue* current_tree = to_classic_expr((ir_rvalue*)tmp->content);
+ foreach_list_const(node,operators)
+ {
+ step++;
+ ir_rvalue* it = (ir_rvalue*) ((box*)node)->content;
+ if(!step)
+ continue;
+ ir_rvalue* current_rvalue = to_classic_expr(it);
+ ir_rvalue* temp_tree = new(current_tree) ir_expression(operation,current_rvalue,current_tree);
+ current_tree = temp_tree;
+ }
+ return current_tree;
+ }
+
+ void eliminate_expr(ir_variable* newvar,element* el,bool& is_modified)
+ {
+ eliminate_expr_flatten(newvar,el,is_modified);
+ foreach_list_safe(node,operators)
+ {
+ bool child_is_modified;
+ ir_rvalue* it = (ir_rvalue*) ((box*)node)->content;
+ ir_expression* expr = it->as_expression();
+ if(!expr)
+ continue;
+ ir_flattened_expression* fexpr = dynamic_cast<ir_flattened_expression*>(expr);
+ fexpr->eliminate_expr(newvar,el,child_is_modified);
+
+ bool size_equal_1 = operators->head && !operators->head->next;
+ if( size_equal_1 )
+ {
+ ir_rvalue* tmp = (ir_rvalue*)((box*)(fexpr->operators->head))->content;
+ operators->push_tail(new (tmp) box(tmp));
+ node->remove();
+ cout<<"unique"<<endl;
+ child_is_modified = true;
+ }
+ is_modified = is_modified || child_is_modified;
+
+ }
+ }
+
+ void display() const
+ {
+ cout<<"OP:"<<operation<<endl;
+ cout<<"VARIABLE:"<<endl;
+ exec_list* vars = get_dereference_variable();
+ foreach_list_const(it,vars)
+ {
+ ir_dereference_variable* dref = (ir_dereference_variable*) ((box*)it)->content;
+ cout<< dref->var->name << " ";
+ }
+ cout<<endl;
+
+ exec_list* exprs = get_expressions();
+ foreach_list_const(it,exprs)
+ {
+ cout<<"LEAVES OF"<<operation<<":"<<endl;
+ ir_flattened_expression* fexpr = (ir_flattened_expression*) ((box*)it)->content;
+ fexpr->display();
+ }
+
+ }
+};
+
+class ir_cse_visitor: public ir_hierarchical_visitor
+{
+
+private:
+ void find_cse_at_same_depth(const ir_flattened_expression*);
+
+protected:
+ expressions_recorder* available_expressions;
+ exec_list* candidates;
+ void discover_cse(const ir_flattened_expression*);
+
+public:
+ ir_cse_visitor(void* mem_ctx);
+
+ virtual ir_visitor_status visit_enter(class ir_assignment*);
+ virtual ir_visitor_status visit_leave(class ir_assignment*);
+ exec_list* get_candidate();
+};
+
+void ir_cse_visitor::find_cse_at_same_depth(const ir_flattened_expression* expr)
+{
+ exec_list* variables = expr->get_dereference_variable();
+ ir_expression_operation op = expr->operation;
+ foreach_list_const(var_i,variables)
+ {
+ foreach_list_const(var_j,variables)
+ {
+ if(var_i != var_j)
+ {
+ ir_dereference_variable* var1 = (ir_dereference_variable*) ((box*)var_i)->content;
+ ir_dereference_variable* var2 = (ir_dereference_variable*) ((box*)var_j)->content;
+
+ available_expressions->add_expression(var1,op,var2);
+ }
+ }
+ }
+}
+
+
+
+void ir_cse_visitor::discover_cse(const ir_flattened_expression* expr)
+{
+ find_cse_at_same_depth(expr);
+ exec_list* exprs = expr->get_expressions();
+ foreach_list_const(it,exprs)
+ {
+ ir_flattened_expression* it_expr = (ir_flattened_expression*) ((box*)it)->content;
+ discover_cse(it_expr);
+ }
+}
+
+
+
+ir_cse_visitor::ir_cse_visitor(void* mem_ctx):ir_hierarchical_visitor()
+{
+ candidates = new (mem_ctx) exec_list();
+ available_expressions = (expressions_recorder*) ralloc_size(mem_ctx,sizeof(expressions_recorder));
+ available_expressions->init();
+}
+
+ir_visitor_status ir_cse_visitor::visit_enter(ir_assignment* ir)
+{
+
+ if(ir_expression* expr = ir->rhs->as_expression())
+ {
+ ir_flattened_expression* fexpr = new(ir) ir_flattened_expression(expr);;
+ discover_cse(fexpr);
+ return visit_continue;
+ }
+ else
+ {
+ return visit_continue;
+ }
+}
+
+ir_visitor_status ir_cse_visitor::visit_leave(ir_assignment* ir)
+{
+ ir_variable* var = ir->lhs->as_dereference_variable()->var;
+ cout<<"removing : "<<var->name<<endl;
+ exec_list* tmplst = available_expressions->kill_variable(var);
+ foreach_list_const(tmp,tmplst)
+ {
+ element* c = (element*)((box*)tmp)->content;
+ candidates->push_tail(new (c) box(c));
+ }
+ return visit_continue;
+}
+
+exec_list* ir_cse_visitor::get_candidate()
+{
+ exec_list* tmplst = available_expressions->flush();
+ if(tmplst)
+ {
+ foreach_list_const(tmp,tmplst)
+ {
+ element* element_tmp = (element*) tmp;
+ candidates->push_tail(new (element_tmp) box(element_tmp));
+ }
+ }
+ exec_list* result = new (tmplst) exec_list();
+
+ foreach_list_const(candidate,candidates)
+ {
+ element* candidate_element = (element*) ((box*)candidate)->content;
+ if(list_size(candidate_element->dereferences)>2)
+ {
+ result->push_tail(new (candidate_element) box (candidate_element));
+ }
+ }
+
+ return result;
+}
+
+class ir_cse_factoriser: public ir_hierarchical_visitor
+{
+protected:
+ element* element_to_remove;
+ ir_variable* newvar;
+ bool activated;
+public:
+ ir_visitor_status visit_enter(ir_assignment* ir);
+ ir_cse_factoriser(element*);
+private:
+ void init_newvar(ir_assignment *& ir);
+ void assign_newvar(ir_assignment* ir);
+};
+
+void ir_cse_factoriser::init_newvar(ir_assignment *& ir)
+{
+ if(!newvar)
+ {
+ pattern p = element_to_remove->element_pattern;
+ newvar = new(ir) ir_variable(p.operand1->type,"tmp",ir_var_temporary);
+ ir->insert_before(newvar);
+
+ }
+}
+
+void ir_cse_factoriser::assign_newvar(ir_assignment* ir)
+{
+ pattern p = element_to_remove->element_pattern;
+ ir_expression* factored = new(ir) ir_expression(p.operation,new (ir) ir_dereference_variable(p.operand1),new (ir) ir_dereference_variable(p.operand2));
+ ir_assignment* assign = new(ir) ir_assignment(new(ir) ir_dereference_variable(newvar),factored,NULL);
+ ir->insert_before(assign);
+}
+
+ir_visitor_status
+ir_cse_factoriser::visit_enter(ir_assignment* ir)
+{
+ init_newvar(ir);
+ ir_expression* expr = ir->rhs->as_expression();
+ if(!expr)
+ return visit_continue;
+ ir_flattened_expression* fexpr = new(ir) ir_flattened_expression(expr);
+
+ bool is_modified;
+ fexpr->eliminate_expr(newvar,element_to_remove,is_modified);
+ if(!activated && is_modified)
+ {
+ assign_newvar(ir);
+ activated = true;
+ }
+
+ ir->rhs = fexpr->to_classic_expression();
+ return visit_continue;
+}
+
+ir_cse_factoriser::ir_cse_factoriser(element* e):element_to_remove(e),newvar(NULL),activated(false)
+{
+
+}
+
+
+
+
+
+static void
+cse_basic_block(ir_instruction *first,
+ ir_instruction *last,
+ void *data)
+{
+ ir_instruction *ir, *ir_next;
+ ir_cse_visitor* visitor = new ir_cse_visitor(first);
+ for (ir = first, ir_next = (ir_instruction *)first->next;;
+ ir = ir_next, ir_next = (ir_instruction *)ir->next)
+ {
+
+ ir->accept(visitor);
+ if(ir==last)
+ break;
+ }
+ exec_list* candidates = visitor->get_candidate();
+ foreach_list_const(it,candidates)
+ {
+ element* it_el = (element*) ((box*)it)->content;
+ pattern tmp = it_el->element_pattern;
+ cout<<"CANDIDATE:";
+ display_pattern(tmp);
+ //cout << (*it)->dereferences->size()/2<<endl;
+ ir_cse_factoriser factoriser(it_el);
+ for (ir = first, ir_next = (ir_instruction *)first->next;;
+ ir = ir_next, ir_next = (ir_instruction *)ir->next)
+ {
+
+ ir->accept(&factoriser);
+ if(ir==last)
+ break;
+ }
+ }
+}
+
+static int occurrence=0;
+
+bool
+do_common_subexpression_elimination(exec_list *instructions)
+{
+
+ call_for_basic_blocks(instructions,cse_basic_block,NULL);
+
+ if(occurrence++==0)
+ return true;
+ /*if(!already_entered)
+ {
+ already_entered = true;
+ return true;
+ }*/
+ return false;
+}
--
1.7.3.4
More information about the mesa-dev
mailing list