Efficient building and placing of gating functions

Peng Tu, David Padua

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 @-nodes. The gating functions specify the control dependence 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 o to v, such that every node in the path is dominated by w 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 node, but also a gating path expression which defines a gating function for the φ-node.

Original languageEnglish (US)
Title of host publicationProceedings of the ACM SIGPLAN 1995 Conference on Programming language Design and Implementation, PLDI 1995
PublisherAssociation for Computing Machinery
Pages47-55
Number of pages9
ISBN (Electronic)0897916972
DOIs
StatePublished - Jun 18 1995
Event1995 ACM SIGPLAN Conference on Programming language Design and Implementation, PLDI 1995 - San Diego, United States
Duration: Jun 18 1995Jun 21 1995

Publication series

NameProceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)
VolumePart F129371

Other

Other1995 ACM SIGPLAN Conference on Programming language Design and Implementation, PLDI 1995
Country/TerritoryUnited States
CitySan Diego
Period6/18/956/21/95

ASJC Scopus subject areas

  • Software

Cite this