LLVM  16.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  if (!Inst.getType()->isSized())
44  return false;
45 
46  const BasicBlock *BB = Inst.getParent();
47  for (const User *U : Inst.users()) {
48  const Instruction *UI = cast<Instruction>(U);
49  if (UI->getParent() != BB || isa<PHINode>(UI))
50  return true;
51  }
52  return false;
53 }
54 
55 static bool runPass(Function &F) {
56  // Insert all new allocas into entry block.
57  BasicBlock *BBEntry = &F.getEntryBlock();
58  assert(pred_empty(BBEntry) &&
59  "Entry block to function must not have predecessors!");
60 
61  // Find first non-alloca instruction and create insertion point. This is
62  // safe if block is well-formed: it always have terminator, otherwise
63  // we'll get and assertion.
64  BasicBlock::iterator I = BBEntry->begin();
65  while (isa<AllocaInst>(I)) ++I;
66 
67  CastInst *AllocaInsertionPoint = new BitCastInst(
69  Type::getInt32Ty(F.getContext()), "reg2mem alloca point", &*I);
70 
71  // Find the escaped instructions. But don't create stack slots for
72  // allocas in entry block.
73  std::list<Instruction*> WorkList;
74  for (Instruction &I : instructions(F))
75  if (!(isa<AllocaInst>(I) && I.getParent() == BBEntry) && valueEscapes(I))
76  WorkList.push_front(&I);
77 
78  // Demote escaped instructions
79  NumRegsDemoted += WorkList.size();
80  for (Instruction *I : WorkList)
81  DemoteRegToStack(*I, false, AllocaInsertionPoint);
82 
83  WorkList.clear();
84 
85  // Find all phi's
86  for (BasicBlock &BB : F)
87  for (auto &Phi : BB.phis())
88  WorkList.push_front(&Phi);
89 
90  // Demote phi nodes
91  NumPhisDemoted += WorkList.size();
92  for (Instruction *I : WorkList)
93  DemotePHIToStack(cast<PHINode>(I), AllocaInsertionPoint);
94 
95  return true;
96 }
97 
99  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
100  auto *LI = &AM.getResult<LoopAnalysis>(F);
102  bool Changed = runPass(F);
103  if (N == 0 && !Changed)
104  return PreservedAnalyses::all();
107  PA.preserve<LoopAnalysis>();
108  return PA;
109 }
110 
111 namespace {
112 struct RegToMemLegacy : public FunctionPass {
113  static char ID; // Pass identification, replacement for typeid
114  RegToMemLegacy() : FunctionPass(ID) {
116  }
117 
118  void getAnalysisUsage(AnalysisUsage &AU) const override {
121  }
122 
123  bool runOnFunction(Function &F) override {
124  if (F.isDeclaration() || skipFunction(F))
125  return false;
126  return runPass(F);
127  }
128 };
129 } // namespace
130 
131 char RegToMemLegacy::ID = 0;
132 INITIALIZE_PASS_BEGIN(RegToMemLegacy, "reg2mem",
133  "Demote all values to stack slots", false, false)
134 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
135 INITIALIZE_PASS_END(RegToMemLegacy, "reg2mem",
137 
138 // createDemoteRegisterToMemory - Provide an entry point to create this pass.
139 char &llvm::DemoteRegisterToMemoryID = RegToMemLegacy::ID;
141  return new RegToMemLegacy();
142 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::Type::isSized
bool isSized(SmallPtrSetImpl< Type * > *Visited=nullptr) const
Return true if it makes sense to take the size of this type.
Definition: Type.h:283
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::AArch64PACKey::ID
ID
Definition: AArch64BaseInfo.h:818
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:774
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:5256
Statistic.h
llvm::DemoteRegisterToMemoryID
char & DemoteRegisterToMemoryID
Definition: Reg2Mem.cpp:139
Local.h
to
Should compile to
Definition: README.txt:449
runPass
static bool runPass(Function &F)
Definition: Reg2Mem.cpp:55
llvm::RegToMemPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Reg2Mem.cpp:98
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:136
reg2mem
reg2mem
Definition: Reg2Mem.cpp:135
Reg2Mem.h
llvm::PassRegistry::getPassRegistry
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Definition: PassRegistry.cpp:24
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:306
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:705
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:140
llvm::initializeRegToMemLegacyPass
void initializeRegToMemLegacyPass(PassRegistry &)
llvm::AnalysisUsage::addPreservedID
AnalysisUsage & addPreservedID(const void *ID)
Definition: PassAnalysisSupport.h:88
llvm::Value::getType
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
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:430
runOnFunction
static bool runOnFunction(Function &F, bool PostInlining)
Definition: EntryExitInstrumenter.cpp:85
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:271
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:848
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:279
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:1268