CS 255/455 Spring 2017

CSC 255/455 Software Analysis and Improvement (Spring 2017)

Lecture slides (when used), demonstration programs, and some of the reading material will be distributed through Blackboard.  Assignments and projects will be listed here.


Assignments:

  • Trivia assignment.  Search slashdot.org for the posts on GCC, LLVM, RUST, Scala or Haskell.  Select two posts to read the posts and all discussions.  Write a summary with 200 or more words for each of the two posts.  The summary should include at least a precise fact on the topic as well as an opinion with all supporting and disagreeing arguments pulled from the discussions.  Print and submit a paper copy Monday January 23rd at the start of the class.  Then see me in one of my office hours for feedback on the summary.   Meet me on or before February 3rd.  The grade is assigned after the meeting.  Bring a copy of your paper to the meeting (in addition to the one you submit).

 Course description

With the increasing diversity and complexity of computers and their applications, the development of efficient, reliable software has become increasingly dependent on automatic support from compilers & other program analysis and translation tools. This course covers principal topics in understanding and transforming programs by the compiler and at run time. Specific techniques include data flow and dependence theories and analyses; type checking and program correctness, security, and verification; memory and cache management; static and dynamic program transformation; and performance analysis and modeling.

Course projects include the design and implementation of program analysis and improvement tools.  Meets jointly with CSC 255, an undergraduate-level course whose requirement includes a subset of topics and a simpler version of the project.

 

 Instructor and grading

Teaching staff: Chen Ding, Prof., CSB Rm 720, x51373;  Dong Chen, Grad TA;  Jacob Bisnett, Undergrad TA.

Lectures: Mondays and Wednesdays, 10:25am-11:40am, CSB 601

Office hours: Ding, Fridays 11am to noon (and Mondays for any 15 minute period between 3:30pm and 5:30pm if pre-arranged).

TA Office hours: Dong Chen, Tuesdays 3:30pm to 4:30, CSB 720. Jacob Bisnett, Thursday 1:00 pm to 1:50 pm, CSB 720.

Grading (total 100%)

  • midterm and final exams are 15% and 20% respectively
  • the projects total to 40% (LVN 5%, GCC/LLVM/RUST 5%, local opt 10%, global opt 10%, final phase 10%)
  • written assignments are 25% (trivial 1%; 3 assignments 8% each)

 Textbooks and other resources

Optimizing Compilers for Modern Architectures (UR access through books24x7), Randy Allen and Ken Kennedy, Morgan Kaufmann Publishers, 2001. Chapters 1, 2, 3, 7, 8, 9, 10, 11. lecture notes from Ken Kennedy. On-line Errata

Engineering a Compiler, (2nd edition preferred, 1st okay), Keith D. Cooper and Linda Torczon, Morgan Kaufmann Publishers. Chapters 1, 8, 9, 10, 12 and 13 (both editions). lecture notes and additional reading from Keith Cooper. On-line Errata

Compilers: Principles, Techniques, and Tools (2nd edition), Alfred V. Aho, Monica S. Lam, Ravi Sethi, and Jeffrey D. Ullman, Pearson.

Static Single Assignment Book, Rastello et al. (in progress)

Robby Findler seminar and guest lecture

 

Macros matter: effectively building lots of programming languages
Robby Findler
Northwestern University & PLT
Monday, November 14, 2016

Building new programming languages from whole cloth is a difficult proposition at best. Macro system provide an alternative; they support the construction of new programming languages from existing pieces, while still providing the flexibility to radically change the syntax and semantics of the programming language.

In this talk, I will give a high-level overview of the myriad of programming languages that Racket supports, as well as an overview of the research area of macros, showing what can be accomplished with them and introducing some of the associated technical challenges (and their solutions).

Robby Findler is currently an Associate Professor at Northwestern University, and received his PhD from Rice University in 2002. His research area is programming languages and he focuses on programming environments, software contracts, and tools for modeling operational semantics. He maintains DrRacket, the program development environment for the programming language Racket and he co-authored the book _How to Design Programs_, a textbook for teaching introductory programming.

(URCS seminar announcement)

Slides

(CSC 253/453 Guest Lecture)  Redex: A Language for Lightweight Semantics Engineering

Professor Robby Findler, Northwestern University

Redex is a programming language designed to support semantics engineers as they experiment with programming language models.  To explore a model, an engineer writes down grammars, type systems, and operational semantics in a notation inspired by the programming languages literature. Redex breathes life into the model, building typing derivations, running example expressions, and using random generation to falsify claims about the model.

