[LLVMdev] ABCD Example Failure Given Here

[Stephan Reiter]

I am trying to employ the ABCD optimization pass to remove unnecessary
branches in the code my compiler generates. But in its current form
(yesterday's trunk) the pass changes the behavior of the code such
that execution yields invalid results, which is obviously not what I
want.

The switch in the following listing is used to implement a virtual
method call, 99999 and 100000 are type identifiers used for this
purpose.
To give an example: %6 is an object of type 99999 (the type id is
stored in the aggregate's first field), allocated on a heap that is
emulated on the stack (%3).

----------
%0 = type <{ <{ }>* }>
%1 = type <{ i32, <{ }>, %2* }>
%2 = type <{ i32, <{ }> }>

define void @shade([4 x float]* noalias nocapture, %0* noalias
nocapture) nounwind {
; <label>:2
  %3 = alloca [1024 x i32], align 4               ; <[1024 x i32]*> [#uses=5]
  %4 = bitcast [1024 x i32]* %3 to %1*            ; <%1*> [#uses=1]
  store %1 zeroinitializer, %1* %4, align 4
  %5 = getelementptr inbounds [1024 x i32]* %3, i32 0, i32 0 ; <i32*> [#uses=1]
  store i32 100004, i32* %5
  %6 = getelementptr inbounds [1024 x i32]* %3, i32 0, i32 1 ; <i32*> [#uses=2]
  %7 = getelementptr [1024 x i32]* %3, i32 0, i32 2 ; <i32*> [#uses=2]
  store i32 99999, i32* %7
  %8 = ptrtoint i32* %7 to i32                    ; <i32> [#uses=1]
  store i32 %8, i32* %6
  %9 = getelementptr [1024 x i32]* %3, i32 0, i32 3 ; <i32*> [#uses=1]
  store i32 100003, i32* %9
  %10 = bitcast i32* %6 to %2**                   ; <%2**> [#uses=1]
  %11 = load %2** %10                             ; <%2*> [#uses=1]
  %12 = getelementptr inbounds %2* %11, i32 0, i32 0 ; <i32*> [#uses=1]
  %13 = load i32* %12                             ; <i32> [#uses=1]
  switch i32 %13, label %15 [
    i32 99999, label %14
    i32 100000, label %21
  ]

; <label>:14                                      ; preds = %2
  br label %15

; <label>:15                                      ; preds = %14, %21, %2
  %16 = phi float [ 2.000000e+000, %21 ], [ 1.000000e+000, %14 ], [
0.000000e+000, %2 ] ; <float> [#uses=3]
  %17 = insertvalue [4 x float] undef, float %16, 0 ; <[4 x float]> [#uses=1]
  %18 = insertvalue [4 x float] %17, float %16, 1 ; <[4 x float]> [#uses=1]
  %19 = insertvalue [4 x float] %18, float %16, 2 ; <[4 x float]> [#uses=1]
  %20 = insertvalue [4 x float] %19, float 0.000000e+000, 3 ; <[4 x
float]> [#uses=1]
  store [4 x float] %20, [4 x float]* %0
  ret void

; <label>:21                                      ; preds = %2
  br label %15
}
----------


I apply the LowerSwitch optimization pass to this code, which
transforms the switch into the following series of branches:

----------
  br label %NodeBlock

NodeBlock:                                        ; preds = %2
  %Pivot = icmp slt i32 %13, 100000               ; <i1> [#uses=1]
  br i1 %Pivot, label %LeafBlock, label %LeafBlock5

LeafBlock5:                                       ; preds = %NodeBlock
  %SwitchLeaf6 = icmp eq i32 %13, 100000          ; <i1> [#uses=1]
  br i1 %SwitchLeaf6, label %21, label %NewDefault

LeafBlock:                                        ; preds = %NodeBlock
  %SwitchLeaf = icmp eq i32 %13, 99999            ; <i1> [#uses=1]
  br i1 %SwitchLeaf, label %14, label %NewDefault

NewDefault:                                       ; preds =
%LeafBlock5, %LeafBlock
  br label %15
----------


Applying the ABCD pass yields:

----------
  br label %NodeBlock

NodeBlock:                                        ; preds = %2
  %Pivot = icmp slt i32 %13, 100000               ; <i1> [#uses=0]
  br label %LeafBlock5

LeafBlock5:                                       ; preds = %NodeBlock
  %SSI_sigma1 = phi i32 [ %13, %NodeBlock ]       ; <i32> [#uses=1]
  %SwitchLeaf6 = icmp eq i32 %SSI_sigma1, 100000  ; <i1> [#uses=1]
  br i1 %SwitchLeaf6, label %21, label %NewDefault

LeafBlock:                                        ; No predecessors!
  %SwitchLeaf = icmp eq i32 undef, 99999          ; <i1> [#uses=1]
  br i1 %SwitchLeaf, label %14, label %NewDefault

NewDefault:                                       ; preds =
%LeafBlock, %LeafBlock5
  br label %15
----------

As you can see, the block based on the 99999 type identifier is now no
longer reachable. However, it is the block that would be entered if
the original, untransformed code was executed. Instead, the
transformed code yields an execution of the switch's default case,
which yields a different result.

Could someone take a look at this? After spending some time trying to
get an understanding of the ABCD pass code, I decided that I am not
the one who should attempt to fix this. ;-)

Thanks!
Stephan