Hi folks,<br><br>Hope this is not a silly question. But it bothers me when I am thinking about it.<br><br>My question is:<br>1. In the implementation of serverSplitPHINodes(), why it only checks the first PHI node for possible<br>
multiple inputs from outside the region to extract. There could be more than one PHI nodes in the header<br> block, and the code only checks the first one. I don't quite get it. What if the first PHI node contains only<br>
incoming values from inside the region, while subsequent PHI nodes have inputs from outside? Is that possible?<br><br>2. Oddly, later in the code, it creates a corresponding new PHI node in the newBB for each PHI in the old header block. And<br>
then it adds the old PHI node as an incoming value to the newPHI node. This is Okay for the first PHI node of original header<br> as it's been proved to have multiple inputs from outside the region earlier. But it does not make sense for subsequent PHI nodes since they<br>
may contain only incoming values from inside. Then what's the point of adding it as an incoming value to the new PHI when it<br> doesn't even have anything from outside. This looks redundant to me. <br><br>
I could only guess it has something to do with the way PHI nodes get inserted in LLVM. Any help is much appreciated!!! <br><br><pre class="fragment"><span class="comment">/// severSplitPHINodes - If a PHI node has multiple inputs from outside of the</span>
<a name="l00185"></a>00185 <span class="comment">/// region, we need to split the entry block of the region so that the PHI node</span>
<a name="l00186"></a>00186 <span class="comment">/// is easier to deal with.</span>
<a name="l00187"></a>00187 <span class="comment"></span><span class="keywordtype">void</span> CodeExtractor::severSplitPHINodes(<a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html" title="LLVM Basic Block Representation.">BasicBlock</a> *&Header) {
<a name="l00188"></a>00188 <span class="keywordtype">unsigned</span> NumPredsFromRegion = 0;
<a name="l00189"></a>00189 <span class="keywordtype">unsigned</span> NumPredsOutsideRegion = 0;
<a name="l00190"></a>00190
<a name="l00191"></a>00191 <span class="keywordflow">if</span> (Header != &Header-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#aca229503e4f5c83a187a6a921c625fa8" title="Return the enclosing method, or null if none.">getParent</a>()-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1Function.html#a30f2c362631e3728d2f47a8203071ade">getEntryBlock</a>()) {
<a name="l00192"></a>00192 <a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html">PHINode</a> *PN = <a class="code" href="http://llvm.org/docs/doxygen/html/namespacellvm.html#ad6dbabbbb9495cf1501d64a5c71729ed">dyn_cast</a><<a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html">PHINode</a>>(Header-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0ed5f3ab3c2e4196ee0cffffa080c062">begin</a>());
<a name="l00193"></a>00193 <span class="keywordflow">if</span> (!PN) <span class="keywordflow">return</span>; <span class="comment">// No PHI nodes.</span>
<a name="l00194"></a>00194
<a name="l00195"></a>00195 <span class="comment">// If the header node contains any PHI nodes, check to see if there is more</span>
<a name="l00196"></a>00196 <span class="comment">// than one entry from outside the region. If so, we need to sever the</span>
<a name="l00197"></a>00197 <span class="comment">// header block into two.</span>
<a name="l00198"></a>00198 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0, e = PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#aa45f6c0433576e3858a6209a43750ad4">getNumIncomingValues</a>(); i != e; ++i)
<a name="l00199"></a>00199 <span class="keywordflow">if</span> (Blocks.<a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a0fd2953d62c1b1cabb87e420be5177c4" title="Count the number of elements of a given key in the SetVector.">count</a>(PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081">getIncomingBlock</a>(i)))
<a name="l00200"></a>00200 ++NumPredsFromRegion;
<a name="l00201"></a>00201 <span class="keywordflow">else</span>
<a name="l00202"></a>00202 ++NumPredsOutsideRegion;
<a name="l00203"></a>00203
<a name="l00204"></a>00204 <span class="comment">// If there is one (or fewer) predecessor from outside the region, we don't</span>
<a name="l00205"></a>00205 <span class="comment">// need to do anything special.</span>
<a name="l00206"></a>00206 <span class="keywordflow">if</span> (NumPredsOutsideRegion <= 1) <span class="keywordflow">return</span>;
<a name="l00207"></a>00207 }
<a name="l00208"></a>00208
<a name="l00209"></a>00209 <span class="comment">// Otherwise, we need to split the header block into two pieces: one</span>
<a name="l00210"></a>00210 <span class="comment">// containing PHI nodes merging values from outside of the region, and a</span>
<a name="l00211"></a>00211 <span class="comment">// second that contains all of the code for the block and merges back any</span>
<a name="l00212"></a>00212 <span class="comment">// incoming values from inside of the region.</span>
<a name="l00213"></a>00213 <a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1ilist__iterator.html">BasicBlock::iterator</a> AfterPHIs = Header-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0e73f4e09745bb69fdd7b15232c45428" title="Returns a pointer to the first instruction in this block that is not a PHINode instruction.">getFirstNonPHI</a>();
<a name="l00214"></a>00214 <a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html" title="LLVM Basic Block Representation.">BasicBlock</a> *NewBB = Header-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a19445f836d9e1ecb32cba27ec4338fff" title="Split the basic block into two basic blocks at the specified instruction.">splitBasicBlock</a>(AfterPHIs,
<a name="l00215"></a>00215 Header-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1Value.html#ad452febc1ac0b394876e640ec03ffa38">getName</a>()+<span class="stringliteral">".ce"</span>);
<a name="l00216"></a>00216
<a name="l00217"></a>00217 <span class="comment">// We only want to code extract the second block now, and it becomes the new</span>
<a name="l00218"></a>00218 <span class="comment">// header of the region.</span>
<a name="l00219"></a>00219 <a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html" title="LLVM Basic Block Representation.">BasicBlock</a> *OldPred = Header;
<a name="l00220"></a>00220 Blocks.<a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a6357ff5654c7cbe5fed8516dc8328eb4" title="Remove an item from the set vector.">remove</a>(OldPred);
<a name="l00221"></a>00221 Blocks.<a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a72d928b7fc2c5f2d56c6ac0265fd9c6e" title="Insert a new element into the SetVector.">insert</a>(NewBB);
<a name="l00222"></a>00222 Header = NewBB;
<a name="l00223"></a>00223
<a name="l00224"></a>00224 <span class="comment">// Okay, update dominator sets. The blocks that dominate the new one are the</span>
<a name="l00225"></a>00225 <span class="comment">// blocks that dominate TIBB plus the new block itself.</span>
<a name="l00226"></a>00226 <span class="keywordflow">if</span> (DT)
<a name="l00227"></a>00227 DT-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1DominatorTree.html#a3d5044cf4966abb56510f1883d275745">splitBlock</a>(NewBB);
<a name="l00228"></a>00228
<a name="l00229"></a>00229 <span class="comment">// Okay, now we need to adjust the PHI nodes and any branches from within the</span>
<a name="l00230"></a>00230 <span class="comment">// region to go to the new header block instead of the old header block.</span>
<a name="l00231"></a>00231 <span class="keywordflow">if</span> (NumPredsFromRegion) {
<a name="l00232"></a>00232 <a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html">PHINode</a> *PN = cast<PHINode>(OldPred-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0ed5f3ab3c2e4196ee0cffffa080c062">begin</a>());
<a name="l00233"></a>00233 <span class="comment">// Loop over all of the predecessors of OldPred that are in the region,</span>
<a name="l00234"></a>00234 <span class="comment">// changing them to branch to NewBB instead.</span>
<a name="l00235"></a>00235 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0, e = PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#aa45f6c0433576e3858a6209a43750ad4">getNumIncomingValues</a>(); i != e; ++i)
<a name="l00236"></a>00236 <span class="keywordflow">if</span> (Blocks.<a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a0fd2953d62c1b1cabb87e420be5177c4" title="Count the number of elements of a given key in the SetVector.">count</a>(PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081">getIncomingBlock</a>(i))) {
<a name="l00237"></a>00237 <a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1TerminatorInst.html">TerminatorInst</a> *TI = PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081">getIncomingBlock</a>(i)-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a5cb76a65b6524dba1493dd2b9dc3abbe" title="Returns the terminator instruction if the block is well formed or null if the block is not well forme...">getTerminator</a>();
<a name="l00238"></a>00238 TI-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1User.html#a1f0b9358936e3e00c42a460abbfb2868">replaceUsesOfWith</a>(OldPred, NewBB);
<a name="l00239"></a>00239 }
<a name="l00240"></a>00240
<a name="l00241"></a>00241 <span class="comment">// Okay, everything within the region is now branching to the right block, we</span>
<a name="l00242"></a>00242 <span class="comment">// just have to update the PHI nodes now, inserting PHI nodes into NewBB.</span>
<a name="l00243"></a>00243 <span class="keywordflow">for</span> (AfterPHIs = OldPred-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0ed5f3ab3c2e4196ee0cffffa080c062">begin</a>(); isa<PHINode>(AfterPHIs); ++AfterPHIs) {
<a name="l00244"></a>00244 <a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html">PHINode</a> *PN = cast<PHINode>(AfterPHIs);
<a name="l00245"></a>00245 <span class="comment">// Create a new PHI node in the new region, which has an incoming value</span>
<a name="l00246"></a>00246 <span class="comment">// from OldPred of PN.</span>
<a name="l00247"></a>00247 <a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html">PHINode</a> *NewPN = <a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#afb5e83bf5123ff7c51058eb0ebebcdc6">PHINode::Create</a>(PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1Value.html#a0cf3748dba54f931bb1241ae4adc76bc">getType</a>(), 1 + NumPredsFromRegion,
<a name="l00248"></a>00248 PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1Value.html#ad452febc1ac0b394876e640ec03ffa38">getName</a>()+<span class="stringliteral">".ce"</span>, NewBB-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0ed5f3ab3c2e4196ee0cffffa080c062">begin</a>());
<a name="l00249"></a>00249 NewPN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a089cccb6f231efee72abc76d0f9c695f">addIncoming</a>(PN, OldPred);
<a name="l00250"></a>00250
<a name="l00251"></a>00251 <span class="comment">// Loop over all of the incoming value in PN, moving them to NewPN if they</span>
<a name="l00252"></a>00252 <span class="comment">// are from the extracted region.</span>
<a name="l00253"></a>00253 <span class="keywordflow">for</span> (<span class="keywordtype">unsigned</span> i = 0; i != PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#aa45f6c0433576e3858a6209a43750ad4">getNumIncomingValues</a>(); ++i) {
<a name="l00254"></a>00254 <span class="keywordflow">if</span> (Blocks.<a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a0fd2953d62c1b1cabb87e420be5177c4" title="Count the number of elements of a given key in the SetVector.">count</a>(PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081">getIncomingBlock</a>(i))) {
<a name="l00255"></a>00255 NewPN->addIncoming(PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#aba6a4cc4ed6d6fef3664b8d65ef04820">getIncomingValue</a>(i), PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081">getIncomingBlock</a>(i));
<a name="l00256"></a>00256 PN-><a class="code" href="http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a6f01dbe965b38186b1a78378689d4105">removeIncomingValue</a>(i);
<a name="l00257"></a>00257 --i;
<a name="l00258"></a>00258 }
<a name="l00259"></a>00259 }
<a name="l00260"></a>00260 }
<a name="l00261"></a>00261 }
<a name="l00262"></a>00262 }</pre><br>
-- <br>Wei<br>