source/opt/loop_unswitch_pass.cpp

// Copyright (c) 2018 Google LLC.
//
// 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.

#include "source/opt/loop_unswitch_pass.h"

#include <functional>
#include <list>
#include <memory>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#include "source/opt/basic_block.h"
#include "source/opt/dominator_tree.h"
#include "source/opt/fold.h"
#include "source/opt/function.h"
#include "source/opt/instruction.h"
#include "source/opt/ir_builder.h"
#include "source/opt/ir_context.h"
#include "source/opt/loop_descriptor.h"

#include "source/opt/loop_utils.h"

namespace spvtools {
namespace opt {
namespace {

static const uint32_t kTypePointerStorageClassInIdx = 0;
static const uint32_t kBranchCondTrueLabIdInIdx = 1;
static const uint32_t kBranchCondFalseLabIdInIdx = 2;

}  // anonymous namespace

namespace {

// This class handle the unswitch procedure for a given loop.
// The unswitch will not happen if:
//  - The loop has any instruction that will prevent it;
//  - The loop invariant condition is not uniform.
class LoopUnswitch {
 public:
  LoopUnswitch(IRContext* context, Function* function, Loop* loop,
               LoopDescriptor* loop_desc)
      : function_(function),
        loop_(loop),
        loop_desc_(*loop_desc),
        context_(context),
        switch_block_(nullptr) {}

  // Returns true if the loop can be unswitched.
  // Can be unswitch if:
  //  - The loop has no instructions that prevents it (such as barrier);
  //  - The loop has one conditional branch or switch that do not depends on the
  //  loop;
  //  - The loop invariant condition is uniform;
  bool CanUnswitchLoop() {
    if (switch_block_) return true;
    if (loop_->IsSafeToClone()) return false;

    CFG& cfg = *context_->cfg();

    for (uint32_t bb_id : loop_->GetBlocks()) {
      BasicBlock* bb = cfg.block(bb_id);
      if (bb->terminator()->IsBranch() &&
          bb->terminator()->opcode() != SpvOpBranch) {
        if (IsConditionLoopInvariant(bb->terminator())) {
          switch_block_ = bb;
          break;
        }
      }
    }

    return switch_block_;
  }

  // Return the iterator to the basic block |bb|.
  Function::iterator FindBasicBlockPosition(BasicBlock* bb_to_find) {
    Function::iterator it = function_->FindBlock(bb_to_find->id());
    assert(it != function_->end() && "Basic Block not found");
    return it;
  }

  // Creates a new basic block and insert it into the function |fn| at the
  // position |ip|. This function preserves the def/use and instr to block
  // managers.
  BasicBlock* CreateBasicBlock(Function::iterator ip) {
    analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr();

    // TODO(1841): Handle id overflow.
    BasicBlock* bb = &*ip.InsertBefore(std::unique_ptr<BasicBlock>(
        new BasicBlock(std::unique_ptr<Instruction>(new Instruction(
            context_, SpvOpLabel, 0, context_->TakeNextId(), {})))));
    bb->SetParent(function_);
    def_use_mgr->AnalyzeInstDef(bb->GetLabelInst());
    context_->set_instr_block(bb->GetLabelInst(), bb);

    return bb;
  }

