Bi-directional Dataflow Type Inference

After reading this paper I've starting implementing a brand new type analysis in Boomerang. The first step is calculating reverse dominance frontiers. A regular dominance frontier is the set of nodes that have a predecessor that is dominated by the given node, but is not itself dominated. These are the nodes where phi statements are to be placed when transforming a program into SSA form. The reverse dominance frontier is much the same, except it is the successors that must be post-dominated. Boomerang already calculates immediate post-dominators for use by the code generation phase, but we've never before had a use for reverse dominator frontiers. The paper describes an extension to SSA form called static single information form (SSI) which introduces a new kind of assignment: the sigma function statement which are placed on the reverse dominator frontiers. The purpose of this new statement is to split definitions before uses on different code paths. I will be using a more verbose form of this notation where a sigma statement for each use is emitted.

For some reason the algorithms used to place sigma functions are more complex than the algorithms we use to place phi functions. This is most probably because we're using the simple dominance frontier based algorithms that don't guarentee O(EV) performance. As such, I'm starting to wonder if sigma functions really are just a performance enhancement and if the same thing can't be achieved with just regular assignments strategically placed on each branch. In any case, it seems to me that reverse dominance frontiers are only necessary so you can calculate minimal SSI form. Reducing the number of sigma functions you introduce is obviously a good thing, but it may not be particularly important for Boomerang as we often detect and remove unused statements anyway.

At this juncture I'm abandoning my implementation. Boomerang needs a lot more retrofitting to support this form than I think is necessary for type inference. Instead, I'm going to try implementing the dataflow alogrithm without SSI and see if/how it fails. Then, if necessary, I'll add some adhoc sigma like manipulations to merge type information from uses.

Comments

Post a Comment

Popular posts from this blog

Disabling OS-X Device Removal Warnings In Yosemite

Image
If you're anything like me you've probably seen the Disk Not Ejected Properly message so many times that you've forgotten how annoying it is.. despite the fact that you never even wrote anything to the usb drive that you're yanking out of your Mac the operating system insists that you remove it "correctly". You're supposed to click the eject button. Why? I dunno, Apple seems to think that if you can write to it then the operating system might have written to it - and being Apple, they probably have. Well ya know what? Fuck you, I won't do what you tell me. Note: this will not fix your external drive disconnecting when your Mac goes to sleep. For that problem try disabling "put hard drive to sleep when possible" in both the Battery and Power Adapter tabs of the OS energy saver settings. What appears below is a dirty hack for deliberately removing a warning that Apple insists on showing you every single time you yank out a usb stick.
Read more

Rebirth Of The Spaceship

Image
Over the last year the space advocate community has splintered into two major groups in answering the question "where should we go next?" Moon First or Mars First . This division was present in the Review of Human Spaceflight (aka Augustine) committee's final report in late 2009, with the surprising conclusion that there isn't the funds for either, suggesting a number of intermediate destinations first - including asteroids. However, as few people consider asteroids to be truly interesting destinations for the human utilization of space ( except me! ), the debate rages on. Many Moon First advocates are "Mars Next" advocates while most Mars First advocates are "Moon Again?" detractors. The former claim that Mars exploration will benefit from lunar exploration, particularly in experience and risk reduction, and perhaps the procurement of propellant. The latter claim that lunar exploration is just a distraction and want to avoid the risk of be
Read more

Mars Direct Without Super Heavy Lift

Image
For a decade or two now the proponents of Bob Zubrin's Mars Direct have been bemoaning the lack of super heavy lift (any vehicle that can lift more than 50 ton to LEO). While few advocates claim a heavy lift launch vehicle is the only component of the Mars Direct plan which is missing, most consider it a necessary prerequisite. Before I tell you why I think that's simply wrong, let's just make a quick list of all the other things we still need: decent life support, space suits for Mars, rovers that run on methane/LOX, the ISRU propellant production system, bigger entry/descent/landing systems than have ever been flown, portable field equipment for the science mission, artificial gravity generation, and the habitat itself. Oh yeah, and a space rated nuclear reactor. The beautiful innovation of the Mars Direct plan was the use of the Mars atmosphere to produce the return propellant so it doesn't need to be carried all the way from Earth. Without this simple idea t
Read more