Hi Henrique,
I have tried using -mergereturn and inserting a free into the predecessors
of dominance frontier of malloc block and it caused double free. It is
possible for multiple free's to be inserted on the path from malloc to an
exit. For example, in the following CFG:
BB10 (malloc)
/ \
BB11 BB12
... / \ / \ ...
\ / \ / \ /
BB13 BB14 BB15
| ...
| /
BB16
The block BB10 dominates BB11, BB12 and BB14. The dominance frontier of
BB10 contains BB13, BB15 and BB16. So if the predecessors of the dominance
frontier contains BB11, BB12 and BB14. If a call to free is inserted into
BB11, BB12, and BB14, double free would occur. The problem boils down to
this: how can we ensure exactly ONE call to free is inserted at each path
from malloc to all the blocks in dominance frontier?
This problem has some other usage. Frame pointer is needed because there
are variable length objects allocated through alloca. Otherwise, frame
pointer can be omitted as an optimization. If we can ensure that they are
deallocated correctly, frame pointers can be omitted even if variable
length objects exist.
On Wed, Nov 13, 2013 at 5:01 AM, Henrique Santos <
henrique.nazare.santos at gmail.com> wrote:
> It seems that placing the calls to free at the predecessors of dominance
>> frontier is inadequate. It is possible that there are exit blocks that
are
>> dominated by BB12 (calls to malloc). I guess we can also insert calls
to
>> free at these exit blocks too.
>
> That crossed my mind a few minutes later. : )
>
> If you're interested, PRE.cpp existed last at r25315. It calculates the
> "availability frontier" which is probably what you're looking
for.
> I suggest, however, that you try coming up with another solution instead.
> You might consider using -mergereturn.
>
> H.
>
>
> On Wed, Nov 13, 2013 at 2:13 AM, Bin Tzeng <bintzeng at gmail.com>
wrote:
>
>> Hi Henrique,
>> Thanks for the quick reply!
>>
>> On Tue, Nov 12, 2013 at 9:13 PM, Henrique Santos <
>> henrique.nazare.santos at gmail.com> wrote:
>>
>>> PRE normally uses a latest placement algorithm to do something of
the
>>> sort.
>>> I don't know about GVN/PRE, but older version of PRE might have
it.
>>> Just placing the calls to free at the predecessors (dominated by
BB12)
>>> of the dominance frontier of BB12 seems to work, however. Is there
anything
>>> wrong with this?
>>>
>> It seems that placing the calls to free at the predecessors of
dominance
>> frontier is inadequate. It is possible that there are exit blocks that
are
>> dominated by BB12 (calls to malloc). I guess we can also insert calls
to
>> free at these exit blocks too.
>>
>>> H.
>>>
>>>
>>> On Tue, Nov 12, 2013 at 11:30 PM, Bin Tzeng <bintzeng at
gmail.com> wrote:
>>>
>>>> Hi all,
>>>>
>>>> I have been writing a pass to heapify some alloca's (it is
>>>> pessimistization, not optimization). For example, in the
following control
>>>> flow graph, there is a call to malloc inserted in block BB12.
In order to
>>>> avoid memory leak, free's are needed. The free cannot be
inserted in BB23
>>>> because BB23 is not dominated by BB12. There are two ways to go
I can think
>>>> of here. One way is to insert a new basic block, say BB24, to
connect both
>>>> BB21 and BB22 and a free can be inserted into the new block
BB24. The new
>>>> block BB24 has to post-dominate BB12 and all the users of
malloc have to
>>>> happen before BB24. Another way to go is to insert a free in
both BB21 and
>>>> BB22. That is, a free is inserted in all the paths from BB12 to
all exits
>>>> after all users of malloc to avoid memory leak. I wonder
whether there is
>>>> any pass that does similar analysis in order to avoid
duplication of
>>>> efforts.
>>>>
>>>> BB10 (entry)
>>>> / \
>>>> BB11 BB12 (malloc)
>>>> / / \
>>>> BB13 / BB15
>>>> \ / / \
>>>> \ / BB18 BB19
>>>> \ / \ /
>>>> BB20 BB21 BB22
>>>> \ | /
>>>> \ | /
>>>> \ | /
>>>> \ | /
>>>> BB23 (exit)
>>>>
>>>> Any advice is appreciated. Thanks in advance!
>>>> Bill
>>>>
>>>>
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>>>>
>>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20131114/a2dd43a5/attachment.html>
Try breaking the critical edges (-break-crit-edges). This way, a new block will be created between BB13 and BB11 (call this BB11.break) and BB15 and BB12 (call this BB12.break). The predecessors of the dominance frontier will, thus, be BB11.break, BB12.break, and BB14. When we enter through a block with a call to malloc(), we will end up in one of the blocks in the dominance frontier (kind of). These blocks must have multiple predecessors, else it would not be in the dominance frontier. If a predecessors of these blocks has only one successor, then that successor is the block in the dominance frontier and it dominates nobody. If it has multiple successors, then a critical edge will be placed between this predecessor and the block in the dominance frontier. Thus, the predecessor will now be a block that also dominates nobody. This means that we cannot reach another block where a call to free() was inserted without going back to BB10 again. I hope this reasoning make sense. : ) Also, you might also have to treat the special case in which the block where the malloc() is placed dominates the return block. H. On Fri, Nov 15, 2013 at 2:29 AM, Bin Tzeng <bintzeng at gmail.com> wrote:> Hi Henrique, > > I have tried using -mergereturn and inserting a free into the predecessors > of dominance frontier of malloc block and it caused double free. It is > possible for multiple free's to be inserted on the path from malloc to an > exit. For example, in the following CFG: > > BB10 (malloc) > / \ > BB11 BB12 > ... / \ / \ ... > \ / \ / \ / > BB13 BB14 BB15 > | ... > | / > BB16 > > The block BB10 dominates BB11, BB12 and BB14. The dominance frontier of > BB10 contains BB13, BB15 and BB16. So if the predecessors of the dominance > frontier contains BB11, BB12 and BB14. If a call to free is inserted into > BB11, BB12, and BB14, double free would occur. The problem boils down to > this: how can we ensure exactly ONE call to free is inserted at each path > from malloc to all the blocks in dominance frontier? > > This problem has some other usage. Frame pointer is needed because there > are variable length objects allocated through alloca. Otherwise, frame > pointer can be omitted as an optimization. If we can ensure that they are > deallocated correctly, frame pointers can be omitted even if variable > length objects exist. > > On Wed, Nov 13, 2013 at 5:01 AM, Henrique Santos < > henrique.nazare.santos at gmail.com> wrote: > >> It seems that placing the calls to free at the predecessors of dominance >>> frontier is inadequate. It is possible that there are exit blocks that are >>> dominated by BB12 (calls to malloc). I guess we can also insert calls to >>> free at these exit blocks too. >> >> That crossed my mind a few minutes later. : ) >> >> If you're interested, PRE.cpp existed last at r25315. It calculates the >> "availability frontier" which is probably what you're looking for. >> I suggest, however, that you try coming up with another solution instead. >> You might consider using -mergereturn. >> >> H. >> >> >> On Wed, Nov 13, 2013 at 2:13 AM, Bin Tzeng <bintzeng at gmail.com> wrote: >> >>> Hi Henrique, >>> Thanks for the quick reply! >>> >>> On Tue, Nov 12, 2013 at 9:13 PM, Henrique Santos < >>> henrique.nazare.santos at gmail.com> wrote: >>> >>>> PRE normally uses a latest placement algorithm to do something of the >>>> sort. >>>> I don't know about GVN/PRE, but older version of PRE might have it. >>>> Just placing the calls to free at the predecessors (dominated by BB12) >>>> of the dominance frontier of BB12 seems to work, however. Is there anything >>>> wrong with this? >>>> >>> It seems that placing the calls to free at the predecessors of dominance >>> frontier is inadequate. It is possible that there are exit blocks that are >>> dominated by BB12 (calls to malloc). I guess we can also insert calls to >>> free at these exit blocks too. >>> >>>> H. >>>> >>>> >>>> On Tue, Nov 12, 2013 at 11:30 PM, Bin Tzeng <bintzeng at gmail.com> wrote: >>>> >>>>> Hi all, >>>>> >>>>> I have been writing a pass to heapify some alloca's (it is >>>>> pessimistization, not optimization). For example, in the following control >>>>> flow graph, there is a call to malloc inserted in block BB12. In order to >>>>> avoid memory leak, free's are needed. The free cannot be inserted in BB23 >>>>> because BB23 is not dominated by BB12. There are two ways to go I can think >>>>> of here. One way is to insert a new basic block, say BB24, to connect both >>>>> BB21 and BB22 and a free can be inserted into the new block BB24. The new >>>>> block BB24 has to post-dominate BB12 and all the users of malloc have to >>>>> happen before BB24. Another way to go is to insert a free in both BB21 and >>>>> BB22. That is, a free is inserted in all the paths from BB12 to all exits >>>>> after all users of malloc to avoid memory leak. I wonder whether there is >>>>> any pass that does similar analysis in order to avoid duplication of >>>>> efforts. >>>>> >>>>> BB10 (entry) >>>>> / \ >>>>> BB11 BB12 (malloc) >>>>> / / \ >>>>> BB13 / BB15 >>>>> \ / / \ >>>>> \ / BB18 BB19 >>>>> \ / \ / >>>>> BB20 BB21 BB22 >>>>> \ | / >>>>> \ | / >>>>> \ | / >>>>> \ | / >>>>> BB23 (exit) >>>>> >>>>> Any advice is appreciated. Thanks in advance! >>>>> Bill >>>>> >>>>> >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>>>> >>>>> >>>> >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131115/a5927e88/attachment.html>
On Fri, Nov 15, 2013 at 8:33 AM, Henrique Santos < henrique.nazare.santos at gmail.com> wrote:> Try breaking the critical edges (-break-crit-edges). > This way, a new block will be created between BB13 and BB11 (call this > BB11.break) and BB15 and BB12 (call this BB12.break). > The predecessors of the dominance frontier will, thus, be BB11.break, > BB12.break, and BB14. > > When we enter through a block with a call to malloc(), we will end up in > one of the blocks in the dominance frontier (kind of). These blocks must > have multiple predecessors, else it would not be in the dominance frontier. > If a predecessors of these blocks has only one successor, then that > successor is the block in the dominance frontier and it dominates nobody. > If it has multiple successors, then a critical edge will be placed between > this predecessor and the block in the dominance frontier. Thus, the > predecessor will now be a block that also dominates nobody. This means that > we cannot reach another block where a call to free() was inserted without > going back to BB10 again. > I hope this reasoning make sense. : ) >That makes sense! It is nice to have such as pass to insert dummy blocks on critical edges. I just implemented that and am debugging it. Thanks!> > Also, you might also have to treat the special case in which the block > where the malloc() is placed dominates the return block. > > H. > > > > On Fri, Nov 15, 2013 at 2:29 AM, Bin Tzeng <bintzeng at gmail.com> wrote: > >> Hi Henrique, >> >> I have tried using -mergereturn and inserting a free into the >> predecessors of dominance frontier of malloc block and it caused double >> free. It is possible for multiple free's to be inserted on the path from >> malloc to an exit. For example, in the following CFG: >> >> BB10 (malloc) >> / \ >> BB11 BB12 >> ... / \ / \ ... >> \ / \ / \ / >> BB13 BB14 BB15 >> | ... >> | / >> BB16 >> >> The block BB10 dominates BB11, BB12 and BB14. The dominance frontier of >> BB10 contains BB13, BB15 and BB16. So if the predecessors of the dominance >> frontier contains BB11, BB12 and BB14. If a call to free is inserted into >> BB11, BB12, and BB14, double free would occur. The problem boils down to >> this: how can we ensure exactly ONE call to free is inserted at each path >> from malloc to all the blocks in dominance frontier? >> >> This problem has some other usage. Frame pointer is needed because there >> are variable length objects allocated through alloca. Otherwise, frame >> pointer can be omitted as an optimization. If we can ensure that they are >> deallocated correctly, frame pointers can be omitted even if variable >> length objects exist. >> >> On Wed, Nov 13, 2013 at 5:01 AM, Henrique Santos < >> henrique.nazare.santos at gmail.com> wrote: >> >>> It seems that placing the calls to free at the predecessors of dominance >>>> frontier is inadequate. It is possible that there are exit blocks that are >>>> dominated by BB12 (calls to malloc). I guess we can also insert calls to >>>> free at these exit blocks too. >>> >>> That crossed my mind a few minutes later. : ) >>> >>> If you're interested, PRE.cpp existed last at r25315. It calculates the >>> "availability frontier" which is probably what you're looking for. >>> I suggest, however, that you try coming up with another solution >>> instead. You might consider using -mergereturn. >>> >>> H. >>> >>> >>> On Wed, Nov 13, 2013 at 2:13 AM, Bin Tzeng <bintzeng at gmail.com> wrote: >>> >>>> Hi Henrique, >>>> Thanks for the quick reply! >>>> >>>> On Tue, Nov 12, 2013 at 9:13 PM, Henrique Santos < >>>> henrique.nazare.santos at gmail.com> wrote: >>>> >>>>> PRE normally uses a latest placement algorithm to do something of the >>>>> sort. >>>>> I don't know about GVN/PRE, but older version of PRE might have it. >>>>> Just placing the calls to free at the predecessors (dominated by BB12) >>>>> of the dominance frontier of BB12 seems to work, however. Is there anything >>>>> wrong with this? >>>>> >>>> It seems that placing the calls to free at the predecessors of >>>> dominance frontier is inadequate. It is possible that there are exit blocks >>>> that are dominated by BB12 (calls to malloc). I guess we can also insert >>>> calls to free at these exit blocks too. >>>> >>>>> H. >>>>> >>>>> >>>>> On Tue, Nov 12, 2013 at 11:30 PM, Bin Tzeng <bintzeng at gmail.com>wrote: >>>>> >>>>>> Hi all, >>>>>> >>>>>> I have been writing a pass to heapify some alloca's (it is >>>>>> pessimistization, not optimization). For example, in the following control >>>>>> flow graph, there is a call to malloc inserted in block BB12. In order to >>>>>> avoid memory leak, free's are needed. The free cannot be inserted in BB23 >>>>>> because BB23 is not dominated by BB12. There are two ways to go I can think >>>>>> of here. One way is to insert a new basic block, say BB24, to connect both >>>>>> BB21 and BB22 and a free can be inserted into the new block BB24. The new >>>>>> block BB24 has to post-dominate BB12 and all the users of malloc have to >>>>>> happen before BB24. Another way to go is to insert a free in both BB21 and >>>>>> BB22. That is, a free is inserted in all the paths from BB12 to all exits >>>>>> after all users of malloc to avoid memory leak. I wonder whether there is >>>>>> any pass that does similar analysis in order to avoid duplication of >>>>>> efforts. >>>>>> >>>>>> BB10 (entry) >>>>>> / \ >>>>>> BB11 BB12 (malloc) >>>>>> / / \ >>>>>> BB13 / BB15 >>>>>> \ / / \ >>>>>> \ / BB18 BB19 >>>>>> \ / \ / >>>>>> BB20 BB21 BB22 >>>>>> \ | / >>>>>> \ | / >>>>>> \ | / >>>>>> \ | / >>>>>> BB23 (exit) >>>>>> >>>>>> Any advice is appreciated. Thanks in advance! >>>>>> Bill >>>>>> >>>>>> >>>>>> _______________________________________________ >>>>>> LLVM Developers mailing list >>>>>> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >>>>>> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >>>>>> >>>>>> >>>>> >>>> >>> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131115/51780ced/attachment.html>
Possibly Parallel Threads
- [LLVMdev] dominator, post-dominator and memory leak
- [LLVMdev] dominator, post-dominator and memory leak
- [LLVMdev] dominator, post-dominator and memory leak
- [LLVMdev] dominator, post-dominator and memory leak
- [LLVMdev] dominator, post-dominator and memory leak