Improving Dynamic Binary Optimization Through Early-Exit Guided Code Region Formation

Most dynamic binary translators (DBT) and optimizers (DBO) tar-get binary traces, i.e. frequently executed paths, as code regions to be translated and optimized. Code region formation is the most im-portant first step in all DBTs and DBOs. The quality of the dynam-ically formed code regions determines the extent and the types of optimization opportunities that can be exposed to DBTs and DBOs, and thus, determines the ultimate quality of the final optimized code. The Next-Executing-Tail (NET) trace formation method used in HP Dynamo is an early example of such techniques. Many exist-ing trace formation schemes are variants of NET. They work very well for most binary traces, but they also suffer a major problem: the formed traces may contain a large number of early exits that could be branched out during the execution. If this happens fre-quently, the program execution will spend more time in the slo