Hi,<br><br>This is a follow-up to the previous question about ExtractLoop().<br><br>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.<br>
<br>Does anyone have any idea on this?<br><br>Thanks a lot.<br><br>Jack<br><br><br><div class="gmail_quote">On Mon, Nov 17, 2008 at 5:42 PM, Jack Tzu-Han Hung <span dir="ltr"><<a href="mailto:thhung@cs.princeton.edu">thhung@cs.princeton.edu</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Hi,<br><br>I have a question about ExtractLoop() in CodeExtractor.cpp.<br><br>The sample code is a simple list traversal, as attached. The generated bitcode (from llvm-gcc -O1) is shown below.<br>
<br>--------------------------------------------------------------------------------------------------------------------------------<br>
define i32 @walk(%struct.node2* %list2) nounwind {<br>entry:<br>        %0 = icmp eq %struct.node2* %list2, null                ; <i1> [#uses=1]<br>        br i1 %0, label %bb2, label %bb<br><br>bb:             ; preds = %bb, %entry<br>

        %list2_addr.05 = phi %struct.node2* [ %list2, %entry ], [ %5, %bb ]             ; <%struct.node2*> [#uses=2]<br>        %sum.04 = phi i32 [ 0, %entry ], [ %3, %bb ]            ; <i32> [#uses=1]<br>        %1 = getelementptr %struct.node2* %list2_addr.05, i32 0, i32 1          ; <i32*> [#uses=1]<br>

        %2 = load i32* %1, align 4              ; <i32> [#uses=1]<br>        %3 = add i32 %2, %sum.04                ; <i32> [#uses=2]<br>        %4 = getelementptr %struct.node2* %list2_addr.05, i32 0, i32 0          ; <%struct.node2**> [#uses=1]<br>

        %5 = load %struct.node2** %4, align 4           ; <%struct.node2*> [#uses=2]<br>        %phitmp = icmp eq %struct.node2* %5, null               ; <i1> [#uses=1]<br>        br i1 %phitmp, label %bb2, label %bb<br>

<br>bb2:            ; preds = %bb, %entry<br>        %sum.0.lcssa = phi i32 [ 0, %entry ], [ %3, %bb ]               ; <i32> [#uses=1]<br>        ret i32 %sum.0.lcssa<br>}<br>--------------------------------------------------------------------------------------------------------------------------------<br>

<br>When ExtractLoop is applied to the loop (containing bb), it will generate an additional function as follows.<br><br>--------------------------------------------------------------------------------------------------------------------------------<br>

define internal void @walk_bb(%struct.node2* %list2, i32* %.out) {<br>newFuncRoot:<br>        br label %bb<br><br>bb2.exitStub:           ; preds = %bb<br>        ret void<br><br>bb:             ; preds = %bb, %newFuncRoot<br>

        %list2_addr.05 = phi %struct.node2* [ %list2, %newFuncRoot ], [ %4, %bb ]               ; <%struct.node2*> [#uses=2]<br>        %sum.04 = phi i32 [ 0, %newFuncRoot ], [ %2, %bb ]              ; <i32> [#uses=1]<br>

        %0 = getelementptr %struct.node2* %list2_addr.05, i32 0, i32 1          ; <i32*> [#uses=1]<br>        %1 = load i32* %0, align 4              ; <i32> [#uses=1]<br>        %2 = add i32 %1, %sum.04                ; <i32> [#uses=1]<br>

        %3 = getelementptr %struct.node2* %list2_addr.05, i32 0, i32 0          ; <%struct.node2**> [#uses=1]<br>        %4 = load %struct.node2** %3, align 4           ; <%struct.node2*> [#uses=2]<br>        %phitmp = icmp eq %struct.node2* %4, null               ; <i1> [#uses=1]<br>

        br i1 %phitmp, label %bb2.exitStub, label %bb<br>}<br>--------------------------------------------------------------------------------------------------------------------------------<br><br>The problem is that the output variable (.out, in this case) is not store at the .exitStub block.<br>

<br>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?<br>

<br>Thank you in advance.<br><font color="#888888"><br>Jack<br><br>
</font></blockquote></div><br><br clear="all"><br>-- <br>Jack Tzu-Han Hung<br><a href="http://www.cs.princeton.edu/~thhung">www.cs.princeton.edu/~thhung</a><br>