//===--- DepUtils.h - DependenceAnalysis based utilities ------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Utilities implemented on top of DependenceAnalysis.
//
//===----------------------------------------------------------------------===//
//====  Copyright (c) 2015 Advanced Micro Devices, Inc.  All rights reserved.
//
//               Developed by: Advanced Micro Devices, Inc.
//
// Permission is hereby granted, free of charge, to any person obtaining a copy
// of this software and associated documentation files (the "Software"), to deal
// with the Software without restriction, including without limitation the
// rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
// sell copies of the Software, and to permit persons to whom the Software is
// furnished to do so, subject to the following conditions:
//
// Redistributions of source code must retain the above copyright notice, this
// list of conditions and the following disclaimers.
//
// Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimers in the documentation
// and/or other materials provided with the distribution.
//
// Neither the names of Advanced Micro Devices, Inc., nor the names of its
// contributors may be used to endorse or promote products derived from this
// Software without specific prior written permission.
//
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
// CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS WITH
// THE SOFTWARE.
//===----------------------------------------------------------------------===//
//

#ifndef LLVM_TRANSFORMS_DEP_GRAPH_H
#define LLVM_TRANSFORMS_DEP_GRAPH_H

#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/DependenceAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Value.h"
#include "llvm/IR/ValueMap.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"

using namespace llvm;

namespace llvm {

// Build a dependence graph:
//   Input: A set of basic blocks.
//   Output:
//       Node: Instruction
//       Edge: Dependence
//   Algorithm:
//       A very naive n^2 algorithm is used currently.
//       1. All loads/stores in the given basic blocks are noted down
//       2. for every pair of load/store (i,j)
//           We check (i,j), (j,i) and (i,i) for dependences.
//           a. In case of scalar dependences, check in both directions is
//              needed.
//           b. In case a dependence (i,j) turns out to be lexicographically
//              negative, we just ignore it. The right dependence will be
//              captured
//              by the other pair (j,i).
//       3. DependenceAnalysis::dependence() requires the caller to provide
//          a hint whether there is a path from "src" to "dst" that doesn't
//          involve back edges. This is required to identify loop-independent
//          dependences.
//          To do this, isPossiblyLoopIndependent() below is used. Here is what
//          it does:
//            - If "src" dominates "dst", then there surely is a loop-free path.
//              (this is a sufficient condition, not a necessary one).
//            - If condition above is not satisfied, then we do a traversal of
//              the CFG, ignoring back edges, and see if "dst" is reachable.
//              A heuristic is that we need not traverse past pdom(dst).
//
class DepGraph {
  // The DepGraph data structure is organized as follows:
  // 1. There is a global list of edges. Each edge is an object of class
  //    Dependence. : gEdgeList
  // 2. There is a global list of Nodes. : gNodeList
  // 3. each Node contains the following:
  //    a. A list of successor edges. Each element in this list is a pair. The
  //       first is an index into gNodeList while the second is an index into
  //       gEdgeList. : succs
  //    b. Similar to above, a list of predecessor edges. : preds
  // 4. To easily handle queries based on instructions (which are Nodes in the
  //    graph), there is a map to determine the index in gNodeList for the
  //    corresponding graph node.
public:
  class Node;

private:
  typedef std::shared_ptr<Dependence> DepPtr;
  // This is a list of all edges in the graph.
  std::vector<DepPtr> gEdgeList;

  // NodeEdgeIntPair->first == index into gNodeList
  // NodeEdgeIntPair->second == index into gEdgeList
  typedef std::pair<unsigned, unsigned> NodeEdgeIntPair;
  std::vector<Node> gNodeList;

  // Given an instruction, get its index in gNodeList.
  ValueMap<const Instruction *, unsigned> instNodeMap;

  friend std::unique_ptr<DepGraph> buildDepGraph(DependenceInfo *DA,
                                                 std::vector<BasicBlock *> &bl);

public:
  typedef std::pair<Node *, std::shared_ptr<Dependence>> NodeEdgePair;
  class Node {
    // These are indices into <gNodeList,gEdgeList>
    SmallVector<NodeEdgeIntPair, 8> succs;
    SmallVector<NodeEdgeIntPair, 8> preds;

    friend std::unique_ptr<DepGraph>
    buildDepGraph(DependenceInfo *DA, std::vector<BasicBlock *> &bl);
    friend class DepGraph;

  public:
    const Instruction *I;
    Node(const Instruction *I_p) { I = I_p; };
  };

  class edge_iterator {
    DepGraph *G;
    Node *N;
    unsigned idx;
    bool predsORsuccs; // 0 -> preds, 1 -> succs

  public:
    edge_iterator(DepGraph *G_p, Node *N_p, unsigned idx_p,
                  bool predsORsuccs_p) {
      G = G_p;
      N = N_p;
      idx = idx_p;
      predsORsuccs = predsORsuccs_p;
      assert((!predsORsuccs && idx <= N->preds.size()) ||
             (predsORsuccs && idx <= N->succs.size()));
    }

    edge_iterator(const edge_iterator &rhs) {
      G = rhs.G;
      N = rhs.N;
      idx = rhs.idx;
      predsORsuccs = rhs.predsORsuccs;
    }

    NodeEdgePair operator*() {
      if (!predsORsuccs) {
        // preds
        assert(idx < N->preds.size());
        return NodeEdgePair(&(G->gNodeList[N->preds[idx].first]),
                            G->gEdgeList[N->preds[idx].second]);
      } else {
        // succs
        assert(idx < N->succs.size());
        return NodeEdgePair(&(G->gNodeList[N->succs[idx].first]),
                            G->gEdgeList[N->succs[idx].second]);
      }
    }

