Subzero: Initial O2 lowering

src/IceCfg.cpp

 //===- subzero/src/IceCfg.cpp - Control flow graph implementation ---------===//
 //
 //                        The Subzero Code Generator
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Cfg class, including constant pool
 // management.
 //
 //===----------------------------------------------------------------------===//
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
 #include "IceDefs.h"
 #include "IceInst.h"
+#include "IceLiveness.h"
 #include "IceOperand.h"
 #include "IceTargetLowering.h"
 
 namespace Ice {
 
 Cfg::Cfg(GlobalContext *Ctx)
     : Ctx(Ctx), FunctionName(""), ReturnType(IceType_void),
       IsInternalLinkage(false), HasError(false), ErrorMessage(""), Entry(NULL),
-      NextInstNumber(1),
+      NextInstNumber(1), Live(NULL),
       Target(TargetLowering::createLowering(Ctx->getTargetArch(), this)),
       CurrentNode(NULL) {}
 
 Cfg::~Cfg() {}
 
 void Cfg::setError(const IceString &Message) {
   HasError = true;
   ErrorMessage = Message;
   Ctx->getStrDump() << "ICE translation error: " << ErrorMessage << "\n";
 }
@@ skipping 44 matching lines @@
     dump();
   }
 }
 
 void Cfg::computePredecessors() {
   for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
     (*I)->computePredecessors();
   }
 }
 
+void Cfg::renumberInstructions() {
+  NextInstNumber = 1;
+  for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
+    (*I)->renumberInstructions();
+  }
+}
+
 // placePhiLoads() must be called before placePhiStores().
 void Cfg::placePhiLoads() {
   for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
     (*I)->placePhiLoads();
   }
 }
 
 // placePhiStores() must be called after placePhiLoads().
 void Cfg::placePhiStores() {
   for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
     (*I)->placePhiStores();
   }
 }
 
 void Cfg::deletePhis() {
   for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
     (*I)->deletePhis();
   }
 }
 
+void Cfg::doAddressOpt() {
+  for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
+    (*I)->doAddressOpt();
+  }
+}
+
 void Cfg::genCode() {
   for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
     (*I)->genCode();
   }
 }
 
 // Compute the stack frame layout.
 void Cfg::genFrame() {
   getTarget()->addProlog(Entry);
   // TODO: Consider folding epilog generation into the final
   // emission/assembly pass to avoid an extra iteration over the node
   // list.  Or keep a separate list of exit nodes.
   for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
     CfgNode *Node = *I;
     if (Node->getHasReturn())
       getTarget()->addEpilog(Node);
   }
 }
 
+void Cfg::liveness(LivenessMode Mode) {
+  if (Mode == Liveness_LREndLightweight) {
+    // Lightweight liveness is a quick single pass and doesn't need to
+    // iterate until convergence.
+    for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
+      (*I)->liveness(Mode, getLiveness());

[JF, 2014/05/25 22:50:50]

Can't getLiveness() return a nullptr here?

[Jim Stichnoth, 2014/05/29 01:39:46]

Yes, but as it turns out, the "lightweight" mode doesn't actually use the
Liveness object, so everything should be OK, right?

Clearly, after having another look at this, it's just icky, so I've broken it
into livenessLightweight() and liveness().  The normal (non-lightweight) version
now has two modes instead of three: the Basic mode that computes live-in,
live-out, and end of live ranges; and the Intervals mode that additional
calculates the live intervals for each variable.

+    }
+    return;
+  }
+
+  Live.reset(new Liveness(this, Mode));
+  Live->init();
+  llvm::BitVector NeedToProcess(Nodes.size());
+  // Mark all nodes as needing to be processed.
+  for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
+    NeedToProcess[(*I)->getIndex()] = true;
+  }

[JF, 2014/05/25 22:50:50]

Can you set the entire bit vector to true? If all nodes have unique indices, and
they're all in the [0, Nodes.size()[ range.

[Jim Stichnoth, 2014/05/29 01:39:46]

Done (via the constructor).  That loop-based initialization was left over from
when the Node indexes weren't necessarily packed.

