Accurate and Efficient Predicate Analysis with Binary Decision
Diagrams [abstract] (ACM DL, PDF, PostScript)
John W. Sias, Wen-mei W. Hwu, and David I. August
Proceedings of the 33rd International Symposium on
Microarchitecture (MICRO), December 2000.
Functionality and performance of EPIC architectural
features depend on extensive compiler support. Predication, one of
these features, promises to reduce control flow overhead and to
enhance optimization, provided that compilers can utilize it
effectively. Previous work has established the need for accurate,
direct predicate analysis and has demonstrated a few useful
techniques, but has not provided an efficient, general framework.
This paper presents the Predicate Analysis System (PAS), which maps
knowledge of predicate and condition relations in general control flow
onto a convenient logical substrate, the reduced ordered binary
decision diagram. PAS is the first such framework to demonstrate
direct, accurate, and efficient analysis of arbitrary condition and
predicate define networks in arbitrary control flow.