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
18#include "llvm/ADT/Statistic.h"
19#include "llvm/IR/BasicBlock.h"
20#include "llvm/IR/CFG.h"
21#include "llvm/IR/Function.h"
22#include "llvm/IR/Instructions.h"
23#include "llvm/IR/LLVMContext.h"
24#include "llvm/IR/Module.h"
25#include "llvm/InitializePasses.h"
26#include "llvm/Pass.h"
27#include "llvm/Transforms/Scalar.h"
28#include "llvm/Transforms/Utils.h"
29#include "llvm/Transforms/Utils/Local.h"
30#include <list>
31using namespace llvm;
32
33#define DEBUG_TYPE "reg2mem"
34
35STATISTIC(NumRegsDemoted, "Number of registers demoted");
36STATISTIC(NumPhisDemoted, "Number of phi-nodes demoted");
37
38namespace {
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
64char RegToMem::ID = 0;
65INITIALIZE_PASS_BEGIN(RegToMem, "reg2mem", "Demote all values to stack slots",
66                false, false)
67INITIALIZE_PASS_DEPENDENCY(BreakCriticalEdges)
68INITIALIZE_PASS_END(RegToMem, "reg2mem", "Demote all values to stack slots",
69                false, false)
70
71bool 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.
126char &llvm::DemoteRegisterToMemoryID = RegToMem::ID;
127FunctionPass *llvm::createDemoteRegisterToMemoryPass() {
128  return new RegToMem();
129}
130