<html>
<head>
<meta content="text/html; charset=ISO-8859-1"
http-equiv="Content-Type">
</head>
<body text="#000000" bgcolor="#FFFFFF">
<div class="moz-cite-prefix">Hi, <br>
<br>
I'm not able to answer your question. I'm wondering if you can
create your own if it is just your own hobby project, <br>
or a project that you don't have to commit to the main repository.
<br>
<br>
Creating DominatorFrontier seems to be expensive. However, if
you are using bit-vector to represent a basic-block-set, I <br>
guess it can be done in linear time in practice. Following is
the algorithm in my mind, I never see people implement<br>
DF this way, and myself are lazying about implementing one.
However, I don't see a problem. Maybe you can try <br>
this one. !!!!!!Caveat: It is at your own risk, as this algorithm
is not proved at all!!!!!<br>
<br>
---------------------------<br>
Let DF(N) be { x | x is N's dom-frontier} <br>
Let Dom(N) be { x | x is dominated by N}<br>
"kid" = successor in dominator tree<br>
"succ" = successor in CFG. <br>
<br>
compute_df(function f) {<br>
walk f's dominator tree from bottom up {<br>
Let N be the node being visited.<br>
1: DF(N) = union of DF(K) where K is N's immediate kid
in dom-tree<br>
2; DF(N) -= DOM(N)<br>
3: DF(N) += { some N's immediate CFG succ which
qualified as DF.} <br>
}<br>
}<br>
---------------------------------------<br>
<br>
I think the algorithm is almost linear because: <br>
o. it walk the dom-tree only once. <br>
o. the # of union in step 1 is exactly the # of edge in
dom-tree.<br>
o. step 2 is nothing if the cfg has no more than 100
basic-block (the set can be represented by some integers)<br>
o. step 3 is nothing as normally a block only have two
immediate succ. <br>
<br>
Again this algorithm is just random idea. It is at your own risk
if you try it. <br>
<br>
On 11/1/13 9:18 PM, Christopher Wood wrote:<br>
</div>
<blockquote
cite="mid:CAO8oSXnhgN0si8840tG6WgTyKmi0_C4d6xed8LkM6HqGn-o0Tw@mail.gmail.com"
type="cite">
<div dir="ltr">
<div>Hi all,<br>
<br>
Does anyone know how to recreate the DominanceFronter and
PostDominanceFrontier structures using the API of the latest
release? To my knowledge, these are needed to implement a PRE
pass (<a moz-do-not-send="true"
href="https://llvm.org/svn/llvm-project/llvm/tags/RELEASE_13/lib/Transforms/Scalar/PRE.cpp">as
done in the past</a>), but they were removed a while ago for
efficiency reasons. Is there a better way to implement PRE
using the current API, or, alternatively, is there an easier
way to construct these data structures?<br>
<br>
</div>
Thanks in advance for any help you can provide.<br>
<br>
Cheers,<br>
Chris<br>
</div>
<br>
<fieldset class="mimeAttachmentHeader"></fieldset>
<br>
<pre wrap="">_______________________________________________
LLVM Developers mailing list
<a class="moz-txt-link-abbreviated" href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a> <a class="moz-txt-link-freetext" href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a>
<a class="moz-txt-link-freetext" href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a>
</pre>
</blockquote>
<br>
</body>
</html>