LLVM  6.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"
20 #include "llvm/IR/BasicBlock.h"
21 #include "llvm/IR/CFG.h"
22 #include "llvm/IR/Function.h"
23 #include "llvm/IR/Instructions.h"
24 #include "llvm/IR/LLVMContext.h"
25 #include "llvm/IR/Module.h"
26 #include "llvm/Pass.h"
27 #include "llvm/Transforms/Scalar.h"
29 #include <list>
30 using namespace llvm;
31 
32 #define DEBUG_TYPE "reg2mem"
33 
34 STATISTIC(NumRegsDemoted, "Number of registers demoted");
35 STATISTIC(NumPhisDemoted, "Number of phi-nodes demoted");
36 
37 namespace {
38  struct RegToMem : public FunctionPass {
39  static char ID; // Pass identification, replacement for typeid
40  RegToMem() : FunctionPass(ID) {
42  }
43 
44  void getAnalysisUsage(AnalysisUsage &AU) const override {
47  }
48 
49  bool valueEscapes(const Instruction *Inst) const {
50  const BasicBlock *BB = Inst->getParent();
51  for (const User *U : Inst->users()) {
52  const Instruction *UI = cast<Instruction>(U);
53  if (UI->getParent() != BB || isa<PHINode>(UI))
54  return true;
55  }
56  return false;
57  }
58 
59  bool runOnFunction(Function &F) override;
60  };
61 }
62 
63 char RegToMem::ID = 0;
64 INITIALIZE_PASS_BEGIN(RegToMem, "reg2mem", "Demote all values to stack slots",
65  false, false)
66 INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
67 INITIALIZE_PASS_END(RegToMem, "reg2mem", "Demote all values to stack slots",
68  false, false)
69 
70 bool RegToMem::runOnFunction(Function &F) {
71  if (F.isDeclaration() || skipFunction(F))
72  return false;
73 
74  // Insert all new allocas into entry block.
75  BasicBlock *BBEntry = &F.getEntryBlock();
76  assert(pred_empty(BBEntry) &&
77  "Entry block to function must not have predecessors!");
78 
79  // Find first non-alloca instruction and create insertion point. This is
80  // safe if block is well-formed: it always have terminator, otherwise
81  // we'll get and assertion.
82  BasicBlock::iterator I = BBEntry->begin();
83  while (isa<AllocaInst>(I)) ++I;
84 
85  CastInst *AllocaInsertionPoint = new BitCastInst(
87  Type::getInt32Ty(F.getContext()), "reg2mem alloca point", &*I);
88 
89  // Find the escaped instructions. But don't create stack slots for
90  // allocas in entry block.
91  std::list<Instruction*> WorkList;
92  for (BasicBlock &ibb : F)
93  for (BasicBlock::iterator iib = ibb.begin(), iie = ibb.end(); iib != iie;
94  ++iib) {
95  if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) &&
96  valueEscapes(&*iib)) {
97  WorkList.push_front(&*iib);
98  }
99  }
100 
101  // Demote escaped instructions
102  NumRegsDemoted += WorkList.size();
103  for (Instruction *ilb : WorkList)
104  DemoteRegToStack(*ilb, false, AllocaInsertionPoint);
105 
106  WorkList.clear();
107 
108  // Find all phi's
109  for (BasicBlock &ibb : F)
110  for (BasicBlock::iterator iib = ibb.begin(), iie = ibb.end(); iib != iie;
111  ++iib)
112  if (isa<PHINode>(iib))
113  WorkList.push_front(&*iib);
114 
115  // Demote phi nodes
116  NumPhisDemoted += WorkList.size();
117  for (Instruction *ilb : WorkList)
118  DemotePHIToStack(cast<PHINode>(ilb), AllocaInsertionPoint);
119 
120  return true;
121 }
122 
123 
124 // createDemoteRegisterToMemory - Provide an entry point to create this pass.
127  return new RegToMem();
128 }
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:125
STATISTIC(NumFunctions, "Total number of functions")
F(f)
FunctionPass * createDemoteRegisterToMemoryPass()
Definition: Reg2Mem.cpp:126
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:207
iterator begin()
Instruction iterator methods.
Definition: BasicBlock.h:252
#define INITIALIZE_PASS_DEPENDENCY(depName)
Definition: PassSupport.h:51
This is the base class for all instructions that perform data casts.
Definition: InstrTypes.h:560
This class represents a no-op cast from one type to another.
AnalysisUsage & addPreservedID(const void *ID)
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:626
Demote all values to stack slots
Definition: Reg2Mem.cpp:67
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:298
Module.h This file contains the declarations for the Module class.
iterator_range< user_iterator > users()
Definition: Value.h:395
static IntegerType * getInt32Ty(LLVMContext &C)
Definition: Type.cpp:176
reg2mem
Definition: Reg2Mem.cpp:67
#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:66