John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 1 | //===- subzero/src/IceInstVarIter.h - Iterate over inst vars ----*- C++ -*-===// |
| 2 | // |
| 3 | // The Subzero Code Generator |
| 4 | // |
| 5 | // This file is distributed under the University of Illinois Open Source |
| 6 | // License. See LICENSE.TXT for details. |
| 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | /// |
| 10 | /// \file |
Jim Stichnoth | 92a6e5b | 2015-12-02 16:52:44 -0800 | [diff] [blame] | 11 | /// \brief Defines a common pattern for iterating over the variables of an |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 12 | /// instruction. |
| 13 | /// |
| 14 | //===----------------------------------------------------------------------===// |
| 15 | |
| 16 | #ifndef SUBZERO_SRC_ICEINSTVARITER_H |
| 17 | #define SUBZERO_SRC_ICEINSTVARITER_H |
| 18 | |
| 19 | /// In Subzero, an Instr may have multiple Ice::Operands, and each Operand can |
| 20 | /// have zero, one, or more Variables. |
| 21 | /// |
| 22 | /// We found that a common pattern in Subzero is to iterate over all the |
| 23 | /// Variables in an Instruction. This led to the following pattern being |
| 24 | /// repeated multiple times across the codebase: |
| 25 | /// |
| 26 | /// for (Operand Op : Instr.Operands()) |
| 27 | /// for (Variable Var : Op.Vars()) |
| 28 | /// do_my_thing(Var, Instr) |
| 29 | /// |
| 30 | /// |
| 31 | /// This code is straightforward, but one may take a couple of seconds to |
| 32 | /// identify what it is doing. We therefore introduce a macroized iterator for |
| 33 | /// hiding this common idiom behind a more explicit interface. |
| 34 | /// |
| 35 | /// FOREACH_VAR_IN_INST(Var, Instr) provides this interface. Its first argument |
| 36 | /// needs to be a valid C++ identifier currently undeclared in the current |
| 37 | /// scope; Instr can be any expression yielding a Ice::Inst&&. Even though its |
| 38 | /// definition is ugly, awful, painful-to-read, using it is fairly simple: |
| 39 | /// |
| 40 | /// FOREACH_VAR_IN_INST(Var, Instr) |
| 41 | /// do_my_thing(Var, Instr) |
| 42 | /// |
| 43 | /// If your loop body contains more than one statement, you can wrap it with a |
| 44 | /// {}, just like any other C++ statement. Note that doing |
| 45 | /// |
| 46 | /// FOREACH_VAR_IN_INST(Var0, Instr0) |
| 47 | /// FOREACH_VAR_IN_INST(Var1, Instr1) |
| 48 | /// |
| 49 | /// is perfectly safe and legal -- as long as Var0 and Var1 are different |
| 50 | /// identifiers. |
| 51 | /// |
| 52 | /// It is sometimes useful to know Var's index in Instr, which can be obtained |
| 53 | /// with |
| 54 | /// |
| 55 | /// IndexOfVarInInst(Var) |
| 56 | /// |
| 57 | /// Similarly, the current Variable's Operand index can be obtained with |
| 58 | /// |
| 59 | /// IndexOfVarOperandInInst(Var). |
| 60 | /// |
| 61 | /// And that's pretty much it. Now, if you really hate yourself, keep reading, |
| 62 | /// but beware! The iterator implementation abuses comma operators, for |
| 63 | /// statements, variable initialization and expression evaluations. You have |
| 64 | /// been warned. |
| 65 | /// |
| 66 | /// **Implementation details** |
| 67 | /// |
| 68 | /// First, let's "break" the two loops into multiple parts: |
| 69 | /// |
| 70 | /// for ( Init1; Cond1; Step1 ) |
| 71 | /// if ( CondIf ) |
| 72 | /// UnreachableThenBody |
| 73 | /// else |
| 74 | /// for ( Init2; Cond2; Step2 ) |
| 75 | /// |
| 76 | /// The hairiest, scariest, most confusing parts here are Init2 and Cond2, so |
| 77 | /// let's save them for later. |
| 78 | /// |
| 79 | /// 1) Init1 declares five integer variables: |
| 80 | /// * i --> outer loop control variable; |
| 81 | /// * Var##Index --> the current variable index |
| 82 | /// * SrcSize --> how many operands does Instr have? |
| 83 | /// * j --> the inner loop control variable |
| 84 | /// * NumVars --> how many variables does the current operand have? |
| 85 | /// |
| 86 | /// 2) Cond1 and Step1 are your typical for condition and step expressions. |
| 87 | /// |
| 88 | /// 3) CondIf is where the voodoo starts. We abuse CondIf to declare a local |
| 89 | /// Operand * variable to hold the current operand being evaluated to avoid |
| 90 | /// invoking an Instr::getOperand for each outter loop iteration -- which |
| 91 | /// caused a small performance regression. We initialize the Operand * |
| 92 | /// variable with nullptr, so UnreachableThenBody is trully unreachable, and |
| 93 | /// use the else statement to declare the inner loop. We want to use an else |
| 94 | /// here to prevent code like |
| 95 | /// |
| 96 | /// FOREACH_VAR_IN_INST(Var, Instr) { |
| 97 | /// } else { |
| 98 | /// } |
| 99 | /// |
| 100 | /// from being legal. We also want to avoid warnings about "dangling else"s. |
| 101 | /// |
| 102 | /// 4) Init2 is where the voodoo starts. It declares a Variable * local |
| 103 | /// variable name 'Var' (i.e., whatever identifier the first parameter to |
| 104 | /// FOREACH_VAR_IN_INST is), and initializes it with nullptr. Why nullptr? |
| 105 | /// Because as stated above, some operands have zero Variables, and therefore |
| 106 | /// initializing Var = CurrentOperand->Variable(0) would lead to an assertion. |
| 107 | /// Init2 is also required to initialize the control variables used in Cond2, |
| 108 | /// as well as the current Operand * holder, Therefore, we use the obscure |
| 109 | /// comma operator to initialize Var, and the control variables. The |
| 110 | /// declaration |
| 111 | /// |
| 112 | /// Variable *Var = (j = 0, CurrentOperand = Instr.Operand[i], |
| 113 | /// NumVars = CurrentOperand.NumVars, nullptr) |
| 114 | /// |
| 115 | /// achieves that. |
| 116 | /// |
| 117 | /// 5) Cond2 is where we lose all hopes of having a self-documenting |
| 118 | /// implementation. The stop condition for the inner loop is simply |
| 119 | /// |
| 120 | /// j < NumVars |
| 121 | /// |
| 122 | /// But there is one more thing we need to do before jumping to the iterator's |
| 123 | /// body: we need to initialize Var with the current variable, but only if the |
| 124 | /// loop has not terminated. So we implemented Cond2 in a way that it would |
| 125 | /// make Var point to the current Variable, but only if there were more |
| 126 | /// variables. So Cond2 became: |
| 127 | /// |
| 128 | /// j < NumVars && (Var = CurrentOperand.Var[j]) |
| 129 | /// |
| 130 | /// which is not quite right. Cond2 would evaluate to false if |
| 131 | /// CurrentOperand.Var[j] == nullptr. Even though that should never happen in |
| 132 | /// Subzero, assuming this is always true is dangerous and could lead to |
| 133 | /// problems in the future. So we abused the comma operator one more time here: |
| 134 | /// |
| 135 | /// j < NumVars && ((Var = CurrentOperand.Var[j]), true) |
| 136 | /// |
| 137 | /// this expression will evaluate to true if, and only if, j < NumVars. |
| 138 | /// |
| 139 | /// 6) Step2 increments the inner loop's control variable, as well as the |
| 140 | /// current variable index. |
| 141 | /// |
| 142 | /// We use Var -- which should be a valid C++ identifier -- to uniquify names |
| 143 | /// -- e.g., i##Var instead of simply i because we want users to be able to use |
| 144 | /// the iterator for cross-products involving instructions' variables. |
| 145 | #define FOREACH_VAR_IN_INST(Var, Instr) \ |
| 146 | for (SizeT Sz_I##Var##_ = 0, Sz_##Var##Index_ = 0, \ |
| 147 | Sz_SrcSize##Var##_ = (Instr).getSrcSize(), Sz_J##Var##_ = 0, \ |
Jim Stichnoth | 28b71be | 2015-10-12 15:24:46 -0700 | [diff] [blame] | 148 | Sz_NumVars##Var##_ = 0, Sz_Foreach_Break = 0; \ |
| 149 | !Sz_Foreach_Break && Sz_I##Var##_ < Sz_SrcSize##Var##_; ++Sz_I##Var##_) \ |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 150 | if (Operand *Sz_Op##Var##_ = nullptr) \ |
| 151 | /*nothing*/; \ |
| 152 | else \ |
| 153 | for (Variable *Var = \ |
| 154 | (Sz_J##Var##_ = 0, \ |
| 155 | Sz_Op##Var##_ = (Instr).getSrc(Sz_I##Var##_), \ |
| 156 | Sz_NumVars##Var##_ = Sz_Op##Var##_->getNumVars(), nullptr); \ |
Jim Stichnoth | 28b71be | 2015-10-12 15:24:46 -0700 | [diff] [blame] | 157 | !Sz_Foreach_Break && Sz_J##Var##_ < Sz_NumVars##Var##_ && \ |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 158 | ((Var = Sz_Op##Var##_->getVar(Sz_J##Var##_)), true); \ |
| 159 | ++Sz_J##Var##_, ++Sz_##Var##Index_) |
| 160 | |
| 161 | #define IsOnlyValidInFOREACH_VAR_IN_INST(V) \ |
| 162 | (static_cast<const SizeT>(Sz_##V##_)) |
| 163 | #define IndexOfVarInInst(Var) IsOnlyValidInFOREACH_VAR_IN_INST(Var##Index) |
| 164 | #define IndexOfVarOperandInInst(Var) IsOnlyValidInFOREACH_VAR_IN_INST(I##Var) |
Jim Stichnoth | 28b71be | 2015-10-12 15:24:46 -0700 | [diff] [blame] | 165 | #define FOREACH_VAR_IN_INST_BREAK \ |
| 166 | if (true) { \ |
| 167 | Sz_Foreach_Break = 1; \ |
| 168 | continue; \ |
| 169 | } else { \ |
| 170 | } |
John Porto | ec3f565 | 2015-08-31 15:07:09 -0700 | [diff] [blame] | 171 | #undef OnlyValidIn_FOREACH_VAR_IN_INSTS |
| 172 | |
| 173 | #endif // SUBZERO_SRC_ICEINSTVARITER_H |