//===============            - AOCC Loop Utils -              ===============//
//
//                          AOCC Loop Utility Extentions
//
//===----------------------------------------------------------------------===//
//                     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.
//
//===----------------------------------------------------------------------===//
// This include the following utilities
// [1] Updates the loop bounds and introduce original bounds as guard checks
//     to cover loop
//===----------------------------------------------------------------------===//
#ifndef LLVM_UTILS_AOCC_H
#define LLVM_UTILS_AOCC_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 <map>

using namespace llvm;

namespace llvm {
// LoopBoundUpdateUtil
class LoopBoundUpdateUtil {
public:
  Loop *L;
  LoopInfo *LI;
  ScalarEvolution *SE;
  DominatorTree *DT;
  const DataLayout *DL;
  PHINode *Induction;
  const SCEV *InductionStart;
  bool fdivIS;
  const SCEV *InductionEnd;
  bool fdivIE;
  const SCEVConstant *Step;

  LoopBoundUpdateUtil(Loop *L, LoopInfo *LI, ScalarEvolution *SE,
                      DominatorTree *DT, const DataLayout *DL)
      : L(L), LI(LI), SE(SE), DT(DT), DL(DL), Induction(nullptr),
        InductionStart(nullptr), InductionEnd(nullptr), Step(nullptr) {}

  bool isLegalToUpdateLoopBounds();
  bool updateLoopBounds(const SCEV *Start, const SCEV *End);
};

enum class LoopPlacementStatus { Illegal, BlockSplitted, Legal };

class LoopPlacementUtils {
public:
  Loop *L;
  LoopInfo *LI;
  ScalarEvolution *SE;
  DominatorTree *DT;
  const DataLayout *DL;
  BasicBlock *GuardBlock;
  BasicBlock *PreHeader;
  BasicBlock *ExitBlock;
  BasicBlock *ExisSucc;
  BasicBlock *GuardPred;
  MapVector<Instruction *, bool> LoopLiveIns;
  MapVector<Instruction *, bool> LoopOutUsages;
  MapVector<BasicBlock *, bool> LoopPlacementBlock;
  LoopPlacementUtils(Loop *L, LoopInfo *LI, ScalarEvolution *SE,
                     DominatorTree *DT, const DataLayout *DL)
      : L(L), LI(LI), SE(SE), DT(DT), DL(DL), GuardBlock(nullptr),
        PreHeader(nullptr), ExitBlock(nullptr), ExisSucc(nullptr),
        GuardPred(nullptr) {
    LoopLiveIns.clear();
    LoopOutUsages.clear();
    LoopPlacementBlock.clear();
  }
  bool isLoopPlacementBlock(BasicBlock *BB) {
    return (LoopPlacementBlock.find(BB) != LoopPlacementBlock.end());
  }
  void collectLiveInsLiveOuts();
  void collectBlockLiveInsLiveOuts(BasicBlock *);
  bool isLegalLoopStructure();
  LoopPlacementStatus
  isLegalToPlaceLoop(std::pair<BasicBlock *, BasicBlock *> &Edge);
  void performLoopPlacement(std::pair<BasicBlock *, BasicBlock *> &Edge);
};

class LoopTileUtil {
  Function &F;
  ScalarEvolution *SE;
  LoopInfo *LI;
  DominatorTree *DT;

  Loop *L;
  Loop *OuterLoop;
  const SCEV *LB;
  bool fdivLB;
  const SCEV *UB;
  bool fdivUB;
  const SCEV * (*InnerLB) (void *, Value *, void *, Loop *, void *, bool &);
  const SCEV * (*InnerUB) (void *, Value *, void *, Loop *, void *, bool &);
  void * AST;
  void * Tile;
  void * Bldr;
  public: 
    LoopTileUtil(Function &F,DominatorTree *DT, Loop * L, Loop *OuterLoop, ScalarEvolution *SE, LoopInfo *LI, 
                 const SCEV *LB, bool fdivLB, const SCEV *UB, bool fdivUB,
                 const SCEV * (*InnerLB)(void *, Value *, void *, Loop *, void*, bool&),
                 const SCEV * (*InnerUB)(void *, Value *, void *, Loop *, void*, bool&),
                 void *AST, void *Tile, void *Bldr) : L(L), OuterLoop(OuterLoop), SE(SE), LI(LI),
                     F(F),DT(DT), LB(LB),fdivLB(fdivLB), UB(UB), fdivUB(fdivUB), InnerLB(InnerLB), InnerUB(InnerUB), AST(AST),
                     Tile(Tile), Bldr(Bldr) {}
    Loop * performTiling();

};
} // namespace llvm
#endif
