Wei Dang
2013-Mar-02 23:22 UTC
[LLVMdev] Question about method CodeExtractor::severSplitPHINodes
Hi folks,
Hope this is not a silly question. But it bothers me when I am thinking
about it.
My question is:
1. In the implementation of serverSplitPHINodes(), why it only checks the
first PHI node for possible
multiple inputs from outside the region to extract. There could be more
than one PHI nodes in the header
block, and the code only checks the first one. I don't quite get it.
What if the first PHI node contains only
incoming values from inside the region, while subsequent PHI nodes have
inputs from outside? Is that possible?
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
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
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
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
doesn't even have anything from outside. This looks redundant to me.
I could only guess it has something to do with the way PHI nodes get
inserted in LLVM. Any help is much appreciated!!!
/// severSplitPHINodes - If a PHI node has multiple inputs from
outside of the00185 /// region, we need to split the entry block of
the region so that the PHI node00186 /// is easier to deal with.00187
void CodeExtractor::severSplitPHINodes(BasicBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html>
*&Header) {00188 unsigned NumPredsFromRegion = 0;00189 unsigned
NumPredsOutsideRegion = 0;00190 00191 if (Header !&Header->getParent
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#aca229503e4f5c83a187a6a921c625fa8>()->getEntryBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1Function.html#a30f2c362631e3728d2f47a8203071ade>())
{00192 PHINode
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html> *PN dyn_cast
<http://llvm.org/docs/doxygen/html/namespacellvm.html#ad6dbabbbb9495cf1501d64a5c71729ed><PHINode
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html>>(Header->begin
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0ed5f3ab3c2e4196ee0cffffa080c062>());00193
if (!PN) return; // No PHI nodes.00194 00195 // If the header
node contains any PHI nodes, check to see if there is more00196 //
than one entry from outside the region. If so, we need to sever
the00197 // header block into two.00198 for (unsigned i = 0, e
= PN->getNumIncomingValues
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#aa45f6c0433576e3858a6209a43750ad4>();
i != e; ++i)00199 if (Blocks.count
<http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a0fd2953d62c1b1cabb87e420be5177c4>(PN->getIncomingBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081>(i)))00200
++NumPredsFromRegion;00201 else00202
++NumPredsOutsideRegion;00203 00204 // If there is one (or fewer)
predecessor from outside the region, we don't00205 // need to do
anything special.00206 if (NumPredsOutsideRegion <= 1)
return;00207 }00208 00209 // Otherwise, we need to split the
header block into two pieces: one00210 // containing PHI nodes
merging values from outside of the region, and a00211 // second that
contains all of the code for the block and merges back any00212 //
incoming values from inside of the region.00213 BasicBlock::iterator
<http://llvm.org/docs/doxygen/html/classllvm_1_1ilist__iterator.html>
AfterPHIs = Header->getFirstNonPHI
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0e73f4e09745bb69fdd7b15232c45428>();00214
BasicBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html>
*NewBB = Header->splitBasicBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a19445f836d9e1ecb32cba27ec4338fff>(AfterPHIs,00215
Header->getName
<http://llvm.org/docs/doxygen/html/classllvm_1_1Value.html#ad452febc1ac0b394876e640ec03ffa38>()+".ce");00216
00217 // We only want to code extract the second block now, and it
becomes the new00218 // header of the region.00219 BasicBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html>
*OldPred = Header;00220 Blocks.remove
<http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a6357ff5654c7cbe5fed8516dc8328eb4>(OldPred);00221
Blocks.insert
<http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a72d928b7fc2c5f2d56c6ac0265fd9c6e>(NewBB);00222
Header = NewBB;00223 00224 // Okay, update dominator sets. The
blocks that dominate the new one are the00225 // blocks that
dominate TIBB plus the new block itself.00226 if (DT)00227
DT->splitBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1DominatorTree.html#a3d5044cf4966abb56510f1883d275745>(NewBB);00228
00229 // Okay, now we need to adjust the PHI nodes and any branches
from within the00230 // region to go to the new header block instead
of the old header block.00231 if (NumPredsFromRegion) {00232
PHINode <http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html>
*PN = cast<PHINode>(OldPred->begin
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0ed5f3ab3c2e4196ee0cffffa080c062>());00233
// Loop over all of the predecessors of OldPred that are in the
region,00234 // changing them to branch to NewBB instead.00235
for (unsigned i = 0, e = PN->getNumIncomingValues
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#aa45f6c0433576e3858a6209a43750ad4>();
i != e; ++i)00236 if (Blocks.count
<http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a0fd2953d62c1b1cabb87e420be5177c4>(PN->getIncomingBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081>(i)))
{00237 TerminatorInst
<http://llvm.org/docs/doxygen/html/classllvm_1_1TerminatorInst.html>
*TI = PN->getIncomingBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081>(i)->getTerminator
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a5cb76a65b6524dba1493dd2b9dc3abbe>();00238
TI->replaceUsesOfWith
<http://llvm.org/docs/doxygen/html/classllvm_1_1User.html#a1f0b9358936e3e00c42a460abbfb2868>(OldPred,
NewBB);00239 }00240 00241 // Okay, everything within the
region is now branching to the right block, we00242 // just have
to update the PHI nodes now, inserting PHI nodes into NewBB.00243
for (AfterPHIs = OldPred->begin
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0ed5f3ab3c2e4196ee0cffffa080c062>();
isa<PHINode>(AfterPHIs); ++AfterPHIs) {00244 PHINode
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html> *PN
cast<PHINode>(AfterPHIs);00245 // Create a new PHI node in the
new region, which has an incoming value00246 // from OldPred of
PN.00247 PHINode
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html> *NewPN
PHINode::Create
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#afb5e83bf5123ff7c51058eb0ebebcdc6>(PN->getType
<http://llvm.org/docs/doxygen/html/classllvm_1_1Value.html#a0cf3748dba54f931bb1241ae4adc76bc>(),
1 + NumPredsFromRegion,00248
PN->getName
<http://llvm.org/docs/doxygen/html/classllvm_1_1Value.html#ad452febc1ac0b394876e640ec03ffa38>()+".ce",
NewBB->begin
<http://llvm.org/docs/doxygen/html/classllvm_1_1BasicBlock.html#a0ed5f3ab3c2e4196ee0cffffa080c062>());00249
NewPN->addIncoming
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a089cccb6f231efee72abc76d0f9c695f>(PN,
OldPred);00250 00251 // Loop over all of the incoming value in
PN, moving them to NewPN if they00252 // are from the extracted
region.00253 for (unsigned i = 0; i != PN->getNumIncomingValues
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#aa45f6c0433576e3858a6209a43750ad4>();
++i) {00254 if (Blocks.count
<http://llvm.org/docs/doxygen/html/classllvm_1_1SetVector.html#a0fd2953d62c1b1cabb87e420be5177c4>(PN->getIncomingBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081>(i)))
{00255 NewPN->addIncoming(PN->getIncomingValue
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#aba6a4cc4ed6d6fef3664b8d65ef04820>(i),
PN->getIncomingBlock
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a4c25b6c00c4867281779c81ab64d2081>(i));00256
PN->removeIncomingValue
<http://llvm.org/docs/doxygen/html/classllvm_1_1PHINode.html#a6f01dbe965b38186b1a78378689d4105>(i);00257
--i;00258 }00259 }00260 }00261 }00262 }
--
Wei
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20130302/8ea10098/attachment.html>
Caldarale, Charles R
2013-Mar-03 01:39 UTC
[LLVMdev] Question about method CodeExtractor::severSplitPHINodes
> From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] > On Behalf Of Wei Dang > Subject: [LLVMdev] Question about method CodeExtractor::severSplitPHINodes> In the implementation of serverSplitPHINodes(), why it only checks the > first PHI node for possible multiple inputs from outside the region to > extract. There could be more than one PHI nodes in the header block, > and the code only checks the first one. I don't quite get it. What if > the first PHI node contains only incoming values from inside the region, > while subsequent PHI nodes have inputs from outside? Is that possible?No, it's not possible. All PHI nodes must include inputs for _all_ predecessors of the block, so only one PHI node needs to checked for the origins. - Chuck THIS COMMUNICATION MAY CONTAIN CONFIDENTIAL AND/OR OTHERWISE PROPRIETARY MATERIAL and is thus for use only by the intended recipient. If you received this in error, please contact the sender and delete the e-mail and its attachments from all computers.
Wei Dang
2013-Mar-03 02:35 UTC
[LLVMdev] Question about method CodeExtractor::severSplitPHINodes
Thanks for reply Chuck. Please excuse me if I'm not supposed to reply to all. Are you saying all PHI nodes are required to include all its predecessor blocks no matter they have input or not? What about successor blocks? Are they optional if they don't provide inputs? BTW, where should I look at to verify this, the mem2reg.cpp & PromoteMemToReg.cpp? Thanks a lot. On Sat, Mar 2, 2013 at 6:39 PM, Caldarale, Charles R < Chuck.Caldarale at unisys.com> wrote:> > From: llvmdev-bounces at cs.uiuc.edu [mailto:llvmdev-bounces at cs.uiuc.edu] > > On Behalf Of Wei Dang > > Subject: [LLVMdev] Question about method > CodeExtractor::severSplitPHINodes > > > In the implementation of serverSplitPHINodes(), why it only checks the > > first PHI node for possible multiple inputs from outside the region to > > extract. There could be more than one PHI nodes in the header block, > > and the code only checks the first one. I don't quite get it. What if > > the first PHI node contains only incoming values from inside the region, > > while subsequent PHI nodes have inputs from outside? Is that possible? > > No, it's not possible. All PHI nodes must include inputs for _all_ > predecessors of the block, so only one PHI node needs to checked for the > origins. > > - Chuck > > > THIS COMMUNICATION MAY CONTAIN CONFIDENTIAL AND/OR OTHERWISE PROPRIETARY > MATERIAL and is thus for use only by the intended recipient. If you > received this in error, please contact the sender and delete the e-mail and > its attachments from all computers. > >-- Wei Dang -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130302/78fcdf5f/attachment.html>