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;

}  // 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 (loop_->GetLatchBlock() == bb) {
        continue;
      }

      if (bb->terminator()->IsBranch() &&
          bb->terminator()->opcode() != SpvOpBranch) {
        if (IsConditionNonConstantLoopInvariant(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;
  }

  Instruction* GetValueForDefaultPathForSwitch(Instruction* switch_inst) {
    assert(switch_inst->opcode() == SpvOpSwitch &&
           "The given instructoin must be an OpSwitch.");

    // Find a value that can be used to select the default path.
    // If none are possible, then it will just use 0.  The value does not matter
    // because this path will never be taken because the new switch outside of
    // the loop cannot select this path either.
    std::vector<uint32_t> existing_values;
    for (uint32_t i = 2; i < switch_inst->NumInOperands(); i += 2) {
      existing_values.push_back(switch_inst->GetSingleWordInOperand(i));
    }
    std::sort(existing_values.begin(), existing_values.end());
    uint32_t value_for_default_path = 0;
    if (existing_values.size() < std::numeric_limits<uint32_t>::max()) {
      for (value_for_default_path = 0;
           value_for_default_path < existing_values.size();
           value_for_default_path++) {
        if (existing_values[value_for_default_path] != value_for_default_path) {
          break;
        }
      }
    }
    InstructionBuilder builder(
        context_, static_cast<Instruction*>(nullptr),
        IRContext::kAnalysisDefUse | IRContext::kAnalysisInstrToBlockMapping);
    return builder.GetUintConstant(value_for_default_path);
  }

  // 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_);
            cloned->SetResultId(TakeNextId());
            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 invariant 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;
    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 =
          GetValueForDefaultPathForSwitch(iv_condition);

      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.   //
      ////////////////////////////////////

      {
        SpecializeLoop(cloned_loop, condition, specialisation_value);

        ///////////////////////////////////////////////////////////
        // 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, &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);
                    uint32_t incoming_value_id = phi->GetSingleWordInOperand(i);
                    // Not all the incoming values 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));
    }

    // Specialize the existing loop.
    SpecializeLoop(loop_, condition, original_loop_constant_value);
    BasicBlock* original_loop_target = loop_->GetPreHeaderBlock();

    /////////////////////////////////////
    // 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);
  }

 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();
  }

  // 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.
  void SpecializeLoop(Loop* loop, Instruction* to_version_insn,
                      Instruction* cst_value) {
    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;

      // 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.
      assert(cst_value && "We do not have a value to use.");
      inst->SetOperand(operand_index, {cst_value->result_id()});
      def_use_mgr->AnalyzeInstUse(inst);
    }
  }

  // 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 not a constant, but is loop invariant and
  // dynamically uniform.
  bool IsConditionNonConstantLoopInvariant(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]);
    if (condition->IsConstant()) {
      return false;
    }

    if (loop_->IsInsideLoop(condition)) {
      return false;
    }

    return 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.GetPlaceholderRootLoop()),
             TreeDFIterator<Loop>())) {
      if (processed_loop.count(&loop)) continue;
      processed_loop.insert(&loop);

      LoopUnswitch unswitcher(context(), f, &loop, &loop_descriptor);
      while (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