function.h

// Copyright (c) 2016 Google Inc.
//
// 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.

#ifndef SOURCE_OPT_FUNCTION_H_
#define SOURCE_OPT_FUNCTION_H_

#include <algorithm>
#include <functional>
#include <memory>
#include <string>
#include <unordered_set>
#include <utility>
#include <vector>

#include "source/opt/basic_block.h"
#include "source/opt/instruction.h"
#include "source/opt/iterator.h"

namespace spvtools {
namespace opt {

class CFG;
class IRContext;
class Module;

// A SPIR-V function.
class Function {
 public:
  using iterator = UptrVectorIterator<BasicBlock>;
  using const_iterator = UptrVectorIterator<BasicBlock, true>;

  // Creates a function instance declared by the given OpFunction instruction
  // |def_inst|.
  inline explicit Function(std::unique_ptr<Instruction> def_inst);

  explicit Function(const Function& f) = delete;

  // Creates a clone of the instruction in the given |context|
  //
  // The parent module will default to null and needs to be explicitly set by
  // the user.
  Function* Clone(IRContext*) const;
  // The OpFunction instruction that begins the definition of this function.
  Instruction& DefInst() { return *def_inst_; }
  const Instruction& DefInst() const { return *def_inst_; }

  // Appends a parameter to this function.
  inline void AddParameter(std::unique_ptr<Instruction> p);
  // Appends a debug instruction in function header to this function.
  inline void AddDebugInstructionInHeader(std::unique_ptr<Instruction> p);
  // Appends a basic block to this function.
  inline void AddBasicBlock(std::unique_ptr<BasicBlock> b);
  // Appends a basic block to this function at the position |ip|.
  inline void AddBasicBlock(std::unique_ptr<BasicBlock> b, iterator ip);
  template <typename T>
  inline void AddBasicBlocks(T begin, T end, iterator ip);

  // Move basic block with |id| to the position after |ip|. Both have to be
  // contained in this function.
  inline void MoveBasicBlockToAfter(uint32_t id, BasicBlock* ip);

  // Delete all basic blocks that contain no instructions.
  inline void RemoveEmptyBlocks();

  // Removes a parameter from the function with result id equal to |id|.
  // Does nothing if the function doesn't have such a parameter.
  inline void RemoveParameter(uint32_t id);

  // Saves the given function end instruction.
  inline void SetFunctionEnd(std::unique_ptr<Instruction> end_inst);

  // Add a non-semantic instruction that succeeds this function in the module.
  // These instructions are maintained in the order they are added.
  inline void AddNonSemanticInstruction(
      std::unique_ptr<Instruction> non_semantic);

  // Returns the given function end instruction.
  inline Instruction* EndInst() { return end_inst_.get(); }
  inline const Instruction* EndInst() const { return end_inst_.get(); }

  // Returns function's id
  inline uint32_t result_id() const { return def_inst_->result_id(); }

  // Returns function's return type id
  inline uint32_t type_id() const { return def_inst_->type_id(); }

  // Returns the function's control mask
  inline uint32_t control_mask() const { return def_inst_->GetSingleWordInOperand(0); }

  // Returns the entry basic block for this function.
  const std::unique_ptr<BasicBlock>& entry() const { return blocks_.front(); }

  // Returns the last basic block in this function.
  BasicBlock* tail() { return blocks_.back().get(); }
  const BasicBlock* tail() const { return blocks_.back().get(); }

  iterator begin() { return iterator(&blocks_, blocks_.begin()); }
  iterator end() { return iterator(&blocks_, blocks_.end()); }
  const_iterator begin() const { return cbegin(); }
  const_iterator end() const { return cend(); }
  const_iterator cbegin() const {
    return const_iterator(&blocks_, blocks_.cbegin());
  }
  const_iterator cend() const {
    return const_iterator(&blocks_, blocks_.cend());
  }

  // Returns an iterator to the basic block |id|.
  iterator FindBlock(uint32_t bb_id) {
    return std::find_if(begin(), end(), [bb_id](const BasicBlock& it_bb) {
      return bb_id == it_bb.id();
    });
  }

  // Runs the given function |f| on instructions in this function, in order,
  // and optionally on debug line instructions that might precede them and
  // non-semantic instructions that succceed the function.
  void ForEachInst(const std::function<void(Instruction*)>& f,
                   bool run_on_debug_line_insts = false,
                   bool run_on_non_semantic_insts = false);
  void ForEachInst(const std::function<void(const Instruction*)>& f,
                   bool run_on_debug_line_insts = false,
                   bool run_on_non_semantic_insts = false) const;
  // Runs the given function |f| on instructions in this function, in order,
  // and optionally on debug line instructions that might precede them and
  // non-semantic instructions that succeed the function.  If |f| returns
  // false, iteration is terminated and this function returns false.
  bool WhileEachInst(const std::function<bool(Instruction*)>& f,
                     bool run_on_debug_line_insts = false,
                     bool run_on_non_semantic_insts = false);
  bool WhileEachInst(const std::function<bool(const Instruction*)>& f,
                     bool run_on_debug_line_insts = false,
                     bool run_on_non_semantic_insts = false) const;

  // Runs the given function |f| on each parameter instruction in this function,
  // in order, and optionally on debug line instructions that might precede
  // them.
  void ForEachParam(const std::function<void(const Instruction*)>& f,
                    bool run_on_debug_line_insts = false) const;
  void ForEachParam(const std::function<void(Instruction*)>& f,
                    bool run_on_debug_line_insts = false);

  // Runs the given function |f| on each debug instruction in this function's
  // header in order.
  void ForEachDebugInstructionsInHeader(
      const std::function<void(Instruction*)>& f);

