🗞️ PhD PRILIMS 🗞️ # BASIC BLOCKS AND FLOW GRAPHS # $IFT : 1

SIFT : 1 -   PARTITIONING THREE - ADDRESS INSTRUCTIONS INTO BASIC BLOCKS.

INPUT : - A SEQUENCE OF THREE ADDRESS INSTRUCTIONS.

OUTPUT : -  A LIST OF THE BASIC BLOCKS FOR THAT SEQUENCE IN WHICH EACH INSTRUCTION IS ASSIGNED TO EXACTLY ONE BASIC BLOCK.

METHOD : -  FIRST, WE DETERMINE THOSE INSTRUCTIONS IN THE INTERMEDIATE CODE THAT ARE LEADERS, THAT IS , THE FIRST INSTRUCTIONS IN SOME BASIC BLOCK. THE INSTRUCTION JUST PAST THE END OF THE INTERMEDIATE PROGRAM IS NOT INCLUDED AS A LEADER. THE RULES FOR FINDING LEADERS ARE : 

1. THE FIRST THREE - ADDRESS INSTRUCTIONS IN THE INTERMEDIATE CODE IS ' A LEADER '.

2. ANY INSTRUCTION THAT IS THE TARGET OF A CONDITIONAL OR UNCONDITIONAL JUMP IS '  A LEADER '.

3. ANY INSTRUCTIONS THAT IMMEDIATELY FOLLOWS A CONDITIONAL OR UNCONDITIONAL JUMP IS ' A LEADER '.

                ANALYTICAL CONCLUSION WITH EXAMPLE : 

 LET US CONSIDER A SOURCE CODE OF A MATRIX OF ORDER I X J ( HAVING I NO. OF ROWS AND J ON. OF COLUMNS  ) THAT TURNS A 10X10 MATRIX INTO AN IDENTITY MATRIX  [ FOR ( I = J = 10 ) ] :

for I from 1 to 10 do

        for j from 1to 10 do

                 a [ I , j ] = 0.0 ;   

for I from 1 to 10 do          

                a [ I , j ] = 1.0 ;

A source code to set a 10 x 10 Matrix to an identity matrix •

                    • A 10 x 10 MATRIX THAT IS DEFINED AS :- 

1st row = [ a1j ]  for all values of j from 1 to 10 = some non zero element may be identical or not.

2nd row = [ a2j ] for all values of j from 1 to 10 = some non zero element may be identical or not.

3rd row = [ a3j ]  for all values of j from 1 to 10 = some non zero element may be identical or not.

4th row = [ a4j ]  for all values of j from 1 to 10 = some non zero element may be identical or not.

5th row = [ a5j ]  for all values of j from 1 to 10 = some non zero element may be identical or not.

6th row = [ a6j ]  for all values of j from 1 to 10 = some non zero element may be identical or not.

7th row = [ a7j ]  for all values of j from 1 to 10 = some non zero element may be identical or not.

8th row = [ a8j ]  for all values of j from 1 to 10 = some non zero element may be identical or not.

9th row = [ a9j ]  for all values of j from 1 to 10 = some non zero element may be identical or not.

10th row = [ a10j ]  for all values of j from 1 to 10 = some non zero element may be identical or not.

       AND A 10 X 10 IDENTITY MATRIX IS DEFINED AS : 

1st row = [ a1j ]  for all values of j from 1 to 10 = 1 as first element and all other elements as zero .

2nd row = [ a2j ]  for all values of j from 1 to 10 = 1 as second element and all other elements as zero .

3rd row = [ a3j ]  for all values of j from 1 to 10 = 1 as third element and all other elements as zero . 

4th row = [ a4j ]  for all values of j from 1 to 10 = 1 as forth element and all other elements as zero .

5th row = [ a5j ]  for all values of j from 1 to 10 = 1 as fifth element and all other elements as zero .

6th row = [ a6j ]  for all values of j from 1 to 10 = 1 as sixth element and all other elements as zero .

7th row = [ a7j ]  for all values of j from 1 to 10 = 1 as seventh element and all other elements as zero .

8th row = [ a8j ]  for all values of j from 1 to 10 = 1 as eighth element and all other elements as zero .

9th row = [ a9j ]  for all values of j from 1 to 10 = 1 as ninth element and all other elements as zero .

10th row = [ a10j ]  for all values of j from 1 to 10 = 1 as tenth element and all other elements as zero .

                IN BRIEF, A IDENTITY MATRIX IS THAT WHICH HAS ALL DIAGONAL ELEMENTS AS 1 AND ALL NON - DIAGONAL ELEMENTS AS ZERO .

1)       I = 1

2)      j = 1

3)      t1 = 10 * i

4)      t2 = t1 + j

5)     t3 = 8 * t2 

6)     t4 = t3 - 88

7)     a [ t4 ] = 0 . 0

