Difference: CS455Team3Wiki (1 vs. 49)

Revision 492008-04-28 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 15 to 15
 

Team Name

  • Vectorizers
Deleted:
<
<

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)
Line: 34 to 28
 
  • Wednesday, April 9, second feedback from the hidden benchmarks.
  • Monday, April 14, midnight, competition concludes.
Added:
>
>

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:

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)

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.
Line: 610 to 640
  Xiaoming
Deleted:
<
<

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!
Line: 661 to 687
 
  • Phony photobooth [This was really funny video, but its unavailable now frown ]
http://www.youtube.com/watch?v=eLM3-0UlyCE
Deleted:
<
<

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)
  \ No newline at end of file

Revision 452008-04-12 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 643 to 643
 
  • Worlds most amazing Trick By David Copperfield
http://www.youtube.com/watch?v=buYBsk8XMXk
Added:
>
>
  • 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
Changed:
<
<
  • Phony photobooth
>
>
  • Phony photobooth [This was really funny video, but its now unavailable now frown ]
 http://www.youtube.com/watch?v=eLM3-0UlyCE

Other Teams

Revision 432008-04-11 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 589 to 589
 

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.
Added:
>
>
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

 

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!

Revision 422008-04-11 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 475 to 475
  s = c + s;
Changed:
<
<

Tuesday, April 10, 3:00 AM

>
>

Thursday, April 10, 3:00 AM

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

L32 of tax.c

Line: 528 to 528
  c = a;
Added:
>
>

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.
 

YouTube Videos

Changed:
<
<
Working on compiler is fun and relaxing! When we do make and make install, we spend the time watching funny YouTube videos. Here are few of them!
>
>
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!
 
Changed:
<
<
Matumbo Goldberg
>
>
  • Matumbo Goldberg
 http://www.youtube.com/watch?v=RCKLYCi2UJk
Changed:
<
<
Ameriquest - All 5 Funny Commercials
>
>
  • Ameriquest - All 5 Funny Commercials
 http://www.youtube.com/watch?v=angJGfCSuUI
Changed:
<
<
Phony photobooth
>
>
  • Phony photobooth
 http://www.youtube.com/watch?v=eLM3-0UlyCE
Changed:
<
<
Phony Photo Booth
>
>
  • Phony Photo Booth
 http://www.youtube.com/watch?v=wsSJ1c7nFWE
Changed:
<
<
Honda Commercial
>
>
  • naughty photo booth
http://www.youtube.com/watch?v=pJpUX-nyWbU
  • Honda Commercial
 http://www.youtube.com/watch?v=xcr6ZIVi-Vg
Changed:
<
<
Funny commercial clip
>
>
  • Funny commercial clip
 http://www.youtube.com/watch?v=t0kz8MCxq6A
Changed:
<
<
outrageously funny commercials
>
>
  • outrageously funny commercials
 http://www.youtube.com/watch?v=8cyAqEjZ2as
Changed:
<
<
FUNNY COMMERCIALS !!!!!!!!!!!!!!!!
>
>
  • FUNNY COMMERCIALS !!!!!!!!!!!!!!!!
 http://www.youtube.com/watch?v=Ri3XqFzcc_k
Changed:
<
<
VW Phaeton - Shadowplay Commercial
>
>
  • 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

  • VW Phaeton - Shadowplay Commercial
 http://www.youtube.com/watch?v=4o_me2Zz7q4

Other Teams

Revision 402008-04-10 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 414 to 414
 
Changed:
<
<

Tuesday, April 9, 9:00 PM

>
>

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!!!

Line: 475 to 475
  s = c + s;
Added:
>
>

Tuesday, April 10, 3:00 AM

  • printf in reverse, will improve one in tax.c

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;
 

YouTube Videos

Working on compiler is fun and relaxing! When we do make and make install, we spend the time watching funny YouTube videos. Here are few of them!

