From 8895bae55ba8d9f62dd59cbd924ac37c8a7dcdb1 Mon Sep 17 00:00:00 2001 From: Ian Romanick Date: Fri, 14 May 2010 12:39:23 -0700 Subject: [PATCH] Add ir_hierarchical_visitor base class and associated infrastructure This type of visitor should eventually replace all or almost all current uses of ir_visitor. --- Makefile.am | 5 +- ir.h | 28 +++++ ir_hierarchical_visitor.cpp | 197 ++++++++++++++++++++++++++++++++ ir_hierarchical_visitor.h | 121 ++++++++++++++++++++ ir_hv_accept.cpp | 265 ++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 615 insertions(+), 1 deletion(-) create mode 100644 ir_hierarchical_visitor.cpp create mode 100644 ir_hierarchical_visitor.h create mode 100644 ir_hv_accept.cpp diff --git a/Makefile.am b/Makefile.am index 105fcc5..aa05021 100644 --- a/Makefile.am +++ b/Makefile.am @@ -46,7 +46,10 @@ glsl_SOURCES = \ ir_optimization.h \ ir_reader.cpp s_expression.cpp \ ir_visit_tree.cpp \ - ir_visit_tree.h + ir_visit_tree.h \ + ir_hv_accept.cpp \ + ir_hierarchical_visitor.h \ + ir_hierarchical_visitor.cpp BUILT_SOURCES = glsl_parser.h glsl_parser.cpp glsl_lexer.cpp CLEANFILES = $(BUILT_SOURCES) diff --git a/ir.h b/ir.h index a533eee..93b4c2b 100644 --- a/ir.h +++ b/ir.h @@ -28,6 +28,7 @@ #include "list.h" #include "ir_visitor.h" +#include "ir_hierarchical_visitor.h" struct ir_program { void *bong_hits; @@ -42,6 +43,7 @@ public: class ir_constant *constant_expression_value(); virtual void accept(ir_visitor *) = 0; + virtual ir_visitor_status accept(ir_hierarchical_visitor *) = 0; /** * \name IR instruction downcast functions @@ -130,6 +132,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + /** * Duplicate an IR variable * @@ -210,6 +214,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + /** * Get the name of the function for which this is a signature */ @@ -277,6 +283,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + void add_signature(ir_function_signature *sig) { sig->function = this; @@ -343,6 +351,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + ir_rvalue *condition; /** List of ir_instruction for the body of the then branch */ exec_list then_instructions; @@ -366,6 +376,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + virtual ir_loop *as_loop() { return this; @@ -403,6 +415,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + virtual ir_assignment * as_assignment() { return this; @@ -531,6 +545,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + ir_expression *clone(); ir_expression_operation operation; @@ -561,6 +577,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + /** * Get a generic ir_call object when an error occurs */ @@ -650,6 +668,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + private: ir_rvalue *value; }; @@ -681,6 +701,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + bool is_break() const { return mode == jump_break; @@ -747,6 +769,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + bool is_lvalue() { return val->is_lvalue() && !mask.has_duplicates; @@ -780,6 +804,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + bool is_lvalue(); /** @@ -825,6 +851,8 @@ public: v->visit(this); } + virtual ir_visitor_status accept(ir_hierarchical_visitor *); + ir_constant *clone() { return new ir_constant(this->type, &this->value); diff --git a/ir_hierarchical_visitor.cpp b/ir_hierarchical_visitor.cpp new file mode 100644 index 0000000..4fec0d7 --- /dev/null +++ b/ir_hierarchical_visitor.cpp @@ -0,0 +1,197 @@ +/* + * Copyright © 2010 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ +#define NULL 0 +#include "ir.h" +#include "ir_hierarchical_visitor.h" + +ir_visitor_status +ir_hierarchical_visitor::visit(ir_variable *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit(ir_constant *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit(ir_loop_jump *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_loop *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_loop *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_function_signature *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_function_signature *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_function *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_function *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_expression *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_expression *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_swizzle *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_swizzle *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_dereference *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_dereference *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_assignment *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_assignment *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_call *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_call *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_return *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_return *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_enter(ir_if *ir) +{ + (void) ir; + return visit_continue; +} + +ir_visitor_status +ir_hierarchical_visitor::visit_leave(ir_if *ir) +{ + (void) ir; + return visit_continue; +} + +void +ir_hierarchical_visitor::run(exec_list *instructions) +{ + foreach_list(n, instructions) { + ir_instruction *ir = (ir_instruction *) n; + + if (ir->accept(this) != visit_continue) + break; + } +} diff --git a/ir_hierarchical_visitor.h b/ir_hierarchical_visitor.h new file mode 100644 index 0000000..daf2209 --- /dev/null +++ b/ir_hierarchical_visitor.h @@ -0,0 +1,121 @@ +/* -*- c++ -*- */ +/* + * Copyright © 2010 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ + +#pragma once +#ifndef IR_HIERARCHICAL_VISITOR_H +#define IR_HIERARCHICAL_VISITOR_H + +/** + * Enumeration values returned by visit methods to guide processing + */ +enum ir_visitor_status { + visit_continue, /**< Continue visiting as normal. */ + visit_continue_with_parent, /**< Don't visit siblings, continue w/parent. */ + visit_stop /**< Stop visiting immediately. */ +}; + + +/** + * Base class of hierarchical visitors of IR instruction trees + * + * Hierarchical visitors differ from traditional visitors in a couple of + * important ways. Rather than having a single \c visit method for each + * subclass in the composite, there are three kinds of visit methods. + * Leaf-node classes have a traditional \c visit method. Internal-node + * classes have a \c visit_enter method, which is invoked just before + * processing child nodes, and a \c visit_leave method which is invoked just + * after processing child nodes. + * + * In addition, each visit method and the \c accept methods in the composite + * have a return value which guides the navigation. Any of the visit methods + * can choose to continue visiting the tree as normal (by returning \c + * visit_continue), terminate visiting any further nodes immediately (by + * returning \c visit_stop), or stop visiting sibling nodes (by returning \c + * visit_continue_with_parent). + * + * These two changes combine to allow nagivation of children to be implemented + * in the composite's \c accept method. The \c accept method for a leaf-node + * class will simply call the \c visit method, as usual, and pass its return + * value on. The \c accept method for internal-node classes will call the \c + * visit_enter method, call the \c accpet method of each child node, and, + * finally, call the \c visit_leave method. If any of these return a value + * other that \c visit_continue, the correct action must be taken. + * + * The final benefit is that the hierarchical visitor base class need not be + * abstract. Default implementations of every \c visit, \c visit_enter, and + * \c visit_leave method can be provided. By default each of these methods + * simply returns \c visit_continue. This allows a significant reduction in + * derived class code. + * + * For more information about hierarchical visitors, see: + * + * http://c2.com/cgi/wiki?HierarchicalVisitorPattern + * http://c2.com/cgi/wiki?HierarchicalVisitorDiscussion + */ + +class ir_hierarchical_visitor { +public: + /** + * \name Visit methods for leaf-node classes + */ + /*@{*/ + virtual ir_visitor_status visit(class ir_variable *); + virtual ir_visitor_status visit(class ir_constant *); + virtual ir_visitor_status visit(class ir_loop_jump *); + /*@}*/ + + /** + * \name Visit methods for internal-node classes + */ + /*@{*/ + virtual ir_visitor_status visit_enter(class ir_loop *); + virtual ir_visitor_status visit_leave(class ir_loop *); + virtual ir_visitor_status visit_enter(class ir_function_signature *); + virtual ir_visitor_status visit_leave(class ir_function_signature *); + virtual ir_visitor_status visit_enter(class ir_function *); + virtual ir_visitor_status visit_leave(class ir_function *); + virtual ir_visitor_status visit_enter(class ir_expression *); + virtual ir_visitor_status visit_leave(class ir_expression *); + virtual ir_visitor_status visit_enter(class ir_swizzle *); + virtual ir_visitor_status visit_leave(class ir_swizzle *); + virtual ir_visitor_status visit_enter(class ir_dereference *); + virtual ir_visitor_status visit_leave(class ir_dereference *); + virtual ir_visitor_status visit_enter(class ir_assignment *); + virtual ir_visitor_status visit_leave(class ir_assignment *); + virtual ir_visitor_status visit_enter(class ir_call *); + virtual ir_visitor_status visit_leave(class ir_call *); + virtual ir_visitor_status visit_enter(class ir_return *); + virtual ir_visitor_status visit_leave(class ir_return *); + virtual ir_visitor_status visit_enter(class ir_if *); + virtual ir_visitor_status visit_leave(class ir_if *); + /*@}*/ + + + /** + * Utility function to process a linked list of instructions with a visitor + */ + void run(struct exec_list *instructions); +}; + +#endif /* IR_HIERARCHICAL_VISITOR_H */ diff --git a/ir_hv_accept.cpp b/ir_hv_accept.cpp new file mode 100644 index 0000000..7249bdb --- /dev/null +++ b/ir_hv_accept.cpp @@ -0,0 +1,265 @@ +/* + * Copyright © 2010 Intel Corporation + * + * Permission is hereby granted, free of charge, to any person obtaining a + * copy of this software and associated documentation files (the "Software"), + * to deal in the Software without restriction, including without limitation + * the rights to use, copy, modify, merge, publish, distribute, sublicense, + * and/or sell copies of the Software, and to permit persons to whom the + * Software is furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice (including the next + * paragraph) shall be included in all copies or substantial portions of the + * Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER + * DEALINGS IN THE SOFTWARE. + */ +#define NULL 0 +#include "ir.h" + +/** + * \file ir_hv_accept.cpp + * Implementations of all hierarchical visitor accept methods for IR + * instructions. + */ + +/** + * Process a list of nodes using a hierarchical vistor + */ +static ir_visitor_status +visit_list_elements(ir_hierarchical_visitor *v, exec_list *l) +{ + foreach_list (n, l) { + ir_instruction *const ir = (ir_instruction *) n; + ir_visitor_status s = ir->accept(v); + + if (s != visit_continue) + return s; + } + + return visit_continue; +} + + +ir_visitor_status +ir_variable::accept(ir_hierarchical_visitor *v) +{ + return v->visit(this); +} + + +ir_visitor_status +ir_loop::accept(ir_hierarchical_visitor *v) +{ + ir_visitor_status s = v->visit_enter(this); + + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + s = visit_list_elements(v, &this->body_instructions); + if (s == visit_stop) + return s; + + if (s != visit_continue_with_parent) { + if (this->from) { + s = this->from->accept(v); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + } + + if (this->to) { + s = this->to->accept(v); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + } + + if (this->increment) { + s = this->increment->accept(v); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + } + } + + return v->visit_leave(this); +} + + +ir_visitor_status +ir_loop_jump::accept(ir_hierarchical_visitor *v) +{ + return v->visit(this); +} + + +ir_visitor_status +ir_function_signature::accept(ir_hierarchical_visitor *v) +{ + ir_visitor_status s = v->visit_enter(this); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + s = visit_list_elements(v, &this->body); + return (s == visit_stop) ? s : v->visit_leave(this); +} + + +ir_visitor_status +ir_function::accept(ir_hierarchical_visitor *v) +{ + /* FINISHME: Do we want to walk into functions? */ + (void) v; + return visit_continue; +} + + +ir_visitor_status +ir_expression::accept(ir_hierarchical_visitor *v) +{ + ir_visitor_status s = v->visit_enter(this); + + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + for (unsigned i = 0; i < this->get_num_operands(); i++) { + switch (this->operands[i]->accept(v)) { + case visit_continue: + break; + + case visit_continue_with_parent: + // I wish for Java's labeled break-statement here. + goto done; + + case visit_stop: + return s; + } + } + +done: + return v->visit_leave(this); +} + + +ir_visitor_status +ir_swizzle::accept(ir_hierarchical_visitor *v) +{ + ir_visitor_status s = v->visit_enter(this); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + s = this->val->accept(v); + return (s == visit_stop) ? s : v->visit_leave(this); +} + + +ir_visitor_status +ir_dereference::accept(ir_hierarchical_visitor *v) +{ + ir_visitor_status s = v->visit_enter(this); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + if (this->mode == ir_reference_array) { + s = this->selector.array_index->accept(v); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + } + + + s = this->var->accept(v); + return (s == visit_stop) ? s : v->visit_leave(this); +} + + +ir_visitor_status +ir_assignment::accept(ir_hierarchical_visitor *v) +{ + ir_visitor_status s = v->visit_enter(this); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + s = this->lhs->accept(v); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + s = this->rhs->accept(v); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + if (this->condition) + s = this->condition->accept(v); + + return (s == visit_stop) ? s : v->visit_leave(this); +} + + +ir_visitor_status +ir_constant::accept(ir_hierarchical_visitor *v) +{ + return v->visit(this); +} + + +ir_visitor_status +ir_call::accept(ir_hierarchical_visitor *v) +{ + ir_visitor_status s = v->visit_enter(this); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + s = visit_list_elements(v, &this->actual_parameters); + if (s == visit_stop) + return s; + + return v->visit_leave(this); +} + + +ir_visitor_status +ir_return::accept(ir_hierarchical_visitor *v) +{ + ir_visitor_status s = v->visit_enter(this); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + ir_rvalue *val = this->get_value(); + if (val) { + s = val->accept(v); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + } + + return v->visit_leave(this); +} + + +ir_visitor_status +ir_if::accept(ir_hierarchical_visitor *v) +{ + ir_visitor_status s = v->visit_enter(this); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + s = this->condition->accept(v); + if (s != visit_continue) + return (s == visit_continue_with_parent) ? visit_continue : s; + + if (s != visit_continue_with_parent) { + s = visit_list_elements(v, &this->then_instructions); + if (s == visit_stop) + return s; + } + + if (s != visit_continue_with_parent) { + s = visit_list_elements(v, &this->else_instructions); + if (s == visit_stop) + return s; + } + + return v->visit_leave(this); +} -- 2.7.4