//===- llvm/Analysis/ControlStructureAnalysis.h - Control Structure Analysis --*- C++ -*-===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===--------------------------------------------------------------------------------===//
//
// This file defines the ControlStructureTree class, used to build a tree 
// of control structures (IF/LOOP/BLOCK) in a function.
// Refer to "Advanced Compiler Design and Implementation" -- Steven. S. Muchnik
// for an explanation of the algorithms and data structures used here.
//
// Warning: Do not confuse "Struct" used throughout this file with C "struct"s.
//          Structure here refers to control structures, such as IF/WHILE etc.
//
//===----------------------------------------------------------------------===//
//====  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_ANALYSIS_CONTROLSTRUCTUREANALYSIS_H
#define LLVM_ANALYSIS_CONTROLSTRUCTUREANALYSIS_H

#include "llvm/IR/Dominators.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/PostDominators.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/Instructions.h"
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <vector>
#include <map>

typedef std::vector<int> IntVector;
typedef std::set<int> IntSet;

namespace llvm  {

  struct ControlStructureTree {
    enum CSTNodeTy {
      CST_None = 0,    // Deleted node / Failuring in id'ing a structure
      // No node can have this type.

      // All constructs below have a single entry.
      CST_Block,       // Straight line blocks code. Note that this
      // need not be one basic block. It can be a
      // straight sequence (no control-flow) of any
      // control structure nodes.
      CST_IfThen,      // An If-Then construct
      CST_IfThenElse,  // an If-Then-Else construct
      CST_Switch,      // Multiway branching - switch statement
      CST_Proper,      // A proper acyclic interval. This is
      // any acyclic structure that is not
      // any of the acyclic structures above.
      CST_SelfLoop,    // A node branching back to itself.
      CST_WhileLoop,   // Single entry, single exit loop.
      CST_NaturalLoop, // A reducible loop (i.e., single entry).
      CST_Improper,    // Consists of a multiple-entry loop.
                       // Single entry is ensured by having
                       // the common dominator also in the node.
    };

    // This represents node in the ControlStructureTree. Note
    // that it also pseudo-represents nodes in the abstract CFG
    // and hence contains Succ,Pred for the abstract CFG.
    struct CSTNode {
      int Index;                    // Index into the "Nodes" vector in Tree. 
      // Valid only if >= 0.
      int preOrderNo, postOrderNo;  // preorder and postorder traversal numbers.

      // Type of this node.
      CSTNodeTy StructType;
      // The set of nodes making up the region abstracted to this node.
      // This set is the set of children of this node in the tree.
      IntVector StructNodes;
      // Index of the region containing this node (parent in the tree)
      int StructOf;

      // Succesors and Predecessors in the abstract CFG (the abstract
      // CFG is initially the function's CFG and is modified as the
      // algorithm progresses by abstracting out nodes).
      IntVector Succ, Pred;

      // DomTree related edges
      IntVector domTreeChildren;
      int iDom;

      // The loop this is immediately contained in, in terms of llvm::LoopInfo.
      // For non-basic-blocks, we update this in Replace().
      Loop *iLoop;

      BasicBlock *BB;     // Only set if this refers a single basic block.

      CSTNode(int Index_p, CSTNodeTy ty) : 
        Index(Index_p), preOrderNo(-1), postOrderNo(-1), StructType(ty), 
        StructOf(-1), iDom(-1), iLoop(nullptr), BB(nullptr) { ; };
      CSTNode(int Index_p, BasicBlock *BB_p) : 
        Index(Index_p), preOrderNo(-1), postOrderNo(-1), StructType(CST_Block),
        StructOf(-1), iDom(-1), iLoop(nullptr), BB(BB_p) { ; };
    };
    typedef std::vector<CSTNode> CSTNodeVector;

  private:
    // The function we are analyzing.
    Function *curF;
    DominatorTree *DT;
    LoopInfo *LI;

    // The set of all nodes in the tree (and the abstract CFG).
    CSTNodeVector Nodes;
    // List of deleted nodes for re-use.
    IntVector deletedNodes;

    // A map from each BB in curF to the Index of its Node in Nodes.
    std::map<BasicBlock *, int> BBToNodeMap;
    // Nodes[Post[i]] is the node with post order number "i".
    IntVector Post;
    // Current node (in main loop) will have post order number PostCtr.
    unsigned PostCtr;
    // Entry into the abstract CFG. This might change during the execution
    // of the algorithm as nodes (including entryNode) are reduced.
    int entryNode;

    // If there are irreducible loops (CST_Improper) in the function,
    // iLoop will be invalid w.r.t LLVM's LoopInfo.
    bool loopInfoValid;