8)     j = j + 1

9)     if    j 

10)   I = I + 1 

11)   if    I 

12)   i = 1

13)   t5 = i - 1

14)   t6 = 88 * t5

15)   a [ t6 ] = 1 . 0

16)   i = i + 1

17)   if   I 

INTERMEDIATE CODE TO SET A 10X10 MATRIX TO AN IDENTITY MATRIX 

EXPLANATION OF INTERMEDIATE CODE : - 

1) INSTRUCTION 1 IS A LEADER BY RULE ONE .

2) INSTRUCTIONS 3 , 2 ,13 ARE LEADERS BY BY RULE TWO .

3) INSTRUCTIONS 10 , 12 ARE LEADERS BY RULE THREE .

REMARK : -  In the above INTERMEDIATE CODE variable t is termed as PSEUDO variable . 

Here also , ( code 3 )    t1 =  10 * i                                       

                & ( code 4 )    t2 = t1 + j   

                                  =>  t2 = 10 i + j         ( step 1 )

               &  ( code 5 )    t3 = 8 * t2          ( from step 1 )

                                  =>  t3 = 8 * ( 10 * i + j )      ( step 2 )

                                =>  t3 = 80 i + 8 j

On substracting 88 from both sides ,

                We have ,  t3 - 88 = 80 i + 8 j - 88

                    =>  t3 - 88 = 8 * ( 10  i + j - 11 )

                   =>   t3 - 88 = 8 * ( 10 i - 10 + j -1 )

                  =>   t3 - 88 = 8 * [ 10 * ( i - 1 ) +  ( j -1 ) ]

                   Now substitute ,  i - 1 = I and  j - 1 = J

We have ,   =>  t3 - 88 = 8 * [ 10 * I + J ]         ( step 3 ) 

                    =>  t3 - 88 = t4 

And for I not equal to J represents that a [ t4 ] will show all  non diagonal elements which are zero .

AGAIN , We have ,  ( code 13 )    t5 = i - 1           (step 4 )

           ( Code 14 )   t6 = 88 * t5 

                        =>     t6 =  88 * ( i - 1 )

                       =>      t6 = 8 * 11 ( i - 1 )

                      =>      t6 = 8 * ( 11 i - 11 )

                      =>      t6 = 8 * ( 10 i - 10 + i -1 )

                      =>      t6 = 8 * [ 10 ( i - 1 ) + ( i - 1 ) ]

 Now substitute,     i - 1 = i '

             We have ,   t6 = 8 * [ 10 * i '  +  i '  ]         ( step 5 )

          Now if,        I ' = i - 1 = j - 1      for all values of i = j  Right Hand Side of step 5 also equal to the Right Hand Side of step 2 & step 3 ,that is t6 will also represents the elements of 10 x 10 Matrix but diagonal elements for which are unity .

Special Remark : -  It should be mention here that values of i and j lies in between 1 & 10 including both 1 & 10 , for matrix to be of order 10 x 10 as I = no. of rows and j = no. of columns .

FLOW GRAPH FOR INTERMEDIATE CODE :-

LOOPS   : -    A SET OF NODES L IN A FLOW GRAPH IS  " A LOOP " IF L CONTAINS A NODE e CALLED ' THE LOOP ENTRY ' , SUCH THAT : 

1) e  IS NOT  'ENTRY ' , THE ENTRY OF THE ENTIRE FLOW GRAPH .

2) NO NODE IN L BESIDES E HAS A PREDECESSOR OUTSIDE L THAT IS EVERY PATH FROM  ' ENTRY ' TO ANY NODE IN L GOES THROUGH e  .

3) EVERY NODE IN L HAS A NONEMPTY PATH, COMPLETELY WITHIN L , TO e .

IN THE ABOVE IMAGERY FLOW GRAPH ,THERE ARE THREE LOOPS  : -

1) B 3 by itself . 2) B 6 by itself . 3) {B 2 , B 3 , B 4 } .

                              The first two are single nodes with an to the nodes itself . For example B 3 forms a loop with B 3 as it's entry. 

Note that the last requirement for a loop is that there be a non - empty path from B 3 to itself .This a single node like B 2 ,which does not have an edge B 2 --> B 2 , is not a loop since there is no non - empty path from B 2 to itself within {B 2} .

The third loop , L = { B 2 , B 3 , B 4 } , has B 2 as its loop entry .

NOTE THAT AMONG THESE THREE NODES, ONLY B2 HAS A PREDECESSOR,  B1 , THAT IS NOT IN L. FURTHER , EACH OF THE THREE NODES HAS A NON EMPTY PATH TO B 2 STAYING WITHIN L .

FOR EXAMPLE B2 HAS THE PATH  B 2 --> B 3 --> B 4 --> B 2 .

🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢🐒🔢

If it is too hard enjoy some tea breaks

🐱🐀▶️