[LLVMdev] Question about ExtractLoop

[Jack Tzu-Han Hung]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20081117/fe2f9121/attachment.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: le.c
Type: text/x-csrc
Size: 1033 bytes
Desc: not available
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20081117/fe2f9121/attachment.c>