Revision 382008-04-10 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 412 to 412
  g = a + c; g = a +c; }
Added:
>
>

Tuesday, 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;
 

YouTube Videos

Working on compiler is fun and relaxing! When we do make and make install, we spend the time watching funny YouTube videos. Here are few of them!
Line: 421 to 484
 Ameriquest - All 5 Funny Commercials http://www.youtube.com/watch?v=angJGfCSuUI
Added:
>
>
Phony photobooth http://www.youtube.com/watch?v=eLM3-0UlyCE
 Honda Commercial http://www.youtube.com/watch?v=xcr6ZIVi-Vg

Revision 362008-04-09 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 348 to 348
  Mering printf, "smart" redundancy elimination in progress.
Deleted:
<
<

Saturday, April 5, 9:09 PM

  • We are enjoying the suffering and tension of other group members, seeing our performance! Lets enjoy till they improve :P
 

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.
Line: 468 to 465
 Yi (reporting/tester)
Deleted:
<
<
 \ No newline at end of file
Added:
>
>

Revision 352008-04-08 - ChrisTice

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 397 to 397
 sort_insertion.c => data[D.1538] = data[j];

Added:
>
>

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;
}
 

YouTube Videos

Working on compiler is fun and relaxing! When we do make and make install, we spend the time watching funny YouTube videos. Here are few of them!

Revision 342008-04-07 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 365 to 365
 
  • 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.
Added:
>
>

Monday, April 7, 6:00 AM

  • Merging printf worked properly and it improved the performance.
 
Added:
>
>

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]; 
 

YouTube Videos

Working on compiler is fun and relaxing! When we do make and make install, we spend the time watching funny YouTube videos. Here are few of them!
Line: 420 to 450
 Yi (reporting/tester)
Changed:
<
<
>
>

Revision 332008-04-06 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 19 to 19
 
  • 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
Changed:
<
<
  • Have a break, Do compiler! --- Naushad UzZaman
>
>
  • Have a break, Do compiler Have a Kit Kat! --- Naushad UzZaman
 

Team Members

  • Chris Tice (lead/developer/gcc guru)
Line: 348 to 348
  Mering printf, "smart" redundancy elimination in progress.
Changed:
<
<

Friday, April 5, 9:09 PM

>
>

Saturday, April 5, 9:09 PM

 
  • We are enjoying the suffering and tension of other group members, seeing our performance! Lets enjoy till they improve :P
Added:
>
>

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.

 

YouTube Videos

Working on compiler is fun and relaxing! When we do make and make install, we spend the time watching funny YouTube videos. Here are few of them!

Revision 322008-04-06 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 18 to 18
 

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
Added:
>
>
  • Comprehensive exams are more important than Compiler Project! --- Naushad UzZaman
  • Have a break, Do compiler! --- Naushad UzZaman
 

Team Members

  • Chris Tice (lead/developer/gcc guru)
Line: 346 to 348
  Mering printf, "smart" redundancy elimination in progress.
Added:
>
>

Friday, April 5, 9:09 PM

  • We are enjoying the suffering and tension of other group members, seeing our performance! Lets enjoy till they improve :P
 

YouTube Videos

Added:
>
>
Working on compiler is fun and relaxing! When we do make and make install, we spend the time watching funny YouTube videos. Here are few of them!
 Matumbo Goldberg http://www.youtube.com/watch?v=RCKLYCi2UJk

Ameriquest - All 5 Funny Commercials http://www.youtube.com/watch?v=angJGfCSuUI

Added:
>
>
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

 
Added:
>
>
FUNNY COMMERCIALS !!!!!!!!!!!!!!!! http://www.youtube.com/watch?v=Ri3XqFzcc_k
  VW Phaeton - Shadowplay Commercial http://www.youtube.com/watch?v=4o_me2Zz7q4

Revision 282008-04-04 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 190 to 190
  /home/vax3/u31/chung/classes/2008Spring/csc455/project