  BasicBlock* InsertBasicBlockAfter(std::unique_ptr<BasicBlock>&& new_block,
                                    BasicBlock* position);

  BasicBlock* InsertBasicBlockBefore(std::unique_ptr<BasicBlock>&& new_block,
                                     BasicBlock* position);

  // Returns true if the function has a return block other than the exit block.
  bool HasEarlyReturn() const;

  // Returns true if the function calls itself either directly or indirectly.
  bool IsRecursive() const;

  // Pretty-prints all the basic blocks in this function into a std::string.
  //
  // |options| are the disassembly options. SPV_BINARY_TO_TEXT_OPTION_NO_HEADER
  // is always added to |options|.
  std::string PrettyPrint(uint32_t options = 0u) const;

  // Dump this function on stderr.  Useful when running interactive
  // debuggers.
  void Dump() const;

  // Returns true is a function declaration and not a function definition.
  bool IsDeclaration() { return begin() == end(); }

  // Reorders the basic blocks in the function to match the structured order.
  void ReorderBasicBlocksInStructuredOrder();

 private:
  // Reorders the basic blocks in the function to match the order given by the
  // range |{begin,end}|.  The range must contain every basic block in the
  // function, and no extras.
  template <class It>
  void ReorderBasicBlocks(It begin, It end);

  template <class It>
  bool ContainsAllBlocksInTheFunction(It begin, It end);

  // The OpFunction instruction that begins the definition of this function.
  std::unique_ptr<Instruction> def_inst_;
  // All parameters to this function.
  std::vector<std::unique_ptr<Instruction>> params_;
  // All debug instructions in this function's header.
  InstructionList debug_insts_in_header_;
  // All basic blocks inside this function in specification order
  std::vector<std::unique_ptr<BasicBlock>> blocks_;
  // The OpFunctionEnd instruction.
  std::unique_ptr<Instruction> end_inst_;
  // Non-semantic instructions succeeded by this function.
  std::vector<std::unique_ptr<Instruction>> non_semantic_;
};

// Pretty-prints |func| to |str|. Returns |str|.
std::ostream& operator<<(std::ostream& str, const Function& func);

inline Function::Function(std::unique_ptr<Instruction> def_inst)
    : def_inst_(std::move(def_inst)), end_inst_() {}

inline void Function::AddParameter(std::unique_ptr<Instruction> p) {
  params_.emplace_back(std::move(p));
}

inline void Function::AddDebugInstructionInHeader(
    std::unique_ptr<Instruction> p) {
  debug_insts_in_header_.push_back(std::move(p));
}

inline void Function::AddBasicBlock(std::unique_ptr<BasicBlock> b) {
  AddBasicBlock(std::move(b), end());
}

inline void Function::AddBasicBlock(std::unique_ptr<BasicBlock> b,
                                    iterator ip) {
  b->SetParent(this);
  ip.InsertBefore(std::move(b));
}

template <typename T>
inline void Function::AddBasicBlocks(T src_begin, T src_end, iterator ip) {
  blocks_.insert(ip.Get(), std::make_move_iterator(src_begin),
                 std::make_move_iterator(src_end));
}

inline void Function::MoveBasicBlockToAfter(uint32_t id, BasicBlock* ip) {
  std::unique_ptr<BasicBlock> block_to_move = std::move(*FindBlock(id).Get());
  blocks_.erase(std::find(std::begin(blocks_), std::end(blocks_), nullptr));

  assert(block_to_move->GetParent() == ip->GetParent() &&
         "Both blocks have to be in the same function.");

  InsertBasicBlockAfter(std::move(block_to_move), ip);
}

inline void Function::RemoveEmptyBlocks() {
  auto first_empty =
      std::remove_if(std::begin(blocks_), std::end(blocks_),
                     [](const std::unique_ptr<BasicBlock>& bb) -> bool {
                       return bb->GetLabelInst()->opcode() == spv::Op::OpNop;
                     });
  blocks_.erase(first_empty, std::end(blocks_));
}

inline void Function::RemoveParameter(uint32_t id) {
  params_.erase(std::remove_if(params_.begin(), params_.end(),
                               [id](const std::unique_ptr<Instruction>& param) {
                                 return param->result_id() == id;
                               }),
                params_.end());
}

inline void Function::SetFunctionEnd(std::unique_ptr<Instruction> end_inst) {
  end_inst_ = std::move(end_inst);
}

inline void Function::AddNonSemanticInstruction(
    std::unique_ptr<Instruction> non_semantic) {
  non_semantic_.emplace_back(std::move(non_semantic));
}

template <class It>
void Function::ReorderBasicBlocks(It begin, It end) {
  // Asserts to make sure every node in the function is in new_order.
  assert(ContainsAllBlocksInTheFunction(begin, end));

  // We have a pointer to all the elements in order, so we can release all
  // pointers in |block_|, and then create the new unique pointers from |{begin,
  // end}|.
  std::for_each(blocks_.begin(), blocks_.end(),
                [](std::unique_ptr<BasicBlock>& bb) { bb.release(); });
  std::transform(begin, end, blocks_.begin(), [](BasicBlock* bb) {
    return std::unique_ptr<BasicBlock>(bb);
  });
}

template <class It>
bool Function::ContainsAllBlocksInTheFunction(It begin, It end) {
  std::unordered_multiset<BasicBlock*> range(begin, end);
  if (range.size() != blocks_.size()) {
    return false;
  }

  for (auto& bb : blocks_) {
    if (range.count(bb.get()) == 0) return false;
  }
  return true;
}

}  // namespace opt
}  // namespace spvtools

#endif  // SOURCE_OPT_FUNCTION_H_