  // Unswitches |loop_|.
  void PerformUnswitch() {
    assert(CanUnswitchLoop() &&
           "Cannot unswitch if there is not constant condition");
    assert(loop_->GetPreHeaderBlock() && "This loop has no pre-header block");
    assert(loop_->IsLCSSA() && "This loop is not in LCSSA form");

    CFG& cfg = *context_->cfg();
    DominatorTree* dom_tree =
        &context_->GetDominatorAnalysis(function_)->GetDomTree();
    analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr();
    LoopUtils loop_utils(context_, loop_);

    //////////////////////////////////////////////////////////////////////////////
    // Step 1: Create the if merge block for structured modules.
    //    To do so, the |loop_| merge block will become the if's one and we
    //    create a merge for the loop. This will limit the amount of duplicated
    //    code the structured control flow imposes.
    //    For non structured program, the new loop will be connected to
    //    the old loop's exit blocks.
    //////////////////////////////////////////////////////////////////////////////

    // Get the merge block if it exists.
    BasicBlock* if_merge_block = loop_->GetMergeBlock();
    // The merge block is only created if the loop has a unique exit block. We
    // have this guarantee for structured loops, for compute loop it will
    // trivially help maintain both a structured-like form and LCSAA.
    BasicBlock* loop_merge_block =
        if_merge_block
            ? CreateBasicBlock(FindBasicBlockPosition(if_merge_block))
            : nullptr;
    if (loop_merge_block) {
      // Add the instruction and update managers.
      InstructionBuilder builder(
          context_, loop_merge_block,
          IRContext::kAnalysisDefUse | IRContext::kAnalysisInstrToBlockMapping);
      builder.AddBranch(if_merge_block->id());
      builder.SetInsertPoint(&*loop_merge_block->begin());
      cfg.RegisterBlock(loop_merge_block);
      def_use_mgr->AnalyzeInstDef(loop_merge_block->GetLabelInst());
      // Update CFG.
      if_merge_block->ForEachPhiInst(
          [loop_merge_block, &builder, this](Instruction* phi) {
            Instruction* cloned = phi->Clone(context_);
            builder.AddInstruction(std::unique_ptr<Instruction>(cloned));
            phi->SetInOperand(0, {cloned->result_id()});
            phi->SetInOperand(1, {loop_merge_block->id()});
            for (uint32_t j = phi->NumInOperands() - 1; j > 1; j--)
              phi->RemoveInOperand(j);
          });
      // Copy the predecessor list (will get invalidated otherwise).
      std::vector<uint32_t> preds = cfg.preds(if_merge_block->id());
      for (uint32_t pid : preds) {
        if (pid == loop_merge_block->id()) continue;
        BasicBlock* p_bb = cfg.block(pid);
        p_bb->ForEachSuccessorLabel(
            [if_merge_block, loop_merge_block](uint32_t* id) {
              if (*id == if_merge_block->id()) *id = loop_merge_block->id();
            });
        cfg.AddEdge(pid, loop_merge_block->id());
      }
      cfg.RemoveNonExistingEdges(if_merge_block->id());
      // Update loop descriptor.
      if (Loop* ploop = loop_->GetParent()) {
        ploop->AddBasicBlock(loop_merge_block);
        loop_desc_.SetBasicBlockToLoop(loop_merge_block->id(), ploop);
      }

      // Update the dominator tree.
      DominatorTreeNode* loop_merge_dtn =
          dom_tree->GetOrInsertNode(loop_merge_block);
      DominatorTreeNode* if_merge_block_dtn =
          dom_tree->GetOrInsertNode(if_merge_block);
      loop_merge_dtn->parent_ = if_merge_block_dtn->parent_;
      loop_merge_dtn->children_.push_back(if_merge_block_dtn);
      loop_merge_dtn->parent_->children_.push_back(loop_merge_dtn);
      if_merge_block_dtn->parent_->children_.erase(std::find(
          if_merge_block_dtn->parent_->children_.begin(),
          if_merge_block_dtn->parent_->children_.end(), if_merge_block_dtn));

      loop_->SetMergeBlock(loop_merge_block);
    }

    ////////////////////////////////////////////////////////////////////////////
    // Step 2: Build a new preheader for |loop_|, use the old one
    //         for the constant branch.
    ////////////////////////////////////////////////////////////////////////////

    BasicBlock* if_block = loop_->GetPreHeaderBlock();
    // If this preheader is the parent loop header,
    // we need to create a dedicated block for the if.
    BasicBlock* loop_pre_header =
        CreateBasicBlock(++FindBasicBlockPosition(if_block));
    InstructionBuilder(
        context_, loop_pre_header,
        IRContext::kAnalysisDefUse | IRContext::kAnalysisInstrToBlockMapping)
        .AddBranch(loop_->GetHeaderBlock()->id());

    if_block->tail()->SetInOperand(0, {loop_pre_header->id()});

    // Update loop descriptor.
    if (Loop* ploop = loop_desc_[if_block]) {
      ploop->AddBasicBlock(loop_pre_header);
      loop_desc_.SetBasicBlockToLoop(loop_pre_header->id(), ploop);
    }

    // Update the CFG.
    cfg.RegisterBlock(loop_pre_header);
    def_use_mgr->AnalyzeInstDef(loop_pre_header->GetLabelInst());
    cfg.AddEdge(if_block->id(), loop_pre_header->id());
    cfg.RemoveNonExistingEdges(loop_->GetHeaderBlock()->id());

    loop_->GetHeaderBlock()->ForEachPhiInst(
        [loop_pre_header, if_block](Instruction* phi) {
          phi->ForEachInId([loop_pre_header, if_block](uint32_t* id) {
            if (*id == if_block->id()) {
              *id = loop_pre_header->id();
            }
          });
        });
    loop_->SetPreHeaderBlock(loop_pre_header);

    // Update the dominator tree.
    DominatorTreeNode* loop_pre_header_dtn =
        dom_tree->GetOrInsertNode(loop_pre_header);
    DominatorTreeNode* if_block_dtn = dom_tree->GetTreeNode(if_block);
    loop_pre_header_dtn->parent_ = if_block_dtn;
    assert(
        if_block_dtn->children_.size() == 1 &&
        "A loop preheader should only have the header block as a child in the "
        "dominator tree");
    loop_pre_header_dtn->children_.push_back(if_block_dtn->children_[0]);
    if_block_dtn->children_.clear();
    if_block_dtn->children_.push_back(loop_pre_header_dtn);

    // Make domination queries valid.
    dom_tree->ResetDFNumbering();

    // Compute an ordered list of basic block to clone: loop blocks + pre-header
    // + merge block.
    loop_->ComputeLoopStructuredOrder(&ordered_loop_blocks_, true, true);

    /////////////////////////////
    // Do the actual unswitch: //
    //   - Clone the loop      //
    //   - Connect exits       //
    //   - Specialize the loop //
    /////////////////////////////

    Instruction* iv_condition = &*switch_block_->tail();
    SpvOp iv_opcode = iv_condition->opcode();
    Instruction* condition =
        def_use_mgr->GetDef(iv_condition->GetOperand(0).words[0]);

    analysis::ConstantManager* cst_mgr = context_->get_constant_mgr();
    const analysis::Type* cond_type =
        context_->get_type_mgr()->GetType(condition->type_id());

    // Build the list of value for which we need to clone and specialize the
    // loop.
    std::vector<std::pair<Instruction*, BasicBlock*>> constant_branch;
    // Special case for the original loop
    Instruction* original_loop_constant_value;
    BasicBlock* original_loop_target;
    if (iv_opcode == SpvOpBranchConditional) {
      constant_branch.emplace_back(
          cst_mgr->GetDefiningInstruction(cst_mgr->GetConstant(cond_type, {0})),
          nullptr);
      original_loop_constant_value =
          cst_mgr->GetDefiningInstruction(cst_mgr->GetConstant(cond_type, {1}));
    } else {
      // We are looking to take the default branch, so we can't provide a
      // specific value.
      original_loop_constant_value = nullptr;
      for (uint32_t i = 2; i < iv_condition->NumInOperands(); i += 2) {
        constant_branch.emplace_back(
            cst_mgr->GetDefiningInstruction(cst_mgr->GetConstant(
                cond_type, iv_condition->GetInOperand(i).words)),
            nullptr);
      }
    }

    // Get the loop landing pads.
    std::unordered_set<uint32_t> if_merging_blocks;
    std::function<bool(uint32_t)> is_from_original_loop;
    if (loop_->GetHeaderBlock()->GetLoopMergeInst()) {
      if_merging_blocks.insert(if_merge_block->id());
      is_from_original_loop = [this](uint32_t id) {
        return loop_->IsInsideLoop(id) || loop_->GetMergeBlock()->id() == id;
      };
    } else {
      loop_->GetExitBlocks(&if_merging_blocks);
      is_from_original_loop = [this](uint32_t id) {
        return loop_->IsInsideLoop(id);
      };
    }

    for (auto& specialisation_pair : constant_branch) {
      Instruction* specialisation_value = specialisation_pair.first;
      //////////////////////////////////////////////////////////
      // Step 3: Duplicate |loop_|.
      //////////////////////////////////////////////////////////
      LoopUtils::LoopCloningResult clone_result;

      Loop* cloned_loop =
          loop_utils.CloneLoop(&clone_result, ordered_loop_blocks_);
      specialisation_pair.second = cloned_loop->GetPreHeaderBlock();

      ////////////////////////////////////
      // Step 4: Specialize the loop.   //
      ////////////////////////////////////

      {
        std::unordered_set<uint32_t> dead_blocks;
        std::unordered_set<uint32_t> unreachable_merges;
        SimplifyLoop(
            make_range(
                UptrVectorIterator<BasicBlock>(&clone_result.cloned_bb_,
                                               clone_result.cloned_bb_.begin()),
                UptrVectorIterator<BasicBlock>(&clone_result.cloned_bb_,
                                               clone_result.cloned_bb_.end())),
            cloned_loop, condition, specialisation_value, &dead_blocks);

        // We tagged dead blocks, create the loop before we invalidate any basic
        // block.
        cloned_loop =
            CleanLoopNest(cloned_loop, dead_blocks, &unreachable_merges);
        CleanUpCFG(
            UptrVectorIterator<BasicBlock>(&clone_result.cloned_bb_,
                                           clone_result.cloned_bb_.begin()),
            dead_blocks, unreachable_merges);

        ///////////////////////////////////////////////////////////
        // Step 5: Connect convergent edges to the landing pads. //
        ///////////////////////////////////////////////////////////

        for (uint32_t merge_bb_id : if_merging_blocks) {
          BasicBlock* merge = context_->cfg()->block(merge_bb_id);
          // We are in LCSSA so we only care about phi instructions.
          merge->ForEachPhiInst([is_from_original_loop, &dead_blocks,
                                 &clone_result](Instruction* phi) {
            uint32_t num_in_operands = phi->NumInOperands();
            for (uint32_t i = 0; i < num_in_operands; i += 2) {
              uint32_t pred = phi->GetSingleWordInOperand(i + 1);
              if (is_from_original_loop(pred)) {
                pred = clone_result.value_map_.at(pred);
                if (!dead_blocks.count(pred)) {
                  uint32_t incoming_value_id = phi->GetSingleWordInOperand(i);
                  // Not all the incoming value are coming from the loop.
                  ValueMapTy::iterator new_value =
                      clone_result.value_map_.find(incoming_value_id);
                  if (new_value != clone_result.value_map_.end()) {
                    incoming_value_id = new_value->second;
                  }
                  phi->AddOperand({SPV_OPERAND_TYPE_ID, {incoming_value_id}});
                  phi->AddOperand({SPV_OPERAND_TYPE_ID, {pred}});
                }
              }
            }
          });
        }
      }
      function_->AddBasicBlocks(clone_result.cloned_bb_.begin(),
                                clone_result.cloned_bb_.end(),
                                ++FindBasicBlockPosition(if_block));
    }

    // Same as above but specialize the existing loop
    {
      std::unordered_set<uint32_t> dead_blocks;
      std::unordered_set<uint32_t> unreachable_merges;
      SimplifyLoop(make_range(function_->begin(), function_->end()), loop_,
                   condition, original_loop_constant_value, &dead_blocks);

      for (uint32_t merge_bb_id : if_merging_blocks) {
        BasicBlock* merge = context_->cfg()->block(merge_bb_id);
        // LCSSA, so we only care about phi instructions.
        // If we the phi is reduced to a single incoming branch, do not
        // propagate it to preserve LCSSA.
        PatchPhis(merge, dead_blocks, true);
      }
      if (if_merge_block) {
        bool has_live_pred = false;
        for (uint32_t pid : cfg.preds(if_merge_block->id())) {
          if (!dead_blocks.count(pid)) {
            has_live_pred = true;
            break;
          }
        }
        if (!has_live_pred) unreachable_merges.insert(if_merge_block->id());
      }
      original_loop_target = loop_->GetPreHeaderBlock();
      // We tagged dead blocks, prune the loop descriptor from any dead loops.
      // After this call, |loop_| can be nullptr (i.e. the unswitch killed this
      // loop).
      loop_ = CleanLoopNest(loop_, dead_blocks, &unreachable_merges);

      CleanUpCFG(function_->begin(), dead_blocks, unreachable_merges);
    }

    /////////////////////////////////////
    // Finally: connect the new loops. //
    /////////////////////////////////////

    // Delete the old jump
    context_->KillInst(&*if_block->tail());
    InstructionBuilder builder(context_, if_block);
    if (iv_opcode == SpvOpBranchConditional) {
      assert(constant_branch.size() == 1);
      builder.AddConditionalBranch(
          condition->result_id(), original_loop_target->id(),
          constant_branch[0].second->id(),
          if_merge_block ? if_merge_block->id() : kInvalidId);
    } else {
      std::vector<std::pair<Operand::OperandData, uint32_t>> targets;
      for (auto& t : constant_branch) {
        targets.emplace_back(t.first->GetInOperand(0).words, t.second->id());
      }

      builder.AddSwitch(condition->result_id(), original_loop_target->id(),
                        targets,
                        if_merge_block ? if_merge_block->id() : kInvalidId);
    }

    switch_block_ = nullptr;
    ordered_loop_blocks_.clear();

    context_->InvalidateAnalysesExceptFor(
        IRContext::Analysis::kAnalysisLoopAnalysis);
  }

