[LLVMdev] DominanceFrontier/PostDominanceFrontier for PRE

[Shuxin Yang]

On 11/3/13 1:12 AM, Daniel Berlin wrote:
> On Sun, Nov 3, 2013 at 1:02 AM, Daniel Berlin <dberlin at dberlin.org> wrote:
>> Is there a reason this is better than the modified algorithm created
>> by Ferrante?
>> It looks like yours has as bad a worst case time bound in reality.
>> That is, the algorithm runs in O(sum of the size of all the dominance
>> frontiers).
>>
>> http://www.cs.rice.edu/~keith/Embed/dom.pdf
>>
>> See figure 5. It will only touch nodes actually in the dominance frontier.
>>
> Note this is mostly rhetorical, as that the paper asserts about the
> dominance frontier algorithm in figure 5: "we contend that the sets
> cannot be built any more efficiently".
> Given the paper's authors, I have a tendency to trust this assertion.
APint can be considered as a dense bit set. Dose it look horrible to you 
:-)?
Sparse bit-set for base-blocks is not inefficient either.  Of course, 
other sets
are scary, I agree.

Normally, a function have no more than 200 bb, making the cost of bit-set
operation almost negligible in practice. Another benefit of using bit-set is
the nice locality.

Anyway, it's just my random boring idea. I believe it maybe 
fundamentally flawed.
Thank you for sharing your insight. But since Christopher is asking 
something else,
let us don't discuss this algorithm to deviate  the original topic:-)

Thanks
Shuxin