octave-nkf: src/pt-jit.h comparison

comparison src/pt-jit.h @ 14935:5801e031a3b5

Place releases after last use and generalize dom visiting

author	Max Brister <max@2bass.com>
date	Mon, 04 Jun 2012 13:10:44 -0500
parents	1f914446157d
children	32deb562ae77

comparison

equal deleted inserted replaced

-:4ec5f49cdfe4
+:5801e031a3b5
 // and code generation.
 class
 jit_function
 {
 public:
-struct overload
+struct
+overload
 {
 overload (void) : function (0), can_error (true), result (0) {}
-overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0) :
+overload (llvm::Function *f, bool e, bool s, jit_type *r, jit_type *arg0) :
-function (f), can_error (e), result (r), arguments (1)
+function (f), can_error (e), side_effects (s), result (r), arguments (1)
 {
 arguments[0] = arg0;
 }
-overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0,
+overload (llvm::Function *f, bool e, bool s, jit_type *r, jit_type *arg0,
-jit_type *arg1) : function (f), can_error (e), result (r),
+jit_type *arg1) : function (f), can_error (e), side_effects (s),
-arguments (2)
+result (r), arguments (2)
 {
 arguments[0] = arg0;
 arguments[1] = arg1;
 }
 llvm::Function *function;
 bool can_error;
+bool side_effects;
 jit_type *result;
 std::vector<jit_type*> arguments;
 };
 void add_overload (const overload& func)
 {
 add_overload (func, func.arguments);
 }
-void add_overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0)
+void add_overload (llvm::Function *f, bool e, bool s, jit_type *r, jit_type *arg0)
 {
-overload ol (f, e, r, arg0);
+overload ol (f, e, s, r, arg0);
 add_overload (ol);
 }
