archive/1.vm/041jump_target.cc

   1 //: Support jumps to a specific label (the 'jump target') in the same recipe.
   2 //: Jump targets must be unique and unambiguous within any recipe.
   3 //:
   4 //: The 'break' and 'loop' pseudo instructions can also take jump targets.
   5 //: Which instruction you use is just documentation about intent; use 'break'
   6 //: to indicate you're exiting one or more loop nests, and 'loop' to indicate
   7 //: you're skipping to the next iteration of some containing loop nest.
   8
   9 //: Since they have to be unique in a recipe, not all labels can be jump
  10 //: targets.
  11 bool is_jump_target(const string& label) {
  12   if (label == "{" || label == "}") return false;
  13   // End is_jump_target Special-cases
  14   return is_label_word(label);
  15 }
  16
  17 void test_jump_to_label() {
  18   run(
  19       "def main [\n"
  20       "  jump +target:label\n"
  21       "  1:num <- copy 0\n"
  22       "  +target\n"
  23       "]\n"
  24   );
  25   CHECK_TRACE_DOESNT_CONTAIN("mem: storing 0 in location 1");
  26 }
  27
  28 :(before "End Mu Types Initialization")
  29 put(Type_ordinal, "label", 0);
  30
  31 :(before "End Instruction Modifying Transforms")
  32 Transform.push_back(transform_labels);  // idempotent
  33
  34 :(code)
  35 void transform_labels(const recipe_ordinal r) {
  36   map<string, int> offset;
  37   for (int i = 0;  i < SIZE(get(Recipe, r).steps);  ++i) {
  38     const instruction& inst = get(Recipe, r).steps.at(i);
  39     if (!inst.is_label) continue;
  40     if (is_jump_target(inst.label)) {
  41       if (!contains_key(offset, inst.label)) {
  42         put(offset, inst.label, i);
  43       }
  44       else {
  45         raise << maybe(get(Recipe, r).name) << "duplicate label '" << inst.label << "'" << end();
  46         // have all jumps skip some random but noticeable and deterministic amount of code
  47         put(offset, inst.label, 9999);
  48       }
  49     }
  50   }
  51   for (int i = 0;  i < SIZE(get(Recipe, r).steps);  ++i) {
  52     instruction& inst = get(Recipe, r).steps.at(i);
  53     if (inst.name == "jump") {
  54       if (inst.ingredients.empty()) {
  55         raise << maybe(get(Recipe, r).name) << "'" << to_original_string(inst) << "' expects an ingredient but got 0\n" << end();
  56         return;
  57       }
  58       replace_offset(inst.ingredients.at(0), offset, i, r);
  59     }
  60     if (inst.name == "jump-if" || inst.name == "jump-unless") {
  61       if (SIZE(inst.ingredients) < 2) {
  62         raise << maybe(get(Recipe, r).name) << "'" << to_original_string(inst) << "' expects 2 ingredients but got " << SIZE(inst.ingredients) << '\n' << end();
  63         return;
  64       }
  65       replace_offset(inst.ingredients.at(1), offset, i, r);
  66     }
  67     if ((inst.name == "loop" || inst.name == "break")
  68         && SIZE(inst.ingredients) >= 1) {
  69       replace_offset(inst.ingredients.at(0), offset, i, r);
  70     }
  71     if ((inst.name == "loop-if" || inst.name == "loop-unless"
  72             || inst.name == "break-if" || inst.name == "break-unless")
  73         && SIZE(inst.ingredients) >= 2) {
  74       replace_offset(inst.ingredients.at(1), offset, i, r);
  75     }
  76   }
  77 }
  78
  79 void replace_offset(reagent& x, /*const*/ map<string, int>& offset, const int current_offset, const recipe_ordinal r) {
  80   if (!is_literal(x)) {
  81     raise << maybe(get(Recipe, r).name) << "jump target must be offset or label but is '" << x.original_string << "'\n" << end();
  82     x.set_value(0);  // no jump by default
  83     return;
  84   }
  85   if (x.initialized) return;
  86   if (is_integer(x.name)) return;  // non-labels will be handled like other number operands
  87   if (!is_jump_target(x.name)) {
  88     raise << maybe(get(Recipe, r).name) << "can't jump to label '" << x.name << "'\n" << end();
  89     x.set_value(0);  // no jump by default
  90     return;
  91   }
  92   if (!contains_key(offset, x.name)) {
  93     raise << maybe(get(Recipe, r).name) << "can't find label '" << x.name << "'\n" << end();
  94     x.set_value(0);  // no jump by default
  95     return;
  96   }
  97   x.set_value(get(offset, x.name) - current_offset);
  98 }
  99
 100 void test_break_to_label() {
 101   run(
 102       "def main [\n"
 103       "  {\n"
 104       "    {\n"
 105       "      break +target:label\n"
 106       "      1:num <- copy 0\n"
 107       "    }\n"
 108       "  }\n"
 109       "  +target\n"
 110       "]\n"
 111   );
 112   CHECK_TRACE_DOESNT_CONTAIN("mem: storing 0 in location 1");
 113 }
 114
 115 void test_jump_if_to_label() {
 116   run(
 117       "def main [\n"
 118       "  {\n"
 119       "    {\n"
 120       "      jump-if 1, +target:label\n"
 121       "      1:num <- copy 0\n"
 122       "    }\n"
 123       "  }\n"
 124       "  +target\n"
 125       "]\n"
 126   );
 127   CHECK_TRACE_DOESNT_CONTAIN("mem: storing 0 in location 1");
 128 }
 129
 130 void test_loop_unless_to_label() {
 131   run(
 132       "def main [\n"
 133       "  {\n"
 134       "    {\n"
 135       "      loop-unless 0, +target:label\n"  // loop/break with a label don't care about braces
 136       "      1:num <- copy 0\n"
 137       "    }\n"
 138       "  }\n"
 139       "  +target\n"
 140       "]\n"
 141   );
 142   CHECK_TRACE_DOESNT_CONTAIN("mem: storing 0 in location 1");
 143 }
 144
 145 void test_jump_runs_code_after_label() {
 146   run(
 147       "def main [\n"
 148       // first a few lines of padding to exercise the offset computation
 149       "  1:num <- copy 0\n"
 150       "  2:num <- copy 0\n"
 151       "  3:num <- copy 0\n"
 152       "  jump +target:label\n"
 153       "  4:num <- copy 0\n"
 154       "  +target\n"
 155       "  5:num <- copy 0\n"
 156       "]\n"
 157   );
 158   CHECK_TRACE_CONTENTS(
 159       "mem: storing 0 in location 5\n"
 160   );
 161   CHECK_TRACE_DOESNT_CONTAIN("mem: storing 0 in location 4");
 162 }
 163
 164 void test_jump_fails_without_target() {
 165   Hide_errors = true;
 166   run(
 167       "def main [\n"
 168       "  jump\n"
 169       "]\n"
 170   );
 171   CHECK_TRACE_CONTENTS(
 172       "error: main: 'jump' expects an ingredient but got 0\n"
 173   );
 174 }
 175
 176 void test_jump_fails_without_target_2() {
 177   Hide_errors = true;
 178   run(
 179       "def main [\n"
 180       "  jump-if true\n"
 181       "]\n"
 182   );
 183   CHECK_TRACE_CONTENTS(
 184       "error: main: 'jump-if true' expects 2 ingredients but got 1\n"
 185   );
 186 }
 187
 188 void test_recipe_fails_on_duplicate_jump_target() {
 189   Hide_errors = true;
 190   run(
 191       "def main [\n"
 192       "  +label\n"
 193       "  1:num <- copy 0\n"
 194       "  +label\n"
 195       "  2:num <- copy 0\n"
 196       "]\n"
 197   );
 198   CHECK_TRACE_CONTENTS(
 199       "error: main: duplicate label '+label'\n"
 200   );
 201 }
 202
 203 void test_jump_ignores_nontarget_label() {
 204   Hide_errors = true;
 205   run(
 206       "def main [\n"
 207       // first a few lines of padding to exercise the offset computation
 208       "  1:num <- copy 0\n"
 209       "  2:num <- copy 0\n"
 210       "  3:num <- copy 0\n"
 211       "  jump $target:label\n"
 212       "  4:num <- copy 0\n"
 213       "  $target\n"
 214       "  5:num <- copy 0\n"
 215       "]\n"
 216   );
 217   CHECK_TRACE_CONTENTS(
 218       "error: main: can't jump to label '$target'\n"
 219   );
 220 }