Tags:
create new tag
view all tags

# Wiki page of Team 3 (Vectorizers) of CS 2/455, Spring 2008

http://www.cs.rochester.edu/twiki/bin/view/Main/ProjectHome#The_Last_Mile_Group_Competition • Vectorizers

## Team Members

• Tagyoung Chung (tester/developer)

## Project Milestones

• Monday, March 24, groups formed, roles assigned.
• Monday, March 24, wiki page created.
• Friday, March 28, design and implementation strategy reviewed. Gcc gurus met.
• Friday, April 4, first feedback from the hidden benchmarks.
• Wednesday, April 9, second feedback from the hidden benchmarks.
• Monday, April 14, midnight, competition concludes.

## Words of Wisdom to Guide Us

• Celui qui étudie pour appliquer au bon moment n'y trouve-t-il pas de la satisfaction? --- Confucius
• Kids, you tried your best and you failed miserably. The lesson is: never try. --- Homer Simpson
• Comprehensive exams are more important than Compiler Project! --- Naushad UzZaman
• Have a break, Do compiler Have a Kit Kat! --- Naushad UzZaman

## Other Teams

```Team 1:

Konstas (gcc guru/developer)

Team 2:

Amal (developer/gcc guru)
Stan (reporting/tester)

Team 3:

Tag (tester/developer)

Team 4:

Jonathan (developer/gcc guru)
Yi (reporting/tester)
```

## Code History

http://www.cs.rochester.edu/twiki/bin/view/Sandbox/CS455Team3wiki#Update_History ## Meeting Notes

### Monday, March 24, 3:30 PM

We met, decided team name and planned what to do. We have def-graph, dead-code elimination working fine. We want to extend our value numbering and the constant propagation. We want to meet again on Wednesday, March 26, after class.

### Tuesday, March 25, 7:10 PM

Handle cases like, a*1 = a; a^0 = 1; a/a = 1; a + 0 = a; two consecutive line with same modify expression.

### Tuesday, March 25, 11:30 PM

Things to check in value numbering:
• global variables
```int a;
void foo()
{
a = 7;
}
int main()
{
int b,c,d;
printf("Input a,b,c,d\n");
scanf("%d %d %d %d", &a, &b, &c, &d);
a = b - c;
b = a + d;
c = b - c;
foo();
d = a + d;
return 0;
}
```

• multiple definition and one of them get modified!
```b = a + c;
g = a + c;
e = a + c;
f = a + c;
=>
b = a + c;
g = b;
e = g;
f = e;
```
• scanf (WORKS)
```case 1:
b = a + 3;
scanf("%d", &a);
g = a + 3;
=>
a.0 = a;
b = a.0 + 3;
scanf (&"%d", &a);
a.0 = a;
g = a.0 + 3;

case 2:
b = a + c;
scanf("%d %d", &a, &c);
g = a + c;
=>
a.0 = a;
c.1 = c;
b = a.0 + c.1;
scanf (&"%d %d", &a, &c);
a.0 = a;
c.1 = c;
g = a.0 + c.1;

code to get the variables from scanf arguments:
if(strcmp(callee_name, "scanf") == 0)
{
tree parms = TREE_OPERAND(stmt, 1); //get argument from scanf statement
for(parms = TREE_CHAIN(parms); parms; parms = TREE_CHAIN(parms)) //first in the chain is " " so we don't need that
{
tree argument = TREE_VALUE(parms); //this gets you '&a'
argument = TREE_OPERAND(argument, 0); //this gets you actual variable 'a'
}
}

```
• constant (WORKS)
```a = b + 17;
c = 17;
e = b + c;
```
• array (WORKS)
```a = ar + br;
b = ar + br;
=>
D.1537 = ar;
D.1538 = br;
a = D.1537 + D.1538;
D.1537 = ar;
D.1538 = br;
b = a;
```
• DVN or EVN

### Wednesday, March 26, 12:59 AM

How do you handle constant propagation with the loop?
• code
```int main(void)
{
int a, b;

for(a = 0; a < 10; a++)
b = b + 1;
}
```

• gimplified
```main ()
{
int b;
int a;

< bb 2 >:
a = 0;
goto < bb 4 > (< L1 >);

< L0 >:;
b = b + 1;
a = a + 1;

< L1 >:;
if (a < = 9) goto < L0 > else goto < L2 >

< L2 >:;
return;
}

```
• More complex case:
```a = 5;
b = 3;

<L1>
a = b  * 5;
b = b + 1;
goto (<L1 >)
```