-void add_overload (llvm::Function *f, bool e, jit_type *r, jit_type *arg0,
+void add_overload (llvm::Function *f, bool e, bool s, jit_type *r, jit_type *arg0,
 jit_type *arg1)
 {
-overload ol (f, e, r, arg0, arg1);
+overload ol (f, e, s, r, arg0, arg1);
 add_overload (ol);
 }
 void add_overload (const overload& func,
 const std::vector<jit_type*>& args);
 static const jit_function& grab (void) { return instance->grab_fn; }
 static const jit_function& release (void)
 {
 return instance->release_fn;
+}
+static const jit_function::overload& get_release (jit_type *type)
+{
+return instance->release_fn.get_overload (type);
 }
 static const jit_function& print_value (void)
 {
 return instance->print_fn;
 // The low level octave jit ir
 // this ir is close to llvm, but contains information for doing type inference.
 // We convert the octave parse tree to this IR directly.
 #define JIT_VISIT_IR_NOTEMPLATE                 \
-JIT_METH(block);                              \
+JIT_METH(block)                               \
-JIT_METH(break);                              \
+JIT_METH(break)                               \
-JIT_METH(cond_break);                         \
+JIT_METH(cond_break)                          \
-JIT_METH(call);                               \
+JIT_METH(call)                                \
-JIT_METH(extract_argument);                   \
+JIT_METH(extract_argument)                    \
-JIT_METH(store_argument);                     \
+JIT_METH(store_argument)                      \
-JIT_METH(phi);                                \
+JIT_METH(phi)                                 \
 JIT_METH(variable)
+#define JIT_VISIT_IR_CONST                      \
+JIT_METH(const_scalar)                        \
+JIT_METH(const_index)                         \
+JIT_METH(const_string)                        \
+JIT_METH(const_range)
+#define JIT_VISIT_IR_ABSTRACT                   \
+JIT_METH(instruction)                         \
+JIT_METH(terminator)
 #define JIT_VISIT_IR_CLASSES                    \
-JIT_VISIT_IR_NOTEMPLATE;                      \
+JIT_VISIT_IR_NOTEMPLATE                       \
 JIT_VISIT_IR_CONST
+#define JIT_VISIT_IR_ALL                        \
+JIT_VISIT_IR_CLASSES                          \
+JIT_VISIT_IR_ABSTRACT
+// forward declare all ir classes
+#define JIT_METH(cname)                         \
+class jit_ ## cname;
+JIT_VISIT_IR_ABSTRACT
+JIT_VISIT_IR_NOTEMPLATE
+#undef JIT_METH
+// constants are typedefs from jit_const
+template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T = T,
+bool QUOTE=false>
+class jit_const;
+typedef jit_const<double, jit_typeinfo::get_scalar> jit_const_scalar;
+typedef jit_const<octave_idx_type, jit_typeinfo::get_index> jit_const_index;
+typedef jit_const<std::string, jit_typeinfo::get_string, const std::string&, true>
+jit_const_string;
+typedef jit_const<jit_range, jit_typeinfo::get_range, const jit_range&>
+jit_const_range;
 class jit_ir_walker;
 class jit_use;
 class
 void stash_llvm (llvm::Value *compiled)
 {
 llvm_value = compiled;
 }
+#define JIT_METH(cname)                                         \
+virtual bool is_ ## cname (void) const                        \
+{ return false; }                                             \
+\
+virtual jit_ ## cname *to_ ## cname (void)                    \
+{ return 0; }                                                 \
+\
+virtual const jit_ ## cname *to_ ## cname (void) const        \
+{ return 0; }
+JIT_VISIT_IR_NOTEMPLATE
+JIT_VISIT_IR_ABSTRACT
+#undef JIT_METH
 protected:
 std::ostream& print_indent (std::ostream& os, size_t indent) const
 {
 for (size_t i = 0; i < indent * 8; ++i)
 os << " ";
 size_t myuse_count;
 };
 std::ostream& operator<< (std::ostream& os, const jit_value& value);
-class jit_instruction;
+#define JIT_GEN_CASTS(cname)                                    \
-class jit_block;
+virtual bool is_ ## cname (void) const                        \
+{ return true; }                                              \
+\
+virtual jit_ ## cname *to_ ## cname (void)                    \
+{ return this; }                                              \
+\
+virtual const jit_ ## cname *to_ ## cname (void) const        \
+{ return this; }
 class
 jit_use
 {
 public:
 size_t index (void) const { return mindex; }
 jit_instruction *user (void) const { return muser; }
 jit_block *user_parent (void) const;
+std::list<jit_block *> user_parent_location (void) const;
 void stash_value (jit_value *avalue, jit_instruction *auser = 0,
 size_t aindex = -1)
 {
 remove ();
 jit_use *mprev;
 jit_instruction *muser;
 size_t mindex;
 };
-class jit_variable;
 class
 jit_instruction : public jit_value
 {
 public:
 // FIXME: this code could be so much pretier with varadic templates...
 llvm::Type *argument_type_llvm (size_t i) const
 {
 assert (argument (i));
 return argument_type (i)->to_llvm ();
 }
+// generate functions of form argument_type where type is any subclass of
+// jit_value
+#define JIT_METH(cname)                                 \
+jit_ ## cname *argument_ ## cname (size_t i) const    \
+{                                                     \
+jit_value *arg = argument (i);                      \
+return arg ? arg->to_ ## cname () : 0;              \
+}
+JIT_VISIT_IR_ABSTRACT
+JIT_VISIT_IR_NOTEMPLATE
+#undef JIT_METH
 std::ostream& print_argument (std::ostream& os, size_t i) const
 {
 if (argument (i))
 return argument (i)->short_print (os);
 // argument types which have been infered already
 const std::vector<jit_type *>& argument_types (void) const
 { return already_infered; }
+virtual bool dead (void) const { return false; }
+virtual bool almost_dead (void) const { return false; }
 virtual bool infer (void) { return false; }
+void remove (void);
 void push_variable (void);
 void pop_variable (void);
 virtual std::ostream& short_print (std::ostream& os) const;
 jit_block *parent (void) const { return mparent; }
+std::list<jit_instruction *>::iterator location (void) const
+{
+return mlocation;
+}
 llvm::BasicBlock *parent_llvm (void) const;
-void stash_parent (jit_block *aparent)
+void stash_parent (jit_block *aparent,
-{
+std::list<jit_instruction *>::iterator alocation)
-assert (! mparent);
+{
 mparent = aparent;
+mlocation = alocation;
 }
 jit_variable *tag (void) const;
 void stash_tag (jit_variable *atag);
+JIT_GEN_CASTS (instruction)
 protected:
 std::vector<jit_type *> already_infered;
 private:
 static size_t next_id (bool reset = false)
 {
 jit_use mtag;
 size_t id;
 jit_block *mparent;
+std::list<jit_instruction *>::iterator mlocation;
 };
 // defnie accept methods for subclasses
 #define JIT_VALUE_ACCEPT(clname)                \
 virtual void accept (jit_ir_walker& walker);
-template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T = T,
+template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T,
-bool QUOTE=false>
+bool QUOTE>
 class
 jit_const : public jit_instruction
 {
 public:
 typedef PASS_T pass_t;
 JIT_VALUE_ACCEPT (jit_const);
 private:
 T mvalue;
 };
-typedef jit_const<double, jit_typeinfo::get_scalar> jit_const_scalar;
-typedef jit_const<octave_idx_type, jit_typeinfo::get_index> jit_const_index;
-typedef jit_const<std::string, jit_typeinfo::get_string, const std::string&, true>
-jit_const_string;
-typedef jit_const<jit_range, jit_typeinfo::get_range, const jit_range&>
-jit_const_range;
-#define JIT_VISIT_IR_CONST                      \
-JIT_METH(const_scalar);                       \
-JIT_METH(const_index);                        \
-JIT_METH(const_string);                       \
-JIT_METH(const_range)
-class jit_terminator;
-class jit_phi;
-class jit_convert;
 class
 jit_block : public jit_value
 {
 public:
 typedef std::list<jit_instruction *> instruction_list;
 const std::string& name (void) const { return mname; }
 jit_instruction *prepend (jit_instruction *instr);
+jit_instruction *prepend_after_phi (jit_instruction *instr);
 jit_instruction *append (jit_instruction *instr);
 jit_instruction *insert_before (iterator loc, jit_instruction *instr);
 jit_instruction *insert_after (iterator loc, jit_instruction *instr);
 void remove (jit_block::iterator iter)
 {
+jit_instruction *instr = *iter;
 instructions.erase (iter);
+instr->stash_parent (0, instructions.end ());
 }
 jit_terminator *terminator (void) const;
 jit_block *pred (size_t idx) const;
 void create_dom_tree (void)
 {
 create_dom_tree (mvisit_count);
 }
-void construct_ssa (jit_convert& convert)
+// visit blocks in the order of the dominator tree
-{
+// inorder - Run on the root first, then children
-do_construct_ssa (convert, mvisit_count);
+// postorder - Run on children first, then the root
-}
+template <typename func_type0, typename func_type1>
+void visit_dom (func_type0 inorder, func_type1 postorder)
+{
+do_visit_dom (mvisit_count, inorder, postorder);
+}
+// call pop_varaible on all instructions
+void pop_all (void);
 virtual std::ostream& print (std::ostream& os, size_t indent) const
 {
 print_indent (os, indent) << mname << ":        %pred = ";
 for (size_t i = 0; i < pred_count (); ++i)
 }
 llvm::BasicBlock *to_llvm (void) const;
 JIT_VALUE_ACCEPT (block)
+JIT_GEN_CASTS (block)
 private:
 void compute_df (size_t visit_count);
 bool update_idom (size_t visit_count);
-void finish_phi (jit_block *pred);
-void do_construct_ssa (jit_convert& convert, size_t visit_count);
 void create_dom_tree (size_t visit_count);
 jit_block *idom_intersect (jit_block *b);
+template <typename func_type0, typename func_type1>
+void do_visit_dom (size_t visit_count, func_type0 inorder, func_type1 postorder);
 static const size_t NO_ID = static_cast<size_t> (-1);
 size_t mvisit_count;
 size_t mid;
 jit_block *idom;
 std::string mname;
 instruction_list instructions;
 mutable std::vector<llvm::BasicBlock *> mpred_llvm;
 };
+// allow regular function pointers as well as pointers to members
+template <typename func_type>
+class jit_block_callback
+{
+public:
+jit_block_callback (func_type afunction) : function (afunction) {}
+void operator() (jit_block& block)
+{
+function (block);
+}
+private:
+func_type function;
+};
+template <>
+class jit_block_callback<void (jit_block::*)(void)>
+{
+public:
+typedef void (jit_block::*func_type)(void);
+jit_block_callback (func_type afunction) : function (afunction) {}
+void operator() (jit_block& ablock)
+{
+(ablock.*function) ();
+}
+private:
+func_type function;
+};
+template <typename func_type0, typename func_type1>
+void
+jit_block::do_visit_dom (size_t visit_count, func_type0 inorder, func_type1 postorder)
+{
+if (mvisit_count > visit_count)
+return;
+mvisit_count = visit_count + 1;
+jit_block_callback<func_type0> inorder_cb (inorder);
+inorder_cb (*this);
+for (size_t i = 0; i < dom_succ.size (); ++i)
+dom_succ[i]->do_visit_dom (visit_count, inorder, postorder);
+jit_block_callback<func_type1> postorder_cb (postorder);
+postorder_cb (*this);
+}
 // A non-ssa variable
 class
 jit_variable : public jit_value
 {
 public:
-jit_variable (const std::string& aname) : mname (aname) {}
+jit_variable (const std::string& aname) : mname (aname), mlast_use (0) {}
 const std::string &name (void) const { return mname; }
 // manipulate the value_stack, for use during SSA construction. The top of the
 // value stack represents the current value for this variable
 jit_value *top (void) const
 {
 return value_stack.top ();
 }
-void push (jit_value *v)
+void push (jit_instruction *v)
 {
 value_stack.push (v);
+mlast_use = v;
 }
 void pop (void)
 {
 value_stack.pop ();
+}
+jit_instruction *last_use (void) const
+{
+return mlast_use;
+}
+void stash_last_use (jit_instruction *instr)
+{
+mlast_use = instr;
 }
 // blocks in which we are used
 void use_blocks (jit_block::df_set& result)
 {
 {
 return print_indent (os, indent) << mname;
 }
 JIT_VALUE_ACCEPT (variable)
+JIT_GEN_CASTS (variable)
 private:
 std::string mname;
 std::stack<jit_value *> value_stack;
+jit_instruction *mlast_use;
 };
 class
 jit_phi : public jit_instruction
 {
 public:
 jit_phi (jit_variable *avariable, size_t npred)
 : jit_instruction (npred)
 {
 stash_tag (avariable);
+}
+virtual bool dead (void) const
+{
+return use_count () == 0;
+}
+virtual bool almost_dead (void) const
+{
+return use_count () <= 1;
 }
 virtual bool infer (void)
 {
 jit_type *infered = 0;
 return os;
 }
 JIT_VALUE_ACCEPT (phi);
+JIT_GEN_CASTS (phi)
 };
 class
 jit_terminator : public jit_instruction
 {
 {
 return sucessor (idx)->short_print (os);
 }
 virtual size_t sucessor_count (void) const = 0;
+JIT_GEN_CASTS (terminator)
 };
 class
 jit_break : public jit_terminator
 {
 print_indent (os, indent) << "break: ";
 return print_sucessor (os);
 }
 JIT_VALUE_ACCEPT (break)
+JIT_GEN_CASTS (break)
 };
 class
 jit_cond_break : public jit_terminator
 {
 print_sucessor (os, 0) << ", ";
 return print_sucessor (os, 1);
 }
 JIT_VALUE_ACCEPT (cond_break)
+JIT_GEN_CASTS (cond_break)
 };
 class
 jit_call : public jit_instruction
 {
 jit_call (const jit_function& (*afunction) (void),
 jit_value *arg0, jit_value *arg1) : jit_instruction (arg0, arg1),
 mfunction (afunction ()) {}
 const jit_function& function (void) const { return mfunction; }
+bool has_side_effects (void) const
+{
+return overload ().side_effects;
+}
 const jit_function::overload& overload (void) const
 {
 return mfunction.get_overload (argument_types ());
 }
 os << ", ";
 }
 return os << ")";
 }
+virtual bool dead (void) const;
+virtual bool almost_dead (void) const;
 virtual bool infer (void);
 JIT_VALUE_ACCEPT (call)
+JIT_GEN_CASTS (call)
 private:
 const jit_function& mfunction;
 };
 class
 short_print (os);
 return os;
 }
 JIT_VALUE_ACCEPT (extract_argument)
+JIT_GEN_CASTS (extract_argument)
 };
 class
 jit_store_argument : public jit_instruction
 {
 short_print (os) << " = ";
 return res->short_print (os);
 }
 JIT_VALUE_ACCEPT (store_argument)
+JIT_GEN_CASTS (store_argument)
 };
 class
 jit_ir_walker
 {
 public:
 virtual ~jit_ir_walker () {}
 #define JIT_METH(clname) \
-virtual void visit (jit_ ## clname&) = 0
+virtual void visit (jit_ ## clname&) = 0;
 JIT_VISIT_IR_CLASSES;
 #undef JIT_METH
 };
 T *ret = new T(arg0, arg1, arg2);
 track_value (ret);
 return ret;
 }
 private:
+typedef std::list<jit_block *> block_list;
+typedef block_list::iterator block_iterator;
 std::vector<std::pair<std::string, bool> > arguments;
 type_bound_vector bounds;
 // used instead of return values from visit_* functions
 jit_instruction *result;
 constants.push_back (value);
 all_values.push_back (value);
 }
 void construct_ssa (jit_block *final_block);