  // Returns true if the unswitch killed the original |loop_|.
  bool WasLoopKilled() const { return loop_ == nullptr; }

 private:
  using ValueMapTy = std::unordered_map<uint32_t, uint32_t>;
  using BlockMapTy = std::unordered_map<uint32_t, BasicBlock*>;

  Function* function_;
  Loop* loop_;
  LoopDescriptor& loop_desc_;
  IRContext* context_;

  BasicBlock* switch_block_;
  // Map between instructions and if they are dynamically uniform.
  std::unordered_map<uint32_t, bool> dynamically_uniform_;
  // The loop basic blocks in structured order.
  std::vector<BasicBlock*> ordered_loop_blocks_;

  // Returns the next usable id for the context.
  uint32_t TakeNextId() {
    // TODO(1841): Handle id overflow.
    return context_->TakeNextId();
  }

  // Patches |bb|'s phi instruction by removing incoming value from unexisting
  // or tagged as dead branches.
  void PatchPhis(BasicBlock* bb,
                 const std::unordered_set<uint32_t>& dead_blocks,
                 bool preserve_phi) {
    CFG& cfg = *context_->cfg();

    std::vector<Instruction*> phi_to_kill;
    const std::vector<uint32_t>& bb_preds = cfg.preds(bb->id());
    auto is_branch_dead = [&bb_preds, &dead_blocks](uint32_t id) {
      return dead_blocks.count(id) ||
             std::find(bb_preds.begin(), bb_preds.end(), id) == bb_preds.end();
    };
    bb->ForEachPhiInst(
        [&phi_to_kill, &is_branch_dead, preserve_phi, this](Instruction* insn) {
          uint32_t i = 0;
          while (i < insn->NumInOperands()) {
            uint32_t incoming_id = insn->GetSingleWordInOperand(i + 1);
            if (is_branch_dead(incoming_id)) {
              // Remove the incoming block id operand.
              insn->RemoveInOperand(i + 1);
              // Remove the definition id operand.
              insn->RemoveInOperand(i);
              continue;
            }
            i += 2;
          }
          // If there is only 1 remaining edge, propagate the value and
          // kill the instruction.
          if (insn->NumInOperands() == 2 && !preserve_phi) {
            phi_to_kill.push_back(insn);
            context_->ReplaceAllUsesWith(insn->result_id(),
                                         insn->GetSingleWordInOperand(0));
          }
        });
    for (Instruction* insn : phi_to_kill) {
      context_->KillInst(insn);
    }
  }

