LLVM  14.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/LLVMContext.h"
28 #include "llvm/IR/Module.h"
29 #include "llvm/IR/PassManager.h"
30 #include "llvm/InitializePasses.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Transforms/Scalar.h"
33 #include "llvm/Transforms/Utils.h"
36 #include <list>
37 using namespace llvm;
38 
39 #define DEBUG_TYPE "reg2mem"
40 
41 STATISTIC(NumRegsDemoted, "Number of registers demoted");
42 STATISTIC(NumPhisDemoted, "Number of phi-nodes demoted");
43 
44 static bool valueEscapes(const Instruction &Inst) {
45  const BasicBlock *BB = Inst.getParent();
46  for (const User *U : Inst.users()) {
47  const Instruction *UI = cast<Instruction>(U);
48  if (UI->getParent() != BB || isa<PHINode>(UI))
49  return true;
50  }
51  return false;
52 }
53 
54 static bool runPass(Function &F) {
55  // Insert all new allocas into entry block.
56  BasicBlock *BBEntry = &F.getEntryBlock();
57  assert(pred_empty(BBEntry) &&
58  "Entry block to function must not have predecessors!");
59 
60  // Find first non-alloca instruction and create insertion point. This is
61  // safe if block is well-formed: it always have terminator, otherwise
62  // we'll get and assertion.
63  BasicBlock::iterator I = BBEntry->begin();
64  while (isa<AllocaInst>(I)) ++I;
65 
66  CastInst *AllocaInsertionPoint = new BitCastInst(
68  Type::getInt32Ty(F.getContext()), "reg2mem alloca point", &*I);
69 
70  // Find the escaped instructions. But don't create stack slots for
71  // allocas in entry block.
72  std::list<Instruction*> WorkList;
73  for (Instruction &I : instructions(F))
74  if (!(isa<AllocaInst>(I) && I.getParent() == BBEntry) && valueEscapes(I))
75  WorkList.push_front(&I);
76 
77  // Demote escaped instructions
78  NumRegsDemoted += WorkList.size();
79  for (Instruction *I : WorkList)
80  DemoteRegToStack(*I, false, AllocaInsertionPoint);
81 
82  WorkList.clear();
83 
84  // Find all phi's
85  for (BasicBlock &BB : F)
86  for (auto &Phi : BB.phis())
87  WorkList.push_front(&Phi);
88 
89  // Demote phi nodes
90  NumPhisDemoted += WorkList.size();
91  for (Instruction *I : WorkList)
92  DemotePHIToStack(cast<PHINode>(I), AllocaInsertionPoint);
93 
94  return true;
95 }
96 
98  auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);
99  auto *LI = &AM.getResult<LoopAnalysis>(F);
101  bool Changed = runPass(F);
102  if (N == 0 && !Changed)
103  return PreservedAnalyses::all();
106  PA.preserve<LoopAnalysis>();
107  return PA;
108 }
109 
110 namespace {
111 struct RegToMemLegacy : public FunctionPass {
112  static char ID; // Pass identification, replacement for typeid
113  RegToMemLegacy() : FunctionPass(ID) {
115  }
116 
117  void getAnalysisUsage(AnalysisUsage &AU) const override {
120  }
121 
122  bool runOnFunction(Function &F) override {
123  if (F.isDeclaration() || skipFunction(F))
124  return false;
125  return runPass(F);
126  }
127 };
128 } // namespace
129 
130 char RegToMemLegacy::ID = 0;
131 INITIALIZE_PASS_BEGIN(RegToMemLegacy, "reg2mem",
132  "Demote all values to stack slots", false, false)
133 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
134 INITIALIZE_PASS_END(RegToMemLegacy, "reg2mem",
136 
137 // createDemoteRegisterToMemory - Provide an entry point to create this pass.
138 char &llvm::DemoteRegisterToMemoryID = RegToMemLegacy::ID;
140  return new RegToMemLegacy();
141 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::BasicBlock::iterator
InstListType::iterator iterator
Instruction iterators...
Definition: BasicBlock.h:90
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:779
Scalar.h
InstIterator.h
llvm::Function
Definition: Function.h:61
Pass.h
llvm::BitCastInst
This class represents a no-op cast from one type to another.
Definition: Instructions.h:5200
Statistic.h
llvm::DemoteRegisterToMemoryID
char & DemoteRegisterToMemoryID
Definition: Reg2Mem.cpp:138
Local.h
to
Should compile to
Definition: README.txt:449
Module.h
runPass
static bool runPass(Function &F)
Definition: Reg2Mem.cpp:54
llvm::RegToMemPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: Reg2Mem.cpp:97
llvm::Type::getInt32Ty
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:203
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::BasicBlock
LLVM Basic Block Representation.
Definition: BasicBlock.h:58
slots
Demote all values to stack slots
Definition: Reg2Mem.cpp:135
reg2mem
reg2mem
Definition: Reg2Mem.cpp:134
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:110
llvm::User
Definition: User.h:44
llvm::BasicBlock::begin
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:296
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:136
false
Definition: StackSlotColoring.cpp:142
llvm::Instruction
Definition: Instruction.h:45
valueEscapes
static bool valueEscapes(const Instruction &Inst)
Definition: Reg2Mem.cpp:44
llvm::STATISTIC
STATISTIC(NumFunctions, "Total number of functions")
Utils.h
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:699
INITIALIZE_PASS_DEPENDENCY
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:176
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:59
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::createDemoteRegisterToMemoryPass
FunctionPass * createDemoteRegisterToMemoryPass()
Definition: Reg2Mem.cpp:139
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:119
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:23
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:69
llvm::Constant::getNullValue
static Constant * getNullValue(Type *Ty)
Constructor to create a '0' constant of arbitrary type.
Definition: Constants.cpp:348
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
Function.h
PassManager.h
llvm::BreakCriticalEdgesID
char & BreakCriticalEdgesID
llvm::DominatorTreeAnalysis
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:252
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:744
Instructions.h
Dominators.h
N
#define N
llvm::Instruction::getParent
const BasicBlock * getParent() const
Definition: Instruction.h:94
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:44
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::AnalysisUsage::addRequiredID
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:267
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
LLVMContext.h
BasicBlockUtils.h
InitializePasses.h
llvm::Value::users
iterator_range< user_iterator > users()
Definition: Value.h:422
llvm::LoopAnalysis
Analysis pass that exposes the LoopInfo for a function.
Definition: LoopInfo.h:1243
llvm::Intrinsic::ID
unsigned ID
Definition: TargetTransformInfo.h:37