Subzero: Improve performance of liveness analysis and live range construction.

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
@@ skipping 435 matching lines @@
 
 Variable *TargetX8632::getPhysicalRegister(SizeT RegNum) {
   assert(RegNum < PhysicalRegisters.size());
   Variable *Reg = PhysicalRegisters[RegNum];
   if (Reg == NULL) {
     Reg = Func->makeVariable(IceType_i32);
     Reg->setRegNum(RegNum);
     PhysicalRegisters[RegNum] = Reg;
     // Specially mark esp as an "argument" so that it is considered
     // live upon function entry.
-    if (RegNum == RegX8632::Reg_esp)
+    if (RegNum == RegX8632::Reg_esp) {
       Func->addImplicitArg(Reg);
+      Reg->setIgnoreLiveness();
+    }
   }
   return Reg;
 }
 
 IceString TargetX8632::getRegName(SizeT RegNum, Type Ty) const {
   assert(RegNum < RegX8632::Reg_NUM);
   static IceString RegNames8[] = {
 #define X(val, encode, name, name16, name8, scratch, preserved, stackptr,      \
           frameptr, isI8, isInt, isFP)                                         \
   name8,
@@ skipping 783 matching lines @@
       InstX8632Label *Label = InstX8632Label::create(Func, this);
       _mov(T_1, Src1Lo, RegX8632::Reg_ecx);
       _mov(T_2, Src0Lo);
       _mov(T_3, Src0Hi);
       _shld(T_3, T_2, T_1);
       _shl(T_2, T_1);
       _test(T_1, BitTest);
       _br(CondX86::Br_e, Label);
       // Because of the intra-block control flow, we need to fake a use
       // of T_3 to prevent its earlier definition from being dead-code
       // eliminated in the presence of its later definition.

[jvoung (off chromium), 2014/10/13 20:50:50]

Now that the fakeuse is removed, can the comment be tweaked slightly?

[Jim Stichnoth, 2014/10/13 23:15:22]

Done.

-      Context.insert(InstFakeUse::create(Func, T_3));
-      _mov(T_3, T_2);
-      _mov(T_2, Zero);
+      _mov_nonkillable(T_3, T_2);
+      _mov_nonkillable(T_2, Zero);
       Context.insert(Label);
       _mov(DestLo, T_2);
       _mov(DestHi, T_3);
     } break;
     case InstArithmetic::Lshr: {
       // a=b>>c (unsigned) ==>
       //   t1:ecx = c.lo & 0xff
       //   t2 = b.lo
       //   t3 = b.hi
       //   t2 = shrd t2, t3, t1
@@ skipping 13 matching lines @@
       _mov(T_1, Src1Lo, RegX8632::Reg_ecx);
       _mov(T_2, Src0Lo);
       _mov(T_3, Src0Hi);
       _shrd(T_2, T_3, T_1);
       _shr(T_3, T_1);
       _test(T_1, BitTest);
       _br(CondX86::Br_e, Label);
       // Because of the intra-block control flow, we need to fake a use
       // of T_3 to prevent its earlier definition from being dead-code
       // eliminated in the presence of its later definition.
-      Context.insert(InstFakeUse::create(Func, T_2));
-      _mov(T_2, T_3);
-      _mov(T_3, Zero);
+      _mov_nonkillable(T_2, T_3);
+      _mov_nonkillable(T_3, Zero);
       Context.insert(Label);
       _mov(DestLo, T_2);
       _mov(DestHi, T_3);
     } break;
     case InstArithmetic::Ashr: {
       // a=b>>c (signed) ==>
       //   t1:ecx = c.lo & 0xff
       //   t2 = b.lo
       //   t3 = b.hi
       //   t2 = shrd t2, t3, t1
@@ skipping 13 matching lines @@
       _mov(T_1, Src1Lo, RegX8632::Reg_ecx);
       _mov(T_2, Src0Lo);
       _mov(T_3, Src0Hi);
       _shrd(T_2, T_3, T_1);
       _sar(T_3, T_1);
       _test(T_1, BitTest);
       _br(CondX86::Br_e, Label);
       // Because of the intra-block control flow, we need to fake a use
       // of T_3 to prevent its earlier definition from being dead-code
       // eliminated in the presence of its later definition.
-      Context.insert(InstFakeUse::create(Func, T_2));
-      _mov(T_2, T_3);
+      _mov_nonkillable(T_2, T_3);
       _sar(T_3, SignExtend);
       Context.insert(Label);
       _mov(DestLo, T_2);
       _mov(DestHi, T_3);
     } break;
     case InstArithmetic::Udiv: {
       const SizeT MaxSrcs = 2;
       InstCall *Call = makeHelperCall("__udivdi3", Dest, MaxSrcs);
       Call->addArg(Inst->getSrc(0));
       Call->addArg(Inst->getSrc(1));
@@ skipping 1162 matching lines @@
   }
   Constant *Default =
       Ctx->getConstantInt32(IceType_i32, TableFcmp[Index].Default);
   _mov(Dest, Default);
   if (HasC1) {
     InstX8632Label *Label = InstX8632Label::create(Func, this);
     _br(TableFcmp[Index].C1, Label);
     if (HasC2) {
       _br(TableFcmp[Index].C2, Label);
     }
-    Context.insert(InstFakeUse::create(Func, Dest));
     Constant *NonDefault =
         Ctx->getConstantInt32(IceType_i32, !TableFcmp[Index].Default);
-    _mov(Dest, NonDefault);
+    _mov_nonkillable(Dest, NonDefault);
     Context.insert(Label);
   }
 }
 
 void TargetX8632::lowerIcmp(const InstIcmp *Inst) {
   Operand *Src0 = legalize(Inst->getSrc(0));
   Operand *Src1 = legalize(Inst->getSrc(1));
   Variable *Dest = Inst->getDest();
 
   if (isVectorType(Dest->getType())) {
@@ skipping 135 matching lines @@
     Operand *Src0HiRM = legalize(hiOperand(Src0), Legal_Reg | Legal_Mem);
     Operand *Src1LoRI = legalize(loOperand(Src1), Legal_Reg | Legal_Imm);
     Operand *Src1HiRI = legalize(hiOperand(Src1), Legal_Reg | Legal_Imm);
     if (Condition == InstIcmp::Eq || Condition == InstIcmp::Ne) {
       InstX8632Label *Label = InstX8632Label::create(Func, this);
       _mov(Dest, (Condition == InstIcmp::Eq ? Zero : One));
       _cmp(Src0LoRM, Src1LoRI);
       _br(CondX86::Br_ne, Label);
       _cmp(Src0HiRM, Src1HiRI);
       _br(CondX86::Br_ne, Label);
-      Context.insert(InstFakeUse::create(Func, Dest));
-      _mov(Dest, (Condition == InstIcmp::Eq ? One : Zero));
+      _mov_nonkillable(Dest, (Condition == InstIcmp::Eq ? One : Zero));
       Context.insert(Label);
     } else {
       InstX8632Label *LabelFalse = InstX8632Label::create(Func, this);
       InstX8632Label *LabelTrue = InstX8632Label::create(Func, this);
       _mov(Dest, One);
       _cmp(Src0HiRM, Src1HiRI);
       _br(TableIcmp64[Index].C1, LabelTrue);
       _br(TableIcmp64[Index].C2, LabelFalse);
       _cmp(Src0LoRM, Src1LoRI);
       _br(TableIcmp64[Index].C3, LabelTrue);
       Context.insert(LabelFalse);
-      Context.insert(InstFakeUse::create(Func, Dest));
-      _mov(Dest, Zero);
+      _mov_nonkillable(Dest, Zero);
       Context.insert(LabelTrue);
     }
     return;
   }
 
   // cmp b, c
   Operand *Src0RM =
       legalize(Src0, IsSrc1ImmOrReg ? (Legal_Reg | Legal_Mem) : Legal_Reg);
   InstX8632Label *Label = InstX8632Label::create(Func, this);
   _cmp(Src0RM, Src1);
   _mov(Dest, One);
   _br(getIcmp32Mapping(Inst->getCondition()), Label);
-  Context.insert(InstFakeUse::create(Func, Dest));
-  _mov(Dest, Zero);
+  _mov_nonkillable(Dest, Zero);
   Context.insert(Label);
 }
 
 void TargetX8632::lowerInsertElement(const InstInsertElement *Inst) {
   Operand *SourceVectNotLegalized = Inst->getSrc(0);
   Operand *ElementToInsertNotLegalized = Inst->getSrc(1);
   ConstantInteger32 *ElementIndex =
       llvm::dyn_cast<ConstantInteger32>(Inst->getSrc(2));
   // Only constant indices are allowed in PNaCl IR.
   assert(ElementIndex);
@@ skipping 410 matching lines @@
     return;
   }
   case Intrinsics::Stacksave: {
     Variable *esp = Func->getTarget()->getPhysicalRegister(RegX8632::Reg_esp);
     Variable *Dest = Instr->getDest();
     _mov(Dest, esp);
     return;
   }
   case Intrinsics::Stackrestore: {
     Variable *esp = Func->getTarget()->getPhysicalRegister(RegX8632::Reg_esp);
-    _mov(esp, Instr->getArg(0));
+    _mov_nonkillable(esp, Instr->getArg(0));
     return;
   }
   case Intrinsics::Trap:
     _ud2();
     return;
   case Intrinsics::UnknownIntrinsic:
     Func->setError("Should not be lowering UnknownIntrinsic");
     return;
   }
   return;