  // Removes any block that is tagged as dead, if the block is in
  // |unreachable_merges| then all block's instructions are replaced by a
  // OpUnreachable.
  void CleanUpCFG(UptrVectorIterator<BasicBlock> bb_it,
                  const std::unordered_set<uint32_t>& dead_blocks,
                  const std::unordered_set<uint32_t>& unreachable_merges) {
    CFG& cfg = *context_->cfg();

    while (bb_it != bb_it.End()) {
      BasicBlock& bb = *bb_it;

      if (unreachable_merges.count(bb.id())) {
        if (bb.begin() != bb.tail() ||
            bb.terminator()->opcode() != SpvOpUnreachable) {
          // Make unreachable, but leave the label.
          bb.KillAllInsts(false);
          InstructionBuilder(context_, &bb).AddUnreachable();
          cfg.RemoveNonExistingEdges(bb.id());
        }
        ++bb_it;
      } else if (dead_blocks.count(bb.id())) {
        cfg.ForgetBlock(&bb);
        // Kill this block.
        bb.KillAllInsts(true);
        bb_it = bb_it.Erase();
      } else {
        cfg.RemoveNonExistingEdges(bb.id());
        ++bb_it;
      }
    }
  }

  // Return true if |c_inst| is a Boolean constant and set |cond_val| with the
  // value that |c_inst|
  bool GetConstCondition(const Instruction* c_inst, bool* cond_val) {
    bool cond_is_const;
    switch (c_inst->opcode()) {
      case SpvOpConstantFalse: {
        *cond_val = false;
        cond_is_const = true;
      } break;
      case SpvOpConstantTrue: {
        *cond_val = true;
        cond_is_const = true;
      } break;
      default: { cond_is_const = false; } break;
    }
    return cond_is_const;
  }

