This week, I finally finished up the RubyWrite port of our existing type inference implementation, and the next step will be to implement slice-hoisting in order to better handle loops. The plan is to have this completed by next week.
I will also need to revisit the code we received from Kevin’s group and analyze the profiler output carefully for opportunities for improvement before our group meeting with them on Tuesday. It doesn’t look like it will be as easy to specialize/optimize as Sid’s code, but hopefully we are able to find some relatively low-hanging fruit.
October 26, 2009
With our recent submission to ASPLOS complete, our immediate task at hand will be to polish up the paper we had accepted to HiPC 09. We will also be continuing the source-level reuse distance work the ASPLOS submission was based on.
Interesting GCC developments
I recently came across this announcement of a vulnerability in the Linux kernel. What’s interesting about it is that while there is a bug in the source code, the actual vulnerability is introduced by the compiler.
The snippet of code in question:
struct sock *sk = tun->sk; // initialize sk with tun->sk
…
if (!tun)
return POLLERR; // if tun is NULL return error
The bug, of course, is that tun is dereferenced before it’s checked for NULL. It also turns out that if control reaches past the NULL check and an attacker has mmapped something at address 0, arbitrary code execution can occur. While the code is buggy, this should still never occur the way it’s written. The real problem is that GCC performs dataflow analysis and deletes NULL checks it deems unnecessary — and since tun has already been referenced, it is assumed to be non-NULL — so the entire if statement is deleted by the optimizer, thus introducing the vulnerability.
This behavior is controlled via -fdelete-null-pointer-checks:
Use global dataflow analysis to identify and eliminate useless checks for null pointers. The compiler assumes that dereferencing a null pointer would have halted the program. If a pointer is checked after it has already been dereferenced, it cannot be null.
In some environments, this assumption is not true, and programs can safely dereference null pointers. Use -fno-delete-null-pointer-checks to disable this optimization for programs which depend on that behavior.
GCC 4.4
GCC 4.4 was released a few months ago, and one of the new features caught my eye:
- The Graphite branch has been merged. This merge has brought in a new framework for loop optimizations based on a polyhedral intermediate representation.
The loop optimizations currently supported by 4.4 are loop interchange, strip-mining, and blocking. Intrigued by the latter, I tried compiling an unblocked matrix multiply in GCC 4.3 and 4.4, but saw little performance difference. It appears that they may only be performing blocking in one dimension then. One of the libraries this new Graphite framework might be of interest to us, however: CLooG is a library “to solve the code generation problem for optimizing compilers based on the polytope model”. There is a related publication titled Code Generation in the Polyhedral Model Is Easier Than You Think from PACT 2004. Looks like the polytope model is the way to go!
August 17, 2009
Since my last update, I’ve finished the MATLAB and C++ unparsers using Andy’s ShadowBoxing tool. There is still plenty of infrastructure work to be done, but for now, I’m putting that aside while the RubyWrite traversals get fixed and am thinking ahead to what’s next.
Our next goal is to think about how to use source-level reuse distances to guide the compiler in performing locality-based optimizations. To do so, we need some way of looking at the source-level reuse distances in two programs and deciding which one is “better” in terms of locality. This isn’t trivial, since the reuse distances we have are per-variable, so we have to find an accurate way to derive an overall measure of the program’s locality based on these.
So my first goal for this week is to read up on some of the existing reuse distance work and see if we can apply any of the existing ideas at the source level. Secondly, I’m going to start thinking about how to perform dependence analysis in RubyWrite, using Melanie’s work from last summer as a starting point. There is also a minor issue in the parser where else ifs need to be distinguished from ordinary ifs that needs to be fixed. Finally, I’m going to try to get my oral quals scheduled by next week.
March 24, 2009
I’ve now got a Rakefile that builds the Octave parser C extension for Ruby in a platform independent way, correctly generating a .so file extension on Linux and .bundle on Mac. While testing this in Ubuntu Linux (which I’m now running in VMWare because I’m still most comfortable in XMonad, a tiling window manager written in Haskell), I discovered that some Octave initialization code was being called, which didn’t cause any problems in Gentoo Linux, but resulted in some errors in Ubuntu (when it tried to load some site files). As a result, I’ve disabled the initialization code and it doesn’t seem to have broken anything.
I think having Ubuntu installed and using it regularly makes for a pretty good development setup, since I can now work on the same codebase in both Linux and Mac OS, and make sure everything is truly as platform independent as we expect. It’s also just one more Linux distribution to test on, as I wouldn’t have discovered the initialization bug otherwise.
I’ve also continued porting the flattener to RubyWrite, with the hope that what I’ve written works once the traversals have been fixed. I’ve also created a ParaM branch for the current Stratego/XT code, and am in the process of reorganizing and cleaning up the new Ruby code. Once that’s done, I’ll replace the ParaM trunk with it.
A few interesting links
Tinyrb, a tiny Ruby virtual machine.
Cilk++, a C++ version of Cilk
Seminar on Static Single Assignment CFP
February 24, 2009
This week, I finally managed to track down the reason why my C extension for Ruby failed to load on Mac OS – it was because the --link-stand-alone flag somehow made its way into my call to mkoctfile. My original Octave parser was a stand-alone executable and actually needed this flag, but it is definitely incorrect to use it when creating a shared library instead. Apparently, the Mac OS dynamic linker isn’t very robust, and when it tries to load an executable as a shared library, it simply hangs and eats up 100% of your CPU. Making the same mistake in Linux immediately results in an error from the dynamic linker. With that problem solved, we now have a working MATLAB/Octave parser that outputs RubyWrite terms.
Next, I’ll need to write an unparser to transform the AST back into MATLAB source.
February 13, 2009
The beginning of this week will be spent preparing my poster for eScience 2008.
After that, I need to investigate why my OctParse Ruby extension fails to load on Mac OS. The reason is most likely because I’m using Octave’s mkoctfile to perform the compilation, and it is using different compiler flags from what Ruby expects. The command I’m currently using is /Applications/Octave.app/Contents/Resources/bin/mkoctfile -I. -DHAVE_CONFIG_H OctParse.cpp -o OctParse.bundle --link-stand-alone -I/System/Library/Frameworks/Ruby.framework/Versions/1.8/usr/lib/ruby/1.8/universal-darwin9.0 -L"/System/Library/Frameworks/Ruby.framework/Versions/1.8/usr/lib" -lruby
Comparing the g++ flags that uses to what Ruby’s mkmf generates, I don’t see any obvious differences that would explain Ruby’s failure to load the resulting library, so I’ll need to do some more digging. A quick sudo dtrace -n "pid\$target:::entry" -c "ruby test.rb" shows that the last userland function that gets called before Ruby hangs is SegmentMachO::getActualLoadAddress(ImageLoader const*). DTrace’s ability to instrument (almost, on Mac OS) any running process is pretty neat. It even works with Ruby code.
Finally, I’ll be pushing ahead with the re-implementation of our ParaM compiler in RubyWrite!
December 8, 2008
I spent most of the week learning about writing C extensions in Ruby, and I’ve successfully created a C extension that calls the Octave parser. Using it is a simple matter of doing:
parser = OctParse.new
ast = parser.parse("Arnoldi")
and the result is an instance of Node. ast is then ready to be processed by any later analysis/transformation passes. Or prettyprinted (the beginning of Arnoldi.m):
:Function[
[:Var[
'V'
]
,:Var[
'H'
]
,:Var[
'f'
]
]
,'Arnoldi'
,[:Var[
'A'
]
,:Var[
'k'
]
,:Var[
'v'
]
]
,:StmtList[
[:Silent[
:Assignment[
:Var[
'n'
]
,'='
,:Subscript[
:Var[
'length'
]
,[:Var[
'v'
]
]
]
]
]
Now that we can parse MATLAB/Octave, I look forward to porting our other passes to RubyWrite!
December 5, 2008
After spending the past week trying to track down the source of the typeinference segfault, I discovered today that the segfault has nothing to do with the C code that interfaces with the MATLAB engine and performs partial evaluation. I had assumed it was there because that is the only non-Stratego code that processes ATerms. However, after changing the prim call to !Const(1.0) and still getting the segfault, it is clearly not the cause of the problem. This was rather surprising to me since I had tried changing the prim call to some other term instantiation a while ago, and it made the segfault disappear. It looks like there may be a bug somewhere in either the ATerm library or Stratego, since this post to the stratego-dev mailing list describes a very similar situation.
Looking forward to this week, I’ll need to put together my poster for the eScience 2008 poster session next week. We’ve also made the decision to dive in and port our compiler to RubyWrite, the system we’ve been developing.
December 5, 2008
I’ve made a little progress in tracking down the crash in typeinference, but now it just crashes later. The constant propagator was blindly evaluating every function it had all the arguments to, including zeros() and rand(), which definitely should not be evaluated at compile time.
Also, it seems like there are a LOT of ATerms being allocated in the constant propagation phase, and I’m starting to wonder whether this should be the case. It looks like the /PropConstDynamic\* on the for loop is iterating over the loop many times (more than it should?), and changing it to not iterate until a fixed-point resolves the crash (but of course, with a reduced number of constants propagated).
The good news is that I noticed this morning that the HIPS deadline has been extended by a week, so we have a little more time to work on this.
November 24, 2008
While I was really hoping to have some experimental test results this week, I ran into a host of new problems while trying to test the example cases. I did find some interesting code from the MathWorks site, and it looks like Outage, Nasmg, and Arnoldi will be suitable examples too.
I uncovered yet another bug in SSA where it was handling certain ifs incorrectly. Strangely, there also seems to be a case where the type inference pass tries to call free() twice during its constant propagation phase. I’m currently trying to track that down. There were also many small fixes I had to make in various other things… which were mostly a result of certain assumptions I had made while writing them. Getting the compiler to run end-to-end is turning out to be significantly harder than I expected, but I feel that I made quite a bit of progress toward that goal this week.
Unfortunately, with only 9 days left before the HIPS deadline, I’m not sure if we’ll have everything done by then, but I will keep trying my best to make it. It looks like the LDTA deadline is shortly after HIPS, and it may be a good backup target. The CFP specifically mentions source-to-source compilers. 
November 14, 2008
Previous Posts