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
Could someone refer me to documentation, or give me a brief explanation as to why the following will not work--with the caveat that I am still new to this, and have not gotten beyond generating and running jitted code via the LLVM libraries: Imagine three functions fa, fb, fc where fa, and fc are generated and jitted with llvm. Function fb on the other hand has external C linkage and is statically compiled along with the llvm generating code into one executable. - fc merely executes an unwind. - fa uses invoke to call fb, passing its own arguments to it, which in turn calls fc. - At runtime fa is called (after jitting from a main(...) C routine), with a pointer to an ExecutionEngine instance, and a Function pointer to fc, both typed as Type::Int8Ty->getPointerTo() (at code generation time). - fa takes these arguments and invokes fb with them. - fb being a non-generated C function, takes the passed in Function pointer and engine instance, retrieves the jitted C pointer, and calls it. - As this pointer is a pointer to fc, the unwind is then executed. Basically I have the call stack fa->fb->fc with fa, fc generated and fb not generated. Given that I was using the intuitive model of a setjump, longjump, I thought that fc's unwind would pass through fb and end up at fa's invoke's exception block. However it cores even though I've verified that each function is being executed. So I guess either there is something fundamental I don't understand, or I have another issue. Although I'm assuming this problem is obvious to those in the know, I can supply test code if desired. Thanks in advance Garrison
Hi Garrison,> - fc merely executes an unwind.the code generators do not know how to codegen unwind. Only the interpreter has support for it. Yes, this sucks. You will need to call the libgcc unwind routine directly. Ciao, Duncan.
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