Identifying Program Loop Nesting Structures during Execution of Machine Code

Yukinori SATO  Yasushi INOGUCHI  Tadao NAKAMURA  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E97-D   No.9   pp.2371-2385
Publication Date: 2014/09/01
Online ISSN: 1745-1361
DOI: 10.1587/transinf.2013EDP7455
Type of Manuscript: PAPER
Category: Computer System
Keyword: 
dynamic loop nests,  loop-call context tree,  on-the-fly loop detection,  

Full Text: PDF(1.9MB)
>>Buy this Article


Summary: 
This paper presents a mechanism for detecting dynamic loop and procedure nesting during the actual program execution on-the-fly. This mechanism aims primarily at making better strategies for performance tuning or parallelization. Using a pre-compiled application executable machine code as an input, our mechanism statically generates simple but precise markers that indicate loop entries and loop exits, and dynamically monitors loop nesting that appears during the actual execution together with call context tree. To keep precise loop structures all the time, we monitor the indirect jumps that enter the loop regions and the setjmp/longjmp functions that cause irregular function call transfers. We also present a novel representation called Loop-Call Context Graph that can keep track of inter-procedural loop nests. We implement our mechanism and evaluate it using SPEC CPU2006 benchmark suite. The results confirm that our mechanism can successfully reveal the precise inter-procedural loop nest structures from all of SPEC CPU2006 benchmark executions without any particular compiler support. The results also show that it can reduce runtime loop detection overheads compared with the existing loop profiling method.