We initially assume that “jump” instructions jump to another location within their parent function, as their origin is usually either a switch statement or a for or while loop. To determine a call tree around “jump” instructions in object code, we make some assumptions. It is trivial to see that func is stored in *%eax in this example, but this may not always be the case. You can see that the jmp *%eax “jump” instructions in this example are indirect, addressing data stored in memory rather than directly jumping to a code address. This can make it difficult to determine function boundaries, which are needed to determine WCET using Rapi Time. The compiler optimized the call to func into a “jump”. Jmp *%eax /* This jump originates from a switch statement */ Jmp *%eax /* This jump originates from a tail call */ Tail calls can be replaced with “jumps”, and compiler optimization eliminates tail calls to minimize overhead see the example below:Ī compiler eliminates the high-overhead tail call by replacing the expression with a “jump” to the func sub-routine: Calls have high overheads as they add a new stack frame to the call stack. Tail call optimizationĪ tail call is a sub-routine call made immediately before a function returns. These indirect "jumps" make it difficult to map assembly instructions to the source code. Some other features of compiler optimization also make this mapping difficult, for example tail call optimization. In this case, the "jump" instruction clearly executes loop control flow by directly addressing iteration, but "jumps" can be indirect, addressing code via an address stored in memory. You may notice that the for loop has been compiled as a “jump” instruction jle iteration, preceded by compare ( cmpl ) and add ( addl ) instructions. While a control flow graph can easily be determined from source code, it is a little more difficult to do this from object code. To trace control flow from object code, we use branch trace information to map each assembly instruction to its origin in the source code. This lets us present the program as a call tree, and each function as a loop nesting tree, and these trees are necessary for our analysis (Figure 1). We need to know the control flow of a program to determine WCET metrics from it. In this post, we’d like to share some details on one of the main difficulties analyzing object code presented us with: tracing control flow. We recently completed the ROCA project, and will be taking the technology further in our current SECT-AIR project. This lets us eliminate instrumentation overhead entirely when performing timing analysis. Instead of having to rely on instrumentation to obtain timing metrics, our tool uses branch trace information collected from the CPU during program execution. In our Rapi Time Object Code Analyser (ROCA) project, as the name implies, we have been developing a tool that lets us use object code to perform timing analysis with Rapi Time. This is why we have been developing Rapi Time, our on-target timing analysis tool, to perform WCET analysis with zero instrumentation. While this is a robust method for determining WCET metrics, it requires that instrumentation be added to source code, increasing overhead. Worst-case execution time (WCET) analysis is critical for the verification of safety-critical real-time embedded systems. This analysis is typically performed by instrumenting source code and obtaining timing data from an instrumented build.
0 Comments
Leave a Reply. |