Security and Data Fabrication

Feedback Directed Program Restructuring (FDPR)

FDPR is a feedback-based post-link optimization tool. It optimizes the executable image of a program by collecting information on the behavior of the program while the program is used for some typical workload, and then creating a new version of the program that is optimized for that workload. The new program generated by FDPR typically runs faster and uses less real memory.

FDPR performs global optimizations at the level of the entire executable, including statically linked library code. Since the executable to be optimized by FDPR will not be re-linked, the compiler and linker conventions do not need to be preserved, thus allowing aggressive optimizations that are not available to optimizing compilers. When used on large subsystems that operate in a multiprocessing setting, FDPR provides significant performance improvements.

The tool is suitable for very large programs or DLLs (dynamic link libraries).

The main optimizations of FDPR include inter-procedural register re-allocation, improving instruction scheduling, data prefetching, function inlining, global data reordering, global code reordering, along with various tuning options for the Power architecture.

The following figure shows how FDPR is used to optimize executable programs:

Click to see full size 

FDPR builds an optimized executable program in three distinct phases:

1. Create an instrumented executable program
   FDPR receives an executable file as input and generates a new instrumented program file.
2. Run the instrumented program and create the profile data
   
   • Instrumented executbale file is run on representative workload.
   • Profile file is generated automatically at run time.
3. Generate the optimized executable program file
   FDPR receives the original executable file along with the generated profile file to create a new optimized executbale file

In 2003, all old FDPR versions were replaced by the FDPR release. FDPR is an object-oriented designed tool, specially developed to support multiple platforms. It includes a shared code-base layer on top of which all post-link optimizations are implemented.

FDPR is currently available on the following platforms:

1. AIX/Power - a product-level tool that is part of the AIX version 5 operating system and higher for both 32-bit and 64-bit applications. FDPR AIX fixes can be downloaded from: IBM Quick links for AIX fixes.
2. Linux on POWER - available for use through the IBM alphaWorks site.
3. z/OS - available as an FDPR prototype. FDPR version is under development.
4. Windows/IA32 - available as an FDPR prototype.

For more information about working with FDPR, see this presentation about FDPR operation and usage.

Publications

R. R. Heisch, "Trace-Directed Program Restructuring for AIX Executables", IBM Journal of Research and Development 38, No. 5, pp. 595-603, Sept 1994.

I. Nahshon and D. Bernstein. "FDPR - A Post-Pass Object Code Optimization Tool", Proc. Poster Session of the International Conference on Compiler Construction, pp. 97-104, April 1996.

W. J. Schmidt, R.R. Roediger, C.S. Mestad, B. Mendelson, I. Shavit-Lottem, and V. Bortnikov-Sitnitsky, "Profile-directed Restructuring of Operating System Code", IBM Systems Journal, 37, No. 2, pp. 270-297, 1998.

Ealan A. Henis, Gadi Haber, Moshe Klausner, and Alex Warshavsky, "FDPR - A post-link optimization tool for large subsystems" Proc. Feedback Directed Optimizations 2 Workshop, pp. , Oct. 1999.

Gadi Haber, Ealan Henis, and Vadim Eisenberg, "Reliable Post-link Optimizations Based on Partial Information Subsystems", Proc. Feedback Directed Optimizations 3 Workshop, Dec. 2000.

Gad Haber, Moshe Klausner, Bilha Mendelson, and Vadim Eisenberg, "Light Weight Optimizations for Reducing Hot Saves and Restore of Callee-Saved Registers", Proc. FDDO4 Workshop, Dec. 2001.

Gadi Haber, Moshe Klausner, Vadim Eisenberg, Bilha Mendelson, and Maxim Gurevich, "Optimization Opportunities Created by Global Data Reordering", Proc. First International Symposium on Code Generation and Optimization (CGO'2003), San Francisco, California, pp. 228-241, March, 2003.

Daniel Citron, Gadi Haber, and Roy Levin, "Reducing program image size by extracting frozen code and data", Proceedings of the 4th ACM International Conference on Embedded Software, Pisa Italy, September, 2004.

O. Boehm, D. Citron, G. Haber, M. Klausner, and R. Levin, "Aggressive Function Inlining with Global Code Reordering", IBM Research Report number H-0247, November, 2006.