    // Initialize the abstract CFG to the actual CFG.
    // Return the index of the function entry node.
    int initializeGraph(void);
    // Clear and fill up "Post".
    void DFSPostorder(int entryNode);
    // Identify known acyclic structures
    CSTNodeTy AcyclicRegionType(IntSet &N, int node, IntVector &nset);
    // Identify arbitrary acyclic structures (proper intervals)
    CSTNodeTy ProperIntervalType(IntSet &N, int node, IntVector &nset);
    // Identify cyclic structures
    CSTNodeTy CyclicRegionType(IntSet &N, int node, IntVector &nset);
    // Replace NodeSet by an abstract region node and set data structures.
    // Return the new CSTNode representing the abstract region.
    int Reduce(IntSet &N, CSTNodeTy rtype, IntVector &NodeSet);
    // Link region "node" into abstract flow graph, adjust the postorder
    // traversal, and update successors and predecessors.
    void Replace(IntSet &N, int node, IntVector &NodeSet);
    // Is edge a backedge. Uses preOrderNo and postOrderNo to compute.
    bool isBackEdge(CSTNode &from, CSTNode &to);
    // Is this CSTNodeTy a cyclic type
    bool isCyclicCSTNodeTy(CSTNodeTy &ty);
    // Is there a cycle within this NodeSet
    bool NodeSetContainsCycle(IntVector &NodeSet);
    // Get the first common dominator for all nodes in NodeSet.
    int nearestCommonDominator(IntVector &NodeSet);
    // Does A dominate B
    bool dominates(int A, int B);
    // Returns true if there is a node "k" such that there is a 
    // (possibly empty) path from "m" to "k" that does not pass 
    // through "n" and an edge "k"->"n" that is a back edge.
    bool PathBack(IntSet &N, int m, int n);
    // Returns true if there is a non-trivial path from n to m such 
    // that all nodes in the path are in I. Otherwise returns false.
    bool Path(int n, int m, IntSet &I);
    // Is A an ancestor of B in the control structure tree?
    bool isCSTAncestor(int A, int B);

  public:
    ControlStructureTree(Function *F) { curF = F; };
    // (re)compute ConstrolStructureTree for curF.
    // Return false if CFG couldn't be analyzed.
    bool analyze(DominatorTree *DTp, LoopInfo *LIp);

    void computeReachUnder(IntVector &ReachUnder, int node);

    // If a CST_Block has another CST_Block as its child, merge them.
    void mergeBlocks(int subtree);

    // Get a list of nodes in the subtree starting at N
    void PopulateSubtree(CSTNode &N, SmallVectorImpl<CSTNode*> &CSTSubtree);
    void print(raw_ostream &OS, CSTNode *N = nullptr);
    void printNode(raw_ostream &OS, CSTNode &N);

    // Some accessors
    int getFunctionEntryNode(void);
    const CSTNodeVector &getNodeList(void);
    CSTNode &getNode(int node);
    Function *getCurF(void);

    // Get specific tree children for each type of node
    int getIf(int node);        // Valid for CST_IfThen and CST_IfThenElse
    int getThen(int node);      // Valid for CST_IfThen and CST_IfThenElse
    int getElse(int node);      // Valid for CST_IfThenElse
    int getEntry(int node);     // Valid for all types of nodes
    int getExit(int node);      // Valid for all types of nodes
    bool isLoopInfoValid(void); // Is CST's loop info valid?
    Loop *getLoop(int node);    // Valid only if CST_*Loop and isLoopInfoValid
    // Recursively call getEntry till a node corresponding
    // to a basic block is found.
    BasicBlock *getEntryBlock(int node);
    // Get the entry block for the exit of "node"
    BasicBlock *getExitBlock(int node);

    // Get CST index for this @BB.
    int getCSTIndexFor(BasicBlock *BB);
    // Get CST index for node representing Loop @L.
    // If unable to find, return -1.
    int getNodeForLoop(Loop *L);

    // Get a list of basic blocks in subtree rooted at "n".
    void getBasicBlocksInSubTree(std::vector<BasicBlock *> &BBs, int n);
    // Does node "n" have an exit out from the function?
    bool ExitsFunction(int n);

    // Modification API
    // Update to new BB for a CSTNode in BBToNodeMap.
    void UpdateToNewBB(int n, BasicBlock *NewBB);
    // Add a new node to the graph, return a reference to it.
    CSTNode &addNode(CSTNodeTy ty, BasicBlock *BB = nullptr);
    // Delete this node and add to free list. Updates to @node's parent and
    // child are not done.
    void deleteNode(int node);
    // Delete this node and all its descendents.
    void deleteSubTree(int node);

  };

} // End llvm namespace


#endif // LLVM_ANALYSIS_CONTROLSTRUCTUREANALYSIS_H
