Re: Recovering control flow information

Andrew Sao-Chun Huang <ahuang@faraday.ece.cmu.edu> writes:
>I'm working on a code scheduler that produces scheduled code for a
>parallel architecture. The scheduler takes as its input the assembly
>listing produced by a modified, sparc GCC frontend. I would like to do
>some global dataflow analysis on the input file before scheduling it. But
>I run into the following 2 problems when I try to reconstruct the control
>flow graph:


I have done a lot of this sort of thing with object code generated for the
MIPS architecture by the MIPS cc and f77 compilers. The problems are not
too difficult to solve.


>1) Identifying the first basic block of each function. The input file
>consists of many basic blocks. I would like to partition them into
>different groups such that each group contains basic blocks from one
>function. I can say that any basic block without a predecessor is the
>first basic block of some function. But this would be wrong since it may
>be the target of a compute branch. Actually, this problem is solved once
>problem 2 is resolved.


This may be good enough for the assembly code from gcc, but it does not
work well with object code from the MIPS compilers. The MIPS assembler
reorganizes instructions to fill branch delays slots. This is often done
by copying an instruction into the delay slot of a branch and then
changing the branch target to the following instruction. The original
instruction remains in the object code with no predecessors. Make sure
that nothing like this occurs in the output of gcc!


To get around this problem, I divide an object file into procedures by
computing connected sets of basic blocks. Starting at the beginning of
the program, I traverse the flow graph ignoring call instructions and
interprocedural jumps. All of the basic blocks between the start and the
furthest block reached in the traversal are included in the same
procedure. This is repeated for the rest of the program.


>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.
Given that information, you can just go through the table and read out all
of the possible destinations of the computed jump. For the MIPS compiler,
this task is particularly easy, because the code generated for computed
jumps always consists of the same instructions in the same order. The
necessary information can be obtained by just pattern-matching and
extracting certain fields from the instructions.


I know that Jim Larus has used this technique is some of his research, and
in fact, it might even be described in the tech reports recently
advertised here in comp.compilers.


>[This information is clearly available to the compiler, so I'd take the
>direct approach and have the compiler put some comments into the file that
>identify entry points, function boundaries, and branch tables. -John]


If you have the option of modifying the compiler and you can figure out
how to accomplish these things in gcc, I agree that this is the best way
to go.


Bob Wilson
bwilson@shasta.stanford.edu
--

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