Subzero: Use the linear-scan register allocator for Om1 as well.

src/IceTargetLoweringX8632.cpp

 //===- subzero/src/IceTargetLoweringX8632.cpp - x86-32 lowering -----------===//
 //
 //                        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 TargetLoweringX8632 class, which
 // consists almost entirely of the lowering sequence for each
 // high-level instruction.  It also implements
 // TargetX8632Fast::postLower() which does the simplest possible

[jvoung (off chromium), 2014/11/14 23:26:22]

This comment about what postLower() does can be updated now.

[Jim Stichnoth, 2014/11/14 23:51:35]

Done.

 // register allocation for the "fast" target.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/MathExtras.h"
 
 #include "IceCfg.h"
 #include "IceCfgNode.h"
@@ skipping 344 matching lines @@
   Func->liveness(Liveness_Intervals);
   if (Func->hasError())
     return;
   // Validate the live range computations.  The expensive validation
   // call is deliberately only made when assertions are enabled.
   assert(Func->validateLiveness());
   // The post-codegen dump is done here, after liveness analysis and
   // associated cleanup, to make the dump cleaner and more useful.
   Func->dump("After initial x8632 codegen");
   Func->getVMetadata()->init(VMK_All);
-  regAlloc();
+  regAlloc(RAK_Global);
   if (Func->hasError())
     return;
   Func->dump("After linear scan regalloc");
 
   if (Ctx->getFlags().PhiEdgeSplit) {
     Func->advancedPhiLowering();
     Func->dump("After advanced Phi lowering");
   }
 
   // Stack frame mapping.
@@ skipping 33 matching lines @@
     return;
   Func->dump("After Phi lowering");
 
   Func->doArgLowering();
 
   Func->genCode();
   if (Func->hasError())
     return;
   Func->dump("After initial x8632 codegen");
 
+  regAlloc(RAK_InfOnly);
+  if (Func->hasError())
+    return;
+  Func->dump("After regalloc of infinite-weight variables");
+
   Func->genFrame();
   if (Func->hasError())
     return;
   Func->dump("After stack frame mapping");
 
   // Nop insertion
   if (shouldDoNopInsertion()) {
     Func->doNopInsertion();
   }
 }
@@ skipping 1367 matching lines @@
   // eliminated after lowering, we would need to ensure that the
   // pre-call and the post-call esp adjustment get eliminated as well.
   if (ParameterAreaSizeBytes) {
     _adjust_stack(ParameterAreaSizeBytes);
   }
 
   // Copy arguments that are passed on the stack to the appropriate
   // stack locations.
   for (SizeT i = 0, e = StackArgs.size(); i < e; ++i) {
     lowerStore(InstStore::create(Func, StackArgs[i], StackArgLocations[i]));
     // TODO: Consider calling postLower() here to reduce the register

[jvoung (off chromium), 2014/11/14 23:26:22]

This postLower comment may not apply anymore?

[Jim Stichnoth, 2014/11/14 23:51:35]

Done.

     // pressure associated with using too many infinite weight
     // temporaries when lowering the call sequence in -Om1 mode.
   }
 
   // Copy arguments to be passed in registers to the appropriate
   // registers.
   // TODO: Investigate the impact of lowering arguments passed in
   // registers after lowering stack arguments as opposed to the other
   // way around.  Lowering register arguments after stack arguments may
   // reduce register pressure.  On the other hand, lowering register
@@ skipping 2275 matching lines @@
     lowerExtractElement(InstExtractElement::create(Func, Op1, Src1, Index));
 
     // Perform the arithmetic as a scalar operation.
     Variable *Res = Func->makeVariable(ElementTy);
     lowerArithmetic(InstArithmetic::create(Func, Kind, Res, Op0, Op1));
 
     // Insert the result into position.
     Variable *DestT = Func->makeVariable(Ty);
     lowerInsertElement(InstInsertElement::create(Func, DestT, T, Res, Index));
     T = DestT;
     // TODO(stichnot): Use postLower() in -Om1 mode to avoid buildup of

[jvoung (off chromium), 2014/11/14 23:26:22]

similar?

[Jim Stichnoth, 2014/11/14 23:51:35]