+  while (NeedToProcess.any()) {
+    // Iterate in reverse topological order to speed up convergence.
+    for (NodeList::reverse_iterator I = Nodes.rbegin(), E = Nodes.rend();
+         I != E; ++I) {
+      CfgNode *Node = *I;
+      if (NeedToProcess[Node->getIndex()]) {
+        NeedToProcess[Node->getIndex()] = false;
+        bool Changed = Node->liveness(Mode, getLiveness());
+        if (Changed) {
+          // If the beginning-of-block liveness changed since the last
+          // iteration, mark all in-edges as needing to be processed.
+          const NodeList &InEdges = Node->getInEdges();
+          for (NodeList::const_iterator I1 = InEdges.begin(),
+                                        E1 = InEdges.end();
+               I1 != E1; ++I1) {
+            CfgNode *Pred = *I1;
+            NeedToProcess[Pred->getIndex()] = true;
+          }
+        }
+      }
+    }
+  }
+  if (Mode == Liveness_RangesFull) {
+    // Reset each variable's live range.
+    for (VarList::const_iterator I = Variables.begin(), E = Variables.end();
+         I != E; ++I) {
+      if (Variable *Var = *I)
+        Var->resetLiveRange();
+    }
+  }
+  Timer T_liveRange;

[JF, 2014/05/25 22:50:50]

Why just time this part?

[Jim Stichnoth, 2014/05/29 01:39:46]

Added a comment to explain.  Basically, I want a breakdown of the live interval
construction in addition to the total time for liveness analysis.  The caller of
Cfg::liveness() is already timing the whole thing.

