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

#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>;

  using ParamList = std::vector<std::unique_ptr<Instruction>>;

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

  // Rewrites the function parameters by calling a replacer callback.

  // The replacer takes two parameters: an expiring unique pointer to a current

  // instruction, and a back-inserter into a new list of unique pointers to

  // instructions.  The replacer is called for each current parameter, in order.

  // Not valid to call while also iterating through the parameter list, e.g.

  // within the ForEachParam method.

  using RewriteParamFn = std::function<void(

      std::unique_ptr<Instruction>&&, std::back_insert_iterator<ParamList>&)>;

  void RewriteParams(RewriteParamFn& replacer) {

    ParamList new_params;

    auto appender = std::back_inserter(new_params);

    for (auto& param : params_) {

      replacer(std::move(param), appender);

    }

    params_ = std::move(new_params);

  }

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

  ParamList 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_