Mercurial > octave
view libinterp/corefcn/jit-ir.h @ 21244:1473547f50f5
include octave-config.h in public header files
* mk-opts.pl, mkbuiltins, mk-ops.awk, sparse-mk-ops.awk:
Emit "#include octave-config.h" statement for generated header files.
* build-env.h, builtins.h, Cell.h, base-text-renderer.h,
c-file-ptr-stream.h, cdisplay.h, comment-list.h, data.h, debug.h,
defaults.in.h, defun-dld.h, defun-int.h, defun.h, dirfns.h, display.h,
dynamic-ld.h, error.h, errwarn.h, event-queue.h, file-io.h,
ft-text-renderer.h, gl-render.h, gl2ps-print.h, graphics.in.h,
gripes.h, help.h, hook-fcn.h, input.h, jit-ir.h, jit-typeinfo.h,
jit-util.h, load-path.h, load-save.h, ls-ascii-helper.h, ls-hdf5.h,
ls-mat-ascii.h, ls-mat4.h, ls-mat5.h, ls-oct-binary.h, ls-oct-text.h,
ls-utils.h, mex.h, mexproto.h, mxarray.in.h, oct-errno.h, oct-fstrm.h,
oct-handle.h, oct-hdf5-types.h, oct-hdf5.h, oct-hist.h, oct-iostrm.h,
oct-lvalue.h, oct-map.h, oct-obj.h, oct-opengl.h, oct-prcstrm.h,
oct-procbuf.h, oct-stdstrm.h, oct-stream.h, oct-strstrm.h, oct.h,
octave-default-image.h, octave-link.h, octave-preserve-stream-state.h,
pager.h, pr-output.h, procstream.h, profiler.h, pt-jit.h,
sighandlers.h, siglist.h, sparse-xdiv.h, sparse-xpow.h, symtab.h,
sysdep.h, text-renderer.h, toplev.h, txt-eng.h, utils.h, variables.h,
workspace-element.h, xdiv.h, xnorm.h, xpow.h, zfstream.h, oct-qhull.h,
ov-base-diag.h, ov-base-int.h, ov-base-mat.h, ov-base-scalar.h,
ov-base-sparse.h, ov-base.h, ov-bool-mat.h, ov-bool-sparse.h,
ov-bool.h, ov-builtin.h, ov-cell.h, ov-ch-mat.h, ov-class.h,
ov-classdef.h, ov-colon.h, ov-complex.h, ov-cs-list.h, ov-cx-diag.h,
ov-cx-mat.h, ov-cx-sparse.h, ov-dld-fcn.h, ov-fcn-handle.h,
ov-fcn-inline.h, ov-fcn.h, ov-float.h, ov-flt-complex.h,
ov-flt-cx-diag.h, ov-flt-cx-mat.h, ov-flt-re-diag.h, ov-flt-re-mat.h,
ov-int-traits.h, ov-int16.h, ov-int32.h, ov-int64.h, ov-int8.h,
ov-intx.h, ov-java.h, ov-lazy-idx.h, ov-mex-fcn.h, ov-null-mat.h,
ov-oncleanup.h, ov-perm.h, ov-range.h, ov-re-diag.h, ov-re-mat.h,
ov-re-sparse.h, ov-scalar.h, ov-str-mat.h, ov-struct.h,
ov-type-conv.h, ov-typeinfo.h, ov-uint16.h, ov-uint32.h, ov-uint64.h,
ov-uint8.h, ov-usr-fcn.h, ov.h, ovl.h, octave.h, op-int.h, ops.h,
options-usage.h, lex.h, parse.h, pt-all.h, pt-arg-list.h,
pt-array-list.h, pt-assign.h, pt-binop.h, pt-bp.h, pt-cbinop.h,
pt-cell.h, pt-check.h, pt-classdef.h, pt-cmd.h, pt-colon.h,
pt-const.h, pt-decl.h, pt-eval.h, pt-except.h, pt-exp.h,
pt-fcn-handle.h, pt-funcall.h, pt-id.h, pt-idx.h, pt-jump.h,
pt-loop.h, pt-mat.h, pt-misc.h, pt-pr-code.h, pt-select.h, pt-stmt.h,
pt-unop.h, pt-walk.h, pt.h, token.h, version.in.h, Array-util.h,
Array.h, CColVector.h, CDiagMatrix.h, CMatrix.h, CNDArray.h,
CRowVector.h, CSparse.h, DiagArray2.h, MArray.h, MDiagArray2.h,
MSparse.h, Matrix.h, MatrixType.h, PermMatrix.h, Range.h, Sparse.h,
boolMatrix.h, boolNDArray.h, boolSparse.h, chMatrix.h, chNDArray.h,
dColVector.h, dDiagMatrix.h, dMatrix.h, dNDArray.h, dRowVector.h,
dSparse.h, dim-vector.h, fCColVector.h, fCDiagMatrix.h, fCMatrix.h,
fCNDArray.h, fCRowVector.h, fColVector.h, fDiagMatrix.h, fMatrix.h,
fNDArray.h, fRowVector.h, idx-vector.h, int16NDArray.h,
int32NDArray.h, int64NDArray.h, int8NDArray.h, intNDArray.h,
uint16NDArray.h, uint32NDArray.h, uint64NDArray.h, uint8NDArray.h,
f77-fcn.h, lo-error.h, quit.h, CmplxAEPBAL.h, CmplxCHOL.h,
CmplxGEPBAL.h, CmplxHESS.h, CmplxLU.h, CmplxQR.h, CmplxQRP.h,
CmplxSCHUR.h, CmplxSVD.h, CollocWt.h, DAE.h, DAEFunc.h, DAERT.h,
DAERTFunc.h, DASPK.h, DASRT.h, DASSL.h, DET.h, EIG.h, LSODE.h, ODE.h,
ODEFunc.h, ODES.h, ODESFunc.h, Quad.h, base-aepbal.h, base-dae.h,
base-de.h, base-lu.h, base-min.h, base-qr.h, bsxfun-decl.h, bsxfun.h,
dbleAEPBAL.h, dbleCHOL.h, dbleGEPBAL.h, dbleHESS.h, dbleLU.h,
dbleQR.h, dbleQRP.h, dbleSCHUR.h, dbleSVD.h, eigs-base.h,
fCmplxAEPBAL.h, fCmplxCHOL.h, fCmplxGEPBAL.h, fCmplxHESS.h,
fCmplxLU.h, fCmplxQR.h, fCmplxQRP.h, fCmplxSCHUR.h, fCmplxSVD.h,
fEIG.h, floatAEPBAL.h, floatCHOL.h, floatGEPBAL.h, floatHESS.h,
floatLU.h, floatQR.h, floatQRP.h, floatSCHUR.h, floatSVD.h,
lo-mappers.h, lo-specfun.h, oct-convn.h, oct-fftw.h, oct-norm.h,
oct-rand.h, oct-spparms.h, randgamma.h, randmtzig.h, randpoisson.h,
sparse-chol.h, sparse-dmsolve.h, sparse-lu.h, sparse-qr.h,
Sparse-diag-op-defs.h, Sparse-op-decls.h, Sparse-op-defs.h,
Sparse-perm-op-defs.h, mx-base.h, mx-defs.h, mx-ext.h, mx-op-decl.h,
mx-op-defs.h, dir-ops.h, file-ops.h, file-stat.h, lo-sysdep.h,
mach-info.h, oct-env.h, oct-group.h, oct-openmp.h, oct-passwd.h,
oct-syscalls.h, oct-time.h, oct-uname.h, pathlen.h, sysdir.h,
syswait.h, action-container.h, base-list.h, byte-swap.h,
caseless-str.h, cmd-edit.h, cmd-hist.h, data-conv.h, functor.h,
glob-match.h, lo-array-errwarn.h, lo-array-gripes.h, lo-cutils.h,
lo-ieee.h, lo-macros.h, lo-math.h, lo-regexp.h, lo-traits.h,
lo-utils.h, oct-alloc.h, oct-base64.h, oct-binmap.h, oct-cmplx.h,
oct-glob.h, oct-inttypes.h, oct-locbuf.h, oct-mutex.h, oct-refcount.h,
oct-rl-edit.h, oct-rl-hist.h, oct-shlib.h, oct-sort.h, oct-sparse.h,
pathsearch.h, singleton-cleanup.h, sparse-sort.h, sparse-util.h,
statdefs.h, str-vec.h, sun-utils.h, unwind-prot.h, url-transfer.h:
Include octave-config.h.
author | John W. Eaton <jwe@octave.org> |
---|---|
date | Wed, 10 Feb 2016 14:25:53 -0500 |
parents | f7084eae3318 |
children | 6c2fd62db1f7 |
line wrap: on
line source
/* Copyright (C) 2012-2015 Max Brister This file is part of Octave. Octave is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version. Octave is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with Octave; see the file COPYING. If not, see <http://www.gnu.org/licenses/>. */ // Author: Max Brister <max@2bass.com> #if ! defined (octave_jit_ir_h) #define octave_jit_ir_h 1 #include "octave-config.h" #ifdef HAVE_LLVM #include <list> #include <stack> #include <set> #include "jit-typeinfo.h" // 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(branch); \ JIT_METH(cond_branch); \ JIT_METH(call); \ JIT_METH(extract_argument); \ JIT_METH(store_argument); \ JIT_METH(return); \ JIT_METH(phi); \ JIT_METH(variable); \ JIT_METH(error_check); \ JIT_METH(assign) \ JIT_METH(argument) \ JIT_METH(magic_end) #define JIT_VISIT_IR_CONST \ JIT_METH(const_bool); \ JIT_METH(const_scalar); \ JIT_METH(const_complex); \ JIT_METH(const_index); \ JIT_METH(const_string); \ JIT_METH(const_range) #define JIT_VISIT_IR_CLASSES \ JIT_VISIT_IR_NOTEMPLATE \ JIT_VISIT_IR_CONST // forward declare all ir classes #define JIT_METH(cname) \ class jit_ ## cname; JIT_VISIT_IR_NOTEMPLATE #undef JIT_METH // ABCs which aren't included in JIT_VISIT_IR_ALL class jit_instruction; class jit_terminator; template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T = T, bool QUOTE=false> class jit_const; typedef jit_const<bool, jit_typeinfo::get_bool> jit_const_bool; typedef jit_const<double, jit_typeinfo::get_scalar> jit_const_scalar; typedef jit_const<Complex, jit_typeinfo::get_complex> jit_const_complex; 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; // Creates and tracks memory for jit_value and subclasses. // Memory managment is simple, all values that are created live as long as the // factory. class jit_factory { typedef std::list<jit_value *> value_list; public: ~jit_factory (void); const value_list& constants (void) const { return mconstants; } template <typename T> T *create (void) { T *ret = new T (); track_value (ret); return ret; } #define DECL_ARG(n) const ARG ## n& arg ## n #define JIT_CREATE(N) \ template <typename T, OCT_MAKE_DECL_LIST (typename, ARG, N)> \ T *create (OCT_MAKE_LIST (DECL_ARG, N)) \ { \ T *ret = new T (OCT_MAKE_ARG_LIST (arg, N)); \ track_value (ret); \ return ret; \ } JIT_CREATE (1) JIT_CREATE (2) JIT_CREATE (3) JIT_CREATE (4) #undef JIT_CREATE #undef DECL_ARG private: void track_value (jit_value *v); value_list all_values; value_list mconstants; }; // A list of basic blocks (jit_block) which form some body of code. // // We do not directly inherit from std::list because we need to update the // blocks stashed location in push_back and insert. class jit_block_list { public: typedef std::list<jit_block *>::iterator iterator; typedef std::list<jit_block *>::const_iterator const_iterator; jit_block *back (void) const { return mlist.back (); } iterator begin (void) { return mlist.begin (); } const_iterator begin (void) const { return mlist.begin (); } iterator end (void) { return mlist.end (); } const_iterator end (void) const { return mlist.end (); } iterator erase (iterator iter) { return mlist.erase (iter); } jit_block *front (void) const { return mlist.front (); } void insert_after (iterator iter, jit_block *ablock); void insert_after (jit_block *loc, jit_block *ablock); void insert_before (iterator iter, jit_block *ablock); void insert_before (jit_block *loc, jit_block *ablock); void label (void); std::ostream& print (std::ostream& os, const std::string& header) const; std::ostream& print_dom (std::ostream& os) const; void push_back (jit_block *b); private: std::list<jit_block *> mlist; }; std::ostream& operator<<(std::ostream& os, const jit_block_list& blocks); class jit_value : public jit_internal_list<jit_value, jit_use> { public: jit_value (void) : llvm_value (0), ty (0), mlast_use (0), min_worklist (false) {} virtual ~jit_value (void); bool in_worklist (void) const { return min_worklist; } void stash_in_worklist (bool ain_worklist) { min_worklist = ain_worklist; } // The block of the first use which is not a jit_error_check // So this is not necessarily first_use ()->parent (). jit_block *first_use_block (void); // replace all uses with virtual void replace_with (jit_value *value); jit_type *type (void) const { return ty; } llvm::Type *type_llvm (void) const { return ty ? ty->to_llvm () : 0; } const std::string& type_name (void) const { return ty->name (); } void stash_type (jit_type *new_ty) { ty = new_ty; } std::string print_string (void) { std::stringstream ss; print (ss); return ss.str (); } jit_instruction *last_use (void) const { return mlast_use; } void stash_last_use (jit_instruction *alast_use) { mlast_use = alast_use; } virtual bool needs_release (void) const { return false; } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const = 0; virtual std::ostream& short_print (std::ostream& os) const { return print (os); } virtual void accept (jit_ir_walker& walker) = 0; bool has_llvm (void) const { return llvm_value; } llvm::Value *to_llvm (void) const { assert (llvm_value); return llvm_value; } void stash_llvm (llvm::Value *compiled) { llvm_value = compiled; } protected: std::ostream& print_indent (std::ostream& os, size_t indent = 0) const { for (size_t i = 0; i < indent * 8; ++i) os << " "; return os; } llvm::Value *llvm_value; private: jit_type *ty; jit_instruction *mlast_use; bool min_worklist; }; std::ostream& operator<< (std::ostream& os, const jit_value& value); std::ostream& jit_print (std::ostream& os, jit_value *avalue); class jit_use : public jit_internal_node<jit_value, jit_use> { public: // some compilers don't allow us to use jit_internal_node without template // paremeters typedef jit_internal_node<jit_value, jit_use> PARENT_T; jit_use (void) : muser (0), mindex (0) { } // we should really have a move operator, but not until c++11 :( jit_use (const jit_use& use) : muser (0), mindex (0) { *this = use; } jit_use& operator= (const jit_use& use) { stash_value (use.value (), use.user (), use.index ()); return *this; } 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) { PARENT_T::stash_value (avalue); mindex = aindex; muser = auser; } private: jit_instruction *muser; size_t mindex; }; class jit_instruction : public jit_value { public: // FIXME: this code could be so much pretier with varadic templates... jit_instruction (void) : mid (next_id ()), mparent (0) { } jit_instruction (size_t nargs) : mid (next_id ()), mparent (0) { already_infered.reserve (nargs); marguments.reserve (nargs); } #define STASH_ARG(i) stash_argument (i, arg ## i); #define JIT_INSTRUCTION_CTOR(N) \ jit_instruction (OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ : already_infered (N), marguments (N), mid (next_id ()), mparent (0) \ { \ OCT_ITERATE_MACRO (STASH_ARG, N); \ } JIT_INSTRUCTION_CTOR(1) JIT_INSTRUCTION_CTOR(2) JIT_INSTRUCTION_CTOR(3) JIT_INSTRUCTION_CTOR(4) #undef STASH_ARG #undef JIT_INSTRUCTION_CTOR jit_instruction (const std::vector<jit_value *>& aarguments) : already_infered (aarguments.size ()), marguments (aarguments.size ()), mid (next_id ()), mparent (0) { for (size_t i = 0; i < aarguments.size (); ++i) stash_argument (i, aarguments[i]); } static void reset_ids (void) { next_id (true); } jit_value *argument (size_t i) const { return marguments[i].value (); } llvm::Value *argument_llvm (size_t i) const { assert (argument (i)); return argument (i)->to_llvm (); } jit_type *argument_type (size_t i) const { return argument (i)->type (); } llvm::Type *argument_type_llvm (size_t i) const { assert (argument (i)); return argument_type (i)->to_llvm (); } std::ostream& print_argument (std::ostream& os, size_t i) const { if (argument (i)) return argument (i)->short_print (os); else return os << "NULL"; } void stash_argument (size_t i, jit_value *arg) { marguments[i].stash_value (arg, this, i); } void push_argument (jit_value *arg) { marguments.push_back (jit_use ()); stash_argument (marguments.size () - 1, arg); already_infered.push_back (0); } size_t argument_count (void) const { return marguments.size (); } void resize_arguments (size_t acount, jit_value *adefault = 0) { size_t old = marguments.size (); marguments.resize (acount); already_infered.resize (acount); if (adefault) for (size_t i = old; i < acount; ++i) stash_argument (i, adefault); } const std::vector<jit_use>& arguments (void) const { return marguments; } // argument types which have been infered already const std::vector<jit_type *>& argument_types (void) const { return already_infered; } virtual void push_variable (void) { } virtual void pop_variable (void) { } virtual void construct_ssa (void) { do_construct_ssa (0, argument_count ()); } virtual bool infer (void) { return false; } void remove (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, std::list<jit_instruction *>::iterator alocation) { mparent = aparent; mlocation = alocation; } size_t id (void) const { return mid; } protected: // Do SSA replacement on arguments in [start, end) void do_construct_ssa (size_t start, size_t end); std::vector<jit_type *> already_infered; private: static size_t next_id (bool reset = false) { static size_t ret = 0; if (reset) return ret = 0; return ret++; } std::vector<jit_use> marguments; size_t mid; jit_block *mparent; std::list<jit_instruction *>::iterator mlocation; }; // defnie accept methods for subclasses #define JIT_VALUE_ACCEPT \ virtual void accept (jit_ir_walker& walker); // for use as a dummy argument during conversion to LLVM class jit_argument : public jit_value { public: jit_argument (jit_type *atype, llvm::Value *avalue) { stash_type (atype); stash_llvm (avalue); } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent); return jit_print (os, type ()) << ": DUMMY"; } JIT_VALUE_ACCEPT; }; template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T, bool QUOTE> class jit_const : public jit_value { public: typedef PASS_T pass_t; jit_const (PASS_T avalue) : mvalue (avalue) { stash_type (EXTRACT_T ()); } PASS_T value (void) const { return mvalue; } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent); jit_print (os, type ()) << ": "; if (QUOTE) os << "\""; os << mvalue; if (QUOTE) os << "\""; return os; } JIT_VALUE_ACCEPT; private: T mvalue; }; class jit_phi_incomming; class jit_block : public jit_value, public jit_internal_list<jit_block, jit_phi_incomming> { typedef jit_internal_list<jit_block, jit_phi_incomming> ILIST_T; public: typedef std::list<jit_instruction *> instruction_list; typedef instruction_list::iterator iterator; typedef instruction_list::const_iterator const_iterator; typedef std::set<jit_block *> df_set; typedef df_set::const_iterator df_iterator; static const size_t NO_ID = static_cast<size_t> (-1); jit_block (const std::string& aname, size_t avisit_count = 0) : mvisit_count (avisit_count), mid (NO_ID), idom (0), mname (aname), malive (false) { } virtual void replace_with (jit_value *value); void replace_in_phi (jit_block *ablock, jit_block *with); // we have a new internal list, but we want to stay compatible with jit_value jit_use *first_use (void) const { return jit_value::first_use (); } size_t use_count (void) const { return jit_value::use_count (); } // if a block is alive, then it might be visited during execution bool alive (void) const { return malive; } void mark_alive (void) { malive = true; } // If we can merge with a successor, do so and return the now empty block jit_block *maybe_merge (); // merge another block into this block, leaving the merge block empty void merge (jit_block& merge); const std::string& name (void) const { return mname; } jit_instruction *prepend (jit_instruction *instr); jit_instruction *prepend_after_phi (jit_instruction *instr); template <typename T> T *append (T *instr) { internal_append (instr); return instr; } jit_instruction *insert_before (iterator loc, jit_instruction *instr); jit_instruction *insert_before (jit_instruction *loc, jit_instruction *instr) { return insert_before (loc->location (), instr); } jit_instruction *insert_after (iterator loc, jit_instruction *instr); jit_instruction *insert_after (jit_instruction *loc, jit_instruction *instr) { return insert_after (loc->location (), instr); } iterator remove (iterator iter) { jit_instruction *instr = *iter; iter = instructions.erase (iter); instr->stash_parent (0, instructions.end ()); return iter; } jit_terminator *terminator (void) const; // is the jump from pred alive? bool branch_alive (jit_block *asucc) const; jit_block *successor (size_t i) const; size_t successor_count (void) const; iterator begin (void) { return instructions.begin (); } const_iterator begin (void) const { return instructions.begin (); } iterator end (void) { return instructions.end (); } const_iterator end (void) const { return instructions.end (); } iterator phi_begin (void); iterator phi_end (void); iterator nonphi_begin (void); // must label before id is valid size_t id (void) const { return mid; } // dominance frontier const df_set& df (void) const { return mdf; } df_iterator df_begin (void) const { return mdf.begin (); } df_iterator df_end (void) const { return mdf.end (); } // label with a RPO walk void label (void) { size_t number = 0; label (mvisit_count, number); } void label (size_t avisit_count, size_t& number); // See for idom computation algorithm // Cooper, Keith D.; Harvey, Timothy J; and Kennedy, Ken (2001). // "A Simple, Fast Dominance Algorithm" void compute_idom (jit_block& entry_block) { bool changed; entry_block.idom = &entry_block; do changed = update_idom (mvisit_count); while (changed); } // compute dominance frontier void compute_df (void) { compute_df (mvisit_count); } void create_dom_tree (void) { create_dom_tree (mvisit_count); } jit_block *dom_successor (size_t idx) const { return dom_succ[idx]; } size_t dom_successor_count (void) const { return dom_succ.size (); } // call pop_varaible on all instructions void pop_all (void); virtual std::ostream& print (std::ostream& os, size_t indent = 0) const; jit_block *maybe_split (jit_factory& factory, jit_block_list& blocks, jit_block *asuccessor); jit_block *maybe_split (jit_factory& factory, jit_block_list& blocks, jit_block& asuccessor) { return maybe_split (factory, blocks, &asuccessor); } // print dominator infomration std::ostream& print_dom (std::ostream& os) const; virtual std::ostream& short_print (std::ostream& os) const { os << mname; if (mid != NO_ID) os << mid; else os << "!"; return os; } llvm::BasicBlock *to_llvm (void) const; std::list<jit_block *>::iterator location (void) const { return mlocation; } void stash_location (std::list<jit_block *>::iterator alocation) { mlocation = alocation; } // used to prevent visiting the same node twice in the graph size_t visit_count (void) const { return mvisit_count; } // check if this node has been visited yet at the given visit count. If we // have not been visited yet, mark us as visited. bool visited (size_t avisit_count) { if (mvisit_count <= avisit_count) { mvisit_count = avisit_count + 1; return false; } return true; } jit_instruction *front (void) { return instructions.front (); } jit_instruction *back (void) { return instructions.back (); } JIT_VALUE_ACCEPT; private: void internal_append (jit_instruction *instr); void compute_df (size_t avisit_count); bool update_idom (size_t avisit_count); void create_dom_tree (size_t avisit_count); static jit_block *idom_intersect (jit_block *i, jit_block *j); size_t mvisit_count; size_t mid; jit_block *idom; df_set mdf; std::vector<jit_block *> dom_succ; std::string mname; instruction_list instructions; bool malive; std::list<jit_block *>::iterator mlocation; }; // keeps track of phi functions that use a block on incomming edges class jit_phi_incomming : public jit_internal_node<jit_block, jit_phi_incomming> { public: jit_phi_incomming (void) : muser (0) { } jit_phi_incomming (jit_phi *auser) : muser (auser) { } jit_phi_incomming (const jit_phi_incomming& use) { *this = use; } jit_phi_incomming& operator= (const jit_phi_incomming& use) { stash_value (use.value ()); muser = use.muser; return *this; } jit_phi *user (void) const { return muser; } jit_block *user_parent (void) const; private: jit_phi *muser; }; // A non-ssa variable class jit_variable : public jit_value { public: 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 bool has_top (void) const { return ! value_stack.empty (); } jit_value *top (void) const { return value_stack.top (); } 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) { jit_use *use = first_use (); while (use) { result.insert (use->user_parent ()); use = use->next (); } } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { return print_indent (os, indent) << mname; } JIT_VALUE_ACCEPT; private: std::string mname; std::stack<jit_value *> value_stack; jit_instruction *mlast_use; }; class jit_assign_base : public jit_instruction { public: jit_assign_base (jit_variable *adest) : jit_instruction (), mdest (adest) { } jit_assign_base (jit_variable *adest, size_t npred) : jit_instruction (npred), mdest (adest) {} jit_assign_base (jit_variable *adest, jit_value *arg0, jit_value *arg1) : jit_instruction (arg0, arg1), mdest (adest) { } jit_variable *dest (void) const { return mdest; } virtual void push_variable (void) { mdest->push (this); } virtual void pop_variable (void) { mdest->pop (); } virtual std::ostream& short_print (std::ostream& os) const { if (type ()) jit_print (os, type ()) << ": "; dest ()->short_print (os); return os << "#" << id (); } private: jit_variable *mdest; }; class jit_assign : public jit_assign_base { public: jit_assign (jit_variable *adest, jit_value *asrc) : jit_assign_base (adest, adest, asrc), martificial (false) { } jit_value *overwrite (void) const { return argument (0); } jit_value *src (void) const { return argument (1); } // variables don't get modified in an SSA, but COW requires we modify // variables. An artificial assign is for when a variable gets modified. We // need an assign in the SSA, but the reference counts shouldn't be updated. bool artificial (void) const { return martificial; } void mark_artificial (void) { martificial = true; } virtual bool infer (void) { jit_type *stype = src ()->type (); if (stype != type()) { stash_type (stype); return true; } return false; } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent) << *this << " = " << *src (); if (artificial ()) os << " [artificial]"; return os; } JIT_VALUE_ACCEPT; private: bool martificial; }; class jit_phi : public jit_assign_base { public: jit_phi (jit_variable *adest, size_t npred) : jit_assign_base (adest, npred) { mincomming.reserve (npred); } // removes arguments form dead incomming jumps bool prune (void); void add_incomming (jit_block *from, jit_value *value) { push_argument (value); mincomming.push_back (jit_phi_incomming (this)); mincomming[mincomming.size () - 1].stash_value (from); } jit_block *incomming (size_t i) const { return mincomming[i].value (); } llvm::BasicBlock *incomming_llvm (size_t i) const { return incomming (i)->to_llvm (); } virtual void construct_ssa (void) { } virtual bool infer (void); virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { std::stringstream ss; print_indent (ss, indent); short_print (ss) << " phi "; std::string ss_str = ss.str (); std::string indent_str (ss_str.size (), ' '); os << ss_str; for (size_t i = 0; i < argument_count (); ++i) { if (i > 0) os << indent_str; os << "| "; os << *incomming (i) << " -> "; os << *argument (i); if (i + 1 < argument_count ()) os << std::endl; } return os; } llvm::PHINode *to_llvm (void) const; JIT_VALUE_ACCEPT; private: std::vector<jit_phi_incomming> mincomming; }; class jit_terminator : public jit_instruction { public: #define JIT_TERMINATOR_CONST(N) \ jit_terminator (size_t asuccessor_count, \ OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ : jit_instruction (OCT_MAKE_ARG_LIST (arg, N)), \ malive (asuccessor_count, false) { } JIT_TERMINATOR_CONST (1) JIT_TERMINATOR_CONST (2) JIT_TERMINATOR_CONST (3) #undef JIT_TERMINATOR_CONST jit_block *successor (size_t idx = 0) const { return static_cast<jit_block *> (argument (idx)); } llvm::BasicBlock *successor_llvm (size_t idx = 0) const { return successor (idx)->to_llvm (); } size_t successor_index (const jit_block *asuccessor) const; std::ostream& print_successor (std::ostream& os, size_t idx = 0) const { if (alive (idx)) os << "[live] "; else os << "[dead] "; return successor (idx)->short_print (os); } // Check if the jump to successor is live bool alive (const jit_block *asuccessor) const { return alive (successor_index (asuccessor)); } bool alive (size_t idx) const { return malive[idx]; } bool alive (int idx) const { return malive[idx]; } size_t successor_count (void) const { return malive.size (); } virtual bool infer (void); llvm::TerminatorInst *to_llvm (void) const; protected: virtual bool check_alive (size_t) const { return true; } private: std::vector<bool> malive; }; class jit_branch : public jit_terminator { public: jit_branch (jit_block *succ) : jit_terminator (1, succ) { } virtual size_t successor_count (void) const { return 1; } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent) << "branch: "; return print_successor (os); } JIT_VALUE_ACCEPT; }; class jit_cond_branch : public jit_terminator { public: jit_cond_branch (jit_value *c, jit_block *ctrue, jit_block *cfalse) : jit_terminator (2, ctrue, cfalse, c) { } jit_value *cond (void) const { return argument (2); } std::ostream& print_cond (std::ostream& os) const { return cond ()->short_print (os); } llvm::Value *cond_llvm (void) const { return cond ()->to_llvm (); } virtual size_t successor_count (void) const { return 2; } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent) << "cond_branch: "; print_cond (os) << ", "; print_successor (os, 0) << ", "; return print_successor (os, 1); } JIT_VALUE_ACCEPT; }; class jit_call : public jit_instruction { public: jit_call (const jit_operation& (*aoperation) (void)) : moperation (aoperation ()) { const jit_function& ol = overload (); if (ol.valid ()) stash_type (ol.result ()); } jit_call (const jit_operation& aoperation) : moperation (aoperation) { const jit_function& ol = overload (); if (ol.valid ()) stash_type (ol.result ()); } #define JIT_CALL_CONST(N) \ jit_call (const jit_operation& aoperation, \ OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ : jit_instruction (OCT_MAKE_ARG_LIST (arg, N)), moperation (aoperation) { } \ \ jit_call (const jit_operation& (*aoperation) (void), \ OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ : jit_instruction (OCT_MAKE_ARG_LIST (arg, N)), moperation (aoperation ()) \ { } JIT_CALL_CONST (1) JIT_CALL_CONST (2) JIT_CALL_CONST (3) JIT_CALL_CONST (4) #undef JIT_CALL_CONST jit_call (const jit_operation& aoperation, const std::vector<jit_value *>& args) : jit_instruction (args), moperation (aoperation) { } const jit_operation& operation (void) const { return moperation; } bool can_error (void) const { return overload ().can_error (); } const jit_function& overload (void) const { return moperation.overload (argument_types ()); } virtual bool needs_release (void) const; virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent); if (use_count ()) short_print (os) << " = "; os << "call " << moperation.name () << " ("; for (size_t i = 0; i < argument_count (); ++i) { print_argument (os, i); if (i + 1 < argument_count ()) os << ", "; } return os << ")"; } virtual bool infer (void); JIT_VALUE_ACCEPT; private: const jit_operation& moperation; }; // FIXME: This is just ugly... // checks error_state, if error_state is false then goto the normal branch, // otherwise goto the error branch class jit_error_check : public jit_terminator { public: // Which variable is the error check for? enum variable { var_error_state, var_interrupt }; static std::string variable_to_string (variable v); jit_error_check (variable var, jit_call *acheck_for, jit_block *normal, jit_block *error) : jit_terminator (2, error, normal, acheck_for), mvariable (var) { } jit_error_check (variable var, jit_block *normal, jit_block *error) : jit_terminator (2, error, normal), mvariable (var) { } variable check_variable (void) const { return mvariable; } bool has_check_for (void) const { return argument_count () == 3; } jit_call *check_for (void) const { assert (has_check_for ()); return static_cast<jit_call *> (argument (2)); } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const; JIT_VALUE_ACCEPT; protected: virtual bool check_alive (size_t idx) const { if (! has_check_for ()) return true; return idx == 1 ? true : check_for ()->can_error (); } private: variable mvariable; }; // for now only handles the 1D case class jit_magic_end : public jit_instruction { public: class context { public: context (void) : value (0), index (0), count (0) { } context (jit_factory& factory, jit_value *avalue, size_t aindex, size_t acount); jit_value *value; jit_const_index *index; jit_const_index *count; }; jit_magic_end (const std::vector<context>& full_context); virtual bool infer (void); const jit_function& overload () const; virtual std::ostream& print (std::ostream& os, size_t indent = 0) const; context resolve_context (void) const; virtual std::ostream& short_print (std::ostream& os) const { return os << "magic_end" << "#" << id (); } JIT_VALUE_ACCEPT; private: std::vector<context> contexts; }; class jit_extract_argument : public jit_assign_base { public: jit_extract_argument (jit_type *atype, jit_variable *adest) : jit_assign_base (adest) { stash_type (atype); } const std::string& name (void) const { return dest ()->name (); } const jit_function& overload (void) const { return jit_typeinfo::cast (type (), jit_typeinfo::get_any ()); } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent); return short_print (os) << " = extract " << name (); } JIT_VALUE_ACCEPT; }; class jit_store_argument : public jit_instruction { public: jit_store_argument (jit_variable *var) : jit_instruction (var), dest (var) { } const std::string& name (void) const { return dest->name (); } const jit_function& overload (void) const { return jit_typeinfo::cast (jit_typeinfo::get_any (), result_type ()); } jit_value *result (void) const { return argument (0); } jit_type *result_type (void) const { return result ()->type (); } llvm::Value *result_llvm (void) const { return result ()->to_llvm (); } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { jit_value *res = result (); print_indent (os, indent) << "store "; dest->short_print (os); if (! isa<jit_variable> (res)) { os << " = "; res->short_print (os); } return os; } JIT_VALUE_ACCEPT; private: jit_variable *dest; }; class jit_return : public jit_instruction { public: jit_return (void) { } jit_return (jit_value *retval) : jit_instruction (retval) { } jit_value *result (void) const { return argument_count () ? argument (0) : 0; } jit_type *result_type (void) const { jit_value *res = result (); return res ? res->type () : 0; } virtual std::ostream& print (std::ostream& os, size_t indent = 0) const { print_indent (os, indent) << "return"; if (result ()) os << " " << *result (); return os; } JIT_VALUE_ACCEPT; }; class jit_ir_walker { public: virtual ~jit_ir_walker () { } #define JIT_METH(clname) \ virtual void visit (jit_ ## clname&) = 0; JIT_VISIT_IR_CLASSES; #undef JIT_METH }; template <typename T, jit_type *(*EXTRACT_T)(void), typename PASS_T, bool QUOTE> void jit_const<T, EXTRACT_T, PASS_T, QUOTE>::accept (jit_ir_walker& walker) { walker.visit (*this); } #undef JIT_VALUE_ACCEPT #endif #endif