### Thursday, March 27, 08:00 PM

- remove statement like, a = a; - handle expressions like, b = a * 2; => b = a + a; b = a / a; => b = 1;

- Makefile to compile all test files at once

- simple script to run all test cases and compare them against correct results

- located under:

/home/vax3/u31/chung/classes/2008Spring/csc455/project

### Friday, March 28, 09:00 PM

- need to modify value numbering in cases where a = d and a and d already have a same value number, this statement can be removed. this will greatly improve programs with scanf statement. (it will take out 10 statements in cases of trivia.c)

- initial_optimization_pass() (bug-fixed) resulted in slight improvement of trivia.c

- gimplified open test cases (unoptimized and -O3) are in /u/chung/classes/2008Spring/csc455/open_test_cases (to see which improvements we can make)

### Saturday, March 29, 09:00 PM

- added the module "eliminate redundant assignment"

### Tuesday, April 1, 08:00 PM

Things we need to add in the "eliminate redundant assignment" pass:

• check index of array (WORKS)
works for many cases, but doesn't work for fibonacci!!

example: fibonacci.c

```val.1 = val;
D.1538 = array[val.1];
=>
D.1538 = array[val];
```

also modify for the lhs of the array index.

```val.1 = val;
array[val.1] = a;
=>
array[val] = a;
```

• handle array (WORKS)
example: sort.c
```idx.0 = idx;
D.1551 = array_4[idx.0];
print (D.1551);
=>
print (array_4[idx])
```

• return statement (WORKS)
example: automaton.c
```D.1540 = n;
return D.1540;
=>
return n;
```

• conditional statement (WORKS)
```a.0 = a;
if(a.0<=0) then do something
=>
if(a<=0) then do something
```

• printf statement (WORKS)
```idx.0 = idx;
D.1551 = array_4[idx.0];
print (D.1551);
=>
print (array_4[idx])
```

• function call (WORKS)
example: automaton.c
```D.1545 = getnextdigit ();
a = D.1545;
=>
a =  getnextdigit ();
```

• type casting (WORKS)
example: automaton.c
```D.1572 = (int) D.1571;
a[D.1555] = D.1572;
=>
a[D.1555] = (int) D.1571;
```

• multiplication and division by same number! or addition and subtraction from same number!
example: binrep.c
```D.1527 = n / 2;
D.1528 = D.1527 * 2;
=>
D.1528 = n;
```
algo:
```if op2 of rhs is const
find op1's definition
if op1's definition's op2 is same const with opposite sign
lhs (current stmt) = op1_of_rhs_of op1's defn
```

### Wednesday, April 2, 3:00 AM

Next TODO on value numbering

• global variables (WORKS)
```int a;
void foo()
{
a = 7;
}
int main()
{
int b,c,d;
printf("Input a,b,c,d\n");
scanf("%d %d %d %d", &a, &b, &c, &d);
a = b - c;
b = a + d;
c = b - c;
foo();
d = a + d;
return 0;
}
```

• multiple definition and one of them get modified!
```b = a + c;
g = a + c;
e = a + c;
f = a + c;
=>
b = a + c;
g = b;
e = g;
f = e;
```

### Thursday, April 3, 9:00 PM

• performance decreased with updating the dynamic_bb and global value number (in sort)

### Friday, April 4, 12:08 AM

Things we are missing:
• automaton.c
- in getnextdigit(), in :;
```  n.0 = n;
n.1 = (unsigned int) n.0;
(should be)  =>
n.1 = (unsigned int) n;
```

Mering printf, "smart" redundancy elimination in progress.

### Sunday, April 6, 2:50 PM

• In merging printf, if we see any function (just function call or rhs is a function), we have to consider that there might be a redefinition of a variable. So we don't merge that printf with previous printf.
• Oops! We actually can't do the multiplication and division by same number! It won't help us, and also will produce wrong answers. n is an integer and they are checking if it is actually even or odd.
```  D.1527 = n / 2;
D.1528 = D.1527 * 2;
```

### Sunday, April 6, 3:00 PM

Next priority:

• Tag and Naushad: Try to fix the problems in hidden test cases
• Chris: i. Merging printf; ii. What else we can improve to catch Foo team! They are in first position again in few cases. Check the programs that we are behind Foo! team.

