Browse Prior Art Database

A method for performing partial dead code elimination without transforming control flow graph

IP.com Disclosure Number: IPCOM000010770D
Original Publication Date: 2003-Jan-20
Included in the Prior Art Database: 2003-Jan-20
Document File: 2 page(s) / 14K

Publishing Venue

IBM

Abstract

Disclosed is a method for performing partial dead code elimination (PDE) without transforming control flow graph (CFG). In general, some special control flow edges (called "critical edges") become barriers for performing PDE. Previous work solves critical edges by inserting a block on each critical edge. However, this solution increases the number of blocks, and thus compilation time and memory consumption are increased. This disclosure describes a method for performing PDE without inserting a block on each critical edge.

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

Page 1 of 2

  A method for performing partial dead code elimination without transforming control flow graph

  In general, some special control flow edges become barriers for performing PDE. These edges are called "critical edges" [1]. Previous work solves critical edges by inserting a block on each critical edge [1]. However, this solution increases the number of blocks, and thus compilation time and memory consumption are increased. This disclosure describes a method for performing PDE without inserting a block on each critical edge. It has the following two steps:

The compiler computes dummy edges in order to correctly perform PDE without

inserting a block on each critical edge. When the compiler performs PDE, it computes dataflow sets by enabling the dummy


1.


2.

edges computed by step 1.

1) When "i=i+1" is not reached at block 4

1

2 3

2)When "i=i+1" is reached at block 4

1

2 3

4

i = i + 1

4

"i=i+1" must not be moved to "i=i+1" can be moved to botheither block 2 or 3blocks 2 and 3

Figure 1. Correct optimization results without transforming CFG

Our goal is to correctly perform PDE without inserting a block on each critical edge. Fig. 1 shows examples of correct optimization results without transforming CFG.

i = i + 1

i = i + 1

 Assuming the edge from block 4 to 3

Figure 2. Basic idea

To achieve the results of Fig. 1, we assume the edge from block 4 to 3 in a PDE phase as shown in Fig. 2. In more detail, steps 1 and 2 perform the following transactions:

[Step1] By using given pre...