//===------------- LoopUnrotate.h - Loop Unrotate Utility -----------------===//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
/// Unrotate a loop by moving the loop condition from latch to header. Also
/// remove the `if' condition guarding the loop entry.
//
//===----------------------------------------------------------------------===//
//====  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/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 "llvm/Analysis/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/PostDominators.h"
#include <list>

namespace llvm {
class LoopUnrotate : public FunctionPass {
private:
  bool LoopInstsUsedOutside(const Loop *L);

  Value* isCompatibleBranch(PHINode *P, const Loop *L, ScalarEvolution *SE);
  BranchInst* isCompatiblePreCond(const Loop *L, Value *LB, Value *UB,
                                  LoopInfo *LI, PostDominatorTree *PDT, ScalarEvolution *SE);

  void UnrotateLoop(PHINode *P, Value *UB, Loop *L, BranchInst *PreBr,
                    DominatorTree *DT, LoopInfo *LI, ScalarEvolution *SE);

public:
  LoopUnrotate() : FunctionPass(ID) {
    initializeLoopUnrotatePass(*PassRegistry::getPassRegistry());
  }

  bool Unrotate(Loop *L, DominatorTree *DT, PostDominatorTree *PDT, LoopInfo *LI,
                ScalarEvolution *SE,OptimizationRemarkEmitter *ORE,
                bool checkUnrotatedSubLoops = true);

  bool runOnFunction(Function &F) override;

  static bool isSimpleHeader(Loop *L);

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

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

  static char ID;
};
} // anonymous namespace
