/*
 * Copyright 2016 WebAssembly Community Group participants
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

//
// Removes obviously unneeded code
//

#include <ir/block-utils.h>
#include <ir/branch-hints.h>
#include <ir/drop.h>
#include <ir/effects.h>
#include <ir/eh-utils.h>
#include <ir/find_all.h>
#include <ir/intrinsics.h>
#include <ir/iteration.h>
#include <ir/literal-utils.h>
#include <ir/utils.h>
#include <pass.h>
#include <wasm-builder.h>
#include <wasm.h>

namespace wasm {

struct Vacuum : public WalkerPass<ExpressionStackWalker<Vacuum>> {
  bool isFunctionParallel() override { return true; }

  std::unique_ptr<Pass> create() override { return std::make_unique<Vacuum>(); }

  // Track whether we need to fix up pops at the end: adding a block in a Try
  // can require that.
  bool hasTry = false;
  bool addedBlocks = false;

  void doWalkFunction(Function* func) {
    walk(func->body);

    if (hasTry && addedBlocks) {
      EHUtils::handleBlockNestedPops(func, *getModule());
    }

    ReFinalize().walkFunctionInModule(func, getModule());
  }

  // Returns nullptr if curr is dead, curr if it must stay as is, or one of its
  // children if it can be replaced. Takes into account:
  //
  //  * The result may be used or unused.
  //  * The type may or may not matter.
  //
  // For example,
  //
  //  (drop
  //   (i32.eqz
  //    (call ..)))
  //
  // The drop means that the value is not used later. And while the call has
  // side effects, the i32.eqz does not. So when we are called on the i32.eqz,
  // and told the result does not matter, we can return the call. Note that in
  // this case the type does not matter either, as drop doesn't care, and anyhow
  // i32.eqz returns the same type as it receives. But for an expression that
  // returns a different type, if the type matters then we cannot replace it.
  Expression* optimize(Expression* curr, bool resultUsed, bool typeMatters) {
    auto type = curr->type;
    // If the type is none, then we can never replace it with another type.
    if (type == Type::none) {
      typeMatters = true;
    }
    // An unreachable node must not be changed. DCE will remove those.
    if (type == Type::unreachable) {
      return curr;
    }
    // resultUsed only makes sense when the type is concrete
    assert(!resultUsed || curr->type != Type::none);
    // If we actually need the result, then we must not change anything.
    // TODO: maybe there is something clever though?
    if (resultUsed) {
      return curr;
    }
    // We iterate on possible replacements.
    auto* prev = curr;
    while (1) {
      // If a replacement changes the type, and the type matters, return the
      // previous one and stop.
      if (typeMatters && curr->type != type) {
        return prev;
      }
      prev = curr;
      // Some instructions have special handling in visit*, and we should do
      // nothing for them here.
      if (curr->is<Drop>() || curr->is<Block>() || curr->is<If>() ||
          curr->is<Loop>() || curr->is<Try>() || curr->is<TryTable>()) {
        return curr;
      }
      // Check if this expression itself must be kept.
      if (mustKeepUnusedParent(curr)) {
        return curr;
      }
      // The result isn't used, and this has no side effects itself, so we can
      // get rid of it. However, the children may have side effects.
      SmallVector<Expression*, 1> childrenWithEffects;
      for (auto* child : ChildIterator(curr)) {
        if (EffectAnalyzer(getPassOptions(), *getModule(), child)
              .hasUnremovableSideEffects()) {
          childrenWithEffects.push_back(child);
        }
      }
      if (childrenWithEffects.empty()) {
        return nullptr;
      }
      if (childrenWithEffects.size() == 1) {
        // We know the result isn't used, and curr has no side effects, so we
        // can skip curr and keep looking into the child.
        curr = childrenWithEffects[0];
        continue;
      }
      // The result is not used, but multiple children have side effects, so we
      // need to keep them around. We must also return something of the proper
      // type - if we can do that, replace everything with the children + a
      // dummy value of the proper type.
      if (curr->type.isDefaultable()) {
        auto* dummy = Builder(*getModule())
                        .makeConstantExpression(Literal::makeZeros(curr->type));
        addedBlocks = true;
        return getDroppedChildrenAndAppend(
          curr, *getModule(), getPassOptions(), dummy);
      }
      // Otherwise, give up.
      return curr;
    }
  }

  // Check if a parent expression must be kept around, given the knowledge that
  // its result is unused (dropped). This is basically just a call to
  // ShallowEffectAnalyzer to see if we can remove it, except that given the
  // result is unused, the relevant hint may help us. (This just checks the
  // parent itself: it may have children that the caller must check and keep
  // around if so.)
  bool mustKeepUnusedParent(Expression* curr) {
    if (auto* call = curr->dynCast<Call>()) {
      // If |curr| is marked as removable if unused, then it is removable
      // without even checking effects.
      if (Intrinsics(*getModule())
            .getCallAnnotations(call, getFunction())
            .removableIfUnused) {
        return false;
      }
    }
    ShallowEffectAnalyzer self(getPassOptions(), *getModule(), curr);
    return self.hasUnremovableSideEffects();
  }

  void visitBlock(Block* curr) {
    auto& list = curr->list;

    // If traps are assumed to never happen, we can remove code on paths that
    // must reach a trap:
    //
    //  (block
    //    (i32.store ..)
    //    (br_if ..)      ;; execution branches here, so the first store remains
    //    (i32.store ..)  ;; this store can be removed
    //    (unreachable);
    //  )
    //
    // For this to be useful we need to have at least 2 elements: something to
    // remove, and an unreachable.
    if (getPassOptions().trapsNeverHappen && list.size() >= 2) {
      // Go backwards. When we find a trap, mark the things before it as heading
      // to a trap.
      auto headingToTrap = false;
      for (int i = list.size() - 1; i >= 0; i--) {
        if (list[i]->is<Unreachable>()) {
          headingToTrap = true;
          continue;
        }

        if (!headingToTrap) {
          continue;
        }

        // Check if we may no longer be heading to a trap. We can only optimize
        // if the trap will actually be reached. Two situations can prevent that
        // here: Control flow might branch away, or we might hang (which can
        // happen in a call or a loop).
        //
        // We also cannot remove a pop as it is necessary for structural
        // reasons.
        EffectAnalyzer effects(getPassOptions(), *getModule(), list[i]);
        if (effects.transfersControlFlow() || effects.calls ||
            effects.mayNotReturn || effects.danglingPop) {
          headingToTrap = false;
          continue;
        }

        // This code can be removed! Turn it into a nop, and leave it for the
        // code lower down to finish cleaning up.
        ExpressionManipulator::nop(list[i]);
      }
    }

    // compress out nops and other dead code
    int skip = 0;
    size_t size = list.size();
    for (size_t z = 0; z < size; z++) {
      auto* child = list[z];
      // The last element may be used.
      bool used =
        z == size - 1 && curr->type.isConcrete() &&
        ExpressionAnalyzer::isResultUsed(expressionStack, getFunction());
      auto* optimized = optimize(child, used, true);
      if (!optimized) {
        auto childType = child->type;
        if (childType.isConcrete()) {
          if (LiteralUtils::canMakeZero(childType)) {
            // We can't just skip a final concrete element, even if it isn't
            // used. Instead, replace it with something that's easy to optimize
            // out (for example, code-folding can merge out identical zeros at
            // the end of if arms).
            optimized = LiteralUtils::makeZero(childType, *getModule());
          } else {
            // Don't optimize it out.
            optimized = child;
          }
        } else if (childType == Type::unreachable) {
          // Don't try to optimize out an unreachable child (dce can do that
          // properly).
          optimized = child;
        }
      }
      if (!optimized) {
        skip++;
      } else {
        if (optimized != child) {
          list[z] = optimized;
        }
        if (skip > 0) {
          list[z - skip] = list[z];
          list[z] = nullptr;
        }
        // if this is unreachable, the rest is dead code
        if (list[z - skip]->type == Type::unreachable && z < size - 1) {
          list.resize(z - skip + 1);
          skip = 0; // nothing more to do on the list
          break;
        }
      }
    }
    if (skip > 0) {
      list.resize(size - skip);
    }
    // the block may now be a trivial one that we can get rid of and just leave
    // its contents
    replaceCurrent(BlockUtils::simplifyToContents(curr, this));
  }

  void visitIf(If* curr) {
    // if the condition is a constant, just apply it
    // we can just return the ifTrue or ifFalse.
    if (auto* value = curr->condition->dynCast<Const>()) {
      Expression* child;
      if (value->value.getInteger()) {
        child = curr->ifTrue;
      } else {
        if (curr->ifFalse) {
          child = curr->ifFalse;
        } else {
          ExpressionManipulator::nop(curr);
          return;
        }
      }
      replaceCurrent(child);
      return;
    }
    // if the condition is unreachable, just return it
    if (curr->condition->type == Type::unreachable) {
      replaceCurrent(curr->condition);
      return;
    }
    // from here on, we can assume the condition executed

    // In trapsNeverHappen mode, a definitely-trapping arm can be assumed to not
    // happen. Such conditional code can be assumed to never be reached in this
    // mode.
    //
    // Ignore the case of an unreachable if, such as having both arms be
    // unreachable. In that case we'd need to fix up the IR to avoid changing
    // the type; leave that for DCE to simplify first. After checking that
    // curr->type != unreachable, we can assume that only one of the arms is
    // unreachable (at most).
    if (getPassOptions().trapsNeverHappen && curr->type != Type::unreachable) {
      auto optimizeArm = [&](Expression* arm, Expression* otherArm) {
        if (!arm->is<Unreachable>()) {
          return false;
        }
        Builder builder(*getModule());
        Expression* rep = builder.makeDrop(curr->condition);
        if (otherArm) {
          rep = builder.makeSequence(rep, otherArm);
        }
        replaceCurrent(rep);
        return true;
      };

      // As mentioned above, do not try to optimize both arms; leave that case
      // for DCE.
      if (optimizeArm(curr->ifTrue, curr->ifFalse) ||
          (curr->ifFalse && optimizeArm(curr->ifFalse, curr->ifTrue))) {
        return;
      }
    }

    if (curr->ifFalse) {
      if (curr->ifFalse->is<Nop>()) {
        curr->ifFalse = nullptr;
      } else if (curr->ifTrue->is<Nop>()) {
        curr->ifTrue = curr->ifFalse;
        curr->ifFalse = nullptr;
        curr->condition =
          Builder(*getModule()).makeUnary(EqZInt32, curr->condition);
        BranchHints::flip(curr, getFunction());
      } else if (curr->ifTrue->is<Drop>() && curr->ifFalse->is<Drop>()) {
        // instead of dropping both sides, drop the if, if they are the same
        // type
        auto* left = curr->ifTrue->cast<Drop>()->value;
        auto* right = curr->ifFalse->cast<Drop>()->value;
        if (left->type == right->type) {
          curr->ifTrue = left;
          curr->ifFalse = right;
          curr->finalize();
          replaceCurrent(Builder(*getModule()).makeDrop(curr));
        }
      }
    } else {
      // This is an if without an else. If the body is empty, we do not need it.
      if (curr->ifTrue->is<Nop>()) {
        replaceCurrent(Builder(*getModule()).makeDrop(curr->condition));
      }
    }
  }

  void visitLoop(Loop* curr) {
    if (curr->body->is<Nop>()) {
      ExpressionManipulator::nop(curr);
    }
  }

  void visitDrop(Drop* curr) {
    // optimize the dropped value, maybe leaving nothing
    curr->value = optimize(curr->value, false, false);
    if (curr->value == nullptr) {
      ExpressionManipulator::nop(curr);
      return;
    }
    // a drop of a tee is a set
    if (auto* set = curr->value->dynCast<LocalSet>()) {
      assert(set->isTee());
      set->makeSet();
      replaceCurrent(set);
      return;
    }

    // If the value has no side effects, or it has side effects we can remove,
    // do so. This basically means that if noTrapsHappen is set then we can
    // use that assumption (that no trap actually happens at runtime) and remove
    // a trapping value.
    //
    // TODO: A complete CFG analysis for noTrapsHappen mode, removing all code
    //       that definitely reaches a trap, *even if* it has side effects.
    //
    // Note that we check the type here to avoid removing unreachable code - we
    // leave that for DCE.
    if (curr->type == Type::none &&
        !EffectAnalyzer(getPassOptions(), *getModule(), curr)
           .hasUnremovableSideEffects()) {
      ExpressionManipulator::nop(curr);
      return;
    }

    // if we are dropping a block's return value, we might be able to remove it
    // entirely
    if (auto* block = curr->value->dynCast<Block>()) {
      auto* last = block->list.back();
      // note that the last element may be concrete but not the block, if the
      // block has an unreachable element in the middle, making the block
      // unreachable despite later elements and in particular the last
      if (last->type.isConcrete() && block->type == last->type) {
        last = optimize(last, false, false);
        if (!last) {
          // we may be able to remove this, if there are no brs
          bool canPop = true;
          if (block->name.is()) {
            BranchUtils::BranchSeeker seeker(block->name);
            Expression* temp = block;
            seeker.walk(temp);
            if (seeker.found && Type::hasLeastUpperBound(seeker.types)) {
              canPop = false;
            }
          }
          if (canPop) {
            block->list.back() = last;
            block->list.pop_back();
            block->type = Type::none;
            // we don't need the drop anymore, let's see what we have left in
            // the block
            if (block->list.size() > 1) {
              replaceCurrent(block);
            } else if (block->list.size() == 1) {
              replaceCurrent(block->list[0]);
            } else {
              ExpressionManipulator::nop(curr);
            }
            return;
          }
        }
      }
    }
    // sink a drop into an arm of an if-else if the other arm ends in an
    // unreachable, as it if is a branch, this can make that branch optimizable
    // and more vacuuming possible
    auto* iff = curr->value->dynCast<If>();
    if (iff && iff->ifFalse && iff->type.isConcrete()) {
      // reuse the drop in both cases
      if (iff->ifTrue->type == Type::unreachable &&
          iff->ifFalse->type.isConcrete()) {
        curr->value = iff->ifFalse;
        iff->ifFalse = curr;
        iff->type = Type::none;
        replaceCurrent(iff);
      } else if (iff->ifFalse->type == Type::unreachable &&
                 iff->ifTrue->type.isConcrete()) {
        curr->value = iff->ifTrue;
        iff->ifTrue = curr;
        iff->type = Type::none;
        replaceCurrent(iff);
      }
    }
  }

  void visitTry(Try* curr) {
    hasTry = true;

    // If try's body does not throw, the whole try-catch can be replaced with
    // the try's body.
    if (!EffectAnalyzer(getPassOptions(), *getModule(), curr->body).throws()) {
      replaceCurrent(curr->body);
      return;
    }

    // The try's body does throw. However, throwing may be the only thing it
    // does, and if the try has a catch-all, then the entire try including
    // children may have no effects. Note that this situation can only happen
    // if we do have a catch-all, so avoid wasted work by checking that first.
    // Also, we can't do this if a result is returned, so check the type.
    if (curr->type == Type::none && curr->hasCatchAll() &&
        !EffectAnalyzer(getPassOptions(), *getModule(), curr)
           .hasUnremovableSideEffects()) {
      ExpressionManipulator::nop(curr);
    }
  }

  void visitTryTable(TryTable* curr) {
    // If try_table's body does not throw, the whole try_table can be replaced
    // with the try_table's body.
    if (!EffectAnalyzer(getPassOptions(), *getModule(), curr->body).throws()) {
      replaceCurrent(curr->body);
      return;
    }
  }

  void visitFunction(Function* curr) {
    auto* optimized =
      optimize(curr->body, curr->getResults() != Type::none, true);
    if (optimized) {
      curr->body = optimized;
    } else {
      ExpressionManipulator::nop(curr->body);
    }
    if (curr->getResults() == Type::none) {
      EffectAnalyzer effects(getPassOptions(), *getModule(), curr);
      if (!effects.hasUnremovableSideEffects()) {
        // We can remove these contents. However, there is one situation we want
        // to handle here: in trapsNeverHappen mode, we can remove traps, but
        // we don't want to remove an actual Unreachable - replacing an
        // Unreachable with a Nop is valid, but does not propagate to callers in
        // other passes.
        //
        // To avoid that situation, after finding we can remove the code, we
        // also require that no Unreachable exists. Note that this is unoptimal:
        // there may be a complex bundle of code whose only effect is to
        // potentially trap, and it happens to contain an Unreachable inside
        // somewhere, then that would prevent us from nopping the entire thing.
        // But we leave untangling such code for other passes.
        //
        // This is also unoptimal as it is a heuristic: some toolchain might
        // emit 0 / 0 for a logical trap, rather than an Unreachable. We would
        // remove that 0 / 0 if we saw it, and the trap would not propagate.
        // (But other passes would handle it, if they saw it first.)
        if (effects.trap) {
          // The code is removable, so the trap is the only effect it has, and
          // we are considering removing it because TNH is enabled.
          assert(getPassOptions().trapsNeverHappen);
          if (!FindAll<Unreachable>(curr->body).list.empty()) {
            return;
          }
        }
        // Either trapsNeverHappen and there is no Unreachable (so we are only
        // removing implicit traps, which is fine), or traps may happen in terms
        // of the flag, but not in this actual code. Either way, we can remove
        // all of this.
        ExpressionManipulator::nop(curr->body);
      }
    }
  }
};

Pass* createVacuumPass() { return new Vacuum(); }

} // namespace wasm