CSCE 434 Lecture 35

« previous | Monday, November 18, 2013 | next »

Lecture Slides

Complex Expressions

Array References

First, agree to storage scheme because memory is linear (i.e. agree on linearization scheme):

row-major order

rightmost subscript varies fastest

A[1,1], A[1,2], A[1,3], A[2,1], A[2,2], A[2,3]

column-major order

leftmost subscript varies fastest

A[1,1], A[2,1], A[1,2], A[2,2], A[1,3], A[2,3]

indirection vectors

vector of pointer to pointers to ... to values

uses much more space

Computing an Address

A[i]

• ${\mbox{base}}(A)+(i-1)\cdot {\mbox{sizeof}}(elem)$
• row-major order: ${\mbox{base}}(A)+((i_{1}-low_{1})\cdot (high_{2}-low_{2}+1)+i_{2}-low_{2})\cdot {\mbox{sizeof}}(elem)$.
• column-major order: ${\mbox{base}}(A)+((i_{2}-low_{2})\cdot (high_{1}-low_{1}+1)+i_{1}-low_{1})\cdot {\mbox{sizeof}}(elem)$

Expensive!

Consider distributing:

• ${\mbox{base}}(A)+i\cdot {\mbox{sizeof}}(elem)-1\cdot {\mbox{sizeof}}(elem)$
• Faster since last term can be computed at compile-time
• the first term is called the address polynomial

Passing as Parameters

• Call by Reference is easy
• Call by Value has to copy entire array, but there are no side-effects.

Optimizing

• combine subexpressions in the address polynomial
• contents of dope vector ....

Optimizations are especially easy if array is iterated in a "nice sweep":

for (int i; i < max; i++) {
    // ...
}

Function Calls

a + foo(1)</math>

Caution:

• Functions may have side-effects
• evaluation order is now important (because of first)

Handling Expressions in a function call

• expression result has no address
  • call by reference: treat as temporary variable
  • call by value: pass value as parameter slot
• expression may contain other function calls

Mixed Type Expressions

• Must have clearly-defined meaning
• Usually convert to more general type
• C promotion: int + int → int, int + float → float
• Machine-dependent code
• Be careful with floating-point precision and performance hits

In assignment, always convert to type of LHS

Store types on AST nodes

• Attribute grammars or ad-hoc tree walk
• generally more complex, but simplifies later passes

Harder Problems:

• Type inferencing (without declarations)
• generated types (classes, structs)

When inferring information about an algorithm, types can help a lot.

Boolean Expressions

• Relational: (less than, greater than, equal)
• Logical: (and, or, not)

Two schools of thought (neither is proven to be better than the other)

1. numerical values
2. True = 1, False = 0; Treat booleans like arithmetic expressions
   • A nice thing about numerical values is that it can use hardware bitwise AND, OR, and NOT
   • Works well for constructs
3. Control Flow
   • represent boolean value by location in code; convert to numeric value when stored
   • code looks terrible, but it allows for short-circuiting
   • Works well for relations

If order is specified, it must be observed. But if not, reorder by cost (cheapest first) and short-circuit if possible.

Better Code

Lecture Slides

Common Subexpressions

Consider $a+a(b-c)+(b-cd)$.

$b-c$ is a common subexpression, so it should be computed only once.

DAGs clearly expose common subexpressions as nodes with more than one parent.

Footnotes