From: tac@eos.ncsu.edu
Subject: Architecture description languages for compilers?
Reply-To: tac@eos.ncsu.edu
Organization: Compilers Central
Date: Tue, 26 Jan 1993 17:41:15 GMT
Keywords: architecture, VHDL

> I'm planning on doing some research in optimization and code generation
> next quarter.  One of the topics I'm interested in is machine
> descriptions--some vanilla way to describe the architecture of a machine
> for purposes of code generation.  (Numbers of registers, addressing modes,
> etc.)

Below, I've included some references dealing with machine description
languages.  Some discuss the use of a description language more than the
language itself.

> [There have been lots of architecture description languages over the years.
> Whether any of them can be used to mechanically generate a compiler is
> another question.  I suspect they'd be more useful for validation. -John]

This depends entirely on what you mean by "architecture description
language".  I would define it as meaning a language that describes the
behavior that a processor exhibits to an assembly language programmer
independent of performance-only issues (since a single instruction set can
have many different implementations at many different levels of
performance).

Given this definition, I have been unable, after a very thorough search,
to find a language which satisfies it (though I am working hard to correct
this egrerious situation :-).  Hardware description languages (HDLs), such
as VHDL, really describe high-level implementations of architectures, not
the architectures themselves.  The difference is similar to that between a
program in a high-level language and a program in assembly; they do the
same thing, but the level of abstraction is substantially different
(unless you are using C :-).

(I mention HDLs because it is trivially easy to find papers whose
abstracts say "a new language for describing computer architectures" and
whose bodies talk about gate-level logic specification.  Logic design is
not computer architecture.)

Anyway, back to compilers.  Compiler generators need to know what
instructions, addressing modes, etc., a processor has.  Unfortunately,
HDLs provide no way of differentiating between instruction descriptions
and arbitrary blocks of hardware.  Therefore, in the general case, it is
not possible (the Halting Problem and all that mess) for a compiler
generator to derive the necessary information from an HDL-based
description.

Also, the machine descriptions found in the articles below don't really
describe the machines, but rather the code generators.  However, this post
is already too long.

--  todd cook
--  tac@eos.ncsu.edu


@article {TOPLAS:Ganapathi85,
	author   = "Mahadevan Ganapathi and Charles N. Fischer",
	title    = "Affix Grammar Driven Code Generation",
	journal  = TOPLAS,
	month    = oct,
	year     = 1985,
	pages    = "560-599"
	}

@article {TOPLAS:Aho89,
	author   = "Alfred V. Aho and Mahadevan Ganapathi and
		Steven W. K. Tjiang",
	title    = "Code Generation Using Tree Matching and Dynamic
		Programming",
	journal  = TOPLAS,
	month    = oct,
	year     = 1989,
	pages    = "491-516"
	}

@article {SWPE:Davidson89,
	author   = "Jack W. Davidson and David B. Whalley",
	title    = "Quick Compilers Using Peephole Optimization",
	journal  = SWPE,
	month    = jan,
	year     = 1989,
	pages    = "79-97"
	}

@article {TOPLAS:Davidson84,
	author   = "Jack W. Davidson and Christopher W. Fraser",
	title    = "Code Selection through Object Code Optimization",
	journal  = TOPLAS,
	month    = oct,
	year     = 1984,
	pages    = "505-526"
	}

@article {AI:Ganapathi88,
	author   = "Mahadevan Ganapathi and Charles N. Fischer",
	title    = "Integrating Code Generation and Peephole Optimization",
	journal  = "Acta Informatica",
	month    = jan,
	year     = 1988,
	pages    = "85-109"
	}

@inproceedings {SCC:Davidson84,
	author    = "Jack W. Davidson and Christopher W. Fraser",
	title     = "Automatic Generation of Peephole Optimizations",
	booktitle = SCC,
	year      = 1984,
	pages     = "111-116"
	}

@inproceedings {SCC:Kessler84,
	author    = "Robert R. Kessler",
	title     = "Peep - An Architectural Description Driven Peephole
		Optimizer",
	booktitle = SCC,
	year      = 1984,
	pages     = "106-110"
	}

@book {Cattell82,
	author    = "R. G. G. Cattell",
	title     = "Formalization and Automatic Derivation of Code
		Generators",
	publisher = "UMI Research Press",
	year      = 1982,
	note      = "QA268 C37 1982"
	}

@article {TOPLAS:Cattell80,
	author   = "R. G. G. Cattell",
	title    = "Automatic Derivation of Code Generators from Machine
		Descriptions",
	journal  = TOPLAS,
	month    = apr,
	year     = 1980,
	pages    = "173-190"
	}

@article {TOPLAS:Davidson80,
	author   = "Jack W. Davidson and Christopher W. Fraser",
	title    = "The Design and Application of a Retargetable Peephole
		Optimizer",
	journal  = TOPLAS,
	month    = apr,
	year     = 1980,
	pages    = "191-202"
	}

@article {SWPE:Davidson84,
	author   = "Jack W. Davidson and Christopher W. Fraser",
	title    = "Register Allocation and Exhaustive Peephole Optimization",
	journal  = SWPE,
	month    = sep,
	year     = 1984,
	pages    = "857-866"
	}

@article {SWPE:Davidson87,
	author   = "Jack W. Davidson and Christopher W. Fraser",
	title    = "Automatic Inference and Fast Interpretation of Peephole
		Optimization Rules",
	journal  = SWPE,
	volume   = 17,
	year     = 1987,
	pages    = "801-812"
	}

@inproceedings {PoPL:Ganapathi82,
	author    = "Mahadevan Ganapathi and Charles N. Fischer",
	title     = "Description-Driven Code Generation Using Attribute
		Grammars",
	booktitle = PoPL,
	year      = 1982,
	pages     = "108-119"
	}

@article {CL:Hatcher91,
	author   = "Philip J. Hatcher",
	title    = "The Equational Specification of Efficient Compiler Code
		Generation",
	journal  = "Computer Languages",
	volume   = 16,
	number   = 1,
	year     = 1991,
	pages    = "81-95"
	}

@inproceedings {PLDI:Fraser89,
	author   = "Christopher W. Fraser",
	title    = "A Language for Writing Code Generators",
	booktitle= PLDI,
	year = 1989,
	pages    = "238-245"
	}

@techreport {UVA:Davidson85,
	author      = "Jack W. Davidson",
	title       = "Simple Machine Description Grammars",
	institution = "University of Virginia",
	address     = "Department of Computer Science",
	number      = "85-22",
	year        = 1985
	}

@inproceedings {PLDI:Giegerich90,
	author   = "Robert Giegerich",
	title    = "On the Structure of Verifiable Code Generator
		Specifications",
	booktitle= PLDI,
	year = 1990,
	pages    = "1-8"
	}

@inproceedings {PLDI:Wendt90,
	author   = "Alan L. Wendt",
	title    = "Fast Code Generation Using Automatically-Generated
		Decision Trees",
	booktitle= PLDI,
	year = 1990,
	pages    = "9-15"
	}

@inproceedings {PLDI:Bradlee91,
	author   = "David G. Bradlee and Robert R. Henry and Susan J. Eggers",
	title    = "The Marion System for Retargetable Instruction
		Scheduling",
	booktitle= PLDI,
	year = 1991,
	pages    = "229-240"
	}

@phdthesis {UW:Bradlee91,
	author   = "David G. Bradlee",
	title    = "Retargetable Instruction Scheduling for Pipelined
		Processors",
	school   = "University of Washington",
	address  = "Dept. of Computer Science and Engineering",
	year     = 1991,
	note     = "Available as Technical Report 91-08-07",
	}

@inproceedings {CC:Despland90,
	author   = "Annie Despland and Monique Mazaud and Raymond Rakotozafy",
	title    = "PAGODE: A Back End Generator Using Attribute Abstract
		Syntaxes and Term Rewritings",
	booktitle= CC90,
	year = 1990,
	pages    = "86-105"
	}

-- 
Send compilers articles to compilers@iecc.cambridge.ma.us or
{ima | spdcc | world}!iecc!compilers.  Meta-mail to compilers-request.
Newsgroups: comp.compilers