Changed:
<
<

Thursday, March 28, 09:00 PM

>
>

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)

Changed:
<
<

Thursday, March 29, 09:00 PM

>
>

Saturday, March 29, 09:00 PM

 - added the module "eliminate redundant assignment"

Tuesday, April 1, 08:00 PM

Line: 330 to 330
 f = e;
Changed:
<
<

Wednesday, April 3, 9:00 PM

>
>

Thursday, April 3, 9:00 PM

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

Wednesday, April 4, 12:08 AM

>
>

Friday, April 4, 12:08 AM

 Things we are missing:
  • automaton.c
- in getnextdigit(), in :;

Revision 252008-04-02 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 18 to 18
 

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
Deleted:
<
<
  • Comprehensive exams are more important than this project! --- Naushad UzZaman
 

Team Members

  • Chris Tice (lead/developer/gcc guru)
Line: 204 to 203
 

Tuesday, April 1, 08:00 PM

Things we need to add in the "eliminate redundant assignment" pass:
Changed:
<
<
  • check index of array (partially works)
>
>
  • check index of array (WORKS)
 works for many cases, but doesn't work for fibonacci!!
Deleted:
<
<
also modify for the lhs of the array index.
 example: fibonacci.c
val.1 = val;

Line: 217 to 214
 D.1538 = array[val];
Changed:
<
<
  • handle array
>
>
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;

Line: 253 to 259
 print (array_4[idx])
Changed:
<
<
  • function call (on progress)
>
>
  • function call (WORKS)
 example: automaton.c
D.1545 = getnextdigit ();

Line: 262 to 268
 a = getnextdigit ();
Changed:
<
<
  • type casting (next)
>
>
  • type casting (WORKS)
 example: automaton.c
D.1572 = (int) D.1571;

Line: 287 to 293
  lhs (current stmt) = op1_of_rhs_of op1's defn
Added:
>
>

Wednesday, April 2, 3:00 AM

Next TODO on 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;
 

Other Teams


Revision 242008-04-02 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 9 to 9
  http://www.cs.rochester.edu/twiki/bin/view/Main/OpenTable
Added:
>
>
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
Added:
>
>
  • Comprehensive exams are more important than this project! --- Naushad UzZaman
 

Team Members

  • Chris Tice (lead/developer/gcc guru)
Line: 200 to 204
 

Tuesday, April 1, 08:00 PM

Things we need to add in the "eliminate redundant assignment" pass:
Changed:
<
<
  • check index of array
>
>
  • check index of array (partially works)
works for many cases, but doesn't work for fibonacci!!

also modify for the lhs of the array index.

 example: fibonacci.c
val.1 = val;

Line: 219 to 227
 print (array_4[idx])
Changed:
<
<
  • return statement
>
>
  • return statement (WORKS)
 example: automaton.c
D.1540 = n;

Line: 228 to 236
 return n;
Changed:
<
<
  • conditional statement
>
>
  • conditional statement (WORKS)
 
a.0 = a;
if(a.0<=0) then do something

Line: 236 to 244
 if(a<=0) then do something
Added:
>
>
  • printf statement (WORKS)
idx.0 = idx;
D.1551 = array_4[idx.0];
print (D.1551);
=> 
print (array_4[idx])

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

  • type casting (next)
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

Revision 232008-04-02 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 197 to 197
 

Thursday, March 29, 09:00 PM

- added the module "eliminate redundant assignment"
Added:
>
>

Tuesday, April 1, 08:00 PM

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

  • check index of array
example: fibonacci.c
val.1 = val;
D.1538 = array[val.1];
=> 
D.1538 = array[val];

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

  • return statement
example: automaton.c
D.1540 = n;
return D.1540;
=> 
return n; 

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

  • 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
 

Other Teams


Added:
>
>
 Team 1:

Rongrong (lead/developer/reporting)

