<html><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">
Sorry I have completely dropped the ball on this. Some comments:<div><br class="webkit-block-placeholder"></div><div>1. Please try using SmallVector instead of std::vector. It may be offer some compile time benefit unless the vector grows too large.</div><div>2. Please try to make coding style of existing code. For example, need a space between for and '(', also if and '('. Also please set indentation level to 2.</div><div>3. Please don't include iostream. Use llvm/Support/Streams.h and DOUT instead.</div><div>4. Please don't include Dominators.h if it's not used. Also MRegisterInfo.h</div><div>5. mf.getBasicBlockList().insert(mf.end(), crit_mbb);</div><div> Just a nit pick, please use push_back(crit_mbb).</div><div>6. This chunk of code:</div><div><font class="Apple-style-span" face="Monaco" size="2"><span class="Apple-style-span" style="font-size: 10px;"><br class="webkit-block-placeholder"></span></font></div><div><font class="Apple-style-span" face="Monaco" size="2"><span class="Apple-style-span" style="font-size: 10px;"><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(0, 116, 0); "><span style="color: #000000"> </span>/// modify every branch in src that points to dst to point to the new</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(0, 116, 0); "><span style="color: #000000"> </span>/// machine basic block instead:</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> MachineBasicBlock::iterator mii = src.end();</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> <span style="color: #aa0d91">bool</span> found_branch = <span style="color: #aa0d91">false</span>;</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> <span style="color: #aa0d91">bool</span> isJumpTable = <span style="color: #aa0d91">false</span>;</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> <span style="color: #aa0d91">while</span> (mii != src.begin()) {</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> mii--;</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(0, 116, 0); "><span style="color: #000000"> </span>// if there are no more branches, finish the loop</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> <span style="color: #aa0d91">if</span> (!tii->isTerminatorInstr(mii->getOpcode())) {</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> <span style="color: #aa0d91">break</span>;</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> } <span style="color: #aa0d91">else</span> <span style="color: #aa0d91">if</span> (tii->isIndirectJump(mii->getOpcode())) {</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> isJumpTable = <span style="color: #aa0d91">true</span>;</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> <span style="color: #aa0d91">continue</span>;</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> }</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(0, 116, 0); "><span style="color: #000000"> </span>// Scan the operands of this branch, replacing any uses of dst with</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(0, 116, 0); "><span style="color: #000000"> </span>// crit_mbb.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> <span style="color: #aa0d91">for</span> (<span style="color: #aa0d91">unsigned</span> i = <span style="color: #1c00cf">0</span>, e = mii->getNumOperands(); i != e; ++i) {</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> MachineOperand & mo = mii->getOperand(i);</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> <span style="color: #aa0d91">if</span> (mo.isMachineBasicBlock() &&</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> mo.getMachineBasicBlock() == & dst) {</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> found_branch = <span style="color: #aa0d91">true</span>;</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> mo.setMachineBasicBlock(crit_mbb);</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> }</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> }</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "> }</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><br class="webkit-block-placeholder"></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;">This is almost identical to ReplaceUsesOfBlockWith(). It's probably better to update ReplaceUsesOfBlockWith() to include the jumptable updating code and use that instead. Also note it also updates successor list.</span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; ">7. </div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(0, 116, 0); "><span style="color: #000000"> </span>// TODO: This is tentative. It may be necessary to fix this code. Maybe</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(0, 116, 0); "><span style="color: #000000"> </span>// I am inserting too many gotos, but I am trusting that the asm printer</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(0, 116, 0); "><span style="color: #000000"> </span>// will optimize the unnecessary gotos.</div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><font class="Apple-style-span" color="#000000">Asm printer won't optimize them away but branch folding pass might. :-)</font></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; color: rgb(0, 116, 0); "><br></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><font class="Apple-style-span" color="#000000">8. I am not sure if any existing pass will benefit from this. But it may be handy. But does it need to be a pass? Can it be a member function of MachineFunction?</font></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><font class="Apple-style-span" color="#000000"><br class="webkit-block-placeholder"></font></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><font class="Apple-style-span" color="#000000">Thanks,</font></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><font class="Apple-style-span" color="#000000"><br class="webkit-block-placeholder"></font></span></font></div><div style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 0px; font: normal normal normal 10px/normal Monaco; "><font class="Apple-style-span" face="Helvetica" size="3"><span class="Apple-style-span" style="font-size: 12px;"><font class="Apple-style-span" color="#000000">Evan</font></span></font></div>
</div>
</span></font></div><div>
<div><br><div><div>On Aug 18, 2007, at 7:51 PM, Fernando Magno Quintao Pereira wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><br>Hi,<br><br>This pass is similar to the one in BreakCriticalEdges.cpp, but it works for MachineFunction's, instead of Functions. The existence of critical edges complicates many optimizations. When doing register allocation, you don't necessarily have to remove critical edges (you can use conventional SSA-form, for instance. See "Translating Out of Static Single Assignment Form. SAS 1999"), yet, to remove them should be easy.<br><br>I can send a patch if you think the code is ok. I am sending you the code.<br><br>best,<br><br>Fernando<br><br><blockquote type="cite">Can you explain briefly what it does? What benefits do you expect?<br></blockquote><br><blockquote type="cite"><blockquote type="cite">At least I think I've solved it. I had to add one method to<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">TargetInstrInfo to tell me when an instruction is an indirect jump -<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">TargetInstrInfo::tii.isIndirectJump(opcode). When that is the case, I<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">update the jump table using:<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"><br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"> // Change jumps to go to the new basic block:<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"> if(isJumpTable) {<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"> mf.getJumpTableInfo()->ReplaceMBBInJumpTables(& dst,<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">crit_mbb);<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"> }<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite"><br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">where dst was the old basic block, and crit_mbb is the new one,<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">created to<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">remove a critical edge. I think this should solve the problem. If you<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">want, I can give you the pass to break critical edges of machine<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">blocks,<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">so that you guys can see if it is worth adding to LLVM's main<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">branch. Up<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">to now, as far as I know, there is no pass to remove critical edges of<br></blockquote></blockquote><blockquote type="cite"><blockquote type="cite">machine functions in LLVM.</blockquote></blockquote><span><CriticalEdgeRemoval_Fer.cpp></span>_______________________________________________<br>LLVM Developers mailing list<br>LLVMdev@cs.uiuc.edu <a href="http://llvm.cs.uiuc.edu">http://llvm.cs.uiuc.edu</a><br><a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br></blockquote></div><br></div></div></body></html>