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

#ifndef SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_
#define SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_

#include <unordered_map>
#include <unordered_set>

#include "source/opt/function.h"
#include "source/util/bit_vector.h"

namespace spvtools {
namespace opt {

class IRContext;

// An analysis that, for each basic block, finds the constructs in which it is
// contained, so we can easily get headers and merge nodes.
class StructuredCFGAnalysis {
 public:
  explicit StructuredCFGAnalysis(IRContext* ctx);

  // Returns the id of the header of the innermost merge construct
  // that contains |bb_id|.  Returns |0| if |bb_id| is not contained in any
  // merge construct.
  uint32_t ContainingConstruct(uint32_t bb_id) {
    auto it = bb_to_construct_.find(bb_id);
    if (it == bb_to_construct_.end()) {
      return 0;
    }
    return it->second.containing_construct;
  }

  // Returns the id of the header of the innermost merge construct
  // that contains |inst|.  Returns |0| if |inst| is not contained in any
  // merge construct.
  uint32_t ContainingConstruct(Instruction* inst);

  // Returns the id of the merge block of the innermost merge construct
  // that contains |bb_id|.  Returns |0| if |bb_id| is not contained in any
  // merge construct.
  uint32_t MergeBlock(uint32_t bb_id);

  // Returns the nesting depth of the given block, i.e. the number of merge
  // constructs containing it. Headers and merge blocks are not considered part
  // of the corresponding merge constructs.
  uint32_t NestingDepth(uint32_t block_id);

  // Returns the id of the header of the innermost loop construct
  // that contains |bb_id|.  Return |0| if |bb_id| is not contained in any loop
  // construct.
  uint32_t ContainingLoop(uint32_t bb_id) {
    auto it = bb_to_construct_.find(bb_id);
    if (it == bb_to_construct_.end()) {
      return 0;
    }
    return it->second.containing_loop;
  }

  // Returns the id of the merge block of the innermost loop construct
  // that contains |bb_id|.  Return |0| if |bb_id| is not contained in any loop
  // construct.
  uint32_t LoopMergeBlock(uint32_t bb_id);

  // Returns the id of the continue block of the innermost loop construct
  // that contains |bb_id|.  Return |0| if |bb_id| is not contained in any loop
  // construct.
  uint32_t LoopContinueBlock(uint32_t bb_id);

  // Returns the loop nesting depth of |bb_id| within its function, i.e. the
  // number of loop constructs in which |bb_id| is contained. As per other
  // functions in StructuredCFGAnalysis, a loop header is not regarded as being
  // part of the loop that it heads, so that e.g. the nesting depth of an
  // outer-most loop header is 0.
  uint32_t LoopNestingDepth(uint32_t bb_id);

  // Returns the id of the header of the innermost switch construct
  // that contains |bb_id| as long as there is no intervening loop.  Returns |0|
  // if no such construct exists.
  uint32_t ContainingSwitch(uint32_t bb_id) {
    auto it = bb_to_construct_.find(bb_id);
    if (it == bb_to_construct_.end()) {
      return 0;
    }
    return it->second.containing_switch;
  }
  // Returns the id of the merge block of the innermost switch construct
  // that contains |bb_id| as long as there is no intervening loop.  Return |0|
  // if no such block exists.
  uint32_t SwitchMergeBlock(uint32_t bb_id);

  // Returns true if |bb_id| is the continue block for a loop.
  bool IsContinueBlock(uint32_t bb_id);

  // Returns true if |bb_id| is in the continue construct for its inner most
  // containing loop.
  bool IsInContainingLoopsContinueConstruct(uint32_t bb_id);

  // Returns true if |bb_id| is in the continue construct for any loop in its
  // function.
  bool IsInContinueConstruct(uint32_t bb_id);

  // Return true if |bb_id| is the merge block for a construct.
  bool IsMergeBlock(uint32_t bb_id);

  // Returns the set of function ids that are called directly or indirectly from
  // a continue construct.
  std::unordered_set<uint32_t> FindFuncsCalledFromContinue();

 private:
  // Struct used to hold the information for a basic block.
  // |containing_construct| is the header for the innermost containing
  // construct, or 0 if no such construct exists.  It could be a selection
  // construct or a loop construct.
  //
  // |containing_loop| is the innermost containing loop construct, or 0 if the
  // basic bloc is not in a loop.  If the basic block is in a selection
  // construct that is contained in a loop construct, then these two values will
  // not be the same.
  //
  // |containing_switch| is the innermost contain selection construct with an
  // |OpSwitch| for the branch, as long as there is not intervening loop.  This
  // is used to identify the selection construct from which it can break.
  //
  // |in_continue| is true of the block is in the continue construct for its
  // innermost containing loop.
  struct ConstructInfo {
    uint32_t containing_construct;
    uint32_t containing_loop;
    uint32_t containing_switch;
    bool in_continue;
  };

  // Populates |bb_to_construct_| with the innermost containing merge and loop
  // constructs for each basic block in |func|.
  void AddBlocksInFunction(Function* func);

  IRContext* context_;

  // A map from a basic block to the headers of its inner most containing
  // constructs.
  std::unordered_map<uint32_t, ConstructInfo> bb_to_construct_;
  utils::BitVector merge_blocks_;
};

}  // namespace opt
}  // namespace spvtools
#endif  // SOURCE_OPT_STRUCT_CFG_ANALYSIS_H_