Accurate and efficient predicate analysis with binary decision diagrams

John W. Sias, Wen mei W. Hwu, David I. August

Research output: Contribution to journalConference articlepeer-review

23 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)112-123
Number of pages12
JournalProceedings of the Annual International Symposium on Microarchitecture
StatePublished - 2000
Externally publishedYes
Event33rd Annual IEEE/ACM International Symposium on Microarchitecture - Monterey, CA, USA
Duration: Dec 10 2000Dec 13 2000

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture
  • Software


Dive into the research topics of 'Accurate and efficient predicate analysis with binary decision diagrams'. Together they form a unique fingerprint.

Cite this