[LLVMdev] Shrink Wrapping - RFC and initial implementation

[Evan Cheng]

Hi John,

It looks pretty good. Thanks for working on this. Some comments:

1. Some of the functions that you introduced, e.g. stringifyCSRegSet  
probably ought to be "static" and ifdef'ed out when NDEBUG is defined.

2. +      // DEBUG
+      if (! MBB->empty() && ! CSRUsed[MBB].intersects(restore)) {
+        MachineInstr* MI = BeforeI;
+        DOUT << "adding restore after ";
+        DEBUG(MI->dump());
+      } else {
+        DOUT << "adding restore to beginning of "
+             << getBasicBlockName(MBB) << "\n";
+      }
+      // DEBUG

Code like this should also be inside ifndef NDEBUG.

3. It can still use more refactoring. :-)

4.  clearSets().
It's not clear what sets it's clearing. Perhaps name it something like  
clearShrinkWrapData()?

5
+void PEI::placeSpillsAndRestores(MachineFunction &Fn) {
+
+  DOUT << "Computing SAVE, RESTORE sets\n";
+
+  // If not shrink wrapping, all spills go into entry block,
+  // all restores in return blocks.
+  if (! ShrinkWrapping) {
+    // Do spills in the entry block.

The shrink wrap version probably should go to its own function.  
Otherwise, it should exit early when the non-shrink wrapping version  
is done. That reduces nesting and please those of us who are a bit  
picky.

6.
+      // Save entry block, return blocks.
+      if (MBB->pred_size() == 0)
+        entryBlock = MBB;

Entry block is the Fn.front().

7.
+        if (!MBB->empty() && MBB->back().getDesc().isReturn())
+          returnBlocks.push_back(MBB);

PEI::insertPrologEpilogCode also traverse MBBs and get at return  
blocks. So these probably ought to be shared, i.e. returnBlocks should  
be an ivar and determined early in PEI.

8.
+    for (MachineBasicBlock::iterator I = MBB->begin(); I != MBB->end 
(); ++I) {
+      for (unsigned i = 0, e = CSI.size(); i != e; ++i) {
+        unsigned Reg = CSI[i].getReg();
+        // If instruction I reads or modifies Reg, add it to  
UsedCSRegs,
+        // CSRUsed map for the current block.
+        if (I->readsRegister(Reg, TRI) || I->modifiesRegister(Reg,  
TRI)) {

readsRegister and modifiesRegister both scan the operands. It's  
probably better to manually walk through the operands.

9.
+  // If all uses of CSRegs are in the entry block, there is nothing
+  // to shrink wrap: spills go in entry block, restores go in exiting
+  // blocks, turn off shrink wrapping.
+  if (allCSRUsesInEntryBlock) {
+    ShrinkWrapping = false;
+    DOUT << "All uses of CSRegs are in entry block, nothing to do.\n";
+  }
+  // If we have decided not to shrink wrap, just return now.
+  if (! ShrinkWrapping)
+    return true;

Why not just return inside if (allCSRUsesInEntryBlock)?

10.
+bool PEI::calculateUsedAnticAvail(MachineFunction &Fn) {
...
+  // Calculate AnticIn, AnticOut using post-order traversal of MCFG.
+  for (po_iterator<MachineBasicBlock*>
+         MBBI = po_begin(Fn.getBlockNumbered(0)),
+         MBBE = po_end(Fn.getBlockNumbered(0)); MBBI != MBBE; ++MBBI) {
+    MachineBasicBlock* MBB = *MBBI;
...
+  // Calculate Avail{In,Out} via top-down walk of Machine dominator  
tree.
+  for (df_iterator<MachineDomTreeNode*> DI = df_begin(DT.getRootNode 
()),
+         E = df_end(DT.getRootNode()); DI != E; ++DI) {


Later in
+/// placeSpillsAndRestores - decide which MBBs need spills, restores
+/// of CSRs.
+///
+void PEI::placeSpillsAndRestores(MachineFunction &Fn) {
...
+    // Calculate CSRRestore using post-order traversal of Machine-CFG.
+    for (po_iterator<MachineBasicBlock*>
+           MBBI = po_begin(Fn.getBlockNumbered(0)),
+           MBBE = po_end(Fn.getBlockNumbered(0)); MBBI != MBBE; + 
+MBBI) {

This seem to be doing traversal at least one too many times? Can this  
be improved?

11. Can you explain a bit more about AnticIn, AvailIn, etc.?

12.
Let's worry about edge splitting for a later time. :-)

13. After the code is cleaned up, we should consider checking it in  
and try it out as llcbeta. Do you have any idea of its compile time  
impact?

Thanks,

Evan

On Mar 4, 2009, at 7:57 PM, John Mosby wrote:

> Here is an updated patch for shrink wrapping with:
>
> - spills/restores done with stack slot stores/loads
> - stack adjustment removed
> - refactoring (but still in need of more)
> - spill/restore insertion code unified with spill/restore placement  
> code
>
> Documentation available here illustrates shrink wrapping with loops  
> and discusses a situation in which the pass would be more effective  
> by splitting edges in the Machine CFG (similar to breaking crit.  
> edges in the CFG).
>
> Test cases are attached.
>
> Thanks,
> John
>
> <shrink-wrapping.P2.patch><test- 
> sw.tar.gz>_______________________________________________
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20090312/f5ac8c05/attachment.html>