Data dependency graph bracing

ABSTRACT

The Sunburst compiler refined at Utah State University employs a powerful mechanism for management of data anti-dependencies in data dependency graphs, DDG's: the DDG Bracer. The term bracing1 is used to mean the fastening of two or more parts together. There are two major goals in bracing: 1) semantic correctness, and 2) creation of an optimal DDG. Bracing provides necessary joining of code fragments, produced by a divide and conquer code generation algorithm, while yielding multiple code sequences. Since no anti-dependency arcs are present, the input DDG's are said to be in normal form. Because anti-dependency arcs occur only when a resource must be reused, a DDG in normal form represents infinite resources. The output DDG is a merging of the two input DDG's such that data dependency arcs between the two DDG's are inserted and data anti-dependency arcs are added to sequentialize the use of common resources. Vegdahl [Veg82] was one of the first to recognize the importance of live track manipulation. A live track is an ordered pair: the first component is the microoperation node ( MO) in which a resource is born, and the second component is the set of nodes in which the resource dies.

REFERENCES

• All86: Vicki Hurst Allan, A critical analysis of the global optimization problem for horizontal microcode (phase-coupled, compaction, code motion, compilation), 1986
• MS86: R.A. Mueller and P.H. Sweany. Horizon Code Generator Series-Parallel DDG Coupler/Decoupler (Version s.1). Technical Report MAD-86-10, Firmware Engineering and Micro-Architecture Design Laboratory, Colorado State University, Fort Collins, CO, August 1986.
• Veg82: Steven Roger Vegdahl, Local code generation and compaction in optimizing microcode compilers, 1982

INDEX TERMS

Primary Classification:
  B. Hardware
  B.1 CONTROL STRUCTURES AND MICROPROGRAMMING
      B.1.4 Microprogram Design Aids
          Subjects: Languages and compilers

General Terms:
Algorithms, Design, Performance