Subject: Luddy Harrison talk at MIT W 10/31
From: Mitchell Wand (wand@ccs.neu.edu)
Date: Sat Oct 27 2001 - 11:05:49 EDT
Date: Wed, 24 Oct 2001 10:01:30 -0400
To: seminars@lcs.mit.edu, fac-res@hq.lcs.mit.edu, grads@hq.lcs.mit.edu,
ugrads@hq.lcs.mit.edu
From: Michael Ernst <mernst@lcs.mit.edu> (by way of Neena Lyall <lyall@lcs.mit.edu>)
Subject: Luddy Harrison talk
Bitwise Constant Propagation by Abstract Interpretation
Luddy Harrison
Intel Corporation
Wednesday, October 31, 2001 in NE43-518
Refreshments at 1:45 PM and Talk at 2:00 PM
Constant propagation is ordinarily carried out in the forward
direction (i.e., in execution order) and at the level of entire
values: whole integers, floating point numbers, addresses, etc. It is
possible to extend constant propagation so that it operates in the
backward direction, and at the level of individual bits. We show how
abstract interpretation can be used to design such a forward and
backward analysis. A forward semantics is used to describe the
(greatest) values produced by a computation from given inputs, and a
backward semantics is used to define the (least) values demanded by a
computation in order to produce a given output. There is an
interesting non-monotonicity in the backward semantics we define for
the basic boolean connectives (AND and OR). We illustrate
corresponding abstract forward and backward semantics. We show how
the fixpoint of these abstract semantics can be computed efficiently
using storage that is linear in the program size. We show how this
bitwise analysis can be applied to the problems of vectorization for
MMX-like instruction sets; algebraic simplification; dead code
elimination; and of course conventional constant folding. We show
that this analysis can be applied even when a minimum of type
information is available, i.e., to the analysis of assembly language
programs as well as compiler intermediate language programs.
********************************************************************
Luddy Harrison is an Engineering Manager at Intel Corporation. He
received B.A. degrees in English Literature and Political Science from
the University of Illinois at Champaign-Urbana in 1983, and a Ph.D. in
Computer Science from the University of Illinois at Champaign-Urbana
in 1988. He led the Symbolic Computation Group in the Center for
Supercomputing Research at the University of Illinois from 1989 to
1993, and was advisor to five Ph.D. recipients at the University of
Illinois. In 1993 he co-founded Connected Components Corporation, a
software vendor specializing in compilers for signal and network
processors. CCC was acquired by Intel in 2001 and is now a software
laboratory within the Intel Architecture Group, focused on compilers
for special-purpose processors. He has published several papers on
program analysis and compilation for parallel architectures and has
given a number of invited talks on these subjects.
Host: Michael Ernst
This archive was generated by hypermail 2b28 : Sat Oct 27 2001 - 11:06:12 EDT