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 11 /// \brief Defines a common pattern for iterating over the variables of an 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, \ 148 Sz_NumVars##Var##_ = 0, Sz_Foreach_Break = 0; \ 149 !Sz_Foreach_Break && Sz_I##Var##_ < Sz_SrcSize##Var##_; ++Sz_I##Var##_) \ 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); \ 157 !Sz_Foreach_Break && Sz_J##Var##_ < Sz_NumVars##Var##_ && \ 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) 165 #define FOREACH_VAR_IN_INST_BREAK \ 166 if (true) { \ 167 Sz_Foreach_Break = 1; \ 168 continue; \ 169 } else { \ 170 } 171 #undef OnlyValidIn_FOREACH_VAR_IN_INSTS 172 173 #endif // SUBZERO_SRC_ICEINSTVARITER_H 174