LLVM  7.0.0svn
Reg2Mem.cpp
Go to the documentation of this file.
1 //===- Reg2Mem.cpp - Convert registers to allocas -------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file demotes all registers to memory references. It is intended to be
11 // the inverse of PromoteMemoryToRegister. By converting to loads, the only
12 // values live across basic blocks are allocas and loads before phi nodes.
13 // It is intended that this should make CFG hacking much easier.
14 // To make later hacking easier, the entry block is split into two, such that
15 // all introduced allocas and nothing else are in the entry block.
16 //
17 //===----------------------------------------------------------------------===//
18 
19 #include "llvm/ADT/Statistic.h"
21 #include "llvm/IR/BasicBlock.h"
22 #include "llvm/IR/CFG.h"
23 #include "llvm/IR/Function.h"
24 #include "llvm/IR/Instructions.h"
25 #include "llvm/IR/LLVMContext.h"
26 #include "llvm/IR/Module.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Transforms/Scalar.h"
29 #include "llvm/Transforms/Utils.h"
30 #include <list>
31 using namespace llvm;
32 
33 #define DEBUG_TYPE "reg2mem"
34 
35 STATISTIC(NumRegsDemoted, "Number of registers demoted");
36 STATISTIC(NumPhisDemoted, "Number of phi-nodes demoted");
37 
38 namespace {
39  struct RegToMem : public FunctionPass {
40  static char ID; // Pass identification, replacement for typeid
41  RegToMem() : FunctionPass(ID) {
43  }
44 
45  void getAnalysisUsage(AnalysisUsage &AU) const override {
48  }
49 
50  bool valueEscapes(const Instruction *Inst) const {
51  const BasicBlock *BB = Inst->getParent();
52  for (const User *U : Inst->users()) {
53  const Instruction *UI = cast<Instruction>(U);
54  if (UI->getParent() != BB || isa<PHINode>(UI))
55  return true;
56  }
57  return false;
58  }
59 
60  bool runOnFunction(Function &F) override;
61  };
62 }
63 
64 char RegToMem::ID = 0;
65 INITIALIZE_PASS_BEGIN(RegToMem, "reg2mem", "Demote all values to stack slots",
66  false, false)
67 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
68 INITIALIZE_PASS_END(RegToMem, "reg2mem", "Demote all values to stack slots",
69  false, false)
70 
71 bool RegToMem::runOnFunction(Function &F) {
72  if (F.isDeclaration() || skipFunction(F))
73  return false;
74 
75  // Insert all new allocas into entry block.
76  BasicBlock *BBEntry = &F.getEntryBlock();
77  assert(pred_empty(BBEntry) &&
78  "Entry block to function must not have predecessors!");
79 
80  // Find first non-alloca instruction and create insertion point. This is
81  // safe if block is well-formed: it always have terminator, otherwise
82  // we'll get and assertion.
83  BasicBlock::iterator I = BBEntry->begin();
84  while (isa<AllocaInst>(I)) ++I;
85 
86  CastInst *AllocaInsertionPoint = new BitCastInst(
88  Type::getInt32Ty(F.getContext()), "reg2mem alloca point", &*I);
89 
90  // Find the escaped instructions. But don't create stack slots for
91  // allocas in entry block.
92  std::list<Instruction*> WorkList;
93  for (BasicBlock &ibb : F)
94  for (BasicBlock::iterator iib = ibb.begin(), iie = ibb.end(); iib != iie;
95  ++iib) {
96  if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) &&
97  valueEscapes(&*iib)) {
98  WorkList.push_front(&*iib);
99  }
100  }
101 
102  // Demote escaped instructions
103  NumRegsDemoted += WorkList.size();
104  for (Instruction *ilb : WorkList)
105  DemoteRegToStack(*ilb, false, AllocaInsertionPoint);
106 
107  WorkList.clear();
108 
109  // Find all phi's
110  for (BasicBlock &ibb : F)
111  for (BasicBlock::iterator iib = ibb.begin(), iie = ibb.end(); iib != iie;
112  ++iib)
113  if (isa<PHINode>(iib))
114  WorkList.push_front(&*iib);
115 
116  // Demote phi nodes
117  NumPhisDemoted += WorkList.size();
118  for (Instruction *ilb : WorkList)
119  DemotePHIToStack(cast<PHINode>(ilb), AllocaInsertionPoint);
120 
121  return true;
122 }
123 
124 
125 // createDemoteRegisterToMemory - Provide an entry point to create this pass.
128  return new RegToMem();
129 }
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 ...
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
Compute iterated dominance frontiers using a linear time algorithm.
Definition: AllocatorList.h:24
char & DemoteRegisterToMemoryID
Definition: Reg2Mem.cpp:126
STATISTIC(NumFunctions, "Total number of functions")
F(f)
FunctionPass * createDemoteRegisterToMemoryPass()
Definition: Reg2Mem.cpp:127
INITIALIZE_PASS_BEGIN(RegToMem, "reg2mem", "Demote all values to stack slots", false, false) INITIALIZE_PASS_END(RegToMem
static Constant * getNullValue(Type *Ty)
Constructor to create a &#39;0&#39; constant of arbitrary type.
Definition: Constants.cpp:268
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:264
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:592
Predicate all(Predicate P0, Predicate P1)
True iff P0 and P1 are true.
This class represents a no-op cast from one type to another.
AnalysisUsage & addPreservedID(const void *ID)
static bool runOnFunction(Function &F, bool PostInlining)
LLVM Basic Block Representation.
Definition: BasicBlock.h:59
char & BreakCriticalEdgesID
ValuesClass values(OptsTy... Options)
Helper to build a ValuesClass by forwarding a variable number of arguments as an initializer list to ...
Definition: CommandLine.h:630
Demote all values to stack slots
Definition: Reg2Mem.cpp:68
Represent the analysis usage information of a pass.
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:285
bool pred_empty(const BasicBlock *BB)
Definition: CFG.h:107
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
void initializeRegToMemPass(PassRegistry &)
Iterator for intrusive lists based on ilist_node.
AnalysisUsage & addRequiredID(const void *ID)
Definition: Pass.cpp:299
Module.h This file contains the declarations for the Module class.
iterator_range< user_iterator > users()
Definition: Value.h:399
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
reg2mem
Definition: Reg2Mem.cpp:68
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
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...
const BasicBlock * getParent() const
Definition: Instruction.h:67