    void operator++(void) {
      assert((!predsORsuccs && idx < N->preds.size()) ||
             (predsORsuccs && idx < N->succs.size()));
      idx++;
    }

    bool operator==(const edge_iterator &rhs) {
      return (G == rhs.G && N == rhs.N && idx == rhs.idx &&
              predsORsuccs == rhs.predsORsuccs);
    }

    bool operator!=(const edge_iterator &rhs) { return !(*this == rhs); }
  };

  class node_iterator {
    DepGraph *G;
    unsigned idx;

  public:
    node_iterator(DepGraph *G_p, unsigned idx_p) {
      G = G_p;
      idx = idx_p;
      assert(idx <= G->gNodeList.size());
    }

    node_iterator(const node_iterator &rhs) {
      G = rhs.G;
      idx = rhs.idx;
    }

    Node *operator*() { return &(G->gNodeList[idx]); }

    void operator++(void) {
      assert(idx < G->gNodeList.size());
      idx++;
    }

    bool operator==(const node_iterator &rhs) {
      return (G == rhs.G && idx == rhs.idx);
    }

    bool operator!=(const node_iterator &rhs) { return !(*this == rhs); }
  };

  class gedge_iterator {
    DepGraph *G;
    unsigned idx;

  public:
    gedge_iterator(DepGraph *G_p, unsigned idx_p) {
      G = G_p;
      idx = idx_p;
      assert(idx <= G->gEdgeList.size());
    }

    gedge_iterator(const gedge_iterator &rhs) {
      G = rhs.G;
      idx = rhs.idx;
    }

    DepPtr operator*() { return (G->gEdgeList[idx]); }

    void operator++(void) {
      assert(idx < G->gEdgeList.size());
      idx++;
    }

    bool operator==(const gedge_iterator &rhs) {
      return (G == rhs.G && idx == rhs.idx);
    }

    bool operator!=(const gedge_iterator &rhs) { return !(*this == rhs); }
  };

  friend class edge_iterator;
  friend class node_iterator;
  friend class gedge_iterator;

  // iterators:
  // Node iterator.
  node_iterator begin_node() { return node_iterator(this, 0); }
  node_iterator end_node() { return node_iterator(this, gNodeList.size()); }
  // preds iterator for a given Node.
  edge_iterator begin_pred(Node *N) { return edge_iterator(this, N, 0, 0); }
  edge_iterator end_pred(Node *N) {
    return edge_iterator(this, N, N->preds.size(), 0);
  }
  // succs iterator for a given Node.
  edge_iterator begin_succ(Node *N) { return edge_iterator(this, N, 0, 1); }
  edge_iterator end_succ(Node *N) {
    return edge_iterator(this, N, N->succs.size(), 1);
  }
  // global edge iterator.
  gedge_iterator begin() { return gedge_iterator(this, 0); }
  gedge_iterator end() { return gedge_iterator(this, gEdgeList.size()); }

  // edge/node accessors:
  std::shared_ptr<Dependence> getDep(const Instruction *src,
                                     const Instruction *dst);
  // return node index for Instruction *I. -1 if not found.
  int getNode(const Instruction *I);
  Node *getNode(unsigned i);
  // Add I to list of nodes and return its index.
  unsigned addNode(const Instruction *I);
  void addEdge(const Instruction *I, const Instruction *J,
               std::shared_ptr<Dependence> &d);
  void addEdge(unsigned i, unsigned j, std::shared_ptr<Dependence> &d);

  // Debug.
  void print(llvm::raw_ostream &O);
};

std::unique_ptr<DepGraph> buildDepGraph(DominatorTree *DT,
                                        PostDominatorTree *PDT,
                                        DependenceInfo *DA,
                                        const std::vector<BasicBlock *> bl,
                                        bool canDoWithRTChecks = false);

// Build dependence matrix.
// TODO: DepGraph is currently used to build the dependence matrix. But it can
// be built without DepGraph also which makes the DepGraph class obsolete. But
// DepGraph is retained for now because it "may" come in handy for profitability
// calculations; otherwise it should be deleted.
class DepMatrix {
  struct DepInfo {
    int direction;
    int distance;

    DepInfo() {
      direction = Dependence::DVEntry::ALL;
      distance = UnknownDistance;
    }
    bool operator==(const DepInfo &rhs) const {
      return (direction == rhs.direction && distance == rhs.distance);
    }
    bool operator!=(const DepInfo &rhs) const { return !((*this) == rhs); }
  };

public:
  // The DepInfoMatrix type
  typedef SmallVector<DepInfo, 4> DepInfoVector;
  typedef SmallVector<DepInfoVector, 4> DepInfoMatrix;
  static const int UnknownDistance = INT_MAX;

private:
  // A numOfDependences x numOfLoopsInNest matrix.
  DepInfoMatrix DIM;

  bool addDependence(std::shared_ptr<Dependence> d);

public:
  // Allow in-place modification of DIM.
  DepInfoMatrix &getMatrix() { return DIM; }

  bool buildMatrix(DominatorTree *DT, PostDominatorTree *PDT,
                   DependenceInfo *DI, const std::vector<BasicBlock *> &BBs,
                   bool canDoWithRTChecks = false);

  // The following functions can be called with a generic DIM.
  static bool hasStarInRow(const DepInfoMatrix &DIM);

  /// Remove dependences carried by any loop covering outL.
  /// Also remove columns lesser than outL
  void removeOuterLoops(Loop *outL);

  static void filter(DepInfoMatrix &DIM);

  static bool validate(const DepInfoMatrix &DIM);

  static void dump(const char *s, const DepInfoMatrix &DIM);
};

} // end of namespace llvm

#endif // LLVM_TRANSFORMS_DEP_GRAPH_H
