Browse Prior Art Database

Generalized Landing Pads

IP.com Disclosure Number: IPCOM000114368D
Original Publication Date: 1994-Dec-01
Included in the Prior Art Database: 2005-Mar-28
Document File: 4 page(s) / 85K

Publishing Venue

IBM

Related People

Hicks, DR: AUTHOR [+2]

Abstract

Disclosed is a method that can be used in an optimizing compiler for improving its ability to perform classical optimizations. A "landing pad" is defined as a synthetic block inserted into the control flow graph of a program. "Landing pads" are often inserted by compilers in the process of code optimization in order to enable particular optimizations involving code motion. What is disclosed here is a method for inserting landing pads which are potentially profitable, without inserting landing pads that cannot possibly improve optimization, and without missing any landing pads which could improve optimization.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Generalized Landing Pads

      Disclosed is a method that can be used in an optimizing
compiler for improving its ability to perform classical
optimizations.  A "landing pad" is defined as a synthetic block
inserted into the control flow graph of a program.  "Landing pads"
are often inserted by compilers in the process of code optimization
in order to enable particular optimizations involving code motion.
What is disclosed here is a method for inserting landing pads which
are potentially profitable, without inserting landing pads that
cannot possibly improve optimization, and without missing any landing
pads which could improve optimization.

      Landing pads can be profitably inserted on any arc which
originates from a block with multiple exits and terminates at a block
with multiple entries.  This criteria covers insertion of landing
pads for both backward code motion and forward code motions.  This
transformation is illustrated in Fig. 1.

      In this flow graph fragment on the left, the arc from the block
labeled (1) to the block labeled (2) meets the criteria of
originating from a block with multiple exits (block 1 is shown with
two arcs flowing from it), and terminates at a block with multiple
entries (block 2 is shown with two arcs flowing into it).  The flow
graph fragment on the right depicts the transformation, with a
landing
pad block (labeled LP) placed on the arc from block 1 to block 2.

      This is in contrast to conventional solutions to this problem,
where for any loops recognized in the program, a "landing pad" is
inserted into the flow graph at the start of the loop (sometimes
called a pre-header block for the loop), and at exits from a loop
(sometimes called post-exit blocks for the loop).  What is disclosed
here covers this situation, and further identifies other
opportunities for landing pad insertion not recognized by this
conventional approach.

      As an example, consider the flow graph shown in Fig. 2.  The
expression "A*B" occurs inside the loop whose body is block (2).
Assuming tha...