Subzero: Provide a macro for iterating over instruction variables.

src/IceInstVarIter.h

+//===- subzero/src/IceInstVarIter.h - Iterate over inst vars-----*- C++ -*-===//

[Jim Stichnoth, 2015/08/29 23:20:39]

s/vars-/vars /

[John, 2015/08/31 16:26:39]

Done.

+//
+//                        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 lead to the following pattern being

[Jim Stichnoth, 2015/08/29 23:20:39]

leads or led

[John, 2015/08/31 16:26:39]

Done.

+/// 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:

[ascull, 2015/08/31 16:30:21]

Why no use a function for this and pass in a lambda. That would make the
definition easier to read and be "more C++". Surely the compiler can do some
optimization to avoid having to do function calls?

[John, 2015/08/31 17:43:09]

I am all for avoiding macros/macro-trickery and other things (though it may not
seem so with the assembler tests and now this), but in this case  macros are the
right tools.

* I don't think C++ compilers would be smart enough to inline functions taking
lambdas / std::function. Those aren't function pointers, but closures -- they
have other state the needs to be passed around.

* Lambdas are also weird-looking entities ([<captures>](<parameters) {...})

* Sometimes you might need access to "internal" loop state (e.g., control
variable, variable index.) If we use lambdas, we need to pass those as
parameters to **every** lambda -- even the ones that do no use them.

* The clumsy implementation is hidden behind a library, but the exposed
interface is somewhat natural:

FOREACH_VAR_IN_INST(Var, Instr) {
  ...
}

versus

foreacg_var_in_inst(Instr, [...](SizeT op_index,
                                 SizeT VarIndex,
                                 SizeT VarIndexInInstr,
                                 SizeT VarIndexInOperand) {
   ...
                           });

* Jim tried using an inline function with an std::function parameter, which led
to a small performance regression.

+///
+/// 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 )
+///   for ( Init2; Cond2; Step2 )
+///
+/// The hariest, scariest, most confusing parts here are Init2 and Cond2, so

[Jim Stichnoth, 2015/08/29 23:20:39]

hairiest

[John, 2015/08/31 16:26:39]

Done.

+/// 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) 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 initialize it with nullptr. Why nullptr?

[Jim Stichnoth, 2015/08/29 23:20:39]

initializes

[John, 2015/08/31 16:26:39]

Done.

+///  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.
+///  Therefore, we use the obscure comma operator to initialize Var, and the
+///  control variables. The declaration
+///
+///    Variable *Var = (j = 0, NumVars = CurrentOperand.NumVars, nullptr)
+///
+/// achieves that.
+///
+///  4) 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 iterators

[Jim Stichnoth, 2015/08/29 23:20:39]

iterator's

[John, 2015/08/31 16:26:40]

Done.

+///  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

[Jim Stichnoth, 2015/08/29 23:20:39]

weird line breaks

[John, 2015/08/31 16:26:39]

Done.

+///  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 evalute 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

[Jim Stichnoth, 2015/08/29 23:20:39]

It is in fact safe to assume that in Subzero.

But the compiler cannot know that, and so changing the second && operand to be
true probably makes the code more efficient.

[John, 2015/08/31 16:26:39]

Acknowledged.

+/// 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.
+///
+///  5) 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 uniquefy names --

[Jim Stichnoth, 2015/08/29 23:20:39]

I think uniquify is the more common spelling of this made-up word.

[John, 2015/08/31 16:26:39]

Done.

+/// 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 ___I##Var##___ = 0, ___##Var##Index##___ = 0,                     \

[Jim Stichnoth, 2015/08/29 23:20:39]

I looked more closely at C++ reserved identifiers, and it seems we should not be
using identifiers with a double underscore anywhere, nor identifiers starting
with an underscore plus an uppercase letter.

[John, 2015/08/31 16:26:39]

Done.

[Jim Stichnoth, 2015/08/31 18:22:21]

Not quite.  You're not allowed to start the identifier with "_Sz" because of an
underscore followed by an uppercase letter.

[ascull, 2015/08/31 18:33:52]

http://en.cppreference.com/w/cpp/language/identifiers has all the rules.
Underscore + lowercase is good, so it ending in an underscore.

+             ___SrcSize##Var##___ = (Instr).getSrcSize(), ___J##Var##___ = 0,  \
+             ___NumVars##Var##___ = 0;                                         \
+       ___I##Var##___ < ___SrcSize##Var##___; ++___I##Var##___)                \
+    for (Variable *Var = (___J##Var##___ = 0,                                  \
+                         ___NumVars##Var##___ =                                \
+                              (Instr).getSrc(___I##Var##___)->getNumVars(),    \
+                         nullptr);                                             \
+         ___J##Var##___ < ___NumVars##Var##___ &&                              \
+         ((Var = (Instr).getSrc(___I##Var##___)->getVar(___J##Var##___)),      \
+          true);                                                               \
+         ++___J##Var##___, ++___##Var##Index___)
+
+#define IndexOfVarInInst(Var) ((const SizeT)___##Var##Index##___)

[Jim Stichnoth, 2015/08/29 23:20:39]

I wonder if we could find good names for the three macros that are more
unifying, like share a common prefix or something?

[John, 2015/08/31 16:26:39]

I am not a huge fan of prefixes/suffixes as I find the resulting names less
"natural" to read. I personally like these names, but I agree that the two
accessor macros are misleading as there's nothing preventing people from writing

IndexOfVarInInst(Var)

I rewrote this code so that IndexOfVar and IndexOfVarOperand now expand to

#define IndexOfVarInInst(Var) \
    OnlyValidIn_FOREACH_VAR_IN_INSTS_Body(_Sz_##Var##Index_)

#define IndexOfVarOperandInInst(Var) \
    OnlyValidIn_FOREACH_VAR_IN_INSTS_Body(_Sz_I##Var##_)

With this implementation, we get a "nice" error

src/IceInstVarIter.h:142:31: note: expanded from macro 'IndexOfVarInInst'
#define IndexOfVarInInst(Var) IsOnlyValidInFOREACH_VAR_IN_INSTS(Var##Index)

thoughts?

[Jim Stichnoth, 2015/08/31 18:22:21]

Sick. :)

+#define IndexOfVarOperandInInst(Var) ((const SizeT)___I##Var##___)
+
+#endif // SUBZERO_SRC_ICEINSTVARITER_H