معالجات دقيقة - ج

441805915
‫مازن محمد النجيمي‬
Given the following segment of source code:
For ( x = 1 ; x <= 10 ; x++ )
For ( y = 20 ; y >= 5 ; y-- )
z = x + y*17 ;
y = x/y + x ;
Symbol Table
Line Lexeme Token Attributes Values
1 { 1 Keyword
2 for 5 Keyword
3 ( 51 Punctuation
4 x 80 Identifier
5 = 29 Operator
6 1 90 Number 00000001
7 ; 53 Punctuation
8 <= 32 Operator
9 10 90 Number 00001010
10 ++ 27 Operator
11 ) 52 Punctuation
12 y 80 Identifier
13 20 90 Number 00010100
14 >= 34 Operator
15 5 90 Number 00000101
16 -- 28 Operator
17 z 80 Identifier 000010001
18 + 25 Operator
19 * 22 Operator
20 17 90 Number
21 / 23 Operator
22 } 2 Keyword
Token File
Line Cal1 Cal2 Cal3 Cal4
1 1 5 80 4
2 29 90 80 4
3 32 90 53 80
4 4 27 52 5
5 51 80 12 29
6 90 53 80 12
7 34 90 53 80
8 12 28 52 80
9 17 29 80 4
10 25 80 12 22
11 90 53 80 12
12 29 80 4 23
13 80 12 25 80
14 4 53 2 $
15
Syntax Analyzer:
The syntax analyzer builds a parse tree representing the structure of
the code. This tree structure cannot be directly displayed in a table
format.
the parse tree:
For
/\
/ \
x For
/\
/ \
y Assign
/\
z +
/\
x *
/\
y 17
Intermediate Code Phase :
This phase might translate the source code into an intermediate
representation. Here's an example of what the intermediate code could
look like:
1: x = 1
2: label_start
3: if x > 10 goto label_end
4: y = 20
5: loop
6: z = x + y * 17
7: y = x / y + x
8: y = y - 1
9: if y >= 5 goto loop
10: x = x + 1
11: goto label_start
12: label_end
L1 x =1
L2 IF x < 10
L3 goto L6
L4 T1 =0
L5 goto L7
L6 T1 =1
L7 IF x ==10
L8 goto L11
L9 T2 =0
L10 goto L12
L11 T2=1
L12 T3 = T1 || T2
L13 IF T3 == 1
L14 goto L16
L15 goto L21
L16 y==20
L7 IF y > 5
L18 goto L21
L19 T1 =0
L20 goto L22
L21 T1 =1
L22 IF y ==5
L23 goto L25
L24 T2 =0
L25 goto L27
L26 T2=1
L27 T3 = T1 || T2
L28 IF T3 == 1
L29 goto L31
L30 goto L36
L31 M1 = x + y*17
L32 z = M1
L33 goto L2
L34 m2 =x/y+x
L35 y=m2
L36 goto L2
Code Optimization Phase :
To optimize the given source code segment, we can make the following
improvements:
1. Constant Folding: Evaluate constant expressions at compile time.
2. Loop-Invariant Code Motion: Move loop-invariant calculations
outside the loop to reduce redundant computations.
3. Strength Reduction: Replace expensive operations with cheaper
alternatives.
Here is the optimized version of the source code segment:
For ( x = 1 ; x <= 10 ; x++ ) {
int temp1 = x * 17;
int temp2 = x / x;
for ( y = 20 ; y >= 5 ; y-- ) {
z = x + y * temp1;
y = temp2 + x;
In this optimized version:
•The multiplication by 17 and division by x are moved outside the inner
loop as they are loop-invariant.
• The division by x simplifies to 1, which reduces the computation.
•The temporary variables L1 and L2 hold the precomputed values for x
* 17 and x / x respectively, reducing redundant calculations inside the
loop.
Code generation phase.
Assuming the compiler applies the common subexpression elimination
optimization as discussed earlier, here's a possible code generation
phase for the provided code:
Target Architecture:
For simplicity, let's assume the target architecture uses assembly-like
instructions.
Generated Code:
assembly
// Load initial value for x (1)
LOAD_CONST 1
STORE x
// Calculate x / y (outside the loop - optimized)
LOAD x
LOAD y // Assuming y has a valid initial value here (e.g., 20)

DIV
STORE temp
// Outer loop start (label)
L1:
// Inner loop start (label)
L2:
// Calculate z using pre-computed temp
LOAD x
LOAD y
LOAD_CONST 17
MUL
ADD
STORE z
// Calculate y using temp
LOAD temp
LOAD x
ADD
STORE y
// Decrement y
LOAD y
LOAD_CONST 1
SUB
STORE y
// Check inner loop condition
LOAD y
LOAD_CONST 5
BGE L2 // Branch if Greater than or Equal to (jump back to L2)
// Increment x
LOAD x
LOAD_CONST 1
ADD
STORE x
// Check outer loop condition
LOAD x
LOAD_CONST 10
BLE L1 // Branch if Less than or Equal to (jump back to L1)
// Program ends
```
Explanation:
1. Load constants:Load the constants 1 and 17 into registers.
2. Optimized calculation:Divide `x` by `y` and store the result in `temp`
(calculated outside the loop).
3. Outer loop: Label `L1` marks the start of the outer loop.
4. Inner loop:Label `L2` marks the start of the inner loop.
5. z calculation:Use the pre-calculated `temp` to efficiently calculate `z`.
6. y update:Update `y` by adding `temp` and `x`.
7. Decrement y: Decrement `y` by 1.
8. Inner loop condition: Branch back to `L2` (continue inner loop) if `y`
is greater than or equal to 5.
9. Increment x: Increment the loop counter `x` by 1.
10. Outer loop condition:Branch back to `L1` (continue outer loop) if `x`
is less than or equal to 10.
11.Program end: The program execution ends here if the outer loop
completes.

معالجات دقيقة - ج

Uploaded by

Copyright:

Available Formats

معالجات دقيقة - ج

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

معالجات دقيقة - ج

Uploaded by

Copyright:

Available Formats

441805915

‫مازن محمد النجيمي‬

Given the following segment of source code:

For ( x = 1 ; x <= 10 ; x++ )

For ( y = 20 ; y >= 5 ; y-- )

Line Cal1 Cal2 Cal3 Cal4

The syntax analyzer builds a parse tree representing the structure of

the code. This tree structure cannot be directly displayed in a table

the parse tree:

Intermediate Code Phase :

This phase might translate the source code into an intermediate

representation. Here's an example of what the intermediate code could

3: if x > 10 goto label_end

9: if y >= 5 goto loop

11: goto label_start

L10 goto L12

L14 goto L16

L15 goto L21

L18 goto L21

L20 goto L22

L25 goto L27

L29 goto L31

L30 goto L36

Code Optimization Phase :

2. Loop-Invariant Code Motion: Move loop-invariant calculations

outside the loop to reduce redundant computations.

3. Strength Reduction: Replace expensive operations with cheaper

Here is the optimized version of the source code segment:

For ( x = 1 ; x <= 10 ; x++ ) {

int temp1 = x * 17;

for ( y = 20 ; y >= 5 ; y-- ) {

In this optimized version:

•The multiplication by 17 and division by x are moved outside the inner

loop as they are loop-invariant.

• The division by x simplifies to 1, which reduces the computation.

•The temporary variables L1 and L2 hold the precomputed values for x

* 17 and x / x respectively, reducing redundant calculations inside the

optimization as discussed earlier, here's a possible code generation

phase for the provided code:

For simplicity, let's assume the target architecture uses assembly-like

// Load initial value for x (1)

// Calculate x / y (outside the loop - optimized)

LOAD y // Assuming y has a valid initial value here (e.g., 20)

// Outer loop start (label)

// Inner loop start (label)

// Calculate z using pre-computed temp

// Calculate y using temp

// Check inner loop condition

BGE L2 // Branch if Greater than or Equal to (jump back to L2)

// Check outer loop condition

BLE L1 // Branch if Less than or Equal to (jump back to L1)

1. Load constants:Load the constants 1 and 17 into registers.

2. Optimized calculation:Divide `x` by `y` and store the result in `temp`

(calculated outside the loop).

5. z calculation:Use the pre-calculated `temp` to efficiently calculate `z`.

6. y update:Update `y` by adding `temp` and `x`.

7. Decrement y: Decrement `y` by 1.

is greater than or equal to 5.

9. Increment x: Increment the loop counter `x` by 1.