  // Simplifies |loop| assuming the instruction |to_version_insn| takes the
  // value |cst_value|. |block_range| is an iterator range returning the loop
  // basic blocks in a structured order (dominator first).
  // The function will ignore basic blocks returned by |block_range| if they
  // does not belong to the loop.
  // The set |dead_blocks| will contain all the dead basic blocks.
  //
  // Requirements:
  //   - |loop| must be in the LCSSA form;
  //   - |cst_value| must be constant or null (to represent the default target
  //   of an OpSwitch).
  void SimplifyLoop(IteratorRange<UptrVectorIterator<BasicBlock>> block_range,
                    Loop* loop, Instruction* to_version_insn,
                    Instruction* cst_value,
                    std::unordered_set<uint32_t>* dead_blocks) {
    CFG& cfg = *context_->cfg();
    analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr();

    std::function<bool(uint32_t)> ignore_node;
    ignore_node = [loop](uint32_t bb_id) { return !loop->IsInsideLoop(bb_id); };

    std::vector<std::pair<Instruction*, uint32_t>> use_list;
    def_use_mgr->ForEachUse(to_version_insn,
                            [&use_list, &ignore_node, this](
                                Instruction* inst, uint32_t operand_index) {
                              BasicBlock* bb = context_->get_instr_block(inst);

                              if (!bb || ignore_node(bb->id())) {
                                // Out of the loop, the specialization does not
                                // apply any more.
                                return;
                              }
                              use_list.emplace_back(inst, operand_index);
                            });

    // First pass: inject the specialized value into the loop (and only the
    // loop).
    for (auto use : use_list) {
      Instruction* inst = use.first;
      uint32_t operand_index = use.second;
      BasicBlock* bb = context_->get_instr_block(inst);

      // If it is not a branch, simply inject the value.
      if (!inst->IsBranch()) {
        // To also handle switch, cst_value can be nullptr: this case
        // means that we are looking to branch to the default target of
        // the switch. We don't actually know its value so we don't touch
        // it if it not a switch.
        if (cst_value) {
          inst->SetOperand(operand_index, {cst_value->result_id()});
          def_use_mgr->AnalyzeInstUse(inst);
        }
      }

      // The user is a branch, kill dead branches.
      uint32_t live_target = 0;
      std::unordered_set<uint32_t> dead_branches;
      switch (inst->opcode()) {
        case SpvOpBranchConditional: {
          assert(cst_value && "No constant value to specialize !");
          bool branch_cond = false;
          if (GetConstCondition(cst_value, &branch_cond)) {
            uint32_t true_label =
                inst->GetSingleWordInOperand(kBranchCondTrueLabIdInIdx);
            uint32_t false_label =
                inst->GetSingleWordInOperand(kBranchCondFalseLabIdInIdx);
            live_target = branch_cond ? true_label : false_label;
            uint32_t dead_target = !branch_cond ? true_label : false_label;
            cfg.RemoveEdge(bb->id(), dead_target);
          }
          break;
        }
        case SpvOpSwitch: {
          live_target = inst->GetSingleWordInOperand(1);
          if (cst_value) {
            if (!cst_value->IsConstant()) break;
            const Operand& cst = cst_value->GetInOperand(0);
            for (uint32_t i = 2; i < inst->NumInOperands(); i += 2) {
              const Operand& literal = inst->GetInOperand(i);
              if (literal == cst) {
                live_target = inst->GetSingleWordInOperand(i + 1);
                break;
              }
            }
          }
          for (uint32_t i = 1; i < inst->NumInOperands(); i += 2) {
            uint32_t id = inst->GetSingleWordInOperand(i);
            if (id != live_target) {
              cfg.RemoveEdge(bb->id(), id);
            }
          }
        }
        default:
          break;
      }
      if (live_target != 0) {
        // Check for the presence of the merge block.
        if (Instruction* merge = bb->GetMergeInst()) context_->KillInst(merge);
        context_->KillInst(&*bb->tail());
        InstructionBuilder builder(context_, bb,
                                   IRContext::kAnalysisDefUse |
                                       IRContext::kAnalysisInstrToBlockMapping);
        builder.AddBranch(live_target);
      }
    }

    // Go through the loop basic block and tag all blocks that are obviously
    // dead.
    std::unordered_set<uint32_t> visited;
    for (BasicBlock& bb : block_range) {
      if (ignore_node(bb.id())) continue;
      visited.insert(bb.id());

      // Check if this block is dead, if so tag it as dead otherwise patch phi
      // instructions.
      bool has_live_pred = false;
      for (uint32_t pid : cfg.preds(bb.id())) {
        if (!dead_blocks->count(pid)) {
          has_live_pred = true;
          break;
        }
      }
      if (!has_live_pred) {
        dead_blocks->insert(bb.id());
        const BasicBlock& cbb = bb;
        // Patch the phis for any back-edge.
        cbb.ForEachSuccessorLabel(
            [dead_blocks, &visited, &cfg, this](uint32_t id) {
              if (!visited.count(id) || dead_blocks->count(id)) return;
              BasicBlock* succ = cfg.block(id);
              PatchPhis(succ, *dead_blocks, false);
            });
        continue;
      }
      // Update the phi instructions, some incoming branch have/will disappear.
      PatchPhis(&bb, *dead_blocks, /* preserve_phi = */ false);
    }
  }

