Accurate and efficient predicate analysis with binary decision diagrams

John W. Sias, Wen-Mei W Hwu, David I. August

Research output: Contribution to journalConference article

Abstract

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 - Dec 1 2000
Event33rd Annual IEEE/ACM International Symposium on Microarchitecture - Monterey, CA, USA
Duration: Dec 10 2000Dec 13 2000

Fingerprint

Binary decision diagrams
Flow control
Substrates

ASJC Scopus subject areas

  • Hardware and Architecture
  • Software

Cite this

Accurate and efficient predicate analysis with binary decision diagrams. / Sias, John W.; Hwu, Wen-Mei W; August, David I.

In: Proceedings of the Annual International Symposium on Microarchitecture, 01.12.2000, p. 112-123.

Research output: Contribution to journalConference article

@article{d1812cf2286a41509e93f9a4bd473d92,
title = "Accurate and efficient predicate analysis with binary decision diagrams",
abstract = "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.",
author = "Sias, {John W.} and Hwu, {Wen-Mei W} and August, {David I.}",
year = "2000",
month = "12",
day = "1",
language = "English (US)",
pages = "112--123",
journal = "Proceedings of the Annual International Symposium on Microarchitecture, MICRO",
issn = "1072-4451",

}

TY - JOUR

T1 - Accurate and efficient predicate analysis with binary decision diagrams

AU - Sias, John W.

AU - Hwu, Wen-Mei W

AU - August, David I.

PY - 2000/12/1

Y1 - 2000/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0034461298&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0034461298&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:0034461298

SP - 112

EP - 123

JO - Proceedings of the Annual International Symposium on Microarchitecture, MICRO

JF - Proceedings of the Annual International Symposium on Microarchitecture, MICRO

SN - 1072-4451

ER -