NDLI: Handling irreducible loops: optimized node splitting versus DJ-graphs

Content Provider	ACM Digital Library
Author	Unger, Sebastian Mueller, Frank
Copyright Year	2002
Abstract	This paper addresses the question of how to handle irreducible regions during optimization, which has become even more relevant for contemporary processors since recent VLIW-like architectures highly rely on instruction scheduling. The contributions of this paper are twofold. First, a method of optimized node splitting to transform irreducible regions of control flow into reducible regions is formally defined and its correctness is shown. This method is superior to approaches previously published since it reduces the number of replicated nodes by comparison. Second, three methods that handle regions of irreducible control flow are evaluated with respect to their impact on compiler optimizations. First, traditional node splitting is evaluated. Second, optimized node splitting is implemented. Third, DJ-Graphs are utilized to recognize nesting of irreducible (and reducible) loops and apply common loop optimizations extended for irreducible loops. Experiments compare the performance of these approaches with unrecognized irreducible loops that cannot be subject to loop optimizations, which is typical for contemporary compilers. Measurements show improvements of 1 to 40% for these methods of handling irreducible loops over the unoptimized case. Optimized node splitting may be chosen to retrofit existing compilers since it has the advantage that it only requires few changes to an optimizing compiler while limiting the code growth of compiled programs compared to traditional node splitting. Recognizing loops via DJ-Graphs should be chosen for new compiler developments since it requires more changes to the optimizer but does not significantly change the code size of compiled programs while yielding comparable improvements. Handling irreducible loops should even yield more benefits for exploiting instruction-level parallelism of modern architectures in the context of global instruction scheduling and optimization techniques that may introduce irreducible loops, such as enhanced modulo scheduling.
Starting Page	299
Ending Page	333
Page Count	35
File Format	PDF
ISSN	01640925
e-ISSN	15584593
DOI	10.1145/567097.567098
Volume Number	24
Issue Number	4
Journal	ACM Transactions on Programming Languages and Systems (TOPLAS)
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2002-07-01
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Code optimization Compilation Control flow graphs Instruction-level parallelism Irreducible flowgraphs Loops Node splitting Reducible flowgraphs
Content Type	Text
Resource Type	Article
Subject	Software

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Making graphs reducible with controlled node splitting

Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs (2000)

Handling irreducible loops: Optimized node splitting vs. dj-graphs (2001)

Identifying loops using DJ graphs

Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs (2001)

A new framework for elimination-based data flow analysis using DJ graphs

Making Graphs Reducible with Controlled Node Splitting (1997)

Transforming Irreducible Regions of Control Flow into Reducible Regions by Optimized Node Splitting (1998)

Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs

Handling irreducible loops: optimized node splitting versus DJ-graphs

Similar Documents

Making graphs reducible with controlled node splitting

Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs (2000)

Handling irreducible loops: Optimized node splitting vs. dj-graphs (2001)

Identifying loops using DJ graphs

Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs (2001)

A new framework for elimination-based data flow analysis using DJ graphs

Making Graphs Reducible with Controlled Node Splitting (1997)

Transforming Irreducible Regions of Control Flow into Reducible Regions by Optimized Node Splitting (1998)

Handling Irreducible Loops: Optimized Node Splitting vs. DJ-Graphs

Handling irreducible loops: optimized node splitting versus DJ-graphs