src/binaryen/src/passes/MergeBlocks.cpp

   1 /*
   2  * Copyright 2015 WebAssembly Community Group participants
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *     http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 //
  18 // Merges blocks to their parents.
  19 //
  20 // We also restructure blocks in order to enable such merging. For
  21 // example,
  22 //
  23 //  (i32.store
  24 //    (block
  25 //      (call $foo)
  26 //      (i32.load (i32.const 100))
  27 //    )
  28 //    (i32.const 0)
  29 //  )
  30 //
  31 // can be transformed into
  32 //
  33 //  (block
  34 //    (call $foo)
  35 //    (i32.store
  36 //      (block
  37 //        (i32.load (i32.const 100))
  38 //      )
  39 //      (i32.const 0)
  40 //    )
  41 //  )
  42 //
  43 // after which the internal block can go away, and
  44 // the new external block might be mergeable. This is always
  45 // worth it if the internal block ends up with 1 item.
  46 // For the second operand,
  47 //
  48 //  (i32.store
  49 //    (i32.const 100)
  50 //    (block
  51 //      (call $foo)
  52 //      (i32.load (i32.const 200))
  53 //    )
  54 //  )
  55 //
  56 // The order of operations requires that the first execute
  57 // before. We can do the same operation, but only if the
  58 // first has no side effects, or the code we are moving out
  59 // has no side effects.
  60 // If we can do this to both operands, we can generate a
  61 // single outside block.
  62 //
  63
  64 #include <wasm.h>
  65 #include <pass.h>
  66 #include <wasm-builder.h>
  67 #include <ir/utils.h>
  68 #include <ir/effects.h>
  69
  70 namespace wasm {
  71
  72 // Looks for reasons we can't remove the values from breaks to an origin
  73 // For example, if there is a switch targeting us, we can't do it - we can't remove the value from other targets
  74 struct ProblemFinder : public ControlFlowWalker<ProblemFinder> {
  75   Name origin;
  76   bool foundProblem = false;
  77   // count br_ifs, and dropped br_ifs. if they don't match, then a br_if flow value is used, and we can't drop it
  78   Index brIfs = 0;
  79   Index droppedBrIfs = 0;
  80   PassOptions& passOptions;
  81
  82   ProblemFinder(PassOptions& passOptions) : passOptions(passOptions) {}
  83
  84   void visitBreak(Break* curr) {
  85     if (curr->name == origin) {
  86       if (curr->condition) {
  87         brIfs++;
  88       }
  89       // if the value has side effects, we can't remove it
  90       if (EffectAnalyzer(passOptions, curr->value).hasSideEffects()) {
  91         foundProblem = true;
  92       }
  93     }
  94   }
  95
  96   void visitDrop(Drop* curr) {
  97     if (auto* br = curr->value->dynCast<Break>()) {
  98       if (br->name == origin && br->condition) {
  99         droppedBrIfs++;
 100       }
 101     }
 102   }
 103
 104   void visitSwitch(Switch* curr) {
 105     if (curr->default_ == origin) {
 106       foundProblem = true;
 107       return;
 108     }
 109     for (auto& target : curr->targets) {
 110       if (target == origin) {
 111         foundProblem = true;
 112         return;
 113       }
 114     }
 115   }
 116
 117   bool found() {
 118     assert(brIfs >= droppedBrIfs);
 119     return foundProblem || brIfs > droppedBrIfs;
 120   }
 121 };
 122
 123 // Drops values from breaks to an origin.
 124 // While doing so it can create new blocks, so optimize blocks as well.
 125 struct BreakValueDropper : public ControlFlowWalker<BreakValueDropper> {
 126   Name origin;
 127   PassOptions& passOptions;
 128
 129   BreakValueDropper(PassOptions& passOptions) : passOptions(passOptions) {}
 130
 131   void visitBlock(Block* curr);
 132
 133   void visitBreak(Break* curr) {
 134     if (curr->value && curr->name == origin) {
 135       Builder builder(*getModule());
 136       auto* value = curr->value;
 137       if (value->type == unreachable) {
 138         // the break isn't even reached
 139         replaceCurrent(value);
 140         return;
 141       }
 142       curr->value = nullptr;
 143       curr->finalize();
 144       replaceCurrent(builder.makeSequence(builder.makeDrop(value), curr));
 145     }
 146   }
 147
 148   void visitDrop(Drop* curr) {
 149     // if we dropped a br_if whose value we removed, then we are now dropping a (block (drop value) (br_if)) with type none, which does not need a drop
 150     // likewise, unreachable does not need to be dropped, so we just leave drops of concrete values
 151     if (!isConcreteWasmType(curr->value->type)) {
 152       replaceCurrent(curr->value);
 153     }
 154   }
 155 };
 156
 157 static bool hasUnreachableChild(Block* block) {
 158   for (auto* test : block->list) {
 159     if (test->type == unreachable) {
 160       return true;
 161     }
 162   }
 163   return false;
 164 }
 165
 166 // core block optimizer routine
 167 static void optimizeBlock(Block* curr, Module* module, PassOptions& passOptions) {
 168   bool more = true;
 169   bool changed = false;
 170   while (more) {
 171     more = false;
 172     for (size_t i = 0; i < curr->list.size(); i++) {
 173       Block* child = curr->list[i]->dynCast<Block>();
 174       if (!child) {
 175         // if we have a child that is (drop (block ..)) then we can move the drop into the block, and remove br values. this allows more merging,
 176         auto* drop = curr->list[i]->dynCast<Drop>();
 177         if (drop) {
 178           child = drop->value->dynCast<Block>();
 179           if (child) {
 180             if (hasUnreachableChild(child)) {
 181               // don't move around unreachable code, as it can change types
 182               // dce should have been run anyhow
 183               continue;
 184             }
 185             if (child->name.is()) {
 186               Expression* expression = child;
 187               // check if it's ok to remove the value from all breaks to us
 188               ProblemFinder finder(passOptions);
 189               finder.origin = child->name;
 190               finder.walk(expression);
 191               if (finder.found()) {
 192                 child = nullptr;
 193               } else {
 194                 // fix up breaks
 195                 BreakValueDropper fixer(passOptions);
 196                 fixer.origin = child->name;
 197                 fixer.setModule(module);
 198                 fixer.walk(expression);
 199               }
 200             }
 201             if (child) {
 202               // we can do it!
 203               // reuse the drop
 204               drop->value = child->list.back();
 205               drop->finalize();
 206               child->list.back() = drop;
 207               child->finalize();
 208               curr->list[i] = child;
 209               more = true;
 210               changed = true;
 211             }
 212           }
 213         }
 214       }
 215       if (!child) continue;
 216       if (child->name.is()) continue; // named blocks can have breaks to them (and certainly do, if we ran RemoveUnusedNames and RemoveUnusedBrs)
 217       ExpressionList merged(module->allocator);
 218       for (size_t j = 0; j < i; j++) {
 219         merged.push_back(curr->list[j]);
 220       }
 221       for (auto item : child->list) {
 222         merged.push_back(item);
 223       }
 224       for (size_t j = i + 1; j < curr->list.size(); j++) {
 225         merged.push_back(curr->list[j]);
 226       }
 227       // if we merged a concrete element in the middle, drop it
 228       if (!merged.empty()) {
 229         auto* last = merged.back();
 230         for (auto*& item : merged) {
 231           if (item != last && isConcreteWasmType(item->type)) {
 232             Builder builder(*module);
 233             item = builder.makeDrop(item);
 234           }
 235         }
 236       }
 237       curr->list.swap(merged);
 238       more = true;
 239       changed = true;
 240       break;
 241     }
 242   }
 243   if (changed) curr->finalize(curr->type);
 244 }
 245
 246 void BreakValueDropper::visitBlock(Block* curr) {
 247   optimizeBlock(curr, getModule(), passOptions);
 248 }
 249
 250 struct MergeBlocks : public WalkerPass<PostWalker<MergeBlocks>> {
 251   bool isFunctionParallel() override { return true; }
 252
 253   Pass* create() override { return new MergeBlocks; }
 254
 255   void visitBlock(Block *curr) {
 256     optimizeBlock(curr, getModule(), getPassOptions());
 257   }
 258
 259   // given
 260   // (curr
 261   //  (block=child
 262   //   (..more..)
 263   //   (back)
 264   //  )
 265   //  (..other..children..)
 266   // )
 267   // if child is a block, we can move this around to
 268   // (block
 269   //  (..more..)
 270   //  (curr
 271   //   (back)
 272   //   (..other..children..)
 273   //  )
 274   // )
 275   // at which point the block is on the outside and potentially mergeable with an outer block
 276   Block* optimize(Expression* curr, Expression*& child, Block* outer = nullptr, Expression** dependency1 = nullptr, Expression** dependency2 = nullptr) {
 277     if (!child) return outer;
 278     if ((dependency1 && *dependency1) || (dependency2 && *dependency2)) {
 279       // there are dependencies, things we must be reordered through. make sure no problems there
 280       EffectAnalyzer childEffects(getPassOptions(), child);
 281       if (dependency1 && *dependency1 && EffectAnalyzer(getPassOptions(), *dependency1).invalidates(childEffects)) return outer;
 282       if (dependency2 && *dependency2 && EffectAnalyzer(getPassOptions(), *dependency2).invalidates(childEffects)) return outer;
 283     }
 284     if (auto* block = child->dynCast<Block>()) {
 285       if (!block->name.is() && block->list.size() >= 2) {
 286         // if we move around unreachable code, type changes could occur. avoid that, as
 287         // anyhow it means we should have run dce before getting here
 288         if (curr->type == none && hasUnreachableChild(block)) {
 289           // moving the block to the outside would replace a none with an unreachable
 290           return outer;
 291         }
 292         auto* back = block->list.back();
 293         if (back->type == unreachable) {
 294           // curr is not reachable, dce could remove it; don't try anything fancy
 295           // here
 296           return outer;
 297         }
 298         // we are going to replace the block with the final element, so they should
 299         // be identically typed
 300         if (block->type != back->type) {
 301           return outer;
 302         }
 303         child = back;
 304         if (outer == nullptr) {
 305           // reuse the block, move it out
 306           block->list.back() = curr;
 307           // we want the block outside to have the same type as curr had
 308           block->finalize(curr->type);
 309           replaceCurrent(block);
 310           return block;
 311         } else {
 312           // append to an existing outer block
 313           assert(outer->list.back() == curr);
 314           outer->list.pop_back();
 315           for (Index i = 0; i < block->list.size() - 1; i++) {
 316             outer->list.push_back(block->list[i]);
 317           }
 318           outer->list.push_back(curr);
 319         }
 320       }
 321     }
 322     return outer;
 323   }
 324
 325   void visitUnary(Unary* curr) {
 326     optimize(curr, curr->value);
 327   }
 328   void visitSetLocal(SetLocal* curr) {
 329     optimize(curr, curr->value);
 330   }
 331   void visitLoad(Load* curr) {
 332     optimize(curr, curr->ptr);
 333   }
 334   void visitReturn(Return* curr) {
 335     optimize(curr, curr->value);
 336   }
 337
 338   void visitBinary(Binary* curr) {
 339     optimize(curr, curr->right, optimize(curr, curr->left), &curr->left);
 340   }
 341   void visitStore(Store* curr) {
 342     optimize(curr, curr->value, optimize(curr, curr->ptr), &curr->ptr);
 343   }
 344   void visitAtomicRMW(AtomicRMW* curr) {
 345     optimize(curr, curr->value, optimize(curr, curr->ptr), &curr->ptr);
 346   }
 347   void optimizeTernary(Expression* curr,
 348                        Expression*& first, Expression*& second, Expression*& third) {
 349     // TODO: for now, just stop when we see any side effect. instead, we could
 350     //       check effects carefully for reordering
 351     Block* outer = nullptr;
 352     if (EffectAnalyzer(getPassOptions(), first).hasSideEffects()) return;
 353     outer = optimize(curr, first, outer);
 354     if (EffectAnalyzer(getPassOptions(), second).hasSideEffects()) return;
 355     outer = optimize(curr, second, outer);
 356     if (EffectAnalyzer(getPassOptions(), third).hasSideEffects()) return;
 357     optimize(curr, third, outer);
 358   }
 359   void visitAtomicCmpxchg(AtomicCmpxchg* curr) {
 360     optimizeTernary(curr, curr->ptr, curr->expected, curr->replacement);
 361   }
 362
 363   void visitSelect(Select* curr) {
 364     optimizeTernary(curr, curr->ifTrue, curr->ifFalse, curr->condition);
 365   }
 366
 367   void visitDrop(Drop* curr) {
 368     optimize(curr, curr->value);
 369   }
 370
 371   void visitBreak(Break* curr) {
 372     optimize(curr, curr->condition, optimize(curr, curr->value), &curr->value);
 373   }
 374   void visitSwitch(Switch* curr) {
 375     optimize(curr, curr->condition, optimize(curr, curr->value), &curr->value);
 376   }
 377
 378   template<typename T>
 379   void handleCall(T* curr) {
 380     Block* outer = nullptr;
 381     for (Index i = 0; i < curr->operands.size(); i++) {
 382       if (EffectAnalyzer(getPassOptions(), curr->operands[i]).hasSideEffects()) return;
 383       outer = optimize(curr, curr->operands[i], outer);
 384     }
 385     return;
 386   }
 387
 388   void visitCall(Call* curr) {
 389     handleCall(curr);
 390   }
 391
 392   void visitCallImport(CallImport* curr) {
 393     handleCall(curr);
 394   }
 395
 396   void visitCallIndirect(CallIndirect* curr) {
 397     Block* outer = nullptr;
 398     for (Index i = 0; i < curr->operands.size(); i++) {
 399       if (EffectAnalyzer(getPassOptions(), curr->operands[i]).hasSideEffects()) return;
 400       outer = optimize(curr, curr->operands[i], outer);
 401     }
 402     if (EffectAnalyzer(getPassOptions(), curr->target).hasSideEffects()) return;
 403     optimize(curr, curr->target, outer);
 404   }
 405 };
 406
 407 Pass *createMergeBlocksPass() {
 408   return new MergeBlocks();
 409 }
 410
 411 } // namespace wasm