+  // Make a final pass over instructions to delete dead instructions
+  // and build each Variable's live range.
+  for (NodeList::iterator I = Nodes.begin(), E = Nodes.end(); I != E; ++I) {
+    (*I)->livenessPostprocess(Mode, getLiveness());
+  }
+  if (Mode == Liveness_RangesFull) {
+    // Special treatment for live in-args.  Their liveness needs to
+    // extend beyond the beginning of the function, otherwise an arg
+    // whose only use is in the first instruction will end up having
+    // the trivial live range [1,1) and will *not* interfere with
+    // other arguments.  So if the first instruction of the method is
+    // "r=arg1+arg2", both args may be assigned the same register.
+    for (SizeT I = 0; I < Args.size(); ++I) {
+      Variable *Arg = Args[I];
+      if (!Live->getLiveRange(Arg).isEmpty()) {
+        // Add live range [-1,0) with weight 0.
+        Live->addLiveRange(Arg, -1, 0, 0);
+      }
+      Variable *Lo = Arg->getLo();
+      if (Lo && !Live->getLiveRange(Lo).isEmpty())
+        Live->addLiveRange(Lo, -1, 0, 0);
+      Variable *Hi = Arg->getHi();
+      if (Hi && !Live->getLiveRange(Hi).isEmpty())
+        Live->addLiveRange(Hi, -1, 0, 0);

[JF, 2014/05/25 22:50:50]

What's this lo/hi thing?

[Jim Stichnoth, 2014/05/29 01:39:46]

Added a comment explaining.  BTW, there's a TODO in IceOperand.h about redoing
the Lo/Hi thing since it's really target-specific.

+    }
+    // Copy Liveness::LiveRanges into individual variables.  TODO:
+    // Remove Variable::LiveRange and redirect to
+    // Liveness::LiveRanges.  TODO: make sure Variable weights
+    // are applied properly.
+    SizeT NumVars = Variables.size();
+    for (SizeT i = 0; i < NumVars; ++i) {
+      Variable *Var = Variables[i];
+      Var->setLiveRange(Live->getLiveRange(Var));
+      if (Var->getWeight().isInf())
+        Var->setLiveRangeInfiniteWeight();
+      setCurrentNode(NULL);
+    }
+    T_liveRange.printElapsedUs(getContext(), "live range construction");
+    dump();

[jvoung (off chromium), 2014/05/28 17:48:15]

If ctx->isVerbose, then dump() to avoid iterating through?

Is CFG->dump() the "highest level" dump?  Maybe just check isVerbose() early in
there and exit early if false, instead of checking isVerbose() in a bunch of
places? Maybe it doesn't work because there's different granularities of
verbosity.

At some point, might also want to #if !NDEBUG the dump() methods if we don't
need it in release mode.

[Jim Stichnoth, 2014/05/29 01:39:46]

Good idea.  dump() now takes an optional intro message argument and all the
isVerbose() checking is simpler.

+    // TODO: validateLiveness() is a heavyweight operation inside an
+    // assert().  In a Release build with asserts enabled, we may want
+    // to disable this call.
+    assert(validateLiveness());

[JF, 2014/05/25 22:50:50]

Could you validate passes after the pass instead? Have validation be an option
(and each pass is declared to have a list of validations that would run after
they run), instead of doing it when asserts are on.

[Jim Stichnoth, 2014/05/29 01:39:46]

Removed the liveness validation from liveness(), and added it after the
liveness() call, and outside the timing measurement.  Added a TODO to put it
under a flag.

+  }
+}
+
+// Traverse every Variable of every Inst and verify that it
+// appears within the Variable's computed live range.
+bool Cfg::validateLiveness() const {
+  bool Valid = true;
+  for (NodeList::const_iterator I1 = Nodes.begin(), E1 = Nodes.end(); I1 != E1;
+       ++I1) {
+    CfgNode *Node = *I1;
+    InstList &Insts = Node->getInsts();
+    for (InstList::const_iterator I2 = Insts.begin(), E2 = Insts.end();
+         I2 != E2; ++I2) {
+      Inst *Inst = *I2;
+      if (Inst->isDeleted())
+        continue;
+      if (llvm::isa<InstFakeKill>(Inst))
+        continue;
+      int32_t InstNumber = Inst->getNumber();
+      Variable *Dest = Inst->getDest();
+      if (Dest) {
+        // TODO: This instruction should actually begin Dest's live
+        // range, so we could probably test that this instruction is
+        // the beginning of some segment of Dest's live range.  But
+        // this wouldn't work with non-SSA temporaries during
+        // lowering.
+        if (!Dest->getLiveRange().containsValue(InstNumber)) {
+          Valid = false;
+          assert(Valid);

[JF, 2014/05/25 22:50:50]

i'm confused by this. Do you want to print the invalid instructions instead?

[Jim Stichnoth, 2014/05/29 01:39:46]

Done.

+        }
+      }
+      SizeT VarIndex = 0;

[jvoung (off chromium), 2014/05/28 17:48:15]

VarIndex unused (just incremented)?

[Jim Stichnoth, 2014/05/29 01:39:46]

This iterator pattern is copied in several places.  I removed the use of
VarIndex everywhere except the two instances where it is actually needed.

+      for (SizeT I = 0; I < Inst->getSrcSize(); ++I) {
+        Operand *Src = Inst->getSrc(I);
+        SizeT NumVars = Src->getNumVars();
+        for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
+          const Variable *Var = Src->getVar(J);
+          if (!Var->getLiveRange().containsValue(InstNumber)) {
+            Valid = false;
+            assert(Valid);

[JF, 2014/05/25 22:50:50]

Ditto.

[Jim Stichnoth, 2014/05/29 01:39:46]

Done.

+          }
+        }
+      }
+    }
+  }
+  return Valid;
+}
+
 // ======================== Dump routines ======================== //
 
 void Cfg::emit() {
   Ostream &Str = Ctx->getStrEmit();
   Timer T_emit;
   if (!Ctx->testAndSetHasEmittedFirstMethod()) {
     // Print a helpful command for assembling the output.
     // TODO: have the Target emit the header
     // TODO: need a per-file emit in addition to per-CFG
     Str << "# $LLVM_BIN_PATH/llvm-mc"
@@ skipping 28 matching lines @@
     Str << ReturnType << " @" << getFunctionName() << "(";
     for (SizeT i = 0; i < Args.size(); ++i) {
       if (i > 0)
         Str << ", ";
       Str << Args[i]->getType() << " ";
       Args[i]->dump(this);
     }
     Str << ") {\n";
   }
   setCurrentNode(NULL);
+  if (getContext()->isVerbose(IceV_Liveness)) {
+    // Print summary info about variables
+    for (VarList::const_iterator I = Variables.begin(), E = Variables.end();
+         I != E; ++I) {
+      Variable *Var = *I;
+      Str << "//"
+          << " multiblock=" << Var->isMultiblockLife() << " "
+          << " weight=" << Var->getWeight() << " ";
+      Var->dump(this);
+      Str << " LIVE=" << Var->getLiveRange() << "\n";
+    }
+  }
   // Print each basic block
   for (NodeList::const_iterator I = Nodes.begin(), E = Nodes.end(); I != E;
        ++I) {
     (*I)->dump(this);
   }
   if (getContext()->isVerbose(IceV_Instructions)) {
     Str << "}\n";
   }
 }
 
 } // end of namespace Ice