Questions regarding Assignment 5

[jhwest1]

1. The result of the optimization may be different when we choose a different order to iterate the basic blocks. For example,

   
   define i32 @f(i32 %a, i32 %b, i32 %c) {
   br label %block2

block1: %cond2 = icmp eq i32 %b, %c br i1 %cond2, label %block3, label %end

block2: %cond = icmp eq i32 %a, %c br i1 %cond, label %block1, label %end

block3: %add = add i32 %a, %b %ret = add i32 %add, %c ret i32 %ret

end: ret i32 0 }

If we loop through basic blocks in the order they appear in the program, we get the result:

...

block3: %add = add i32 %a, %b %ret = add i32 %add, %b ret i32 %ret

...

However, if we loop through basic blocks in the reverse order they appear in the program, we get the result:

...

block3: %add = add i32 %a, %a %ret = add i32 %add, %a ret i32 %ret

...

My question is, do we have to assume a certain order that the optimizations are done when writing the tests? Or should the test be written in a way such that no matter what the order of the optimization will be, it would output a consistent result?

2. Do we have to consider phi instructions into optimization? Particularly, 

define i32 @f(i32 %a, i32 %b) { %cond = icmp eq i32 %a, %b br i1 %cond, label %if.true, label %if.false

if.true: br label %if.end

if.false: br label %if.end

if.end: %ret = phi i32 [ %b, %if.true ], [ %a, %if.false ] ret i32 %ret }

do we have to optimize this code to the following?

...

if.end: %ret = phi i32 [ %a, %if.true ], [ %a, %if.false ] ret i32 %ret }

[strikef]

1. In the assignment 5 README we've specified the substitution order as following:

   1. If two instructions %x and %y are compared, and %x dominates %y, replace %y with %x.
   2. If two arguments %x and %y are compared, replace the one which appeared later in the function argument list with the other one which appeared earlier.

2. Each phi operand is executed after comparison & dominated by its predecessing basic block, so the suggested optimization should take place.

[jhwest1]

My second question was resolved. Thanks!

For the first question, I would like to clarify my point in detail. I am aware that the substitution order is given in the README file, so in the case I provided, we should substitute, for example, %b with %a and %c with %b but not %a with %b according to the order they appear in the argument list.

Despite of this specification, I claim that the problem is still vague since which icmp operation we should apply the substitution first is not specified. In the example, there are two icmp operations, which are %cond2 = icmp eq i32 %b, %c in block1 and %cond = icmp eq i32 %a, %c in block2.

If we decided to apply the substitution for %cond2 = icmp eq i32 %b, %c first, this would substitute all appropriate occurences of %c with %b, resulting in the following program.

 define i32 @f(i32 %a, i32 %b, i32 %c) {
  br label %block2

block1:
  %cond2 = icmp eq i32 %b, %c
  br i1 %cond2, label %block3, label %end

block2:
  %cond = icmp eq i32 %a, %c
  br i1 %cond, label %block1, label %end

block3:
  %add = add i32 %a, %b
  %ret = add i32 %add, %b                                            ; <-- change here
  ret i32 %ret

end:
  ret i32 0
}

Then, applying the substitution for %cond = icmp eq i32 %a, %c, this will replace all appropriate occurences of %c with %a, resulting in:

 define i32 @f(i32 %a, i32 %b, i32 %c) {
  br label %block2

block1:
  %cond2 = icmp eq i32 %b, %a                                        ; <-- changed here
  br i1 %cond2, label %block3, label %end

block2:
  %cond = icmp eq i32 %a, %c
  br i1 %cond, label %block1, label %end

block3:
  %add = add i32 %a, %b
  %ret = add i32 %add, %b
  ret i32 %ret

end:
  ret i32 0
}

However, if we decided to process %cond = icmp eq i32 %a, %c first, the program will first be transformed to:

define i32 @f(i32 %a, i32 %b, i32 %c) {
  br label %block2

block1:
  %cond2 = icmp eq i32 %b, %a                                        ; <-- changed here
  br i1 %cond2, label %block3, label %end

block2:
  %cond = icmp eq i32 %a, %c
  br i1 %cond, label %block1, label %end

block3:
  %add = add i32 %a, %b
  %ret = add i32 %add, %a                                            ; <-- changed here
  ret i32 %ret

end:
  ret i32 0
}

