[LLVMdev] dominator, post-dominator and memory leak
Bin Tzeng
bintzeng at gmail.com
Fri Nov 15 10:50:37 PST 2013
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>
More information about the llvm-dev
mailing list