//===- LoopUnswitch.h - Hoist loop-invariant conditionals in loop -------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// 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 pass transforms loops that contain branches on loop-invariant conditions
// to multiple loops.  For example, it turns the left into the right code:
//
//  for (...)                  if (lic)
//    A                          for (...)
//    if (lic)                     A; B; C
//      B                      else
//    C                          for (...)
//                                 A; C
//
// This can increase the size of the code exponentially (doubling it every time
// a loop is unswitched) so we only unswitch if the resultant code will be
// smaller than a threshold.
//
// This pass expects LICM to be run before it to hoist invariant conditions out
// of the loop, to make the unswitching opportunity obvious.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_TRANSFORMS_SCALAR_LOOPUNSWITCH_H
#define LLVM_TRANSFORMS_SCALAR_LOOPUNSWITCH_H

#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/Transforms/Scalar/LoopPassManager.h"
#include <map>

extern cl::opt<unsigned> LoopUnswitchThreshold;

namespace {
  class LUAnalysisCache {
    using UnswitchedValsMap =
        DenseMap<const SwitchInst *, SmallPtrSet<const Value *, 8>>;
    using UnswitchedValsIt = UnswitchedValsMap::iterator;

    struct LoopProperties {
      unsigned CanBeUnswitchedCount;
      unsigned WasUnswitchedCount;
      unsigned SizeEstimation;
      UnswitchedValsMap UnswitchedVals;
    };

    bool LargeBlockUnswitch = false;

    // Stores the variables that are not profitable to be unswitched with
    // the new heuristic. The map is used in the subsequent encounters of the
    // of the same variable to prevent redundant counting of the already
    // visited variable.
    SmallPtrSet<const Value *, 32> notProfitableBranchConditionValues;

    // Here we use std::map instead of DenseMap, since we need to keep valid
    // LoopProperties pointer for current loop for better performance.
    using LoopPropsMap = std::map<const Loop *, LoopProperties>;
    using LoopPropsMapIt = LoopPropsMap::iterator;

    LoopPropsMap LoopsProperties;
    UnswitchedValsMap *CurLoopInstructions = nullptr;
    LoopProperties *CurrentLoopProperties = nullptr;

    // A loop unswitching with an estimated cost above this threshold
    // is not performed. MaxSize is turned into unswitching quota for
    // the current loop, and reduced correspondingly, though note that
    // the quota is returned by releaseMemory() when the loop has been
    // processed, so that MaxSize will return to its previous
    // value. So in most cases MaxSize will equal the Threshold flag
    // when a new loop is processed. An exception to that is that
    // MaxSize will have a smaller value while processing nested loops
    // that were introduced due to loop unswitching of an outer loop.
    //
    // FIXME: The way that MaxSize works is subtle and depends on the
    // pass manager processing loops and calling releaseMemory() in a
    // specific order. It would be good to find a more straightforward
    // way of doing what MaxSize does.
    unsigned MaxSize;

  public:
    LUAnalysisCache() : MaxSize(LoopUnswitchThreshold) {}

    // Analyze loop. Check its size, calculate is it possible to unswitch
    // it. Returns true if we can unswitch this loop.
    bool countLoop(const Loop *L, const TargetTransformInfo &TTI,
                   AssumptionCache *AC);

    // Clean all data related to given loop.
    void forgetLoop(const Loop *L);
    void reset();

    // Mark case value as unswitched.
    // Since SI instruction can be partly unswitched, in order to avoid
    // extra unswitching in cloned loops keep track all unswitched values.
    void setUnswitched(const SwitchInst *SI, const Value *V);

    // Check was this case value unswitched before or not.
    bool isUnswitched(const SwitchInst *SI, const Value *V);

    // Check if loop has large blocks that can be unswitched.
    bool isLargeBlockUnswitch();

    // If a variable is non-profitable with the new heuristic, add it
    // into the set.
    void addNotProfitableBranchConditionValue(Value *V) {
      notProfitableBranchConditionValues.insert(V);
    }

    // Check if the variable is already encountered and is non-profitable
    // with the new heuristic.
    bool isNotProfitableBranchConditionValue(Value *V) {
      return notProfitableBranchConditionValues.count(V);
    }

    // Returns true if another unswitching could be done within the cost
    // threshold.
    bool costAllowsUnswitching();

    // Clone all loop-unswitch related loop properties.
    // Redistribute unswitching quotas.
    // Note, that new loop data is stored inside the VMap.
    void cloneData(const Loop *NewLoop, const Loop *OldLoop,
                   const ValueToValueMapTy &VMap);
  };
} // end anonymous namespace

namespace llvm {

class LoopUnswitchPass : public PassInfoMixin<LoopUnswitchPass> {
	bool OptimizeForSize, HasBranchDivergence;
	LUAnalysisCache BranchesInfo;
	Loop *CurrentLoop = nullptr;
  bool EnableAggressiveLoopTransform;
  bool IgnoreLoopGuard = false;

	// FIXME: Not sure if this is ever invoked. It is an overridden function
  // in LoopUnswitchLegacyPass.
	void releaseMemory() { BranchesInfo.forgetLoop(CurrentLoop); }

public:
  LoopUnswitchPass(bool Os = false, bool HasBranchDivergence = false,
                   bool EnableAggressiveLoopTransform = true, bool IgnoreLoopGuard = false)
      : OptimizeForSize(Os), HasBranchDivergence(HasBranchDivergence),
        EnableAggressiveLoopTransform(EnableAggressiveLoopTransform), IgnoreLoopGuard(IgnoreLoopGuard) {}

  PreservedAnalyses run(LoopNest &LN, LoopAnalysisManager &AM,
                        LoopStandardAnalysisResults &AR, LPMUpdater &U);

};

} // end namespace llvm

#endif // LLVM_TRANSFORMS_SCALAR_LOOPUNSWITCH_H
