RTCG Meeting Notes, 11 April 1995

1. Analysis requirements
   The analysis must do the following:
   • Identify run-time constants
   • Handle arbitrary CFGs
   • Identify templates
   • Determine the distinction between templates and set-up code
   • Insert appropriate stitching code In today's discussion, we discussed the identification of run-time constants for a subset of CFGs, in particular, a set of special cases.
2. Analysis examples
   During this discussion, Joel presented a few examples of well-defined CFGs and how an analysis can be applied within a standard DFA framework to identify run-time constants.
   

   Example 1:

   if (v)
       x = 0;
   else
       x = 1;
   y += x;
   

   where v is a dynamic variable.
   x is a derived dynamic variable, so the following code should be produced:

   stich (template1);
   
   template1:
   if (v)
       x = 0;
   else
       x = 1;
   y += x;
   

   
   

   Example 2:

   if (r)
       x = 0;
   else
       x = 1;
   y += x;
   

   where r is a run-time constant
   x is a derived run-time constant, so the following code should be produced:

   if (r)
       x = 0;
   else
       x = 1;
   stich (template1, x->rtconst1);
   
   template1:
   y += rtconst1;
   

   • Simple case
     The simple case is characterized as a branch and a merge pair which have single entry, single exit regions on both the true and false paths of the branch. These regions could internally have more complex structures, but must be single entry, single exit with respect to the branch and merge. In the diagram below, A and B are the single entry, single exit regions.

     	+---------------+
     	|    if (sym)	|
     	+---------------+
     		/\
     	     T /  \ F
     	      /    \
            -------	  -------
            (     (    (     (      
            )     )    )     )
            (  A  (    (  B  (      
            )     )    )     )
            -------	  -------
     	    \      /
     	     \    /
     	       \ / 
     	+---------------+
     	|    		|
     	+---------------+
     

   • An IDFA can be used to identify RTC. At this point, for the simple case, we are assuming that you can identify loops and the single entry, single exit regions via some black box.
   • A set element corresponds to a pair of a symbol and the rtl statement which binds a value to it {symbol:rtl}
     • The root set is a run-time constant
     • Bottom is a run-time constant
     • For statements of the form:

       	
       	x = constant; 		Add x to the set
       	x = y op z;		Add x only if y, z are in the set
       

     • At a branch, propagate the info to both paths
     • At a merge, we use the following: The general rule is to use the intersection.
       If a symbol is in both incoming sets and the symbol is actually a run-time constant, we can use a special rule. There can be two cases for this special rule:
       1. Incoming sets: {r:a} and {r:a} => {r:a}
       2. Incoming sets: {r:a} and {r:b} => {r:d}, where d corresponds to the merge point
       In example 3, below, the first rule is demonstrated for the symbol rtc. The second rule is demonstrated for symbol x.
   Example 3:

   
   	     {rtc:q}
   	+---------------+
   	|    if (sym)	|
   	+---------------+
   		/\ {rtc:q}
   	     T /  \ F
   	      /    \
          +-----+	  +-----+
        b:| x=0 |  c:| x=1 |      
          +-----+	  +-----+
   {x:b,rtc:q} \      / {x:c,rtc:q}
   	     \    /
   	       \ / 
   	+---------------+
         d:|    y =+ x 	|
   	+---------------+
   	   {x:d,rtc:q}
   

3. Stitching
   Set-up code can be handled by leaving the CFG intact, and adding stitch instructions as appropriate. The stitch instructions are added at the end of the single entry, single exit regions.
   • Handling switch statements
   • For simple switch statments, where the various case paths are mutually exclusive, the above technique for IFs can still be used.
   • In the general case, however, switches may have fall-thru cases and may also introduce unstructured graphs. A general case technique still has to be determined.
   • Code duplication is an option to handle fall-thru branches, but code explosion is a concern.
   • The Multiflow compiler provides an option to convert switches to nested ifs. For some switch statements, this may be useful.