  // Returns true if the header is not reachable or tagged as dead or if we
  // never loop back.
  bool IsLoopDead(BasicBlock* header, BasicBlock* latch,
                  const std::unordered_set<uint32_t>& dead_blocks) {
    if (!header || dead_blocks.count(header->id())) return true;
    if (!latch || dead_blocks.count(latch->id())) return true;
    for (uint32_t pid : context_->cfg()->preds(header->id())) {
      if (!dead_blocks.count(pid)) {
        // Seems reachable.
        return false;
      }
    }
    return true;
  }

  // Cleans the loop nest under |loop| and reflect changes to the loop
  // descriptor. This will kill all descriptors that represent dead loops.
  // If |loop_| is killed, it will be set to nullptr.
  // Any merge blocks that become unreachable will be added to
  // |unreachable_merges|.
  // The function returns the pointer to |loop| or nullptr if the loop was
  // killed.
  Loop* CleanLoopNest(Loop* loop,
                      const std::unordered_set<uint32_t>& dead_blocks,
                      std::unordered_set<uint32_t>* unreachable_merges) {
    // This represent the pair of dead loop and nearest alive parent (nullptr if
    // no parent).
    std::unordered_map<Loop*, Loop*> dead_loops;
    auto get_parent = [&dead_loops](Loop* l) -> Loop* {
      std::unordered_map<Loop*, Loop*>::iterator it = dead_loops.find(l);
      if (it != dead_loops.end()) return it->second;
      return nullptr;
    };

    bool is_main_loop_dead =
        IsLoopDead(loop->GetHeaderBlock(), loop->GetLatchBlock(), dead_blocks);
    if (is_main_loop_dead) {
      if (Instruction* merge = loop->GetHeaderBlock()->GetLoopMergeInst()) {
        context_->KillInst(merge);
      }
      dead_loops[loop] = loop->GetParent();
    } else {
      dead_loops[loop] = loop;
    }

    // For each loop, check if we killed it. If we did, find a suitable parent
    // for its children.
    for (Loop& sub_loop :
         make_range(++TreeDFIterator<Loop>(loop), TreeDFIterator<Loop>())) {
      if (IsLoopDead(sub_loop.GetHeaderBlock(), sub_loop.GetLatchBlock(),
                     dead_blocks)) {
        if (Instruction* merge =
                sub_loop.GetHeaderBlock()->GetLoopMergeInst()) {
          context_->KillInst(merge);
        }
        dead_loops[&sub_loop] = get_parent(&sub_loop);
      } else {
        // The loop is alive, check if its merge block is dead, if it is, tag it
        // as required.
        if (sub_loop.GetMergeBlock()) {
          uint32_t merge_id = sub_loop.GetMergeBlock()->id();
          if (dead_blocks.count(merge_id)) {
            unreachable_merges->insert(sub_loop.GetMergeBlock()->id());
          }
        }
      }
    }
    if (!is_main_loop_dead) dead_loops.erase(loop);

    // Remove dead blocks from live loops.
    for (uint32_t bb_id : dead_blocks) {
      Loop* l = loop_desc_[bb_id];
      if (l) {
        l->RemoveBasicBlock(bb_id);
        loop_desc_.ForgetBasicBlock(bb_id);
      }
    }

    std::for_each(
        dead_loops.begin(), dead_loops.end(),
        [&loop,
         this](std::unordered_map<Loop*, Loop*>::iterator::reference it) {
          if (it.first == loop) loop = nullptr;
          loop_desc_.RemoveLoop(it.first);
        });

    return loop;
  }

