[LLVMdev] Question about ExtractLoop

[Jack Tzu-Han Hung]

Hi,

This is a follow-up to the previous question about ExtractLoop().

I just found that the live-outs are same for all the loop exit blocks (in
the current implementation of loop extraction). If we remember the live-outs
for each exit block (this can be done in findInputsOutputs()), and store the
necessary live-outs at each exit block (in emitCallAndSwitchStatement()),
then we may not need to do the dominance check.

Does anyone have any idea on this?

Thanks a lot.

Jack


On Mon, Nov 17, 2008 at 5:42 PM, Jack Tzu-Han Hung
<thhung at cs.princeton.edu>wrote:

> Hi,
>
> I have a question about ExtractLoop() in CodeExtractor.cpp.
>
> The sample code is a simple list traversal, as attached. The generated
> bitcode (from llvm-gcc -O1) is shown below.
>
>
> --------------------------------------------------------------------------------------------------------------------------------
> define i32 @walk(%struct.node2* %list2) nounwind {
> entry:
>         %0 = icmp eq %struct.node2* %list2, null                ; <i1>
> [#uses=1]
>         br i1 %0, label %bb2, label %bb
>
> bb:             ; preds = %bb, %entry
>         %list2_addr.05 = phi %struct.node2* [ %list2, %entry ], [ %5, %bb
> ]             ; <%struct.node2*> [#uses=2]
>         %sum.04 = phi i32 [ 0, %entry ], [ %3, %bb ]            ; <i32>
> [#uses=1]
>         %1 = getelementptr %struct.node2* %list2_addr.05, i32 0, i32
> 1          ; <i32*> [#uses=1]
>         %2 = load i32* %1, align 4              ; <i32> [#uses=1]
>         %3 = add i32 %2, %sum.04                ; <i32> [#uses=2]
>         %4 = getelementptr %struct.node2* %list2_addr.05, i32 0, i32
> 0          ; <%struct.node2**> [#uses=1]
>         %5 = load %struct.node2** %4, align 4           ; <%struct.node2*>
> [#uses=2]
>         %phitmp = icmp eq %struct.node2* %5, null               ; <i1>
> [#uses=1]
>         br i1 %phitmp, label %bb2, label %bb
>
> bb2:            ; preds = %bb, %entry
>         %sum.0.lcssa = phi i32 [ 0, %entry ], [ %3, %bb ]               ;
> <i32> [#uses=1]
>         ret i32 %sum.0.lcssa
> }
>
> --------------------------------------------------------------------------------------------------------------------------------
>
> When ExtractLoop is applied to the loop (containing bb), it will generate
> an additional function as follows.
>
>
> --------------------------------------------------------------------------------------------------------------------------------
> define internal void @walk_bb(%struct.node2* %list2, i32* %.out) {
> newFuncRoot:
>         br label %bb
>
> bb2.exitStub:           ; preds = %bb
>         ret void
>
> bb:             ; preds = %bb, %newFuncRoot
>         %list2_addr.05 = phi %struct.node2* [ %list2, %newFuncRoot ], [ %4,
> %bb ]               ; <%struct.node2*> [#uses=2]
>         %sum.04 = phi i32 [ 0, %newFuncRoot ], [ %2, %bb ]              ;
> <i32> [#uses=1]
>         %0 = getelementptr %struct.node2* %list2_addr.05, i32 0, i32
> 1          ; <i32*> [#uses=1]
>         %1 = load i32* %0, align 4              ; <i32> [#uses=1]
>         %2 = add i32 %1, %sum.04                ; <i32> [#uses=1]
>         %3 = getelementptr %struct.node2* %list2_addr.05, i32 0, i32
> 0          ; <%struct.node2**> [#uses=1]
>         %4 = load %struct.node2** %3, align 4           ; <%struct.node2*>
> [#uses=2]
>         %phitmp = icmp eq %struct.node2* %4, null               ; <i1>
> [#uses=1]
>         br i1 %phitmp, label %bb2.exitStub, label %bb
> }
>
> --------------------------------------------------------------------------------------------------------------------------------
>
> The problem is that the output variable (.out, in this case) is not store
> at the .exitStub block.
>
> I checked the implementation in emitCallAndSwitchStatement() (in
> CodeExtractor.cpp) and found that the values will be stored only when bb
> dominates bb2, when is not true in this example. I'm not sure why is the
> check on dominance relationship needed (even though it's not completely
> correct.) Could anyone please answer this question?
>
> Thank you in advance.
>
> Jack
>
>


-- 
Jack Tzu-Han Hung
www.cs.princeton.edu/~thhung
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20081121/b6901fc0/attachment.html>