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/Analysis/Utils/Local.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) {
42       initializeRegToMemPass(*PassRegistry::getPassRegistry());
43     }
44 
45     void getAnalysisUsage(AnalysisUsage &AU) const override {
46       AU.addRequiredID(BreakCriticalEdgesID);
47       AU.addPreservedID(BreakCriticalEdgesID);
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(
87       Constant::getNullValue(Type::getInt32Ty(F.getContext())),
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.
126 char &llvm::DemoteRegisterToMemoryID = RegToMem::ID;
127 FunctionPass *llvm::createDemoteRegisterToMemoryPass() {
128   return new RegToMem();
129 }
130