BMAT -- A Binary Matching Tool for Stale Profile Propagation

A major challenge of applying profile-based optimization on large real-world applications is how to capture adequate profile information. A large program, especially a GUI-based application, may be used in a large variety of ways by different users on different machines. Extensive collection of profile data is necessary to fully characterize this type of program behavior. Unfortunately, in a realistic software production environment, many developers and testers need fast access to the latest build, leaving little time for collecting profiles. To address this dilemma, we would like to re-use stale profile information from a prior program build. In this paper we present BMAT, a fast and effective tool that matches two versions of a binary program without knowledge of source code changes. BMAT enables the propagation of profile information from an older, extensively profiled build to a newer build, thus greatly reducing or even eliminating the need for re-profiling. We use two metrics to evaluate the quality of the results using propagated profile information: static branch prediction and the accuracy of code coverage. These metrics measure how well the matching algorithm works for the frequently executed core code and across the whole program, respectively. Experiments on a set of large DLLs from Microsoft Windows 2000 and Internet Explorer show that compared to freshly collected profiles, propagated information using BMAT is typically over 99% as effective in branch prediction and over 98% as accurate in code coverage information