loop_nesting.h

// This file if part of the llir-opt project.
// Licensing information can be found in the LICENSE file.
// (C) 2018 Nandor Licker. All rights reserved.
 
#pragma once
 
#include <memory>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <vector>
#include <llvm/ADT/iterator_range.h>
 
#include "core/adt/hash.h"
#include "core/analysis/union_find.h"
 
class Block;
class Func;
 
 
 
class LoopNesting final {
public:
  class Loop {
  public:
    const Block *GetHeader() const { return header_; }
 
    using LoopIter = std::vector<Loop *>::iterator;
    LoopIter loop_begin() { return loops_.begin(); }
    LoopIter loop_end() { return loops_.end(); }
    llvm::iterator_range<LoopIter> loops()
    {
      return llvm::make_range(loop_begin(), loop_end());
    }
 
    using BlockIter = std::vector<const Block *>::iterator;
    BlockIter block_begin() { return blocks_.begin(); }
    BlockIter block_end() { return blocks_.end(); }
    llvm::iterator_range<BlockIter> blocks()
    {
      return llvm::make_range(block_begin(), block_end());
    }
 
  private:
    friend class LoopNesting;
    Loop(const Block *header) : header_(header), blocks_({header}) {}
 
  public:
    const Block *header_;
    std::vector<Loop *> loops_;
    std::vector<const Block *> blocks_;
  };
 
  LoopNesting(const Func *func);
 
  bool IsLoopEdge(const Block *a, const Block *b);
 
  const Block *HighestAncestor(const Block *s, const Block *t);
 
  std::set<Loop *>::iterator begin() { return roots_.begin(); }
  std::set<Loop *>::iterator end() { return roots_.end(); }
 
  void dump(llvm::raw_ostream &os = llvm::errs());
 
private:
  void FindLoop(unsigned header);
 
  bool IsCrossEdge(unsigned a, unsigned b);
  bool IsTreeEdge(unsigned a, unsigned b);
  bool IsForwardEdge(unsigned a, unsigned b);
  bool IsBackEdge(unsigned a, unsigned b);
 
  unsigned DFS(const Block *block, unsigned parent);
  void LCA(unsigned node);
 
  void MarkIrreducibleLoops(unsigned node);
 
  void HnCA(Loop *loop, std::set<const Block *> blocks);
 
private:
  using Edge = std::pair<unsigned, unsigned>;
 
  struct GraphNode {
    unsigned Parent;
    const Block *BlockPtr;
    Loop *LoopPtr;
    unsigned Start;
    unsigned End;
 
    unsigned Link;
    unsigned Rank;
    unsigned Class;
 
    std::vector<unsigned> Pred;
    std::vector<unsigned> Children;
    std::vector<unsigned> CrossForwardCandidates;
    std::vector<Edge> CrossForwardEdges;
  };
 
  unsigned n_;
 
  std::vector<GraphNode> graph_;
  std::unordered_map<const Block *, unsigned> blockToId_;
  unsigned count_;
 
  UnionFind loopHeaders_;
  UnionFind reducibleLoopHeaders_;
 
  UnionFind lcaParents_;
  std::vector<bool> lcaVisited_;
  std::vector<unsigned> lcaAncestor_;
 
  std::vector<bool> irreducibleLoopHeader_;
  std::vector<std::optional<unsigned>> loopParent_;
 
  std::set<Loop *> roots_;
  std::unordered_map<const Block *, std::unique_ptr<Loop>> blockToLoop_;
};