Download Control Flow Graphs for Real-Time System Analysis

Chapter 8
Interprocedural Path Analysis
This chapter will introduce path analysis for graphs with context. It is the result of my
research in this area (see [Theiling, 2002]), improving the precision and flexibility of the
existing framework. The algorithms are implemented in a tool called pathan, which is
part of the WCET analysis framework.
8.1 Basic Constraints
In this section, the ideas from the previous chapter will be the basis for generating an
ILP for graphs with contexts.
It is important to note that the graphs with context information still represent control
flow in the same way as the normal graph: edges mark control flow and nodes represent basic blocks. The fact that context information has split one block or edge into
many ones does not influence this fact, because the edges are inserted at context changes
exactly according to the possibilities of context change. I. e. usually a call node has an
outgoing edge in the call graph that changes the context and enters the start node of
another routine.
Of course, this is no surprise, because the PAG framework introduces these graphs for
analysis, so they are constructed to work in the same way as graphs without contexts.
So in short, the basic idea of ILP generation still works on graphs with contexts in the
same way it does on graphs without.
119