<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//TaxonX//DTD Taxonomic Treatment Publishing DTD v0 20100105//EN" "../../nlm/tax-treatment-NS0.dtd">
<article xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:tp="http://www.plazi.org/taxpub" article-type="research-article" dtd-version="3.0" xml:lang="en">
  <front>
    <journal-meta>
      <journal-id journal-id-type="publisher-id">109</journal-id>
      <journal-id journal-id-type="index">urn:lsid:arphahub.com:pub:3dc5f44e-8666-58db-bc76-a455210e8891</journal-id>
      <journal-title-group>
        <journal-title xml:lang="en">JUCS - Journal of Universal Computer Science</journal-title>
        <abbrev-journal-title xml:lang="en">jucs</abbrev-journal-title>
      </journal-title-group>
      <issn pub-type="ppub">0948-695X</issn>
      <issn pub-type="epub">0948-6968</issn>
      <publisher>
        <publisher-name>Journal of Universal Computer Science</publisher-name>
      </publisher>
    </journal-meta>
    <article-meta>
      <article-id pub-id-type="doi">10.3217/jucs-012-08-1007</article-id>
      <article-id pub-id-type="publisher-id">28647</article-id>
      <article-categories>
        <subj-group subj-group-type="heading">
          <subject>Research Article</subject>
        </subj-group>
        <subj-group subj-group-type="scientific_subject">
          <subject>D.1.3 - Concurrent Programming</subject>
          <subject>D.3.4 - Processors</subject>
          <subject>I.1.2 - Algorithms</subject>
        </subj-group>
      </article-categories>
      <title-group>
        <article-title>Eliminating Redundant Join-Set Computations in Static Single Assignment</article-title>
      </title-group>
      <contrib-group content-type="authors">
        <contrib contrib-type="author" corresp="yes">
          <name name-style="western">
            <surname>French</surname>
            <given-names>Angela</given-names>
          </name>
          <email xlink:type="simple">french@cs.ualberta.ca</email>
          <xref ref-type="aff" rid="A1">1</xref>
        </contrib>
        <contrib contrib-type="author" corresp="no">
          <name name-style="western">
            <surname>Amaral</surname>
            <given-names>Jose N.</given-names>
          </name>
          <xref ref-type="aff" rid="A2">2</xref>
        </contrib>
      </contrib-group>
      <aff id="A1">
        <label>1</label>
        <addr-line content-type="verbatim">University of Alberta, , Canada</addr-line>
        <institution>University of Alberta</institution>
        <country>Canada</country>
      </aff>
      <aff id="A2">
        <label>2</label>
        <addr-line content-type="verbatim">Computing Science Dept., University of Alberta, Edmonton, Canada</addr-line>
        <institution>Computing Science Dept., University of Alberta</institution>
        <addr-line content-type="city">Edmonton</addr-line>
        <country>Canada</country>
      </aff>
      <author-notes>
        <fn fn-type="corresp">
          <p>Corresponding author: Angela French (<email xlink:type="simple">french@cs.ualberta.ca</email>).</p>
        </fn>
        <fn fn-type="edited-by">
          <p>Academic editor: </p>
        </fn>
      </author-notes>
      <pub-date pub-type="collection">
        <year>2006</year>
      </pub-date>
      <pub-date pub-type="epub">
        <day>28</day>
        <month>08</month>
        <year>2006</year>
      </pub-date>
      <volume>12</volume>
      <issue>8</issue>
      <fpage>1007</fpage>
      <lpage>1019</lpage>
      <uri content-type="arpha" xlink:href="http://openbiodiv.net/73199A4B-BEAC-50DD-AEC0-4FE7E86A371A">73199A4B-BEAC-50DD-AEC0-4FE7E86A371A</uri>
      <uri content-type="zenodo_dep_id" xlink:href="https://zenodo.org/record/6997082">6997082</uri>
      <permissions>
        <copyright-statement>Angela French, Jose N. Amaral</copyright-statement>
        <license license-type="creative-commons-attribution" xlink:href="" xlink:type="simple">
          <license-p>This article is freely available under the J.UCS Open Content License.</license-p>
        </license>
      </permissions>
      <abstract>
        <label>Abstract</label>
        <p>The seminal algorithm developed by Ron Cytron, Jeanne Ferrante and colleagues in 1989 for the placement of φ-nodes in a control flow graph is still widely used in commercial compilers. Placing φ-nodes is necessary when converting a program representation to Static Single Assignment (SSA) form. This paper shows that if a variable x is defined in a set of basic blocks A(x), then the iterated join set of A(x) can be decomposed into the computation of the iterated join set of a disjoint collection of subsets of A(x). We use this result to show that some join set computations are redundant. We measured the number of redundant computations in the Open Research Compiler (ORC) in a selection of SPEC 2000 benchmarks.</p>
      </abstract>
    </article-meta>
  </front>
</article>
