METHOD AND APPARATUS FOR PROFILE-BASED REORDERING OF PROGRAM PORTIONS IN A COMPUTER PROGRAM

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.