llvm dev - Jan 2011 - [LLVMdev] Update PHINode after extracting code

On 01/26/2011 07:50 PM, Vu Le wrote:
> I guess I didn't have a clear question.
>
> Suppose we have BB1 and BB2 both point to BB3.
> BB1 has variable x. BB2 also as variable x.
> BB3 will have PHINode for x with 2 value from BB1 and BB2.
> BB1   BB2
>     \       /
>       BB3
>
> Now if BB1 and BB2 is extracted into a function
> (using ExtractCodeRegion), they will be replaced by
> a basic block called codeRepl (which has a call to the extracted
> function).
> codeRepl
>       |
>      BB3
>
> The problem is that the PHINode in BB3 still has 2 values x,
> both from codeRepl. That's wrong because BB3 has only 1 successors,
> which is codeRepl. In fact, there is NO way to update PhiNode,
> because all the x are from ONE node, codeRepl.
> So the function ExtractCodeRegion doesn't work in this example.
>
> My solution for this is before extracting BB1 and BB2, I split the PHINode
> in BB3 into another basic block
> BB1   BB2
>     \       /
>     PhiBB
>         |
>        BB
> And extract BB1, BB2 and PhiBB.
> If you have any ideas or if you think this will not work, please let me
> know.
> Thanks.
> Vu
Hi Vu,

I believe this is the right approach. If I am right and you work on the 
RegionInfo pass I believe what you want is only to extract so called 
simpleRegions that have just a single entry and exit edge.

Have a look at the email from Andreas Simbuerger two weeks ago:

[llvm-commits] [PATCH] Add SeSeRegionInfo transform pass

This should contain the functions needed to transform a refined region 
into a simple region. Either we get this patch committed and you could 
just use this pass or we add the corresponding functions to RegionInfo 
and you translate just the regions that you finally will extract.

Cheers
Tobi

Hi Tobias,
If the PHI node at exit block of region R has multiple inputs from the R,
I split the exit block into 2.
The first block contains all PHI nodes whose input are all from the region.
The second is the new exit node.

All branches (outside R) to the old exit now point the new exit.
All regions whose exit is the old exit are also updated with the new exit
node.

It works like a charm.
Thanks.
Vu
On Wed, Jan 26, 2011 at 7:26 PM, Tobias Grosser
<grosser at fim.uni-passau.de>wrote:
> On 01/26/2011 07:50 PM, Vu Le wrote:
>
>> I guess I didn't have a clear question.
>>
>> Suppose we have BB1 and BB2 both point to BB3.
>> BB1 has variable x. BB2 also as variable x.
>> BB3 will have PHINode for x with 2 value from BB1 and BB2.
>> BB1   BB2
>>    \       /
>>      BB3
>>
>> Now if BB1 and BB2 is extracted into a function
>> (using ExtractCodeRegion), they will be replaced by
>> a basic block called codeRepl (which has a call to the extracted
>> function).
>> codeRepl
>>      |
>>     BB3
>>
>> The problem is that the PHINode in BB3 still has 2 values x,
>> both from codeRepl. That's wrong because BB3 has only 1 successors,
>> which is codeRepl. In fact, there is NO way to update PhiNode,
>> because all the x are from ONE node, codeRepl.
>> So the function ExtractCodeRegion doesn't work in this example.
>>
>> My solution for this is before extracting BB1 and BB2, I split the
PHINode
>> in BB3 into another basic block
>> BB1   BB2
>>    \       /
>>    PhiBB
>>        |
>>       BB
>> And extract BB1, BB2 and PhiBB.
>> If you have any ideas or if you think this will not work, please let me
>> know.
>> Thanks.
>> Vu
>>
>
> Hi Vu,
>
> I believe this is the right approach. If I am right and you work on the
> RegionInfo pass I believe what you want is only to extract so called
> simpleRegions that have just a single entry and exit edge.
>
> Have a look at the email from Andreas Simbuerger two weeks ago:
>
> [llvm-commits] [PATCH] Add SeSeRegionInfo transform pass
>
> This should contain the functions needed to transform a refined region into
> a simple region. Either we get this patch committed and you could just use
> this pass or we add the corresponding functions to RegionInfo and you
> translate just the regions that you finally will extract.
>
> Cheers
> Tobi
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20110126/5d76bad3/attachment.html>

On 01/27/2011 12:48 AM, Vu Le wrote:
> Hi Tobias,
> If the PHI node at exit block of region R has multiple inputs from the R,
> I split the exit block into 2.
> The first block contains all PHI nodes whose input are all from the region.
> The second is the new exit node.
>
> All branches (outside R) to the old exit now point the new exit.
> All regions whose exit is the old exit are also updated with the new
> exit node.
>
> It works like a charm.
Great. Did you check with Andreas patch. I believe you also may need to 
update the entry nodes of all regions that started at the old node to 
the new node.

Are you going to contribute your region extractor? It would be pretty 
useful for me.

Cheers
Tobi