Re: Recovering control flow information

bwilson@shasta.Stanford.EDU (Bob Wilson) writes:
>Andrew Sao-Chun Huang <ahuang@faraday.ece.cmu.edu> writes:
>>2) Computed branches. Sometimes 'switch' statements get compiled into a
>>computed branch where the targets are store in a table in data memory. I
>>need to add control flow arcs from the basic block that contains the
>>computed branch to each of the target basic blocks.
>
>This problem can be be solved by analyzing the assembly instructions used
>to compute the branch target address. In some sense, you can just
>interpret the instructions at compile time. All that you need to find are
>the starting address of the table and the number of entries in the table.


In the general case, I think this may require interprocedural analysis.
The variable used in the switch statement could be passed as a parameter,
and then you'll have a harder time determining the actual size of the
table. If the table is embedded in the object code, sometimes the offset
will look like instructions (if you're scanning the code to find the end
of the table).


Another problem area is function pointers. Here the variable could be
stored with the procedure's address at any arbitrary place in the program.
Depending on the architecture, an indexed jump through a function pointer
might look like a case/switch statement.


We wanted to do something similar to this. Essentially, enhance the output
of IBM's compilers to provide relocations for all procedure calls and
subdivide the "per-module" csects into "per procedure" csects; strip the
TBT; and add TOC reload instructions for all procedure calls (the Apple
Linker would replace the reload with a nop as necessary). Note that this
was to be done on the compiler's output, so not all calls were necessarily
resolved at this point.


The simple cases were easy to handle. Switch statements, function
pointers, and similar stuff made us realize that we probably couldn't do
this without being unsafe in some cases. It was cheaper in time and effort
to just pay IBM to enhance their compilers the way we wanted. (Part of our
problem is that we were changing code length - which effects all those
branch offsets.)


Since Andrew's original goal seems in the area of code scheduling, in my
mind, it'd be better to hack on gcc to produce the schedules you want. All
the information is there, and if it isn't you can change the compiler to
synthesize it!
--
Chuck Lins, Apple Computer, Inc. Oberon-2 Paladin lins@apple.com
--

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