﻿Problem ------- In this assignment we will learn to perform copy propagation in a basic block. Consider the following example to understand constant propagation: int main() { int a, b, c, d; a = 2; b = 3; c = a; } Observe that variable a and b have constant value viz. 2 and 3. The value taken by c is dependent on a. Since, 'a' is a constant, 'c' is also a constant. a. Write an intraprocedural pass to identify the variables with constant values. Print all the variables and their constant values at the end of each basic block. b. Bonus : When the value of one or both the operands of the right hand side is constant, modify the gimple statement. So the above example should get transformed as, a = 2; b = 3; c = 2; Procedure --------- a. 1. We have already seen how to extract the operands of a gimple statement in Assignment 2. 2. Extract LHS and RHS operand of a GIMPLE statement with the use of gimple_assign_lhs & gimple_assign_rhs1. To identify if an operand is constant, use the API INTEGER_CST alongwith TREE_CODE. To identify if an operand is variable, use the API VAR_DECL alongwith TREE_CODE. The value of integer constant e is given by ((TREE_INT_CST_HIGH (e) << HOST_BITS_PER_WIDE_INT) + TREE_INT_CST_LOW (e)) 3. At the end of each basic block print all the variables and their constant values. b. For the part b of the assignment, you have to modify the gimple statement. Here you need to transfrom the gimple statement gimple_assign to the gimple statement gimple_assign API's `build_int_cst', `gimple_build_assign', `gsi_replace' can be used for above part. More details can be found in gimple.c file. Solution -------- This assignment helps us to perform constant propagation in a basic block. a. To identify if any operand is a constant, extract the RHS operand as seen in Assignment 2 Part b. To find out the value of the constant, refer gcc internals document, page 203/694, note on INTEGER_CST. The value of integer constant e is given by ((TREE_INT_CST_HIGH (e) << HOST_BITS_PER_WIDE_INT) + TREE_INT_CST_LOW (e)) We will store the variable-value pair in some data structure. b. To replace original gimple statement by the new one, we would create our new statement by using the API `gimple_build_assign'. In order to replace the statemnt we use the API 'gsi_replace' Details about the API can be found in file 'gimple-iterator.c' Subquestions ------------ 1. Outline a strategy to perform dead code elimination after performing constant propagation. An assignment would be considered as dead code if the variable on left hand side is not used further. eg. In the below example, after perfroming constant propagation, variable `b' is not used further. Thus the statement `b = 5' is dead code. Input Program | Constant Propagation ----------------------------------------------------------- void main() | void main() { | { int a,b,c,d; | int a,b,c,d; | a = 2; | a = 2; b = 5; | b = 5; /* Dead code */ | c = a + b; | c = 7; | fn (a, c); | fn (a, c); } | }