LLVM  15.0.0git
Reg2Mem.cpp
Go to the documentation of this file.
1 //===- Reg2Mem.cpp - Convert registers to allocas -------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file demotes all registers to memory references. It is intended to be
10 // the inverse of PromoteMemoryToRegister. By converting to loads, the only
11 // values live across basic blocks are allocas and loads before phi nodes.
12 // It is intended that this should make CFG hacking much easier.
13 // To make later hacking easier, the entry block is split into two, such that
14 // all introduced allocas and nothing else are in the entry block.
15 //
16 //===----------------------------------------------------------------------===//
17 
19 #include "llvm/ADT/Statistic.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/Dominators.h"
24 #include "llvm/IR/Function.h"
25 #include "llvm/IR/InstIterator.h"
26 #include "llvm/IR/Instructions.h"
27 #include "llvm/IR/PassManager.h"
28 #include "llvm/InitializePasses.h"
29 #include "llvm/Pass.h"
30 #include "llvm/Transforms/Scalar.h"
31 #include "llvm/Transforms/Utils.h"
34 #include <list>
35 using namespace llvm;
36 
37 #define DEBUG_TYPE "reg2mem"
38 
39 STATISTIC(NumRegsDemoted, "Number of registers demoted");
40 STATISTIC(NumPhisDemoted, "Number of phi-nodes demoted");
41 
42 static bool valueEscapes(const Instruction &Inst) {
43  const BasicBlock *BB = Inst.getParent();
44  for (const User *U : Inst.users()) {
45  const Instruction *UI = cast<Instruction>(U);
46  if (UI->getParent() != BB || isa<PHINode>(UI))
47  return true;
48  }
49  return false;
50 }
51 
52 static bool runPass(Function &F) {
53  // Insert all new allocas into entry block.
54  BasicBlock *BBEntry = &F.getEntryBlock();
55  assert(pred_empty(BBEntry) &&
56  "Entry block to function must not have predecessors!");
57 
58  // Find first non-alloca instruction and create insertion point. This is
59  // safe if block is well-formed: it always have terminator, otherwise
60  // we'll get and assertion.
61  BasicBlock::iterator I = BBEntry->begin();
62  while (isa<AllocaInst>(I)) ++I;
63 
64  CastInst *AllocaInsertionPoint = new BitCastInst(
66  Type::getInt32Ty(F.getContext()), "reg2mem alloca point", &*I);
67 
68  // Find the escaped instructions. But don't create stack slots for
69  // allocas in entry block.
70  std::list<Instruction*> WorkList;
71  for (Instruction &I : instructions(F))
72  if (!(isa<AllocaInst>(I) && I.getParent() == BBEntry) && valueEscapes(I))
73  WorkList.push_front(&I);
74 
75  // Demote escaped instructions
76  NumRegsDemoted += WorkList.size();
77  for (Instruction *I : WorkList)
78  DemoteRegToStack(*I, false, AllocaInsertionPoint);
79 
80  WorkList.clear();
81 
82  // Find all phi's
83  for (BasicBlock &BB : F)
84  for (auto &Phi : BB.phis())
85  WorkList.push_front(&Phi);
86 
87  // Demote phi nodes
88  NumPhisDemoted += WorkList.size();
89  for (Instruction *I : WorkList)
90  DemotePHIToStack(cast<PHINode>(I), AllocaInsertionPoint);
91 
92  return true;
93 }
94 
96  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
97  auto *LI = &AM.getResult<LoopAnalysis>(F);
99  bool Changed = runPass(F);
100  if (N == 0 && !Changed)
101  return PreservedAnalyses::all();
104  PA.preserve<LoopAnalysis>();
105  return PA;
106 }
107 
108 namespace {
109 struct RegToMemLegacy : public FunctionPass {
110  static char ID; // Pass identification, replacement for typeid
111  RegToMemLegacy() : FunctionPass(ID) {
113  }
114 
115  void getAnalysisUsage(AnalysisUsage &AU) const override {
118  }
119 
120  bool runOnFunction(Function &F) override {
121  if (F.isDeclaration() || skipFunction(F))
122  return false;
123  return runPass(F);
124  }
125 };
126 } // namespace
127 
128 char RegToMemLegacy::ID = 0;
129 INITIALIZE_PASS_BEGIN(RegToMemLegacy, "reg2mem",
130  "Demote all values to stack slots", false, false)
131 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
132 INITIALIZE_PASS_END(RegToMemLegacy, "reg2mem",
134 
135 // createDemoteRegisterToMemory - Provide an entry point to create this pass.
136 char &llvm::DemoteRegisterToMemoryID = RegToMemLegacy::ID;
138  return new RegToMemLegacy();
139 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:17
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:87
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:780
Scalar.h
InstIterator.h
llvm::Function
Definition: Function.h:60
Pass.h
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5212
Statistic.h
llvm::DemoteRegisterToMemoryID
char & DemoteRegisterToMemoryID
Definition: Reg2Mem.cpp:136
Local.h
to
Should compile to
Definition: README.txt:449
runPass
static bool runPass(Function &F)
Definition: Reg2Mem.cpp:52
llvm::RegToMemPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Reg2Mem.cpp:95
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:239
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:55
slots
Demote all values to stack slots
Definition: Reg2Mem.cpp:133
reg2mem
reg2mem
Definition: Reg2Mem.cpp:132
Reg2Mem.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:31
llvm::DemotePHIToStack
AllocaInst * DemotePHIToStack(PHINode *P, Instruction *AllocaPoint=nullptr)
This function takes a virtual register computed by a phi node and replaces it with a slot in the stac...
Definition: DemoteRegToStack.cpp:109
llvm::User
Definition: User.h:44
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:297
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::CriticalEdgeSplittingOptions
Option class for critical edge splitting.
Definition: BasicBlockUtils.h:142
false
Definition: StackSlotColoring.cpp:141
llvm::Instruction
Definition: Instruction.h:42
valueEscapes
static bool valueEscapes(const Instruction &Inst)
Definition: Reg2Mem.cpp:42
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
Utils.h
llvm::CallingConv::ID
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
Definition: CallingConv.h:24
INITIALIZE_PASS_END
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
Definition: PassSupport.h:58
CFG.h
LoopInfo.h
INITIALIZE_PASS_BEGIN
INITIALIZE_PASS_BEGIN(RegToMemLegacy, "reg2mem", "Demote all values to stack slots", false, false) INITIALIZE_PASS_END(RegToMemLegacy
BasicBlock.h
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::cl::values
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:685
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::LegalityPredicates::all
Predicate all(Predicate P0, Predicate P1)
True iff P0 and P1 are true.
Definition: LegalizerInfo.h:228
I
#define I(x, y, z)
Definition: MD5.cpp:58
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::createDemoteRegisterToMemoryPass
FunctionPass * createDemoteRegisterToMemoryPass()
Definition: Reg2Mem.cpp:137
llvm::initializeRegToMemLegacyPass
void initializeRegToMemLegacyPass(PassRegistry &)
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
llvm::pred_empty
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:118
llvm::DemoteRegToStack
AllocaInst * DemoteRegToStack(Instruction &X, bool VolatileLoads=false, Instruction *AllocaPoint=nullptr)
This function takes a virtual register computed by an Instruction and replaces it with a slot in the ...
Definition: DemoteRegToStack.cpp:22
llvm::CastInst
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:429
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:69
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:350
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
Function.h
PassManager.h
llvm::BreakCriticalEdgesID
char & BreakCriticalEdgesID
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:267
llvm::SplitAllCriticalEdges
unsigned SplitAllCriticalEdges(Function &F, const CriticalEdgeSplittingOptions &Options=CriticalEdgeSplittingOptions())
Loop over all of the edges in the CFG, breaking critical edges as they are found.
Definition: BasicBlockUtils.cpp:767
Instructions.h
Dominators.h
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:91
stack
S is passed via registers r2 But gcc stores them to the stack
Definition: README.txt:189
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:277
BB
Common register allocation spilling lr str ldr sxth r3 ldr mla r4 can lr mov lr str ldr sxth r3 mla r4 and then merge mul and lr str ldr sxth r3 mla r4 It also increase the likelihood the store may become dead bb27 Successors according to LLVM BB
Definition: README.txt:39
BasicBlockUtils.h
InitializePasses.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:421
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1262
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:38