Done.

     // infinite weight temporaries.
   }
 
   lowerAssign(InstAssign::create(Func, Dest, T));
 }
 
 // The following pattern occurs often in lowered C and C++ code:
 //
 //   %cmp     = fcmp/icmp pred <n x ty> %src0, %src1
 //   %cmp.ext = sext <n x i1> %cmp to <n x ty>
@@ skipping 67 matching lines @@
 // Lower the pre-ordered list of assignments into mov instructions.
 // Also has to do some ad-hoc register allocation as necessary.
 void TargetX8632::lowerPhiAssignments(CfgNode *Node,
                                       const AssignList &Assignments) {
   // Check that this is a properly initialized shell of a node.
   assert(Node->getOutEdges().size() == 1);
   assert(Node->getInsts().empty());
   assert(Node->getPhis().empty());
   CfgNode *Succ = Node->getOutEdges().front();
   getContext().init(Node);
   // Register set setup similar to regAlloc() and postLower().

[jvoung (off chromium), 2014/11/14 23:26:22]

similar comment about postLower 

[Jim Stichnoth, 2014/11/14 23:51:35]

Done.

   RegSetMask RegInclude = RegSet_All;
   RegSetMask RegExclude = RegSet_StackPointer;
   if (hasFramePointer())
     RegExclude |= RegSet_FramePointer;
   llvm::SmallBitVector Available = getRegisterSet(RegInclude, RegExclude);
   bool NeedsRegs = false;
   // Initialize the set of available registers to the set of what is
   // available (not live) at the beginning of the successor block,
   // minus all registers used as Dest operands in the Assignments.  To
   // do this, we start off assuming all registers are available, then
@@ skipping 291 matching lines @@
   assert(Type != IceType_i64);
   Variable *Reg = Func->makeVariable(Type);
   if (RegNum == Variable::NoRegister)
     Reg->setWeightInfinite();
   else
     Reg->setRegNum(RegNum);
   return Reg;
 }
 
 void TargetX8632::postLower() {
-  if (Ctx->getOptLevel() != Opt_m1) {
-    // Find two-address non-SSA instructions where Dest==Src0, and set
-    // the DestNonKillable flag to keep liveness analysis consistent.
-    for (auto Inst = Context.begin(), E = Context.end(); Inst != E; ++Inst) {
-      if (Inst->isDeleted())
-        continue;
-      if (Variable *Dest = Inst->getDest()) {
-        // TODO(stichnot): We may need to consider all source
-        // operands, not just the first one, if using 3-address
-        // instructions.
-        if (Inst->getSrcSize() > 0 && Inst->getSrc(0) == Dest)
-          Inst->setDestNonKillable();
-      }
-    }
+  if (Ctx->getOptLevel() == Opt_m1)
     return;
-  }
-  // TODO: Avoid recomputing WhiteList every instruction.
-  RegSetMask RegInclude = RegSet_All;
-  RegSetMask RegExclude = RegSet_StackPointer;
-  if (hasFramePointer())
-    RegExclude |= RegSet_FramePointer;
-  llvm::SmallBitVector WhiteList = getRegisterSet(RegInclude, RegExclude);
-  // Make one pass to black-list pre-colored registers.  TODO: If
-  // there was some prior register allocation pass that made register
-  // assignments, those registers need to be black-listed here as
-  // well.
-  llvm::DenseMap<const Variable *, const Inst *> LastUses;
-  // The first pass also keeps track of which instruction is the last
-  // use for each infinite-weight variable.  After the last use, the
-  // variable is released to the free list.
+  // Find two-address non-SSA instructions where Dest==Src0, and set
+  // the DestNonKillable flag to keep liveness analysis consistent.
   for (auto Inst = Context.begin(), E = Context.end(); Inst != E; ++Inst) {
     if (Inst->isDeleted())
       continue;
-    // Don't consider a FakeKill instruction, because (currently) it
-    // is only used to kill all scratch registers at a call site, and
-    // we don't want to black-list all scratch registers during the
-    // call lowering.  This could become a problem since it relies on
-    // the lowering sequence not keeping any infinite-weight variables
-    // live across a call.  TODO(stichnot): Consider replacing this
-    // whole postLower() implementation with a robust local register
-    // allocator, for example compute live ranges only for pre-colored
-    // and infinite-weight variables and run the existing linear-scan
-    // allocator.
-    assert(!llvm::isa<InstFakeKill>(Inst) || Inst->getSrcSize() == 0);
-    for (SizeT SrcNum = 0; SrcNum < Inst->getSrcSize(); ++SrcNum) {
-      Operand *Src = Inst->getSrc(SrcNum);
-      SizeT NumVars = Src->getNumVars();
-      for (SizeT J = 0; J < NumVars; ++J) {
-        const Variable *Var = Src->getVar(J);
-        // Track last uses of all variables, regardless of whether
-        // they are pre-colored or infinite-weight.
-        LastUses[Var] = Inst;
-        if (!Var->hasReg())
-          continue;
-        WhiteList[Var->getRegNum()] = false;
-      }
+    if (Variable *Dest = Inst->getDest()) {
+      // TODO(stichnot): We may need to consider all source
+      // operands, not just the first one, if using 3-address
+      // instructions.
+      if (Inst->getSrcSize() > 0 && Inst->getSrc(0) == Dest)
+        Inst->setDestNonKillable();
     }
   }
-  // The second pass colors infinite-weight variables.
-  llvm::SmallBitVector AvailableRegisters = WhiteList;
-  llvm::SmallBitVector FreedRegisters(WhiteList.size());
-  for (auto Inst = Context.begin(), E = Context.end(); Inst != E; ++Inst) {
-    FreedRegisters.reset();
-    if (Inst->isDeleted())
-      continue;
-    // Iterate over all variables referenced in the instruction,
-    // including the Dest variable (if any).  If the variable is
-    // marked as infinite-weight, find it a register.  If this
-    // instruction is the last use of the variable in the lowered
-    // sequence, release the register to the free list after this
-    // instruction is completely processed.  Note that the first pass
-    // ignores the Dest operand, under the assumption that a
-    // pre-colored Dest will appear as a source operand in some
-    // subsequent instruction in the lowered sequence.
-    Variable *Dest = Inst->getDest();
-    SizeT NumSrcs = Inst->getSrcSize();
-    if (Dest)
-      ++NumSrcs;
-    if (NumSrcs == 0)
-      continue;
-    OperandList Srcs(NumSrcs);
-    for (SizeT i = 0; i < Inst->getSrcSize(); ++i)
-      Srcs[i] = Inst->getSrc(i);
-    if (Dest)
-      Srcs[NumSrcs - 1] = Dest;
-    for (SizeT SrcNum = 0; SrcNum < NumSrcs; ++SrcNum) {
-      Operand *Src = Srcs[SrcNum];
-      SizeT NumVars = Src->getNumVars();
-      for (SizeT J = 0; J < NumVars; ++J) {
-        Variable *Var = Src->getVar(J);
-        if (!Var->hasReg() && Var->getWeight().isInf()) {
-          llvm::SmallBitVector AvailableTypedRegisters =
-              AvailableRegisters & getRegisterSetForType(Var->getType());
-          assert(AvailableTypedRegisters.any());
-          int32_t RegNum = AvailableTypedRegisters.find_first();
-          Var->setRegNum(RegNum);
-          AvailableRegisters[RegNum] = false;
-        }
-        if (Var->hasReg()) {
-          int32_t RegNum = Var->getRegNum();
-          assert(!AvailableRegisters[RegNum]);
-          if (LastUses[Var] == Inst) {
-            if (WhiteList[RegNum])
-              FreedRegisters[RegNum] = true;
-          }
-        }
-      }
-    }
-    AvailableRegisters |= FreedRegisters;
-  }
 }
 
 template <> void ConstantInteger32::emit(GlobalContext *Ctx) const {
   Ostream &Str = Ctx->getStrEmit();
   Str << "$" << (int32_t)getValue();
 }
 
 template <> void ConstantInteger64::emit(GlobalContext *) const {
   llvm_unreachable("Not expecting to emit 64-bit integers");
 }
@@ skipping 102 matching lines @@
   } else if (IsConstant || IsExternal)
     Str << "\t.zero\t" << Size << "\n";
   // Size is part of .comm.
 
   if (IsConstant || HasNonzeroInitializer || IsExternal)
     Str << "\t.size\t" << MangledName << ", " << Size << "\n";
   // Size is part of .comm.
 }
 
 } // end of namespace Ice