[LLVMdev] ABCD Example Failure Given Here

[Owen Anderson]

Stephan, 

The ABCD pass is known not to work at this time.  It doesn't pass large swaths of the nightly testsuite.

--Owen

On Nov 18, 2009, at 4:02 AM, Stephan Reiter wrote:

> 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
> _______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev