Subzero: Provide a macro for iterating over instruction variables.
This makes it easier and less error-prone to implement the relatively common
pattern of looking at all the Variable operands contained within an instruction.
BUG= none
R=stichnot@chromium.org
Review URL: https://codereview.chromium.org/1323693002.
diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index 5797fdc..416376b 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -22,6 +22,7 @@
#include "IceELFObjectWriter.h"
#include "IceGlobalInits.h"
#include "IceInst.h"
+#include "IceInstVarIter.h"
#include "IceLiveness.h"
#include "IceOperand.h"
#include "IceTargetLowering.h"
@@ -585,19 +586,14 @@
}
}
}
- for (SizeT I = 0; I < Inst.getSrcSize(); ++I) {
- Operand *Src = Inst.getSrc(I);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J) {
- const Variable *Var = Src->getVar(J);
- const bool IsDest = false;
- if (!Var->getIgnoreLiveness() &&
- !Var->getLiveRange().containsValue(InstNumber, IsDest)) {
- Valid = false;
- Str << "Liveness error: inst " << Inst.getNumber() << " var ";
- Var->dump(this);
- Str << " live range " << Var->getLiveRange() << "\n";
- }
+ FOREACH_VAR_IN_INST(Var, Inst) {
+ static constexpr bool IsDest = false;
+ if (!Var->getIgnoreLiveness() &&
+ !Var->getLiveRange().containsValue(InstNumber, IsDest)) {
+ Valid = false;
+ Str << "Liveness error: inst " << Inst.getNumber() << " var ";
+ Var->dump(this);
+ Str << " live range " << Var->getLiveRange() << "\n";
}
}
}
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index f0fae92..4199c41 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -19,6 +19,7 @@
#include "IceCfg.h"
#include "IceGlobalInits.h"
#include "IceInst.h"
+#include "IceInstVarIter.h"
#include "IceLiveness.h"
#include "IceOperand.h"
#include "IceTargetLowering.h"
@@ -846,26 +847,21 @@
// instruction started the dest variable's live range.
if (!Instr->isDestNonKillable() && Dest && Dest->hasReg())
++LiveRegCount[Dest->getRegNum()];
- for (SizeT I = 0; I < Instr->getSrcSize(); ++I) {
- Operand *Src = Instr->getSrc(I);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J) {
- const Variable *Var = Src->getVar(J);
- bool ShouldReport = Instr->isLastUse(Var);
- if (ShouldReport && Var->hasReg()) {
- // Don't report end of live range until the live count reaches 0.
- SizeT NewCount = --LiveRegCount[Var->getRegNum()];
- if (NewCount)
- ShouldReport = false;
- }
- if (ShouldReport) {
- if (First)
- Str << " \t# END=";
- else
- Str << ",";
- Var->emit(Func);
- First = false;
- }
+ FOREACH_VAR_IN_INST(Var, *Instr) {
+ bool ShouldReport = Instr->isLastUse(Var);
+ if (ShouldReport && Var->hasReg()) {
+ // Don't report end of live range until the live count reaches 0.
+ SizeT NewCount = --LiveRegCount[Var->getRegNum()];
+ if (NewCount)
+ ShouldReport = false;
+ }
+ if (ShouldReport) {
+ if (First)
+ Str << " \t# END=";
+ else
+ Str << ",";
+ Var->emit(Func);
+ First = false;
}
}
}
diff --git a/src/IceInst.cpp b/src/IceInst.cpp
index 4b89eb7..ae63ffa 100644
--- a/src/IceInst.cpp
+++ b/src/IceInst.cpp
@@ -17,6 +17,7 @@
#include "IceCfg.h"
#include "IceCfgNode.h"
+#include "IceInstVarIter.h"
#include "IceLiveness.h"
#include "IceOperand.h"
#include "IceTargetLowering.h"
@@ -95,19 +96,14 @@
return false; // early-exit optimization
if (const Variable *TestVar = llvm::dyn_cast<const Variable>(TestSrc)) {
LREndedBits Mask = LiveRangesEnded;
- for (SizeT I = 0; I < getSrcSize(); ++I) {
- Operand *Src = getSrc(I);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J) {
- const Variable *Var = Src->getVar(J);
- if (Var == TestVar) {
- // We've found where the variable is used in the instruction.
- return Mask & 1;
- }
- Mask >>= 1;
- if (Mask == 0)
- return false; // another early-exit optimization
+ FOREACH_VAR_IN_INST(Var, *this) {
+ if (Var == TestVar) {
+ // We've found where the variable is used in the instruction.
+ return Mask & 1;
}
+ Mask >>= 1;
+ if (Mask == 0)
+ return false; // another early-exit optimization
}
}
return false;
@@ -155,20 +151,14 @@
assert(!isDeleted());
resetLastUses();
VariablesMetadata *VMetadata = Func->getVMetadata();
- SizeT VarIndex = 0;
- for (SizeT I = 0; I < getSrcSize(); ++I) {
- Operand *Src = getSrc(I);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
- const Variable *Var = Src->getVar(J);
- if (VMetadata->isMultiBlock(Var))
- continue;
- SizeT Index = Var->getIndex();
- if (Live[Index])
- continue;
- Live[Index] = true;
- setLastUse(VarIndex);
- }
+ FOREACH_VAR_IN_INST(Var, *this) {
+ if (VMetadata->isMultiBlock(Var))
+ continue;
+ SizeT Index = Var->getIndex();
+ if (Live[Index])
+ continue;
+ Live[Index] = true;
+ setLastUse(IndexOfVarInInst(Var));
}
}
@@ -198,39 +188,29 @@
// we still need to update LiveRangesEnded.
bool IsPhi = llvm::isa<InstPhi>(this);
resetLastUses();
- SizeT VarIndex = 0;
- for (SizeT I = 0; I < getSrcSize(); ++I) {
- Operand *Src = getSrc(I);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J, ++VarIndex) {
- const Variable *Var = Src->getVar(J);
- SizeT VarNum = Liveness->getLiveIndex(Var->getIndex());
- if (!Live[VarNum]) {
- setLastUse(VarIndex);
- if (!IsPhi) {
- Live[VarNum] = true;
- // For a variable in SSA form, its live range can end at
- // most once in a basic block. However, after lowering to
- // two-address instructions, we end up with sequences like
- // "t=b;t+=c;a=t" where t's live range begins and ends
- // twice. ICE only allows a variable to have a single
- // liveness interval in a basic block (except for blocks
- // where a variable is live-in and live-out but there is a
- // gap in the middle). Therefore, this lowered sequence
- // needs to represent a single conservative live range for
- // t. Since the instructions are being traversed backwards,
- // we make sure LiveEnd is only set once by setting it only
- // when LiveEnd[VarNum]==0 (sentinel value). Note that it's
- // OK to set LiveBegin multiple times because of the
- // backwards traversal.
- if (LiveEnd && Liveness->getRangeMask(Var->getIndex())) {
- // Ideally, we would verify that VarNum wasn't already
- // added in this block, but this can't be done very
- // efficiently with LiveEnd as a vector. Instead,
- // livenessPostprocess() verifies this after the vector
- // has been sorted.
- LiveEnd->push_back(std::make_pair(VarNum, InstNumber));
- }
+ FOREACH_VAR_IN_INST(Var, *this) {
+ SizeT VarNum = Liveness->getLiveIndex(Var->getIndex());
+ if (!Live[VarNum]) {
+ setLastUse(IndexOfVarInInst(Var));
+ if (!IsPhi) {
+ Live[VarNum] = true;
+ // For a variable in SSA form, its live range can end at most once in a
+ // basic block. However, after lowering to two-address instructions, we
+ // end up with sequences like "t=b;t+=c;a=t" where t's live range begins
+ // and ends twice. ICE only allows a variable to have a single liveness
+ // interval in a basic block (except for blocks where a variable is
+ // live-in and live-out but there is a gap in the middle). Therefore,
+ // this lowered sequence needs to represent a single conservative live
+ // range for t. Since the instructions are being traversed backwards,
+ // we make sure LiveEnd is only set once by setting it only when
+ // LiveEnd[VarNum]==0 (sentinel value). Note that it's OK to set
+ // LiveBegin multiple times because of the backwards traversal.
+ if (LiveEnd && Liveness->getRangeMask(Var->getIndex())) {
+ // Ideally, we would verify that VarNum wasn't already added in this
+ // block, but this can't be done very efficiently with LiveEnd as a
+ // vector. Instead, livenessPostprocess() verifies this after the
+ // vector has been sorted.
+ LiveEnd->push_back(std::make_pair(VarNum, InstNumber));
}
}
}
@@ -581,19 +561,14 @@
// Print "LIVEEND={a,b,c}" for all source operands whose live ranges
// are known to end at this instruction.
if (Func->isVerbose(IceV_Liveness)) {
- for (SizeT I = 0; I < getSrcSize(); ++I) {
- Operand *Src = getSrc(I);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J) {
- const Variable *Var = Src->getVar(J);
- if (isLastUse(Var)) {
- if (First)
- Str << " // LIVEEND={";
- else
- Str << ",";
- Var->dump(Func);
- First = false;
- }
+ FOREACH_VAR_IN_INST(Var, *this) {
+ if (isLastUse(Var)) {
+ if (First)
+ Str << " // LIVEEND={";
+ else
+ Str << ",";
+ Var->dump(Func);
+ First = false;
}
}
if (!First)
diff --git a/src/IceInstVarIter.h b/src/IceInstVarIter.h
new file mode 100644
index 0000000..35cee00
--- /dev/null
+++ b/src/IceInstVarIter.h
@@ -0,0 +1,167 @@
+//===- subzero/src/IceInstVarIter.h - Iterate over inst vars ----*- C++ -*-===//
+//
+// The Subzero Code Generator
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+///
+/// \file
+/// This file defines a common pattern for iterating over the variables of an
+/// instruction.
+///
+//===----------------------------------------------------------------------===//
+
+#ifndef SUBZERO_SRC_ICEINSTVARITER_H
+#define SUBZERO_SRC_ICEINSTVARITER_H
+
+/// In Subzero, an Instr may have multiple Ice::Operands, and each Operand can
+/// have zero, one, or more Variables.
+///
+/// We found that a common pattern in Subzero is to iterate over all the
+/// Variables in an Instruction. This led to the following pattern being
+/// repeated multiple times across the codebase:
+///
+/// for (Operand Op : Instr.Operands())
+/// for (Variable Var : Op.Vars())
+/// do_my_thing(Var, Instr)
+///
+///
+/// This code is straightforward, but one may take a couple of seconds to
+/// identify what it is doing. We therefore introduce a macroized iterator for
+/// hiding this common idiom behind a more explicit interface.
+///
+/// FOREACH_VAR_IN_INST(Var, Instr) provides this interface. Its first argument
+/// needs to be a valid C++ identifier currently undeclared in the current
+/// scope; Instr can be any expression yielding a Ice::Inst&&. Even though its
+/// definition is ugly, awful, painful-to-read, using it is fairly simple:
+///
+/// FOREACH_VAR_IN_INST(Var, Instr)
+/// do_my_thing(Var, Instr)
+///
+/// If your loop body contains more than one statement, you can wrap it with a
+/// {}, just like any other C++ statement. Note that doing
+///
+/// FOREACH_VAR_IN_INST(Var0, Instr0)
+/// FOREACH_VAR_IN_INST(Var1, Instr1)
+///
+/// is perfectly safe and legal -- as long as Var0 and Var1 are different
+/// identifiers.
+///
+/// It is sometimes useful to know Var's index in Instr, which can be obtained
+/// with
+///
+/// IndexOfVarInInst(Var)
+///
+/// Similarly, the current Variable's Operand index can be obtained with
+///
+/// IndexOfVarOperandInInst(Var).
+///
+/// And that's pretty much it. Now, if you really hate yourself, keep reading,
+/// but beware! The iterator implementation abuses comma operators, for
+/// statements, variable initialization and expression evaluations. You have
+/// been warned.
+///
+/// **Implementation details**
+///
+/// First, let's "break" the two loops into multiple parts:
+///
+/// for ( Init1; Cond1; Step1 )
+/// if ( CondIf )
+/// UnreachableThenBody
+/// else
+/// for ( Init2; Cond2; Step2 )
+///
+/// The hairiest, scariest, most confusing parts here are Init2 and Cond2, so
+/// let's save them for later.
+///
+/// 1) Init1 declares five integer variables:
+/// * i --> outer loop control variable;
+/// * Var##Index --> the current variable index
+/// * SrcSize --> how many operands does Instr have?
+/// * j --> the inner loop control variable
+/// * NumVars --> how many variables does the current operand have?
+///
+/// 2) Cond1 and Step1 are your typical for condition and step expressions.
+///
+/// 3) CondIf is where the voodoo starts. We abuse CondIf to declare a local
+/// Operand * variable to hold the current operand being evaluated to avoid
+/// invoking an Instr::getOperand for each outter loop iteration -- which
+/// caused a small performance regression. We initialize the Operand *
+/// variable with nullptr, so UnreachableThenBody is trully unreachable, and
+/// use the else statement to declare the inner loop. We want to use an else
+/// here to prevent code like
+///
+/// FOREACH_VAR_IN_INST(Var, Instr) {
+/// } else {
+/// }
+///
+/// from being legal. We also want to avoid warnings about "dangling else"s.
+///
+/// 4) Init2 is where the voodoo starts. It declares a Variable * local
+/// variable name 'Var' (i.e., whatever identifier the first parameter to
+/// FOREACH_VAR_IN_INST is), and initializes it with nullptr. Why nullptr?
+/// Because as stated above, some operands have zero Variables, and therefore
+/// initializing Var = CurrentOperand->Variable(0) would lead to an assertion.
+/// Init2 is also required to initialize the control variables used in Cond2,
+/// as well as the current Operand * holder, Therefore, we use the obscure
+/// comma operator to initialize Var, and the control variables. The
+/// declaration
+///
+/// Variable *Var = (j = 0, CurrentOperand = Instr.Operand[i],
+/// NumVars = CurrentOperand.NumVars, nullptr)
+///
+/// achieves that.
+///
+/// 5) Cond2 is where we lose all hopes of having a self-documenting
+/// implementation. The stop condition for the inner loop is simply
+///
+/// j < NumVars
+///
+/// But there is one more thing we need to do before jumping to the iterator's
+/// body: we need to initialize Var with the current variable, but only if the
+/// loop has not terminated. So we implemented Cond2 in a way that it would
+/// make Var point to the current Variable, but only if there were more
+/// variables. So Cond2 became:
+///
+/// j < NumVars && (Var = CurrentOperand.Var[j])
+///
+/// which is not quite right. Cond2 would evaluate to false if
+/// CurrentOperand.Var[j] == nullptr. Even though that should never happen in
+/// Subzero, assuming this is always true is dangerous and could lead to
+/// problems in the future. So we abused the comma operator one more time here:
+///
+/// j < NumVars && ((Var = CurrentOperand.Var[j]), true)
+///
+/// this expression will evaluate to true if, and only if, j < NumVars.
+///
+/// 6) Step2 increments the inner loop's control variable, as well as the
+/// current variable index.
+///
+/// We use Var -- which should be a valid C++ identifier -- to uniquify names
+/// -- e.g., i##Var instead of simply i because we want users to be able to use
+/// the iterator for cross-products involving instructions' variables.
+#define FOREACH_VAR_IN_INST(Var, Instr) \
+ for (SizeT Sz_I##Var##_ = 0, Sz_##Var##Index_ = 0, \
+ Sz_SrcSize##Var##_ = (Instr).getSrcSize(), Sz_J##Var##_ = 0, \
+ Sz_NumVars##Var##_ = 0; \
+ Sz_I##Var##_ < Sz_SrcSize##Var##_; ++Sz_I##Var##_) \
+ if (Operand *Sz_Op##Var##_ = nullptr) \
+ /*nothing*/; \
+ else \
+ for (Variable *Var = \
+ (Sz_J##Var##_ = 0, \
+ Sz_Op##Var##_ = (Instr).getSrc(Sz_I##Var##_), \
+ Sz_NumVars##Var##_ = Sz_Op##Var##_->getNumVars(), nullptr); \
+ Sz_J##Var##_ < Sz_NumVars##Var##_ && \
+ ((Var = Sz_Op##Var##_->getVar(Sz_J##Var##_)), true); \
+ ++Sz_J##Var##_, ++Sz_##Var##Index_)
+
+#define IsOnlyValidInFOREACH_VAR_IN_INST(V) \
+ (static_cast<const SizeT>(Sz_##V##_))
+#define IndexOfVarInInst(Var) IsOnlyValidInFOREACH_VAR_IN_INST(Var##Index)
+#define IndexOfVarOperandInInst(Var) IsOnlyValidInFOREACH_VAR_IN_INST(I##Var)
+#undef OnlyValidIn_FOREACH_VAR_IN_INSTS
+
+#endif // SUBZERO_SRC_ICEINSTVARITER_H
diff --git a/src/IceOperand.cpp b/src/IceOperand.cpp
index 32316ba..c10656f 100644
--- a/src/IceOperand.cpp
+++ b/src/IceOperand.cpp
@@ -18,6 +18,7 @@
#include "IceCfg.h"
#include "IceCfgNode.h"
#include "IceInst.h"
+#include "IceInstVarIter.h"
#include "IceTargetLowering.h" // dumping stack/frame pointer register
namespace Ice {
@@ -328,16 +329,11 @@
assert(DestNum < Metadata.size());
Metadata[DestNum].markDef(Kind, &I, Node);
}
- for (SizeT SrcNum = 0; SrcNum < I.getSrcSize(); ++SrcNum) {
- Operand *Src = I.getSrc(SrcNum);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J) {
- const Variable *Var = Src->getVar(J);
- SizeT VarNum = Var->getIndex();
- assert(VarNum < Metadata.size());
- constexpr bool IsImplicit = false;
- Metadata[VarNum].markUse(Kind, &I, Node, IsImplicit);
- }
+ FOREACH_VAR_IN_INST(Var, I) {
+ SizeT VarNum = Var->getIndex();
+ assert(VarNum < Metadata.size());
+ constexpr bool IsImplicit = false;
+ Metadata[VarNum].markUse(Kind, &I, Node, IsImplicit);
}
}
}
diff --git a/src/IceRegAlloc.cpp b/src/IceRegAlloc.cpp
index 2c6d742..cad7fb5 100644
--- a/src/IceRegAlloc.cpp
+++ b/src/IceRegAlloc.cpp
@@ -18,6 +18,7 @@
#include "IceCfg.h"
#include "IceCfgNode.h"
#include "IceInst.h"
+#include "IceInstVarIter.h"
#include "IceOperand.h"
#include "IceTargetLowering.h"
@@ -180,16 +181,11 @@
}
}
}
- for (SizeT I = 0; I < Inst.getSrcSize(); ++I) {
- Operand *Src = Inst.getSrc(I);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J) {
- const Variable *Var = Src->getVar(J);
- if (Var->getIgnoreLiveness())
- continue;
- if (Var->hasReg() || Var->mustHaveReg())
- LREnd[Var->getIndex()] = Inst.getNumber();
- }
+ FOREACH_VAR_IN_INST(Var, Inst) {
+ if (Var->getIgnoreLiveness())
+ continue;
+ if (Var->hasReg() || Var->mustHaveReg())
+ LREnd[Var->getIndex()] = Inst.getNumber();
}
}
}
@@ -298,14 +294,9 @@
// Remove from RegMask any physical registers referenced during Cur's live
// range. Start looking after SpillPoint gets set, i.e. once Cur's live
// range begins.
- for (SizeT i = 0; i < I->getSrcSize(); ++i) {
- Operand *Src = I->getSrc(i);
- SizeT NumVars = Src->getNumVars();
- for (SizeT j = 0; j < NumVars; ++j) {
- const Variable *Var = Src->getVar(j);
- if (Var->hasRegTmp())
- Iter.RegMask[Var->getRegNumTmp()] = false;
- }
+ FOREACH_VAR_IN_INST(Var, *I) {
+ if (Var->hasRegTmp())
+ Iter.RegMask[Var->getRegNumTmp()] = false;
}
}
}
diff --git a/src/IceTargetLowering.cpp b/src/IceTargetLowering.cpp
index 5ef6d09..5268aa7 100644
--- a/src/IceTargetLowering.cpp
+++ b/src/IceTargetLowering.cpp
@@ -25,6 +25,7 @@
#include "IceCfg.h" // setError()
#include "IceCfgNode.h"
#include "IceGlobalInits.h"
+#include "IceInstVarIter.h"
#include "IceOperand.h"
#include "IceRegAlloc.h"
#include "IceTargetLoweringARM32.h"
@@ -289,13 +290,8 @@
continue;
if (const Variable *Var = Inst.getDest())
IsVarReferenced[Var->getIndex()] = true;
- for (SizeT I = 0; I < Inst.getSrcSize(); ++I) {
- Operand *Src = Inst.getSrc(I);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J) {
- const Variable *Var = Src->getVar(J);
- IsVarReferenced[Var->getIndex()] = true;
- }
+ FOREACH_VAR_IN_INST(Var, Inst) {
+ IsVarReferenced[Var->getIndex()] = true;
}
}
}
diff --git a/src/IceTargetLoweringX86BaseImpl.h b/src/IceTargetLoweringX86BaseImpl.h
index afbbaf3..bb0ba86 100644
--- a/src/IceTargetLoweringX86BaseImpl.h
+++ b/src/IceTargetLoweringX86BaseImpl.h
@@ -23,6 +23,7 @@
#include "IceDefs.h"
#include "IceELFObjectWriter.h"
#include "IceGlobalInits.h"
+#include "IceInstVarIter.h"
#include "IceLiveness.h"
#include "IceOperand.h"
#include "IcePhiLoweringImpl.h"
@@ -193,24 +194,21 @@
Producers[Var->getIndex()] = BoolFoldingEntry<MachineTraits>(&Instr);
}
// Check each src variable against the map.
- for (SizeT I = 0; I < Instr.getSrcSize(); ++I) {
- Operand *Src = Instr.getSrc(I);
- SizeT NumVars = Src->getNumVars();
- for (SizeT J = 0; J < NumVars; ++J) {
- const Variable *Var = Src->getVar(J);
- SizeT VarNum = Var->getIndex();
- if (containsValid(VarNum)) {
- if (I != 0 // All valid consumers use Var as the first source operand
- || getConsumerKind(&Instr) == CK_None // must be white-listed
- || (Producers[VarNum].IsComplex && // complex can't be multi-use
- Producers[VarNum].NumUses > 0)) {
- setInvalid(VarNum);
- continue;
- }
- ++Producers[VarNum].NumUses;
- if (Instr.isLastUse(Var)) {
- Producers[VarNum].IsLiveOut = false;
- }
+ FOREACH_VAR_IN_INST(Var, Instr) {
+ SizeT VarNum = Var->getIndex();
+ if (containsValid(VarNum)) {
+ if (IndexOfVarOperandInInst(Var) !=
+ 0 // All valid consumers use Var as the first source operand
+ ||
+ getConsumerKind(&Instr) == CK_None // must be white-listed
+ || (Producers[VarNum].IsComplex && // complex can't be multi-use
+ Producers[VarNum].NumUses > 0)) {
+ setInvalid(VarNum);
+ continue;
+ }
+ ++Producers[VarNum].NumUses;
+ if (Instr.isLastUse(Var)) {
+ Producers[VarNum].IsLiveOut = false;
}
}
}