  // Returns true if |var| is dynamically uniform.
  // Note: this is currently approximated as uniform.
  bool IsDynamicallyUniform(Instruction* var, const BasicBlock* entry,
                            const DominatorTree& post_dom_tree) {
    assert(post_dom_tree.IsPostDominator());
    analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr();

    auto it = dynamically_uniform_.find(var->result_id());

    if (it != dynamically_uniform_.end()) return it->second;

    analysis::DecorationManager* dec_mgr = context_->get_decoration_mgr();

    bool& is_uniform = dynamically_uniform_[var->result_id()];
    is_uniform = false;

    dec_mgr->WhileEachDecoration(var->result_id(), SpvDecorationUniform,
                                 [&is_uniform](const Instruction&) {
                                   is_uniform = true;
                                   return false;
                                 });
    if (is_uniform) {
      return is_uniform;
    }

    BasicBlock* parent = context_->get_instr_block(var);
    if (!parent) {
      return is_uniform = true;
    }

    if (!post_dom_tree.Dominates(parent->id(), entry->id())) {
      return is_uniform = false;
    }
    if (var->opcode() == SpvOpLoad) {
      const uint32_t PtrTypeId =
          def_use_mgr->GetDef(var->GetSingleWordInOperand(0))->type_id();
      const Instruction* PtrTypeInst = def_use_mgr->GetDef(PtrTypeId);
      uint32_t storage_class =
          PtrTypeInst->GetSingleWordInOperand(kTypePointerStorageClassInIdx);
      if (storage_class != SpvStorageClassUniform &&
          storage_class != SpvStorageClassUniformConstant) {
        return is_uniform = false;
      }
    } else {
      if (!context_->IsCombinatorInstruction(var)) {
        return is_uniform = false;
      }
    }

    return is_uniform = var->WhileEachInId([entry, &post_dom_tree,
                                            this](const uint32_t* id) {
      return IsDynamicallyUniform(context_->get_def_use_mgr()->GetDef(*id),
                                  entry, post_dom_tree);
    });
  }