This talk gives an overview of Redex, motivating its design choices and giving a sense of how it feels to program in Redex. Then the talk dives into some of the techniques that Redex uses to generate random expressions.

A video by Prof. Findler on Redex

https://docs.racket-lang.org/redex/

CSC 253 Fall 2016

CSC 253/453 Dynamic Language & Software Development

Prerequisites: CSC 252 and CSC 254 are required for CSC 453 and recommended for others. Familiarity with a dynamic programming language such as Python.
Crosslisted: TCS 453

This course studies dynamically-typed programming languages and modular software development. Topics include principles and practice of modular design, functional and object-oriented programming techniques, software engineering concepts, software correctness and reliability, programming tools, and design examples. Ruby is used as the main instruction language. The lessons complement those in traditional compilers and programming languages courses, which focus mainly on statically-typed languages and individual algorithms rather than system design. A significant portion of the assignment is a group project.

Teaching Staff and office hours:  Prof. Chen Ding, Fridays 11am to 12pm in CSB 720; John Jacobs, Thursdays 3:30-4:30pm in CSB 720.

Preparation (before first class):

“No Silver Bullet — Essence and Accidents of Software Engineering” is a classic paper on software engineering written by Turing Award winner Fred Brooks in 1986.  Read the paper (available here if accessed inside the UR network) especially pages 3 to 5 on the “essential difficulties” of software development.

“A former member of the SD10 Panel on Computing in Support of Battle Management explains why he believes the ‘star wars’ effort will not achieve its stated goals.”  Read the paper (available here if accessed inside the UR network) pages 2 to 4 the section titled “Why software is unreliable.”  Which of the “essential difficulties” was Parnas discussing?

More background of this debate, detailed rationales and an illuminating discussion of the ethical issues can be found in another article of Parnas: “SDI: A Violation of Professional Responsibility”.  The article does not seem to have a free version online, but you can read it by borrowing the book “Software Fundamentals” (included as Chapter 27) from the textbook reserve for CSC 253/453 at the Carlson Library.  The lease is two hours.

Further material will be distributed through the Blackboard web site  for students who have registered.  Contact the instructor if you have problem accessing the site.

Textbooks:
Design patterns in Ruby
Author: Olsen, Russ.
Imprint: Upper Saddle River, NJ : Addison-Wesley, c2008.
On Reserve at: Internet

Fundamentals of software engineering
Author: Ghezzi, Carlo.
Imprint: Upper Saddle River, N.J. : Prentice Hall, c2003.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: QA76.758 .G47 2003

Object-oriented and classical software engineering
Author: Schach, Stephen R.
Imprint: New York : McGraw-Hill, c2011.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: QA76.758 .S318 2011

PROGRAMMING LANGUAGE PRAGMATICS, 3rd ed
Author: Scott, Michael L.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: CRL PersCpy

Software fundamentals : collected papers by David L. Parnas
Author: Parnas, David Lorge.
Imprint: Boston : Addison-Wesley, 2001.
On Reserve at: Carlson Library Reserve Desk 2nd Floor
Call Number: QA76.754 .P365 2001

