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

Task

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

http://www.cs.rochester.edu/twiki/bin/view/Main/OpenTable

Previous wiki page: http://www.cs.rochester.edu/twiki/bin/view/Sandbox/CS455Team3wiki

Team Name

  • Vectorizers

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

Team Members

  • Chris Tice (lead/developer/gcc guru)
  • Tagyoung Chung (tester/developer)
  • Naushad UzZaman (reporting/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.

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"[0], &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"[0], &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[3] + br[3];
b = ar[3] + br[3];
=>
D.1537 = ar[3];
D.1538 = br[3];
a = D.1537 + D.1538;
D.1537 = ar[3];
D.1538 = br[3];
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"[0], 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"[0], 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"[0], 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"[0], 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 frown 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[3] = Array2[4]), which needs to be fixed.

before value numbering =>

  array_3[0] = 5;
  array_3[1] = 5;

after value numbering =>

  array_3[0] = 5;
  array_3[1] = array_3[0];

A[1] = A[2] 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

Code History

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

YouTube Videos

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 now unavailable now frown ]
http://www.youtube.com/watch?v=eLM3-0UlyCE

Other Teams



Team 1:

Rongrong (lead/developer/reporting)
Konstas (gcc guru/developer)
Tivadar (developer/tester)

Team 2:

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

Team 3:

Chris (lead/developer/gcc guru)
Naushad (reporting/developer)
Tag (tester/developer)

Team 4:

Bin (lead/tester/developer)
Jonathan (developer/gcc guru)
Yi (reporting/tester)

Edit | Attach | Watch | Print version | History: r49 < r48 < r47 < r46 < r45 | Backlinks | Raw View | Raw edit | More topic actions...
Topic revision: r46 - 2008-04-14 - NaushadUzZaman
 
  • Edit
  • Attach
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2017 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding URCS? Send feedback