@@ skipping 788 matching lines @@
 
   if (Dest->getType() == IceType_i64) {
     Variable *DestLo = llvm::cast<Variable>(loOperand(Dest));
     Variable *DestHi = llvm::cast<Variable>(hiOperand(Dest));
     Operand *SrcLoRI = legalize(loOperand(SrcT), Legal_Reg | Legal_Imm);
     Operand *SrcHiRI = legalize(hiOperand(SrcT), Legal_Reg | Legal_Imm);
     _cmp(ConditionRM, Zero);
     _mov(DestLo, SrcLoRI);
     _mov(DestHi, SrcHiRI);
     _br(CondX86::Br_ne, Label);
-    Context.insert(InstFakeUse::create(Func, DestLo));
-    Context.insert(InstFakeUse::create(Func, DestHi));
     Operand *SrcFLo = loOperand(SrcF);
     Operand *SrcFHi = hiOperand(SrcF);
     SrcLoRI = legalize(SrcFLo, Legal_Reg | Legal_Imm);
     SrcHiRI = legalize(SrcFHi, Legal_Reg | Legal_Imm);
-    _mov(DestLo, SrcLoRI);
-    _mov(DestHi, SrcHiRI);
+    _mov_nonkillable(DestLo, SrcLoRI);
+    _mov_nonkillable(DestHi, SrcHiRI);
   } else {
     _cmp(ConditionRM, Zero);
     SrcT = legalize(SrcT, Legal_Reg | Legal_Imm);
     _mov(Dest, SrcT);
     _br(CondX86::Br_ne, Label);
-    Context.insert(InstFakeUse::create(Func, Dest));
     SrcF = legalize(SrcF, Legal_Reg | Legal_Imm);
-    _mov(Dest, SrcF);
+    _mov_nonkillable(Dest, SrcF);
   }
 
   Context.insert(Label);
 }
 
 void TargetX8632::lowerStore(const InstStore *Inst) {
   Operand *Value = Inst->getData();
   Operand *Addr = Inst->getAddr();
   OperandX8632Mem *NewAddr = FormMemoryOperand(Addr, Value->getType());
   Type Ty = NewAddr->getType();
@@ skipping 320 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)
+  if (Ctx->getOptLevel() != Opt_m1) {
+    // Find non-SSA instructions where Dest==Src0, and set the

[jvoung (off chromium), 2014/10/13 20:50:50]

Add a note to clarify that this is for two-address instruction patterns?

[Jim Stichnoth, 2014/10/13 23:15:22]

Done.

+    // DestNonKillable flag to keep liveness analysis consistent.
+    for (Inst *Inst : Context) {
+      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();
+      }
+    }
     return;
-  TimerMarker T(TimerStack::TT_postLower, Func);

[jvoung (off chromium), 2014/10/13 20:50:50]

Is this removal intentional? Otherwise, you could remove TT_postLower from the
enum.

[Jim Stichnoth, 2014/10/13 23:15:22]

Removed the enum value.

I removed the TimerMarker because timing every instruction adds a lot of timing
overhead.  I'm hesitant to even keep per-block timers, but I did leave one, and
it appears to cost about 3% of total execution time.

+  }
   // 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.
@@ skipping 223 matching lines @@
         llvm::report_fatal_error(StrBuf.str());
         break;
       }
       }
     }
     Str << "\t.size\t" << MangledName << ", " << Global.getNumBytes() << "\n";
   }
 }
 
 } // end of namespace Ice