149 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file demotes all registers to memory references. It is intended to be10// the inverse of PromoteMemoryToRegister. By converting to loads, the only11// 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 that14// all introduced allocas and nothing else are in the entry block.15//16//===----------------------------------------------------------------------===//17 18#include "llvm/Transforms/Scalar/Reg2Mem.h"19#include "llvm/ADT/Statistic.h"20#include "llvm/Analysis/LoopInfo.h"21#include "llvm/IR/BasicBlock.h"22#include "llvm/IR/CFG.h"23#include "llvm/IR/Dominators.h"24#include "llvm/IR/Function.h"25#include "llvm/IR/InstIterator.h"26#include "llvm/IR/Instructions.h"27#include "llvm/IR/PassManager.h"28#include "llvm/InitializePasses.h"29#include "llvm/Transforms/Scalar.h"30#include "llvm/Transforms/Utils.h"31#include "llvm/Transforms/Utils/BasicBlockUtils.h"32#include "llvm/Transforms/Utils/Local.h"33#include <list>34using namespace llvm;35 36#define DEBUG_TYPE "reg2mem"37 38STATISTIC(NumRegsDemoted, "Number of registers demoted");39STATISTIC(NumPhisDemoted, "Number of phi-nodes demoted");40 41static bool valueEscapes(const Instruction &Inst) {42 if (!Inst.getType()->isSized())43 return false;44 45 const BasicBlock *BB = Inst.getParent();46 for (const User *U : Inst.users()) {47 const Instruction *UI = cast<Instruction>(U);48 if (UI->getParent() != BB || isa<PHINode>(UI))49 return true;50 }51 return false;52}53 54static bool runPass(Function &F) {55 // Insert all new allocas into entry block.56 BasicBlock *BBEntry = &F.getEntryBlock();57 assert(pred_empty(BBEntry) &&58 "Entry block to function must not have predecessors!");59 60 // Find first non-alloca instruction and create insertion point. This is61 // safe if block is well-formed: it always have terminator, otherwise62 // we'll get and assertion.63 BasicBlock::iterator I = BBEntry->begin();64 while (isa<AllocaInst>(I)) ++I;65 66 CastInst *AllocaInsertionPoint = new BitCastInst(67 Constant::getNullValue(Type::getInt32Ty(F.getContext())),68 Type::getInt32Ty(F.getContext()), "reg2mem alloca point", I);69 70 // Find the escaped instructions. But don't create stack slots for71 // allocas in entry block.72 std::list<Instruction*> WorkList;73 for (Instruction &I : instructions(F))74 if (!(isa<AllocaInst>(I) && I.getParent() == BBEntry) && valueEscapes(I))75 WorkList.push_front(&I);76 77 // Demote escaped instructions78 NumRegsDemoted += WorkList.size();79 for (Instruction *I : WorkList)80 DemoteRegToStack(*I, false, AllocaInsertionPoint->getIterator());81 82 WorkList.clear();83 84 // Find all phi's85 for (BasicBlock &BB : F)86 for (auto &Phi : BB.phis())87 WorkList.push_front(&Phi);88 89 // Demote phi nodes90 NumPhisDemoted += WorkList.size();91 for (Instruction *I : WorkList)92 DemotePHIToStack(cast<PHINode>(I), AllocaInsertionPoint->getIterator());93 94 return true;95}96 97PreservedAnalyses RegToMemPass::run(Function &F, FunctionAnalysisManager &AM) {98 auto *DT = &AM.getResult<DominatorTreeAnalysis>(F);99 auto *LI = &AM.getResult<LoopAnalysis>(F);100 unsigned N = SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI));101 bool Changed = runPass(F);102 if (N == 0 && !Changed)103 return PreservedAnalyses::all();104 PreservedAnalyses PA;105 PA.preserve<DominatorTreeAnalysis>();106 PA.preserve<LoopAnalysis>();107 return PA;108}109 110namespace {111 112class RegToMemWrapperPass : public FunctionPass {113public:114 static char ID;115 116 RegToMemWrapperPass() : FunctionPass(ID) {}117 118 void getAnalysisUsage(AnalysisUsage &AU) const override {119 AU.setPreservesAll();120 121 AU.addPreserved<DominatorTreeWrapperPass>();122 AU.addRequired<DominatorTreeWrapperPass>();123 124 AU.addPreserved<LoopInfoWrapperPass>();125 AU.addRequired<LoopInfoWrapperPass>();126 }127 128 bool runOnFunction(Function &F) override {129 DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();130 LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();131 132 unsigned N = SplitAllCriticalEdges(F, CriticalEdgeSplittingOptions(DT, LI));133 bool Changed = runPass(F);134 return N != 0 || Changed;135 }136};137} // namespace138 139INITIALIZE_PASS_BEGIN(RegToMemWrapperPass, "reg2mem", "", true, true)140INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass);141INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass);142INITIALIZE_PASS_END(RegToMemWrapperPass, "reg2mem", "", true, true)143 144char RegToMemWrapperPass::ID = 0;145 146FunctionPass *llvm::createRegToMemWrapperPass() {147 return new RegToMemWrapperPass();148}149