Browse Prior Art Database

Moving N Invariant Conditional Branches out of a Loop

IP.com Disclosure Number: IPCOM000118101D
Original Publication Date: 1996-Sep-01
Included in the Prior Art Database: 2005-Mar-31

Publishing Venue

IBM

Related People

Ziv, I: AUTHOR

Abstract

Disclosed is an invention which will improve performance of programs by allowing better scheduling and by isolating the parts of a loop that are heavily executed from those parts of a loop that are less executed. It allows N invariant conditional branches to move in a single scan of the code, thus saving compile time. It also defines identical invariant conditional branches and moves them out of the loop as ONE invariant conditional branch, thus saving on code explosion. It also suggests some code transformation which can make two or more invariant conditional branches identical. The invention also suggests handling efficiency of the invariant conditional branches in the most inner loop.

This text was extracted from an ASCII text file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 23% of the total text.

Moving N Invariant Conditional Branches out of a

Loop

      Disclosed is an invention which will improve performance of
programs by allowing better scheduling and by isolating the parts of
a loop that are heavily executed from those parts of a loop that are
less executed.  It allows N invariant conditional branches to move in
a single scan of the code, thus saving compile time.  It also defines
identical invariant conditional branches and moves them out of the
loop as ONE invariant conditional branch, thus saving on code
explosion.  It also suggests some code transformation which can make
two or more invariant conditional branches identical.  The invention
also suggests handling efficiency of the invariant conditional
branches in the most inner loop.

      There have been several works done on the subject of moving
invariant conditional branches out of a loop.  The most significant
one is (1).  Others are: (2), (3), (4), (5), (6), (7).

This innovation is different from all previous works in the following
points:
  1.  It offers an algorithm to remove N invariant conditional
       branches out of a loop in a single scan of the code rather
       than moving one invariant conditional branch at a time.
  2.  It defines an equivalency relation between invariant
       conditional branches and moves them all as a SINGLE
       invariant conditional branch.
  3.  It offers a code transformation to expose equivalent
       conditional branches.
  4.  It deals with the case when an invariant conditional branch
       is embedded in a most inner loop and offers an efficient way
       to remove it directly from the most outer loop.
  5.  It analyzes the case when the fall through path and the
       taken path of an invariant conditional branch are completely
       included in the fall through path of another invariant
       conditional branch.  It moves N invariant conditional
       branches out of a loop.

      This algorithm will make it possible to move N invariant
conditional branches out of a loop in a single scan of the code in
the loop.  This mission can be accomplished also by moving one
invariant conditional branch at a time, followed by reconstructing
the program graph.

      The move of the last invariant conditional branch may require
the most effort since there are many copies of the original loop
where this invariant conditional branch exists.

      The algorithm allows us to avoid the extraneous work of
reconstructing the program graph after each move, and the tracing of
the invariant conditional branches as copies of the original loop are
being created.

      Users tend to code loops with many invariant conditional
branches, to alleviate the problem of code maintenance.  In a
compiler environment, however, more optimizations are possible if we
have a smoother code without many conditional branches.  In case of
profil...