1e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman//===- CodeExtractor.cpp - Pull code region into a new function -----------===// 2fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 3e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// The LLVM Compiler Infrastructure 4e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// License. See LICENSE.TXT for details. 7fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman// 8e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman//===----------------------------------------------------------------------===// 9e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// 10e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// This file implements the interface to tear out a code region, such as an 11e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// individual loop or a parallel section, into a new function, replacing it with 12e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// a call to the new function. 13e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman// 14e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman//===----------------------------------------------------------------------===// 15e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 1699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth#include "llvm/Transforms/Utils/CodeExtractor.h" 17e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Constants.h" 18e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/DerivedTypes.h" 19e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Instructions.h" 20bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner#include "llvm/Intrinsics.h" 210a205a459884ec745df1c529396dd921f029dafdOwen Anderson#include "llvm/LLVMContext.h" 22e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Module.h" 23e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Pass.h" 24b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner#include "llvm/Analysis/Dominators.h" 25e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Analysis/LoopInfo.h" 2630ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth#include "llvm/Analysis/RegionInfo.h" 2730ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth#include "llvm/Analysis/RegionIterator.h" 28ffada9327301094411146627cf6bc16cd517585dChris Lattner#include "llvm/Analysis/Verifier.h" 29e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include "llvm/Transforms/Utils/BasicBlockUtils.h" 30551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 31551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 327d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 33bdff548e4dd577a72094d57b282de4e765643b96Chris Lattner#include "llvm/Support/raw_ostream.h" 34c5dd34209b9936cb500c3d11e732dc094373200dJulien Lerouge#include "llvm/ADT/SetVector.h" 35551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/ADT/StringExtras.h" 36e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman#include <algorithm> 370e06674287b15696f66a65f20f2ba99137b29213Chris Lattner#include <set> 38e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukmanusing namespace llvm; 39e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 4022108fac63eac53d1a23b781a9963fab99700135Misha Brukman// Provide a command-line option to aggregate function arguments into a struct 41a4a83c314c5997ff2b5eadae8e711fec6501121dMisha Brukman// for functions produced by the code extractor. This is useful when converting 4222108fac63eac53d1a23b781a9963fab99700135Misha Brukman// extracted functions to pthread-based code, as only one argument (void*) can 4322108fac63eac53d1a23b781a9963fab99700135Misha Brukman// be passed in to pthread_create(). 4422108fac63eac53d1a23b781a9963fab99700135Misha Brukmanstatic cl::opt<bool> 4522108fac63eac53d1a23b781a9963fab99700135Misha BrukmanAggregateArgsOpt("aggregate-extracted-args", cl::Hidden, 4622108fac63eac53d1a23b781a9963fab99700135Misha Brukman cl::desc("Aggregate arguments to code-extracted functions")); 4722108fac63eac53d1a23b781a9963fab99700135Misha Brukman 4899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth/// \brief Test whether a block is valid for extraction. 4999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruthstatic bool isBlockValidForExtraction(const BasicBlock &BB) { 5099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth // Landing pads must be in the function where they were inserted for cleanup. 5199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (BB.isLandingPad()) 5299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth return false; 53fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 5499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth // Don't hoist code containing allocas, invokes, or vastarts. 5599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth for (BasicBlock::const_iterator I = BB.begin(), E = BB.end(); I != E; ++I) { 5699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (isa<AllocaInst>(I) || isa<InvokeInst>(I)) 57bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner return false; 5899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (const CallInst *CI = dyn_cast<CallInst>(I)) 5999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (const Function *F = CI->getCalledFunction()) 6099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (F->getIntrinsicID() == Intrinsic::vastart) 6199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth return false; 6299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth } 6399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 6499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth return true; 6599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth} 6699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 6799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth/// \brief Build a set of blocks to extract if the input blocks are viable. 6830ba82933c433611e05b07ef95da36bba8721b8bChandler Carruthtemplate <typename IteratorT> 6930ba82933c433611e05b07ef95da36bba8721b8bChandler Carruthstatic SetVector<BasicBlock *> buildExtractionBlockSet(IteratorT BBBegin, 7030ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth IteratorT BBEnd) { 7199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth SetVector<BasicBlock *> Result; 7299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 7330ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth assert(BBBegin != BBEnd); 7427742c1a76634312bc28cf37e89c83209576149fChandler Carruth 7599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth // Loop over the blocks, adding them to our set-vector, and aborting with an 7699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth // empty set if we encounter invalid blocks. 7730ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth for (IteratorT I = BBBegin, E = BBEnd; I != E; ++I) { 7899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (!Result.insert(*I)) 7950955031b81ef1abd54fecd587bee7959f7fa19dChandler Carruth llvm_unreachable("Repeated basic blocks in extraction input"); 8099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 8199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (!isBlockValidForExtraction(**I)) { 8299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Result.clear(); 836a81f64ab6bfda1d17de5b405b3b47f67697c3bcChandler Carruth return Result; 84bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 8599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth } 86bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 8727742c1a76634312bc28cf37e89c83209576149fChandler Carruth#ifndef NDEBUG 8830ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth for (SetVector<BasicBlock *>::iterator I = llvm::next(Result.begin()), 8930ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth E = Result.end(); 9027742c1a76634312bc28cf37e89c83209576149fChandler Carruth I != E; ++I) 9127742c1a76634312bc28cf37e89c83209576149fChandler Carruth for (pred_iterator PI = pred_begin(*I), PE = pred_end(*I); 9227742c1a76634312bc28cf37e89c83209576149fChandler Carruth PI != PE; ++PI) 9327742c1a76634312bc28cf37e89c83209576149fChandler Carruth assert(Result.count(*PI) && 9427742c1a76634312bc28cf37e89c83209576149fChandler Carruth "No blocks in this region may have entries from outside the region" 9527742c1a76634312bc28cf37e89c83209576149fChandler Carruth " except for the first block!"); 9627742c1a76634312bc28cf37e89c83209576149fChandler Carruth#endif 9727742c1a76634312bc28cf37e89c83209576149fChandler Carruth 9899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth return Result; 9999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth} 10099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 10130ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth/// \brief Helper to call buildExtractionBlockSet with an ArrayRef. 10230ba82933c433611e05b07ef95da36bba8721b8bChandler Carruthstatic SetVector<BasicBlock *> 10330ba82933c433611e05b07ef95da36bba8721b8bChandler CarruthbuildExtractionBlockSet(ArrayRef<BasicBlock *> BBs) { 10430ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth return buildExtractionBlockSet(BBs.begin(), BBs.end()); 10530ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth} 10630ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth 10730ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth/// \brief Helper to call buildExtractionBlockSet with a RegionNode. 10830ba82933c433611e05b07ef95da36bba8721b8bChandler Carruthstatic SetVector<BasicBlock *> 10930ba82933c433611e05b07ef95da36bba8721b8bChandler CarruthbuildExtractionBlockSet(const RegionNode &RN) { 11030ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth if (!RN.isSubRegion()) 11130ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth // Just a single BasicBlock. 11230ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth return buildExtractionBlockSet(RN.getNodeAs<BasicBlock>()); 11330ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth 11430ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth const Region &R = *RN.getNodeAs<Region>(); 11530ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth 11630ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth return buildExtractionBlockSet(R.block_begin(), R.block_end()); 11730ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth} 11830ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth 11999650c9088c5dd4b6788a99b63c82d13e0518961Chandler CarruthCodeExtractor::CodeExtractor(BasicBlock *BB, bool AggregateArgs) 12099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth : DT(0), AggregateArgs(AggregateArgs||AggregateArgsOpt), 12199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Blocks(buildExtractionBlockSet(BB)), NumExitBlocks(~0U) {} 122e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 12399650c9088c5dd4b6788a99b63c82d13e0518961Chandler CarruthCodeExtractor::CodeExtractor(ArrayRef<BasicBlock *> BBs, DominatorTree *DT, 12499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth bool AggregateArgs) 12599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth : DT(DT), AggregateArgs(AggregateArgs||AggregateArgsOpt), 12699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Blocks(buildExtractionBlockSet(BBs)), NumExitBlocks(~0U) {} 127e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 12899650c9088c5dd4b6788a99b63c82d13e0518961Chandler CarruthCodeExtractor::CodeExtractor(DominatorTree &DT, Loop &L, bool AggregateArgs) 12999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth : DT(&DT), AggregateArgs(AggregateArgs||AggregateArgsOpt), 13099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Blocks(buildExtractionBlockSet(L.getBlocks())), NumExitBlocks(~0U) {} 131e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 13230ba82933c433611e05b07ef95da36bba8721b8bChandler CarruthCodeExtractor::CodeExtractor(DominatorTree &DT, const RegionNode &RN, 13330ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth bool AggregateArgs) 13430ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth : DT(&DT), AggregateArgs(AggregateArgs||AggregateArgsOpt), 13530ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth Blocks(buildExtractionBlockSet(RN)), NumExitBlocks(~0U) {} 13630ba82933c433611e05b07ef95da36bba8721b8bChandler Carruth 13799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth/// definedInRegion - Return true if the specified value is defined in the 13899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth/// extracted region. 13999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruthstatic bool definedInRegion(const SetVector<BasicBlock *> &Blocks, Value *V) { 14099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (Instruction *I = dyn_cast<Instruction>(V)) 14199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (Blocks.count(I->getParent())) 14299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth return true; 14399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth return false; 14499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth} 14599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth 14699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth/// definedInCaller - Return true if the specified value is defined in the 14799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth/// function being code extracted, but not in the region being extracted. 14899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth/// These values must be passed in as live-ins to the function. 14999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruthstatic bool definedInCaller(const SetVector<BasicBlock *> &Blocks, Value *V) { 15099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (isa<Argument>(V)) return true; 15199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (Instruction *I = dyn_cast<Instruction>(V)) 15299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (!Blocks.count(I->getParent())) 15399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth return true; 15499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth return false; 155e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 156e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 15790cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruthvoid CodeExtractor::findInputsOutputs(ValueSet &Inputs, 15890cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth ValueSet &Outputs) const { 15990cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth for (SetVector<BasicBlock *>::const_iterator I = Blocks.begin(), 16090cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth E = Blocks.end(); 16190cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth I != E; ++I) { 16290cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth BasicBlock *BB = *I; 16390cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth 16490cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth // If a used value is defined outside the region, it's an input. If an 16590cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth // instruction is used outside the region, it's an output. 16690cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth for (BasicBlock::iterator II = BB->begin(), IE = BB->end(); 16790cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth II != IE; ++II) { 16890cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth for (User::op_iterator OI = II->op_begin(), OE = II->op_end(); 16990cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth OI != OE; ++OI) 17090cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth if (definedInCaller(Blocks, *OI)) 17190cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth Inputs.insert(*OI); 17290cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth 17390cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth for (Value::use_iterator UI = II->use_begin(), UE = II->use_end(); 17490cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth UI != UE; ++UI) 17590cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth if (!definedInRegion(Blocks, *UI)) { 17690cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth Outputs.insert(II); 17790cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth break; 17890cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth } 17990cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth } 18090cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth } 18190cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth} 18290cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth 183bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// severSplitPHINodes - If a PHI node has multiple inputs from outside of the 184bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// region, we need to split the entry block of the region so that the PHI node 185bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// is easier to deal with. 186bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::severSplitPHINodes(BasicBlock *&Header) { 187d8b4fb4aab4d6fedb2b14bed1b846451b17bde7cJay Foad unsigned NumPredsFromRegion = 0; 188e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner unsigned NumPredsOutsideRegion = 0; 189e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 190ecb7a77885b174cf4d001a9b48533b3979e7810dDan Gohman if (Header != &Header->getParent()->getEntryBlock()) { 191e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *PN = dyn_cast<PHINode>(Header->begin()); 192e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (!PN) return; // No PHI nodes. 193e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 194e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // If the header node contains any PHI nodes, check to see if there is more 195e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // than one entry from outside the region. If so, we need to sever the 196e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // header block into two. 197e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 19899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (Blocks.count(PN->getIncomingBlock(i))) 199d8b4fb4aab4d6fedb2b14bed1b846451b17bde7cJay Foad ++NumPredsFromRegion; 200e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner else 201e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner ++NumPredsOutsideRegion; 202e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 203e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // If there is one (or fewer) predecessor from outside the region, we don't 204e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // need to do anything special. 205e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner if (NumPredsOutsideRegion <= 1) return; 206e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 207bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 208e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Otherwise, we need to split the header block into two pieces: one 209e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // containing PHI nodes merging values from outside of the region, and a 210e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // second that contains all of the code for the block and merges back any 211e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // incoming values from inside of the region. 21202dea8b39f3acad5de1df36273444d149145e7fcDan Gohman BasicBlock::iterator AfterPHIs = Header->getFirstNonPHI(); 213e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock *NewBB = Header->splitBasicBlock(AfterPHIs, 214e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Header->getName()+".ce"); 215e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 216e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // We only want to code extract the second block now, and it becomes the new 217e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // header of the region. 218e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner BasicBlock *OldPred = Header; 21999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Blocks.remove(OldPred); 22099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Blocks.insert(NewBB); 221e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Header = NewBB; 222e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 223e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, update dominator sets. The blocks that dominate the new one are the 224e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // blocks that dominate TIBB plus the new block itself. 2250e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel if (DT) 2260e7f728ad1ac25b0ed450fe0f8b86a38d3c2a93aDevang Patel DT->splitBlock(NewBB); 227bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 228e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Okay, now we need to adjust the PHI nodes and any branches from within the 229e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // region to go to the new header block instead of the old header block. 230d8b4fb4aab4d6fedb2b14bed1b846451b17bde7cJay Foad if (NumPredsFromRegion) { 231e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PHINode *PN = cast<PHINode>(OldPred->begin()); 232e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the predecessors of OldPred that are in the region, 233e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // changing them to branch to NewBB instead. 234e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 23599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (Blocks.count(PN->getIncomingBlock(i))) { 236e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner TerminatorInst *TI = PN->getIncomingBlock(i)->getTerminator(); 237e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner TI->replaceUsesOfWith(OldPred, NewBB); 238e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 239e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 2407a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner // Okay, everything within the region is now branching to the right block, we 241e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // just have to update the PHI nodes now, inserting PHI nodes into NewBB. 2422da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (AfterPHIs = OldPred->begin(); isa<PHINode>(AfterPHIs); ++AfterPHIs) { 2432da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(AfterPHIs); 244e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Create a new PHI node in the new region, which has an incoming value 245e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // from OldPred of PN. 2463ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PHINode *NewPN = PHINode::Create(PN->getType(), 1 + NumPredsFromRegion, 2473ecfc861b4365f341c5c969b40e1afccde676e6fJay Foad PN->getName()+".ce", NewBB->begin()); 248e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewPN->addIncoming(PN, OldPred); 249e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 250e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the incoming value in PN, moving them to NewPN if they 251e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // are from the extracted region. 252e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner for (unsigned i = 0; i != PN->getNumIncomingValues(); ++i) { 25399650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (Blocks.count(PN->getIncomingBlock(i))) { 254e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner NewPN->addIncoming(PN->getIncomingValue(i), PN->getIncomingBlock(i)); 255e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner PN->removeIncomingValue(i); 256e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner --i; 257e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 258e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 259e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 260e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner } 261d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner} 262e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 263d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattnervoid CodeExtractor::splitReturnBlocks() { 26499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth for (SetVector<BasicBlock *>::iterator I = Blocks.begin(), E = Blocks.end(); 26599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth I != E; ++I) 2669ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson if (ReturnInst *RI = dyn_cast<ReturnInst>((*I)->getTerminator())) { 2679ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson BasicBlock *New = (*I)->splitBasicBlock(RI, (*I)->getName()+".ret"); 2689ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson if (DT) { 269e2d50046fd29cb3eb2483e080cb7c39b460fbb19Gabor Greif // Old dominates New. New node dominates all other nodes dominated 270e2d50046fd29cb3eb2483e080cb7c39b460fbb19Gabor Greif // by Old. 2719ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson DomTreeNode *OldNode = DT->getNode(*I); 27255a0f1e41f1b166eb924909eeec94a54417f95ebOwen Anderson SmallVector<DomTreeNode*, 8> Children; 2739ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson for (DomTreeNode::iterator DI = OldNode->begin(), DE = OldNode->end(); 2749ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson DI != DE; ++DI) 2759ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson Children.push_back(*DI); 2769ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson 2779ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson DomTreeNode *NewNode = DT->addNewBlock(New, *I); 2789ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson 27955a0f1e41f1b166eb924909eeec94a54417f95ebOwen Anderson for (SmallVector<DomTreeNode*, 8>::iterator I = Children.begin(), 2809ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson E = Children.end(); I != E; ++I) 2819ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson DT->changeImmediateDominator(*I, NewNode); 2829ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson } 2839ea9fcdf654b9a54a072a3e28cb2091b6c84cf1cOwen Anderson } 284bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner} 285bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 286e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// constructFunction - make a function based on inputs and outputs, as follows: 287e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// f(in0, ..., inN, out0, ..., outN) 288e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman/// 28999650c9088c5dd4b6788a99b63c82d13e0518961Chandler CarruthFunction *CodeExtractor::constructFunction(const ValueSet &inputs, 29099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth const ValueSet &outputs, 2915cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner BasicBlock *header, 292e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newRootNode, 293e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman BasicBlock *newHeader, 2945cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner Function *oldFunction, 2955cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner Module *M) { 296ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "inputs: " << inputs.size() << "\n"); 297ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "outputs: " << outputs.size() << "\n"); 298e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 299e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This function returns unsigned, outputs will go back by reference. 300346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 301346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 3021d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson case 1: RetTy = Type::getVoidTy(header->getContext()); break; 3031d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson case 2: RetTy = Type::getInt1Ty(header->getContext()); break; 3041d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson default: RetTy = Type::getInt16Ty(header->getContext()); break; 305346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner } 306346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 3075fdd6c8793462549e3593890ec61573da06e3346Jay Foad std::vector<Type*> paramTy; 308e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 309e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Add the types of the input values to the function's argument list 31099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth for (ValueSet::const_iterator i = inputs.begin(), e = inputs.end(); 31199650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth i != e; ++i) { 312e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman const Value *value = *i; 313ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "value used in func: " << *value << "\n"); 314e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman paramTy.push_back(value->getType()); 315e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 316e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 317b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Add the types of the output values to the function's argument list. 31899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth for (ValueSet::const_iterator I = outputs.begin(), E = outputs.end(); 319b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner I != E; ++I) { 320ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "instr used in func: " << **I << "\n"); 32122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) 32222108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back((*I)->getType()); 32322108fac63eac53d1a23b781a9963fab99700135Misha Brukman else 324debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson paramTy.push_back(PointerType::getUnqual((*I)->getType())); 325e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 326e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 327ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << "Function type: " << *RetTy << " f("); 3285fdd6c8793462549e3593890ec61573da06e3346Jay Foad for (std::vector<Type*>::iterator i = paramTy.begin(), 3290d45a096cff7de5b487f7f7aac17684945dd0b93Bill Wendling e = paramTy.end(); i != e; ++i) 330ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << **i << ", "); 331ddc5de4cd6a19244de3ea9a2b0f8d1184031ac4aDavid Greene DEBUG(dbgs() << ")\n"); 332e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 33322108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 3340a205a459884ec745df1c529396dd921f029dafdOwen Anderson PointerType *StructPtr = 335d7f2a6cb3fbc012763adb42fd967f6fefbb22a37Owen Anderson PointerType::getUnqual(StructType::get(M->getContext(), paramTy)); 33622108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.clear(); 33722108fac63eac53d1a23b781a9963fab99700135Misha Brukman paramTy.push_back(StructPtr); 33822108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 339db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner FunctionType *funcType = 340debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson FunctionType::get(RetTy, paramTy, false); 341e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 342e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Create the new function 343051a950000e21935165db56695e35bade668193bGabor Greif Function *newFunction = Function::Create(funcType, 344051a950000e21935165db56695e35bade668193bGabor Greif GlobalValue::InternalLinkage, 345051a950000e21935165db56695e35bade668193bGabor Greif oldFunction->getName() + "_" + 346051a950000e21935165db56695e35bade668193bGabor Greif header->getName(), M); 34731535f1f04853974ec53dfc61d90e8dc4a09b456Chris Lattner // If the old function is no-throw, so is the new one. 34831535f1f04853974ec53dfc61d90e8dc4a09b456Chris Lattner if (oldFunction->doesNotThrow()) 34931535f1f04853974ec53dfc61d90e8dc4a09b456Chris Lattner newFunction->setDoesNotThrow(true); 35031535f1f04853974ec53dfc61d90e8dc4a09b456Chris Lattner 351e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman newFunction->getBasicBlockList().push_back(newRootNode); 352e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 353b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Create an iterator to name all of the arguments we inserted. 354e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator AI = newFunction->arg_begin(); 355b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 356b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner // Rewrite all users of the inputs in the extracted region to use the 35722108fac63eac53d1a23b781a9963fab99700135Misha Brukman // arguments (or appropriate addressing into struct) instead. 35822108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 35922108fac63eac53d1a23b781a9963fab99700135Misha Brukman Value *RewriteVal; 36022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 361b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Value *Idx[2]; 3621d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[0] = Constant::getNullValue(Type::getInt32Ty(header->getContext())); 3631d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[1] = ConstantInt::get(Type::getInt32Ty(header->getContext()), i); 36422108fac63eac53d1a23b781a9963fab99700135Misha Brukman TerminatorInst *TI = newFunction->begin()->getTerminator(); 365f6ccee5a9d2b9573f679bca6266ade3eb8cd3f88Daniel Dunbar GetElementPtrInst *GEP = 366a9203109f4ac95aa7e9624f2838e3d89623ec902Jay Foad GetElementPtrInst::Create(AI, Idx, "gep_" + inputs[i]->getName(), TI); 367f6ccee5a9d2b9573f679bca6266ade3eb8cd3f88Daniel Dunbar RewriteVal = new LoadInst(GEP, "loadgep_" + inputs[i]->getName(), TI); 36822108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else 36922108fac63eac53d1a23b781a9963fab99700135Misha Brukman RewriteVal = AI++; 37022108fac63eac53d1a23b781a9963fab99700135Misha Brukman 371e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(inputs[i]->use_begin(), inputs[i]->use_end()); 372e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman for (std::vector<User*>::iterator use = Users.begin(), useE = Users.end(); 373ffada9327301094411146627cf6bc16cd517585dChris Lattner use != useE; ++use) 374ffada9327301094411146627cf6bc16cd517585dChris Lattner if (Instruction* inst = dyn_cast<Instruction>(*use)) 37599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (Blocks.count(inst->getParent())) 37622108fac63eac53d1a23b781a9963fab99700135Misha Brukman inst->replaceUsesOfWith(inputs[i], RewriteVal); 377e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 378e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 37922108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Set names for input and output arguments. 38022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) { 381e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner AI = newFunction->arg_begin(); 38222108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i, ++AI) 3836bc41e8a74d1756da0003641bfebd02a3d6d9586Owen Anderson AI->setName(inputs[i]->getName()); 38422108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = outputs.size(); i != e; ++i, ++AI) 385fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman AI->setName(outputs[i]->getName()+".out"); 38622108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 387b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner 388e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Rewrite branches to basic blocks outside of the loop to new dummy blocks 389e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // within the new function. This must be done before we lose track of which 390e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // blocks were originally in the code region. 391e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman std::vector<User*> Users(header->use_begin(), header->use_end()); 3925cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner for (unsigned i = 0, e = Users.size(); i != e; ++i) 3935cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // The BasicBlock which contains the branch is not in the region 3945cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // modify the branch target to a new block 3955cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner if (TerminatorInst *TI = dyn_cast<TerminatorInst>(Users[i])) 39699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (!Blocks.count(TI->getParent()) && 3975cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner TI->getParent()->getParent() == oldFunction) 3985cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner TI->replaceUsesOfWith(header, newHeader); 399e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 400e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 401e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 402e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 403613bf1ef018514e88f64f5e60f126096963248f3Owen Anderson/// FindPhiPredForUseInBlock - Given a value and a basic block, find a PHI 404613bf1ef018514e88f64f5e60f126096963248f3Owen Anderson/// that uses the value within the basic block, and return the predecessor 405613bf1ef018514e88f64f5e60f126096963248f3Owen Anderson/// block associated with that use, or return 0 if none is found. 40660fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Andersonstatic BasicBlock* FindPhiPredForUseInBlock(Value* Used, BasicBlock* BB) { 40760fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson for (Value::use_iterator UI = Used->use_begin(), 40860fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson UE = Used->use_end(); UI != UE; ++UI) { 40960fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson PHINode *P = dyn_cast<PHINode>(*UI); 41060fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson if (P && P->getParent() == BB) 41160fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson return P->getIncomingBlock(UI); 41260fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson } 41360fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson 41460fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson return 0; 41560fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson} 41660fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson 417bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// emitCallAndSwitchStatement - This method sets up the caller side by adding 418bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// the call instruction, splitting any PHI nodes in the header block as 419bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner/// necessary. 420bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor:: 421bf749367cb2aef7072ee36a9eb681b35aab51921Chris LattneremitCallAndSwitchStatement(Function *newFunction, BasicBlock *codeReplacer, 42299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth ValueSet &inputs, ValueSet &outputs) { 423bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Emit a call to the new function, passing in: *pointer to struct (if 424bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // aggregating parameters), or plan inputs and allocated memory for outputs 4259db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson std::vector<Value*> params, StructValues, ReloadOutputs, Reloads; 4261d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson 4271d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson LLVMContext &Context = newFunction->getContext(); 42822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 42922108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Add inputs as params, or to be filled into the struct 43099650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth for (ValueSet::iterator i = inputs.begin(), e = inputs.end(); i != e; ++i) 43122108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) 43222108fac63eac53d1a23b781a9963fab99700135Misha Brukman StructValues.push_back(*i); 43322108fac63eac53d1a23b781a9963fab99700135Misha Brukman else 43422108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(*i); 43522108fac63eac53d1a23b781a9963fab99700135Misha Brukman 43622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Create allocas for the outputs 43799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth for (ValueSet::iterator i = outputs.begin(), e = outputs.end(); i != e; ++i) { 43822108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 43922108fac63eac53d1a23b781a9963fab99700135Misha Brukman StructValues.push_back(*i); 44022108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else { 44122108fac63eac53d1a23b781a9963fab99700135Misha Brukman AllocaInst *alloca = 44250dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson new AllocaInst((*i)->getType(), 0, (*i)->getName()+".loc", 44322108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getParent()->begin()->begin()); 44422108fac63eac53d1a23b781a9963fab99700135Misha Brukman ReloadOutputs.push_back(alloca); 44522108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(alloca); 44622108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 44722108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 44822108fac63eac53d1a23b781a9963fab99700135Misha Brukman 44922108fac63eac53d1a23b781a9963fab99700135Misha Brukman AllocaInst *Struct = 0; 45022108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs && (inputs.size() + outputs.size() > 0)) { 4515fdd6c8793462549e3593890ec61573da06e3346Jay Foad std::vector<Type*> ArgTypes; 45299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth for (ValueSet::iterator v = StructValues.begin(), 45322108fac63eac53d1a23b781a9963fab99700135Misha Brukman ve = StructValues.end(); v != ve; ++v) 45422108fac63eac53d1a23b781a9963fab99700135Misha Brukman ArgTypes.push_back((*v)->getType()); 45522108fac63eac53d1a23b781a9963fab99700135Misha Brukman 45622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Allocate a struct at the beginning of this function 457d7f2a6cb3fbc012763adb42fd967f6fefbb22a37Owen Anderson Type *StructArgTy = StructType::get(newFunction->getContext(), ArgTypes); 458fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman Struct = 45950dead06ffc107edb7e84857baaeeb09039c631cOwen Anderson new AllocaInst(StructArgTy, 0, "structArg", 46022108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getParent()->begin()->begin()); 46122108fac63eac53d1a23b781a9963fab99700135Misha Brukman params.push_back(Struct); 46222108fac63eac53d1a23b781a9963fab99700135Misha Brukman 46322108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned i = 0, e = inputs.size(); i != e; ++i) { 464b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Value *Idx[2]; 4651d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 4661d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), i); 46722108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP = 468a9203109f4ac95aa7e9624f2838e3d89623ec902Jay Foad GetElementPtrInst::Create(Struct, Idx, 469051a950000e21935165db56695e35bade668193bGabor Greif "gep_" + StructValues[i]->getName()); 47022108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(GEP); 47122108fac63eac53d1a23b781a9963fab99700135Misha Brukman StoreInst *SI = new StoreInst(StructValues[i], GEP); 47222108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(SI); 47322108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 474fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman } 47522108fac63eac53d1a23b781a9963fab99700135Misha Brukman 47622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Emit the call to the function 477a3efbb15ddd5aa9006564cd79086723640084878Jay Foad CallInst *call = CallInst::Create(newFunction, params, 478051a950000e21935165db56695e35bade668193bGabor Greif NumExitBlocks > 1 ? "targetBlock" : ""); 47922108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(call); 48022108fac63eac53d1a23b781a9963fab99700135Misha Brukman 481e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator OutputArgBegin = newFunction->arg_begin(); 48222108fac63eac53d1a23b781a9963fab99700135Misha Brukman unsigned FirstOut = inputs.size(); 48322108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) 48422108fac63eac53d1a23b781a9963fab99700135Misha Brukman std::advance(OutputArgBegin, inputs.size()); 48504229c192bc153210e8ee8a18eb28d7f1ec21bfeChris Lattner 48622108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Reload the outputs passed in by reference 487b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (unsigned i = 0, e = outputs.size(); i != e; ++i) { 48822108fac63eac53d1a23b781a9963fab99700135Misha Brukman Value *Output = 0; 48922108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 490b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Value *Idx[2]; 4911d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 4921d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), FirstOut + i); 493fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman GetElementPtrInst *GEP 494a9203109f4ac95aa7e9624f2838e3d89623ec902Jay Foad = GetElementPtrInst::Create(Struct, Idx, 495051a950000e21935165db56695e35bade668193bGabor Greif "gep_reload_" + outputs[i]->getName()); 49622108fac63eac53d1a23b781a9963fab99700135Misha Brukman codeReplacer->getInstList().push_back(GEP); 49722108fac63eac53d1a23b781a9963fab99700135Misha Brukman Output = GEP; 49822108fac63eac53d1a23b781a9963fab99700135Misha Brukman } else { 49922108fac63eac53d1a23b781a9963fab99700135Misha Brukman Output = ReloadOutputs[i]; 50022108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 50122108fac63eac53d1a23b781a9963fab99700135Misha Brukman LoadInst *load = new LoadInst(Output, outputs[i]->getName()+".reload"); 5029db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson Reloads.push_back(load); 503b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner codeReplacer->getInstList().push_back(load); 504b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner std::vector<User*> Users(outputs[i]->use_begin(), outputs[i]->use_end()); 505b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner for (unsigned u = 0, e = Users.size(); u != e; ++u) { 506b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner Instruction *inst = cast<Instruction>(Users[u]); 50799650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (!Blocks.count(inst->getParent())) 508b5c1dbf50388c4efe26c9e7ba81e514a109c65d7Chris Lattner inst->replaceUsesOfWith(outputs[i], load); 509e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 510e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 51112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 512e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Now we can emit a switch statement using the call as a value. 513346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner SwitchInst *TheSwitch = 5141d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson SwitchInst::Create(Constant::getNullValue(Type::getInt16Ty(Context)), 515051a950000e21935165db56695e35bade668193bGabor Greif codeReplacer, 0, codeReplacer); 516e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 517e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Since there may be multiple exits from the original region, make the new 51812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // function return an unsigned, switch on that number. This loop iterates 51912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // over all of the blocks in the extracted region, updating any terminator 52012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // instructions in the to-be-extracted region that branch to blocks that are 52112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // not in the region to be extracted. 52212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner std::map<BasicBlock*, BasicBlock*> ExitBlockMap; 52312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 524e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman unsigned switchVal = 0; 52599650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth for (SetVector<BasicBlock*>::const_iterator i = Blocks.begin(), 52699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth e = Blocks.end(); i != e; ++i) { 52712f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TerminatorInst *TI = (*i)->getTerminator(); 52812f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner for (unsigned i = 0, e = TI->getNumSuccessors(); i != e; ++i) 52999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (!Blocks.count(TI->getSuccessor(i))) { 53012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *OldTarget = TI->getSuccessor(i); 53112f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // add a new basic block which returns the appropriate value 53212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner BasicBlock *&NewTarget = ExitBlockMap[OldTarget]; 53312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner if (!NewTarget) { 53412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // If we don't already have an exit stub for this non-extracted 53512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // destination, create one now! 5361d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson NewTarget = BasicBlock::Create(Context, 5371d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson OldTarget->getName() + ".exitStub", 538051a950000e21935165db56695e35bade668193bGabor Greif newFunction); 539346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner unsigned SuccNum = switchVal++; 540346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner 541346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner Value *brVal = 0; 542346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 543346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 544346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: break; // No value needed. 545346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 2: // Conditional branch, return a bool 5461d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson brVal = ConstantInt::get(Type::getInt1Ty(Context), !SuccNum); 547346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 548346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner default: 5491d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson brVal = ConstantInt::get(Type::getInt16Ty(Context), SuccNum); 550346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 551346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner } 55212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 5531d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst *NTRet = ReturnInst::Create(Context, brVal, NewTarget); 55412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 55512f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Update the switch instruction. 5561d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson TheSwitch->addCase(ConstantInt::get(Type::getInt16Ty(Context), 5571d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson SuccNum), 558346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner OldTarget); 55912f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner 56012f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // Restore values just before we exit 561e4d5c441e04bdc00ccf1804744af670655123b07Chris Lattner Function::arg_iterator OAI = OutputArgBegin; 56222108fac63eac53d1a23b781a9963fab99700135Misha Brukman for (unsigned out = 0, e = outputs.size(); out != e; ++out) { 56322108fac63eac53d1a23b781a9963fab99700135Misha Brukman // For an invoke, the normal destination is the only one that is 56422108fac63eac53d1a23b781a9963fab99700135Misha Brukman // dominated by the result of the invocation 56522108fac63eac53d1a23b781a9963fab99700135Misha Brukman BasicBlock *DefBlock = cast<Instruction>(outputs[out])->getParent(); 5669ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 5679ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner bool DominatesDef = true; 5689ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 56968c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner if (InvokeInst *Invoke = dyn_cast<InvokeInst>(outputs[out])) { 57022108fac63eac53d1a23b781a9963fab99700135Misha Brukman DefBlock = Invoke->getNormalDest(); 57168c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner 57268c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner // Make sure we are looking at the original successor block, not 57368c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner // at a newly inserted exit block, which won't be in the dominator 57468c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner // info. 57568c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner for (std::map<BasicBlock*, BasicBlock*>::iterator I = 57668c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner ExitBlockMap.begin(), E = ExitBlockMap.end(); I != E; ++I) 57768c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner if (DefBlock == I->second) { 57868c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner DefBlock = I->first; 57968c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner break; 58068c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner } 5819ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 5829ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner // In the extract block case, if the block we are extracting ends 5839ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner // with an invoke instruction, make sure that we don't emit a 5849ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner // store of the invoke value for the unwind block. 5854b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang Patel if (!DT && DefBlock != OldTarget) 5869ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner DominatesDef = false; 58768c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner } 58868c311aac64ca3bc50f48f4f1b4fd4c21fe0c4dfChris Lattner 5899db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson if (DT) { 5904b90e3a276c0bb1bd4d90289e27aa3c4f890b5afDevang Patel DominatesDef = DT->dominates(DefBlock, OldTarget); 5919db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson 5929db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson // If the output value is used by a phi in the target block, 5939db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson // then we need to test for dominance of the phi's predecessor 5949db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson // instead. Unfortunately, this a little complicated since we 5959db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson // have already rewritten uses of the value to uses of the reload. 59660fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson BasicBlock* pred = FindPhiPredForUseInBlock(Reloads[out], 59760fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson OldTarget); 59860fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson if (pred && DT && DT->dominates(DefBlock, pred)) 59960fd8be183f7cf17dd07c0b8ce8a4e5332d20765Owen Anderson DominatesDef = true; 6009db7e91fe826ff4009d28fc82263923fa4774496Owen Anderson } 6019ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner 6029ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner if (DominatesDef) { 60322108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (AggregateArgs) { 604b8f74793b9d161bc666fe27fc92fe112b6ec169bDavid Greene Value *Idx[2]; 6051d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[0] = Constant::getNullValue(Type::getInt32Ty(Context)); 6061d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Idx[1] = ConstantInt::get(Type::getInt32Ty(Context), 6071d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson FirstOut+out); 60822108fac63eac53d1a23b781a9963fab99700135Misha Brukman GetElementPtrInst *GEP = 609a9203109f4ac95aa7e9624f2838e3d89623ec902Jay Foad GetElementPtrInst::Create(OAI, Idx, 610051a950000e21935165db56695e35bade668193bGabor Greif "gep_" + outputs[out]->getName(), 611051a950000e21935165db56695e35bade668193bGabor Greif NTRet); 61222108fac63eac53d1a23b781a9963fab99700135Misha Brukman new StoreInst(outputs[out], GEP, NTRet); 6139ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner } else { 61422108fac63eac53d1a23b781a9963fab99700135Misha Brukman new StoreInst(outputs[out], OAI, NTRet); 6159ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner } 6169ecc0461841ad2fb44996a965f30ab3931efbf70Chris Lattner } 61722108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Advance output iterator even if we don't emit a store 61822108fac63eac53d1a23b781a9963fab99700135Misha Brukman if (!AggregateArgs) ++OAI; 61922108fac63eac53d1a23b781a9963fab99700135Misha Brukman } 620e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 6210e06674287b15696f66a65f20f2ba99137b29213Chris Lattner 62212f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner // rewrite the original branch instruction with this new target 62312f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner TI->setSuccessor(i, NewTarget); 62412f390e9c03d5439fd84c26d7cbd451cda80601aChris Lattner } 625e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman } 62665826bf435620824763af926270cf0efdc82ea5aChris Lattner 6275b01e298ed42d5ce6aaf7634618b5e1769766b21Chris Lattner // Now that we've done the deed, simplify the switch instruction. 628db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner Type *OldFnRetTy = TheSwitch->getParent()->getParent()->getReturnType(); 629346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner switch (NumExitBlocks) { 630346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 0: 631b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner // There are no successors (the block containing the switch itself), which 63222108fac63eac53d1a23b781a9963fab99700135Misha Brukman // means that previously this was the last part of the function, and hence 63322108fac63eac53d1a23b781a9963fab99700135Misha Brukman // this should be rewritten as a `ret' 634fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 63522108fac63eac53d1a23b781a9963fab99700135Misha Brukman // Check if the function should return a value 636f012705c7e4ca8cf90b6b734ce1d5355daca5ba5Benjamin Kramer if (OldFnRetTy->isVoidTy()) { 6371d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(Context, 0, TheSwitch); // Return void 638b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner } else if (OldFnRetTy == TheSwitch->getCondition()->getType()) { 63922108fac63eac53d1a23b781a9963fab99700135Misha Brukman // return what we have 6401d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(Context, TheSwitch->getCondition(), TheSwitch); 641b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner } else { 642b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner // Otherwise we must have code extracted an unwind or something, just 643b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner // return whatever we want. 6441d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson ReturnInst::Create(Context, 6451d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson Constant::getNullValue(OldFnRetTy), TheSwitch); 646b519efbafedb356a30a04a32c15a6b406779a997Chris Lattner } 64722108fac63eac53d1a23b781a9963fab99700135Misha Brukman 6481adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman TheSwitch->eraseFromParent(); 649346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 650346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 1: 651346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // Only a single destination, change the switch into an unconditional 652346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // branch. 653051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch); 6541adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman TheSwitch->eraseFromParent(); 655346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 656346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner case 2: 657051a950000e21935165db56695e35bade668193bGabor Greif BranchInst::Create(TheSwitch->getSuccessor(1), TheSwitch->getSuccessor(2), 658051a950000e21935165db56695e35bade668193bGabor Greif call, TheSwitch); 6591adec83ae84031bfa9f0bf209c5ee6c64906a1ffDan Gohman TheSwitch->eraseFromParent(); 660346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 661346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner default: 662346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // Otherwise, make the default destination of the switch instruction be one 663346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner // of the other successors. 66424473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy TheSwitch->setCondition(call); 66524473120a253a05f3601cd3373403b47e6d03d41Stepan Dyatkovskiy TheSwitch->setDefaultDest(TheSwitch->getSuccessor(NumExitBlocks)); 666c10fa6c801e48771b5eade50afc2fe6abaf08227Stepan Dyatkovskiy // Remove redundant case 66743c3a4a7e76920c5646e473b72620acc7eb4ca5aStepan Dyatkovskiy SwitchInst::CaseIt ToBeRemoved(TheSwitch, NumExitBlocks-1); 66843c3a4a7e76920c5646e473b72620acc7eb4ca5aStepan Dyatkovskiy TheSwitch->removeCase(ToBeRemoved); 669346be7f5bc1bab5768b9fa0a01a015d2fdca19c5Chris Lattner break; 67065826bf435620824763af926270cf0efdc82ea5aChris Lattner } 671e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 672e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 673bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattnervoid CodeExtractor::moveCodeToFunction(Function *newFunction) { 67499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth Function *oldFunc = (*Blocks.begin())->getParent(); 675bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function::BasicBlockListType &oldBlocks = oldFunc->getBasicBlockList(); 676bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner Function::BasicBlockListType &newBlocks = newFunction->getBasicBlockList(); 677bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 67899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth for (SetVector<BasicBlock*>::const_iterator i = Blocks.begin(), 67999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth e = Blocks.end(); i != e; ++i) { 680bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Delete the basic block from the old function, and the list of blocks 681bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner oldBlocks.remove(*i); 682bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 683bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Insert this basic block into the new function 684bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner newBlocks.push_back(*i); 685bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner } 686bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner} 687e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 68899650c9088c5dd4b6788a99b63c82d13e0518961Chandler CarruthFunction *CodeExtractor::extractCodeRegion() { 68999650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (!isEligible()) 69022108fac63eac53d1a23b781a9963fab99700135Misha Brukman return 0; 69122108fac63eac53d1a23b781a9963fab99700135Misha Brukman 69299650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth ValueSet inputs, outputs; 693e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 694e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // Assumption: this is a single-entry code region, and the header is the first 6950de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner // block in the region. 69699650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth BasicBlock *header = *Blocks.begin(); 697bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 698d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner // If we have to split PHI nodes or the entry block, do so now. 699e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner severSplitPHINodes(header); 700e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 701d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner // If we have any return instructions in the region, split those blocks so 702d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner // that the return is not in the region. 703d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner splitReturnBlocks(); 704d99e1d3afbe664694ee04a5db5e4a7a8104858a1Chris Lattner 705e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman Function *oldFunction = header->getParent(); 706e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 707e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // This takes place of the original loop 7081d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *codeReplacer = BasicBlock::Create(header->getContext(), 7091d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "codeRepl", oldFunction, 710b1dbcd886a4b5597a839f299054b78b33fb2d6dfGabor Greif header); 711e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 712e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman // The new function needs a root node because other nodes can branch to the 713bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // head of the region, but the entry node of a function cannot have preds. 7141d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson BasicBlock *newFuncRoot = BasicBlock::Create(header->getContext(), 7151d0be15f89cb5056e20e2d24faa8d6afb1573bcaOwen Anderson "newFuncRoot"); 716051a950000e21935165db56695e35bade668193bGabor Greif newFuncRoot->getInstList().push_back(BranchInst::Create(header)); 717e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 718bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Find inputs to, outputs from the code region. 719bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner findInputsOutputs(inputs, outputs); 720bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner 72190cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth SmallPtrSet<BasicBlock *, 1> ExitBlocks; 72290cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth for (SetVector<BasicBlock *>::iterator I = Blocks.begin(), E = Blocks.end(); 72390cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth I != E; ++I) 72490cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth for (succ_iterator SI = succ_begin(*I), SE = succ_end(*I); SI != SE; ++SI) 72590cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth if (!Blocks.count(*SI)) 72690cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth ExitBlocks.insert(*SI); 72790cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth NumExitBlocks = ExitBlocks.size(); 72890cb7089e364fdf09058bfb6a89a250fd7a871fbChandler Carruth 729bf749367cb2aef7072ee36a9eb681b35aab51921Chris Lattner // Construct new function based on inputs/outputs & add allocas for all defs. 730e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner Function *newFunction = constructFunction(inputs, outputs, header, 731fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman newFuncRoot, 7320de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner codeReplacer, oldFunction, 7330de632bfaedf07b5ae6fd616864716bd5427cb17Chris Lattner oldFunction->getParent()); 734e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 7350e06674287b15696f66a65f20f2ba99137b29213Chris Lattner emitCallAndSwitchStatement(newFunction, codeReplacer, inputs, outputs); 736e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 7370e06674287b15696f66a65f20f2ba99137b29213Chris Lattner moveCodeToFunction(newFunction); 738e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman 739e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // Loop over all of the PHI nodes in the header block, and change any 7405cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner // references to the old incoming edge to be the new incoming edge. 7412da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = header->begin(); isa<PHINode>(I); ++I) { 7422da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 7435cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 74499650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (!Blocks.count(PN->getIncomingBlock(i))) 7455cc8ca642095e5d6af377ce0709fa29512c40ad5Chris Lattner PN->setIncomingBlock(i, newFuncRoot); 7462da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer } 747fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 748d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // Look at all successors of the codeReplacer block. If any of these blocks 749d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // had PHI nodes in them, we need to update the "from" block to be the code 750d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner // replacer, not the original block in the extracted region. 751d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner std::vector<BasicBlock*> Succs(succ_begin(codeReplacer), 752d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner succ_end(codeReplacer)); 753d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner for (unsigned i = 0, e = Succs.size(); i != e; ++i) 7542da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer for (BasicBlock::iterator I = Succs[i]->begin(); isa<PHINode>(I); ++I) { 7552da5c3dda6f5b9c4ec6d55008d33327764364bd4Reid Spencer PHINode *PN = cast<PHINode>(I); 756a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner std::set<BasicBlock*> ProcessedPreds; 757d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) 75899650c9088c5dd4b6788a99b63c82d13e0518961Chandler Carruth if (Blocks.count(PN->getIncomingBlock(i))) { 759a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner if (ProcessedPreds.insert(PN->getIncomingBlock(i)).second) 760a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner PN->setIncomingBlock(i, codeReplacer); 761a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner else { 762a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner // There were multiple entries in the PHI for this block, now there 763a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner // is only one, so remove the duplicated entries. 764a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner PN->removeIncomingValue(i, false); 765a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner --i; --e; 766a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner } 76707e6e56f57e8781a8d7bc601cc9034a3741d84c2Anton Korobeynikov } 768a670c684a637e9922be87d8b459d2e052675f0e4Chris Lattner } 769fd93908ae8b9684fe71c239e3c6cfe13ff6a2663Misha Brukman 770e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling //cerr << "NEW FUNCTION: " << *newFunction; 771e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // verifyFunction(*newFunction); 772e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner 773e81561909d128c6e2d8033cb5465a49b2596b26aBill Wendling // cerr << "OLD FUNCTION: " << *oldFunction; 774e746ad512efc447f352f9580a82c808c2d32ab26Chris Lattner // verifyFunction(*oldFunction); 775d07f89969166750f96c0e3055e387ec82bba88c5Chris Lattner 7767d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin DEBUG(if (verifyFunction(*newFunction)) 77775361b69f3f327842b9dad69fa7f28ae3b688412Chris Lattner report_fatal_error("verifyFunction failed!")); 778e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman return newFunction; 779e6336031b8b85a438e2fcaa9e56e7392afbbb7dcMisha Brukman} 780