//===============            - LoopSplitUtils.h -              ===============//
// Splits the itertion space based on conditions in the specified partitions
//
//===----------------------------------------------------------------------===//
//                     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_LOOPSPILIT_H
#define LLVM_UTILS_LOOPSPILIT_H
#include "llvm/Analysis/LoopInductionAccesses.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/IPO.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Analysis/CFG.h"
#include <map>

using namespace llvm;

namespace llvm {
// Information of an PHINode at the start and the end of a paticular partition
class PHIInfo {
private:
  PHINode *PN;
  Value *Start;
  Value *End;

public:
  PHIInfo(PHINode *PN) : PN(PN) {}
  // Returns the starting value for PHINode
  Value *getStart() { return Start; }
  // Returns the ending value for PHINode
  Value *getEnd() { return End; }
  // Captures the starting value for the PHINode
  void setStart(Value *S) { Start = S; }
  // Captures the ending value for the PHINode
  void setEnd(Value *E) { End = E; }
};

// Container for the Partition
class Partition {
private:
  const SCEV *Start;
  const SCEV *End;
  Loop *PartitionLoop;

public:
  ValueToValueMapTy VMap;
  MapVector<PHINode *, PHIInfo *> PHIInformation;
  MapVector<Instruction *, PHINode *> OutsideUsageList;
  Partition(const SCEV *Start, const SCEV *End)
      : Start(Start), End(End), PartitionLoop(nullptr) {
    VMap.clear();
    PHIInformation.clear();
    OutsideUsageList.clear();
  }
  // Destructor: Deletes the allocated memory
  ~Partition() {
    for (auto &Itr : PHIInformation)
      delete Itr.second;
  }
  // Copy and update outside usage from existing map
  void copyOutsideUsage(MapVector<Instruction *, PHINode *> &UsageList);
  // Create outside usage list, from previous partition info
  void createOutsideUsageList(Partition *PrevPart);
  // The range start SCEV for the partition
  const SCEV *getStart() { return Start; }
  // The range end SCEV for the partition
  const SCEV *getEnd() { return End; }
  // Create and return the PHIInfo for the PHINode
  PHIInfo *createPHIInfo(PHINode *PN) {
    PHIInfo *PI = new PHIInfo(PN);
    PHIInformation[PN] = PI;
    return PI;
  }
  // Returns the PHIInfo for the PHINode
  PHIInfo *getPHIInfo(PHINode *PN) {
    auto Itr = PHIInformation.find(PN);
    if (Itr != PHIInformation.end())
      return Itr->second;
    return nullptr;
  }
  // Set the PartitionLoop
  void setPartitionLoop(Loop *L) { PartitionLoop = L; }
  // Get the loop which partition actually represent
  Loop *getPartitionLoop() { return PartitionLoop; }
  // Prints the partition range
  void printPartition() {
    dbgs() << "  Partition Range: \n";
    dbgs() << "    Start: " << *Start << "\n";
    dbgs() << "    End:   " << *End << "\n";
  }
};

class LoopSplitUtils {
private:
  Loop *L;
  ScalarEvolution *SE;
  DominatorTree *DT;
  const DataLayout *DL;
  LoopInfo *LI;
  LoopInductionAccesses *LIA;
  const SCEV *InductionStart;
  const SCEV *InductionEnd;
  MapVector<unsigned, Partition *> Partitions;
  MapVector<Instruction *, PHINode *> OutSideUsage;
  std::map<PHINode *, PHINode *> FinalPHIMapping;
  std::map<Value *, PHINode *> FinalNonPHIMapping;
  SmallVector<Instruction *, 2> LoopValueOutsideAccess;
  bool MultiExitLoop;
  // Return the induction variable involved in loop exit check
  Value *getInvolvedInductionInLoopExit();
  // Update the partition PHI information
  void updatePartitionPHIInfo(Loop *L, Partition *P);
  // Prepare the loop for loop splitting by getting it in the right form
  bool prepareForLoopSplit();
  // Prepare the loop for loop splitting by getting it in the right form
  bool prepareForLoopSplitWithoutRTCheck();
  // Return true if the inst part of current loop, else return false
  bool instPartOfLoop(Instruction *I);
  // getExitBlock returns nullptr if the loop has multiple exit blocks. This
  // function returns the same exit block for single exit loops, and returns
  // the exit block to which the multi-exit loop exits from the loop latch.
  BasicBlock *getLatchExitBlock(Loop*);
public:
  LoopSplitUtils(Loop *L, ScalarEvolution *SE, DominatorTree *DT,
                 const DataLayout *DL, LoopInfo *LI,
                 bool MultiExitLoop = false)
      : L(L), SE(SE), DT(DT), DL(DL), LI(LI), LIA(nullptr),
        InductionStart(nullptr), InductionEnd(nullptr),
        MultiExitLoop(MultiExitLoop) {
    Partitions.clear();
    OutSideUsage.clear();
    FinalPHIMapping.clear();
    FinalNonPHIMapping.clear();
    LoopValueOutsideAccess.clear();
    LIA = new LoopInductionAccesses(L, LI, SE);
  }
  ~LoopSplitUtils() {
    if(LIA) {
      delete LIA;
    }
  }
  // Returns the unique induction variable
  PHINode *getInduction() { return LIA->getInduction(); }
  // Add partition with a specific PartitionNumber
  void addPartition(Partition *P, unsigned PartitionNumber);
  // Return the number of partitions
  unsigned getNumOfPartitions() { return Partitions.size(); }
  // Return partition with specific PartitionNumber
  Partition *getPartition(unsigned PartitionNumber);
  // Splits the loop
  bool performLoopSplitting();
  // Splits the loop without RT checks
  bool performLoopSplittingWithoutRTCheck();
  // Returns true if its legal to perform loop splitting
  bool isLegalForItrSplitting();
  // Backedge taken count turns out to be notAbleToCompute in case of a complex
  // multi exiting loop. This function tries to compute backedge taken count
  // for such kind of a loop for it's exit through the loop latch.
  // This is a bypass to compute the SCEV.
  const SCEV* getBackedgeTCforMultiExitLoop();
  // Return LoopInductionAccesses
  LoopInductionAccesses *getLoopInductionAccesses();
  // Return the mapping instruction from the input partition number
  Instruction* getClonedInstruction(Instruction *I, int PartitionNum);
};
} // namespace llvm
#endif
