Assignment 3 Code Review

24 October 2002 - CS 509

Assignment 3 Code Review

Big Ideas
Design
- Top-Down design and stepwise refinement
Analysis
- What's the Problem?
- What's the Solution?
Design
- Animating scripts
- Animation steps
- Time steps
- Drawing boxes
Test Cases
Statistics
Coding problems

What's the Problem?

You can't solve a problem you don't understand.
What's the problem?
- Optimize code blocks.
"Optimize" means what?
- Reduce the code block's execution time.
Subject to what constraints?
- Lots, but the main one is memory behavior.
- The memory behavior of optimized and original code must be the same.
Code optimization is an interesting problem.
- It's relatively easy to solve.
- It's difficult and expensive to solve well.

The Big Ideas

What are this problem's big ideas?
- Identical memory behavior.
- Statement packing.
These are in order of importance to the solution.
- Statement packing determines the data structures.
- Memory behavior determines the optimizations.
Knowledge determines big ideas.
- Incremental and iterative approaches to optimization.

Top-Down Design

Top-down design starts with an abstract view of the problem.
What's the problem?
Input a code block,
optimize a code block,
output a code block
That's it; that's the problem.
- What if the first instruction is move r0 r1?
  - Who cares? Worry about it later.
- What happens if ! is an operator?
  - Who cares? Worry about it later.
Abstract problems are simpler to solve.

What's the Solution?

Writing down the problem practically describes the solution.

int main()

  block::code cblock

  while (block::input(std::cin, cblock)) 
    block::optimize(cblock)
    block::output(std::cout, cblock)

Now what?

Now what are the problems?
What's a code block?
- I dunno. A data structure. An object. Whatever.
- It depends on what you want to do with it.
How do I optimize a code block?
- This is hard.
Let's get something working, then fix it up.

Code Blocks

What's a code block?
- A sequence of statements?

What's a statement?

I dunno. A string, maybe. Probably not.
A string will do for now.

typedef std::vector<std::string> code;

bool input(std::istream & is, code & blk)

  if !read_nonblank_line(is, str)
    return false

  blk.clear()

  do blk.push_back(str)
  while getline(is, str) and !is_blank_line(str)

  return true

void optimize(code & blk) { }

void output(std::ostream & os, const code & blk)
  for i = blk.begin(); i != blk.end(); i++
    os << *i << "\n"

Step 1

We have a working solution.
- It handles empty input correctly.
- It copies everything else.
Now what?
- The only thing left is optimization.
- Other matters (input, errors) are not as important.
  - They don't relate to optimization either.

Optimization

What are the big ideas for optimization?
- Identical memory behavior.
- Statement packing.
Which to focus on?
- It depends.
- Statement packing is less abstract.
- Memory behavior isn't directly useful.
I chose memory behavior next.
- Tackle the hard things first.
- And soon, I wasn't making any progress.
I then backtracked and re-chose statement packing.

Statement Packing

What's the problem?
- Combine several statements into one.
Subject to what constraints?
- Identical memory behavior.
- Five statements maximum.
- Two identical operations maximum.
Now what?
- Five statements is not hard.
  - Move statements to a new statement.
- Two operations is not hard.
  - Move statements to a new statement.
- That leaves combining statements.

Combining Statements

What's the problem?
- Can I combine any two statements?
- Clearly no:
```
move  a r0
move r0  b
```
  is not the same as
```
move a r0 ; move r0 b
```
  r0 is involved in a race condition.
- Jumping over race conditions is incorrect too.
```
move r1  b
move r0  a
add  r2 r0
```
  is not the same as
```
move r1  b ; add  r2 r0
move r0  a
```

Lifting Statements

The big idea: repeatedly combine statements until all adjacent statements conflict.
A code block is now a set of statements.
```
typedef std::vector<statement_set> code;
```
- Initially there are n statement sets, one statement in each.
A statement is compatible with a statement set
if s has no conflicts with any statement in the set.
```
bool statement_set::compatible(statement s)
```
I chose to bubble-up statements: "lifting".

Lifting Statements, Implemented

static bool 
lift_statements(block::code & blk)

  bool changed = false;

  block::code new_blk
  new_blk.push_back(blk[0])

  for (unsigned i = 1; i < blk.size(); i++)

    const statement_set & old_ss = blk[i]
    statement_set new_ss;

    for (unsigned j = 0; j < old_ss.size(); j++)
      const statement & s = old_ss[j]
      unsigned home = new_blk.size()

      while ((home > 0) && new_blk[home - 1].compatible(s))
        home--

      if (home != new_blk.size())
        new_blk[home].add(s)
        changed = true
      else
        ss.add(s)

    if (!ss.empty())
      new_blk.push_back(ss)

  if (changed)
    std::swap(blk, new_blk)

  return changed

Size Constraints

But what about the 5 and 2 statement maximums?
- Repeatedly try to bubble-down extra operations.
- Repeatedly try to bubble-down extra statements.
- Split statements otherwise.
- I call this normalization.
```
static void
normalize(block::code & blk)
  while (normalize_opers(blk) || 
         normalize_size(blk)) { }
  split_sets(blk);
```

Block optimization now looks like this:

void optimize(code & blk)
  lift_statements(blk);
  normalize(blk);

Operator Normalization.

