#ifndef LLVM_RECURSION_DEPTH_ESTIMATION_H
#define LLVM_RECURSION_DEPTH_ESTIMATION_H
//=========- RecursionDepthEstimation.h - Recursion Depth Analysis -==========//
//
//===----------------------------------------------------------------------===//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// 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.
//
//===----------------------------------------------------------------------===//
//
//===----------------------------------------------------------------------===//
#include "llvm/ADT/APInt.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/AliasSetTracker.h"
#include "llvm/Analysis/CFG.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/VectorUtils.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Function.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/TypeFinder.h"
#include "llvm/IR/ValueSymbolTable.h"
namespace llvm {
class RecursionDepthEstimator {
private:
  class CompareInfo {
  private:
    CmpInst *Cmp;
    unsigned FormalArgNum;
    bool CmpResToRecurse;

  public:
    CompareInfo(CmpInst *Cmp, unsigned FormalArgNum, bool CmpResToRecurse)
        : Cmp(Cmp), FormalArgNum(FormalArgNum),
          CmpResToRecurse(CmpResToRecurse) {}
    CmpInst *getCmpInst() { return Cmp; }
    unsigned getFormalArgNum() { return FormalArgNum; }
    bool getCmpResToRecurse() { return CmpResToRecurse; }
  };

  class SwitchInfo {
  public:
    SwitchInst *Switch;
    BasicBlock *RecursiveCallSiteBlock;
    std::map<int, bool> RecursionExitCase;
    SwitchInfo(SwitchInst *Switch, BasicBlock *RecursiveCallSiteBlock)
        : Switch(Switch), RecursiveCallSiteBlock(RecursiveCallSiteBlock) {
      RecursionExitCase.clear();
    }
    void analyzeSwitch(DominatorTree *);
  };

  Function *F;
  ScalarEvolution *SE;
  DominatorTree *DT;
  SmallVector<CallInst *, 2> RecursiveCallSites;
  SmallVector<CompareInfo *, 2> CompareInfoVec;
  SmallVector<SwitchInfo *, 2> SwitchInfoVec;
  MapVector<unsigned, const ConstantInt *> ArgumentStrideInfo;

  const ConstantInt *getStride(unsigned);
  void addCompareInfo(CmpInst *, unsigned, bool);
  bool analyzeBranchInst(BranchInst *, BasicBlock *);
  bool analyzeSwitchInst(SwitchInst *, BasicBlock *);
  bool hasValidStrideForArgument(unsigned);
  bool identifyStrideForArguments();
  bool analyzeRecursiveCallSiteProperties();
  const SCEV *calculateDepth(const SCEV *S1, const SCEV *S2, bool AdjustDepth);
public:
  SmallVector<CallInst *, 2> ExternalCallSites;
  RecursionDepthEstimator(Function *F, ScalarEvolution *SE, DominatorTree *DT)
      : F(F), SE(SE), DT(DT) {
    RecursiveCallSites.clear();
    ExternalCallSites.clear();
    ArgumentStrideInfo.clear();
    CompareInfoVec.clear();
    SwitchInfoVec.clear();
  }
  bool canEstimateRecursionDepth();
  std::pair<const SCEV *, const SCEV *>
  identifyRecursionDepthForCallSite(CallInst *);
};
} // namespace llvm
#endif