### Monday, April 7, 6:00 AM

• Merging printf worked properly and it improved the performance.

### Monday, April 7, 3:00 PM

things we are doing:
```
a = array[i];
b = a + c;
=>
b = array[i] + c;
```
this is not permitted, but things we can do is:
```
a = array[i];
b = a;
=>
b = array[i];
```

### Monday, April 7, 4:45 PM

• Places we cannot optimize:
```automaton.c =>  D.1539 = (unsigned int) n.0 - 0ffffffff;
fibonacci.c =>   D.1543 = D.1540 + fib (D.1541);
mandel.c => D.1533 = square (real) + square (imag);   also    D.1570 = absval (real) + absval (imag);
jacobi.c =>  D.1550 = (double) i + 1.2e+1;   also   D.1562 = b[D.1557] + b[D.1560];
a[D.1548] = (int) D.1552;   OR   b[D.1555] = a[D.1555];   [i guess even this is illegal according to the rule..!]
movingedge.c => D.1554 = V[D.1550] * nbr_5[D.1552];
sort.c => printf (&"%d\n", array_1[idx]);   also     if (array_1[idx] > array_1[D.1571]) goto ; else goto ;
sort_insertion.c => data[D.1538] = data[j];
```

### Tuesday, April 8, 1:18 AM

• Made invalidation of global variables for value numbering more clever so it can handle cases like this:
```int a;

foo ()
{
voodoo magic ...
}

main ()
{
b = a + c;                           b = a +c;
d = a + c;                           d = b;
foo ();                 ==>          foo ();
g = a + c;                           g = a +c;
}
```

### Wednesday, April 9, 9:00 PM

• Removed all "illegal" operations, which we didn't know as illegal. We have same result as Segmentation Fault team. We are falling behind in few cases and these are the cases we are missing.

- for some reason, we missed this obvious case!!!

tax.c

```
g = e + f;
line5 = g;
(it should be) =>
line5 = e + f;
```

• We shouldn't be doing this. Need to check these cases when LHS is array:

sort_insertion.c (WORKS)

```
D.1540 = data[j.1];
data[D.1538] = D.1540;
=>
data[D.1538] = data[j];
```

fibonacci.c (WORKS)

```
D.1543 = D.1540 + D.1542;
array[val.1] = D.1543;
=>
array[val] = D.1540 + D.1542;
```

jacobi.c (WORKS)

```
a[D.1548] = (int) D.1552;
b[D.1548] = (int) D.1552;
b[D.1555] = a[D.1555];
```

We are now missing few obvious optimization now:

```
D.1538 = c;
s = s / D.1538;
(should be) =>
s = s / c;
```

```  D.1539 = b;
s = D.1539 + s;
(should be) =>
s = b + s;
```

```
D.1541 = c;
s = D.1541 + s;
(should be)=>
s = c + s;
```

### Thursday, April 10, 3:00 AM

• printf in reverse, will improve one in tax.c (WORKS and improved performance)

L32 of tax.c

```  printf (&"%d\n", line6);
D.1566 = line8 + line7;
printf (&"%d\n%d\n%d\n%d\n%d\n%d\n%d\nThank you for using ez-tax.\n", D.1566, line10, b, e, d, deadline11, deadline12);
```
We can convert this to:
```
D.1566 = line8 + line7;
printf (&"%d\n%d\n%d\n%d\n%d\n%d\n%d\n%d\nThank you for using ez-tax.\n", line6, D.1566, line10, b, e, d, deadline11, deadline12);
```

