Mercurial > octave-dspies
changeset 15002:3172d7916158
Merge erroneously crated head
| author | Carlo de Falco <cdf@users.sourceforge.net> |
|---|---|
| date | Sun, 22 Jul 2012 04:16:02 +0200 |
| parents | 894cf2c07f92 (diff) 4c8ddf57fcda (current diff) |
| children | 1f5dbfc23fc2 |
| files | scripts/pkg/private/absolute_pathname.m |
| diffstat | 47 files changed, 7414 insertions(+), 95 deletions(-) [+] |
line wrap: on
line diff
--- a/NEWS Thu Jul 19 21:28:00 2012 +0200 +++ b/NEWS Sun Jul 22 04:16:02 2012 +0200 @@ -74,10 +74,13 @@ ** Other new functions added in 3.8.0: - betaincinv lines tetramesh - colorcube rgbplot - erfcinv shrinkfaces - findfigs splinefit + betaincinv erfcinv splinefit + cmpermute findfigs tetramesh + cmunique fminsearch rgbplot + colorcube lines shrinkfaces + + ** The default name of the Octave crash dump file is now called + octave-workspace instead of octave-core. ** Deprecated functions.
--- a/build-aux/common.mk Thu Jul 19 21:28:00 2012 +0200 +++ b/build-aux/common.mk Sun Jul 22 04:16:02 2012 +0200 @@ -181,6 +181,10 @@ Z_LDFLAGS = @Z_LDFLAGS@ Z_LIBS = @Z_LIBS@ +LLVM_CPPFLAGS = @LLVM_CPPFLAGS@ +LLVM_LDFLAGS = @LLVM_LDFLAGS@ +LLVM_LIBS = @LLVM_LIBS@ + GRAPHICS_LIBS = @GRAPHICS_LIBS@ QHULL_CPPFLAGS = @QHULL_CPPFLAGS@ @@ -252,7 +256,7 @@ DL_LIBS = @DL_LIBS@ LIBS = @LIBS@ -ALL_CPPFLAGS = $(CPPFLAGS) $(HDF5_CPPFLAGS) $(Z_CPPFLAGS) +ALL_CPPFLAGS = $(CPPFLAGS) $(HDF5_CPPFLAGS) $(Z_CPPFLAGS) $(LLVM_CPPFLAGS) SPARSE_XCPPFLAGS = \ $(CHOLMOD_CPPFLAGS) $(UMFPACK_CPPFLAGS) \ @@ -544,6 +548,9 @@ -e "s|%OCTAVE_CONF_MAGICK_CPPFLAGS%|\"${MAGICK_CPPFLAGS}\"|" \ -e "s|%OCTAVE_CONF_MAGICK_LDFLAGS%|\"${MAGICK_LDFLAGS}\"|" \ -e "s|%OCTAVE_CONF_MAGICK_LIBS%|\"${MAGICK_LIBS}\"|" \ + -e "s|%OCTAVE_CONF_LLVM_CPPFLAGS%|\"${LLVM_CPPFLAGS}\"|" \ + -e "s|%OCTAVE_CONF_LLVM_LDFLAGS%|\"${LLVM_LDFLAGS}\"|" \ + -e "s|%OCTAVE_CONF_LLVM_LIBS%|\"${LLVM_LIBS}\"|" \ -e 's|%OCTAVE_CONF_MKOCTFILE_DL_LDFLAGS%|\"@MKOCTFILE_DL_LDFLAGS@\"|' \ -e "s|%OCTAVE_CONF_OCTAVE_LINK_DEPS%|\"${OCTAVE_LINK_DEPS}\"|" \ -e "s|%OCTAVE_CONF_OCTAVE_LINK_OPTS%|\"${OCTAVE_LINK_OPTS}\"|" \
--- a/configure.ac Thu Jul 19 21:28:00 2012 +0200 +++ b/configure.ac Sun Jul 22 04:16:02 2012 +0200 @@ -715,6 +715,96 @@ [ZLIB library not found. Octave will not be able to save or load compressed data files or HDF5 files.], [zlib.h], [gzclearerr]) +### Check for the llvm library +dnl +dnl +dnl llvm is odd and has its own pkg-config like script. We should probably check +dnl for existance and +dnl +save_CPPFLAGS="$CPPFLAGS" +save_CXXFLAGS="$CXXFLAGS" +save_LIBS="$LIBS" +save_LDFLAGS="$LDFLAGS" + +warn_llvm="LLVM library fails tests. JIT compilation will be disabled." + +AC_ARG_VAR(LLVM_CONFIG, [path to llvm-config utility]) + +AC_ARG_ENABLE([jit-debug], + AS_HELP_STRING([--enable-jit-debug], [Enable debug printing of jit IRs])) + +AS_IF([test "x$enable_jit_debug" = "xyes"], [ + AC_DEFINE(OCTAVE_JIT_DEBUG, 1, [Define for jit debug printing]) +]) + +LLVM_CXXFLAGS= +LLVM_CPPFLAGS= +LLVM_LDFLAGS= +LLVM_LIBS= + +if test "x$ac_cv_env_LLVM_CONFIG_set" = "xset"; then + # We use -isystem if avaiable because we do not want to see warnings in llvm + LLVM_INCLUDE_FLAG=-I + OCTAVE_CC_FLAG(-isystem ., [ + LLVM_INCLUDE_FLAG=-isystem + AC_MSG_NOTICE([using -isystem for llvm headers])]) + + LLVM_LDFLAGS="-L`$LLVM_CONFIG --libdir`" + LLVM_LIBS=`$LLVM_CONFIG --libs` + dnl Use -isystem so we don't get warnings from llvm headers + LLVM_CPPFLAGS="$LLVM_INCLUDE_FLAG `$LLVM_CONFIG --includedir`" + LLVM_CXXFLAGS= + + dnl + dnl We define some extra flags that llvm requires in order to include headers. + dnl Idealy we should get these from llvm-config, but llvm-config isn't very + dnl helpful. + dnl + CPPFLAGS="-D__STDC_CONSTANT_MACROS -D__STDC_LIMIT_MACROS $LLVM_CPPFLAGS $CPPFLAGS" + CXXFLAGS="$LLVM_CXXFLAGS $CXXFLAGS" + LIBS="$LLVM_LIBS $LIBS" + LDFLAGS="$LLVM_LDFLAGS $LDFLAGS" + + AC_LANG_PUSH(C++) + AC_CHECK_HEADER([llvm/LLVMContext.h], [ + AC_MSG_CHECKING([for llvm::getGlobalContext in llvm/LLVMContext.h]) + AC_COMPILE_IFELSE( + [AC_LANG_PROGRAM([[#include <llvm/LLVMContext.h>]], + [[llvm::LLVMContext& ctx = llvm::getGlobalContext ();]])], + [ + AC_MSG_RESULT([yes]) + warn_llvm= + XTRA_CXXFLAGS="$XTRA_CXXFLAGS $LLVM_CXXFLAGS $LLVM_CPPFLAGS" + ], + [AC_MSG_RESULT([no]) + ]) + ]) + AC_LANG_POP(C++) + +else + warn_llvm="LLVM_CONFIG not set. JIT compilation will be disabled." +fi + +if test -z "$warn_llvm"; then + AC_DEFINE(HAVE_LLVM, 1, [Define if LLVM is available]) +else + LLVM_CXXFLAGS= + LLVM_CPPFLAGS= + LLVM_LDFLAGS= + LLVM_LIBS= + OCTAVE_CONFIGURE_WARNING([warn_llvm]) +fi + +AC_SUBST(LLVM_CXXFLAGS) +AC_SUBST(LLVM_CPPFLAGS) +AC_SUBST(LLVM_LDFLAGS) +AC_SUBST(LLVM_LIBS) + +CPPFLAGS="$save_CPPFLAGS" +CXXFLAGS="$save_CXXFLAGS" +LIBS="$save_LIBS" +LDFLAGS="$save_LDFLAGS" + ### Check for HDF5 library. save_CPPFLAGS="$CPPFLAGS" @@ -2245,6 +2335,9 @@ Magick++ CPPFLAGS: $MAGICK_CPPFLAGS Magick++ LDFLAGS: $MAGICK_LDFLAGS Magick++ libraries: $MAGICK_LIBS + LLVM CPPFLAGS: $LLVM_CPPFLAGS + LLVM LDFLAGS: $LLVM_LDFLAGS + LLVM Libraries: $LLVM_LIBS HDF5 CPPFLAGS: $HDF5_CPPFLAGS HDF5 LDFLAGS: $HDF5_LDFLAGS HDF5 libraries: $HDF5_LIBS
--- a/doc/interpreter/contrib.txi Thu Jul 19 21:28:00 2012 +0200 +++ b/doc/interpreter/contrib.txi Sun Jul 22 04:16:02 2012 +0200 @@ -135,7 +135,11 @@ @section Basics of Generating a Changeset The preferable form of contribution is creating a Mercurial changeset -and sending it via e-mail to the octave-maintainers mailing list. +and submit it to the @uref{http://savannah.gnu.org/bugs/?group=octave, bug} or +@uref{http://savannah.gnu.org/patch/?func=additem&group=octave, patch} +trackers@footnote{Please use the patch tracker only for patches which add new +features. If you have a patch to submit that fixes a bug, you should use the +bug tracker instead.}. Mercurial is the source code management system currently used to develop Octave. Other forms of contributions (e.g., simple diff patches) are also acceptable, but they slow down the review process. If you want to @@ -159,15 +163,14 @@ hg export -o ../cool.diff tip # export the changeset to a diff # file -# send ../cool.diff via email +# attach ../cool.diff to your bug report @end group @end example You may want to get familiar with Mercurial queues to manage your changesets. Here is a slightly more complex example using Mercurial queues, where work on two unrelated changesets is done in parallel and -one of the changesets is updated after discussion on the maintainers -mailing list: +one of the changesets is updated after discussion on the bug tracker: @example hg qnew nasty_bug # create a new patch @@ -178,7 +181,7 @@ # save again with commit message hg export -o ../nasty.diff tip # export the patch -# send ../nasty.diff via email +# attach ../nasty.diff to your bug report hg qpop # undo the application of the patch # and remove the changes from the # source tree @@ -188,14 +191,14 @@ # save the changes into the patch hg export -o ../doc.diff tip # export the second patch -# send ../doc.diff tip via email +# attach ../doc.diff to your bug report hg qpop -# discussion in the maintainers mailing list @dots{} +# discussion in the bug tracker @dots{} hg qpush nasty_bug # apply the patch again # change sources yet again @dots{} hg qref hg export -o ../nasty2.diff tip -# send ../nasty2.diff via email +# attach ../nasty2.diff to your bug report @end example @node General Guidelines
--- a/doc/interpreter/image.txi Thu Jul 19 21:28:00 2012 +0200 +++ b/doc/interpreter/image.txi Sun Jul 22 04:16:02 2012 +0200 @@ -93,15 +93,15 @@ @node Representing Images @section Representing Images -In general Octave supports four different kinds of images, gray-scale -images, RGB images, binary images, and indexed images. A gray-scale +In general Octave supports four different kinds of images, grayscale +images, RGB images, binary images, and indexed images. A grayscale image is represented with an M-by-N matrix in which each element corresponds to the intensity of a pixel. An RGB image is represented with an M-by-N-by-3 array where each 3-vector corresponds to the red, green, and blue intensities of each pixel. -The actual meaning of the value of a pixel in a gray-scale or RGB +The actual meaning of the value of a pixel in a grayscale or RGB image depends on the class of the matrix. If the matrix is of class @code{double} pixel intensities are between 0 and 1, if it is of class @code{uint8} intensities are between 0 and 255, and if it is of class @@ -187,6 +187,12 @@ @DOCSTRING(whitebg) +The following functions can be used to manipulate colormaps. + +@DOCSTRING(cmunique) + +@DOCSTRING(cmpermute) + @node Plotting on top of Images @section Plotting on top of Images
--- a/doc/interpreter/io.txi Thu Jul 19 21:28:00 2012 +0200 +++ b/doc/interpreter/io.txi Sun Jul 22 04:16:02 2012 +0200 @@ -239,7 +239,7 @@ If Octave for some reason exits unexpectedly it will by default save the variables available in the workspace to a file in the current directory. -By default this file is named @samp{octave-core} and can be loaded +By default this file is named @samp{octave-workspace} and can be loaded into memory with the @code{load} command. While the default behavior most often is reasonable it can be changed through the following functions.
--- a/doc/interpreter/nonlin.txi Thu Jul 19 21:28:00 2012 +0200 +++ b/doc/interpreter/nonlin.txi Sun Jul 22 04:16:02 2012 +0200 @@ -172,7 +172,11 @@ the zeroes where it crosses the x-axis. @code{fminbnd} is designed for the simpler, but very common, case of a univariate function where the interval to search is bounded. For unbounded minimization of a function with -potentially many variables use @code{fminunc}. @xref{Optimization}, for +potentially many variables use @code{fminunc} or @code{fminsearch}. The two +functions use different internal algorithms and some knowledge of the objective +function is required. For functions which can be differentiated, @code{fminunc} +is appropriate. For functions with discontinuities, or for which a gradient +search would fail, use @code{fminsearch}. @xref{Optimization}, for minimization with the presence of constraint functions. Note that searches can be made for maxima by simply inverting the objective function @tex @@ -186,3 +190,5 @@ @DOCSTRING(fminunc) +@DOCSTRING(fminsearch) +
--- a/liboctave/Array.h Thu Jul 19 21:28:00 2012 +0200 +++ b/liboctave/Array.h Sun Jul 22 04:16:02 2012 +0200 @@ -164,6 +164,14 @@ return &nr; } +protected: + + // For jit support + Array (T *sdata, octave_idx_type slen, octave_idx_type *adims, void *arep) + : dimensions (adims), + rep (reinterpret_cast<typename Array<T>::ArrayRep *> (arep)), + slice_data (sdata), slice_len (slen) {} + public: // Empty ctor (0x0). @@ -693,6 +701,16 @@ // supposedly equal dimensions (e.g. structs in the interpreter). bool optimize_dimensions (const dim_vector& dv); + // WARNING: Only call these functions from jit + + int *jit_ref_count (void) { return rep->count.get (); } + + T *jit_slice_data (void) const { return slice_data; } + + octave_idx_type *jit_dimensions (void) const { return dimensions.to_jit (); } + + void *jit_array_rep (void) const { return rep; } + private: void resize2 (octave_idx_type nr, octave_idx_type nc, const T& rfv);
--- a/liboctave/MArray.h Thu Jul 19 21:28:00 2012 +0200 +++ b/liboctave/MArray.h Sun Jul 22 04:16:02 2012 +0200 @@ -39,6 +39,12 @@ class MArray : public Array<T> { +protected: + + // For jit support + MArray (T *sdata, octave_idx_type slen, octave_idx_type *adims, void *arep) + : Array<T> (sdata, slen, adims, arep) { } + public: MArray (void) : Array<T> () {}
--- a/liboctave/dNDArray.h Thu Jul 19 21:28:00 2012 +0200 +++ b/liboctave/dNDArray.h Sun Jul 22 04:16:02 2012 +0200 @@ -64,6 +64,10 @@ NDArray (const charNDArray&); + // For jit support only + NDArray (double *sdata, octave_idx_type slen, octave_idx_type *adims, void *arep) + : MArray<double> (sdata, slen, adims, arep) { } + NDArray& operator = (const NDArray& a) { MArray<double>::operator = (a);
--- a/liboctave/dim-vector.h Thu Jul 19 21:28:00 2012 +0200 +++ b/liboctave/dim-vector.h Sun Jul 22 04:16:02 2012 +0200 @@ -212,6 +212,12 @@ void chop_all_singletons (void); + // WARNING: Only call by jit + octave_idx_type *to_jit (void) const + { + return rep; + } + private: static octave_idx_type *nil_rep (void) @@ -220,9 +226,6 @@ return zv.rep; } - explicit dim_vector (octave_idx_type *r) - : rep (r) { } - public: static octave_idx_type dim_max (void); @@ -233,6 +236,10 @@ dim_vector (const dim_vector& dv) : rep (dv.rep) { OCTREFCOUNT_ATOMIC_INCREMENT (&(count())); } + // FIXME: Should be private, but required by array constructor for jit + explicit dim_vector (octave_idx_type *r) + : rep (r) { } + static dim_vector alloc (int n) { return dim_vector (newrep (n < 2 ? 2 : n));
--- a/liboctave/lo-macros.h Thu Jul 19 21:28:00 2012 +0200 +++ b/liboctave/lo-macros.h Sun Jul 22 04:16:02 2012 +0200 @@ -92,4 +92,8 @@ #define OCT_MAKE_DECL_LIST(TYPE, PREFIX, NUM) \ OCT_ITERATE_PARAM_MACRO(OCT_MAKE_DECL_LIST_HELPER, TYPE PREFIX, NUM) +// expands to PREFIX0, PREFIX1, ..., PREFIX ## (NUM-1) +#define OCT_MAKE_ARG_LIST(PREFIX, NUM) \ + OCT_ITERATE_PARAM_MACRO(OCT_MAKE_DECL_LIST_HELPER, PREFIX, NUM) + #endif
--- a/liboctave/oct-refcount.h Thu Jul 19 21:28:00 2012 +0200 +++ b/liboctave/oct-refcount.h Sun Jul 22 04:16:02 2012 +0200 @@ -82,6 +82,11 @@ return static_cast<count_type const volatile&> (count); } + count_type *get (void) + { + return &count; + } + private: count_type count; };
--- a/m4/acinclude.m4 Thu Jul 19 21:28:00 2012 +0200 +++ b/m4/acinclude.m4 Sun Jul 22 04:16:02 2012 +0200 @@ -286,7 +286,7 @@ dnl dnl OCTAVE_CC_FLAG AC_DEFUN([OCTAVE_CC_FLAG], [ - ac_safe=`echo "$1" | sed 'y%./+-:=%__p___%'` + ac_safe=`echo "$1" | sed 'y% ./+-:=%___p___%'` AC_MSG_CHECKING([whether ${CC-cc} accepts $1]) AC_CACHE_VAL(octave_cv_cc_flag_$ac_safe, [ AC_LANG_PUSH(C)
--- a/scripts/geometry/voronoi.m Thu Jul 19 21:28:00 2012 +0200 +++ b/scripts/geometry/voronoi.m Sun Jul 22 04:16:02 2012 +0200 @@ -126,8 +126,8 @@ xbox = [xmin - scale * xdelta; xmin - scale * xdelta; ... xmax + scale * xdelta; xmax + scale * xdelta]; - ybox = [xmin - scale * xdelta; xmax + scale * xdelta; ... - xmax + scale * xdelta; xmin - scale * xdelta]; + ybox = [ymin - scale * ydelta; ymax + scale * ydelta; ... + ymax + scale * ydelta; ymin - scale * ydelta]; [p, c, infi] = __voronoi__ ("voronoi", [[x(:) ; xbox(:)], [y(:); ybox(:)]],
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/image/cmpermute.m Sun Jul 22 04:16:02 2012 +0200 @@ -0,0 +1,144 @@ +## Copyright (C) 2004 Josep Mones i Teixidor +## Copyright (C) 2012 Rik Wehbring +## +## 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/>. + +## -*- texinfo -*- +## @deftypefn {Function File} {[@var{Y}, @var{newmap}] =} cmpermute (@var{X}, @var{map}) +## @deftypefnx {Function File} {[@var{Y}, @var{newmap}] =} cmpermute (@var{X}, @var{map}, @var{index}) +## Reorder colors in a colormap. +## +## When called with only two arguments, @code{cmpermute} randomly rearranges +## the colormap @var{map} and returns a new colormap @var{newmap}. It also +## returns the indexed image @var{Y} which is the equivalent of the original +## input image @var{X} when displayed using @var{newmap}. The input image +## @var{X} must be an indexed image of class uint8 or double. +## +## When called with an optional third argument the order of colors in the +## new colormap is defined by @var{index}. +## +## @strong{Caution:} @code{index} should not have repeated elements or the +## function will fail. +## +## @end deftypefn + +## Author: Josep Mones i Teixidor <jmones@puntbarra.com> + +function [Y, newmap] = cmpermute (X, map, index) + + if (nargin < 2 || nargin > 3) + print_usage (); + endif + + ## FIXME: Matlab only accepts 2 types. Expand to uint16 & single?? + if (! (isa (X, "uint8") || isa (X, "double"))) + error ("cmpermute: X must be of class uint8 or double"); + endif + + if (! isreal (X) || issparse (X) + || (isfloat (X) && (any (X(:) < 1 || any (X(:) != fix (X(:))))))) + error ("cmpermute: X must be an indexed image"); + endif + + if (! isnumeric (map) || iscomplex (map) + || ndims (map) != 2 || columns (map) != 3 + || any (map(:) < 0) || any (map(:) > 1)) + error ("cmpermute: MAP must be a valid colormap"); + endif + + if (nargin < 3) + index = randperm (rows (map)); + elseif (! isvector (index) || length (index) != rows (map)) + error ("cmpermute: invalid parameter INDEX"); + endif + + ## new colormap + newmap = map(index,:); + + ## build reverse index + rindex = zeros (size (index)); + rindex(index) = 1:length (index); + + ## adapt indices + if (isa (X, "uint8")) + rindex = uint8 (rindex-1); + ## 0-based indices + Y = rindex(double (X) + 1); + else + Y = rindex(X); + endif + +endfunction + + +%!demo +%! [Y, newmap] = cmpermute ([1:4], hot (4), 4:-1:1) +%! ## colormap will be arranged in reverse order (so will image) + +%!shared X, map +%! X = uint8 (magic (16)); +%! [X, map] = cmunique (X); + +%!test # random permutation, 0-based index +%! [Y, newmap] = cmpermute (X, map); +%! ## test we didn't lose colors +%! assert (sort (map), sortrows (newmap)); +%! ## test if images are equal +%! assert (map(double (X)+1), newmap(double (Y)+1)); + +%!test # reverse map, 0-based index +%! [Y, newmap] = cmpermute (X, map, rows (map):-1:1); +%! ## we expect a reversed colormap +%! assert (flipud (newmap), map); +%! ## we expect reversed indices in image +%! assert (X, max (Y(:)) - Y); + +%!shared X,map +%! X = uint16 (magic (20)); +%! [X, map] = cmunique (X); + +%!test # random permutation, 1-based index +%! [Y, newmap] = cmpermute (X, map); +%! ## test we didn't lose colors +%! assert (sort (map), sortrows (newmap)); +%! ## test if images are equal +%! assert (map(X), newmap(Y)); + +%!test # reverse map, 1-based index +%! [Y, newmap] = cmpermute (X, map, rows (map):-1:1); +%! ## we expect a reversed colormap +%! assert (newmap (rows (newmap):-1:1,:), map); +%! ## we expect reversed indices in image +%! assert (X, max (Y(:)) + 1 - Y); + +## Test input validation +%!error cmpermute () +%!error cmpermute (1,2,3,4) +%!error <X must be of class uint8> cmpermute (uint16 (magic (16)), jet (256)) +%!error <X must be an indexed image> cmpermute (1+i, jet (256)) +%!error <X must be an indexed image> cmpermute (sparse (1), jet (256)) +%!error <X must be an indexed image> cmpermute (0, jet (256)) +%!error <X must be an indexed image> cmpermute (1.5, jet (256)) +%!error <MAP must be a valid colormap> cmpermute (1, "a") +%!error <MAP must be a valid colormap> cmpermute (1, i) +%!error <MAP must be a valid colormap> cmpermute (1, ones (3,3,3)) +%!error <MAP must be a valid colormap> cmpermute (1, ones (3,2)) +%!error <MAP must be a valid colormap> cmpermute (1, [-1 1 1]) +%!error <MAP must be a valid colormap> cmpermute (1, [2 1 1]) +%!error <invalid parameter INDEX> cmpermute (1, [0 1 0;1 0 1], ones (3)) +%!error <invalid parameter INDEX> cmpermute (1, [0 1 0;1 0 1], 1:3) +
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/image/cmunique.m Sun Jul 22 04:16:02 2012 +0200 @@ -0,0 +1,204 @@ +## Copyright (C) 2004 Josep Mones i Teixidor +## Copyright (C) 2012 Rik Wehbring +## +## 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/>. + +## -*- texinfo -*- +## @deftypefn {Function File} {[@var{Y}, @var{newmap}] =} cmunique (@var{X}, @var{map}) +## @deftypefnx {Function File} {[@var{Y}, @var{newmap}] =} cmunique (@var{RGB}) +## @deftypefnx {Function File} {[@var{Y}, @var{newmap}] =} cmunique (@var{I}) +## Convert an input image @var{X} to an ouput indexed image @var{Y} which uses +## the smallest colormap possible @var{newmap}. +## +## When the input is an indexed image (@var{X} with colormap @var{map}) the +## output is a colormap @var{newmap} from which any repeated rows have been +## eliminated. The output image, @var{Y}, is the original input image with +## the indices adjusted to match the new, possibly smaller, colormap. +## +## When the input is an RGB image (an MxNx3 array), the output colormap +## will contain one entry for every unique color in the original image. +## In the worst case the new map could have as many rows as the number of +## pixels in the original image. +## +## When the input is a grayscale image @var{I}, the output colormap will +## contain one entry for every unique intensity value in the original image. +## In the worst case the new map could have as many rows as the number of +## pixels in the original image. +## +## Implementation Details: +## +## @var{newmap} is always an Mx3 matrix, even if the input image is +## an intensity grayscale image @var{I} (all three RGB planes are +## assigned the same value). +## +## The output image is of class uint8 if the size of the new colormap is +## less than or equal to 256. Otherwise, the output image is of class double. +## +## @seealso{rgb2ind, gray2ind} +## @end deftypefn + + +## Author: Josep Mones i Teixidor <jmones@puntbarra.com> + +function [Y, newmap] = cmunique (X, map) + + if (nargin < 1 || nargin > 2) + print_usage (); + endif + + cls = class (X); + ## FIXME: Documentation accepts only 3 classes. Could easily add 'single'. + if (! any (isa (X, {"uint8", "uint16", "double"}))) + error ("cmunique: X is of invalid data type '%s'", cls); + endif + + if (nargin == 2) + ## (X, map) case + if (! isnumeric (map) || iscomplex (map) + || ndims (map) != 2 || columns (map) != 3 + || any (map(:) < 0) || any (map(:) > 1)) + error ("cmunique: MAP must be a valid colormap"); + endif + [newmap,i,j] = unique (map, "rows"); # calculate unique colormap + if (isa (X, "double")) + Y = j(X); # find new indices + else + Y = j(double (X) + 1); # find new indices + endif + else + switch (size (X,3)) + case (1) + ## I case + [newmap,i,j] = unique (X); # calculate unique colormap + newmap = repmat (newmap,1,3); # get a RGB colormap + Y = reshape (j, rows (X), columns (X)); # Y is j reshaped + case (3) + ## RGB case + ## build a map with all values + map = [X(:,:,1)(:), X(:,:,2)(:), X(:,:,3)(:)]; + [newmap,i,j] = unique (map, "rows"); # calculate unique colormap + Y = reshape (j, rows (X), columns (X)); # Y is j reshaped + otherwise + error ("cmunique: X is not a valid image"); + endswitch + + ## if image was uint8 or uint16 we have to convert newmap to [0,1] range + if (! isa (X, "double")) + newmap = double (newmap) / double (intmax (class (X))); + endif + endif + + if (rows (newmap) <= 256) + ## convert Y to uint8 (0-based indices then) + Y = uint8 (Y-1); + endif + +endfunction + + +%!demo +%! [Y, newmap] = cmunique ([1:4;5:8], [hot(4);hot(4)]) +%! ## Both rows are equal since map maps colors to the same value +%! ## cmunique will give the same indices to both + +## Check that output is uint8 in short colormaps +%!test +%! [Y, newmap] = cmunique ([1:4;5:8], [hot(4);hot(4)]); +%! assert (Y, uint8 ([0:3;0:3])); +%! assert (newmap, hot (4)); + +## Check that output is double in bigger +%!test +%! [Y, newmap] = cmunique ([1:300;301:600], [hot(300);hot(300)]); +%! assert (Y, [1:300;1:300]); +%! assert (newmap, hot (300)); + +## Check boundary case 256 +%!test +%! [Y, newmap] = cmunique ([1:256;257:512], [hot(256);hot(256)]); +%! assert (Y, uint8 ([0:255;0:255])); +%! assert (newmap, hot (256)); + +## Check boundary case 257 +%!test +%! [Y, newmap] = cmunique ([1:257;258:514], [hot(257);hot(257)]); +%! assert (Y, [1:257;1:257]); +%! assert (newmap, hot (257)); + +## Random RGB image +%!test +%! RGB = rand (10,10,3); +%! [Y, newmap] = cmunique (RGB); +%! assert (RGB(:,:,1), newmap(:,1)(Y+1)); +%! assert (RGB(:,:,2), newmap(:,2)(Y+1)); +%! assert (RGB(:,:,3), newmap(:,3)(Y+1)); + +## Random uint8 RGB image +%!test +%! RGB = uint8 (rand (10,10,3)*255); +%! RGBd = double (RGB) / 255; +%! [Y, newmap] = cmunique (RGB); +%! assert (RGBd(:,:,1), newmap(:,1)(Y+1)); +%! assert (RGBd(:,:,2), newmap(:,2)(Y+1)); +%! assert (RGBd(:,:,3), newmap(:,3)(Y+1)); + +## Random uint16 RGB image +%!test +%! RGB = uint16 (rand (10,10,3)*65535); +%! RGBd = double (RGB) / 65535; +%! [Y, newmap] = cmunique (RGB); +%! assert (RGBd(:,:,1), newmap(:,1)(Y+1)); +%! assert (RGBd(:,:,2), newmap(:,2)(Y+1)); +%! assert (RGBd(:,:,3), newmap(:,3)(Y+1)); + +## Random I image +%!test +%! I = rand (10,10); +%! [Y, newmap] = cmunique (I); +%! assert (I, newmap(:,1)(Y+1)); +%! assert (I, newmap(:,2)(Y+1)); +%! assert (I, newmap(:,3)(Y+1)); + +## Random uint8 I image +%!test +%! I = uint8 (rand (10,10)*256); +%! Id = double (I) / 255; +%! [Y, newmap] = cmunique (I); +%! assert (Id, newmap(:,1)(Y+1)); +%! assert (Id, newmap(:,2)(Y+1)); +%! assert (Id, newmap(:,3)(Y+1)); + +## Random uint16 I image +%!test +%! I = uint16 (rand (10,10)*65535); +%! Id = double (I) / 65535; +%! [Y,newmap] = cmunique (I); +%! assert (Id,newmap (:,1)(Y+1)); +%! assert (Id,newmap (:,2)(Y+1)); +%! assert (Id,newmap (:,3)(Y+1)); + +## Test input validation +%!error cmpermute () +%!error cmpermute (1,2,3) +%!error <X is of invalid data type> cmunique (single (magic (16))) +%!error <MAP must be a valid colormap> cmunique (1, "a") +%!error <MAP must be a valid colormap> cmunique (1, i) +%!error <MAP must be a valid colormap> cmunique (1, ones (3,3,3)) +%!error <MAP must be a valid colormap> cmunique (1, ones (3,2)) +%!error <MAP must be a valid colormap> cmunique (1, [-1 1 1]) +%!error <MAP must be a valid colormap> cmunique (1, [2 1 1]) +
--- a/scripts/image/imshow.m Thu Jul 19 21:28:00 2012 +0200 +++ b/scripts/image/imshow.m Sun Jul 22 04:16:02 2012 +0200 @@ -25,7 +25,7 @@ ## @deftypefnx {Function File} {} imshow (@dots{}, @var{string_param1}, @var{value1}, @dots{}) ## @deftypefnx {Function File} {@var{h} =} imshow (@dots{}) ## Display the image @var{im}, where @var{im} can be a 2-dimensional -## (gray-scale image) or a 3-dimensional (RGB image) matrix. +## (grayscale image) or a 3-dimensional (RGB image) matrix. ## ## If @var{limits} is a 2-element vector @code{[@var{low}, @var{high}]}, ## the image is shown using a display range between @var{low} and
--- a/scripts/image/module.mk Thu Jul 19 21:28:00 2012 +0200 +++ b/scripts/image/module.mk Sun Jul 22 04:16:02 2012 +0200 @@ -4,6 +4,8 @@ image/autumn.m \ image/bone.m \ image/brighten.m \ + image/cmpermute.m \ + image/cmunique.m \ image/colorcube.m \ image/colormap.m \ image/contrast.m \
--- a/scripts/optimization/fminbnd.m Thu Jul 19 21:28:00 2012 +0200 +++ b/scripts/optimization/fminbnd.m Sun Jul 22 04:16:02 2012 +0200 @@ -20,14 +20,13 @@ ## -*- texinfo -*- ## @deftypefn {Function File} {[@var{x}, @var{fval}, @var{info}, @var{output}] =} fminbnd (@var{fun}, @var{a}, @var{b}, @var{options}) -## Find a minimum point of a univariate function. @var{fun} should be a -## function -## handle or name. @var{a}, @var{b} specify a starting interval. @var{options} -## is a -## structure specifying additional options. Currently, @code{fminbnd} -## recognizes these options: @code{"FunValCheck"}, @code{"OutputFcn"}, -## @code{"TolX"}, @code{"MaxIter"}, @code{"MaxFunEvals"}. -## For description of these options, see @ref{doc-optimset,,optimset}. +## Find a minimum point of a univariate function. +## +## @var{fun} should be a function handle or name. @var{a}, @var{b} specify a +## starting interval. @var{options} is a structure specifying additional +## options. Currently, @code{fminbnd} recognizes these options: +## "FunValCheck", "OutputFcn", "TolX", "MaxIter", "MaxFunEvals". For a +## description of these options, see @ref{doc-optimset,,optimset}. ## ## On exit, the function returns @var{x}, the approximate minimum point ## and @var{fval}, the function value thereof. @@ -43,7 +42,13 @@ ## @item -1 ## The algorithm has been terminated from user output function. ## @end itemize -## @seealso{optimset, fzero, fminunc} +## +## Notes: The search for a minimum is restricted to be in the interval +## bound by @var{a} and @var{b}. If you only have an initial point +## to begin searching from you will need to use an unconstrained +## minimization algorithm such as @code{fminunc} or @code{fminsearch}. +## @code{fminbnd} internally uses a Golden Section search strategy. +## @seealso{fzero, fminunc, fminsearch, optimset} ## @end deftypefn ## This is patterned after opt/fmin.f from Netlib, which in turn is taken from
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/scripts/optimization/fminsearch.m Sun Jul 22 04:16:02 2012 +0200 @@ -0,0 +1,352 @@ +## Copyright (C) 2003,2012 Andy Adler +## Copyright (C) 2002 N.J.Higham +## +## 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/>. + +## -*- texinfo -*- +## @deftypefn {Function File} {@var{x} =} fminsearch (@var{fun}, @var{x0}) +## @deftypefnx {Function File} {@var{x} =} fminsearch (@var{fun}, @var{x0}, @var{options}) +## @deftypefnx {Function File} {[@var{x}, @var{fval}] =} fminsearch (@dots{}) +## +## Find a value of @var{x} which minimizes the function @var{fun}. +## The search begins at the point @var{x0} and iterates using the +## Nelder & Mead Simplex algorithm (a derivative-free method). This algorithm +## is better-suited to functions which have discontinuities or for which +## a gradient-based search such as @code{fminunc} fails. +## +## Options for the search are provided in the parameter @var{options} using +## the function @code{optimset}. Currently, @code{fminsearch} accepts the +## options: "TolX", "MaxFunEvals", "MaxIter", "Display". For a description of +## these options, see @code{optimset}. +## +## On exit, the function returns @var{x}, the minimum point, +## and @var{fval}, the function value thereof. +## +## Example usages: +## +## @example +## @group +## fminsearch (@@(x) (x(1)-5).^2+(x(2)-8).^4, [0;0]) +## +## fminsearch (inline ("(x(1)-5).^2+(x(2)-8).^4", "x"), [0;0]) +## @end group +## @end example +## @seealso{fminbnd, fminunc, optimset} +## @end deftypefn + +## PKG_ADD: ## Discard result to avoid polluting workspace with ans at startup. +## PKG_ADD: [~] = __all_opts__ ("fminsearch"); + +## FIXME: Add support for "exitflag" output variable +## FIXME: Add support for "output" output variable +## FIXME: For Display option, add 'final' and 'notify' options. Not too hard. +## FIXME: Add support for OutputFcn. See fminunc for a template +## FIXME: Add support for exiting based on TolFun. See fminunc for an idea. + +function [x, fval] = fminsearch (fun, x0, options = struct ()) + + ## Get default options if requested. + if (nargin == 1 && ischar (fun) && strcmp (fun, "defaults")) + x = optimset ("Display", "notify", "FunValCheck", "off", + "MaxFunEvals", 400, "MaxIter", 400, + "OutputFcn", [], + "TolFun", 1e-7, "TolX", 1e-4); + return; + endif + + if (nargin < 2 || nargin > 3) + print_usage (); + endif + + x = nmsmax (fun, x0, options); + + if (isargout (2)) + fval = feval (fun, x); + endif + +endfunction + +##NMSMAX Nelder-Mead simplex method for direct search optimization. +## [x, fmax, nf] = NMSMAX(FUN, x0, STOPIT, SAVIT) attempts to +## maximize the function FUN, using the starting vector x0. +## The Nelder-Mead direct search method is used. +## Output arguments: +## x = vector yielding largest function value found, +## fmax = function value at x, +## nf = number of function evaluations. +## The iteration is terminated when either +## - the relative size of the simplex is <= STOPIT(1) +## (default 1e-3), +## - STOPIT(2) function evaluations have been performed +## (default inf, i.e., no limit), or +## - a function value equals or exceeds STOPIT(3) +## (default inf, i.e., no test on function values). +## The form of the initial simplex is determined by STOPIT(4): +## STOPIT(4) = 0: regular simplex (sides of equal length, the default) +## STOPIT(4) = 1: right-angled simplex. +## Progress of the iteration is not shown if STOPIT(5) = 0 (default 1). +## STOPIT(6) indicates the direction (ie. minimization or +## maximization.) Default is 1, maximization. +## set STOPIT(6)=-1 for minimization +## If a non-empty fourth parameter string SAVIT is present, then +## `SAVE SAVIT x fmax nf' is executed after each inner iteration. +## NB: x0 can be a matrix. In the output argument, in SAVIT saves, +## and in function calls, x has the same shape as x0. +## NMSMAX(fun, x0, STOPIT, SAVIT, P1, P2,...) allows additional +## arguments to be passed to fun, via feval(fun,x,P1,P2,...). +## References: +## N. J. Higham, Optimization by direct search in matrix computations, +## SIAM J. Matrix Anal. Appl, 14(2): 317-333, 1993. +## C. T. Kelley, Iterative Methods for Optimization, Society for Industrial +## and Applied Mathematics, Philadelphia, PA, 1999. + +## From Matrix Toolbox +## Copyright (C) 2002 N.J.Higham +## www.maths.man.ac.uk/~higham/mctoolbox +## +## Modifications for Octave by A.Adler 2003 + +function [stopit, savit, dirn, trace, tol, maxiter] = parse_options (options, x ); + + ## Tolerance for cgce test based on relative size of simplex. + stopit(1) = tol = optimget (options, "TolX", 1e-4); + + ## Max no. of f-evaluations. + stopit(2) = optimget (options, "MaxFunEvals", length (x) * 200); + + ## Max no. of iterations + maxiter = optimget (options, "MaxIter", length (x) * 200); + + ## Default target for f-values. + stopit(3) = Inf; # FIXME: expose this parameter to the outside + + ## Default initial simplex. + stopit(4) = 0; # FIXME: expose this parameter to the outside + + ## Default: show progress. + display = optimget (options, "Display", "notify"); + if (strcmp (display, "iter")) + stopit(5) = 1; + else + stopit(5) = 0; + endif + trace = stopit(5); + + ## Use function to minimize, not maximize + stopit(6) = dirn = -1; + + ## File name for snapshots. + savit = []; # FIXME: expose this parameter to the outside + +endfunction + +function [x, fmax, nf] = nmsmax (fun, x, options, savit, varargin) + + [stopit, savit, dirn, trace, tol, maxiter] = parse_options (options, x); + + if (strcmpi (optimget (options, "FunValCheck", "off"), "on")) + ## Replace fcn with a guarded version. + fun = @(x) guarded_eval (fun, x); + endif + + x0 = x(:); # Work with column vector internally. + n = length (x0); + + V = [zeros(n,1) eye(n)]; + f = zeros (n+1,1); + V(:,1) = x0; + f(1) = dirn * feval (fun,x,varargin{:}); + fmax_old = f(1); + + if (trace) + fprintf ("f(x0) = %9.4e\n", f(1)); + endif + + k = 0; m = 0; + + ## Set up initial simplex. + scale = max (norm (x0,Inf), 1); + if (stopit(4) == 0) + ## Regular simplex - all edges have same length. + ## Generated from construction given in reference [18, pp. 80-81] of [1]. + alpha = scale / (n*sqrt (2)) * [sqrt(n+1)-1+n, sqrt(n+1)-1]; + V(:,2:n+1) = (x0 + alpha(2)*ones (n,1)) * ones (1,n); + for j = 2:n+1 + V(j-1,j) = x0(j-1) + alpha(1); + x(:) = V(:,j); + f(j) = dirn * feval (fun,x,varargin{:}); + endfor + else + ## Right-angled simplex based on co-ordinate axes. + alpha = scale * ones(n+1,1); + for j=2:n+1 + V(:,j) = x0 + alpha(j)*V(:,j); + x(:) = V(:,j); + f(j) = dirn * feval (fun,x,varargin{:}); + endfor + endif + nf = n+1; + how = "initial "; + + [~,j] = sort (f); + j = j(n+1:-1:1); + f = f(j); + V = V(:,j); + + alpha = 1; beta = 1/2; gamma = 2; + + while (1) # Outer (and only) loop. + k++; + + if (k > maxiter) + msg = "Exceeded maximum iterations...quitting\n"; + break; + endif + + fmax = f(1); + if (fmax > fmax_old) + if (! isempty (savit)) + x(:) = V(:,1); + eval (["save " savit " x fmax nf"]); + endif + endif + if (trace) + fprintf ("Iter. %2.0f,", k); + fprintf ([" how = " how " "]); + fprintf ("nf = %3.0f, f = %9.4e (%2.1f%%)\n", nf, fmax, ... + 100*(fmax-fmax_old)/(abs(fmax_old)+eps)); + endif + fmax_old = fmax; + + ## Three stopping tests from MDSMAX.M + + ## Stopping Test 1 - f reached target value? + if (fmax >= stopit(3)) + msg = "Exceeded target...quitting\n"; + break; + endif + + ## Stopping Test 2 - too many f-evals? + if (nf >= stopit(2)) + msg = "Max no. of function evaluations exceeded...quitting\n"; + break; + endif + + ## Stopping Test 3 - converged? This is test (4.3) in [1]. + v1 = V(:,1); + size_simplex = norm (V(:,2:n+1)-v1(:,ones (1,n)),1) / max (1, norm (v1,1)); + if (size_simplex <= tol) + msg = sprintf ("Simplex size %9.4e <= %9.4e...quitting\n", ... + size_simplex, tol); + break; + endif + + ## One step of the Nelder-Mead simplex algorithm + ## NJH: Altered function calls and changed CNT to NF. + ## Changed each `fr < f(1)' type test to `>' for maximization + ## and re-ordered function values after sort. + + vbar = (sum (V(:,1:n)')/n)'; # Mean value + vr = (1 + alpha)*vbar - alpha*V(:,n+1); + x(:) = vr; + fr = dirn * feval (fun,x,varargin{:}); + nf = nf + 1; + vk = vr; fk = fr; how = "reflect, "; + if (fr > f(n)) + if (fr > f(1)) + ve = gamma*vr + (1-gamma)*vbar; + x(:) = ve; + fe = dirn * feval (fun,x,varargin{:}); + nf = nf + 1; + if (fe > f(1)) + vk = ve; + fk = fe; + how = "expand, "; + endif + endif + else + vt = V(:,n+1); + ft = f(n+1); + if (fr > ft) + vt = vr; + ft = fr; + endif + vc = beta*vt + (1-beta)*vbar; + x(:) = vc; + fc = dirn * feval (fun,x,varargin{:}); + nf = nf + 1; + if (fc > f(n)) + vk = vc; fk = fc; + how = "contract,"; + else + for j = 2:n + V(:,j) = (V(:,1) + V(:,j))/2; + x(:) = V(:,j); + f(j) = dirn * feval (fun,x,varargin{:}); + endfor + nf = nf + n-1; + vk = (V(:,1) + V(:,n+1))/2; + x(:) = vk; + fk = dirn * feval (fun,x,varargin{:}); + nf = nf + 1; + how = "shrink, "; + endif + endif + V(:,n+1) = vk; + f(n+1) = fk; + [~,j] = sort(f); + j = j(n+1:-1:1); + f = f(j); + V = V(:,j); + + endwhile # End of outer (and only) loop. + + ## Finished. + if (trace) + fprintf (msg); + endif + x(:) = V(:,1); + +endfunction + +## A helper function that evaluates a function and checks for bad results. +function y = guarded_eval (fun, x) + + y = fun (x); + + if (! (isreal (f))) + error ("fminsearch:notreal", "fminsearch: non-real value encountered"); + elseif (any (isnan (f(:)))) + error ("fminsearch:isnan", "fminsearch: NaN value encountered"); + elseif (any (isinf (f(:)))) + error ("fminsearch:isinf", "fminsearch: Inf value encountered"); + endif + +endfunction + + +%!demo +%! fcn = @(x) (x(1)-5).^2 + (x(2)-8).^4 +%! x0 = [0;0]; +%! [xmin, fval] = fminsearch (fcn, x0) + +%!assert (fminsearch (@sin, 3, optimset ("MaxIter", 3)), 4.8750, 1e-4) +%!assert (fminsearch (@sin, 3, optimset ("MaxIter", 30)), 4.7124, 1e-4) +%!shared c +%! c = 1.5; +%!assert (fminsearch (@(x) x(1).^2+c*x(2).^2,[1;1]), [0;0], 1e-4) +
--- a/scripts/optimization/fminunc.m Thu Jul 19 21:28:00 2012 +0200 +++ b/scripts/optimization/fminunc.m Sun Jul 22 04:16:02 2012 +0200 @@ -24,6 +24,7 @@ ## @deftypefnx {Function File} {[@var{x}, @var{fvec}, @var{info}, @var{output}, @var{grad}, @var{hess}] =} fminunc (@var{fcn}, @dots{}) ## Solve an unconstrained optimization problem defined by the function ## @var{fcn}. +## ## @var{fcn} should accepts a vector (array) defining the unknown variables, ## and return the objective function value, optionally with gradient. ## In other words, this function attempts to determine a vector @var{x} such @@ -72,9 +73,12 @@ ## (@var{output}), the output gradient (@var{grad}) and approximate Hessian ## (@var{hess}). ## -## Note: If you only have a single nonlinear equation of one variable, using -## @code{fminbnd} is usually a much better idea. -## @seealso{fminbnd, optimset} +## Notes: If you only have a single nonlinear equation of one variable then +## using @code{fminbnd} is usually a much better idea. The algorithm used is a +## gradient search which depends on the objective function being differentiable. +## If the function has discontinuities it may be better to use a derivative-free +## algorithm such as @code{fminsearch}. +## @seealso{fminbnd, fminsearch, optimset} ## @end deftypefn ## PKG_ADD: ## Discard result to avoid polluting workspace with ans at startup.
--- a/scripts/optimization/module.mk Thu Jul 19 21:28:00 2012 +0200 +++ b/scripts/optimization/module.mk Sun Jul 22 04:16:02 2012 +0200 @@ -6,6 +6,7 @@ optimization_FCN_FILES = \ optimization/__all_opts__.m \ optimization/fminbnd.m \ + optimization/fminsearch.m \ optimization/fminunc.m \ optimization/fsolve.m \ optimization/fzero.m \
--- a/scripts/optimization/optimset.m Thu Jul 19 21:28:00 2012 +0200 +++ b/scripts/optimization/optimset.m Sun Jul 22 04:16:02 2012 +0200 @@ -26,16 +26,34 @@ ## ## Valid parameters are: ## -## @itemize @bullet +## @table @asis ## @item AutoScaling ## ## @item ComplexEqn ## +## @item Display +## Request verbose display of results from optimizations. Values are: +## +## @table @asis +## @item "off" [default] +## No display. +## +## @item "iter" +## Display intermediate results for every loop iteration. +## +## @item "final" +## Display the result of the final loop iteration. +## +## @item "notify" +## Display the result of the final loop iteration if the function has +## failed to converge. +## @end table +## ## @item FinDiffType ## ## @item FunValCheck ## When enabled, display an error if the objective function returns an invalid -## value (a complex value, NaN, or Inf). Must be set to "on" or "off" +## value (a complex number, NaN, or Inf). Must be set to "on" or "off" ## [default]. Note: the functions @code{fzero} and @code{fminbnd} correctly ## handle Inf values and only complex values or NaN will cause an error in this ## case. @@ -77,7 +95,7 @@ ## @item TypicalX ## ## @item Updating -## @end itemize +## @end table ## @end deftypefn function retval = optimset (varargin)
--- a/src/DLD-FUNCTIONS/eig.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/DLD-FUNCTIONS/eig.cc Sun Jul 22 04:16:02 2012 +0200 @@ -39,12 +39,12 @@ @deftypefnx {Loadable Function} {@var{lambda} =} eig (@var{A}, @var{B})\n\ @deftypefnx {Loadable Function} {[@var{V}, @var{lambda}] =} eig (@var{A})\n\ @deftypefnx {Loadable Function} {[@var{V}, @var{lambda}] =} eig (@var{A}, @var{B})\n\ -Compute the eigenvalues and eigenvectors of a matrix.\n\ +Compute the eigenvalues (and optionally the eigenvectors) of a matrix\n\ +or a pair of matrices\n\ \n\ -Eigenvalues are computed in a several step process which begins with a\n\ -Hessenberg decomposition, followed by a Schur@tie{}decomposition, from which\n\ -the eigenvalues are apparent. The eigenvectors, when desired, are computed\n\ -by further manipulations of the Schur@tie{}decomposition.\n\ +The algorithm used depends on whether there are one or two input\n\ +matrices, if they are real or complex and if they are symmetric\n\ +(Hermitian if complex) or nonsymmetric.\n\ \n\ The eigenvalues returned by @code{eig} are not ordered.\n\ @seealso{eigs, svd}\n\
--- a/src/Makefile.am Thu Jul 19 21:28:00 2012 +0200 +++ b/src/Makefile.am Sun Jul 22 04:16:02 2012 +0200 @@ -220,6 +220,7 @@ pt-fcn-handle.h \ pt-id.h \ pt-idx.h \ + pt-jit.h \ pt-jump.h \ pt-loop.h \ pt-mat.h \ @@ -392,6 +393,7 @@ pt-fcn-handle.cc \ pt-id.cc \ pt-idx.cc \ + pt-jit.cc \ pt-jump.cc \ pt-loop.cc \ pt-mat.cc \
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/TEMPLATE-INST/Array-jit.cc Sun Jul 22 04:16:02 2012 +0200 @@ -0,0 +1,40 @@ +/* + +Copyright (C) 2012 Max Brister <max@2bass.com> + +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/>. + +*/ + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +#ifdef HAVE_LLVM + +#include "Array.h" +#include "Array.cc" + +extern template class OCTAVE_API Array<octave_idx_type>; + +#include "pt-jit.h" + +NO_INSTANTIATE_ARRAY_SORT (jit_operation::overload); + +INSTANTIATE_ARRAY (jit_operation::overload, OCTINTERP_API); + +#endif
--- a/src/TEMPLATE-INST/module.mk Thu Jul 19 21:28:00 2012 +0200 +++ b/src/TEMPLATE-INST/module.mk Sun Jul 22 04:16:02 2012 +0200 @@ -2,4 +2,5 @@ TEMPLATE_INST_SRC = \ TEMPLATE-INST/Array-os.cc \ - TEMPLATE-INST/Array-tc.cc + TEMPLATE-INST/Array-tc.cc \ + TEMPLATE-INST/Array-jit.cc
--- a/src/input.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/input.cc Sun Jul 22 04:16:02 2012 +0200 @@ -1379,7 +1379,7 @@ This can be useful for coloring the prompt. For example,\n\ \n\ @example\n\ -PS1 (\"\\\\[\\\\033[01;31m\\\\]\\\\s:\\\\#> \\\\[\\\\033[0m\\]\")\n\ +PS1 (\"\\\\[\\\\033[01;31m\\\\]\\\\s:\\\\#> \\\\[\\\\033[0m\\\\]\")\n\ @end example\n\ \n\ @noindent\n\
--- a/src/link-deps.mk Thu Jul 19 21:28:00 2012 +0200 +++ b/src/link-deps.mk Sun Jul 22 04:16:02 2012 +0200 @@ -13,14 +13,16 @@ $(Z_LIBS) \ $(OPENGL_LIBS) \ $(X11_LIBS) \ - $(CARBON_LIBS) + $(CARBON_LIBS) \ + $(LLVM_LIBS) LIBOCTINTERP_LINK_OPTS = \ $(GRAPHICS_LDFLAGS) \ $(FT2_LDFLAGS) \ $(HDF5_LDFLAGS) \ $(Z_LDFLAGS) \ - $(REGEX_LDFLAGS) + $(REGEX_LDFLAGS) \ + $(LLVM_LDFLAGS) OCT_LINK_DEPS =
--- a/src/load-path.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/load-path.cc Sun Jul 22 04:16:02 2012 +0200 @@ -1798,7 +1798,11 @@ // way we look for old.dir_name in sys_path to avoid // partial matches? - if (sys_path.find (old.dir_name) != std::string::npos + // Don't warn about Contents.m files since we expect + // more than one to exist in the load path. + + if (fname != "Contents.m" + && sys_path.find (old.dir_name) != std::string::npos && in_path_list (sys_path, old.dir_name)) { std::string fcn_path = file_ops::concat (dir_name, fname);
--- a/src/load-save.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/load-save.cc Sun Jul 22 04:16:02 2012 +0200 @@ -91,7 +91,7 @@ #include "zfstream.h" #endif -// Write octave-core file if Octave crashes or is killed by a signal. +// Write octave-workspace file if Octave crashes or is killed by a signal. static bool Vcrash_dumps_octave_core = true; // The maximum amount of memory (in kilobytes) that we will attempt to @@ -99,7 +99,7 @@ static double Voctave_core_file_limit = -1.0; // The name of the Octave core file. -static std::string Voctave_core_file_name = "octave-core"; +static std::string Voctave_core_file_name = "octave-workspace"; // The default output format. May be one of "binary", "text", // "mat-binary", or "hdf5". @@ -1751,7 +1751,7 @@ @deftypefnx {Built-in Function} {@var{old_val} =} crash_dumps_octave_core (@var{new_val})\n\ @deftypefnx {Built-in Function} {} crash_dumps_octave_core (@var{new_val}, \"local\")\n\ Query or set the internal variable that controls whether Octave tries\n\ -to save all current variables to the file \"octave-core\" if it\n\ +to save all current variables to the file \"octave-workspace\" if it\n\ crashes or receives a hangup, terminate or similar signal.\n\ \n\ When called from inside a function with the \"local\" option, the variable is\n\ @@ -1812,7 +1812,7 @@ @deftypefnx {Built-in Function} {} octave_core_file_name (@var{new_val}, \"local\")\n\ Query or set the internal variable that specifies the name of the file\n\ used for saving data from the top-level workspace if Octave aborts.\n\ -The default value is @code{\"octave-core\"}\n\ +The default value is @code{\"octave-workspace\"}\n\ \n\ When called from inside a function with the \"local\" option, the variable is\n\ changed locally for the function and any subroutines it calls. The original\n\
--- a/src/oct-conf.in.h Thu Jul 19 21:28:00 2012 +0200 +++ b/src/oct-conf.in.h Sun Jul 22 04:16:02 2012 +0200 @@ -384,6 +384,18 @@ #define OCTAVE_CONF_MAGICK_LIBS %OCTAVE_CONF_MAGICK_LIBS% #endif +#ifndef OCTAVE_CONF_LLVM_CPPFLAGS +#define OCTAVE_CONF_LLVM_CPPFLAGS %OCTAVE_CONF_LLVM_CPPFLAGS% +#endif + +#ifndef OCTAVE_CONF_LLVM_LDFLAGS +#define OCTAVE_CONF_LLVM_LDFLAGS %OCTAVE_CONF_LLVM_LDFLAGS% +#endif + +#ifndef OCTAVE_CONF_LLVM_LIBS +#define OCTAVE_CONF_LLVM_LIBS %OCTAVE_CONF_LLVM_LIBS% +#endif + #ifndef OCTAVE_CONF_MKOCTFILE_DL_LDFLAGS #define OCTAVE_CONF_MKOCTFILE_DL_LDFLAGS %OCTAVE_CONF_MKOCTFILE_DL_LDFLAGS% #endif
--- a/src/ov-base.h Thu Jul 19 21:28:00 2012 +0200 +++ b/src/ov-base.h Sun Jul 22 04:16:02 2012 +0200 @@ -756,6 +756,21 @@ virtual bool fast_elem_insert_self (void *where, builtin_type_t btyp) const; + // Grab the reference count. For use by jit. + void + grab (void) + { + ++count; + } + + // Release the reference count. For use by jit. + void + release (void) + { + if (--count == 0) + delete this; + } + protected: // This should only be called for derived types.
--- a/src/ov-builtin.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/ov-builtin.cc Sun Jul 22 04:16:02 2012 +0200 @@ -152,5 +152,22 @@ return retval; } +jit_type * +octave_builtin::to_jit (void) const +{ + return jtype; +} + +void +octave_builtin::stash_jit (jit_type &type) +{ + jtype = &type; +} + +octave_builtin::fcn +octave_builtin::function (void) const +{ + return f; +} const std::list<octave_lvalue> *octave_builtin::curr_lvalue_list = 0;
--- a/src/ov-builtin.h Thu Jul 19 21:28:00 2012 +0200 +++ b/src/ov-builtin.h Sun Jul 22 04:16:02 2012 +0200 @@ -30,6 +30,7 @@ class octave_value; class octave_value_list; +class jit_type; // Builtin functions. @@ -39,13 +40,13 @@ { public: - octave_builtin (void) : octave_function (), f (0) { } + octave_builtin (void) : octave_function (), f (0), jtype (0) { } typedef octave_value_list (*fcn) (const octave_value_list&, int); octave_builtin (fcn ff, const std::string& nm = std::string (), const std::string& ds = std::string ()) - : octave_function (nm, ds), f (ff) { } + : octave_function (nm, ds), f (ff), jtype (0) { } ~octave_builtin (void) { } @@ -75,6 +76,12 @@ do_multi_index_op (int nargout, const octave_value_list& args, const std::list<octave_lvalue>* lvalue_list); + jit_type *to_jit (void) const; + + void stash_jit (jit_type& type); + + fcn function (void) const; + static const std::list<octave_lvalue> *curr_lvalue_list; protected: @@ -82,6 +89,9 @@ // A pointer to the actual function. fcn f; + // A pointer to the jit type that represents the function. + jit_type *jtype; + private: // No copying!
--- a/src/pt-eval.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/pt-eval.cc Sun Jul 22 04:16:02 2012 +0200 @@ -44,6 +44,12 @@ #include "symtab.h" #include "unwind-prot.h" +#if HAVE_LLVM +//FIXME: This should be part of tree_evaluator +#include "pt-jit.h" +static tree_jit jiter; +#endif + static tree_evaluator std_evaluator; tree_evaluator *current_evaluator = &std_evaluator; @@ -290,6 +296,11 @@ if (debug_mode) do_breakpoint (cmd.is_breakpoint ()); +#if HAVE_LLVM + if (jiter.execute (cmd)) + return; +#endif + // FIXME -- need to handle PARFOR loops here using cmd.in_parallel () // and cmd.maxproc_expr ();
--- a/src/pt-id.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/pt-id.cc Sun Jul 22 04:16:02 2012 +0200 @@ -65,7 +65,7 @@ if (error_state) return retval; - octave_value val = xsym ().find (); + octave_value val = sym->find (); if (val.is_defined ()) { @@ -116,7 +116,7 @@ octave_lvalue tree_identifier::lvalue (void) { - return octave_lvalue (&(xsym ().varref ())); + return octave_lvalue (&(sym->varref ())); } tree_identifier *
--- a/src/pt-id.h Thu Jul 19 21:28:00 2012 +0200 +++ b/src/pt-id.h Sun Jul 22 04:16:02 2012 +0200 @@ -46,12 +46,12 @@ public: tree_identifier (int l = -1, int c = -1) - : tree_expression (l, c), sym (), scope (-1) { } + : tree_expression (l, c) { } tree_identifier (const symbol_table::symbol_record& s, int l = -1, int c = -1, symbol_table::scope_id sc = symbol_table::current_scope ()) - : tree_expression (l, c), sym (s), scope (sc) { } + : tree_expression (l, c), sym (s, sc) { } ~tree_identifier (void) { } @@ -63,9 +63,9 @@ // accessing it through sym so that this function may remain const. std::string name (void) const { return sym.name (); } - bool is_defined (void) { return xsym ().is_defined (); } + bool is_defined (void) { return sym->is_defined (); } - virtual bool is_variable (void) { return xsym ().is_variable (); } + virtual bool is_variable (void) { return sym->is_variable (); } virtual bool is_black_hole (void) { return false; } @@ -87,14 +87,14 @@ octave_value do_lookup (const octave_value_list& args = octave_value_list ()) { - return xsym ().find (args); + return sym->find (args); } - void mark_global (void) { xsym ().mark_global (); } + void mark_global (void) { sym->mark_global (); } - void mark_as_static (void) { xsym ().init_persistent (); } + void mark_as_static (void) { sym->init_persistent (); } - void mark_as_formal_parameter (void) { xsym ().mark_formal (); } + void mark_as_formal_parameter (void) { sym->mark_formal (); } // We really need to know whether this symbol referst to a variable // or a function, but we may not know that yet. @@ -114,28 +114,14 @@ void accept (tree_walker& tw); + symbol_table::symbol_reference symbol (void) const + { + return sym; + } private: // The symbol record that this identifier references. - symbol_table::symbol_record sym; - - symbol_table::scope_id scope; - - // A script may be executed in multiple scopes. If the last one was - // different from the one we are in now, update sym to be from the - // new scope. - symbol_table::symbol_record& xsym (void) - { - symbol_table::scope_id curr_scope = symbol_table::current_scope (); - - if (scope != curr_scope || ! sym.is_valid ()) - { - scope = curr_scope; - sym = symbol_table::insert (sym.name ()); - } - - return sym; - } + symbol_table::symbol_reference sym; // No copying!
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/pt-jit.cc Sun Jul 22 04:16:02 2012 +0200 @@ -0,0 +1,3888 @@ +/* + +Copyright (C) 2012 Max Brister <max@2bass.com> + +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/>. + +*/ + +#define __STDC_LIMIT_MACROS +#define __STDC_CONSTANT_MACROS + +#ifdef HAVE_CONFIG_H +#include <config.h> +#endif + +#ifdef HAVE_LLVM + +#include "pt-jit.h" + +#include <typeinfo> + +#include <llvm/LLVMContext.h> +#include <llvm/Module.h> +#include <llvm/Function.h> +#include <llvm/BasicBlock.h> +#include <llvm/Intrinsics.h> +#include <llvm/Support/IRBuilder.h> +#include <llvm/ExecutionEngine/ExecutionEngine.h> +#include <llvm/ExecutionEngine/JIT.h> +#include <llvm/PassManager.h> +#include <llvm/Analysis/Verifier.h> +#include <llvm/Analysis/CallGraph.h> +#include <llvm/Analysis/Passes.h> +#include <llvm/Target/TargetData.h> +#include <llvm/Transforms/Scalar.h> +#include <llvm/Transforms/IPO.h> +#include <llvm/Support/TargetSelect.h> +#include <llvm/Support/raw_os_ostream.h> +#include <llvm/Support/FormattedStream.h> +#include <llvm/Bitcode/ReaderWriter.h> + +#include "octave.h" +#include "ov-fcn-handle.h" +#include "ov-usr-fcn.h" +#include "ov-builtin.h" +#include "ov-scalar.h" +#include "ov-complex.h" +#include "pt-all.h" +#include "symtab.h" + +static llvm::IRBuilder<> builder (llvm::getGlobalContext ()); + +static llvm::LLVMContext& context = llvm::getGlobalContext (); + +jit_typeinfo *jit_typeinfo::instance; + +// thrown when we should give up on JIT and interpret +class jit_fail_exception : public std::runtime_error +{ +public: + jit_fail_exception (void) : std::runtime_error ("unknown"), mknown (false) {} + jit_fail_exception (const std::string& reason) : std::runtime_error (reason), + mknown (true) + {} + + bool known (void) const { return mknown; } +private: + bool mknown; +}; + +static void fail (void) GCC_ATTR_NORETURN; +static void fail (const std::string&) GCC_ATTR_NORETURN; + +static void +fail (void) +{ + throw jit_fail_exception (); +} + +#ifdef OCTAVE_JIT_DEBUG +static void +fail (const std::string& reason) +{ + throw jit_fail_exception (reason); +} +#else +static void +fail (const std::string&) +{ + throw jit_fail_exception (); +} +#endif // OCTAVE_JIT_DEBUG + +std::ostream& jit_print (std::ostream& os, jit_type *atype) +{ + if (! atype) + return os << "null"; + return os << atype->name (); +} + +// function that jit code calls +extern "C" void +octave_jit_print_any (const char *name, octave_base_value *obv) +{ + obv->print_with_name (octave_stdout, name, true); +} + +extern "C" void +octave_jit_print_double (const char *name, double value) +{ + // FIXME: We should avoid allocating a new octave_scalar each time + octave_value ov (value); + ov.print_with_name (octave_stdout, name); +} + +extern "C" octave_base_value* +octave_jit_binary_any_any (octave_value::binary_op op, octave_base_value *lhs, + octave_base_value *rhs) +{ + octave_value olhs (lhs, true); + octave_value orhs (rhs, true); + octave_value result = do_binary_op (op, olhs, orhs); + octave_base_value *rep = result.internal_rep (); + rep->grab (); + return rep; +} + +extern "C" octave_idx_type +octave_jit_compute_nelem (double base, double limit, double inc) +{ + Range rng = Range (base, limit, inc); + return rng.nelem (); +} + +extern "C" void +octave_jit_release_any (octave_base_value *obv) +{ + obv->release (); +} + +extern "C" void +octave_jit_release_matrix (jit_matrix *m) +{ + delete m->array; +} + +extern "C" octave_base_value * +octave_jit_grab_any (octave_base_value *obv) +{ + obv->grab (); + return obv; +} + +extern "C" void +octave_jit_grab_matrix (jit_matrix *result, jit_matrix *m) +{ + *result = *m->array; +} + +extern "C" octave_base_value * +octave_jit_cast_any_matrix (jit_matrix *m) +{ + octave_value ret (*m->array); + octave_base_value *rep = ret.internal_rep (); + rep->grab (); + delete m->array; + + return rep; +} + +extern "C" void +octave_jit_cast_matrix_any (jit_matrix *ret, octave_base_value *obv) +{ + NDArray m = obv->array_value (); + *ret = m; + obv->release (); +} + +extern "C" double +octave_jit_cast_scalar_any (octave_base_value *obv) +{ + double ret = obv->double_value (); + obv->release (); + return ret; +} + +extern "C" octave_base_value * +octave_jit_cast_any_scalar (double value) +{ + return new octave_scalar (value); +} + +extern "C" Complex +octave_jit_cast_complex_any (octave_base_value *obv) +{ + Complex ret = obv->complex_value (); + obv->release (); + return ret; +} + +extern "C" octave_base_value * +octave_jit_cast_any_complex (Complex c) +{ + if (c.imag () == 0) + return new octave_scalar (c.real ()); + else + return new octave_complex (c); +} + +extern "C" void +octave_jit_gripe_nan_to_logical_conversion (void) +{ + try + { + gripe_nan_to_logical_conversion (); + } + catch (const octave_execution_exception&) + { + gripe_library_execution_error (); + } +} + +extern "C" void +octave_jit_ginvalid_index (void) +{ + try + { + gripe_invalid_index (); + } + catch (const octave_execution_exception&) + { + gripe_library_execution_error (); + } +} + +extern "C" void +octave_jit_gindex_range (int nd, int dim, octave_idx_type iext, + octave_idx_type ext) +{ + try + { + gripe_index_out_of_range (nd, dim, iext, ext); + } + catch (const octave_execution_exception&) + { + gripe_library_execution_error (); + } +} + +extern "C" void +octave_jit_paren_subsasgn_impl (jit_matrix *mat, octave_idx_type index, + double value) +{ + NDArray *array = mat->array; + if (array->nelem () < index) + array->resize1 (index); + + double *data = array->fortran_vec (); + data[index - 1] = value; + + mat->update (); +} + +extern "C" void +octave_jit_paren_subsasgn_matrix_range (jit_matrix *result, jit_matrix *mat, + jit_range *index, double value) +{ + NDArray *array = mat->array; + bool done = false; + + // optimize for the simple case (no resizing and no errors) + if (*array->jit_ref_count () == 1 + && index->all_elements_are_ints ()) + { + // this code is similar to idx_vector::fill, but we avoid allocating an + // idx_vector and its associated rep + octave_idx_type start = static_cast<octave_idx_type> (index->base) - 1; + octave_idx_type step = static_cast<octave_idx_type> (index->inc); + octave_idx_type nelem = index->nelem; + octave_idx_type final = start + nelem * step; + if (step < 0) + { + step = -step; + std::swap (final, start); + } + + if (start >= 0 && final < mat->slice_len) + { + done = true; + + double *data = array->jit_slice_data (); + if (step == 1) + std::fill (data + start, data + start + nelem, value); + else + { + for (octave_idx_type i = start; i < final; i += step) + data[i] = value; + } + } + } + + if (! done) + { + idx_vector idx (*index); + NDArray avalue (dim_vector (1, 1)); + avalue.xelem (0) = value; + array->assign (idx, avalue); + } + + result->update (array); +} + +extern "C" Complex +octave_jit_complex_div (Complex lhs, Complex rhs) +{ + // see src/OPERATORS/op-cs-cs.cc + if (rhs == 0.0) + gripe_divide_by_zero (); + + return lhs / rhs; +} + +// FIXME: CP form src/xpow.cc +static inline int +xisint (double x) +{ + return (D_NINT (x) == x + && ((x >= 0 && x < INT_MAX) + || (x <= 0 && x > INT_MIN))); +} + +extern "C" Complex +octave_jit_pow_scalar_scalar (double lhs, double rhs) +{ + // FIXME: almost CP from src/xpow.cc + if (lhs < 0.0 && ! xisint (rhs)) + return std::pow (Complex (lhs), rhs); + return std::pow (lhs, rhs); +} + +extern "C" Complex +octave_jit_pow_complex_complex (Complex lhs, Complex rhs) +{ + if (lhs.imag () == 0 && rhs.imag () == 0) + return octave_jit_pow_scalar_scalar (lhs.real (), rhs.real ()); + return std::pow (lhs, rhs); +} + +extern "C" Complex +octave_jit_pow_complex_scalar (Complex lhs, double rhs) +{ + if (lhs.imag () == 0) + return octave_jit_pow_scalar_scalar (lhs.real (), rhs); + return std::pow (lhs, rhs); +} + +extern "C" Complex +octave_jit_pow_scalar_complex (double lhs, Complex rhs) +{ + if (rhs.imag () == 0) + return octave_jit_pow_scalar_scalar (lhs, rhs.real ()); + return std::pow (lhs, rhs); +} + +extern "C" void +octave_jit_print_matrix (jit_matrix *m) +{ + std::cout << *m << std::endl; +} + +static void +gripe_bad_result (void) +{ + error ("incorrect type information given to the JIT compiler"); +} + +// FIXME: Add support for multiple outputs +extern "C" octave_base_value * +octave_jit_call (octave_builtin::fcn fn, size_t nargin, + octave_base_value **argin, jit_type *result_type) +{ + octave_value_list ovl (nargin); + for (size_t i = 0; i < nargin; ++i) + ovl.xelem (i) = octave_value (argin[i]); + + ovl = fn (ovl, 1); + + // These type checks are not strictly required, but I'm guessing that + // incorrect types will be entered on occasion. This will be very difficult to + // debug unless we do the sanity check here. + if (result_type) + { + if (ovl.length () != 1) + { + gripe_bad_result (); + return 0; + } + + octave_value& result = ovl.xelem (0); + jit_type *jtype = jit_typeinfo::join (jit_typeinfo::type_of (result), + result_type); + if (jtype != result_type) + { + gripe_bad_result (); + return 0; + } + + octave_base_value *ret = result.internal_rep (); + ret->grab (); + return ret; + } + + if (! (ovl.length () == 0 + || (ovl.length () == 1 && ovl.xelem (0).is_undefined ()))) + gripe_bad_result (); + + return 0; +} + +// -------------------- jit_range -------------------- +bool +jit_range::all_elements_are_ints () const +{ + Range r (*this); + return r.all_elements_are_ints (); +} + +std::ostream& +operator<< (std::ostream& os, const jit_range& rng) +{ + return os << "Range[" << rng.base << ", " << rng.limit << ", " << rng.inc + << ", " << rng.nelem << "]"; +} + +// -------------------- jit_matrix -------------------- + +std::ostream& +operator<< (std::ostream& os, const jit_matrix& mat) +{ + return os << "Matrix[" << mat.ref_count << ", " << mat.slice_data << ", " + << mat.slice_len << ", " << mat.dimensions << ", " + << mat.array << "]"; +} + +// -------------------- jit_type -------------------- +llvm::Type * +jit_type::to_llvm_arg (void) const +{ + return llvm_type ? llvm_type->getPointerTo () : 0; +} + +// -------------------- jit_operation -------------------- +void +jit_operation::add_overload (const overload& func, + const std::vector<jit_type*>& args) +{ + if (args.size () >= overloads.size ()) + overloads.resize (args.size () + 1); + + Array<overload>& over = overloads[args.size ()]; + dim_vector dv (over.dims ()); + Array<octave_idx_type> idx = to_idx (args); + bool must_resize = false; + + if (dv.length () != idx.numel ()) + { + dv.resize (idx.numel ()); + must_resize = true; + } + + for (octave_idx_type i = 0; i < dv.length (); ++i) + if (dv(i) <= idx(i)) + { + must_resize = true; + dv(i) = idx(i) + 1; + } + + if (must_resize) + over.resize (dv); + + over(idx) = func; +} + +const jit_operation::overload& +jit_operation::get_overload (const std::vector<jit_type*>& types) const +{ + // FIXME: We should search for the next best overload on failure + static overload null_overload; + if (types.size () >= overloads.size ()) + return null_overload; + + for (size_t i =0; i < types.size (); ++i) + if (! types[i]) + return null_overload; + + const Array<overload>& over = overloads[types.size ()]; + dim_vector dv (over.dims ()); + Array<octave_idx_type> idx = to_idx (types); + for (octave_idx_type i = 0; i < dv.length (); ++i) + if (idx(i) >= dv(i)) + return null_overload; + + return over(idx); +} + +Array<octave_idx_type> +jit_operation::to_idx (const std::vector<jit_type*>& types) const +{ + octave_idx_type numel = types.size (); + if (numel == 1) + numel = 2; + + Array<octave_idx_type> idx (dim_vector (1, numel)); + for (octave_idx_type i = 0; i < static_cast<octave_idx_type> (types.size ()); + ++i) + idx(i) = types[i]->type_id (); + + if (types.size () == 1) + { + idx(1) = idx(0); + idx(0) = 0; + } + + return idx; +} + +// -------------------- jit_typeinfo -------------------- +void +jit_typeinfo::initialize (llvm::Module *m, llvm::ExecutionEngine *e) +{ + instance = new jit_typeinfo (m, e); +} + +jit_typeinfo::jit_typeinfo (llvm::Module *m, llvm::ExecutionEngine *e) + : module (m), engine (e), next_id (0) +{ + // FIXME: We should be registering types like in octave_value_typeinfo + llvm::Type *any_t = llvm::StructType::create (context, "octave_base_value"); + any_t = any_t->getPointerTo (); + + llvm::Type *scalar_t = llvm::Type::getDoubleTy (context); + llvm::Type *bool_t = llvm::Type::getInt1Ty (context); + llvm::Type *string_t = llvm::Type::getInt8Ty (context); + string_t = string_t->getPointerTo (); + llvm::Type *index_t = llvm::Type::getIntNTy (context, + sizeof(octave_idx_type) * 8); + + llvm::StructType *range_t = llvm::StructType::create (context, "range"); + std::vector<llvm::Type *> range_contents (4, scalar_t); + range_contents[3] = index_t; + range_t->setBody (range_contents); + + llvm::Type *refcount_t = llvm::Type::getIntNTy (context, sizeof(int) * 8); + llvm::Type *int_t = refcount_t; + + llvm::StructType *matrix_t = llvm::StructType::create (context, "matrix"); + llvm::Type *matrix_contents[5]; + matrix_contents[0] = refcount_t->getPointerTo (); + matrix_contents[1] = scalar_t->getPointerTo (); + matrix_contents[2] = index_t; + matrix_contents[3] = index_t->getPointerTo (); + matrix_contents[4] = string_t; + matrix_t->setBody (llvm::makeArrayRef (matrix_contents, 5)); + + llvm::Type *complex_t = llvm::VectorType::get (scalar_t, 2); + + // this is the structure that C functions return. Use this in order to get calling + // conventions right. + complex_ret = llvm::StructType::create (context, "complex_ret"); + llvm::Type *complex_ret_contents[] = {scalar_t, scalar_t}; + complex_ret->setBody (complex_ret_contents); + + // create types + any = new_type ("any", 0, any_t); + matrix = new_type ("matrix", any, matrix_t); + complex = new_type ("complex", any, complex_t); + scalar = new_type ("scalar", complex, scalar_t); + range = new_type ("range", any, range_t); + string = new_type ("string", any, string_t); + boolean = new_type ("bool", any, bool_t); + index = new_type ("index", any, index_t); + + casts.resize (next_id + 1); + identities.resize (next_id + 1, 0); + + // bind global variables + lerror_state = new llvm::GlobalVariable (*module, bool_t, false, + llvm::GlobalValue::ExternalLinkage, + 0, "error_state"); + engine->addGlobalMapping (lerror_state, + reinterpret_cast<void *> (&error_state)); + + // any with anything is an any op + llvm::Function *fn; + llvm::Type *binary_op_type + = llvm::Type::getIntNTy (context, sizeof (octave_value::binary_op)); + llvm::Function *any_binary = create_function ("octave_jit_binary_any_any", + any_t, binary_op_type, + any_t, any_t); + engine->addGlobalMapping (any_binary, + reinterpret_cast<void*>(&octave_jit_binary_any_any)); + + binary_ops.resize (octave_value::num_binary_ops); + for (size_t i = 0; i < octave_value::num_binary_ops; ++i) + { + octave_value::binary_op op = static_cast<octave_value::binary_op> (i); + std::string op_name = octave_value::binary_op_as_string (op); + binary_ops[i].stash_name ("binary" + op_name); + } + + for (int op = 0; op < octave_value::num_binary_ops; ++op) + { + llvm::Twine fn_name ("octave_jit_binary_any_any_"); + fn_name = fn_name + llvm::Twine (op); + fn = create_function (fn_name, any, any, any); + llvm::BasicBlock *block = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (block); + llvm::APInt op_int(sizeof (octave_value::binary_op), op, + std::numeric_limits<octave_value::binary_op>::is_signed); + llvm::Value *op_as_llvm = llvm::ConstantInt::get (binary_op_type, op_int); + llvm::Value *ret = builder.CreateCall3 (any_binary, + op_as_llvm, + fn->arg_begin (), + ++fn->arg_begin ()); + builder.CreateRet (ret); + binary_ops[op].add_overload (fn, true, any, any, any); + } + + llvm::Type *void_t = llvm::Type::getVoidTy (context); + + // grab any + fn = create_function ("octave_jit_grab_any", any, any); + engine->addGlobalMapping (fn, reinterpret_cast<void*>(&octave_jit_grab_any)); + grab_fn.add_overload (fn, false, any, any); + grab_fn.stash_name ("grab"); + + // grab matrix + llvm::Function *print_matrix = create_function ("octave_jit_print_matrix", + void_t, + matrix_t->getPointerTo ()); + engine->addGlobalMapping (print_matrix, + reinterpret_cast<void*>(&octave_jit_print_matrix)); + fn = create_function ("octave_jit_grab_matrix", void_t, + matrix_t->getPointerTo (), matrix_t->getPointerTo ()); + engine->addGlobalMapping (fn, + reinterpret_cast<void *> (&octave_jit_grab_matrix)); + grab_fn.add_overload (fn, false, matrix, matrix); + + // release any + fn = create_function ("octave_jit_release_any", void_t, any_t); + llvm::Function *release_any = fn; + engine->addGlobalMapping (fn, + reinterpret_cast<void*>(&octave_jit_release_any)); + release_fn.add_overload (fn, false, 0, any); + release_fn.stash_name ("release"); + + // release matrix + fn = create_function ("octave_jit_release_matrix", void_t, + matrix_t->getPointerTo ()); + engine->addGlobalMapping (fn, + reinterpret_cast<void *> (&octave_jit_release_matrix)); + release_fn.add_overload (fn, false, 0, matrix); + + // release scalar + fn = create_identity (scalar); + release_fn.add_overload (fn, false, 0, scalar); + + // release complex + fn = create_identity (complex); + release_fn.add_overload (fn, false, 0, complex); + + // release index + fn = create_identity (index); + release_fn.add_overload (fn, false, 0, index); + + // now for binary scalar operations + // FIXME: Finish all operations + add_binary_op (scalar, octave_value::op_add, llvm::Instruction::FAdd); + add_binary_op (scalar, octave_value::op_sub, llvm::Instruction::FSub); + add_binary_op (scalar, octave_value::op_mul, llvm::Instruction::FMul); + add_binary_op (scalar, octave_value::op_el_mul, llvm::Instruction::FMul); + + add_binary_fcmp (scalar, octave_value::op_lt, llvm::CmpInst::FCMP_ULT); + add_binary_fcmp (scalar, octave_value::op_le, llvm::CmpInst::FCMP_ULE); + add_binary_fcmp (scalar, octave_value::op_eq, llvm::CmpInst::FCMP_UEQ); + add_binary_fcmp (scalar, octave_value::op_ge, llvm::CmpInst::FCMP_UGE); + add_binary_fcmp (scalar, octave_value::op_gt, llvm::CmpInst::FCMP_UGT); + add_binary_fcmp (scalar, octave_value::op_ne, llvm::CmpInst::FCMP_UNE); + + llvm::Function *gripe_div0 = create_function ("gripe_divide_by_zero", void_t); + engine->addGlobalMapping (gripe_div0, + reinterpret_cast<void *> (&gripe_divide_by_zero)); + + // divide is annoying because it might error + fn = create_function ("octave_jit_div_scalar_scalar", scalar, scalar, scalar); + llvm::BasicBlock *body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::BasicBlock *warn_block = llvm::BasicBlock::Create (context, "warn", + fn); + llvm::BasicBlock *normal_block = llvm::BasicBlock::Create (context, + "normal", fn); + + llvm::Value *zero = llvm::ConstantFP::get (scalar_t, 0); + llvm::Value *check = builder.CreateFCmpUEQ (zero, ++fn->arg_begin ()); + builder.CreateCondBr (check, warn_block, normal_block); + + builder.SetInsertPoint (warn_block); + builder.CreateCall (gripe_div0); + builder.CreateBr (normal_block); + + builder.SetInsertPoint (normal_block); + llvm::Value *ret = builder.CreateFDiv (fn->arg_begin (), + ++fn->arg_begin ()); + builder.CreateRet (ret); + + jit_operation::overload ol (fn, true, scalar, scalar, scalar); + binary_ops[octave_value::op_div].add_overload (ol); + binary_ops[octave_value::op_el_div].add_overload (ol); + } + llvm::verifyFunction (*fn); + + // ldiv is the same as div with the operators reversed + fn = mirror_binary (fn); + { + jit_operation::overload ol (fn, true, scalar, scalar, scalar); + binary_ops[octave_value::op_ldiv].add_overload (ol); + binary_ops[octave_value::op_el_ldiv].add_overload (ol); + } + + // In general, the result of scalar ^ scalar is a complex number. We might be + // able to improve on this if we keep track of the range of values varaibles + // can take on. + fn = create_function ("octave_jit_pow_scalar_scalar", complex_ret, scalar_t, + scalar_t); + engine->addGlobalMapping (fn, reinterpret_cast<void *> (octave_jit_pow_scalar_scalar)); + { + jit_operation::overload ol (wrap_complex (fn), false, complex, scalar, + scalar); + binary_ops[octave_value::op_pow].add_overload (ol); + binary_ops[octave_value::op_el_pow].add_overload (ol); + } + + // now for binary complex operations + add_binary_op (complex, octave_value::op_add, llvm::Instruction::FAdd); + add_binary_op (complex, octave_value::op_sub, llvm::Instruction::FSub); + + fn = create_function ("octave_jit_*_complex_complex", complex, complex, + complex); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + // (x0*x1 - y0*y1, x0*y1 + y0*x1) = (x0,y0) * (x1,y1) + // We compute this in one vectorized multiplication, a subtraction, and an + // addition. + llvm::Value *lhs = fn->arg_begin (); + llvm::Value *rhs = ++fn->arg_begin (); + + // FIXME: We need a better way of doing this, working with llvm's IR + // directly is sort of a pain. + llvm::Value *zero = builder.getInt32 (0); + llvm::Value *one = builder.getInt32 (1); + llvm::Value *two = builder.getInt32 (2); + llvm::Value *three = builder.getInt32 (3); + + llvm::Type *vec4 = llvm::VectorType::get (scalar_t, 4); + llvm::Value *mlhs = llvm::UndefValue::get (vec4); + llvm::Value *mrhs = mlhs; + + llvm::Value *temp = complex_real (lhs); + mlhs = builder.CreateInsertElement (mlhs, temp, zero); + mlhs = builder.CreateInsertElement (mlhs, temp, two); + temp = complex_imag (lhs); + mlhs = builder.CreateInsertElement (mlhs, temp, one); + mlhs = builder.CreateInsertElement (mlhs, temp, three); + + temp = complex_real (rhs); + mrhs = builder.CreateInsertElement (mrhs, temp, zero); + mrhs = builder.CreateInsertElement (mrhs, temp, three); + temp = complex_imag (rhs); + mrhs = builder.CreateInsertElement (mrhs, temp, one); + mrhs = builder.CreateInsertElement (mrhs, temp, two); + + llvm::Value *mres = builder.CreateFMul (mlhs, mrhs); + llvm::Value *tlhs = builder.CreateExtractElement (mres, zero); + llvm::Value *trhs = builder.CreateExtractElement (mres, one); + llvm::Value *ret_real = builder.CreateFSub (tlhs, trhs); + + tlhs = builder.CreateExtractElement (mres, two); + trhs = builder.CreateExtractElement (mres, three); + llvm::Value *ret_imag = builder.CreateFAdd (tlhs, trhs); + builder.CreateRet (complex_new (ret_real, ret_imag)); + + jit_operation::overload ol (fn, false, complex, complex, complex); + binary_ops[octave_value::op_mul].add_overload (ol); + binary_ops[octave_value::op_el_mul].add_overload (ol); + } + llvm::verifyFunction (*fn); + + llvm::Function *complex_div = create_function ("octave_jit_complex_div", + complex_ret, complex_ret, + complex_ret); + engine->addGlobalMapping (complex_div, + reinterpret_cast<void *> (&octave_jit_complex_div)); + complex_div = wrap_complex (complex_div); + { + jit_operation::overload ol (complex_div, true, complex, complex, complex); + binary_ops[octave_value::op_div].add_overload (ol); + binary_ops[octave_value::op_ldiv].add_overload (ol); + } + + fn = mirror_binary (complex_div); + { + jit_operation::overload ol (fn, true, complex, complex, complex); + binary_ops[octave_value::op_ldiv].add_overload (ol); + binary_ops[octave_value::op_el_ldiv].add_overload (ol); + } + + fn = create_function ("octave_jit_pow_complex_complex", complex_ret, + complex_ret, complex_ret); + engine->addGlobalMapping (fn, reinterpret_cast<void *> (octave_jit_pow_complex_complex)); + { + jit_operation::overload ol (wrap_complex (fn), false, complex, complex, + complex); + binary_ops[octave_value::op_pow].add_overload (ol); + binary_ops[octave_value::op_el_pow].add_overload (ol); + } + + fn = create_function ("octave_jit_*_scalar_complex", complex, scalar, + complex); + llvm::Function *mul_scalar_complex = fn; + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *lhs = fn->arg_begin (); + llvm::Value *tlhs = complex_new (lhs, lhs); + llvm::Value *rhs = ++fn->arg_begin (); + builder.CreateRet (builder.CreateFMul (tlhs, rhs)); + + jit_operation::overload ol (fn, false, complex, scalar, complex); + binary_ops[octave_value::op_mul].add_overload (ol); + binary_ops[octave_value::op_el_mul].add_overload (ol); + } + llvm::verifyFunction (*fn); + + fn = mirror_binary (mul_scalar_complex); + { + jit_operation::overload ol (fn, false, complex, complex, scalar); + binary_ops[octave_value::op_mul].add_overload (ol); + binary_ops[octave_value::op_el_mul].add_overload (ol); + } + + fn = create_function ("octave_jit_+_scalar_complex", complex, scalar, + complex); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *lhs = fn->arg_begin (); + llvm::Value *rhs = ++fn->arg_begin (); + llvm::Value *real = builder.CreateFAdd (lhs, complex_real (rhs)); + builder.CreateRet (complex_real (rhs, real)); + llvm::verifyFunction (*fn); + + binary_ops[octave_value::op_add].add_overload (fn, false, complex, scalar, + complex); + fn = mirror_binary (fn); + binary_ops[octave_value::op_add].add_overload (fn, false, complex, complex, + scalar); + } + + fn = create_function ("octave_jit_-_complex_scalar", complex, complex, + scalar); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *lhs = fn->arg_begin (); + llvm::Value *rhs = ++fn->arg_begin (); + llvm::Value *real = builder.CreateFSub (complex_real (lhs), rhs); + builder.CreateRet (complex_real (lhs, real)); + llvm::verifyFunction (*fn); + + binary_ops[octave_value::op_sub].add_overload (fn, false, complex, complex, + scalar); + } + + fn = create_function ("octave_jit_-_scalar_complex", complex, scalar, + complex); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *lhs = fn->arg_begin (); + llvm::Value *rhs = ++fn->arg_begin (); + llvm::Value *real = builder.CreateFSub (lhs, complex_real (rhs)); + builder.CreateRet (complex_real (rhs, real)); + llvm::verifyFunction (*fn); + + binary_ops[octave_value::op_sub].add_overload (fn, false, complex, scalar, + complex); + } + + fn = create_function ("octave_jit_pow_scalar_complex", complex_ret, + scalar_t, complex_ret); + engine->addGlobalMapping (fn, reinterpret_cast<void *> (octave_jit_pow_scalar_complex)); + { + jit_operation::overload ol (wrap_complex (fn), false, complex, scalar, + complex); + binary_ops[octave_value::op_pow].add_overload (ol); + binary_ops[octave_value::op_el_pow].add_overload (ol); + } + + fn = create_function ("octave_jit_pow_complex_scalar", complex_ret, + complex_ret, scalar_t); + engine->addGlobalMapping (fn, reinterpret_cast<void *> (octave_jit_pow_complex_complex)); + { + jit_operation::overload ol (wrap_complex (fn), false, complex, complex, + scalar); + binary_ops[octave_value::op_pow].add_overload (ol); + binary_ops[octave_value::op_el_pow].add_overload (ol); + } + + // now for binary index operators + add_binary_op (index, octave_value::op_add, llvm::Instruction::Add); + + // and binary bool operators + add_binary_op (boolean, octave_value::op_el_or, llvm::Instruction::Or); + add_binary_op (boolean, octave_value::op_el_and, llvm::Instruction::And); + + // now for printing functions + print_fn.stash_name ("print"); + add_print (any, reinterpret_cast<void*> (&octave_jit_print_any)); + add_print (scalar, reinterpret_cast<void*> (&octave_jit_print_double)); + + // initialize for loop + for_init_fn.stash_name ("for_init"); + + fn = create_function ("octave_jit_for_range_init", index, range); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *zero = llvm::ConstantInt::get (index_t, 0); + builder.CreateRet (zero); + } + llvm::verifyFunction (*fn); + for_init_fn.add_overload (fn, false, index, range); + + // bounds check for for loop + for_check_fn.stash_name ("for_check"); + + fn = create_function ("octave_jit_for_range_check", boolean, range, index); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *nelem + = builder.CreateExtractValue (fn->arg_begin (), 3); + llvm::Value *idx = ++fn->arg_begin (); + llvm::Value *ret = builder.CreateICmpULT (idx, nelem); + builder.CreateRet (ret); + } + llvm::verifyFunction (*fn); + for_check_fn.add_overload (fn, false, boolean, range, index); + + // index variabe for for loop + for_index_fn.stash_name ("for_index"); + + fn = create_function ("octave_jit_for_range_idx", scalar, range, index); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *idx = ++fn->arg_begin (); + llvm::Value *didx = builder.CreateSIToFP (idx, scalar_t); + llvm::Value *rng = fn->arg_begin (); + llvm::Value *base = builder.CreateExtractValue (rng, 0); + llvm::Value *inc = builder.CreateExtractValue (rng, 2); + + llvm::Value *ret = builder.CreateFMul (didx, inc); + ret = builder.CreateFAdd (base, ret); + builder.CreateRet (ret); + } + llvm::verifyFunction (*fn); + for_index_fn.add_overload (fn, false, scalar, range, index); + + // logically true + logically_true_fn.stash_name ("logically_true"); + + llvm::Function *gripe_nantl + = create_function ("octave_jit_gripe_nan_to_logical_conversion", void_t); + engine->addGlobalMapping (gripe_nantl, reinterpret_cast<void *> (&octave_jit_gripe_nan_to_logical_conversion)); + + fn = create_function ("octave_jit_logically_true_scalar", boolean, scalar); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::BasicBlock *error_block = llvm::BasicBlock::Create (context, "error", + fn); + llvm::BasicBlock *normal_block = llvm::BasicBlock::Create (context, + "normal", fn); + + llvm::Value *check = builder.CreateFCmpUNE (fn->arg_begin (), + fn->arg_begin ()); + builder.CreateCondBr (check, error_block, normal_block); + + builder.SetInsertPoint (error_block); + builder.CreateCall (gripe_nantl); + builder.CreateBr (normal_block); + builder.SetInsertPoint (normal_block); + + llvm::Value *zero = llvm::ConstantFP::get (scalar_t, 0); + llvm::Value *ret = builder.CreateFCmpONE (fn->arg_begin (), zero); + builder.CreateRet (ret); + } + llvm::verifyFunction (*fn); + logically_true_fn.add_overload (fn, true, boolean, scalar); + + fn = create_function ("octave_logically_true_bool", boolean, boolean); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + builder.CreateRet (fn->arg_begin ()); + llvm::verifyFunction (*fn); + logically_true_fn.add_overload (fn, false, boolean, boolean); + + // make_range + // FIXME: May be benificial to implement all in LLVM + make_range_fn.stash_name ("make_range"); + llvm::Function *compute_nelem + = create_function ("octave_jit_compute_nelem", index, scalar, scalar, + scalar); + engine->addGlobalMapping (compute_nelem, + reinterpret_cast<void*> (&octave_jit_compute_nelem)); + + fn = create_function ("octave_jit_make_range", range, scalar, scalar, scalar); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Function::arg_iterator args = fn->arg_begin (); + llvm::Value *base = args; + llvm::Value *limit = ++args; + llvm::Value *inc = ++args; + llvm::Value *nelem = builder.CreateCall3 (compute_nelem, base, limit, inc); + + llvm::Value *dzero = llvm::ConstantFP::get (scalar_t, 0); + llvm::Value *izero = llvm::ConstantInt::get (index_t, 0); + llvm::Value *rng = llvm::ConstantStruct::get (range_t, dzero, dzero, dzero, + izero, NULL); + rng = builder.CreateInsertValue (rng, base, 0); + rng = builder.CreateInsertValue (rng, limit, 1); + rng = builder.CreateInsertValue (rng, inc, 2); + rng = builder.CreateInsertValue (rng, nelem, 3); + builder.CreateRet (rng); + } + llvm::verifyFunction (*fn); + make_range_fn.add_overload (fn, false, range, scalar, scalar, scalar); + + // paren_subsref + llvm::Function *ginvalid_index = create_function ("gipe_invalid_index", + void_t); + engine->addGlobalMapping (ginvalid_index, + reinterpret_cast<void*> (&octave_jit_ginvalid_index)); + + llvm::Function *gindex_range = create_function ("gripe_index_out_of_range", + void_t, int_t, int_t, index_t, + index_t); + engine->addGlobalMapping (gindex_range, + reinterpret_cast<void*> (&octave_jit_gindex_range)); + + fn = create_function ("()subsref", scalar, matrix, scalar); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *one = llvm::ConstantInt::get (index_t, 1); + llvm::Value *ione; + if (index_t == int_t) + ione = one; + else + ione = llvm::ConstantInt::get (int_t, 1); + + llvm::Value *undef = llvm::UndefValue::get (scalar_t); + + llvm::Function::arg_iterator args = fn->arg_begin (); + llvm::Value *mat = args++; + llvm::Value *idx = args; + + // convert index to scalar to integer, and check index >= 1 + llvm::Value *int_idx = builder.CreateFPToSI (idx, index_t); + llvm::Value *check_idx = builder.CreateSIToFP (int_idx, scalar_t); + llvm::Value *cond0 = builder.CreateFCmpUNE (idx, check_idx); + llvm::Value *cond1 = builder.CreateICmpSLT (int_idx, one); + llvm::Value *cond = builder.CreateOr (cond0, cond1); + + llvm::BasicBlock *done = llvm::BasicBlock::Create (context, "done", fn); + + llvm::BasicBlock *conv_error = llvm::BasicBlock::Create (context, + "conv_error", fn, + done); + llvm::BasicBlock *normal = llvm::BasicBlock::Create (context, "normal", fn, + done); + builder.CreateCondBr (cond, conv_error, normal); + + builder.SetInsertPoint (conv_error); + builder.CreateCall (ginvalid_index); + builder.CreateBr (done); + + builder.SetInsertPoint (normal); + llvm::Value *len = builder.CreateExtractValue (mat, + llvm::ArrayRef<unsigned> (2)); + cond = builder.CreateICmpSGT (int_idx, len); + + + llvm::BasicBlock *bounds_error = llvm::BasicBlock::Create (context, + "bounds_error", + fn, done); + + llvm::BasicBlock *success = llvm::BasicBlock::Create (context, "success", + fn, done); + builder.CreateCondBr (cond, bounds_error, success); + + builder.SetInsertPoint (bounds_error); + builder.CreateCall4 (gindex_range, ione, ione, int_idx, len); + builder.CreateBr (done); + + builder.SetInsertPoint (success); + llvm::Value *data = builder.CreateExtractValue (mat, + llvm::ArrayRef<unsigned> (1)); + llvm::Value *gep = builder.CreateInBoundsGEP (data, int_idx); + llvm::Value *ret = builder.CreateLoad (gep); + builder.CreateBr (done); + + builder.SetInsertPoint (done); + + llvm::PHINode *merge = llvm::PHINode::Create (scalar_t, 3); + builder.Insert (merge); + merge->addIncoming (undef, conv_error); + merge->addIncoming (undef, bounds_error); + merge->addIncoming (ret, success); + builder.CreateRet (merge); + } + llvm::verifyFunction (*fn); + paren_subsref_fn.add_overload (fn, true, scalar, matrix, scalar); + + // paren subsasgn + paren_subsasgn_fn.stash_name ("()subsasgn"); + + llvm::Function *resize_paren_subsasgn + = create_function ("octave_jit_paren_subsasgn_impl", void_t, + matrix_t->getPointerTo (), index_t, scalar_t); + engine->addGlobalMapping (resize_paren_subsasgn, + reinterpret_cast<void *> (&octave_jit_paren_subsasgn_impl)); + + fn = create_function ("octave_jit_paren_subsasgn", matrix, matrix, scalar, + scalar); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *one = llvm::ConstantInt::get (index_t, 1); + + llvm::Function::arg_iterator args = fn->arg_begin (); + llvm::Value *mat = args++; + llvm::Value *idx = args++; + llvm::Value *value = args; + + llvm::Value *int_idx = builder.CreateFPToSI (idx, index_t); + llvm::Value *check_idx = builder.CreateSIToFP (int_idx, scalar_t); + llvm::Value *cond0 = builder.CreateFCmpUNE (idx, check_idx); + llvm::Value *cond1 = builder.CreateICmpSLT (int_idx, one); + llvm::Value *cond = builder.CreateOr (cond0, cond1); + + llvm::BasicBlock *done = llvm::BasicBlock::Create (context, "done", fn); + + llvm::BasicBlock *conv_error = llvm::BasicBlock::Create (context, + "conv_error", fn, + done); + llvm::BasicBlock *normal = llvm::BasicBlock::Create (context, "normal", fn, + done); + builder.CreateCondBr (cond, conv_error, normal); + builder.SetInsertPoint (conv_error); + builder.CreateCall (ginvalid_index); + builder.CreateBr (done); + + builder.SetInsertPoint (normal); + llvm::Value *len = builder.CreateExtractValue (mat, + llvm::ArrayRef<unsigned> (2)); + cond0 = builder.CreateICmpSGT (int_idx, len); + + llvm::Value *rcount = builder.CreateExtractValue (mat, 0); + rcount = builder.CreateLoad (rcount); + cond1 = builder.CreateICmpSGT (rcount, one); + cond = builder.CreateOr (cond0, cond1); + + llvm::BasicBlock *bounds_error = llvm::BasicBlock::Create (context, + "bounds_error", + fn, done); + + llvm::BasicBlock *success = llvm::BasicBlock::Create (context, "success", + fn, done); + builder.CreateCondBr (cond, bounds_error, success); + + // resize on out of bounds access + builder.SetInsertPoint (bounds_error); + llvm::Value *resize_result = builder.CreateAlloca (matrix_t); + builder.CreateStore (mat, resize_result); + builder.CreateCall3 (resize_paren_subsasgn, resize_result, int_idx, value); + resize_result = builder.CreateLoad (resize_result); + builder.CreateBr (done); + + builder.SetInsertPoint (success); + llvm::Value *data = builder.CreateExtractValue (mat, + llvm::ArrayRef<unsigned> (1)); + llvm::Value *gep = builder.CreateInBoundsGEP (data, int_idx); + builder.CreateStore (value, gep); + builder.CreateBr (done); + + builder.SetInsertPoint (done); + + llvm::PHINode *merge = llvm::PHINode::Create (matrix_t, 3); + builder.Insert (merge); + merge->addIncoming (mat, conv_error); + merge->addIncoming (resize_result, bounds_error); + merge->addIncoming (mat, success); + builder.CreateRet (merge); + } + llvm::verifyFunction (*fn); + paren_subsasgn_fn.add_overload (fn, true, matrix, matrix, scalar, scalar); + + fn = create_function ("octave_jit_paren_subsasgn_matrix_range", void_t, + matrix_t->getPointerTo (), matrix_t->getPointerTo (), + range_t->getPointerTo (), scalar_t); + engine->addGlobalMapping (fn, + reinterpret_cast<void *> (&octave_jit_paren_subsasgn_matrix_range)); + paren_subsasgn_fn.add_overload (fn, true, matrix, matrix, range, scalar); + + casts[any->type_id ()].stash_name ("(any)"); + casts[scalar->type_id ()].stash_name ("(scalar)"); + casts[complex->type_id ()].stash_name ("(complex)"); + casts[matrix->type_id ()].stash_name ("(matrix)"); + + // cast any <- matrix + fn = create_function ("octave_jit_cast_any_matrix", any_t, + matrix_t->getPointerTo ()); + engine->addGlobalMapping (fn, + reinterpret_cast<void*> (&octave_jit_cast_any_matrix)); + casts[any->type_id ()].add_overload (fn, false, any, matrix); + + // cast matrix <- any + fn = create_function ("octave_jit_cast_matrix_any", void_t, + matrix_t->getPointerTo (), any_t); + engine->addGlobalMapping (fn, + reinterpret_cast<void*> (&octave_jit_cast_matrix_any)); + casts[matrix->type_id ()].add_overload (fn, false, matrix, any); + + // cast any <- scalar + fn = create_function ("octave_jit_cast_any_scalar", any, scalar); + engine->addGlobalMapping (fn, reinterpret_cast<void*> (&octave_jit_cast_any_scalar)); + casts[any->type_id ()].add_overload (fn, false, any, scalar); + + // cast scalar <- any + fn = create_function ("octave_jit_cast_scalar_any", scalar, any); + engine->addGlobalMapping (fn, reinterpret_cast<void*> (&octave_jit_cast_scalar_any)); + casts[scalar->type_id ()].add_overload (fn, false, scalar, any); + + // cast any <- complex + fn = create_function ("octave_jit_cast_any_complex", any_t, complex_ret); + engine->addGlobalMapping (fn, reinterpret_cast<void*> (&octave_jit_cast_any_complex)); + casts[any->type_id ()].add_overload (wrap_complex (fn), false, any, complex); + + // cast complex <- any + fn = create_function ("octave_jit_cast_complex_any", complex_ret, any_t); + engine->addGlobalMapping (fn, reinterpret_cast<void *> (&octave_jit_cast_complex_any)); + casts[complex->type_id ()].add_overload (wrap_complex (fn), false, complex, + any); + + // cast complex <- scalar + fn = create_function ("octave_jit_cast_complex_scalar", complex, scalar); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + llvm::Value *zero = llvm::ConstantFP::get (scalar_t, 0); + builder.CreateRet (complex_new (fn->arg_begin (), zero)); + llvm::verifyFunction (*fn); + } + casts[complex->type_id ()].add_overload (fn, false, complex, scalar); + + // cast scalar <- complex + fn = create_function ("octave_jit_cast_scalar_complex", scalar, complex); + body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + { + builder.CreateRet (complex_real (fn->arg_begin ())); + llvm::verifyFunction (*fn); + } + casts[scalar->type_id ()].add_overload (fn, false, scalar, complex); + + // cast any <- any + fn = create_identity (any); + casts[any->type_id ()].add_overload (fn, false, any, any); + + // cast scalar <- scalar + fn = create_identity (scalar); + casts[scalar->type_id ()].add_overload (fn, false, scalar, scalar); + + // cast complex <- complex + fn = create_identity (complex); + casts[complex->type_id ()].add_overload (fn, false, complex, complex); + + // -------------------- builtin functions -------------------- + add_builtin ("#unknown_function"); + unknown_function = builtins["#unknown_function"]; + + add_builtin ("sin"); + register_intrinsic ("sin", llvm::Intrinsic::sin, scalar, scalar); + register_generic ("sin", matrix, matrix); + + add_builtin ("cos"); + register_intrinsic ("cos", llvm::Intrinsic::cos, scalar, scalar); + register_generic ("cos", matrix, matrix); + + add_builtin ("exp"); + register_intrinsic ("exp", llvm::Intrinsic::cos, scalar, scalar); + register_generic ("exp", matrix, matrix); + + casts.resize (next_id + 1); + fn = create_identity (any); + for (std::map<std::string, jit_type *>::iterator iter = builtins.begin (); + iter != builtins.end (); ++iter) + { + jit_type *btype = iter->second; + release_fn.add_overload (release_any, false, 0, btype); + casts[any->type_id ()].add_overload (fn, false, any, btype); + casts[btype->type_id ()].add_overload (fn, false, btype, any); + } +} + +void +jit_typeinfo::add_print (jit_type *ty, void *call) +{ + std::stringstream name; + name << "octave_jit_print_" << ty->name (); + + llvm::Type *void_t = llvm::Type::getVoidTy (context); + llvm::Function *fn = create_function (name.str (), void_t, + llvm::Type::getInt8PtrTy (context), + ty->to_llvm ()); + engine->addGlobalMapping (fn, call); + + jit_operation::overload ol (fn, false, 0, string, ty); + print_fn.add_overload (ol); +} + +// FIXME: cp between add_binary_op, add_binary_icmp, and add_binary_fcmp +void +jit_typeinfo::add_binary_op (jit_type *ty, int op, int llvm_op) +{ + std::stringstream fname; + octave_value::binary_op ov_op = static_cast<octave_value::binary_op>(op); + fname << "octave_jit_" << octave_value::binary_op_as_string (ov_op) + << "_" << ty->name (); + + llvm::Function *fn = create_function (fname.str (), ty, ty, ty); + llvm::BasicBlock *block = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (block); + llvm::Instruction::BinaryOps temp + = static_cast<llvm::Instruction::BinaryOps>(llvm_op); + llvm::Value *ret = builder.CreateBinOp (temp, fn->arg_begin (), + ++fn->arg_begin ()); + builder.CreateRet (ret); + llvm::verifyFunction (*fn); + + jit_operation::overload ol(fn, false, ty, ty, ty); + binary_ops[op].add_overload (ol); +} + +void +jit_typeinfo::add_binary_icmp (jit_type *ty, int op, int llvm_op) +{ + std::stringstream fname; + octave_value::binary_op ov_op = static_cast<octave_value::binary_op>(op); + fname << "octave_jit" << octave_value::binary_op_as_string (ov_op) + << "_" << ty->name (); + + llvm::Function *fn = create_function (fname.str (), boolean, ty, ty); + llvm::BasicBlock *block = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (block); + llvm::CmpInst::Predicate temp + = static_cast<llvm::CmpInst::Predicate>(llvm_op); + llvm::Value *ret = builder.CreateICmp (temp, fn->arg_begin (), + ++fn->arg_begin ()); + builder.CreateRet (ret); + llvm::verifyFunction (*fn); + + jit_operation::overload ol (fn, false, boolean, ty, ty); + binary_ops[op].add_overload (ol); +} + +void +jit_typeinfo::add_binary_fcmp (jit_type *ty, int op, int llvm_op) +{ + std::stringstream fname; + octave_value::binary_op ov_op = static_cast<octave_value::binary_op>(op); + fname << "octave_jit" << octave_value::binary_op_as_string (ov_op) + << "_" << ty->name (); + + llvm::Function *fn = create_function (fname.str (), boolean, ty, ty); + llvm::BasicBlock *block = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (block); + llvm::CmpInst::Predicate temp + = static_cast<llvm::CmpInst::Predicate>(llvm_op); + llvm::Value *ret = builder.CreateFCmp (temp, fn->arg_begin (), + ++fn->arg_begin ()); + builder.CreateRet (ret); + llvm::verifyFunction (*fn); + + jit_operation::overload ol (fn, false, boolean, ty, ty); + binary_ops[op].add_overload (ol); +} + +llvm::Function * +jit_typeinfo::create_function (const llvm::Twine& name, jit_type *ret, + const std::vector<jit_type *>& args) +{ + llvm::Type *void_t = llvm::Type::getVoidTy (context); + std::vector<llvm::Type *> llvm_args (args.size (), void_t); + for (size_t i = 0; i < args.size (); ++i) + if (args[i]) + llvm_args[i] = args[i]->to_llvm (); + + return create_function (name, ret ? ret->to_llvm () : void_t, llvm_args); +} + +llvm::Function * +jit_typeinfo::create_function (const llvm::Twine& name, llvm::Type *ret, + const std::vector<llvm::Type *>& args) +{ + llvm::FunctionType *ft = llvm::FunctionType::get (ret, args, false); + llvm::Function *fn = llvm::Function::Create (ft, + llvm::Function::ExternalLinkage, + name, module); + fn->addFnAttr (llvm::Attribute::AlwaysInline); + return fn; +} + +llvm::Function * +jit_typeinfo::create_identity (jit_type *type) +{ + size_t id = type->type_id (); + if (id >= identities.size ()) + identities.resize (id + 1, 0); + + if (! identities[id]) + { + llvm::Function *fn = create_function ("id", type, type); + llvm::BasicBlock *body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + builder.CreateRet (fn->arg_begin ()); + llvm::verifyFunction (*fn); + identities[id] = fn; + } + + return identities[id]; +} + +llvm::Value * +jit_typeinfo::do_insert_error_check (void) +{ + return builder.CreateLoad (lerror_state); +} + +void +jit_typeinfo::add_builtin (const std::string& name) +{ + jit_type *btype = new_type (name, any, any->to_llvm ()); + builtins[name] = btype; + + octave_builtin *ov_builtin = find_builtin (name); + if (ov_builtin) + ov_builtin->stash_jit (*btype); +} + +void +jit_typeinfo::register_intrinsic (const std::string& name, size_t iid, + jit_type *result, + const std::vector<jit_type *>& args) +{ + jit_type *builtin_type = builtins[name]; + size_t nargs = args.size (); + llvm::SmallVector<llvm::Type *, 5> llvm_args (nargs); + for (size_t i = 0; i < nargs; ++i) + llvm_args[i] = args[i]->to_llvm (); + + llvm::Intrinsic::ID id = static_cast<llvm::Intrinsic::ID> (iid); + llvm::Function *ifun = llvm::Intrinsic::getDeclaration (module, id, + llvm_args); + std::stringstream fn_name; + fn_name << "octave_jit_" << name; + + std::vector<jit_type *> args1 (nargs + 1); + args1[0] = builtin_type; + std::copy (args.begin (), args.end (), args1.begin () + 1); + + // The first argument will be the Octave function, but we already know that + // the function call is the equivalent of the intrinsic, so we ignore it and + // call the intrinsic with the remaining arguments. + llvm::Function *fn = create_function (fn_name.str (), result, args1); + llvm::BasicBlock *body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + + llvm::SmallVector<llvm::Value *, 5> fargs (nargs); + llvm::Function::arg_iterator iter = fn->arg_begin (); + ++iter; + for (size_t i = 0; i < nargs; ++i, ++iter) + fargs[i] = iter; + + llvm::Value *ret = builder.CreateCall (ifun, fargs); + builder.CreateRet (ret); + llvm::verifyFunction (*fn); + + paren_subsref_fn.add_overload (fn, false, result, args1); +} + +octave_builtin * +jit_typeinfo::find_builtin (const std::string& name) +{ + // FIXME: Finalize what we want to store in octave_builtin, then add functions + // to access these values in octave_value + octave_value ov_builtin = symbol_table::find (name); + return dynamic_cast<octave_builtin *> (ov_builtin.internal_rep ()); +} + +void +jit_typeinfo::register_generic (const std::string&, jit_type *, + const std::vector<jit_type *>&) +{ + // FIXME: Implement +} + +llvm::Function * +jit_typeinfo::mirror_binary (llvm::Function *fn) +{ + llvm::FunctionType *fn_type = fn->getFunctionType (); + llvm::Function *ret = create_function (fn->getName () + "_reverse", + fn_type->getReturnType (), + fn_type->getParamType (1), + fn_type->getParamType (0)); + llvm::BasicBlock *body = llvm::BasicBlock::Create (context, "body", ret); + builder.SetInsertPoint (body); + llvm::Value *result = builder.CreateCall2 (fn, ++ret->arg_begin (), + ret->arg_begin ()); + if (ret->getReturnType () == builder.getVoidTy ()) + builder.CreateRetVoid (); + else + builder.CreateRet (result); + + llvm::verifyFunction (*ret); + return ret; +} + +llvm::Function * +jit_typeinfo::wrap_complex (llvm::Function *wrap) +{ + llvm::SmallVector<llvm::Type *, 5> new_args; + new_args.reserve (wrap->arg_size ()); + llvm::Type *complex_t = complex->to_llvm (); + for (llvm::Function::arg_iterator iter = wrap->arg_begin (); + iter != wrap->arg_end (); ++iter) + { + llvm::Value *value = iter; + llvm::Type *type = value->getType (); + new_args.push_back (type == complex_ret ? complex_t : type); + } + + llvm::FunctionType *wrap_type = wrap->getFunctionType (); + bool convert_ret = wrap_type->getReturnType () == complex_ret; + llvm::Type *rtype = convert_ret ? complex_t : wrap->getReturnType (); + llvm::FunctionType *ft = llvm::FunctionType::get (rtype, new_args, false); + llvm::Function *fn = llvm::Function::Create (ft, + llvm::Function::ExternalLinkage, + wrap->getName () + "_wrap", + module); + llvm::BasicBlock *body = llvm::BasicBlock::Create (context, "body", fn); + builder.SetInsertPoint (body); + + llvm::SmallVector<llvm::Value *, 5> converted (new_args.size ()); + llvm::Function::arg_iterator witer = wrap->arg_begin (); + llvm::Function::arg_iterator fiter = fn->arg_begin (); + for (size_t i = 0; i < new_args.size (); ++i, ++witer, ++fiter) + { + llvm::Value *warg = witer; + llvm::Value *arg = fiter; + converted[i] = warg->getType () == arg->getType () ? arg + : pack_complex (arg); + } + + llvm::Value *ret = builder.CreateCall (wrap, converted); + if (wrap_type->getReturnType () != builder.getVoidTy ()) + { + if (convert_ret) + ret = unpack_complex (ret); + builder.CreateRet (ret); + } + else + builder.CreateRetVoid (); + + llvm::verifyFunction (*fn); + return fn; +} + +llvm::Value * +jit_typeinfo::pack_complex (llvm::Value *cplx) +{ + llvm::Value *real = builder.CreateExtractElement (cplx, builder.getInt32 (0)); + llvm::Value *imag = builder.CreateExtractElement (cplx, builder.getInt32 (1)); + llvm::Value *ret = llvm::UndefValue::get (complex_ret); + ret = builder.CreateInsertValue (ret, real, 0); + return builder.CreateInsertValue (ret, imag, 1); +} + +llvm::Value * +jit_typeinfo::unpack_complex (llvm::Value *result) +{ + llvm::Type *complex_t = complex->to_llvm (); + llvm::Value *real = builder.CreateExtractValue (result, 0); + llvm::Value *imag = builder.CreateExtractValue (result, 1); + llvm::Value *ret = llvm::UndefValue::get (complex_t); + ret = builder.CreateInsertElement (ret, real, builder.getInt32 (0)); + return builder.CreateInsertElement (ret, imag, builder.getInt32 (1)); +} + +llvm::Value * +jit_typeinfo::complex_real (llvm::Value *cx) +{ + return builder.CreateExtractElement (cx, builder.getInt32 (0)); +} + +llvm::Value * +jit_typeinfo::complex_real (llvm::Value *cx, llvm::Value *real) +{ + return builder.CreateInsertElement (cx, real, builder.getInt32 (0)); +} + +llvm::Value * +jit_typeinfo::complex_imag (llvm::Value *cx) +{ + return builder.CreateExtractElement (cx, builder.getInt32 (1)); +} + +llvm::Value * +jit_typeinfo::complex_imag (llvm::Value *cx, llvm::Value *imag) +{ + return builder.CreateInsertElement (cx, imag, builder.getInt32 (1)); +} + +llvm::Value * +jit_typeinfo::complex_new (llvm::Value *real, llvm::Value *imag) +{ + llvm::Value *ret = llvm::UndefValue::get (complex->to_llvm ()); + ret = complex_real (ret, real); + return complex_imag (ret, imag); +} + +jit_type * +jit_typeinfo::do_type_of (const octave_value &ov) const +{ + if (ov.is_function ()) + { + // FIXME: This is ugly, we need to finalize how we want to to this, then + // have octave_value fully support the needed functionality + octave_builtin *builtin + = dynamic_cast<octave_builtin *> (ov.internal_rep ()); + return builtin && builtin->to_jit () ? builtin->to_jit () + : unknown_function; + } + + if (ov.is_range ()) + return get_range (); + + if (ov.is_double_type ()) + { + if (ov.is_real_scalar ()) + return get_scalar (); + + if (ov.is_matrix_type ()) + return get_matrix (); + } + + if (ov.is_complex_scalar ()) + return get_complex (); + + return get_any (); +} + +jit_type* +jit_typeinfo::new_type (const std::string& name, jit_type *parent, + llvm::Type *llvm_type) +{ + jit_type *ret = new jit_type (name, parent, llvm_type, next_id++); + id_to_type.push_back (ret); + return ret; +} + +// -------------------- jit_use -------------------- +jit_block * +jit_use::user_parent (void) const +{ + return muser->parent (); +} + +// -------------------- jit_value -------------------- +jit_value::~jit_value (void) +{} + +jit_block * +jit_value::first_use_block (void) +{ + jit_use *use = first_use (); + while (use) + { + if (! isa<jit_error_check> (use->user ())) + return use->user_parent (); + + use = use->next (); + } + + return 0; +} + +void +jit_value::replace_with (jit_value *value) +{ + while (first_use ()) + { + jit_instruction *user = first_use ()->user (); + size_t idx = first_use ()->index (); + user->stash_argument (idx, value); + } +} + +#define JIT_METH(clname) \ + void \ + jit_ ## clname::accept (jit_ir_walker& walker) \ + { \ + walker.visit (*this); \ + } + +JIT_VISIT_IR_NOTEMPLATE +#undef JIT_METH + +std::ostream& +operator<< (std::ostream& os, const jit_value& value) +{ + return value.short_print (os); +} + +std::ostream& +jit_print (std::ostream& os, jit_value *avalue) +{ + if (avalue) + return avalue->print (os); + return os << "NULL"; +} + +// -------------------- jit_instruction -------------------- +void +jit_instruction::remove (void) +{ + if (mparent) + mparent->remove (mlocation); + resize_arguments (0); +} + +llvm::BasicBlock * +jit_instruction::parent_llvm (void) const +{ + return mparent->to_llvm (); +} + +std::ostream& +jit_instruction::short_print (std::ostream& os) const +{ + if (type ()) + jit_print (os, type ()) << ": "; + return os << "#" << mid; +} + +void +jit_instruction::do_construct_ssa (size_t start, size_t end) +{ + for (size_t i = start; i < end; ++i) + { + jit_value *arg = argument (i); + jit_variable *var = dynamic_cast<jit_variable *> (arg); + if (var && var->has_top ()) + stash_argument (i, var->top ()); + } +} + +// -------------------- jit_block -------------------- +void +jit_block::replace_with (jit_value *value) +{ + assert (isa<jit_block> (value)); + jit_block *block = static_cast<jit_block *> (value); + + jit_value::replace_with (block); + + while (ILIST_T::first_use ()) + { + jit_phi_incomming *incomming = ILIST_T::first_use (); + incomming->stash_value (block); + } +} + +void +jit_block::replace_in_phi (jit_block *ablock, jit_block *with) +{ + jit_phi_incomming *node = ILIST_T::first_use (); + while (node) + { + jit_phi_incomming *prev = node; + node = node->next (); + + if (prev->user_parent () == ablock) + prev->stash_value (with); + } +} + +jit_block * +jit_block::maybe_merge () +{ + if (successor_count () == 1 && successor (0) != this + && (successor (0)->use_count () == 1 || instructions.size () == 1)) + { + jit_block *to_merge = successor (0); + merge (*to_merge); + return to_merge; + } + + return 0; +} + +void +jit_block::merge (jit_block& block) +{ + // the merge block will contain a new terminator + jit_terminator *old_term = terminator (); + if (old_term) + old_term->remove (); + + bool was_empty = end () == begin (); + iterator merge_begin = end (); + if (! was_empty) + --merge_begin; + + instructions.splice (end (), block.instructions); + if (was_empty) + merge_begin = begin (); + else + ++merge_begin; + + // now merge_begin points to the start of the new instructions, we must + // update their parent information + for (iterator iter = merge_begin; iter != end (); ++iter) + { + jit_instruction *instr = *iter; + instr->stash_parent (this, iter); + } + + block.replace_with (this); +} + +jit_instruction * +jit_block::prepend (jit_instruction *instr) +{ + instructions.push_front (instr); + instr->stash_parent (this, instructions.begin ()); + return instr; +} + +jit_instruction * +jit_block::prepend_after_phi (jit_instruction *instr) +{ + // FIXME: Make this O(1) + for (iterator iter = begin (); iter != end (); ++iter) + { + jit_instruction *temp = *iter; + if (! isa<jit_phi> (temp)) + { + insert_before (iter, instr); + return instr; + } + } + + return append (instr); +} + +void +jit_block::internal_append (jit_instruction *instr) +{ + instructions.push_back (instr); + instr->stash_parent (this, --instructions.end ()); +} + +jit_instruction * +jit_block::insert_before (iterator loc, jit_instruction *instr) +{ + iterator iloc = instructions.insert (loc, instr); + instr->stash_parent (this, iloc); + return instr; +} + +jit_instruction * +jit_block::insert_after (iterator loc, jit_instruction *instr) +{ + ++loc; + iterator iloc = instructions.insert (loc, instr); + instr->stash_parent (this, iloc); + return instr; +} + +jit_terminator * +jit_block::terminator (void) const +{ + assert (this); + if (instructions.empty ()) + return 0; + + jit_instruction *last = instructions.back (); + return dynamic_cast<jit_terminator *> (last); +} + +bool +jit_block::branch_alive (jit_block *asucc) const +{ + return terminator ()->alive (asucc); +} + +jit_block * +jit_block::successor (size_t i) const +{ + jit_terminator *term = terminator (); + return term->successor (i); +} + +size_t +jit_block::successor_count (void) const +{ + jit_terminator *term = terminator (); + return term ? term->successor_count () : 0; +} + +llvm::BasicBlock * +jit_block::to_llvm (void) const +{ + return llvm::cast<llvm::BasicBlock> (llvm_value); +} + +std::ostream& +jit_block::print_dom (std::ostream& os) const +{ + short_print (os); + os << ":\n"; + os << " mid: " << mid << std::endl; + os << " predecessors: "; + for (jit_use *use = first_use (); use; use = use->next ()) + os << *use->user_parent () << " "; + os << std::endl; + + os << " successors: "; + for (size_t i = 0; i < successor_count (); ++i) + os << *successor (i) << " "; + os << std::endl; + + os << " idom: "; + if (idom) + os << *idom; + else + os << "NULL"; + os << std::endl; + os << " df: "; + for (df_iterator iter = df_begin (); iter != df_end (); ++iter) + os << **iter << " "; + os << std::endl; + + os << " dom_succ: "; + for (size_t i = 0; i < dom_succ.size (); ++i) + os << *dom_succ[i] << " "; + + return os << std::endl; +} + +void +jit_block::compute_df (size_t avisit_count) +{ + if (visited (avisit_count)) + return; + + if (use_count () >= 2) + { + for (jit_use *use = first_use (); use; use = use->next ()) + { + jit_block *runner = use->user_parent (); + while (runner != idom) + { + runner->mdf.insert (this); + runner = runner->idom; + } + } + } + + for (size_t i = 0; i < successor_count (); ++i) + successor (i)->compute_df (avisit_count); +} + +bool +jit_block::update_idom (size_t avisit_count) +{ + if (visited (avisit_count) || ! use_count ()) + return false; + + bool changed = false; + for (jit_use *use = first_use (); use; use = use->next ()) + { + jit_block *pred = use->user_parent (); + changed = pred->update_idom (avisit_count) || changed; + } + + jit_use *use = first_use (); + jit_block *new_idom = use->user_parent (); + use = use->next (); + + for (; use; use = use->next ()) + { + jit_block *pred = use->user_parent (); + jit_block *pidom = pred->idom; + if (pidom) + new_idom = idom_intersect (pidom, new_idom); + } + + if (idom != new_idom) + { + idom = new_idom; + return true; + } + + return changed; +} + +void +jit_block::pop_all (void) +{ + for (iterator iter = begin (); iter != end (); ++iter) + { + jit_instruction *instr = *iter; + instr->pop_variable (); + } +} + +jit_block * +jit_block::maybe_split (jit_convert& convert, jit_block *asuccessor) +{ + if (successor_count () > 1) + { + jit_terminator *term = terminator (); + size_t idx = term->successor_index (asuccessor); + jit_block *split = convert.create<jit_block> ("phi_split", mvisit_count); + + // try to place splits where they make sense + if (id () < asuccessor->id ()) + convert.insert_before (asuccessor, split); + else + convert.insert_after (this, split); + + term->stash_argument (idx, split); + jit_branch *br = split->append (convert.create<jit_branch> (asuccessor)); + replace_in_phi (asuccessor, split); + + if (alive ()) + { + split->mark_alive (); + br->infer (); + } + + return split; + } + + return this; +} + +void +jit_block::create_dom_tree (size_t avisit_count) +{ + if (visited (avisit_count)) + return; + + if (idom != this) + idom->dom_succ.push_back (this); + + for (size_t i = 0; i < successor_count (); ++i) + successor (i)->create_dom_tree (avisit_count); +} + +jit_block * +jit_block::idom_intersect (jit_block *i, jit_block *j) +{ + while (i && j && i != j) + { + while (i && i->id () > j->id ()) + i = i->idom; + + while (i && j && j->id () > i->id ()) + j = j->idom; + } + + return i ? i : j; +} + +// -------------------- jit_phi_incomming -------------------- + +jit_block * +jit_phi_incomming::user_parent (void) const +{ return muser->parent (); } + +// -------------------- jit_phi -------------------- +bool +jit_phi::prune (void) +{ + jit_block *p = parent (); + size_t new_idx = 0; + jit_value *unique = argument (1); + + for (size_t i = 0; i < argument_count (); ++i) + { + jit_block *inc = incomming (i); + if (inc->branch_alive (p)) + { + if (unique != argument (i)) + unique = 0; + + if (new_idx != i) + { + stash_argument (new_idx, argument (i)); + mincomming[new_idx].stash_value (inc); + } + + ++new_idx; + } + } + + if (new_idx != argument_count ()) + { + resize_arguments (new_idx); + mincomming.resize (new_idx); + } + + assert (argument_count () > 0); + if (unique) + { + replace_with (unique); + return true; + } + + return false; +} + +bool +jit_phi::infer (void) +{ + jit_block *p = parent (); + if (! p->alive ()) + return false; + + jit_type *infered = 0; + for (size_t i = 0; i < argument_count (); ++i) + { + jit_block *inc = incomming (i); + if (inc->branch_alive (p)) + infered = jit_typeinfo::join (infered, argument_type (i)); + } + + if (infered != type ()) + { + stash_type (infered); + return true; + } + + return false; +} + +llvm::PHINode * +jit_phi::to_llvm (void) const +{ + return llvm::cast<llvm::PHINode> (jit_value::to_llvm ()); +} + +// -------------------- jit_terminator -------------------- +size_t +jit_terminator::successor_index (const jit_block *asuccessor) const +{ + size_t scount = successor_count (); + for (size_t i = 0; i < scount; ++i) + if (successor (i) == asuccessor) + return i; + + panic_impossible (); +} + +bool +jit_terminator::infer (void) +{ + if (! parent ()->alive ()) + return false; + + bool changed = false; + for (size_t i = 0; i < malive.size (); ++i) + if (! malive[i] && check_alive (i)) + { + changed = true; + malive[i] = true; + successor (i)->mark_alive (); + } + + return changed; +} + +llvm::TerminatorInst * +jit_terminator::to_llvm (void) const +{ + return llvm::cast<llvm::TerminatorInst> (jit_value::to_llvm ()); +} + +// -------------------- jit_call -------------------- +bool +jit_call::infer (void) +{ + // FIXME: explain algorithm + for (size_t i = 0; i < argument_count (); ++i) + { + already_infered[i] = argument_type (i); + if (! already_infered[i]) + return false; + } + + jit_type *infered = mfunction.get_result (already_infered); + if (! infered && use_count ()) + { + std::stringstream ss; + ss << "Missing overload in type inference for "; + print (ss, 0); + fail (ss.str ()); + } + + if (infered != type ()) + { + stash_type (infered); + return true; + } + + return false; +} + +// -------------------- jit_convert -------------------- +jit_convert::jit_convert (llvm::Module *module, tree &tee) + : iterator_count (0), short_count (0), breaking (false) +{ + jit_instruction::reset_ids (); + + entry_block = create<jit_block> ("body"); + final_block = create<jit_block> ("final"); + append (entry_block); + entry_block->mark_alive (); + block = entry_block; + visit (tee); + + // FIXME: Remove if we no longer only compile loops + assert (! breaking); + assert (breaks.empty ()); + assert (continues.empty ()); + + block->append (create<jit_branch> (final_block)); + append (final_block); + + for (vmap_t::iterator iter = vmap.begin (); iter != vmap.end (); ++iter) + { + jit_variable *var = iter->second; + const std::string& name = var->name (); + if (name.size () && name[0] != '#') + final_block->append (create<jit_store_argument> (var)); + } + + construct_ssa (); + + // initialize the worklist to instructions derived from constants + for (std::list<jit_value *>::iterator iter = constants.begin (); + iter != constants.end (); ++iter) + append_users (*iter); + + // FIXME: Describe algorithm here + while (worklist.size ()) + { + jit_instruction *next = worklist.front (); + worklist.pop_front (); + next->stash_in_worklist (false); + + if (next->infer ()) + { + // terminators need to be handles specially + if (jit_terminator *term = dynamic_cast<jit_terminator *> (next)) + append_users_term (term); + else + append_users (next); + } + } + + remove_dead (); + merge_blocks (); + final_block->label (); + place_releases (); + simplify_phi (); + +#ifdef OCTAVE_JIT_DEBUG + final_block->label (); + std::cout << "-------------------- Compiling tree --------------------\n"; + std::cout << tee.str_print_code () << std::endl; + print_blocks ("octave jit ir"); +#endif + + // for now just init arguments from entry, later we will have to do something + // more interesting + for (jit_block::iterator iter = entry_block->begin (); + iter != entry_block->end (); ++iter) + if (jit_extract_argument *extract + = dynamic_cast<jit_extract_argument *> (*iter)) + arguments.push_back (std::make_pair (extract->name (), true)); + + convert_llvm to_llvm (*this); + function = to_llvm.convert (module, arguments, blocks, constants); + +#ifdef OCTAVE_JIT_DEBUG + std::cout << "-------------------- llvm ir --------------------"; + llvm::raw_os_ostream llvm_cout (std::cout); + function->print (llvm_cout); + std::cout << std::endl; + llvm::verifyFunction (*function); +#endif +} + +jit_convert::~jit_convert (void) +{ + for (std::list<jit_value *>::iterator iter = all_values.begin (); + iter != all_values.end (); ++iter) + delete *iter; +} + +void +jit_convert::visit_anon_fcn_handle (tree_anon_fcn_handle&) +{ + fail (); +} + +void +jit_convert::visit_argument_list (tree_argument_list&) +{ + fail (); +} + +void +jit_convert::visit_binary_expression (tree_binary_expression& be) +{ + if (be.op_type () >= octave_value::num_binary_ops) + { + tree_boolean_expression *boole; + boole = dynamic_cast<tree_boolean_expression *> (&be); + assert (boole); + bool is_and = boole->op_type () == tree_boolean_expression::bool_and; + + std::stringstream ss; + ss << "#short_result" << short_count++; + + std::string short_name = ss.str (); + jit_variable *short_result = create<jit_variable> (short_name); + vmap[short_name] = short_result; + + jit_block *done = create<jit_block> (block->name ()); + tree_expression *lhs = be.lhs (); + jit_value *lhsv = visit (lhs); + lhsv = create_checked (&jit_typeinfo::logically_true, lhsv); + + jit_block *short_early = create<jit_block> ("short_early"); + append (short_early); + + jit_block *short_cont = create<jit_block> ("short_cont"); + + if (is_and) + block->append (create<jit_cond_branch> (lhsv, short_cont, short_early)); + else + block->append (create<jit_cond_branch> (lhsv, short_early, short_cont)); + + block = short_early; + + jit_value *early_result = create<jit_const_bool> (! is_and); + block->append (create<jit_assign> (short_result, early_result)); + block->append (create<jit_branch> (done)); + + append (short_cont); + block = short_cont; + + tree_expression *rhs = be.rhs (); + jit_value *rhsv = visit (rhs); + rhsv = create_checked (&jit_typeinfo::logically_true, rhsv); + block->append (create<jit_assign> (short_result, rhsv)); + block->append (create<jit_branch> (done)); + + append (done); + block = done; + result = short_result; + } + else + { + tree_expression *lhs = be.lhs (); + jit_value *lhsv = visit (lhs); + + tree_expression *rhs = be.rhs (); + jit_value *rhsv = visit (rhs); + + const jit_operation& fn = jit_typeinfo::binary_op (be.op_type ()); + result = create_checked (fn, lhsv, rhsv); + } +} + +void +jit_convert::visit_break_command (tree_break_command&) +{ + breaks.push_back (block); + breaking = true; +} + +void +jit_convert::visit_colon_expression (tree_colon_expression& expr) +{ + // in the futher we need to add support for classes and deal with rvalues + jit_value *base = visit (expr.base ()); + jit_value *limit = visit (expr.limit ()); + jit_value *increment; + tree_expression *tinc = expr.increment (); + + if (tinc) + increment = visit (tinc); + else + increment = create<jit_const_scalar> (1); + + result = block->append (create<jit_call> (jit_typeinfo::make_range, base, + limit, increment)); +} + +void +jit_convert::visit_continue_command (tree_continue_command&) +{ + continues.push_back (block); + breaking = true; +} + +void +jit_convert::visit_global_command (tree_global_command&) +{ + fail (); +} + +void +jit_convert::visit_persistent_command (tree_persistent_command&) +{ + fail (); +} + +void +jit_convert::visit_decl_elt (tree_decl_elt&) +{ + fail (); +} + +void +jit_convert::visit_decl_init_list (tree_decl_init_list&) +{ + fail (); +} + +void +jit_convert::visit_simple_for_command (tree_simple_for_command& cmd) +{ + // Note we do an initial check to see if the loop will run atleast once. + // This allows us to get better type inference bounds on variables defined + // and used only inside the for loop (e.g. the index variable) + + // If we are a nested for loop we need to store the previous breaks + assert (! breaking); + unwind_protect prot; + prot.protect_var (breaks); + prot.protect_var (continues); + prot.protect_var (breaking); + breaks.clear (); + continues.clear (); + + // we need a variable for our iterator, because it is used in multiple blocks + std::stringstream ss; + ss << "#iter" << iterator_count++; + std::string iter_name = ss.str (); + jit_variable *iterator = create<jit_variable> (iter_name); + vmap[iter_name] = iterator; + + jit_block *body = create<jit_block> ("for_body"); + append (body); + + jit_block *tail = create<jit_block> ("for_tail"); + + // do control expression, iter init, and condition check in prev_block (block) + jit_value *control = visit (cmd.control_expr ()); + jit_call *init_iter = create<jit_call> (jit_typeinfo::for_init, control); + block->append (init_iter); + block->append (create<jit_assign> (iterator, init_iter)); + + jit_value *check = block->append (create<jit_call> (jit_typeinfo::for_check, + control, iterator)); + block->append (create<jit_cond_branch> (check, body, tail)); + block = body; + + // compute the syntactical iterator + jit_call *idx_rhs = create<jit_call> (jit_typeinfo::for_index, control, + iterator); + block->append (idx_rhs); + do_assign (cmd.left_hand_side (), idx_rhs); + + // do loop + tree_statement_list *pt_body = cmd.body (); + pt_body->accept (*this); + + if (breaking && continues.empty ()) + { + // WTF are you doing user? Every branch was a continue, why did you have + // a loop??? Users are silly people... + finish_breaks (tail, breaks); + append (tail); + block = tail; + return; + } + + // check our condition, continues jump to this block + jit_block *check_block = create<jit_block> ("for_check"); + append (check_block); + + if (! breaking) + block->append (create<jit_branch> (check_block)); + finish_breaks (check_block, continues); + + block = check_block; + const jit_operation& add_fn = jit_typeinfo::binary_op (octave_value::op_add); + jit_value *one = create<jit_const_index> (1); + jit_call *iter_inc = create<jit_call> (add_fn, iterator, one); + block->append (iter_inc); + block->append (create<jit_assign> (iterator, iter_inc)); + check = block->append (create<jit_call> (jit_typeinfo::for_check, control, + iterator)); + block->append (create<jit_cond_branch> (check, body, tail)); + + // breaks will go to our tail + append (tail); + finish_breaks (tail, breaks); + block = tail; +} + +void +jit_convert::visit_complex_for_command (tree_complex_for_command&) +{ + fail (); +} + +void +jit_convert::visit_octave_user_script (octave_user_script&) +{ + fail (); +} + +void +jit_convert::visit_octave_user_function (octave_user_function&) +{ + fail (); +} + +void +jit_convert::visit_octave_user_function_header (octave_user_function&) +{ + fail (); +} + +void +jit_convert::visit_octave_user_function_trailer (octave_user_function&) +{ + fail (); +} + +void +jit_convert::visit_function_def (tree_function_def&) +{ + fail (); +} + +void +jit_convert::visit_identifier (tree_identifier& ti) +{ + result = get_variable (ti.name ()); +} + +void +jit_convert::visit_if_clause (tree_if_clause&) +{ + fail (); +} + +void +jit_convert::visit_if_command (tree_if_command& cmd) +{ + tree_if_command_list *lst = cmd.cmd_list (); + assert (lst); // jwe: Can this be null? + lst->accept (*this); +} + +void +jit_convert::visit_if_command_list (tree_if_command_list& lst) +{ + tree_if_clause *last = lst.back (); + size_t last_else = static_cast<size_t> (last->is_else_clause ()); + + // entry_blocks represents the block you need to enter in order to execute + // the condition check for the ith clause. For the else, it is simple the + // else body. If there is no else body, then it is padded with the tail + std::vector<jit_block *> entry_blocks (lst.size () + 1 - last_else); + std::vector<jit_block *> branch_blocks (lst.size (), 0); // final blocks + entry_blocks[0] = block; + + // we need to construct blocks first, because they have jumps to eachother + tree_if_command_list::iterator iter = lst.begin (); + ++iter; + for (size_t i = 1; iter != lst.end (); ++iter, ++i) + { + tree_if_clause *tic = *iter; + if (tic->is_else_clause ()) + entry_blocks[i] = create<jit_block> ("else"); + else + entry_blocks[i] = create<jit_block> ("ifelse_cond"); + } + + jit_block *tail = create<jit_block> ("if_tail"); + if (! last_else) + entry_blocks[entry_blocks.size () - 1] = tail; + + size_t num_incomming = 0; // number of incomming blocks to our tail + iter = lst.begin (); + for (size_t i = 0; iter != lst.end (); ++iter, ++i) + { + tree_if_clause *tic = *iter; + block = entry_blocks[i]; + assert (block); + + if (i) // the first block is prev_block, so it has already been added + append (entry_blocks[i]); + + if (! tic->is_else_clause ()) + { + tree_expression *expr = tic->condition (); + jit_value *cond = visit (expr); + jit_call *check = create_checked (&jit_typeinfo::logically_true, + cond); + jit_block *body = create<jit_block> (i == 0 ? "if_body" + : "ifelse_body"); + append (body); + + jit_instruction *br = create<jit_cond_branch> (check, body, + entry_blocks[i + 1]); + block->append (br); + block = body; + } + + tree_statement_list *stmt_lst = tic->commands (); + assert (stmt_lst); // jwe: Can this be null? + stmt_lst->accept (*this); + + if (breaking) + breaking = false; + else + { + ++num_incomming; + block->append (create<jit_branch> (tail)); + } + } + + if (num_incomming || ! last_else) + { + append (tail); + block = tail; + } + else + // every branch broke, so we don't have a tail + breaking = true; +} + +void +jit_convert::visit_index_expression (tree_index_expression& exp) +{ + std::pair<jit_value *, jit_value *> res = resolve (exp); + jit_value *object = res.first; + jit_value *index = res.second; + + result = create_checked (jit_typeinfo::paren_subsref, object, index); +} + +void +jit_convert::visit_matrix (tree_matrix&) +{ + fail (); +} + +void +jit_convert::visit_cell (tree_cell&) +{ + fail (); +} + +void +jit_convert::visit_multi_assignment (tree_multi_assignment&) +{ + fail (); +} + +void +jit_convert::visit_no_op_command (tree_no_op_command&) +{ + fail (); +} + +void +jit_convert::visit_constant (tree_constant& tc) +{ + octave_value v = tc.rvalue1 (); + if (v.is_real_scalar () && v.is_double_type ()) + { + double dv = v.double_value (); + result = create<jit_const_scalar> (dv); + } + else if (v.is_range ()) + { + Range rv = v.range_value (); + result = create<jit_const_range> (rv); + } + else if (v.is_complex_scalar ()) + { + Complex cv = v.complex_value (); + result = create<jit_const_complex> (cv); + } + else + fail ("Unknown constant"); +} + +void +jit_convert::visit_fcn_handle (tree_fcn_handle&) +{ + fail (); +} + +void +jit_convert::visit_parameter_list (tree_parameter_list&) +{ + fail (); +} + +void +jit_convert::visit_postfix_expression (tree_postfix_expression&) +{ + fail (); +} + +void +jit_convert::visit_prefix_expression (tree_prefix_expression&) +{ + fail (); +} + +void +jit_convert::visit_return_command (tree_return_command&) +{ + fail (); +} + +void +jit_convert::visit_return_list (tree_return_list&) +{ + fail (); +} + +void +jit_convert::visit_simple_assignment (tree_simple_assignment& tsa) +{ + if (tsa.op_type () != octave_value::op_asn_eq) + fail ("Unsupported assign"); + + // resolve rhs + tree_expression *rhs = tsa.right_hand_side (); + jit_value *rhsv = visit (rhs); + + result = do_assign (tsa.left_hand_side (), rhsv); +} + +void +jit_convert::visit_statement (tree_statement& stmt) +{ + tree_command *cmd = stmt.command (); + tree_expression *expr = stmt.expression (); + + if (cmd) + visit (cmd); + else + { + // stolen from tree_evaluator::visit_statement + bool do_bind_ans = false; + + if (expr->is_identifier ()) + { + tree_identifier *id = dynamic_cast<tree_identifier *> (expr); + + do_bind_ans = (! id->is_variable ()); + } + else + do_bind_ans = (! expr->is_assignment_expression ()); + + jit_value *expr_result = visit (expr); + + if (do_bind_ans) + do_assign ("ans", expr_result, expr->print_result ()); + else if (expr->is_identifier () && expr->print_result ()) + { + // FIXME: ugly hack, we need to come up with a way to pass + // nargout to visit_identifier + const jit_operation& fn = jit_typeinfo::print_value (); + jit_const_string *name = create<jit_const_string> (expr->name ()); + block->append (create<jit_call> (fn, name, expr_result)); + } + } +} + +void +jit_convert::visit_statement_list (tree_statement_list& lst) +{ + for (tree_statement_list::iterator iter = lst.begin (); iter != lst.end(); + ++iter) + { + tree_statement *elt = *iter; + // jwe: Can this ever be null? + assert (elt); + elt->accept (*this); + + if (breaking) + break; + } +} + +void +jit_convert::visit_switch_case (tree_switch_case&) +{ + fail (); +} + +void +jit_convert::visit_switch_case_list (tree_switch_case_list&) +{ + fail (); +} + +void +jit_convert::visit_switch_command (tree_switch_command&) +{ + fail (); +} + +void +jit_convert::visit_try_catch_command (tree_try_catch_command&) +{ + fail (); +} + +void +jit_convert::visit_unwind_protect_command (tree_unwind_protect_command&) +{ + fail (); +} + +void +jit_convert::visit_while_command (tree_while_command& wc) +{ + assert (! breaking); + unwind_protect prot; + prot.protect_var (breaks); + prot.protect_var (continues); + prot.protect_var (breaking); + breaks.clear (); + continues.clear (); + + jit_block *cond_check = create<jit_block> ("while_cond_check"); + block->append (create<jit_branch> (cond_check)); + append (cond_check); + block = cond_check; + + tree_expression *expr = wc.condition (); + assert (expr && "While expression can not be null"); + jit_value *check = visit (expr); + check = create_checked (&jit_typeinfo::logically_true, check); + + jit_block *body = create<jit_block> ("while_body"); + append (body); + + jit_block *tail = create<jit_block> ("while_tail"); + block->append (create<jit_cond_branch> (check, body, tail)); + block = body; + + tree_statement_list *loop_body = wc.body (); + if (loop_body) + loop_body->accept (*this); + + finish_breaks (tail, breaks); + finish_breaks (cond_check, continues); + + if (! breaking) + block->append (create<jit_branch> (cond_check)); + + append (tail); + block = tail; +} + +void +jit_convert::visit_do_until_command (tree_do_until_command&) +{ + fail (); +} + +void +jit_convert::append (jit_block *ablock) +{ + blocks.push_back (ablock); + ablock->stash_location (--blocks.end ()); +} + +void +jit_convert::insert_before (block_iterator iter, jit_block *ablock) +{ + iter = blocks.insert (iter, ablock); + ablock->stash_location (iter); +} + +void +jit_convert::insert_after (block_iterator iter, jit_block *ablock) +{ + ++iter; + insert_before (iter, ablock); +} + +jit_variable * +jit_convert::get_variable (const std::string& vname) +{ + vmap_t::iterator iter; + iter = vmap.find (vname); + if (iter != vmap.end ()) + return iter->second; + + jit_variable *var = create<jit_variable> (vname); + octave_value val = symbol_table::find (vname); + jit_type *type = jit_typeinfo::type_of (val); + jit_extract_argument *extract; + extract = create<jit_extract_argument> (type, var); + entry_block->prepend (extract); + + return vmap[vname] = var; +} + +std::pair<jit_value *, jit_value *> +jit_convert::resolve (tree_index_expression& exp) +{ + std::string type = exp.type_tags (); + if (! (type.size () == 1 && type[0] == '(')) + fail ("Unsupported index operation"); + + std::list<tree_argument_list *> args = exp.arg_lists (); + if (args.size () != 1) + fail ("Bad number of arguments in tree_index_expression"); + + tree_argument_list *arg_list = args.front (); + if (! arg_list) + fail ("null argument list"); + + if (arg_list->size () != 1) + fail ("Bad number of arguments in arg_list"); + + tree_expression *tree_object = exp.expression (); + jit_value *object = visit (tree_object); + tree_expression *arg0 = arg_list->front (); + jit_value *index = visit (arg0); + + return std::make_pair (object, index); +} + +jit_value * +jit_convert::do_assign (tree_expression *exp, jit_value *rhs, bool artificial) +{ + if (! exp) + fail ("NULL lhs in assign"); + + if (isa<tree_identifier> (exp)) + return do_assign (exp->name (), rhs, exp->print_result (), artificial); + else if (tree_index_expression *idx + = dynamic_cast<tree_index_expression *> (exp)) + { + std::pair<jit_value *, jit_value *> res = resolve (*idx); + jit_value *object = res.first; + jit_value *index = res.second; + jit_call *new_object = create<jit_call> (&jit_typeinfo::paren_subsasgn, + object, index, rhs); + block->append (new_object); + do_assign (idx->expression (), new_object, true); + create_check (new_object); + + // FIXME: Will not work for values that must be release/grabed + return rhs; + } + else + fail ("Unsupported assignment"); +} + +jit_value * +jit_convert::do_assign (const std::string& lhs, jit_value *rhs, + bool print, bool artificial) +{ + jit_variable *var = get_variable (lhs); + jit_assign *assign = block->append (create<jit_assign> (var, rhs)); + + if (artificial) + assign->mark_artificial (); + + if (print) + { + const jit_operation& print_fn = jit_typeinfo::print_value (); + jit_const_string *name = create<jit_const_string> (lhs); + block->append (create<jit_call> (print_fn, name, var)); + } + + return var; +} + +jit_value * +jit_convert::visit (tree& tee) +{ + result = 0; + tee.accept (*this); + + jit_value *ret = result; + result = 0; + return ret; +} + +void +jit_convert::append_users_term (jit_terminator *term) +{ + for (size_t i = 0; i < term->successor_count (); ++i) + { + if (term->alive (i)) + { + jit_block *succ = term->successor (i); + for (jit_block::iterator iter = succ->begin (); iter != succ->end () + && isa<jit_phi> (*iter); ++iter) + push_worklist (*iter); + + jit_terminator *sterm = succ->terminator (); + if (sterm) + push_worklist (sterm); + } + } +} + +void +jit_convert::merge_blocks (void) +{ + std::vector<jit_block *> dead; + for (block_list::iterator iter = blocks.begin (); iter != blocks.end (); + ++iter) + { + jit_block *b = *iter; + jit_block *merged = b->maybe_merge (); + + if (merged) + { + if (merged == final_block) + final_block = b; + + if (merged == entry_block) + entry_block = b; + + dead.push_back (merged); + } + } + + for (size_t i = 0; i < dead.size (); ++i) + blocks.erase (dead[i]->location ()); +} + +void +jit_convert::construct_ssa (void) +{ + merge_blocks (); + final_block->label (); + final_block->compute_idom (entry_block); + entry_block->compute_df (); + entry_block->create_dom_tree (); + + // insert phi nodes where needed, this is done on a per variable basis + for (vmap_t::iterator iter = vmap.begin (); iter != vmap.end (); ++iter) + { + jit_block::df_set visited, added_phi; + std::list<jit_block *> ssa_worklist; + iter->second->use_blocks (visited); + ssa_worklist.insert (ssa_worklist.begin (), visited.begin (), + visited.end ()); + + while (ssa_worklist.size ()) + { + jit_block *b = ssa_worklist.front (); + ssa_worklist.pop_front (); + + for (jit_block::df_iterator diter = b->df_begin (); + diter != b->df_end (); ++diter) + { + jit_block *dblock = *diter; + if (! added_phi.count (dblock)) + { + jit_phi *phi = create<jit_phi> (iter->second, + dblock->use_count ()); + dblock->prepend (phi); + added_phi.insert (dblock); + } + + if (! visited.count (dblock)) + { + ssa_worklist.push_back (dblock); + visited.insert (dblock); + } + } + } + } + + do_construct_ssa (*entry_block, entry_block->visit_count ()); +} + +void +jit_convert::do_construct_ssa (jit_block& ablock, size_t avisit_count) +{ + if (ablock.visited (avisit_count)) + return; + + // replace variables with their current SSA value + for (jit_block::iterator iter = ablock.begin (); iter != ablock.end (); ++iter) + { + jit_instruction *instr = *iter; + instr->construct_ssa (); + instr->push_variable (); + } + + // finish phi nodes of successors + for (size_t i = 0; i < ablock.successor_count (); ++i) + { + jit_block *finish = ablock.successor (i); + + for (jit_block::iterator iter = finish->begin (); iter != finish->end () + && isa<jit_phi> (*iter);) + { + jit_phi *phi = static_cast<jit_phi *> (*iter); + jit_variable *var = phi->dest (); + if (var->has_top ()) + { + phi->add_incomming (&ablock, var->top ()); + ++iter; + } + else + { + // temporaries may have extranious phi nodes which can be removed + assert (! phi->use_count ()); + assert (var->name ().size () && var->name ()[0] == '#'); + iter = finish->remove (iter); + } + } + } + + for (size_t i = 0; i < ablock.dom_successor_count (); ++i) + do_construct_ssa (*ablock.dom_successor (i), avisit_count); + + ablock.pop_all (); +} + +void +jit_convert::remove_dead () +{ + block_list::iterator biter; + for (biter = blocks.begin (); biter != blocks.end (); ++biter) + { + jit_block *b = *biter; + if (b->alive ()) + { + for (jit_block::iterator iter = b->begin (); iter != b->end () + && isa<jit_phi> (*iter);) + { + jit_phi *phi = static_cast<jit_phi *> (*iter); + if (phi->prune ()) + iter = b->remove (iter); + else + ++iter; + } + } + } + + for (biter = blocks.begin (); biter != blocks.end ();) + { + jit_block *b = *biter; + if (b->alive ()) + { + // FIXME: A special case for jit_error_check, if we generalize to + // we will need to change! + jit_terminator *term = b->terminator (); + if (term && term->successor_count () == 2 && ! term->alive (0)) + { + jit_block *succ = term->successor (1); + term->remove (); + jit_branch *abreak = b->append (create<jit_branch> (succ)); + abreak->infer (); + } + + ++biter; + } + else + { + jit_terminator *term = b->terminator (); + if (term) + term->remove (); + biter = blocks.erase (biter); + } + } +} + +void +jit_convert::place_releases (void) +{ + std::set<jit_value *> temporaries; + for (block_list::iterator iter = blocks.begin (); iter != blocks.end (); + ++iter) + { + jit_block& ablock = **iter; + if (ablock.id () != jit_block::NO_ID) + { + release_temp (ablock, temporaries); + release_dead_phi (ablock); + } + } +} + +void +jit_convert::release_temp (jit_block& ablock, std::set<jit_value *>& temp) +{ + for (jit_block::iterator iter = ablock.begin (); iter != ablock.end (); + ++iter) + { + jit_instruction *instr = *iter; + + // check for temporaries that require release and live across + // multiple blocks + if (instr->needs_release ()) + { + jit_block *fu_block = instr->first_use_block (); + if (fu_block && fu_block != &ablock) + temp.insert (instr); + } + + if (isa<jit_call> (instr)) + { + // place releases for temporary arguments + for (size_t i = 0; i < instr->argument_count (); ++i) + { + jit_value *arg = instr->argument (i); + if (arg->needs_release ()) + { + jit_call *release = create<jit_call> (&jit_typeinfo::release, + arg); + release->infer (); + ablock.insert_after (iter, release); + ++iter; + temp.erase (arg); + } + } + } + } + + if (! temp.size () || ! isa<jit_error_check> (ablock.terminator ())) + return; + + // FIXME: If we support try/catch or unwind_protect final_block may not be the + // destination + jit_block *split = ablock.maybe_split (*this, final_block); + jit_terminator *term = split->terminator (); + for (std::set<jit_value *>::const_iterator iter = temp.begin (); + iter != temp.end (); ++iter) + { + jit_value *value = *iter; + jit_call *release = create<jit_call> (&jit_typeinfo::release, value); + split->insert_before (term, release); + release->infer (); + } +} + +void +jit_convert::release_dead_phi (jit_block& ablock) +{ + jit_block::iterator iter = ablock.begin (); + while (iter != ablock.end () && isa<jit_phi> (*iter)) + { + jit_phi *phi = static_cast<jit_phi *> (*iter); + ++iter; + + jit_use *use = phi->first_use (); + if (phi->use_count () == 1 && isa<jit_assign> (use->user ())) + { + // instead of releasing on assign, release on all incomming branches, + // this can get rid of casts inside loops + for (size_t i = 0; i < phi->argument_count (); ++i) + { + jit_value *arg = phi->argument (i); + jit_block *inc = phi->incomming (i); + jit_block *split = inc->maybe_split (*this, ablock); + jit_terminator *term = split->terminator (); + jit_call *release = create<jit_call> (jit_typeinfo::release, arg); + release->infer (); + split->insert_before (term, release); + } + + phi->replace_with (0); + phi->remove (); + } + } +} + +void +jit_convert::simplify_phi (void) +{ + for (block_list::iterator biter = blocks.begin (); biter != blocks.end (); + ++biter) + { + jit_block &ablock = **biter; + for (jit_block::iterator iter = ablock.begin (); iter != ablock.end () + && isa<jit_phi> (*iter); ++iter) + simplify_phi (*static_cast<jit_phi *> (*iter)); + } +} + +void +jit_convert::simplify_phi (jit_phi& phi) +{ + jit_block& pblock = *phi.parent (); + const jit_operation& cast_fn = jit_typeinfo::cast (phi.type ()); + jit_variable *dest = phi.dest (); + for (size_t i = 0; i < phi.argument_count (); ++i) + { + jit_value *arg = phi.argument (i); + if (arg->type () != phi.type ()) + { + jit_block *pred = phi.incomming (i); + jit_block *split = pred->maybe_split (*this, pblock); + jit_terminator *term = split->terminator (); + jit_instruction *cast = create<jit_call> (cast_fn, arg); + jit_assign *assign = create<jit_assign> (dest, cast); + + split->insert_before (term, cast); + split->insert_before (term, assign); + cast->infer (); + assign->infer (); + phi.stash_argument (i, assign); + } + } +} + +void +jit_convert::finish_breaks (jit_block *dest, const block_list& lst) +{ + for (block_list::const_iterator iter = lst.begin (); iter != lst.end (); + ++iter) + { + jit_block *b = *iter; + b->append (create<jit_branch> (dest)); + } +} + +// -------------------- jit_convert::convert_llvm -------------------- +llvm::Function * +jit_convert::convert_llvm::convert (llvm::Module *module, + const std::vector<std::pair< std::string, bool> >& args, + const std::list<jit_block *>& blocks, + const std::list<jit_value *>& constants) +{ + jit_type *any = jit_typeinfo::get_any (); + + // argument is an array of octave_base_value*, or octave_base_value** + llvm::Type *arg_type = any->to_llvm (); // this is octave_base_value* + arg_type = arg_type->getPointerTo (); + llvm::FunctionType *ft = llvm::FunctionType::get (llvm::Type::getVoidTy (context), + arg_type, false); + function = llvm::Function::Create (ft, llvm::Function::ExternalLinkage, + "foobar", module); + + try + { + prelude = llvm::BasicBlock::Create (context, "prelude", function); + builder.SetInsertPoint (prelude); + + llvm::Value *arg = function->arg_begin (); + for (size_t i = 0; i < args.size (); ++i) + { + llvm::Value *loaded_arg = builder.CreateConstInBoundsGEP1_32 (arg, i); + arguments[args[i].first] = loaded_arg; + } + + std::list<jit_block *>::const_iterator biter; + for (biter = blocks.begin (); biter != blocks.end (); ++biter) + { + jit_block *jblock = *biter; + llvm::BasicBlock *block = llvm::BasicBlock::Create (context, + jblock->name (), + function); + jblock->stash_llvm (block); + } + + jit_block *first = *blocks.begin (); + builder.CreateBr (first->to_llvm ()); + + // constants aren't in the IR, we visit those first + for (std::list<jit_value *>::const_iterator iter = constants.begin (); + iter != constants.end (); ++iter) + if (! isa<jit_instruction> (*iter)) + visit (*iter); + + // convert all instructions + for (biter = blocks.begin (); biter != blocks.end (); ++biter) + visit (*biter); + + // now finish phi nodes + for (biter = blocks.begin (); biter != blocks.end (); ++biter) + { + jit_block& block = **biter; + for (jit_block::iterator piter = block.begin (); + piter != block.end () && isa<jit_phi> (*piter); ++piter) + { + jit_instruction *phi = *piter; + finish_phi (static_cast<jit_phi *> (phi)); + } + } + + jit_block *last = blocks.back (); + builder.SetInsertPoint (last->to_llvm ()); + builder.CreateRetVoid (); + } catch (const jit_fail_exception& e) + { + function->eraseFromParent (); + throw; + } + + return function; +} + +void +jit_convert::convert_llvm::finish_phi (jit_phi *phi) +{ + llvm::PHINode *llvm_phi = phi->to_llvm (); + for (size_t i = 0; i < phi->argument_count (); ++i) + { + llvm::BasicBlock *pred = phi->incomming_llvm (i); + llvm_phi->addIncoming (phi->argument_llvm (i), pred); + } +} + +void +jit_convert::convert_llvm::visit (jit_const_string& cs) +{ + cs.stash_llvm (builder.CreateGlobalStringPtr (cs.value ())); +} + +void +jit_convert::convert_llvm::visit (jit_const_bool& cb) +{ + cb.stash_llvm (llvm::ConstantInt::get (cb.type_llvm (), cb.value ())); +} + +void +jit_convert::convert_llvm::visit (jit_const_scalar& cs) +{ + cs.stash_llvm (llvm::ConstantFP::get (cs.type_llvm (), cs.value ())); +} + +void +jit_convert::convert_llvm::visit (jit_const_complex& cc) +{ + llvm::Type *scalar_t = jit_typeinfo::get_scalar_llvm (); + llvm::Constant *values[2]; + Complex value = cc.value (); + values[0] = llvm::ConstantFP::get (scalar_t, value.real ()); + values[1] = llvm::ConstantFP::get (scalar_t, value.imag ()); + cc.stash_llvm (llvm::ConstantVector::get (values)); +} + +void jit_convert::convert_llvm::visit (jit_const_index& ci) +{ + ci.stash_llvm (llvm::ConstantInt::get (ci.type_llvm (), ci.value ())); +} + +void +jit_convert::convert_llvm::visit (jit_const_range& cr) +{ + llvm::StructType *stype = llvm::cast<llvm::StructType>(cr.type_llvm ()); + llvm::Type *scalar_t = jit_typeinfo::get_scalar_llvm (); + llvm::Type *idx = jit_typeinfo::get_index_llvm (); + const jit_range& rng = cr.value (); + + llvm::Constant *constants[4]; + constants[0] = llvm::ConstantFP::get (scalar_t, rng.base); + constants[1] = llvm::ConstantFP::get (scalar_t, rng.limit); + constants[2] = llvm::ConstantFP::get (scalar_t, rng.inc); + constants[3] = llvm::ConstantInt::get (idx, rng.nelem); + + llvm::Value *as_llvm; + as_llvm = llvm::ConstantStruct::get (stype, + llvm::makeArrayRef (constants, 4)); + cr.stash_llvm (as_llvm); +} + +void +jit_convert::convert_llvm::visit (jit_block& b) +{ + llvm::BasicBlock *block = b.to_llvm (); + builder.SetInsertPoint (block); + for (jit_block::iterator iter = b.begin (); iter != b.end (); ++iter) + visit (*iter); +} + +void +jit_convert::convert_llvm::visit (jit_branch& b) +{ + b.stash_llvm (builder.CreateBr (b.successor_llvm ())); +} + +void +jit_convert::convert_llvm::visit (jit_cond_branch& cb) +{ + llvm::Value *cond = cb.cond_llvm (); + llvm::Value *br; + br = builder.CreateCondBr (cond, cb.successor_llvm (0), + cb.successor_llvm (1)); + cb.stash_llvm (br); +} + +void +jit_convert::convert_llvm::visit (jit_call& call) +{ + llvm::Value *ret = create_call (call.overload (), call.arguments ()); + call.stash_llvm (ret); +} + +void +jit_convert::convert_llvm::visit (jit_extract_argument& extract) +{ + llvm::Value *arg = arguments[extract.name ()]; + assert (arg); + arg = builder.CreateLoad (arg); + + jit_value *jarg = jthis.create<jit_argument> (jit_typeinfo::get_any (), arg); + extract.stash_llvm (create_call (extract.overload (), jarg)); +} + +void +jit_convert::convert_llvm::visit (jit_store_argument& store) +{ + llvm::Value *arg_value = create_call (store.overload (), store.result ()); + + llvm::Value *arg = arguments[store.name ()]; + store.stash_llvm (builder.CreateStore (arg_value, arg)); +} + +void +jit_convert::convert_llvm::visit (jit_phi& phi) +{ + // we might not have converted all incoming branches, so we don't + // set incomming branches now + llvm::PHINode *node = llvm::PHINode::Create (phi.type_llvm (), + phi.argument_count ()); + builder.Insert (node); + phi.stash_llvm (node); +} + +void +jit_convert::convert_llvm::visit (jit_variable&) +{ + fail ("ERROR: SSA construction should remove all variables"); +} + +void +jit_convert::convert_llvm::visit (jit_error_check& check) +{ + llvm::Value *cond = jit_typeinfo::insert_error_check (); + llvm::Value *br = builder.CreateCondBr (cond, check.successor_llvm (0), + check.successor_llvm (1)); + check.stash_llvm (br); +} + +void +jit_convert::convert_llvm::visit (jit_assign& assign) +{ + assign.stash_llvm (assign.src ()->to_llvm ()); + + if (assign.artificial ()) + return; + + jit_value *new_value = assign.src (); + if (isa<jit_assign_base> (new_value)) + { + const jit_operation::overload& ol + = jit_typeinfo::get_grab (new_value->type ()); + if (ol.function) + assign.stash_llvm (create_call (ol, new_value)); + } + + jit_value *overwrite = assign.overwrite (); + if (isa<jit_assign_base> (overwrite)) + { + const jit_operation::overload& ol + = jit_typeinfo::get_release (overwrite->type ()); + if (ol.function) + create_call (ol, overwrite); + } +} + +void +jit_convert::convert_llvm::visit (jit_argument&) +{} + +llvm::Value * +jit_convert::convert_llvm::create_call (const jit_operation::overload& ol, + const std::vector<jit_value *>& jargs) +{ + llvm::IRBuilder<> alloca_inserter (prelude, prelude->begin ()); + + llvm::Function *fun = ol.function; + if (! fun) + fail ("Missing overload"); + + const llvm::Function::ArgumentListType& alist = fun->getArgumentList (); + size_t nargs = alist.size (); + bool sret = false; + if (nargs != jargs.size ()) + { + // first argument is the structure return value + assert (nargs == jargs.size () + 1); + sret = true; + } + + std::vector<llvm::Value *> args (nargs); + llvm::Function::arg_iterator llvm_arg = fun->arg_begin (); + if (sret) + { + args[0] = alloca_inserter.CreateAlloca (ol.result->to_llvm ()); + ++llvm_arg; + } + + for (size_t i = 0; i < jargs.size (); ++i, ++llvm_arg) + { + llvm::Value *arg = jargs[i]->to_llvm (); + llvm::Type *arg_type = arg->getType (); + llvm::Type *llvm_arg_type = llvm_arg->getType (); + + if (arg_type == llvm_arg_type) + args[i + sret] = arg; + else + { + // pass structure by pointer + assert (arg_type->getPointerTo () == llvm_arg_type); + llvm::Value *new_arg = alloca_inserter.CreateAlloca (arg_type); + builder.CreateStore (arg, new_arg); + args[i + sret] = new_arg; + } + } + + llvm::Value *llvm_call = builder.CreateCall (fun, args); + return sret ? builder.CreateLoad (args[0]) : llvm_call; +} + +llvm::Value * +jit_convert::convert_llvm::create_call (const jit_operation::overload& ol, + const std::vector<jit_use>& uses) +{ + std::vector<jit_value *> values (uses.size ()); + for (size_t i = 0; i < uses.size (); ++i) + values[i] = uses[i].value (); + + return create_call (ol, values); +} + +// -------------------- tree_jit -------------------- + +tree_jit::tree_jit (void) : module (0), engine (0) +{ +} + +tree_jit::~tree_jit (void) +{} + +bool +tree_jit::execute (tree_simple_for_command& cmd) +{ + if (! initialize ()) + return false; + + jit_info *info = cmd.get_info (); + if (! info || ! info->match ()) + { + delete info; + info = new jit_info (*this, cmd); + cmd.stash_info (info); + } + + return info->execute (); +} + +bool +tree_jit::initialize (void) +{ + if (engine) + return true; + + if (! module) + { + llvm::InitializeNativeTarget (); + module = new llvm::Module ("octave", context); + } + + // sometimes this fails pre main + engine = llvm::ExecutionEngine::createJIT (module); + + if (! engine) + return false; + + module_pass_manager = new llvm::PassManager (); + module_pass_manager->add (llvm::createAlwaysInlinerPass ()); + + pass_manager = new llvm::FunctionPassManager (module); + pass_manager->add (new llvm::TargetData(*engine->getTargetData ())); + pass_manager->add (llvm::createBasicAliasAnalysisPass ()); + pass_manager->add (llvm::createPromoteMemoryToRegisterPass ()); + pass_manager->add (llvm::createInstructionCombiningPass ()); + pass_manager->add (llvm::createReassociatePass ()); + pass_manager->add (llvm::createGVNPass ()); + pass_manager->add (llvm::createCFGSimplificationPass ()); + pass_manager->doInitialization (); + + jit_typeinfo::initialize (module, engine); + + return true; +} + + +void +tree_jit::optimize (llvm::Function *fn) +{ + module_pass_manager->run (*module); + pass_manager->run (*fn); + +#ifdef OCTAVE_JIT_DEBUG + std::string error; + llvm::raw_fd_ostream fout ("test.bc", error, + llvm::raw_fd_ostream::F_Binary); + llvm::WriteBitcodeToFile (module, fout); +#endif +} + +// -------------------- jit_info -------------------- +jit_info::jit_info (tree_jit& tjit, tree& tee) + : engine (tjit.get_engine ()), llvm_function (0) +{ + try + { + jit_convert conv (tjit.get_module (), tee); + llvm_function = conv.get_function (); + arguments = conv.get_arguments (); + bounds = conv.get_bounds (); + } + catch (const jit_fail_exception& e) + { +#ifdef OCTAVE_JIT_DEBUG + if (e.known ()) + std::cout << "jit fail: " << e.what () << std::endl; +#endif + } + + if (! llvm_function) + { + function = 0; + return; + } + + tjit.optimize (llvm_function); + +#ifdef OCTAVE_JIT_DEBUG + std::cout << "-------------------- optimized llvm ir --------------------\n"; + llvm::raw_os_ostream llvm_cout (std::cout); + llvm_function->print (llvm_cout); + std::cout << std::endl; +#endif + + void *void_fn = engine->getPointerToFunction (llvm_function); + function = reinterpret_cast<jited_function> (void_fn); +} + +jit_info::~jit_info (void) +{ + if (llvm_function) + llvm_function->eraseFromParent (); +} + +bool +jit_info::execute (void) const +{ + if (! function) + return false; + + std::vector<octave_base_value *> real_arguments (arguments.size ()); + for (size_t i = 0; i < arguments.size (); ++i) + { + if (arguments[i].second) + { + octave_value ¤t = symbol_table::varref (arguments[i].first); + octave_base_value *obv = current.internal_rep (); + obv->grab (); + real_arguments[i] = obv; + current = octave_value (); + } + } + + function (&real_arguments[0]); + + for (size_t i = 0; i < arguments.size (); ++i) + symbol_table::varref (arguments[i].first) = real_arguments[i]; + + return true; +} + +bool +jit_info::match (void) const +{ + if (! function) + return true; + + for (size_t i = 0; i < bounds.size (); ++i) + { + const std::string& arg_name = bounds[i].second; + octave_value value = symbol_table::find (arg_name); + jit_type *type = jit_typeinfo::type_of (value); + + // FIXME: Check for a parent relationship + if (type != bounds[i].first) + return false; + } + + return true; +} +#endif
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/pt-jit.h Sun Jul 22 04:16:02 2012 +0200 @@ -0,0 +1,2358 @@ +/* + +Copyright (C) 2012 Max Brister <max@2bass.com> + +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/>. + +*/ + +#if !defined (octave_tree_jit_h) +#define octave_tree_jit_h 1 + +#ifdef HAVE_LLVM + +#include <list> +#include <map> +#include <set> +#include <stdexcept> +#include <vector> +#include <stack> + +#include "Array.h" +#include "Range.h" +#include "pt-walk.h" + +// -------------------- Current status -------------------- +// Simple binary operations (+-*/) on octave_scalar's (doubles) are optimized. +// a = 5; +// b = a * 5 + a; +// +// Indexing matrices with scalars works. +// +// if, elseif, else, break, continue, and for compile. Compilation is triggered +// at the start of a simple for loop. +// +// The octave low level IR is a linear IR, it works by converting everything to +// calls to jit_operations. This turns expressions like c = a + b into +// c = call binary+ (a, b) +// The jit_operations contain information about overloads for different types. +// For, example, if we know a and b are scalars, then c must also be a scalar. +// +// Support for function calls is in progress. Currently, calls to sin with a +// scalar argument will compile. +// +// TODO: +// 1. Function calls (In progress) +// 2. Cleanup/documentation +// 3. ... +// --------------------------------------------------------- + + +// we don't want to include llvm headers here, as they require +// __STDC_LIMIT_MACROS and __STDC_CONSTANT_MACROS be defined in the entire +// compilation unit +namespace llvm +{ + class Value; + class Module; + class FunctionPassManager; + class PassManager; + class ExecutionEngine; + class Function; + class BasicBlock; + class LLVMContext; + class Type; + class StructType; + class Twine; + class GlobalVariable; + class TerminatorInst; + class PHINode; +} + +class octave_base_value; +class octave_builtin; +class octave_value; +class tree; +class tree_expression; + +template <typename HOLDER_T, typename SUB_T> +class jit_internal_node; + +// jit_internal_list and jit_internal_node implement generic embedded doubly +// linked lists. List items extend from jit_internal_list, and can be placed +// in nodes of type jit_internal_node. We use CRTP twice. +template <typename LIST_T, typename NODE_T> +class +jit_internal_list +{ + friend class jit_internal_node<LIST_T, NODE_T>; +public: + jit_internal_list (void) : use_head (0), use_tail (0), muse_count (0) {} + + virtual ~jit_internal_list (void) + { + while (use_head) + use_head->stash_value (0); + } + + NODE_T *first_use (void) const { return use_head; } + + size_t use_count (void) const { return muse_count; } +private: + NODE_T *use_head; + NODE_T *use_tail; + size_t muse_count; +}; + +// a node for internal linked lists +template <typename LIST_T, typename NODE_T> +class +jit_internal_node +{ +public: + typedef jit_internal_list<LIST_T, NODE_T> jit_ilist; + + jit_internal_node (void) : mvalue (0), mnext (0), mprev (0) {} + + ~jit_internal_node (void) { remove (); } + + LIST_T *value (void) const { return mvalue; } + + void stash_value (LIST_T *avalue) + { + remove (); + + mvalue = avalue; + + if (mvalue) + { + jit_ilist *ilist = mvalue; + NODE_T *sthis = static_cast<NODE_T *> (this); + if (ilist->use_head) + { + ilist->use_tail->mnext = sthis; + mprev = ilist->use_tail; + } + else + ilist->use_head = sthis; + + ilist->use_tail = sthis; + ++ilist->muse_count; + } + } + + NODE_T *next (void) const { return mnext; } + + NODE_T *prev (void) const { return mprev; } +private: + void remove () + { + if (mvalue) + { + jit_ilist *ilist = mvalue; + if (mprev) + mprev->mnext = mnext; + else + // we are the use_head + ilist->use_head = mnext; + + if (mnext) + mnext->mprev = mprev; + else + // we are the use tail + ilist->use_tail = mprev; + + mnext = mprev = 0; + --ilist->muse_count; + mvalue = 0; + } + } + + LIST_T *mvalue; + NODE_T *mnext; + NODE_T *mprev; +}; + +// Use like: isa<jit_phi> (value) +// basically just a short cut type typing dyanmic_cast. +template <typename T, typename U> +bool isa (U *value) +{ + return dynamic_cast<T *> (value); +} + +// jit_range is compatable with the llvm range structure +struct +jit_range +{ + jit_range (const Range& from) : base (from.base ()), limit (from.limit ()), + inc (from.inc ()), nelem (from.nelem ()) + {} + + operator Range () const + { + return Range (base, limit, inc); + } + + bool all_elements_are_ints () const; + + double base; + double limit; + double inc; + octave_idx_type nelem; +}; + +std::ostream& operator<< (std::ostream& os, const jit_range& rng); + +// jit_array is compatable with the llvm array/matrix structures +template <typename T, typename U> +struct +jit_array +{ + jit_array (T& from) : array (new T (from)) + { + update (); + } + + void update (void) + { + ref_count = array->jit_ref_count (); + slice_data = array->jit_slice_data () - 1; + slice_len = array->capacity (); + dimensions = array->jit_dimensions (); + } + + void update (T *aarray) + { + array = aarray; + update (); + } + + operator T () const + { + return *array; + } + + int *ref_count; + + U *slice_data; + octave_idx_type slice_len; + octave_idx_type *dimensions; + + T *array; +}; + +typedef jit_array<NDArray, double> jit_matrix; + +std::ostream& operator<< (std::ostream& os, const jit_matrix& mat); + +// Used to keep track of estimated (infered) types during JIT. This is a +// hierarchical type system which includes both concrete and abstract types. +// +// Current, we only support any and scalar types. If we can't figure out what +// type a variable is, we assign it the any type. This allows us to generate +// code even for the case of poor type inference. +class +jit_type +{ +public: + jit_type (const std::string& aname, jit_type *aparent, llvm::Type *allvm_type, + int aid) : + mname (aname), mparent (aparent), llvm_type (allvm_type), mid (aid), + mdepth (aparent ? aparent->mdepth + 1 : 0) + {} + + // a user readable type name + const std::string& name (void) const { return mname; } + + // a unique id for the type + int type_id (void) const { return mid; } + + // An abstract base type, may be null + jit_type *parent (void) const { return mparent; } + + // convert to an llvm type + llvm::Type *to_llvm (void) const { return llvm_type; } + + // how this type gets passed as a function argument + llvm::Type *to_llvm_arg (void) const; + + size_t depth (void) const { return mdepth; } +private: + std::string mname; + jit_type *mparent; + llvm::Type *llvm_type; + int mid; + size_t mdepth; +}; + +// seperate print function to allow easy printing if type is null +std::ostream& jit_print (std::ostream& os, jit_type *atype); + +// Keeps track of overloads for a builtin function. Used for both type inference +// and code generation. +class +jit_operation +{ +public: + struct + overload + { + overload (void) : function (0), can_error (false), result (0) {} + +#define ASSIGN_ARG(i) arguments[i] = arg ## i; +#define OVERLOAD_CTOR(N) \ + overload (llvm::Function *f, bool e, jit_type *ret, \ + OCT_MAKE_DECL_LIST (jit_type *, arg, N)) \ + : function (f), can_error (e), result (ret), arguments (N) \ + { \ + OCT_ITERATE_MACRO (ASSIGN_ARG, N); \ + } + + OVERLOAD_CTOR (1) + OVERLOAD_CTOR (2) + OVERLOAD_CTOR (3) + +#undef ASSIGN_ARG +#undef OVERLOAD_CTOR + + overload (llvm::Function *f, bool e, jit_type *r, + const std::vector<jit_type *>& aarguments) + : function (f), can_error (e), result (r), arguments (aarguments) + {} + + llvm::Function *function; + bool can_error; + jit_type *result; + std::vector<jit_type*> arguments; + }; + + void add_overload (const overload& func) + { + add_overload (func, func.arguments); + } + +#define ADD_OVERLOAD(N) \ + void add_overload (llvm::Function *f, bool e, jit_type *ret, \ + OCT_MAKE_DECL_LIST (jit_type *, arg, N)) \ + { \ + overload ol (f, e, ret, OCT_MAKE_ARG_LIST (arg, N)); \ + add_overload (ol); \ + } + + ADD_OVERLOAD (1); + ADD_OVERLOAD (2); + ADD_OVERLOAD (3); + +#undef ADD_OVERLOAD + + void add_overload (llvm::Function *f, bool e, jit_type *r, + const std::vector<jit_type *>& args) + { + overload ol (f, e, r, args); + add_overload (ol); + } + + void add_overload (const overload& func, + const std::vector<jit_type*>& args); + + const overload& get_overload (const std::vector<jit_type *>& types) const; + + const overload& get_overload (jit_type *arg0) const + { + std::vector<jit_type *> types (1); + types[0] = arg0; + return get_overload (types); + } + + const overload& get_overload (jit_type *arg0, jit_type *arg1) const + { + std::vector<jit_type *> types (2); + types[0] = arg0; + types[1] = arg1; + return get_overload (types); + } + + jit_type *get_result (const std::vector<jit_type *>& types) const + { + const overload& temp = get_overload (types); + return temp.result; + } + + jit_type *get_result (jit_type *arg0, jit_type *arg1) const + { + const overload& temp = get_overload (arg0, arg1); + return temp.result; + } + + const std::string& name (void) const { return mname; } + + void stash_name (const std::string& aname) { mname = aname; } +private: + Array<octave_idx_type> to_idx (const std::vector<jit_type*>& types) const; + + std::vector<Array<overload> > overloads; + + std::string mname; +}; + +// Get information and manipulate jit types. +class +jit_typeinfo +{ +public: + static void initialize (llvm::Module *m, llvm::ExecutionEngine *e); + + static jit_type *join (jit_type *lhs, jit_type *rhs) + { + return instance->do_join (lhs, rhs); + } + + static jit_type *get_any (void) { return instance->any; } + + static jit_type *get_matrix (void) { return instance->matrix; } + + static jit_type *get_scalar (void) { return instance->scalar; } + + static llvm::Type *get_scalar_llvm (void) + { return instance->scalar->to_llvm (); } + + static jit_type *get_range (void) { return instance->range; } + + static jit_type *get_string (void) { return instance->string; } + + static jit_type *get_bool (void) { return instance->boolean; } + + static jit_type *get_index (void) { return instance->index; } + + static llvm::Type *get_index_llvm (void) + { return instance->index->to_llvm (); } + + static jit_type *get_complex (void) { return instance->complex; } + + static jit_type *type_of (const octave_value& ov) + { + return instance->do_type_of (ov); + } + + static const jit_operation& binary_op (int op) + { + return instance->do_binary_op (op); + } + + static const jit_operation& grab (void) { return instance->grab_fn; } + + static const jit_operation::overload& get_grab (jit_type *type) + { + return instance->grab_fn.get_overload (type); + } + + static const jit_operation& release (void) + { + return instance->release_fn; + } + + static const jit_operation::overload& get_release (jit_type *type) + { + return instance->release_fn.get_overload (type); + } + + static const jit_operation& print_value (void) + { + return instance->print_fn; + } + + static const jit_operation& for_init (void) + { + return instance->for_init_fn; + } + + static const jit_operation& for_check (void) + { + return instance->for_check_fn; + } + + static const jit_operation& for_index (void) + { + return instance->for_index_fn; + } + + static const jit_operation& make_range (void) + { + return instance->make_range_fn; + } + + static const jit_operation& paren_subsref (void) + { + return instance->paren_subsref_fn; + } + + static const jit_operation& paren_subsasgn (void) + { + return instance->paren_subsasgn_fn; + } + + static const jit_operation& logically_true (void) + { + return instance->logically_true_fn; + } + + static const jit_operation& cast (jit_type *result) + { + return instance->do_cast (result); + } + + static const jit_operation::overload& cast (jit_type *to, jit_type *from) + { + return instance->do_cast (to, from); + } + + static llvm::Value *insert_error_check (void) + { + return instance->do_insert_error_check (); + } +private: + jit_typeinfo (llvm::Module *m, llvm::ExecutionEngine *e); + + // FIXME: Do these methods really need to be in jit_typeinfo? + jit_type *do_join (jit_type *lhs, jit_type *rhs) + { + // empty case + if (! lhs) + return rhs; + + if (! rhs) + return lhs; + + // check for a shared parent + while (lhs != rhs) + { + if (lhs->depth () > rhs->depth ()) + lhs = lhs->parent (); + else if (lhs->depth () < rhs->depth ()) + rhs = rhs->parent (); + else + { + // we MUST have depth > 0 as any is the base type of everything + do + { + lhs = lhs->parent (); + rhs = rhs->parent (); + } + while (lhs != rhs); + } + } + + return lhs; + } + + jit_type *do_difference (jit_type *lhs, jit_type *) + { + // FIXME: Maybe we can do something smarter? + return lhs; + } + + jit_type *do_type_of (const octave_value &ov) const; + + const jit_operation& do_binary_op (int op) const + { + assert (static_cast<size_t>(op) < binary_ops.size ()); + return binary_ops[op]; + } + + const jit_operation& do_cast (jit_type *to) + { + static jit_operation null_function; + if (! to) + return null_function; + + size_t id = to->type_id (); + if (id >= casts.size ()) + return null_function; + return casts[id]; + } + + const jit_operation::overload& do_cast (jit_type *to, jit_type *from) + { + return do_cast (to).get_overload (from); + } + + jit_type *new_type (const std::string& name, jit_type *parent, + llvm::Type *llvm_type); + + + void add_print (jit_type *ty, void *call); + + void add_binary_op (jit_type *ty, int op, int llvm_op); + + void add_binary_icmp (jit_type *ty, int op, int llvm_op); + + void add_binary_fcmp (jit_type *ty, int op, int llvm_op); + + + llvm::Function *create_function (const llvm::Twine& name, llvm::Type *ret) + { + std::vector<llvm::Type *> args; + return create_function (name, ret, args); + } + +#define ASSIGN_ARG(i) args[i] = arg ## i; +#define CREATE_FUNCTIONT(TYPE, N) \ + llvm::Function *create_function (const llvm::Twine& name, TYPE *ret, \ + OCT_MAKE_DECL_LIST (TYPE *, arg, N)) \ + { \ + std::vector<TYPE *> args (N); \ + OCT_ITERATE_MACRO (ASSIGN_ARG, N); \ + return create_function (name, ret, args); \ + } + +#define CREATE_FUNCTION(N) \ + CREATE_FUNCTIONT(llvm::Type, N) \ + CREATE_FUNCTIONT(jit_type, N) + + CREATE_FUNCTION(1) + CREATE_FUNCTION(2) + CREATE_FUNCTION(3) + CREATE_FUNCTION(4) + +#undef ASSIGN_ARG +#undef CREATE_FUNCTIONT +#undef CREATE_FUNCTION + + llvm::Function *create_function (const llvm::Twine& name, jit_type *ret, + const std::vector<jit_type *>& args); + + llvm::Function *create_function (const llvm::Twine& name, llvm::Type *ret, + const std::vector<llvm::Type *>& args); + + llvm::Function *create_identity (jit_type *type); + + llvm::Value *do_insert_error_check (void); + + void add_builtin (const std::string& name); + + void register_intrinsic (const std::string& name, size_t id, + jit_type *result, jit_type *arg0) + { + std::vector<jit_type *> args (1, arg0); + register_intrinsic (name, id, result, args); + } + + void register_intrinsic (const std::string& name, size_t id, jit_type *result, + const std::vector<jit_type *>& args); + + void register_generic (const std::string& name, jit_type *result, + jit_type *arg0) + { + std::vector<jit_type *> args (1, arg0); + register_generic (name, result, args); + } + + void register_generic (const std::string& name, jit_type *result, + const std::vector<jit_type *>& args); + + octave_builtin *find_builtin (const std::string& name); + + llvm::Function *mirror_binary (llvm::Function *fn); + + llvm::Function *wrap_complex (llvm::Function *wrap); + + llvm::Value *pack_complex (llvm::Value *cplx); + + llvm::Value *unpack_complex (llvm::Value *result); + + llvm::Value *complex_real (llvm::Value *cx); + + llvm::Value *complex_real (llvm::Value *cx, llvm::Value *real); + + llvm::Value *complex_imag (llvm::Value *cx); + + llvm::Value *complex_imag (llvm::Value *cx, llvm::Value *imag); + + llvm::Value *complex_new (llvm::Value *real, llvm::Value *imag); + + static jit_typeinfo *instance; + + llvm::Module *module; + llvm::ExecutionEngine *engine; + int next_id; + + llvm::GlobalVariable *lerror_state; + + std::vector<jit_type*> id_to_type; + jit_type *any; + jit_type *matrix; + jit_type *scalar; + jit_type *range; + jit_type *string; + jit_type *boolean; + jit_type *index; + jit_type *complex; + jit_type *unknown_function; + std::map<std::string, jit_type *> builtins; + + llvm::StructType *complex_ret; + + std::vector<jit_operation> binary_ops; + jit_operation grab_fn; + jit_operation release_fn; + jit_operation print_fn; + jit_operation for_init_fn; + jit_operation for_check_fn; + jit_operation for_index_fn; + jit_operation logically_true_fn; + jit_operation make_range_fn; + jit_operation paren_subsref_fn; + jit_operation paren_subsasgn_fn; + + // type id -> cast function TO that type + std::vector<jit_operation> casts; + + // type id -> identity function + std::vector<llvm::Function *> identities; +}; + +// 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(phi); \ + JIT_METH(variable); \ + JIT_METH(error_check); \ + JIT_METH(assign) \ + JIT_METH(argument) + +#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 + +class jit_convert; + +// 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; + +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: + 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) + { + jit_internal_node::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 + + 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 compatable 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) + { + if (visited (avisit_count)) + return; + + for (jit_use *use = first_use (); use; use = use->next ()) + { + jit_block *pred = use->user_parent (); + pred->label (avisit_count, number); + } + + mid = 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 + { + print_indent (os, indent); + short_print (os) << ": %pred = "; + for (jit_use *use = first_use (); use; use = use->next ()) + { + jit_block *pred = use->user_parent (); + os << *pred; + if (use->next ()) + os << ", "; + } + os << std::endl; + + for (const_iterator iter = begin (); iter != end (); ++iter) + { + jit_instruction *instr = *iter; + instr->print (os, indent + 1) << std::endl; + } + return os; + } + + // ... + jit_block *maybe_split (jit_convert& convert, jit_block *asuccessor); + + jit_block *maybe_split (jit_convert& convert, jit_block& asuccessor) + { + return maybe_split (convert, &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; + 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_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) : jit_internal_node () + { + *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: +#define JIT_CALL_CONST(N) \ + jit_call (const jit_operation& afunction, \ + OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ + : jit_instruction (OCT_MAKE_ARG_LIST (arg, N)), mfunction (afunction) {} \ + \ + jit_call (const jit_operation& (*afunction) (void), \ + OCT_MAKE_DECL_LIST (jit_value *, arg, N)) \ + : jit_instruction (OCT_MAKE_ARG_LIST (arg, N)), mfunction (afunction ()) {} + + JIT_CALL_CONST (1) + JIT_CALL_CONST (2) + JIT_CALL_CONST (3) + JIT_CALL_CONST (4) + +#undef JIT_CALL_CONST + + + const jit_operation& function (void) const { return mfunction; } + + bool can_error (void) const + { + return overload ().can_error; + } + + const jit_operation::overload& overload (void) const + { + return mfunction.get_overload (argument_types ()); + } + + virtual bool needs_release (void) const + { + return type () && jit_typeinfo::get_release (type ()).function; + } + + virtual std::ostream& print (std::ostream& os, size_t indent = 0) const + { + print_indent (os, indent); + + if (use_count ()) + short_print (os) << " = "; + os << "call " << mfunction.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& mfunction; +}; + +// FIXME: This is just ugly... +// checks error_state, if error_state is false then goto the normal branche, +// otherwise goto the error branch +class +jit_error_check : public jit_terminator +{ +public: + jit_error_check (jit_call *acheck_for, jit_block *normal, jit_block *error) + : jit_terminator (2, error, normal, acheck_for) {} + + jit_call *check_for (void) const + { + return static_cast<jit_call *> (argument (2)); + } + + virtual std::ostream& print (std::ostream& os, size_t indent = 0) const + { + print_indent (os, indent) << "error_check " << *check_for () << ", "; + print_successor (os, 1) << ", "; + return print_successor (os, 0); + } + + JIT_VALUE_ACCEPT; +protected: + virtual bool check_alive (size_t idx) const + { + return idx == 1 ? true : check_for ()->can_error (); + } +}; + +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_operation::overload& 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_operation::overload& 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_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); +} + +// convert between IRs +// FIXME: Class relationships are messy from here on down. They need to be +// cleaned up. +class +jit_convert : public tree_walker +{ +public: + typedef std::pair<jit_type *, std::string> type_bound; + typedef std::vector<type_bound> type_bound_vector; + + jit_convert (llvm::Module *module, tree &tee); + + ~jit_convert (void); + + llvm::Function *get_function (void) const { return function; } + + const std::vector<std::pair<std::string, bool> >& get_arguments(void) const + { return arguments; } + + const type_bound_vector& get_bounds (void) const { return bounds; } + + void visit_anon_fcn_handle (tree_anon_fcn_handle&); + + void visit_argument_list (tree_argument_list&); + + void visit_binary_expression (tree_binary_expression&); + + void visit_break_command (tree_break_command&); + + void visit_colon_expression (tree_colon_expression&); + + void visit_continue_command (tree_continue_command&); + + void visit_global_command (tree_global_command&); + + void visit_persistent_command (tree_persistent_command&); + + void visit_decl_elt (tree_decl_elt&); + + void visit_decl_init_list (tree_decl_init_list&); + + void visit_simple_for_command (tree_simple_for_command&); + + void visit_complex_for_command (tree_complex_for_command&); + + void visit_octave_user_script (octave_user_script&); + + void visit_octave_user_function (octave_user_function&); + + void visit_octave_user_function_header (octave_user_function&); + + void visit_octave_user_function_trailer (octave_user_function&); + + void visit_function_def (tree_function_def&); + + void visit_identifier (tree_identifier&); + + void visit_if_clause (tree_if_clause&); + + void visit_if_command (tree_if_command&); + + void visit_if_command_list (tree_if_command_list&); + + void visit_index_expression (tree_index_expression&); + + void visit_matrix (tree_matrix&); + + void visit_cell (tree_cell&); + + void visit_multi_assignment (tree_multi_assignment&); + + void visit_no_op_command (tree_no_op_command&); + + void visit_constant (tree_constant&); + + void visit_fcn_handle (tree_fcn_handle&); + + void visit_parameter_list (tree_parameter_list&); + + void visit_postfix_expression (tree_postfix_expression&); + + void visit_prefix_expression (tree_prefix_expression&); + + void visit_return_command (tree_return_command&); + + void visit_return_list (tree_return_list&); + + void visit_simple_assignment (tree_simple_assignment&); + + void visit_statement (tree_statement&); + + void visit_statement_list (tree_statement_list&); + + void visit_switch_case (tree_switch_case&); + + void visit_switch_case_list (tree_switch_case_list&); + + void visit_switch_command (tree_switch_command&); + + void visit_try_catch_command (tree_try_catch_command&); + + void visit_unwind_protect_command (tree_unwind_protect_command&); + + void visit_while_command (tree_while_command&); + + void visit_do_until_command (tree_do_until_command&); + + // this would be easier with variadic templates + 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 + +#define JIT_CREATE_CHECKED(N) \ + template <OCT_MAKE_DECL_LIST (typename, ARG, N)> \ + jit_call *create_checked (OCT_MAKE_LIST (DECL_ARG, N)) \ + { \ + jit_call *ret = create<jit_call> (OCT_MAKE_ARG_LIST (arg, N)); \ + return create_checked_impl (ret); \ + } + + JIT_CREATE_CHECKED (1) + JIT_CREATE_CHECKED (2) + JIT_CREATE_CHECKED (3) + JIT_CREATE_CHECKED (4) + +#undef JIT_CREATE_CHECKED +#undef DECL_ARG + + typedef std::list<jit_block *> block_list; + typedef block_list::iterator block_iterator; + + void append (jit_block *ablock); + + void insert_before (block_iterator iter, jit_block *ablock); + + void insert_before (jit_block *loc, jit_block *ablock) + { + insert_before (loc->location (), ablock); + } + + void insert_after (block_iterator iter, jit_block *ablock); + + void insert_after (jit_block *loc, jit_block *ablock) + { + insert_after (loc->location (), ablock); + } +private: + std::vector<std::pair<std::string, bool> > arguments; + type_bound_vector bounds; + + // used instead of return values from visit_* functions + jit_value *result; + + jit_block *entry_block; + + jit_block *final_block; + + jit_block *block; + + llvm::Function *function; + + std::list<jit_block *> blocks; + + std::list<jit_instruction *> worklist; + + std::list<jit_value *> constants; + + std::list<jit_value *> all_values; + + size_t iterator_count; + size_t short_count; + + typedef std::map<std::string, jit_variable *> vmap_t; + vmap_t vmap; + + jit_call *create_checked_impl (jit_call *ret) + { + block->append (ret); + create_check (ret); + return ret; + } + + jit_error_check *create_check (jit_call *call) + { + jit_block *normal = create<jit_block> (block->name ()); + jit_error_check *ret + = block->append (create<jit_error_check> (call, normal, final_block)); + append (normal); + block = normal; + + return ret; + } + + jit_variable *get_variable (const std::string& vname); + + std::pair<jit_value *, jit_value *> resolve (tree_index_expression& exp); + + jit_value *do_assign (tree_expression *exp, jit_value *rhs, + bool artificial = false); + + jit_value *do_assign (const std::string& lhs, jit_value *rhs, bool print, + bool artificial = false); + + jit_value *visit (tree *tee) { return visit (*tee); } + + jit_value *visit (tree& tee); + + void push_worklist (jit_instruction *instr) + { + if (! instr->in_worklist ()) + { + instr->stash_in_worklist (true); + worklist.push_back (instr); + } + } + + void append_users (jit_value *v) + { + for (jit_use *use = v->first_use (); use; use = use->next ()) + push_worklist (use->user ()); + } + + void append_users_term (jit_terminator *term); + + void track_value (jit_value *value) + { + if (value->type ()) + constants.push_back (value); + all_values.push_back (value); + } + + void merge_blocks (void); + + void construct_ssa (void); + + void do_construct_ssa (jit_block& block, size_t avisit_count); + + void remove_dead (); + + void place_releases (void); + + void release_temp (jit_block& ablock, std::set<jit_value *>& temp); + + void release_dead_phi (jit_block& ablock); + + void simplify_phi (void); + + void simplify_phi (jit_phi& phi); + + void print_blocks (const std::string& header) + { + std::cout << "-------------------- " << header << " --------------------\n"; + for (std::list<jit_block *>::iterator iter = blocks.begin (); + iter != blocks.end (); ++iter) + { + assert (*iter); + (*iter)->print (std::cout, 0); + } + std::cout << std::endl; + } + + void print_dom (void) + { + std::cout << "-------------------- dom info --------------------\n"; + for (std::list<jit_block *>::iterator iter = blocks.begin (); + iter != blocks.end (); ++iter) + { + assert (*iter); + (*iter)->print_dom (std::cout); + } + std::cout << std::endl; + } + + bool breaking; // true if we are breaking OR continuing + block_list breaks; + block_list continues; + + void finish_breaks (jit_block *dest, const block_list& lst); + + // this case is much simpler, just convert from the jit ir to llvm + class + convert_llvm : public jit_ir_walker + { + public: + convert_llvm (jit_convert& jc) : jthis (jc) {} + + llvm::Function *convert (llvm::Module *module, + const std::vector<std::pair<std::string, bool> >& args, + const std::list<jit_block *>& blocks, + const std::list<jit_value *>& constants); + +#define JIT_METH(clname) \ + virtual void visit (jit_ ## clname&); + + JIT_VISIT_IR_CLASSES; + +#undef JIT_METH + private: + // name -> llvm argument + std::map<std::string, llvm::Value *> arguments; + + void finish_phi (jit_phi *phi); + + void visit (jit_value *jvalue) + { + return visit (*jvalue); + } + + void visit (jit_value &jvalue) + { + jvalue.accept (*this); + } + + llvm::Value *create_call (const jit_operation::overload& ol, jit_value *arg0) + { + std::vector<jit_value *> args (1, arg0); + return create_call (ol, args); + } + + llvm::Value *create_call (const jit_operation::overload& ol, jit_value *arg0, + jit_value *arg1) + { + std::vector<jit_value *> args (2); + args[0] = arg0; + args[1] = arg1; + + return create_call (ol, args); + } + + llvm::Value *create_call (const jit_operation::overload& ol, + const std::vector<jit_value *>& jargs); + + llvm::Value *create_call (const jit_operation::overload& ol, + const std::vector<jit_use>& uses); + private: + jit_convert &jthis; + llvm::Function *function; + llvm::BasicBlock *prelude; + }; +}; + +class jit_info; + +class +tree_jit +{ +public: + tree_jit (void); + + ~tree_jit (void); + + bool execute (tree_simple_for_command& cmd); + + llvm::ExecutionEngine *get_engine (void) const { return engine; } + + llvm::Module *get_module (void) const { return module; } + + void optimize (llvm::Function *fn); + private: + bool initialize (void); + + // FIXME: Temorary hack to test + typedef std::map<tree *, jit_info *> compiled_map; + llvm::Module *module; + llvm::PassManager *module_pass_manager; + llvm::FunctionPassManager *pass_manager; + llvm::ExecutionEngine *engine; +}; + +class +jit_info +{ +public: + jit_info (tree_jit& tjit, tree& tee); + + ~jit_info (void); + + bool execute (void) const; + + bool match (void) const; +private: + typedef jit_convert::type_bound type_bound; + typedef jit_convert::type_bound_vector type_bound_vector; + typedef void (*jited_function)(octave_base_value**); + + llvm::ExecutionEngine *engine; + jited_function function; + llvm::Function *llvm_function; + + std::vector<std::pair<std::string, bool> > arguments; + type_bound_vector bounds; +}; + +// some #defines we use in the header, but not the cc file +#undef JIT_VISIT_IR_CLASSES +#undef JIT_VISIT_IR_CONST +#undef JIT_VALUE_ACCEPT + +#endif +#endif
--- a/src/pt-loop.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/pt-loop.cc Sun Jul 22 04:16:02 2012 +0200 @@ -35,6 +35,7 @@ #include "pt-bp.h" #include "pt-cmd.h" #include "pt-exp.h" +#include "pt-jit.h" #include "pt-jump.h" #include "pt-loop.h" #include "pt-stmt.h" @@ -97,6 +98,7 @@ delete list; delete lead_comm; delete trail_comm; + delete compiled; } tree_command *
--- a/src/pt-loop.h Thu Jul 19 21:28:00 2012 +0200 +++ b/src/pt-loop.h Sun Jul 22 04:16:02 2012 +0200 @@ -36,6 +36,8 @@ #include "pt-cmd.h" #include "symtab.h" +class jit_info; + // While. class @@ -146,7 +148,7 @@ tree_simple_for_command (int l = -1, int c = -1) : tree_command (l, c), parallel (false), lhs (0), expr (0), - maxproc (0), list (0), lead_comm (0), trail_comm (0) { } + maxproc (0), list (0), lead_comm (0), trail_comm (0), compiled (0) { } tree_simple_for_command (bool parallel_arg, tree_expression *le, tree_expression *re, @@ -157,7 +159,7 @@ int l = -1, int c = -1) : tree_command (l, c), parallel (parallel_arg), lhs (le), expr (re), maxproc (maxproc_arg), list (lst), - lead_comm (lc), trail_comm (tc) { } + lead_comm (lc), trail_comm (tc), compiled (0) { } ~tree_simple_for_command (void); @@ -180,8 +182,18 @@ void accept (tree_walker& tw); + // some functions use by tree_jit + jit_info *get_info (void) const + { + return compiled; + } + + void stash_info (jit_info *jinfo) + { + compiled = jinfo; + } + private: - // TRUE means operate in parallel (subject to the value of the // maxproc expression). bool parallel; @@ -205,6 +217,9 @@ // Comment preceding ENDFOR token. octave_comment_list *trail_comm; + // compiled version of the loop + jit_info *compiled; + // No copying! tree_simple_for_command (const tree_simple_for_command&);
--- a/src/pt-stmt.h Thu Jul 19 21:28:00 2012 +0200 +++ b/src/pt-stmt.h Sun Jul 22 04:16:02 2012 +0200 @@ -35,12 +35,13 @@ #include "base-list.h" #include "comment-list.h" #include "symtab.h" +#include "pt.h" // A statement is either a command to execute or an expression to // evaluate. class -tree_statement +tree_statement : public tree { public:
--- a/src/sighandlers.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/sighandlers.cc Sun Jul 22 04:16:02 2012 +0200 @@ -63,7 +63,7 @@ // TRUE means we should try to enter the debugger on SIGINT. static bool Vdebug_on_interrupt = false; -// Allow users to avoid writing octave-core for SIGHUP (sent by +// Allow users to avoid writing octave-workspace for SIGHUP (sent by // closing gnome-terminal, for example). Note that this variable has // no effect if Vcrash_dumps_octave_core is FALSE. static bool Vsighup_dumps_octave_core = true; @@ -147,12 +147,12 @@ #endif case SIGFPE: - std::cerr << "warning: floating point exception -- trying to return to prompt" << std::endl; + std::cerr << "warning: floating point exception" << std::endl; break; #ifdef SIGPIPE case SIGPIPE: - std::cerr << "warning: broken pipe -- some output may be lost" << std::endl; + std::cerr << "warning: broken pipe" << std::endl; break; #endif } @@ -1001,7 +1001,7 @@ @deftypefnx {Built-in Function} {@var{old_val} =} sighup_dumps_octave_core (@var{new_val})\n\ @deftypefnx {Built-in Function} {} sighup_dumps_octave_core (@var{new_val}, \"local\")\n\ Query or set the internal variable that controls whether Octave tries\n\ -to save all current variables to the file \"octave-core\" if it receives\n\ +to save all current variables to the file \"octave-workspace\" if it receives\n\ a hangup signal.\n\ \n\ When called from inside a function with the \"local\" option, the variable is\n\ @@ -1030,7 +1030,7 @@ @deftypefnx {Built-in Function} {@var{old_val} =} sigterm_dumps_octave_core (@var{new_val})\n\ @deftypefnx {Built-in Function} {} sigterm_dumps_octave_core (@var{new_val}, \"local\")\n\ Query or set the internal variable that controls whether Octave tries\n\ -to save all current variables to the file \"octave-core\" if it receives\n\ +to save all current variables to the file \"octave-workspace\" if it receives\n\ a terminate signal.\n\ \n\ When called from inside a function with the \"local\" option, the variable is\n\
--- a/src/symtab.h Thu Jul 19 21:28:00 2012 +0200 +++ b/src/symtab.h Sun Jul 22 04:16:02 2012 +0200 @@ -484,7 +484,7 @@ return symbol_record (rep->dup (new_scope)); } - std::string name (void) const { return rep->name; } + const std::string& name (void) const { return rep->name; } octave_value find (const octave_value_list& args = octave_value_list ()) const; @@ -581,6 +581,66 @@ symbol_record (symbol_record_rep *new_rep) : rep (new_rep) { } }; + // Always access a symbol from the current scope. + // Useful for scripts, as they may be executed in more than one scope. + class + symbol_reference + { + public: + symbol_reference (void) : scope (-1) {} + + symbol_reference (symbol_record record, + scope_id curr_scope = symbol_table::current_scope ()) + : scope (curr_scope), sym (record) + {} + + symbol_reference& operator = (const symbol_reference& ref) + { + scope = ref.scope; + sym = ref.sym; + return *this; + } + + // The name is the same regardless of scope. + const std::string& name (void) const { return sym.name (); } + + symbol_record *operator-> (void) + { + update (); + return &sym; + } + + symbol_record *operator-> (void) const + { + update (); + return &sym; + } + + // can be used to place symbol_reference in maps, we don't overload < as + // it doesn't make any sense for symbol_reference + struct comparator + { + bool operator ()(const symbol_reference& lhs, + const symbol_reference& rhs) const + { + return lhs.name () < rhs.name (); + } + }; + private: + void update (void) const + { + scope_id curr_scope = symbol_table::current_scope (); + if (scope != curr_scope || ! sym.is_valid ()) + { + scope = curr_scope; + sym = symbol_table::insert (sym.name ()); + } + } + + mutable scope_id scope; + mutable symbol_record sym; + }; + class fcn_info {
--- a/src/toplev.cc Thu Jul 19 21:28:00 2012 +0200 +++ b/src/toplev.cc Sun Jul 22 04:16:02 2012 +0200 @@ -1325,6 +1325,9 @@ { false, "MAGICK_CPPFLAGS", OCTAVE_CONF_MAGICK_CPPFLAGS }, { false, "MAGICK_LDFLAGS", OCTAVE_CONF_MAGICK_LDFLAGS }, { false, "MAGICK_LIBS", OCTAVE_CONF_MAGICK_LIBS }, + { false, "LLVM_CPPFLAGS", OCTAVE_CONF_LLVM_CPPFLAGS }, + { false, "LLVM_LDFLAGS", OCTAVE_CONF_LLVM_LDFLAGS }, + { false, "LLVM_LIBS", OCTAVE_CONF_LLVM_LIBS }, { false, "MKOCTFILE_DL_LDFLAGS", OCTAVE_CONF_MKOCTFILE_DL_LDFLAGS }, { false, "OCTAVE_LINK_DEPS", OCTAVE_CONF_OCTAVE_LINK_DEPS }, { false, "OCTAVE_LINK_OPTS", OCTAVE_CONF_OCTAVE_LINK_OPTS },