Method and apparatus for profile-based reordering of program portions in

Abstract

An apparatus and several methods provide for a more optimized computer program that will have a faster execution time than was possible using the prior art reordering technique that adds to a trace until it finds no more predecessors or successors to add. The apparatus and methods disclosed herein use a variety of methods to reorder the program portions in a more intelligent manner that will improve its run-time performance. Each of these methods involves constructing traces in the control flow graph of the computer program. In a first embodiment, a basic block is only added to a trace if it is not negligible within predetermined limits. This negligibility test results in traces that are not extended for infrequently executed basic blocks. In a second embodiment, a basic block is only added to a trace if it is a perfect partner with the last basic block added to the trace. The concept of a 'perfect partner' helps to match basic blocks together in a trace that have the greatest affinity for each other. In a third embodiment, a basic block is only added to a trace if it satisfies 'should follow' flags and predetermined negligibility criteria. The 'should follow' flags and negligibility criteria provide a complex criteria for adding basic blocks to a trace, criteria that create more efficient code in some specific circumstances.