|
Vol: 59(73) No: 2 / December 2014 Data Flow Graph Generation of Nested Loops from Imperative High Level Description Péter Arató Department of Control Engineering and Information Technology, Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics, 2 Magyar tudósok körútja 2., 1117 Budapest, Hungary, e-mail: arato@iit.bme.hu, web: http://hls.iit.bme.hu Gergely Suba Department of Control Engineering and Information Technology, Budapest University of Technology and Economics, Faculty of Electrical Engineering and Informatics, 2 Magyar tudósok körútja 2., 1117 Budapest, Hungary, e-mail: suba.gergely@iit.bme.hu Keywords: high-level synthesis, system-level synthesis, data flow graph, nested loops, static single assignment, GCC, GIMPLE Abstract The first essential task in high-level or system-level synthesis is to process the source code of the input task and produce an intermediate representation. This representation is a data flow graph description in most cases. The further steps attempt optimizing the data flow graph and transform the algorithm into an output representation (usually Verilog, VHDL for FPGA target, and ASM, C for CPU target). Nowadays, the imperative languages are dominant in the field of software technology. The aim of this paper is to present a method for compiling an imperative language description into a hierarchical data flow graph, which is able to represent also nested loops in a beneficial way. For practical reasons, C has been chosen as input for demonstrating the method, because it is one of the most widely used language in software and hardware design field. For parsing and analyzing the C code, the frontend of the GNU Compiler Collection (GCC) is applied. The existing data flow graph generation solutions suffer from the difficulty of handling loop nest hierarchy. We present a method, which transforms systematically the GCC produced control- and data flow like description (called GIMPLE) into a hierarchical data flow graph representation by handling the nested loops. The whole method is illustrated on a C source code example and on the intermediate descriptions of the conversation steps. References [1] J. Merrill, “Generic and gimple: A new tree representation for entire functions,” In Proceedings of the GCC Summit, 2003. [2] R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck, “Efficiently computing static single assignment form and the control dependence graph,” ACM Trans. Program. Lang. Syst., vol. 13, no. 4, pp. 451–490, 1991. [3] R. M. Stallman and G. D. Community, “Gnu compiler collection internals. for gcc version 4.8.0.” 2010. [4] D. Novillo, “Tree ssa - a new optimization infrastructure for gcc,” 2004. [5] L. Semeria and G. D. Micheli, “Spc: synthesis of pointers in c application of pointer analysis to the behavioral synthesis from c. in computer-aided design,” ICCAD 98. Digest of Technical Papers. 1998 IEEE/ACM International Conference, pp. 340–346, 1998. [6] L. Sem´ eria, K. Sato, and G. De Micheli, “Synthesis of hardware models´ in c with pointers and complex data structures,” IEEE Trans. Very Large Scale Integr. Syst., vol. 9, no. 6, pp. 743–756, Dec. 2001. [7] J. Zhu and S. Calman, “Context sensitive symbolic pointer analysis,” Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, vol. 24, no. 516–531, April 2005. [8] H. Hwang, T. Oh, H. Jung, and S. Ha, “Conversion of reference c code to dataflow model h.264 encoder case study,” In Design Automation, Asia and South Pacific Conference on, p. 6, 2006. [9] N. Kavvadias and K. Masselos, “Hardware design space exploration using hercules hls,” in Proceedings of the 17th Panhellenic Conference on Informatics, ser. PCI ’13. New York, NY, USA: ACM, 2013, pp. 195–202. [10] N. Kavvadias, V. Giannakopoulou, and K. Masselos, Embedded Systems - Theory and Design Methodology. InTech, 2012, ch. FSMD-Based Hardware Accelerators for FPGAs. [11] P. Coussy, C. Chavet, P. Bomel, D. Heller, E. Senn, and E. Martin, “Gaut: A high-level synthesis tool for dsp applications,” in High-Level Synthesis, P. Coussy and A. Morawiec, Eds. Springer Netherlands, 2008, pp. 147–169. [12] G. Suba, “Hierarchical pipelining of nested loops in high-level synthesis,” Periodica Polytechnica Electrical Engineering and Computer Science, 2014, 58 (3) pp. 81–91. [13] G. Suba, “A data flow graph generation method starting from C description by handling loop nest hierarchy,” IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI), 2014, pp. 69-274. |