  // Returns true if |insn| is constant and dynamically uniform within the loop.
  bool IsConditionLoopInvariant(Instruction* insn) {
    assert(insn->IsBranch());
    assert(insn->opcode() != SpvOpBranch);
    analysis::DefUseManager* def_use_mgr = context_->get_def_use_mgr();

    Instruction* condition = def_use_mgr->GetDef(insn->GetOperand(0).words[0]);
    return !loop_->IsInsideLoop(condition) &&
           IsDynamicallyUniform(
               condition, function_->entry().get(),
               context_->GetPostDominatorAnalysis(function_)->GetDomTree());
  }
};

}  // namespace

Pass::Status LoopUnswitchPass::Process() {
  bool modified = false;
  Module* module = context()->module();

  // Process each function in the module
  for (Function& f : *module) {
    modified |= ProcessFunction(&f);
  }

  return modified ? Status::SuccessWithChange : Status::SuccessWithoutChange;
}

bool LoopUnswitchPass::ProcessFunction(Function* f) {
  bool modified = false;
  std::unordered_set<Loop*> processed_loop;

  LoopDescriptor& loop_descriptor = *context()->GetLoopDescriptor(f);

  bool loop_changed = true;
  while (loop_changed) {
    loop_changed = false;
    for (Loop& loop :
         make_range(++TreeDFIterator<Loop>(loop_descriptor.GetDummyRootLoop()),
                    TreeDFIterator<Loop>())) {
      if (processed_loop.count(&loop)) continue;
      processed_loop.insert(&loop);

      LoopUnswitch unswitcher(context(), f, &loop, &loop_descriptor);
      while (!unswitcher.WasLoopKilled() && unswitcher.CanUnswitchLoop()) {
        if (!loop.IsLCSSA()) {
          LoopUtils(context(), &loop).MakeLoopClosedSSA();
        }
        modified = true;
        loop_changed = true;
        unswitcher.PerformUnswitch();
      }
      if (loop_changed) break;
    }
  }

  return modified;
}

}  // namespace opt
}  // namespace spvtools