Article Preview
Top1. Introduction
For exploitation of instruction level parallelism through compiler optimization it is very important to consider the code optimization and code generation phases efficiently. Instruction scheduling and register allocation (Silva et al., 2012) have great importance in code generation. Recent studies (Castañeda Lozano et al., 2012; Tang et al., 2013) show a lot of efforts on integrated approaches for instruction scheduling and register allocation. The combinations of instruction scheduling and register allocation have been discussed in section 3. The key aspect of proposed technique is the modeling of the hardware resources by redefining the MDES of trimaran infrastructure (Chakrapani et al., 2015) and comparison of results with LLVM compiler. The algorithm is implemented for instruction scheduling and register allocation based on subgraph isomorphism theory (Kumar and Mishra, 2014) on the trimaran compiler for HPL-PD architecture (Kathail, 2000). For the purpose of feasibility and flexibility, the integrated approach is designed for the HPL-PD architecture on the trimaran compiler. This paper is organized as follows: Section 2 presents related work, Section 3 presents use of instruction scheduling and register allocation, Section 4 presents HPL-PD Architecture, Section 5 presents proposed algorithm for instruction scheduling and register allocation, Section 6 presents MDES description steps, Section 7 represents the Experimental results, Section 8 represents the comparison of some of the results with MIPS (Chow, 1998) architecture on LLVM compiler (Lattner and Adve, 2004), Section 9 represents the conclusion and future scope.
The advantage of register allocation is the speed. (Magno and Pereira, 2014) pointed that Register allocation is the optimization technique that can increase efficiency of algorithm up to 250%. As the computers have limited number of CPU registers therefore it is not possible to assign all variables to the registers. A 32-bit variable spilled to memory avails an allocation of 32 bit of stack space. Such variable has a much slower processing speed then a variable in register. (Chaitin et al., 1981) pointed that the spill free register allocation is an NP-Complete problem. They proved that any graph is the interference graph of a program. Graph coloring and Linear scan approaches have been used for register allocation. (Sarkar and Barik, 2007) added a recent work to Linear Scan algorithms called Extended Linear Scan. It applies copy and swap instructions along the source program and uses minimal number of registers to compile the program.
The graph coloring (Björklund et al., 2008) is seen as the optimal approach for register allocation. It has been adopted by several modern compilers like LLVM and Trimaran. A simpler approach linear scan has also been used for the same. The fact by which the minimal coloring to a graph was proved to be NP-Complete (Karp et al., 1972). Subgraph isomorphism is defined as a generalization of graph isomorphism problem which asks whether a graph G isomorphic to graph H. (De La Higuera et al., 2013) computed a subgraph isomorphism problem that has a query complexity of Ω(n3/2). Subgraph isomorphism is seen as a very general form for pattern matching and it provides a platform for several important graph problem, like Hamiltonian paths (Wang et al., 2014), shortest path (Elkin, 2005), cliques (Cheng et al., 2011), etc.