Reg2Mem.cpp revision 1d0be15f89cb5056e20e2d24faa8d6afb1573bca 
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 intented to be
11// the inverse of PromoteMemoryToRegister.  By converting to loads, the only
12// values live accross 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#define DEBUG_TYPE "reg2mem"
20#include "llvm/Transforms/Scalar.h"
21#include "llvm/Transforms/Utils/Local.h"
22#include "llvm/Pass.h"
23#include "llvm/Function.h"
24#include "llvm/LLVMContext.h"
25#include "llvm/Module.h"
26#include "llvm/BasicBlock.h"
27#include "llvm/Instructions.h"
28#include "llvm/ADT/Statistic.h"
29#include "llvm/Support/Compiler.h"
30#include "llvm/Support/CFG.h"
31#include <list>
32using namespace llvm;
33
34STATISTIC(NumRegsDemoted, "Number of registers demoted");
35STATISTIC(NumPhisDemoted, "Number of phi-nodes demoted");
36
37namespace {
38  struct VISIBILITY_HIDDEN RegToMem : public FunctionPass {
39    static char ID; // Pass identification, replacement for typeid
40    RegToMem() : FunctionPass(&ID) {}
41
42    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
43      AU.addRequiredID(BreakCriticalEdgesID);
44      AU.addPreservedID(BreakCriticalEdgesID);
45    }
46
47   bool valueEscapes(Instruction* i) {
48      BasicBlock* bb = i->getParent();
49      for (Value::use_iterator ii = i->use_begin(), ie = i->use_end();
50           ii != ie; ++ii)
51        if (cast<Instruction>(*ii)->getParent() != bb ||
52            isa<PHINode>(*ii))
53          return true;
54      return false;
55    }
56
57    virtual bool runOnFunction(Function &F) {
58      if (!F.isDeclaration()) {
59        // Insert all new allocas into entry block.
60        BasicBlock* BBEntry = &F.getEntryBlock();
61        assert(pred_begin(BBEntry) == pred_end(BBEntry) &&
62               "Entry block to function must not have predecessors!");
63
64        // Find first non-alloca instruction and create insertion point. This is
65        // safe if block is well-formed: it always have terminator, otherwise
66        // we'll get and assertion.
67        BasicBlock::iterator I = BBEntry->begin();
68        while (isa<AllocaInst>(I)) ++I;
69
70        CastInst *AllocaInsertionPoint =
71          CastInst::Create(Instruction::BitCast,
72                      Constant::getNullValue(Type::getInt32Ty(F.getContext())),
73                                             Type::getInt32Ty(F.getContext()),
74                           "reg2mem alloca point", I);
75
76        // Find the escaped instructions. But don't create stack slots for
77        // allocas in entry block.
78        std::list<Instruction*> worklist;
79        for (Function::iterator ibb = F.begin(), ibe = F.end();
80             ibb != ibe; ++ibb)
81          for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end();
82               iib != iie; ++iib) {
83            if (!(isa<AllocaInst>(iib) && iib->getParent() == BBEntry) &&
84                valueEscapes(iib)) {
85              worklist.push_front(&*iib);
86            }
87          }
88
89        // Demote escaped instructions
90        NumRegsDemoted += worklist.size();
91        for (std::list<Instruction*>::iterator ilb = worklist.begin(),
92               ile = worklist.end(); ilb != ile; ++ilb)
93          DemoteRegToStack(**ilb, false, AllocaInsertionPoint);
94
95        worklist.clear();
96
97        // Find all phi's
98        for (Function::iterator ibb = F.begin(), ibe = F.end();
99             ibb != ibe; ++ibb)
100          for (BasicBlock::iterator iib = ibb->begin(), iie = ibb->end();
101               iib != iie; ++iib)
102            if (isa<PHINode>(iib))
103              worklist.push_front(&*iib);
104
105        // Demote phi nodes
106        NumPhisDemoted += worklist.size();
107        for (std::list<Instruction*>::iterator ilb = worklist.begin(),
108               ile = worklist.end(); ilb != ile; ++ilb)
109          DemotePHIToStack(cast<PHINode>(*ilb), AllocaInsertionPoint);
110
111        return true;
112      }
113      return false;
114    }
115  };
116}
117
118char RegToMem::ID = 0;
119static RegisterPass<RegToMem>
120X("reg2mem", "Demote all values to stack slots");
121
122// createDemoteRegisterToMemory - Provide an entry point to create this pass.
123//
124const PassInfo *const llvm::DemoteRegisterToMemoryID = &X;
125FunctionPass *llvm::createDemoteRegisterToMemoryPass() {
126  return new RegToMem();
127}
128