Programming Languages: Application and Interpretation (http://cs.brown.edu/~sk/Publications/Books/ProgLangs/2007-04-26/)
Copyright © 2003-07, Shriram Krishnamurthi
(Also see Prof. Findler’s course EECS 321 at https://www.eecs.northwestern.edu/~robby/courses/)

Topics:

schedule

schedule.numbers-2016 topics

 

CS255 Assignment #1 (LVN)

In this assignment, you are asked to implement local value numbering (LVN) and check for redundant expressions.

You are expected to handle commutativity for commutative operations. Recall that an operation is commutative if you can change the order of operands without changing the result. For example (+) is commutative but (-) is not. Your implementation must be able to assign the same value number to a+b and b+a.

As the final requirement, improve LVN by adding the Stewart extension. The Stewart extension improves LVN by identifying additional redundancy in the following example form.

a = b + c

d = a – b

Specifically, it guides LVN to assign the same value number to both (c) and (d). The idea of the solution was first raised by Chris Stewart when he was taking the class around 2004.  His idea was to insert additional value relations into the value number table. You should first work out this idea and make it concrete as an extension to the basic value numbering algorithm.

Note 1: You are expected to apply the Stewart extension on four operations: ‘+’, ‘-‘, ‘*’, and ‘/’.

Note 2: You should make sure that the Stewart extension can be applied on the following code as well.

a = b + c

e = a

d = e – b

 

To complete this assignment, take the following steps:

1. From Blackboard, download block.rb and vn_tests.rb to your project directory.

2. Implement the LVN class in the new file vn.rb.

4. Make sure all the tests in vn_tests.rb pass.

5. Document any test failures, if there is any, and explain why, in README.txt in plain text.

6. Extra credit.  In addition to finding the statements with a redundant expression, generate optimized code where all redundant expressions are removed.  Demonstrate the optimizer with a set of tests and put them in opt_tests.rb.  The tests should include all three tests in vn_tests.rb.

7. Submit your assignment on Blackboard. Make sure to include all the ruby files in your submission.

Due time: Friday Jan 29th at 23:59:59 EST.

Late submission policy: Each student can have a total of two days used for late submissions over all assignments . This means that if you submit the LVN assignment on Sunday, you will not be able to do any other late submission. But if you submit on Saturday, you still have one more day to use for one other assignment.

Policy on academic honesty :  Every line of code of the LVN analyzer and optimizer must be written by the student.  Do not copy code.  Do not show your LVN code to others until 2 days (48 hours) past the assignment due time.  The teaching staff is required to report every violation of the policy or suspicion of violation to the university’s Academic Honesty Board.  Contact the teaching staff if you have questions on the policy.

 

CS 255/455 Spring 2016

 IMG_2434

CSC 255/455 Software Analysis and Improvement (Spring 2016)

Lecture slides (when used), demonstration programs, and some of the reading material will be distributed through Blackboard.  Assignments and projects will be listed here.


Assignments:

  • def-use in URCC/LLVM
  • LVN in URCC/LLVM
  • CFG pass in URCC/LLVM
  • Instruction counting in GCC/LLVM
  • Local value numbering
  • Trivia assignment.  Read slashdot.org for any current or archived posts.  Select any two posts on a topic of either GNU, GCC, or LVM (both posts may be on the same topic).  Read the posts and all discussions.  Write a summary with 200 or more words for each of the two posts.  In the summary, review facts and main opinions people agreed or disagreed.  Print and submit a paper copy Wednesday January 20th at the start of the class.  Then see me in one of my office hours for feedback on the summary.   There is no deadline for the meeting, but the grade is assigned only after the meeting.  If you see me before submitting the paper, bring your paper; otherwise, don’t since I’ll have your paper.

 Course description

With the increasing diversity and complexity of computers and their applications, the development of efficient, reliable software has become increasingly dependent on automatic support from compilers & other program analysis and translation tools. This course covers principal topics in understanding and transforming programs by the compiler and at run time. Specific techniques include data flow and dependence theories and analyses; type checking and program correctness, security, and verification; memory and cache management; static and dynamic program transformation; and performance analysis and modeling.

Course projects include the design and implementation of program analysis and improvement tools.  Meets jointly with CSC 255, an undergraduate-level course whose requirement includes a subset of topics and a simpler version of the project.

 

 Instructor and grading

Teaching staff: Chen Ding, Prof., CSB Rm 720, x51373; Rahman Lavaee, TA. CSB 630, x52569.

Lectures: Mondays and Wednesdays, 10:25am-11:40am, CSB 632

Office hours: Ding, Fridays 3:30pm-4:30pm (and Mondays the same time if pre-arranged);

TA Office hours: Wednesdays 3:30pm – 4:30pm, CSB 720.

Grading (total 100%)

  • midterm and final exams are 15% and 20% respectively
  • the projects total to 40% (LVN 5%, GCC/LLVM 5%, local opt 10%, global opt 10%, final phase 10%)
  • written assignments are 25% (trivial 1%; 3 assignments 8% each)

 Textbooks and other resources

Optimizing Compilers for Modern Architectures (UR access through books24x7), Randy Allen and Ken Kennedy, Morgan Kaufmann Publishers, 2001. Chapters 1, 2, 3, 7, 8, 9, 10, 11. lecture notes from Ken Kennedy. On-line Errata

Engineering a Compiler, (2nd edition preferred, 1st okay) Keith D. Cooper and Linda Torczon, Morgan Kaufmann Publishers. Chapters 1, 8, 9, 10, 12 and 13 (both editions). lecture notes and additional reading from Keith Cooper. On-line Errata

Workload Modeling for Computer Systems Performance Evaluation, Dror G. Feitelson, Cambridge University Press, 2014.   (book pdf for personal use)  Chapters 1, 3.1, 6.2