Efficient Building and Placing of Gating Functions

Peng Tu, David Padua

Research output: Contribution to journalArticlepeer-review


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
Issue number6
StatePublished - Jan 6 1995

ASJC Scopus subject areas

  • Software
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Efficient Building and Placing of Gating Functions'. Together they form a unique fingerprint.

Cite this