[LLVMdev] ABCD Example Failure Given Here
Owen Anderson
resistor at mac.com
Wed Nov 18 11:31:07 PST 2009
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
More information about the llvm-dev
mailing list