Revision 202008-03-29 - TagChung

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 188 to 188
  /home/vax3/u31/chung/classes/2008Spring/csc455/project
Added:
>
>

Thursday, 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)
 
Added:
>
>
- initial_optimization_pass() (bug-fixed) resulted in slight improvement of trivia.c
 
Added:
>
>
- gimplified open test cases (unoptimized and -O3) are in /u/chung/classes/2008Spring/csc455/open_test_cases (to see which improvements we can make)
 

Other Teams

Revision 192008-03-28 - ChrisTice

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 33 to 33
 

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.
Changed:
<
<

Monday, March 25, 7:10 PM

>
>

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.
Changed:
<
<

Monday, March 25, 11:30 PM

>
>

Tuesday, March 25, 11:30 PM

 Things to check in value numbering:
  • global variables

Line: 128 to 128
 
  • DVN or EVN
Changed:
<
<

Monday, March 26, 12:59 AM

>
>

Wednesday, March 26, 12:59 AM

 How do you handle constant propagation with the loop?
  • code

Line: 175 to 175
 goto (<L1 >)
Changed:
<
<

Monday, March 27, 08:00 PM

>
>

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;

Revision 152008-03-28 - TagChung

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 12 to 12
 

Team Name

  • Vectorizers
Added:
>
>

Words of Wisdom to Guide Us

  • Celui qui étudie pour appliquer au bon moment n'y trouve-t-il pas de la satisfaction? --- Confucius
  • Mom, when I grow up I want to be just like you. I want to do nothing, I want to be nothing. --- Kelly Bundy
  • Kids, you tried your best and you failed miserably. The lesson is: never try. --- Homer Simpson
 

Team Members

  • Chris Tice (lead/developer/gcc guru)
  • Tagyoung Chung (tester/developer)

Revision 72008-03-26 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 7 to 7
 

Task

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

Team Name

  • Vectorizers
Line: 20 to 22
 
  • 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.
Changed:
<
<
  • Monday, April 7, midnight, competition concludes.
>
>
  • Wednesday, April 9, second feedback from the hidden benchmarks.
  • Monday, April 14, midnight, competition concludes.
 

Meeting Notes

Monday, March 24, 3:30 PM

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

Monday, March 25, 11:30 PM

Things to check in value numbering:
Added:
>
>
  • 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

Added:
>
>
case 1:
 b = a + 3; scanf("%d", &a); g = a + 3;
Line: 41 to 78
 a.0 = a; g = a.0 + 3;
Changed:
<
<
getting the variables from scanf arguments:
>
>
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
Line: 49 to 99
  { tree argument = TREE_VALUE(parms); //this gets you '&a' argument = TREE_OPERAND(argument, 0); //this gets you actual variable 'a'
Changed:
<
<
>
>
} }
 
  • constant
Line: 69 to 120
 D.1537 = ar[3]; D.1538 = br[3];
Deleted:
<
<
  • multiple definition and one changes!
b = a + c;
g = a + c;
e = a + c;
f = a + c;
=> 
b = a + c;
g = b;
e = g;
f = e;
 
  • DVN or EVN

Other Teams

Line: 109 to 148
 Jonathan (developer/gcc guru) Yi (reporting/tester)
Deleted:
<
<
-- NaushadUzZaman - 24 Mar 2008
  \ No newline at end of file

Revision 62008-03-26 - TagChung

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 41 to 41
 a.0 = a; g = a.0 + 3;
