1afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//===- ExtractFunction.cpp - Extract a function from Program --------------===// 23da94aec4d429b2ba0f65fa040c33650cade196bMisha Brukman// 37c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell// The LLVM Compiler Infrastructure 47c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell// 521c62da287237d39d0d95004881ea4baae3be6daChris Lattner// This file is distributed under the University of Illinois Open Source 621c62da287237d39d0d95004881ea4baae3be6daChris Lattner// License. See LICENSE.TXT for details. 73da94aec4d429b2ba0f65fa040c33650cade196bMisha Brukman// 87c0e022c5c4be4b11e199a53f73bbdd84e34aa80John Criswell//===----------------------------------------------------------------------===// 9afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner// 10efdc0b505712d1ca4460def27e51c430f033d58dChris Lattner// This file implements several methods that are used to extract functions, 11efdc0b505712d1ca4460def27e51c430f033d58dChris Lattner// loops, or portions of a module from the rest of the module. 12afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner// 13afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner//===----------------------------------------------------------------------===// 14afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 15afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner#include "BugDriver.h" 16f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Analysis/Verifier.h" 17f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Assembly/Writer.h" 180b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 190b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DerivedTypes.h" 210b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/LLVMContext.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Module.h" 23d1a85a744cc1001c2b7fc37cf37aca266964f519Brian Gaeke#include "llvm/Pass.h" 24f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/PassManager.h" 25551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/CommandLine.h" 26551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/Debug.h" 27551ccae044b0ff658fe629dd67edd5ffe75d10e8Reid Spencer#include "llvm/Support/FileUtilities.h" 281f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/Path.h" 291f6efa3996dd1929fbc129203ce5009b620e6969Michael J. Spencer#include "llvm/Support/Signals.h" 30f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Support/ToolOutputFile.h" 31f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Transforms/IPO.h" 32f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Transforms/Scalar.h" 33f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Transforms/Utils/Cloning.h" 34f010c464a11444733ec67e31aace8bcebeaf2588Chandler Carruth#include "llvm/Transforms/Utils/CodeExtractor.h" 35fb4b96e77e2930bf3d0c148f1c3685b6a4434666Chris Lattner#include <set> 36c6b519d64ef55d39e66a49510d4703a49bf228ccChris Lattnerusing namespace llvm; 37d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 38d0fde30ce850b78371fd1386338350591f9ff494Brian Gaekenamespace llvm { 39c6b519d64ef55d39e66a49510d4703a49bf228ccChris Lattner bool DisableSimplifyCFG = false; 4068ccdaa84909108c42417a8091c771598e26456eDaniel Dunbar extern cl::opt<std::string> OutputPrefix; 41d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke} // End llvm namespace 42d0fde30ce850b78371fd1386338350591f9ff494Brian Gaeke 436db70ef879916e6115ac97eb76e4fea973652e2cChris Lattnernamespace { 446db70ef879916e6115ac97eb76e4fea973652e2cChris Lattner cl::opt<bool> 456db70ef879916e6115ac97eb76e4fea973652e2cChris Lattner NoDCE ("disable-dce", 466db70ef879916e6115ac97eb76e4fea973652e2cChris Lattner cl::desc("Do not use the -dce pass to reduce testcases")); 4747ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner cl::opt<bool, true> 4847ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner NoSCFG("disable-simplifycfg", cl::location(DisableSimplifyCFG), 496db70ef879916e6115ac97eb76e4fea973652e2cChris Lattner cl::desc("Do not use the -simplifycfg pass to reduce testcases")); 50967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman 51967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman Function* globalInitUsesExternalBA(GlobalVariable* GV) { 52967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman if (!GV->hasInitializer()) 53967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman return 0; 54967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman 55967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman Constant *I = GV->getInitializer(); 56967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman 57967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman // walk the values used by the initializer 58967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman // (and recurse into things like ConstantExpr) 59967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman std::vector<Constant*> Todo; 60967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman std::set<Constant*> Done; 61967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman Todo.push_back(I); 62967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman 63967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman while (!Todo.empty()) { 64967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman Constant* V = Todo.back(); 65967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman Todo.pop_back(); 66967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman Done.insert(V); 67967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman 68967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman if (BlockAddress *BA = dyn_cast<BlockAddress>(V)) { 69967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman Function *F = BA->getFunction(); 70967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman if (F->isDeclaration()) 71967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman return F; 72967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman } 73967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman 74967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman for (User::op_iterator i = V->op_begin(), e = V->op_end(); i != e; ++i) { 75967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman Constant *C = dyn_cast<Constant>(*i); 76967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman if (C && !isa<GlobalValue>(C) && !Done.count(C)) 77967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman Todo.push_back(C); 78967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman } 79967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman } 80967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman return 0; 81967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman } 82967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman} // end anonymous namespace 83afade9294af43c6b947b9aeaa1555883d5f853e3Chris Lattner 846520785dcd22012535934098942d57c07c7631c2Chris Lattner/// deleteInstructionFromProgram - This method clones the current Program and 856520785dcd22012535934098942d57c07c7631c2Chris Lattner/// deletes the specified instruction from the cloned module. It then runs a 866520785dcd22012535934098942d57c07c7631c2Chris Lattner/// series of cleanup passes (ADCE and SimplifyCFG) to eliminate any code which 876520785dcd22012535934098942d57c07c7631c2Chris Lattner/// depends on the value. The modified module is then returned. 886520785dcd22012535934098942d57c07c7631c2Chris Lattner/// 890cc8807029f577996a442b96d24c3346ed6de091Chris LattnerModule *BugDriver::deleteInstructionFromProgram(const Instruction *I, 90866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola unsigned Simplification) { 91866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola // FIXME, use vmap? 92866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola Module *Clone = CloneModule(Program); 936520785dcd22012535934098942d57c07c7631c2Chris Lattner 940cc8807029f577996a442b96d24c3346ed6de091Chris Lattner const BasicBlock *PBB = I->getParent(); 950cc8807029f577996a442b96d24c3346ed6de091Chris Lattner const Function *PF = PBB->getParent(); 966520785dcd22012535934098942d57c07c7631c2Chris Lattner 97866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola Module::iterator RFI = Clone->begin(); // Get iterator to corresponding fn 980cc8807029f577996a442b96d24c3346ed6de091Chris Lattner std::advance(RFI, std::distance(PF->getParent()->begin(), 990cc8807029f577996a442b96d24c3346ed6de091Chris Lattner Module::const_iterator(PF))); 1006520785dcd22012535934098942d57c07c7631c2Chris Lattner 1016520785dcd22012535934098942d57c07c7631c2Chris Lattner Function::iterator RBI = RFI->begin(); // Get iterator to corresponding BB 1020cc8807029f577996a442b96d24c3346ed6de091Chris Lattner std::advance(RBI, std::distance(PF->begin(), Function::const_iterator(PBB))); 1036520785dcd22012535934098942d57c07c7631c2Chris Lattner 1046520785dcd22012535934098942d57c07c7631c2Chris Lattner BasicBlock::iterator RI = RBI->begin(); // Get iterator to corresponding inst 1050cc8807029f577996a442b96d24c3346ed6de091Chris Lattner std::advance(RI, std::distance(PBB->begin(), BasicBlock::const_iterator(I))); 1060cc8807029f577996a442b96d24c3346ed6de091Chris Lattner Instruction *TheInst = RI; // Got the corresponding instruction! 1076520785dcd22012535934098942d57c07c7631c2Chris Lattner 1086520785dcd22012535934098942d57c07c7631c2Chris Lattner // If this instruction produces a value, replace any users with null values 109e49a13e7260b83ce56d01446f2a165cc9f35da7fDan Gohman if (!TheInst->getType()->isVoidTy()) 110a7235ea7245028a0723e8ab7fd011386b3900777Owen Anderson TheInst->replaceAllUsesWith(Constant::getNullValue(TheInst->getType())); 1116520785dcd22012535934098942d57c07c7631c2Chris Lattner 1126520785dcd22012535934098942d57c07c7631c2Chris Lattner // Remove the instruction from the program. 1130cc8807029f577996a442b96d24c3346ed6de091Chris Lattner TheInst->getParent()->getInstList().erase(TheInst); 1146520785dcd22012535934098942d57c07c7631c2Chris Lattner 11544be25716628941b4cccccf56a28ee0ba2606850Chris Lattner // Spiff up the output a little bit. 116866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola std::vector<std::string> Passes; 1175da69c79f9c4490c6657c207430dfeb1060fc4ddChris Lattner 118866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola /// Can we get rid of the -disable-* options? 1196db70ef879916e6115ac97eb76e4fea973652e2cChris Lattner if (Simplification > 1 && !NoDCE) 120866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola Passes.push_back("dce"); 12147ae4a1cee5eec5767a11403c0fac7c91ec45461Chris Lattner if (Simplification && !DisableSimplifyCFG) 122866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola Passes.push_back("simplifycfg"); // Delete dead control flow 123866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola 124866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola Passes.push_back("verify"); 125866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola Module *New = runPassesOn(Clone, Passes); 126866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola delete Clone; 127866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola if (!New) { 128866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola errs() << "Instruction removal failed. Sorry. :( Please report a bug!\n"; 129866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola exit(1); 130866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola } 131866aa0d742b7bc9811fd1b45507af999c605205aRafael Espindola return New; 1326520785dcd22012535934098942d57c07c7631c2Chris Lattner} 133ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner 134ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner/// performFinalCleanups - This method clones the current Program and performs 135ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner/// a series of cleanups intended to get rid of extra cruft on the module 1369b5b1905dbad19de374e7617f615ba522ffe0468Chris Lattner/// before handing it to the user. 137ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner/// 138fcb6ec0c7e37c2d15ddb04878f05cbd69d1da036Chris LattnerModule *BugDriver::performFinalCleanups(Module *M, bool MayModifySemantics) { 13928b8ed90c75ce6c271500fa778fef252f267a5ffChris Lattner // Make all functions external, so GlobalDCE doesn't delete them... 14028b8ed90c75ce6c271500fa778fef252f267a5ffChris Lattner for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 14128b8ed90c75ce6c271500fa778fef252f267a5ffChris Lattner I->setLinkage(GlobalValue::ExternalLinkage); 1423da94aec4d429b2ba0f65fa040c33650cade196bMisha Brukman 1438261dfed05e32302469ef707cc881fed2c31f85fRafael Espindola std::vector<std::string> CleanupPasses; 1448261dfed05e32302469ef707cc881fed2c31f85fRafael Espindola CleanupPasses.push_back("globaldce"); 145fcb6ec0c7e37c2d15ddb04878f05cbd69d1da036Chris Lattner 146c6b519d64ef55d39e66a49510d4703a49bf228ccChris Lattner if (MayModifySemantics) 1478261dfed05e32302469ef707cc881fed2c31f85fRafael Espindola CleanupPasses.push_back("deadarghaX0r"); 148c6b519d64ef55d39e66a49510d4703a49bf228ccChris Lattner else 1498261dfed05e32302469ef707cc881fed2c31f85fRafael Espindola CleanupPasses.push_back("deadargelim"); 150fcb6ec0c7e37c2d15ddb04878f05cbd69d1da036Chris Lattner 151a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner Module *New = runPassesOn(M, CleanupPasses); 152a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner if (New == 0) { 15365f57c233cd4499e2e8b52a503201e64edfd6a9eDan Gohman errs() << "Final cleanups failed. Sorry. :( Please report a bug!\n"; 1549b5b1905dbad19de374e7617f615ba522ffe0468Chris Lattner return M; 155fcb6ec0c7e37c2d15ddb04878f05cbd69d1da036Chris Lattner } 156a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner delete M; 157a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner return New; 158ba386d943f4a83095d9c625cb0d46c1afe45ed1fChris Lattner} 159be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner 160be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner 1617546c3884a400b72d10fc19f120c6798b294a39dChris Lattner/// ExtractLoop - Given a module, extract up to one loop from it into a new 1627546c3884a400b72d10fc19f120c6798b294a39dChris Lattner/// function. This returns null if there are no extractable loops in the 1637546c3884a400b72d10fc19f120c6798b294a39dChris Lattner/// program or if the loop extractor crashes. 1647546c3884a400b72d10fc19f120c6798b294a39dChris LattnerModule *BugDriver::ExtractLoop(Module *M) { 1658261dfed05e32302469ef707cc881fed2c31f85fRafael Espindola std::vector<std::string> LoopExtractPasses; 1668261dfed05e32302469ef707cc881fed2c31f85fRafael Espindola LoopExtractPasses.push_back("loop-extract-single"); 1677546c3884a400b72d10fc19f120c6798b294a39dChris Lattner 168a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner Module *NewM = runPassesOn(M, LoopExtractPasses); 169a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner if (NewM == 0) { 170ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman outs() << "*** Loop extraction failed: "; 171bae1b71cbb930e419df03db209ebc547a0e4ec72Rafael Espindola EmitProgressBitcode(M, "loopextraction", true); 172ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman outs() << "*** Sorry. :( Please report a bug!\n"; 1737546c3884a400b72d10fc19f120c6798b294a39dChris Lattner return 0; 1747546c3884a400b72d10fc19f120c6798b294a39dChris Lattner } 175a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner 176a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner // Check to see if we created any new functions. If not, no loops were 177a269ec7b0a83d3b20730fd2d9f7c3ed5a552da90Chris Lattner // extracted and we should return null. Limit the number of loops we extract 178a269ec7b0a83d3b20730fd2d9f7c3ed5a552da90Chris Lattner // to avoid taking forever. 179a269ec7b0a83d3b20730fd2d9f7c3ed5a552da90Chris Lattner static unsigned NumExtracted = 32; 18090c18c5c69d9c451e5fdca1e4b4b95e8ed13291aChris Lattner if (M->size() == NewM->size() || --NumExtracted == 0) { 181a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner delete NewM; 182a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner return 0; 18390c18c5c69d9c451e5fdca1e4b4b95e8ed13291aChris Lattner } else { 18490c18c5c69d9c451e5fdca1e4b4b95e8ed13291aChris Lattner assert(M->size() < NewM->size() && "Loop extract removed functions?"); 18590c18c5c69d9c451e5fdca1e4b4b95e8ed13291aChris Lattner Module::iterator MI = NewM->begin(); 18690c18c5c69d9c451e5fdca1e4b4b95e8ed13291aChris Lattner for (unsigned i = 0, e = M->size(); i != e; ++i) 18790c18c5c69d9c451e5fdca1e4b4b95e8ed13291aChris Lattner ++MI; 188a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner } 1893da94aec4d429b2ba0f65fa040c33650cade196bMisha Brukman 190a75766a6c14b364b74b30546802e26d4b4b36a9bChris Lattner return NewM; 1917546c3884a400b72d10fc19f120c6798b294a39dChris Lattner} 1927546c3884a400b72d10fc19f120c6798b294a39dChris Lattner 1937546c3884a400b72d10fc19f120c6798b294a39dChris Lattner 194be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner// DeleteFunctionBody - "Remove" the function by deleting all of its basic 195be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner// blocks, making it external. 196be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner// 197be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattnervoid llvm::DeleteFunctionBody(Function *F) { 198be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner // delete the body of the function... 199be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner F->deleteBody(); 2005cbf985dcbc89fba3208e7baf8b6f488b06d3ec9Reid Spencer assert(F->isDeclaration() && "This didn't make the function external!"); 201be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner} 202be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner 2035a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner/// GetTorInit - Given a list of entries for static ctors/dtors, return them 2045a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner/// as a constant array. 2055a7a9e53861188ad84cb0e08e34562da744a907aChris Lattnerstatic Constant *GetTorInit(std::vector<std::pair<Function*, int> > &TorList) { 2065a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner assert(!TorList.empty() && "Don't create empty tor list!"); 2075a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner std::vector<Constant*> ArrayElts; 2085fdd6c8793462549e3593890ec61573da06e3346Jay Foad Type *Int32Ty = Type::getInt32Ty(TorList[0].first->getContext()); 209b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner 210db125cfaf57cc83e7dd7453de2d509bc8efd0e5eChris Lattner StructType *STy = 211b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner StructType::get(Int32Ty, TorList[0].first->getType(), NULL); 2125a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner for (unsigned i = 0, e = TorList.size(); i != e; ++i) { 213b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner Constant *Elts[] = { 214b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner ConstantInt::get(Int32Ty, TorList[i].second), 215b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner TorList[i].first 216b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner }; 217b065b06c12dba6001b8140df2744d0c856ef6ea1Chris Lattner ArrayElts.push_back(ConstantStruct::get(STy, Elts)); 2185a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner } 219debcb01b0f0a15f568ca69e8f288fade4bfc7297Owen Anderson return ConstantArray::get(ArrayType::get(ArrayElts[0]->getType(), 2205a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner ArrayElts.size()), 2215a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner ArrayElts); 2225a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner} 2235a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 2245a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner/// SplitStaticCtorDtor - A module was recently split into two parts, M1/M2, and 2255a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner/// M1 has all of the global variables. If M2 contains any functions that are 2265a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner/// static ctors/dtors, we need to add an llvm.global_[cd]tors global to M2, and 2275a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner/// prune appropriate entries out of M1s list. 228d50330cd02b00c8e3de40e8544c45701b9891d87Dan Gohmanstatic void SplitStaticCtorDtor(const char *GlobalName, Module *M1, Module *M2, 2291ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy &VMap) { 2305a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner GlobalVariable *GV = M1->getNamedGlobal(GlobalName); 231bb46f52027416598a662dc1c58f48d9d56b1a65bRafael Espindola if (!GV || GV->isDeclaration() || GV->hasLocalLinkage() || 2325a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner !GV->use_empty()) return; 2335a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 2345a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner std::vector<std::pair<Function*, int> > M1Tors, M2Tors; 2355a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner ConstantArray *InitList = dyn_cast<ConstantArray>(GV->getInitializer()); 2365a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner if (!InitList) return; 2375a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 2385a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner for (unsigned i = 0, e = InitList->getNumOperands(); i != e; ++i) { 2395a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner if (ConstantStruct *CS = dyn_cast<ConstantStruct>(InitList->getOperand(i))){ 2405a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner if (CS->getNumOperands() != 2) return; // Not array of 2-element structs. 2415a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 2425a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner if (CS->getOperand(1)->isNullValue()) 2435a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner break; // Found a null terminator, stop here. 2445a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 245b83eb6447ba155342598f0fabe1f08f5baa9164aReid Spencer ConstantInt *CI = dyn_cast<ConstantInt>(CS->getOperand(0)); 246b83eb6447ba155342598f0fabe1f08f5baa9164aReid Spencer int Priority = CI ? CI->getSExtValue() : 0; 2475a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 2485a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner Constant *FP = CS->getOperand(1); 2495a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner if (ConstantExpr *CE = dyn_cast<ConstantExpr>(FP)) 2503da59db637a887474c1b1346c1f3ccf53b6c4663Reid Spencer if (CE->isCast()) 2515a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner FP = CE->getOperand(0); 2525a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner if (Function *F = dyn_cast<Function>(FP)) { 2535cbf985dcbc89fba3208e7baf8b6f488b06d3ec9Reid Spencer if (!F->isDeclaration()) 2545a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner M1Tors.push_back(std::make_pair(F, Priority)); 2555a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner else { 2565a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner // Map to M2's version of the function. 257e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel F = cast<Function>(VMap[F]); 2585a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner M2Tors.push_back(std::make_pair(F, Priority)); 2595a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner } 2605a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner } 2615a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner } 2625a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner } 2635a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 2645a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner GV->eraseFromParent(); 2655a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner if (!M1Tors.empty()) { 2665a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner Constant *M1Init = GetTorInit(M1Tors); 267e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson new GlobalVariable(*M1, M1Init->getType(), false, 2683d29df3e8a203b167d8071ea6f805b21db18a5afOwen Anderson GlobalValue::AppendingLinkage, 269e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson M1Init, GlobalName); 2705a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner } 2715a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 2725a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner GV = M2->getNamedGlobal(GlobalName); 2735a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner assert(GV && "Not a clone of M1?"); 2745a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner assert(GV->use_empty() && "llvm.ctors shouldn't have uses!"); 2755a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 2765a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner GV->eraseFromParent(); 2775a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner if (!M2Tors.empty()) { 2785a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner Constant *M2Init = GetTorInit(M2Tors); 279e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson new GlobalVariable(*M2, M2Init->getType(), false, 2803d29df3e8a203b167d8071ea6f805b21db18a5afOwen Anderson GlobalValue::AppendingLinkage, 281e9b11b431308f4766b73cda93e38ec930c912122Owen Anderson M2Init, GlobalName); 2825a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner } 2835a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner} 2845a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 285e47863e212e0af6239f6f40b2496ede29847bbcePatrick Jenkins 286be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner/// SplitFunctionsOutOfModule - Given a module and a list of functions in the 287be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner/// module, split the functions OUT of the specified module, and place them in 288be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner/// the new module. 289d50330cd02b00c8e3de40e8544c45701b9891d87Dan GohmanModule * 290d50330cd02b00c8e3de40e8544c45701b9891d87Dan Gohmanllvm::SplitFunctionsOutOfModule(Module *M, 291d50330cd02b00c8e3de40e8544c45701b9891d87Dan Gohman const std::vector<Function*> &F, 2921ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy &VMap) { 293be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner // Make sure functions & globals are all external so that linkage 294be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner // between the two modules will work. 295be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I) 296be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner I->setLinkage(GlobalValue::ExternalLinkage); 2975a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 2987220b814ed6f432d1d31d444b65e0c3b120942dfOwen Anderson I != E; ++I) { 2993f53fa9a51c4ce7ba81170ca7ab2e49bd37281b0Daniel Dunbar if (I->hasName() && I->getName()[0] == '\01') 3003f53fa9a51c4ce7ba81170ca7ab2e49bd37281b0Daniel Dunbar I->setName(I->getName().substr(1)); 301be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner I->setLinkage(GlobalValue::ExternalLinkage); 3027220b814ed6f432d1d31d444b65e0c3b120942dfOwen Anderson } 303be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner 3041ed219a9d2279ce5a5bbcf16d9b7ccc05cce638cRafael Espindola ValueToValueMapTy NewVMap; 305e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel Module *New = CloneModule(M, NewVMap); 306be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner 307fef02427cda8dc0b3e6aedd6d78c4ba3e1e48069Chris Lattner // Remove the Test functions from the Safe module 308d50330cd02b00c8e3de40e8544c45701b9891d87Dan Gohman std::set<Function *> TestFunctions; 309be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner for (unsigned i = 0, e = F.size(); i != e; ++i) { 310e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel Function *TNOF = cast<Function>(VMap[F[i]]); 31165f57c233cd4499e2e8b52a503201e64edfd6a9eDan Gohman DEBUG(errs() << "Removing function "); 31265f57c233cd4499e2e8b52a503201e64edfd6a9eDan Gohman DEBUG(WriteAsOperand(errs(), TNOF, false)); 31365f57c233cd4499e2e8b52a503201e64edfd6a9eDan Gohman DEBUG(errs() << "\n"); 314e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel TestFunctions.insert(cast<Function>(NewVMap[TNOF])); 315fef02427cda8dc0b3e6aedd6d78c4ba3e1e48069Chris Lattner DeleteFunctionBody(TNOF); // Function is now external in this module! 316e47863e212e0af6239f6f40b2496ede29847bbcePatrick Jenkins } 317e47863e212e0af6239f6f40b2496ede29847bbcePatrick Jenkins 3185a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 319fef02427cda8dc0b3e6aedd6d78c4ba3e1e48069Chris Lattner // Remove the Safe functions from the Test module 320fef02427cda8dc0b3e6aedd6d78c4ba3e1e48069Chris Lattner for (Module::iterator I = New->begin(), E = New->end(); I != E; ++I) 321d50330cd02b00c8e3de40e8544c45701b9891d87Dan Gohman if (!TestFunctions.count(I)) 322fef02427cda8dc0b3e6aedd6d78c4ba3e1e48069Chris Lattner DeleteFunctionBody(I); 323fef02427cda8dc0b3e6aedd6d78c4ba3e1e48069Chris Lattner 324e47863e212e0af6239f6f40b2496ede29847bbcePatrick Jenkins 325967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman // Try to split the global initializers evenly 326967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman for (Module::global_iterator I = M->global_begin(), E = M->global_end(); 327967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman I != E; ++I) { 328967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman GlobalVariable *GV = cast<GlobalVariable>(NewVMap[I]); 329967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman if (Function *TestFn = globalInitUsesExternalBA(I)) { 330967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman if (Function *SafeFn = globalInitUsesExternalBA(GV)) { 331967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman errs() << "*** Error: when reducing functions, encountered " 332967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman "the global '"; 333967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman WriteAsOperand(errs(), GV, false); 334967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman errs() << "' with an initializer that references blockaddresses " 335967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman "from safe function '" << SafeFn->getName() 336967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman << "' and from test function '" << TestFn->getName() << "'.\n"; 337967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman exit(1); 338967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman } 339967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman I->setInitializer(0); // Delete the initializer to make it external 340967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman } else { 341967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman // If we keep it in the safe module, then delete it in the test module 342967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman GV->setInitializer(0); 343967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman } 344967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman } 345967570f2ecdbedeae80bcc19744cf111c3e112e1Eli Friedman 3465a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner // Make sure that there is a global ctor/dtor array in both halves of the 3475a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner // module if they both have static ctor/dtor functions. 348e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel SplitStaticCtorDtor("llvm.global_ctors", M, New, NewVMap); 349e9916a302f1bacad234d7dafc1df3dc968a6ba0fDevang Patel SplitStaticCtorDtor("llvm.global_dtors", M, New, NewVMap); 3505a7a9e53861188ad84cb0e08e34562da744a907aChris Lattner 351be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner return New; 352be21ca54e08339ede5dd4bbb882182d22e274988Chris Lattner} 3535e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner 3545e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner//===----------------------------------------------------------------------===// 3555e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner// Basic Block Extraction Code 3565e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner//===----------------------------------------------------------------------===// 3575e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner 3585e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner/// ExtractMappedBlocksFromModule - Extract all but the specified basic blocks 3595e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner/// into their own functions. The only detail is that M is actually a module 3605e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner/// cloned from the one the BBs are in, so some mapping needs to be performed. 3615e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner/// If this operation fails for some reason (ie the implementation is buggy), 3625e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner/// this function should return null, otherwise it returns a new Module. 3635e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris LattnerModule *BugDriver::ExtractMappedBlocksFromModule(const 3645e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner std::vector<BasicBlock*> &BBs, 3655e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner Module *M) { 36668ccdaa84909108c42417a8091c771598e26456eDaniel Dunbar sys::Path uniqueFilename(OutputPrefix + "-extractblocks"); 3676fa98b13206583e6eb90b8304758b35548914944Nick Lewycky std::string ErrMsg; 3686fa98b13206583e6eb90b8304758b35548914944Nick Lewycky if (uniqueFilename.createTemporaryFileOnDisk(true, &ErrMsg)) { 369ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman outs() << "*** Basic Block extraction failed!\n"; 37065f57c233cd4499e2e8b52a503201e64edfd6a9eDan Gohman errs() << "Error creating temporary file: " << ErrMsg << "\n"; 371bae1b71cbb930e419df03db209ebc547a0e4ec72Rafael Espindola EmitProgressBitcode(M, "basicblockextractfail", true); 3726fa98b13206583e6eb90b8304758b35548914944Nick Lewycky return 0; 3736fa98b13206583e6eb90b8304758b35548914944Nick Lewycky } 3746fa98b13206583e6eb90b8304758b35548914944Nick Lewycky sys::RemoveFileOnSignal(uniqueFilename); 3756fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 376ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman std::string ErrorInfo; 377f29140106f74d15ba357aa0a7f109adc939c3104Dan Gohman tool_output_file BlocksToNotExtractFile(uniqueFilename.c_str(), ErrorInfo); 378ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman if (!ErrorInfo.empty()) { 379ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman outs() << "*** Basic Block extraction failed!\n"; 380ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman errs() << "Error writing list of blocks to not extract: " << ErrorInfo 38165f57c233cd4499e2e8b52a503201e64edfd6a9eDan Gohman << "\n"; 382bae1b71cbb930e419df03db209ebc547a0e4ec72Rafael Espindola EmitProgressBitcode(M, "basicblockextractfail", true); 3836fa98b13206583e6eb90b8304758b35548914944Nick Lewycky return 0; 3846fa98b13206583e6eb90b8304758b35548914944Nick Lewycky } 3856fa98b13206583e6eb90b8304758b35548914944Nick Lewycky for (std::vector<BasicBlock*>::const_iterator I = BBs.begin(), E = BBs.end(); 3866fa98b13206583e6eb90b8304758b35548914944Nick Lewycky I != E; ++I) { 3876fa98b13206583e6eb90b8304758b35548914944Nick Lewycky BasicBlock *BB = *I; 3884a6a6f21f3342428e5dcf28b0ddfbe0039a040e5Chris Lattner // If the BB doesn't have a name, give it one so we have something to key 3894a6a6f21f3342428e5dcf28b0ddfbe0039a040e5Chris Lattner // off of. 3904a6a6f21f3342428e5dcf28b0ddfbe0039a040e5Chris Lattner if (!BB->hasName()) BB->setName("tmpbb"); 391a7b0cb759433c715065440ee2a963a04db7f2b0bBenjamin Kramer BlocksToNotExtractFile.os() << BB->getParent()->getName() << " " 392d4c454317a38d65957edebe62bfc69fc8d9885e8Dan Gohman << BB->getName() << "\n"; 3936fa98b13206583e6eb90b8304758b35548914944Nick Lewycky } 394d4c454317a38d65957edebe62bfc69fc8d9885e8Dan Gohman BlocksToNotExtractFile.os().close(); 395d4c454317a38d65957edebe62bfc69fc8d9885e8Dan Gohman if (BlocksToNotExtractFile.os().has_error()) { 396f29140106f74d15ba357aa0a7f109adc939c3104Dan Gohman errs() << "Error writing list of blocks to not extract: " << ErrorInfo 397f29140106f74d15ba357aa0a7f109adc939c3104Dan Gohman << "\n"; 398f29140106f74d15ba357aa0a7f109adc939c3104Dan Gohman EmitProgressBitcode(M, "basicblockextractfail", true); 399d4c454317a38d65957edebe62bfc69fc8d9885e8Dan Gohman BlocksToNotExtractFile.os().clear_error(); 400f29140106f74d15ba357aa0a7f109adc939c3104Dan Gohman return 0; 401f29140106f74d15ba357aa0a7f109adc939c3104Dan Gohman } 402f29140106f74d15ba357aa0a7f109adc939c3104Dan Gohman BlocksToNotExtractFile.keep(); 4036fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 40412ea66a7277240c5b045ed14c140f94d453eea0eBenjamin Kramer std::string uniqueFN = "--extract-blocks-file=" + uniqueFilename.str(); 40512ea66a7277240c5b045ed14c140f94d453eea0eBenjamin Kramer const char *ExtraArg = uniqueFN.c_str(); 4066fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 4078261dfed05e32302469ef707cc881fed2c31f85fRafael Espindola std::vector<std::string> PI; 4088261dfed05e32302469ef707cc881fed2c31f85fRafael Espindola PI.push_back("extract-blocks"); 4096fa98b13206583e6eb90b8304758b35548914944Nick Lewycky Module *Ret = runPassesOn(M, PI, false, 1, &ExtraArg); 4106fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 411d27047f87dae7c6eb59069b1e5d1368a0b2db5ffDan Gohman uniqueFilename.eraseFromDisk(); // Free disk space 4126fa98b13206583e6eb90b8304758b35548914944Nick Lewycky 413891150f0b2a124a75c9f31516182ce864ae69ef8Chris Lattner if (Ret == 0) { 414ac95cc79ac0b899d566cc29c0f646f39c2fa35c0Dan Gohman outs() << "*** Basic Block extraction failed, please report a bug!\n"; 415bae1b71cbb930e419df03db209ebc547a0e4ec72Rafael Espindola EmitProgressBitcode(M, "basicblockextractfail", true); 416891150f0b2a124a75c9f31516182ce864ae69ef8Chris Lattner } 4175e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner return Ret; 4185e783ab0b5fc3407ec59f1a598fdb9ef3b96b287Chris Lattner} 419