+static void do_construct_ssa (jit_block& block);
+void place_releases (void);
 void print_blocks (const std::string& header)
 {
 std::cout << "-------------------- " << header << " --------------------\n";
 for (std::list<jit_block *>::iterator iter = blocks.begin ();
 (*iter)->print_dom (std::cout);
 }
 std::cout << std::endl;
 }
-typedef std::list<jit_block *> break_list;
 bool breaking; // true if we are breaking OR continuing
-break_list breaks;
+block_list breaks;
-break_list continues;
+block_list continues;
-void finish_breaks (jit_block *dest, const break_list& lst);
+void finish_breaks (jit_block *dest, const block_list& lst);
+struct release_placer
+{
+release_placer (jit_convert& aconvert) : convert (aconvert) {}
+jit_convert& convert;
+void operator() (jit_block& block);
+};
 // this case is much simpler, just convert from the jit ir to llvm
 class
 convert_llvm : public jit_ir_walker
 {
 #undef JIT_METH
 private:
 // name -> llvm argument
 std::map<std::string, llvm::Value *> arguments;
+void finish_phi (jit_instruction *phi);
 void visit (jit_value *jvalue)
 {
 return visit (*jvalue);
 }

Mercurial > hg > octave-nkf

comparison src/pt-jit.h @ 14935:5801e031a3b5