//===============      - LoopInductionAccesses.h -             ===============//
// This utility analysis track the induction variable usage inside the loop
// The access of interest are mostly binary operations on induction with
// a known constant or a loop invariant expression
//===----------------------------------------------------------------------===//
//                     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.
//
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
#ifndef LLVM_UTILS_LOOPINDUCTIONACCESSES_H
#define LLVM_UTILS_LOOPINDUCTIONACCESSES_H
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/StringExtras.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ScalarEvolutionExpressions.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/DerivedTypes.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/InstIterator.h"
#include "llvm/IR/InstrTypes.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/Module.h"
#include "llvm/IR/TypeFinder.h"
#include "llvm/IR/ValueSymbolTable.h"
#include "llvm/Pass.h"
#include "llvm/Support/Debug.h"

namespace llvm {

// Captures loop induction and its related access
class LoopInductionAccesses {
private:
  Loop *L;
  LoopInfo *LI;
  ScalarEvolution *SE;
  PHINode *Induction;
  bool HasUniqueInduction;

  MapVector<const Value *, bool> LoopInductionAccess;
  // Adds the value as loop induction access
  void addLoopInductionAccess(const Value *V);
  // Collects the induction and its related usages
  void collectInductionRelatedUsage(Value *V, Loop *L, bool AcrossFunction,
                                    MapVector<const Value *, bool> &Visitor);
  // Process the loop for induction and its related access collection
  void processLoop();

public:
  LoopInductionAccesses(Loop *L, LoopInfo *LI, ScalarEvolution *SE)
      : L(L), LI(LI), SE(SE), Induction(nullptr), HasUniqueInduction(true) {
    LoopInductionAccess.clear();
    processLoop();
  }
  // Return true if the value is loop induction or related access
  bool isLoopInductionAccess(const Value *V);
  // Return true if the loop has unique induction variable
  bool hasUniqueInduction() { return HasUniqueInduction; }
  // Return loop induction variable
  PHINode *getInduction() { return Induction; }
  // Return the current loop
  Loop *getLoop() { return L; }
};

// Return true if the value is loop invariant or constant
// else return false
bool isLoopInvariantOrConstant(Value *V, Loop *L, ScalarEvolution *SE,
                               bool AcrossFunction);
} // namespace llvm
#endif