We are missing it, because we traverse all statements and then check the previous printf (if any of the variables in printf is modified upto previous printf block then we don't merge with the previous stmt), instead of that if we check the next printf, we will be able to get this optimization as well, which will give equal performance as Seg Fault in tax.c, i.e. 114.

• possible error in function propagation
```int i; (global)
foo(){
i++;
}

main(){
a = foo();
b = a;
c = a;
print (b, c);
}
```
We might convert this to:
```
a = foo();
b = foo(); [expecting 'a' will be removed in the deadcode elimination => a will be removed eventually]
c = foo(); [expecting 'b' will be removed in the deadcode elimination => but b wont be removed!!! incrementing global 'i' twice from foo()]
print (b, c);
```

If we don't do the function propagation then the performance decreases. To solve this problem, best way to do is, do function propagation only for temporary variables, e.g. handle the following cases:

```
D.1545 = getnextdigit ();
a = D.1545;
(variable with D.something) =>
a = getnextdigit ();
```
but don't function propagate on these cases:
```  a = foo();
b = a;
c = a;
```

### Friday, April 11, 2:00 AM

Last day we spent our time undo'ing what we did last few days, as these are "illegal" http://www.cs.rochester.edu/twiki/bin/view/Main/ProjectHome#Competition_Rules . Fixing those we faced some unexpected stupid errors, which took all of today to fix! But we got few extra things done.
• We are doing the merging printf for both direction now, forward and backward, i.e. we will have one pass with previous implementation and another pass with newer implementation. This improved in tax.c.
• We have to fix the function propagation now, described above. Now we are not doing the function propagation at all, which decreased performance in every cases But this is the first priority now.

### Friday, April 11, 3:00 AM

• function propagation WORKS now
• We are falling behind everyone in sort.c. Possible case we are missing are:

In main()

```
L10:;
= = =
D.1571 = idx + 1;
= = =
L11:;
= = =
D.1571 = idx + 1;
= = =
```

D.1571 is redefined with the same value, so we can skip it.

• implement the obvious case of copy propagation that we missed before
tax.c
```
g = e + f;
line5 = g;
(it should be) =>
line5 = e + f;
```

### Friday, April 11, 4:00 AM

In sort.c main()
```
L10:;
= = =
D.1571 = idx + 1;
= = =
L11:;
= = =
D.1571 = idx + 1;
= = =
```

D.1571 is redefined with the same value, so we can skip it.

Possible solution for this problem could be:

```
for each bb
for each stmt in bb
if var1 is defined (var1 = var2 + var3)
find the redefinition of var1 in the rest of block and also the successors of the current blocks
if the redefinition is same as definition (var1 = var2 + var3)
then remove the redifiniton
```

### Friday, April 11, 5:00 AM

Fix the array propagation in the value numbering. Doing some illegal operations in sort.c (e.g. Array1 = Array2), which needs to be fixed.

before value numbering =>

```  array_3 = 5;
array_3 = 5;
```

after value numbering =>

```  array_3 = 5;
array_3 = array_3;
```

A = A is apparently illegal.

### Friday, April 11, 3:14 PM

From Xiaoming:

Congratulations, Vectorizers. Your code passes all the hidden benchmarks now. Please see the details in the ranking wiki-page. Maybe you still need to do some undo work but remember to make the code stable.

Xiaoming

Working on compiler is fun and relaxing! When we do make and make install (which takes a loooottttt of time, even in new dual core machines!), we spend the time watching funny YouTube videos. Here are just few of them!

• Matumbo Goldberg
http://www.youtube.com/watch?v=RCKLYCi2UJk • Ameriquest - All 5 Funny Commercials
http://www.youtube.com/watch?v=angJGfCSuUI • Phony Photo Booth
http://www.youtube.com/watch?v=wsSJ1c7nFWE • naughty photo booth
http://www.youtube.com/watch?v=pJpUX-nyWbU • Honda Commercial
http://www.youtube.com/watch?v=xcr6ZIVi-Vg • Funny commercial clip
http://www.youtube.com/watch?v=t0kz8MCxq6A • outrageously funny commercials
http://www.youtube.com/watch?v=8cyAqEjZ2as • FUNNY COMMERCIALS !!!!!!!!!!!!!!!!
http://www.youtube.com/watch?v=Ri3XqFzcc_k • World's Most Amazing Trick Shot!
http://www.youtube.com/watch?v=2XTGBOKqccw • Worlds most amazing Trick By David Copperfield
http://www.youtube.com/watch?v=buYBsk8XMXk • Kobe jumps over a moving Aston Martin?!?
http://www.youtube.com/watch?v=FodyWz9d6vM • Kobe biting MJ
http://www.youtube.com/watch?v=74zX6R2qbrs • Kobe Bryant's Top 10 Plays of 2007
http://www.youtube.com/watch?v=RAkjaQoG3bY • VW Phaeton - Shadowplay Commercial
http://www.youtube.com/watch?v=4o_me2Zz7q4 • Phony photobooth [This was really funny video, but its unavailable now ]
http://www.youtube.com/watch?v=eLM3-0UlyCE Topic revision: r49 - 2008-04-28 - NaushadUzZaman Home   Main Web  P P View Edit      Copyright © 2008-2020 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback