blob: 9a5dba219cee506ca31023f29ed4ca599230fdf9 [file] [log] [blame]
//===-- MoveAutoInit.cpp - move auto-init inst closer to their use site----===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
// This pass moves instruction maked as auto-init closer to the basic block that
// use it, eventually removing it from some control path of the function.
#include "llvm/Transforms/Utils/MoveAutoInit.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/MemorySSA.h"
#include "llvm/Analysis/MemorySSAUpdater.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/IR/DebugInfo.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/IRBuilder.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/IntrinsicInst.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Transforms/Utils.h"
#include "llvm/Transforms/Utils/LoopUtils.h"
using namespace llvm;
#define DEBUG_TYPE "move-auto-init"
STATISTIC(NumMoved, "Number of instructions moved");
static cl::opt<unsigned> MoveAutoInitThreshold(
"move-auto-init-threshold", cl::Hidden, cl::init(128),
cl::desc("Maximum instructions to analyze per moved initialization"));
static bool hasAutoInitMetadata(const Instruction &I) {
return I.hasMetadata(LLVMContext::MD_annotation) &&
[](const MDOperand &Op) { return Op.equalsStr("auto-init"); });
static std::optional<MemoryLocation> writeToAlloca(const Instruction &I) {
MemoryLocation ML;
if (auto *MI = dyn_cast<MemIntrinsic>(&I))
ML = MemoryLocation::getForDest(MI);
else if (auto *SI = dyn_cast<StoreInst>(&I))
ML = MemoryLocation::get(SI);
return std::nullopt;
if (isa<AllocaInst>(getUnderlyingObject(ML.Ptr)))
return ML;
return {};
/// Finds a BasicBlock in the CFG where instruction `I` can be moved to while
/// not changing the Memory SSA ordering and being guarded by at least one
/// condition.
static BasicBlock *usersDominator(const MemoryLocation &ML, Instruction *I,
DominatorTree &DT, MemorySSA &MSSA) {
BasicBlock *CurrentDominator = nullptr;
MemoryUseOrDef &IMA = *MSSA.getMemoryAccess(I);
BatchAAResults AA(MSSA.getAA());
SmallPtrSet<MemoryAccess *, 8> Visited;
auto AsMemoryAccess = [](User *U) { return cast<MemoryAccess>(U); };
SmallVector<MemoryAccess *> WorkList(map_range(IMA.users(), AsMemoryAccess));
while (!WorkList.empty()) {
MemoryAccess *MA = WorkList.pop_back_val();
if (!Visited.insert(MA).second)
if (Visited.size() > MoveAutoInitThreshold)
return nullptr;
bool FoundClobberingUser = false;
if (auto *M = dyn_cast<MemoryUseOrDef>(MA)) {
Instruction *MI = M->getMemoryInst();
// If this memory instruction may not clobber `I`, we can skip it.
// LifetimeEnd is a valid user, but we do not want it in the user
// dominator.
if (AA.getModRefInfo(MI, ML) != ModRefInfo::NoModRef &&
!MI->isLifetimeStartOrEnd() && MI != I) {
FoundClobberingUser = true;
CurrentDominator = CurrentDominator
? DT.findNearestCommonDominator(CurrentDominator,
: MI->getParent();
if (!FoundClobberingUser) {
auto UsersAsMemoryAccesses = map_range(MA->users(), AsMemoryAccess);
append_range(WorkList, UsersAsMemoryAccesses);
return CurrentDominator;
static bool runMoveAutoInit(Function &F, DominatorTree &DT, MemorySSA &MSSA) {
BasicBlock &EntryBB = F.getEntryBlock();
SmallVector<std::pair<Instruction *, BasicBlock *>> JobList;
// Compute movable instructions.
for (Instruction &I : EntryBB) {
if (!hasAutoInitMetadata(I))
std::optional<MemoryLocation> ML = writeToAlloca(I);
if (!ML)
if (I.isVolatile())
BasicBlock *UsersDominator = usersDominator(ML.value(), &I, DT, MSSA);
if (!UsersDominator)
if (UsersDominator == &EntryBB)
// Traverse the CFG to detect cycles `UsersDominator` would be part of.
SmallPtrSet<BasicBlock *, 8> TransitiveSuccessors;
SmallVector<BasicBlock *> WorkList(successors(UsersDominator));
bool HasCycle = false;
while (!WorkList.empty()) {
BasicBlock *CurrBB = WorkList.pop_back_val();
if (CurrBB == UsersDominator)
// No early exit because we want to compute the full set of transitive
// successors.
HasCycle = true;
for (BasicBlock *Successor : successors(CurrBB)) {
if (!TransitiveSuccessors.insert(Successor).second)
// Don't insert if that could create multiple execution of I,
// but we can insert it in the non back-edge predecessors, if it exists.
if (HasCycle) {
BasicBlock *UsersDominatorHead = UsersDominator;
while (BasicBlock *UniquePredecessor =
UsersDominatorHead = UniquePredecessor;
if (UsersDominatorHead == &EntryBB)
BasicBlock *DominatingPredecessor = nullptr;
for (BasicBlock *Pred : predecessors(UsersDominatorHead)) {
// If one of the predecessor of the dominator also transitively is a
// successor, moving to the dominator would do the inverse of loop
// hoisting, and we don't want that.
if (TransitiveSuccessors.count(Pred))
if (!DT.isReachableFromEntry(Pred))
DominatingPredecessor =
? DT.findNearestCommonDominator(DominatingPredecessor, Pred)
: Pred;
if (!DominatingPredecessor || DominatingPredecessor == &EntryBB)
UsersDominator = DominatingPredecessor;
// CatchSwitchInst blocks can only have one instruction, so they are not
// good candidates for insertion.
while (isa<CatchSwitchInst>(UsersDominator->getFirstNonPHI())) {
for (BasicBlock *Pred : predecessors(UsersDominator))
if (DT.isReachableFromEntry(Pred))
UsersDominator = DT.findNearestCommonDominator(UsersDominator, Pred);
// We finally found a place where I can be moved while not introducing extra
// execution, and guarded by at least one condition.
if (UsersDominator != &EntryBB)
JobList.emplace_back(&I, UsersDominator);
// Perform the actual substitution.
if (JobList.empty())
return false;
MemorySSAUpdater MSSAU(&MSSA);
// Reverse insertion to respect relative order between instructions:
// if two instructions are moved from the same BB to the same BB, we insert
// the second one in the front, then the first on top of it.
for (auto &Job : reverse(JobList)) {
Job.first->moveBefore(*Job.second, Job.second->getFirstInsertionPt());
MSSAU.moveToPlace(MSSA.getMemoryAccess(Job.first), Job.first->getParent(),
if (VerifyMemorySSA)
NumMoved += JobList.size();
return true;
PreservedAnalyses MoveAutoInitPass::run(Function &F,
FunctionAnalysisManager &AM) {
auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
auto &MSSA = AM.getResult<MemorySSAAnalysis>(F).getMSSA();
if (!runMoveAutoInit(F, DT, MSSA))
return PreservedAnalyses::all();
PreservedAnalyses PA;
return PA;