bool normalize_opers(code & blk)

  bool changed = false

  for (i = 0; i < blk.size() - 1; i++)

    statement_set & ss = blk[i]

    for (j = 0; j < ss.size(); j++) 
      const statement & s = ss[j]

      if (    (s.opr() != "move")
          and (ss.opr_cnt(s.opr()) > 2)
          and blk[i + 1].compatible(s))
        blk[i + 1].add(s);
        ss.rem(s)
        changed = true

  return changed

Note the absence of operator names.

Line Statistics - Newlines

	200	300	400	500	600	700
0		1		1
10	1
20		1
30			1
40
50		1	2	1		1
60	1	1	3	1
70			1			1
80	1					1
90			1
Totals	3	4	8	3	0	3

Line Statistics - Semicolons

	100	200	300
0	2	2
10	1	2	1
20			1
30	1
40	3	1
50		2
60	2
70
80	2
90	1
Totals	12	7	2

Procedure Statistics

total	pages per procedure
procs	1	2	3	4	5	6
7	4	3
7	5	1	1
10	7	2	1
10	8		1	1
10	9	1
11	9			1		1
14	11	2	1
14	13		1
14	7	5	2
15	13	1	1
17	14	2	1
19	17	2
26	26
27	23	3	1
28	22	5	1
36	35	1

Prefer Strings to Character Arrays

IsInstructionValid(vString insvec) {

  string ins
  char szInstruction[MAX_STRING]
  vector<string>::const_iterator it

  char *szRegisters[8] = {"r0", . . ., "r7"}

  for (it=insvec.begin(); it !=insvec.end() ; ++it)
    ins += (*it)

  strcpy(szInstruction, ins.c_str())

  for (int i = 0; i < 8; ++i)
    if (ins.find(szRegisters[i]) != -1)
      bregisterFound = true
      break

This is a buffer overflow error.
When trek(6) reads in keyboard input, a bounds check was not performed correctly. If more than 100 characters are entered, a buffer overrun occurs.
--- Security Focus,
19 October 2002
Buffer overflow errors are going to cost you. Dearly.

Prefer Vectors to Dynamic Memory

inputfile
read_inputfile(istream is, unsigned count, unsigned cnt1)

  inputfile ss;

  if (!readline(is, line))
    line = "";
    ss = new command_row[count + 1];
    cnt = cnt1;
  else
    ss = read_inputfile(is, count + 1, ++cnt1);

  ss[count] = line

  return ss

How many lines were input?

Prefer vectors.


vector<string> read(istream is)

  vector<string> input
  string line

  while (readline(is, line)
    input.push_back(line)
  return input

How many lines were input? input.size().

Use Named Constants

Which is better?

const unsigned DEST = 1;
const unsigned SRC = 2;

if (is_move_opcode()) 
  if (is_register(simple_st[DEST]) && 
      is_register(simple_st[SRC]))
    return false;
  else if (!is_register(simple_st[DEST]) && 
           !is_register(simple_st[SRC]))
    return false;
else if (!is_register(simple_st[DEST]) || 
         !is_register(simple_st[SRC]))
  return false

for (i = 0; i < EIGHT; i++)
  if (vstr[1] == registers[i]) flagd = true;
for (i = 0; i < EIGHT; i++)
  if (vstr[2] == registers[i]) flags = true;

flag = flagd || flags;

return flag;

Avoid Duplicate Code

Duplicate code is bad code.

It's hard to change.
It causes code bloat.
It's hard to understand. (Is it really duplicate?)

bool alpha_test(vector < string > vect)
  if (vect[0] == "move")
    if (vect[1] == "r0" || vect[1] == "r1" || vect[1] == "r2" || 
        vect[1] == "r3" || vect[1] == "r4" || vect[1] == "r5" || 
	vect[1] == "r6" || vect[1] == "r7") {

      if (vect[2] == " r0" || vect[2] == "r1" || vect[2] == " r2" || 
          vect[2] == "r3" || vect[2] == "r4"||vect[2] == "r5" || 
	  vect[2] == "r6" || vect[2] == "r7") {  }

        if (vect[2] == "r0" || vect[2] == "r1" || vect[2] == "r2" || 
	    vect[2] == "r3" || vect[2] == "r4" || vect[2] == "r5" ||
	    vect[2] == "r6" || vect[2] == "r7" ) { }

bool move_test(vector < string > vect )
  if (vect[0]!="move")
    for (unsigned int k = 1; k < vect.size();k++)
      if (vect[k] == "r0" || vect[k] == "r1" || vect[k] == "r2" ||
          vect[k] == "r3" || vect[k] == "r4" || vect[k] == "r5" || 
	  vect[k] == "r6" || vect[k] == "r7") {  }

Put duplicate code in a procedure and call the procedure.

Use What You're Given

Don't re-implement existing function.

vector<string> getInputRows(){

  vector<string> vsInput
  char cInput
  string sInput

  while cin.get(cInput)
    if (cInput != '\n')
      sInput += cInput
    else
      vsInput.push_back(sInput)
      sInput = ""

  if (sInput! = "") 
    vsInput.push_back(sInput)

  return vsInput

Points to Remember

Figure out the big ideas.
- Learn to appreciate the important details.
Design from the top down with stepwise refinement.
- Little by little, bit by bit.
Study the problem.

This page last modified on 25 October 2002.