Efficient Building and Placing of Gating Functions

Peng Tu, David Padua

Research output: Contribution to journalArticlepeer-review

Abstract

In this paper, we present an almost-linear time algorithm for constructing Gated Single Assignment (GSA), which is SSA augmented with gating functions at 0—nodes. The gating functions specify the control dependences for each reaching definition at a node. We introduce a new concept of gating path, which is a path in the control flow graph from the immediate dominator u of a. node v to v, such that every node in the path is dominated by u. Previous algorithms start with —function placement, and then traverse the control flow graph to compute the gating functions. By formulating the problem into gating path construction, we are able to identify not only a (f>—node, but also a gating path expression which defines a gating function for the d>-node.

Original languageEnglish (US)
Pages (from-to)47-55
Number of pages9
JournalACM SIGPLAN Notices
Volume30
Issue number6
DOIs
StatePublished - Jan 6 1995

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design

Cite this