Then applying %cond2 = icmp eq i32 %b, %a, it will become:

define i32 @f(i32 %a, i32 %b, i32 %c) {
  br label %block2

block1:
  %cond2 = icmp eq i32 %b, %a
  br i1 %cond2, label %block3, label %end

block2:
  %cond = icmp eq i32 %a, %c
  br i1 %cond, label %block1, label %end

block3:
  %add = add i32 %a, %a                                              ; <-- changed here
  %ret = add i32 %add, %a
  ret i32 %ret

end:
  ret i32 0
}

So, two different order of applying the substitution results in different programs.

[strikef]

I see the point that this optimization may yield syntactically different (although semantically identical since %a == %b == %c in this scenario) programs when you take different evaluation order.

If two comparisons are not dominated by each other, the comparison that appears earlier (or above) should be evaluated first.

Above here means syntactic (or 'as-written'). That is, the comparison that appears earlier in the iteration should be evaluated before the one appears later in the iteration.

[jhwest1]

I see. Thank you for your comment!

[kkomul1]

If two comparisons are not dominated by each other, the comparison that appears earlier (or above) should be evaluated first.

@strikef I wonder about what "If two comparisons are not dominated by each other" means.

In jhwest1's example code, %cond = icmp eq i32 %a, %c in block 2 dominates %cond2 = icmp eq i32 %b, %c in block 1. Should I handle icmp instuction in block 2 first since it dominates icmp instruction in block 1? Or should I handle icmp instruction in block 1 first since it appears earlier (or above) than icmp instruction in block 2?

[strikef]

Come to think of it, I think it's better to say 'not dominated by one another' than 'not dominated by each other'...

Or to simply put, what I originally meant was 'if two icmps do not have any domination relation between them'.

[kkomul1]

I see. Then, in this case, I should handle icmp in block 2 first since it dominates icmp in block 1.

Thank you for responding so quickly despite the late hour.

[kkomul1]

If two instructions %x and %y are compared, and %x dominates %y, replace %y with %x. If two arguments %x and %y are compared, replace the one which appeared later in the function argument list with the other one which appeared earlier.

I have another question. If two instructions %x and %y are compared, and there is no dominance relation between %x and %y, how can I determine which register should be replaced with the other?

EDIT: I thought about this issue and concluded that there is no case that two registers no dominance between them cannot be operands of icmp eq instruction directly. Is this correct?

[strikef]

Actually they can be compared even if two registers have no dominance relation btw/ them (ex: two regs defined in the same BB) In such cases, replace the register that appeared later with the one appeared earlier.

[Wits15730]

I would like to ask a question about the above comments

1. Is this required? (I see this is the best way to do this, just want to know if it is a HW requirement)

   Then, in this case, I should handle icmp in block 2 first since it dominates icmp in block 1.

2. The HW readme stated that the registers be changed when the BB is dominated by the branch instruction. So, in the example of the phi instruction, you replied

Each phi operand is executed after comparison & dominated by its predecessing basic block, so the suggested optimization should take place.

but in the code, the conditional branch does not dominate the for.end block(that is, taking the if.false path will also lead to for.end), and thus I think the phi instruction should not be modified. Am I missing something?

thank you

[strikef]

1. Is this required? (I see this is the best way to do this, just want to know if it is a HW requirement)

It is required. Otherwise we will have to allow some degree of nondeterminism to the pass when grading, which will increase complexity given that you also have to create your own tests.

---

2. The HW readme stated that the registers be changed when the BB is dominated by the branch instruction....

Actually, the README says

please replace x with y (or y with x) for all uses of x that are (1) executed after the branch is taken (2) dominated by the conditional branch.

Domination relation is not strictly limited to 'between-two-blocks'. Even if the basic block that contains the phi node is not dominated, each phi node entry is still dominated by its predecessor. So, at least the phi node entry should be modified.