LoopRotationUtils.cpp | Explore in Territory

//===----------------- LoopRotationUtils.cpp -----------------------------===//
//
// 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
//
//===----------------------------------------------------------------------===//
//
// This file provides utilities to convert a loop into a loop with bottom test.
//
//===----------------------------------------------------------------------===//

#include "llvm/Transforms/Utils/LoopRotationUtils.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/AssumptionCache.h"
#include "llvm/Analysis/CodeMetrics.h"
#include "llvm/Analysis/DomTreeUpdater.h"
#include "llvm/Analysis/InstructionSimplify.h"
#include "llvm/Analysis/LoopInfo.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ScalarEvolution.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/CFG.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/IR/MDBuilder.h"
#include "llvm/IR/ProfDataUtils.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Transforms/Utils/SSAUpdater.h"
#include "llvm/Transforms/Utils/ValueMapper.h"
usingnamespacellvm;

#define DEBUG_TYPE …

STATISTIC(NumNotRotatedDueToHeaderSize,
          "Number of loops not rotated due to the header size");
STATISTIC(NumInstrsHoisted,
          "Number of instructions hoisted into loop preheader");
STATISTIC(NumInstrsDuplicated,
          "Number of instructions cloned into loop preheader");
STATISTIC(NumRotated, "Number of loops rotated");

static cl::opt<bool>
    MultiRotate("loop-rotate-multi", cl::init(false), cl::Hidden,
                cl::desc("Allow loop rotation multiple times in order to reach "
                         "a better latch exit"));

// Probability that a rotated loop has zero trip count / is never entered.
static constexpr uint32_t ZeroTripCountWeights[] = …;

namespace {
/// A simple loop rotation transformation.
class LoopRotate { … };
} // end anonymous namespace

/// Insert (K, V) pair into the ValueToValueMap, and verify the key did not
/// previously exist in the map, and the value was inserted.
static void InsertNewValueIntoMap(ValueToValueMapTy &VM, Value *K, Value *V) { … }
/// RewriteUsesOfClonedInstructions - We just cloned the instructions from the
/// old header into the preheader.  If there were uses of the values produced by
/// these instruction that were outside of the loop, we have to insert PHI nodes
/// to merge the two values.  Do this now.
static void RewriteUsesOfClonedInstructions(BasicBlock *OrigHeader,
                                            BasicBlock *OrigPreheader,
                                            ValueToValueMapTy &ValueMap,
                                            ScalarEvolution *SE,
                                SmallVectorImpl<PHINode*> *InsertedPHIs) { … }

// Assuming both header and latch are exiting, look for a phi which is only
// used outside the loop (via a LCSSA phi) in the exit from the header.
// This means that rotating the loop can remove the phi.
static bool profitableToRotateLoopExitingLatch(Loop *L) { … }

// Check that latch exit is deoptimizing (which means - very unlikely to happen)
// and there is another exit from the loop which is non-deoptimizing.
// If we rotate latch to that exit our loop has a better chance of being fully
// canonical.
//
// It can give false positives in some rare cases.
static bool canRotateDeoptimizingLatchExit(Loop *L) { … }

static void updateBranchWeights(BranchInst &PreHeaderBI, BranchInst &LoopBI,
                                bool HasConditionalPreHeader,
                                bool SuccsSwapped) { … }

/// Rotate loop LP. Return true if the loop is rotated.
///
/// \param SimplifiedLatch is true if the latch was just folded into the final
/// loop exit. In this case we may want to rotate even though the new latch is
/// now an exiting branch. This rotation would have happened had the latch not
/// been simplified. However, if SimplifiedLatch is false, then we avoid
/// rotating loops in which the latch exits to avoid excessive or endless
/// rotation. LoopRotate should be repeatable and converge to a canonical
/// form. This property is satisfied because simplifying the loop latch can only
/// happen once across multiple invocations of the LoopRotate pass.
///
/// If -loop-rotate-multi is enabled we can do multiple rotations in one go
/// so to reach a suitable (non-deoptimizing) exit.
bool LoopRotate::rotateLoop(Loop *L, bool SimplifiedLatch) { … }

/// Determine whether the instructions in this range may be safely and cheaply
/// speculated. This is not an important enough situation to develop complex
/// heuristics. We handle a single arithmetic instruction along with any type
/// conversions.
static bool shouldSpeculateInstrs(BasicBlock::iterator Begin,
                                  BasicBlock::iterator End, Loop *L) { … }

/// Fold the loop tail into the loop exit by speculating the loop tail
/// instructions. Typically, this is a single post-increment. In the case of a
/// simple 2-block loop, hoisting the increment can be much better than
/// duplicating the entire loop header. In the case of loops with early exits,
/// rotation will not work anyway, but simplifyLoopLatch will put the loop in
/// canonical form so downstream passes can handle it.
///
/// I don't believe this invalidates SCEV.
bool LoopRotate::simplifyLoopLatch(Loop *L) { … }

/// Rotate \c L, and return true if any modification was made.
bool LoopRotate::processLoop(Loop *L) { … }


/// The utility to convert a loop into a loop with bottom test.
bool llvm::LoopRotation(Loop *L, LoopInfo *LI, const TargetTransformInfo *TTI,
                        AssumptionCache *AC, DominatorTree *DT,
                        ScalarEvolution *SE, MemorySSAUpdater *MSSAU,
                        const SimplifyQuery &SQ, bool RotationOnly = true,
                        unsigned Threshold = unsigned(-1),
                        bool IsUtilMode = true, bool PrepareForLTO) { … }
llvm/llvm/lib/Transforms/Utils/LoopRotationUtils.cpp
