textbook pages: http://wps.aw.com/aw_aho_compilers_2/0,11227,2663889-,00.html

class parser website: https://netfiles.uiuc.edu/hoefling/www/index.html

JVM

• http://en.wikipedia.org/wiki/Java_bytecode
• http://java.sun.com/docs/books/vmspec/2nd-edition/html/ClassFile.doc.html
• http://java.sun.com/docs/books/vmspec/2nd-edition/html/Instructions2.doc.html
• http://java.sun.com/docs/books/vmspec/2nd-edition/html/Overview.doc.html

December 12th- give out final exam - take home. Solve by the 15th.

Sign up for final project turn in. 15th.

2006-12-05

2006-11-30

2006-11-14

Garbage collection

2006-10-31

2006-10-26

• node splitting on page 25, cs426-11.pdf.

     a
    / \
   /   \  
  b<--->c
  
     a
    / \
   /   \
  b---->c<---->b
  

2006-10-05

• O(n)
  • scanning, parsing, ast generation
• polynomial
  • global data flow, local data flow, inter procedural optimization
• np complete
  • instruction scheduling, register allocation
• ast -> (intermediate code generation -> machine low level code generation) -> machine code
  • middle two attempts might be combined
• each optimization pass
  • should use a common IR
  • should have one goal
  • shoudl be optimized the same, regardless if it's user or compiler generated
• assumptions
  • register allocator does a good job
  • optimization phase does a good job
  • little to no special case analysis
  • global data flow analysis is worthwile

2006-09-28

• • S' -> S
  • S -> V=E
  • S -> E
  • E -> V
  • V -> id
  • V -> +E

2006-09-14

• MP1 due today!
  • turn in the assignments to Dr. Padua.
  • don't include the +- infront of a floating point number as part of it's token. The parser needs more information in order to make an informed decision.
    • Ex a--3.5

2006-09-12

• notes on cs426-5.pdf

2006-09-07

• Desirable properties for memory management:
  • space efficnency - minimize fragmentation
  • program efficiency - seek locality
  • low overhead - can't take too long to provide memory
• locality
  • temporal locality - data, once used, is likely to be reused soon
  • spacial locality - data nearby used data is likely to be accessed in the near future.
• allocation strategies
  • first fit - first chunk where object can fit
  • best fit- smalles chunk that the oject can fit
    • can create an array of linked list of "bins". Each index of the array corresponds to a histogram of bins, and the linked list contains all the bin locations.
    • can make a hierachial bit map of which sections of memory are free and which are empty.
  • worst fit - always largest chunk
  • next fit - fit in the chunk used in the last allocation
• coalescing ???
  • Illustration in guest speaker's slides
  • store valid status and length at the beggining and end of every boundary.
  • when freeing memory, can travel over adacent memory locations, combine them.
• deallocation problems
  • memory leaks - forget to deallocate memory that is no longer used
  • dereferencing memory that has already been deallocated
  • deleting memory that was not allocated.
• solutions
  • object ownership
    • objects lifetime can be detemined statically
  • reference counting
    • when lifetime needs to be determined at runtime
    • does not detect cycles
  • region based allocation
    • for sets of objects related to one stage of the program
    • can be seldom applied.
• Garbage collection
  • requirements
    • allows collector to identify pointers and sizes
    • pointers point to the beginning of objects
  • execution times
    • ovarl execution- collection is expensive
    • space usage - avoid fragmentation
    • pause time - can't pause when freeing in real time system
    • program locality - spacial and temporal
  • Reachability
    • root set - data available w/o folowing pointers
    • object reachable from the root set
    • depends on compiler cooperation to run efficiently

2006-09-05

Runtime Environments

• allocation
• deallocation? (garbage collection)
• management of data structions the compiled program uses (call stack, etc)

Environment

• mappng from names to addresses (name --> void*)

State

• mapping from addresses to values (void* --> Real)

scope of declaration:

• context where 'x' refers to the corresponding decl of x
• static/lexical - scope is obvious from code
• dynamic: otherwise

Things inside an activation record

• actual parameters
• returned values
• control link - old instruction pointer
• access link - if you have nested procedured, then access link needed to get to previous nested scopes. NOT the same as control link when you consider recursive functions.
• saved machine status - flag bits
• local data
• temporaries

callng sequence fills in AR of the procedure called, return sequence restore sate upon return using the actication record

• best to put stuff in the callee to avoid duplication

Contents of the AR in memory:

• parameters
• fixed width fields
• var length data
• top of stack ptr
  • usually points to end of fixed length fields (so we know how long the var length stuff is, stack pointer - top of stack.)

* access links can be managed through a linked list or a simple array reserved on the heap

2006-08-29

Physical notes on 2:2

Notes today started at register allocation on the second set of slides, stoped at pg 41. Moved on to a new set of slides that aren't availiable yet.

2006-08-24

physical notes on 1:12

class webpage: http://polaris.cs.uiuc.edu/~padua/cs426

Padua isn't involved with the LLVM project? nope

Using Jasmine as the intermediate "assembly" language. He would also we prefer we use java.

• language we are parsing is a C subset.
• compiling for java VM.