Re: exception handling and optimization papers?

V.C. SREEDHAR <sreedhar@ccl.CS.McGill.CA> wrote:
>Can some one give me pointers to papers that discusses data flow
>analysis and optimizations for programs that contain exception
>handling...


Nope, but I can say a little bit... First, let's talk about scope.
I'll refrain from talking about traditional techniques (let say, those
techniques used by a C compiler), they are a prerequisite for this
article and you can learn about them from many good books and papers.
Also, I'll try and stay away from codegen issues, as you didn't ask
about them. Below I will only talk about those things that you must
do in addition to the standard optimizations, for the standard stuff
to continue to work, and then I'll move onto the EH only or EH
specific things. My background is EH in C++, so that may slant my
view of the world some.


The way that I think of it, EH just adds some additional edges to the
basic block information from the control-flow analysis in a manner
similar to goto, and it adds some values and variables to track during
data-flow analysis to support more interesting EH specific
optimizations. The first one is mandatory, the second isn't (unless
you want to go on to implement the EH specific optimizations).


throw/rethrow (whether explicit or implicit) adds an edge from the
throw point to the first (innermost) nested catch point, or if there
is none, out of the function, similar to return, but not the same as
return. In particular the return value isn't live. As with a goto,
various scopes can end on the edge and variables in those scopes die
on the edge.


At each function call, there is an edge from it, up (as above).


These two I think will allow all the optimizations that people
normally do, subject to getting the codegen details right.


Now, onto the EH specific things. Value tracking on the type/value of
the EH object. By tracking the type/value of the EH object, you can
transform conditional jumps based upon those into unconditional jumps.
Further, you can transform throws where you can determine where they
will wind up, into simpler jumps. Combine these two, and code like:


int main() {
    try {
        throw 1;
    } catch (int i) {
        printf("Hi\n");
    }
}


can be transformed into:


int main() {
    printf("Hi\n");
}


Further, with inlining,


void foo() {
    throw 1;
}


int main() {
    try {
        foo();
    } catch (int i) {
        printf("Hi\n");
    }
}


can be transformed into:


int main() {
    printf("Hi\n");
}


You can transform catch/rethrows as in:


int main() {
    try {
        [...]
    } catch (...) {
        throw;
    }
}


into code like:


int main() {
    [...]
}


If you said more about your codegen strategies for EH, I could have
more easily commented more on the various optimizations that you can
do. For example, if you use unwind tables (like with a zero cost EH
implementation), you can migrate the start and ends of EH regions
closer together, as long as it is not over something that can throw.
This allows you to collapse empty regions out entirely and to merge
nested regions with the same starting and ending positions together.
For example,


int foo throw();
int bar throw();


int main() {
    bar();
    try {
        foo();
    } catch (int i) {
    }
}


can be transformed into:


int main() {
    bar();
    foo();
}


with no unwind information for main, and


int main() {
    try {
        try {
            ...
        } catch (int i) {
        }
    } catch (int i) {
    }
}


can be transformed into:


int main() {
    ...
}


Anyway, most of this stuff it fairly straightforward when you think
about it (unpatentable). There are probably some more pieces that can
be added to these basics, people that know of some that I missed can
elaborate, but these should get you started.
--

Return to the comp.compilers page.
Search the comp.compilers archives again.