Changed:
<
<
way to handle scanf:
>
>
getting the variables from scanf arguments:
  if(strcmp(callee_name, "scanf") == 0) {
Changed:
<
<
//check if printf has more than one variable //printf("check params for scanf:"); tree p = TREE_OPERAND (stmt, 1); //added later int num_parms; p = TREE_CHAIN(p); for (num_parms = 0; p; p = TREE_CHAIN (p))
>
>
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
  {
Changed:
<
<
num_parms++; tree arg = TREE_VALUE(p); arg = TREE_OPERAND(arg,0);
printf("arg
%d\n", num_parms-1); print_generic_stmt (stdout, arg, 0); int op_val = my_vn_lookup(arg, value_table); my_expr_vn_pair_t tmp_lhs2;
>
>
tree argument = TREE_VALUE(parms); //this gets you '&a' argument = TREE_OPERAND(argument, 0); //this gets you actual variable 'a'
 
Deleted:
<
<
my_vn_add(value_table, arg, vn++); if(op_val!=0) {
//printf("scanf
FOUND IN HASHTABLE %u \n", op_val); print_generic_stmt (stdout, stmt, 0);

tmp_lhs2.vn = op_val; delete_element_by_vn(tmp_lhs2); tree_array[op_val] = NULL; }

}

 
  • constant

Revision 52008-03-26 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 27 to 27
 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.

Monday, 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.
Added:
>
>

Monday, March 25, 11:30 PM

Things to check in value numbering:
  • scanf
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;

way to handle scanf: 
                                if(strcmp(callee_name, "scanf") == 0)
				{
					//check if printf has more than one variable
					//printf("check params for scanf:");
					tree p = TREE_OPERAND (stmt, 1);
					//added later
					int num_parms;					
					p = TREE_CHAIN(p);
					for (num_parms = 0; p; p = TREE_CHAIN (p))
					{
						num_parms++;
						tree arg = TREE_VALUE(p);
						arg = TREE_OPERAND(arg,0);
						printf("arg: %d\n", num_parms-1);
						print_generic_stmt (stdout, arg, 0);
						int op_val = my_vn_lookup(arg, value_table);
						my_expr_vn_pair_t tmp_lhs2;

						my_vn_add(value_table, arg, vn++);
						if(op_val!=0)
						{
							//printf("scanf: FOUND IN HASHTABLE  %u \n", op_val);
							print_generic_stmt (stdout, stmt, 0);

							tmp_lhs2.vn = op_val;
							delete_element_by_vn(tmp_lhs2);
							tree_array[op_val] = NULL;
						}

					}

  • constant
a = b + 17;
c = 17;
e = b + c;
  • array
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];
  • multiple definition and one changes!
b = a + c;
g = a + c;
e = a + c;
f = a + c;
=> 
b = a + c;
g = b;
e = g;
f = e;
  • DVN or EVN
 

Other Teams

Added:
>
>

 Team 1:

Rongrong (lead/developer/reporting)

Line: 52 to 130
 Bin (lead/tester/developer) Jonathan (developer/gcc guru) Yi (reporting/tester)
Changed:
<
<
>
>
 -- NaushadUzZaman - 24 Mar 2008

Revision 42008-03-25 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 25 to 25
 

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.
Changed:
<
<
>
>

Monday, 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.
 

Other Teams

Team 1:

Revision 32008-03-25 - NaushadUzZaman

Line: 1 to 1
 
META TOPICPARENT name="NaushadUzZaman"
Line: 27 to 27
 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.
Added:
>
>

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)

  -- NaushadUzZaman - 24 Mar 2008

Deleted:
<
<
META PREFERENCE name="ALLOWTOPICCHANGE" title="ALLOWTOPICCHANGE" type="Set" value="Main.NaushadUzZaman, TagChung, ChrisTice, ChenDing, XiaomingGu"
META PREFERENCE name="ALLOWTOPICVIEW" title="ALLOWTOPICVIEW" type="Set" value="Main.NaushadUzZaman, TagChung, ChrisTice, ChenDing, XiaomingGu"

Revision 12008-03-25 - NaushadUzZaman

Line: 1 to 1
Added:
>
>
META TOPICPARENT name="NaushadUzZaman"

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

Team Name

  • Vectorizers

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.
  • Monday, April 7, 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.

-- NaushadUzZaman - 24 Mar 2008

 
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