//===------------- LoopFuse.h - Loop Fusion Utility -----------------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
/// Fuse two adjacent loops to improve cache locality.
//
//===----------------------------------------------------------------------===//
//====  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_TRANSFORMS_SCALAR_LOOPFUSEAOCC_H
#define LLVM_TRANSFORMS_SCALAR_LOOPFUSEAOCC_H

#include "llvm/ADT/DepthFirstIterator.h"
#include "llvm/ADT/EquivalenceClasses.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/LoopAccessAnalysis.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Verifier.h"
#include "llvm/InitializePasses.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
#include "llvm/Transforms/Utils/LoopVersioning.h"
#include <list>
#include <map>

namespace llvmamd {
  using namespace llvm;
/// \brief Loop Fuse utility class.
class LoopFuseBase {
public:
  // Kind of fusion made.
  enum Kind {
    NO_FUSION = 0,   // Fusion was not made even to check dependence legality.
                     // This is when loops had failed basic structure checks.
    REVERTED_FUSION, // Fusion was reverted due to failed dependence legality.
    PURE_FUSION,     // Fusion succeeded with removal of original loops.
    VERSIONED_FUSION // Fusion succeeded with versioning due to runtime checks.
  };

private:
  // Analyses used.
  LoopInfo *LI;
//  LoopAccessAnalysis *LAA;
  LoopAccessLegacyAnalysis *LAA;
  DominatorTree *DT;
  ScalarEvolution *SE;

  // FusionSwitcher - Branch instruction that controls switching between
  // original and fused versions. This gets initialized to true when loops are
  // multiversioned to check fusion legality. By default, it points to original
  // version.
  BranchInst *FusionSwitcher;

  Loop *FusedLoop;

  // LAI for FusedLoop.
  const LoopAccessInfo *LAI;

  // Kind of fusion that happened.
  Kind FusionKind;

  // CustomVMap: VMap of BBs for fused loop. The problem about having
  // ValueToValueMapTy passed from a client is that it gets updated when the
  // loops are removed based on fusion success and this is undesirable. Also
  // a ValueToValueMapTy is used when both Values are present. So, only a
  // normal llvm::Value* is maintained as map's value in contrast with
  // ValueToValueMapTy's WeakVH. Clients can use this mapping as a VMap.
  typedef std::map<const Value *, Value *> CustomVMap;
  CustomVMap VMap;

  // Rewrite IncomingBlocks in PHIs of @Br's successor blocks from Br's parent
  // to @To.
  void RewritePHI(BranchInst *Br, BasicBlock *To);

  // Fuse loops - @L1 and @L2 and return the fused loop.
  Loop *FuseLoops(Loop &L1, Loop &L2);

  // Legality and profitability checks.
  bool DependenceLegal(Loop &L1, Loop &L2);
  bool DefsUsedAcrossLoops(Loop &L1, Loop &L2);
  bool IsLegalAndProfitable(Loop &L1, Loop &L2);

  // Removal routines based on fusion success.
  void RemoveLoopCompletelyWithPreheader(Loop &L);
  void RemoveFusionSwitcher(Loop &L);

  // Outside use updates.
  void UpdateUsesOutsideLoop(Loop &L);
  void AddPHIsOutsideLoop(Loop &L, BasicBlock *OrigIncomingBlock);

public:
  // Initialization interface for LoopFuseBase class.
  LoopFuseBase(LoopInfo *_LI, LoopAccessLegacyAnalysis *_LAA, DominatorTree *_DT,
               ScalarEvolution *_SE)
      : LI(_LI), LAA(_LAA), DT(_DT), SE(_SE) {}

  Loop *getFusedLoop() { return FusedLoop; }

  const CustomVMap &getVMap() { return VMap; }

  unsigned getFusionKind() { return FusionKind; }
  void revertFusion(Loop &L1, Loop &L2);
  bool fuse(Loop &L1, Loop &L2, bool AllowRuntimeChecks = true);
};
}

namespace llvm {
class LoopFuse : public FunctionPass {
public:
  LoopFuse() : FunctionPass(ID) {
    initializeLoopFusePass(*PassRegistry::getPassRegistry());
  }

  bool runOnFunction(Function &F) override;

  void getAnalysisUsage(AnalysisUsage &AU) const override {
    AU.addRequired<LoopInfoWrapperPass>();
    AU.addRequired<LoopAccessLegacyAnalysis>();
    AU.addRequired<DominatorTreeWrapperPass>();
    AU.addRequired<ScalarEvolutionWrapperPass>();

    AU.addPreserved<LoopInfoWrapperPass>();
    AU.addPreserved<DominatorTreeWrapperPass>();
    AU.addPreserved<ScalarEvolutionWrapperPass>();
  }

  static char ID;
};
} // anonymous namespace

#endif
