Page MenuHomePhabricator

No OneTemporary

File Metadata

Created
Jan 24 2020, 3:51 PM
This file is larger than 256 KB, so syntax highlighting was skipped.
Index: llvm/trunk/tools/bugpoint/TestPasses.cpp
===================================================================
--- llvm/trunk/tools/bugpoint/TestPasses.cpp (revision 15333)
+++ llvm/trunk/tools/bugpoint/TestPasses.cpp (revision 15334)
@@ -1,64 +1,64 @@
//===- TestPasses.cpp - "buggy" passes used to test bugpoint --------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file contains "buggy" passes that are used to test bugpoint, to check
// that it is narrowing down testcases correctly.
//
//===----------------------------------------------------------------------===//
#include "llvm/BasicBlock.h"
#include "llvm/Constant.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include "llvm/Pass.h"
#include "llvm/Support/InstVisitor.h"
using namespace llvm;
namespace {
/// CrashOnCalls - This pass is used to test bugpoint. It intentionally
/// crashes on any call instructions.
class CrashOnCalls : public BasicBlockPass {
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
}
bool runOnBasicBlock(BasicBlock &BB) {
for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
if (isa<CallInst>(*I))
abort();
return false;
}
};
RegisterPass<CrashOnCalls>
X("bugpoint-crashcalls",
"BugPoint Test Pass - Intentionally crash on CallInsts");
}
namespace {
/// DeleteCalls - This pass is used to test bugpoint. It intentionally
/// deletes some call instructions, "misoptimizing" the program.
class DeleteCalls : public BasicBlockPass {
bool runOnBasicBlock(BasicBlock &BB) {
for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I)
if (CallInst *CI = dyn_cast<CallInst>(I)) {
if (!CI->use_empty())
CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
CI->getParent()->getInstList().erase(CI);
break;
}
return false;
}
};
RegisterPass<DeleteCalls>
Y("bugpoint-deletecalls",
"BugPoint Test Pass - Intentionally 'misoptimize' CallInsts");
}
Property changes on: llvm/trunk/tools/bugpoint/TestPasses.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.7
\ No newline at end of property
+1.8
\ No newline at end of property
Index: llvm/trunk/tools/bugpoint/CrashDebugger.cpp
===================================================================
--- llvm/trunk/tools/bugpoint/CrashDebugger.cpp (revision 15333)
+++ llvm/trunk/tools/bugpoint/CrashDebugger.cpp (revision 15334)
@@ -1,445 +1,445 @@
//===- CrashDebugger.cpp - Debug compilation crashes ----------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the bugpoint internals that narrow down compilation crashes
//
//===----------------------------------------------------------------------===//
#include "BugDriver.h"
#include "ListReducer.h"
#include "llvm/Constant.h"
-#include "llvm/iTerminators.h"
+#include "llvm/Instructions.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/PassManager.h"
#include "llvm/SymbolTable.h"
#include "llvm/Type.h"
#include "llvm/Analysis/Verifier.h"
#include "llvm/Bytecode/Writer.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/ToolRunner.h"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Cloning.h"
#include "Support/FileUtilities.h"
#include <fstream>
#include <set>
using namespace llvm;
namespace llvm {
class ReducePassList : public ListReducer<const PassInfo*> {
BugDriver &BD;
public:
ReducePassList(BugDriver &bd) : BD(bd) {}
// doTest - Return true iff running the "removed" passes succeeds, and
// running the "Kept" passes fail when run on the output of the "removed"
// passes. If we return true, we update the current module of bugpoint.
//
virtual TestResult doTest(std::vector<const PassInfo*> &Removed,
std::vector<const PassInfo*> &Kept);
};
}
ReducePassList::TestResult
ReducePassList::doTest(std::vector<const PassInfo*> &Prefix,
std::vector<const PassInfo*> &Suffix) {
std::string PrefixOutput;
Module *OrigProgram = 0;
if (!Prefix.empty()) {
std::cout << "Checking to see if these passes crash: "
<< getPassesString(Prefix) << ": ";
if (BD.runPasses(Prefix, PrefixOutput))
return KeepPrefix;
OrigProgram = BD.Program;
BD.Program = ParseInputFile(PrefixOutput);
if (BD.Program == 0) {
std::cerr << BD.getToolName() << ": Error reading bytecode file '"
<< PrefixOutput << "'!\n";
exit(1);
}
removeFile(PrefixOutput);
}
std::cout << "Checking to see if these passes crash: "
<< getPassesString(Suffix) << ": ";
if (BD.runPasses(Suffix)) {
delete OrigProgram; // The suffix crashes alone...
return KeepSuffix;
}
// Nothing failed, restore state...
if (OrigProgram) {
delete BD.Program;
BD.Program = OrigProgram;
}
return NoFailure;
}
namespace llvm {
class ReduceCrashingFunctions : public ListReducer<Function*> {
BugDriver &BD;
bool (*TestFn)(BugDriver &, Module *);
public:
ReduceCrashingFunctions(BugDriver &bd,
bool (*testFn)(BugDriver &, Module *))
: BD(bd), TestFn(testFn) {}
virtual TestResult doTest(std::vector<Function*> &Prefix,
std::vector<Function*> &Kept) {
if (!Kept.empty() && TestFuncs(Kept))
return KeepSuffix;
if (!Prefix.empty() && TestFuncs(Prefix))
return KeepPrefix;
return NoFailure;
}
bool TestFuncs(std::vector<Function*> &Prefix);
};
}
bool ReduceCrashingFunctions::TestFuncs(std::vector<Function*> &Funcs) {
// Clone the program to try hacking it apart...
Module *M = CloneModule(BD.getProgram());
// Convert list to set for fast lookup...
std::set<Function*> Functions;
for (unsigned i = 0, e = Funcs.size(); i != e; ++i) {
Function *CMF = M->getFunction(Funcs[i]->getName(),
Funcs[i]->getFunctionType());
assert(CMF && "Function not in module?!");
Functions.insert(CMF);
}
std::cout << "Checking for crash with only these functions: ";
PrintFunctionList(Funcs);
std::cout << ": ";
// Loop over and delete any functions which we aren't supposed to be playing
// with...
for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
if (!I->isExternal() && !Functions.count(I))
DeleteFunctionBody(I);
// Try running the hacked up program...
if (TestFn(BD, M)) {
BD.setNewProgram(M); // It crashed, keep the trimmed version...
// Make sure to use function pointers that point into the now-current
// module.
Funcs.assign(Functions.begin(), Functions.end());
return true;
}
delete M;
return false;
}
namespace {
/// ReduceCrashingBlocks reducer - This works by setting the terminators of
/// all terminators except the specified basic blocks to a 'ret' instruction,
/// then running the simplify-cfg pass. This has the effect of chopping up
/// the CFG really fast which can reduce large functions quickly.
///
class ReduceCrashingBlocks : public ListReducer<const BasicBlock*> {
BugDriver &BD;
bool (*TestFn)(BugDriver &, Module *);
public:
ReduceCrashingBlocks(BugDriver &bd, bool (*testFn)(BugDriver &, Module *))
: BD(bd), TestFn(testFn) {}
virtual TestResult doTest(std::vector<const BasicBlock*> &Prefix,
std::vector<const BasicBlock*> &Kept) {
if (!Kept.empty() && TestBlocks(Kept))
return KeepSuffix;
if (!Prefix.empty() && TestBlocks(Prefix))
return KeepPrefix;
return NoFailure;
}
bool TestBlocks(std::vector<const BasicBlock*> &Prefix);
};
}
bool ReduceCrashingBlocks::TestBlocks(std::vector<const BasicBlock*> &BBs) {
// Clone the program to try hacking it apart...
Module *M = CloneModule(BD.getProgram());
// Convert list to set for fast lookup...
std::set<BasicBlock*> Blocks;
for (unsigned i = 0, e = BBs.size(); i != e; ++i) {
// Convert the basic block from the original module to the new module...
const Function *F = BBs[i]->getParent();
Function *CMF = M->getFunction(F->getName(), F->getFunctionType());
assert(CMF && "Function not in module?!");
// Get the mapped basic block...
Function::iterator CBI = CMF->begin();
std::advance(CBI, std::distance(F->begin(),
Function::const_iterator(BBs[i])));
Blocks.insert(CBI);
}
std::cout << "Checking for crash with only these blocks:";
unsigned NumPrint = Blocks.size();
if (NumPrint > 10) NumPrint = 10;
for (unsigned i = 0, e = NumPrint; i != e; ++i)
std::cout << " " << BBs[i]->getName();
if (NumPrint < Blocks.size())
std::cout << "... <" << Blocks.size() << " total>";
std::cout << ": ";
// Loop over and delete any hack up any blocks that are not listed...
for (Module::iterator I = M->begin(), E = M->end(); I != E; ++I)
for (Function::iterator BB = I->begin(), E = I->end(); BB != E; ++BB)
if (!Blocks.count(BB) && BB->getTerminator()->getNumSuccessors()) {
// Loop over all of the successors of this block, deleting any PHI nodes
// that might include it.
for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
(*SI)->removePredecessor(BB);
if (BB->getTerminator()->getType() != Type::VoidTy)
BB->getTerminator()->replaceAllUsesWith(
Constant::getNullValue(BB->getTerminator()->getType()));
// Delete the old terminator instruction...
BB->getInstList().pop_back();
// Add a new return instruction of the appropriate type...
const Type *RetTy = BB->getParent()->getReturnType();
new ReturnInst(RetTy == Type::VoidTy ? 0 :
Constant::getNullValue(RetTy), BB);
}
// The CFG Simplifier pass may delete one of the basic blocks we are
// interested in. If it does we need to take the block out of the list. Make
// a "persistent mapping" by turning basic blocks into <function, name> pairs.
// This won't work well if blocks are unnamed, but that is just the risk we
// have to take.
std::vector<std::pair<Function*, std::string> > BlockInfo;
for (std::set<BasicBlock*>::iterator I = Blocks.begin(), E = Blocks.end();
I != E; ++I)
BlockInfo.push_back(std::make_pair((*I)->getParent(), (*I)->getName()));
// Now run the CFG simplify pass on the function...
PassManager Passes;
Passes.add(createCFGSimplificationPass());
Passes.add(createVerifierPass());
Passes.run(*M);
// Try running on the hacked up program...
if (TestFn(BD, M)) {
BD.setNewProgram(M); // It crashed, keep the trimmed version...
// Make sure to use basic block pointers that point into the now-current
// module, and that they don't include any deleted blocks.
BBs.clear();
for (unsigned i = 0, e = BlockInfo.size(); i != e; ++i) {
SymbolTable &ST = BlockInfo[i].first->getSymbolTable();
SymbolTable::plane_iterator PI = ST.find(Type::LabelTy);
if (PI != ST.plane_end() && PI->second.count(BlockInfo[i].second))
BBs.push_back(cast<BasicBlock>(PI->second[BlockInfo[i].second]));
}
return true;
}
delete M; // It didn't crash, try something else.
return false;
}
/// DebugACrash - Given a predicate that determines whether a component crashes
/// on a program, try to destructively reduce the program while still keeping
/// the predicate true.
static bool DebugACrash(BugDriver &BD, bool (*TestFn)(BugDriver &, Module *)) {
bool AnyReduction = false;
// See if we can get away with nuking all of the global variable initializers
// in the program...
if (BD.getProgram()->gbegin() != BD.getProgram()->gend()) {
Module *M = CloneModule(BD.getProgram());
bool DeletedInit = false;
for (Module::giterator I = M->gbegin(), E = M->gend(); I != E; ++I)
if (I->hasInitializer()) {
I->setInitializer(0);
I->setLinkage(GlobalValue::ExternalLinkage);
DeletedInit = true;
}
if (!DeletedInit) {
delete M; // No change made...
} else {
// See if the program still causes a crash...
std::cout << "\nChecking to see if we can delete global inits: ";
if (TestFn(BD, M)) { // Still crashes?
BD.setNewProgram(M);
AnyReduction = true;
std::cout << "\n*** Able to remove all global initializers!\n";
} else { // No longer crashes?
std::cout << " - Removing all global inits hides problem!\n";
delete M;
}
}
}
// Now try to reduce the number of functions in the module to something small.
std::vector<Function*> Functions;
for (Module::iterator I = BD.getProgram()->begin(),
E = BD.getProgram()->end(); I != E; ++I)
if (!I->isExternal())
Functions.push_back(I);
if (Functions.size() > 1) {
std::cout << "\n*** Attempting to reduce the number of functions "
"in the testcase\n";
unsigned OldSize = Functions.size();
ReduceCrashingFunctions(BD, TestFn).reduceList(Functions);
if (Functions.size() < OldSize) {
BD.EmitProgressBytecode("reduced-function");
AnyReduction = true;
}
}
// Attempt to delete entire basic blocks at a time to speed up
// convergence... this actually works by setting the terminator of the blocks
// to a return instruction then running simplifycfg, which can potentially
// shrinks the code dramatically quickly
//
if (!DisableSimplifyCFG) {
std::vector<const BasicBlock*> Blocks;
for (Module::const_iterator I = BD.getProgram()->begin(),
E = BD.getProgram()->end(); I != E; ++I)
for (Function::const_iterator FI = I->begin(), E = I->end(); FI !=E; ++FI)
Blocks.push_back(FI);
ReduceCrashingBlocks(BD, TestFn).reduceList(Blocks);
}
// FIXME: This should use the list reducer to converge faster by deleting
// larger chunks of instructions at a time!
unsigned Simplification = 2;
do {
--Simplification;
std::cout << "\n*** Attempting to reduce testcase by deleting instruc"
<< "tions: Simplification Level #" << Simplification << '\n';
// Now that we have deleted the functions that are unnecessary for the
// program, try to remove instructions that are not necessary to cause the
// crash. To do this, we loop through all of the instructions in the
// remaining functions, deleting them (replacing any values produced with
// nulls), and then running ADCE and SimplifyCFG. If the transformed input
// still triggers failure, keep deleting until we cannot trigger failure
// anymore.
//
unsigned InstructionsToSkipBeforeDeleting = 0;
TryAgain:
// Loop over all of the (non-terminator) instructions remaining in the
// function, attempting to delete them.
unsigned CurInstructionNum = 0;
for (Module::const_iterator FI = BD.getProgram()->begin(),
E = BD.getProgram()->end(); FI != E; ++FI)
if (!FI->isExternal())
for (Function::const_iterator BI = FI->begin(), E = FI->end(); BI != E;
++BI)
for (BasicBlock::const_iterator I = BI->begin(), E = --BI->end();
I != E; ++I, ++CurInstructionNum)
if (InstructionsToSkipBeforeDeleting) {
--InstructionsToSkipBeforeDeleting;
} else {
std::cout << "Checking instruction '" << I->getName() << "': ";
Module *M = BD.deleteInstructionFromProgram(I, Simplification);
// Find out if the pass still crashes on this pass...
if (TestFn(BD, M)) {
// Yup, it does, we delete the old module, and continue trying
// to reduce the testcase...
BD.setNewProgram(M);
AnyReduction = true;
InstructionsToSkipBeforeDeleting = CurInstructionNum;
goto TryAgain; // I wish I had a multi-level break here!
}
// This pass didn't crash without this instruction, try the next
// one.
delete M;
}
if (InstructionsToSkipBeforeDeleting) {
InstructionsToSkipBeforeDeleting = 0;
goto TryAgain;
}
} while (Simplification);
// Try to clean up the testcase by running funcresolve and globaldce...
std::cout << "\n*** Attempting to perform final cleanups: ";
Module *M = CloneModule(BD.getProgram());
M = BD.performFinalCleanups(M, true);
// Find out if the pass still crashes on the cleaned up program...
if (TestFn(BD, M)) {
BD.setNewProgram(M); // Yup, it does, keep the reduced version...
AnyReduction = true;
} else {
delete M;
}
if (AnyReduction)
BD.EmitProgressBytecode("reduced-simplified");
return false;
}
static bool TestForOptimizerCrash(BugDriver &BD, Module *M) {
return BD.runPasses(M);
}
/// debugOptimizerCrash - This method is called when some pass crashes on input.
/// It attempts to prune down the testcase to something reasonable, and figure
/// out exactly which pass is crashing.
///
bool BugDriver::debugOptimizerCrash() {
std::cout << "\n*** Debugging optimizer crash!\n";
// Reduce the list of passes which causes the optimizer to crash...
unsigned OldSize = PassesToRun.size();
ReducePassList(*this).reduceList(PassesToRun);
std::cout << "\n*** Found crashing pass"
<< (PassesToRun.size() == 1 ? ": " : "es: ")
<< getPassesString(PassesToRun) << '\n';
EmitProgressBytecode("passinput");
return DebugACrash(*this, TestForOptimizerCrash);
}
static bool TestForCodeGenCrash(BugDriver &BD, Module *M) {
try {
std::cerr << '\n';
BD.compileProgram(M);
std::cerr << '\n';
return false;
} catch (ToolExecutionError &TEE) {
std::cerr << "<crash>\n";
return true; // Tool is still crashing.
}
}
/// debugCodeGeneratorCrash - This method is called when the code generator
/// crashes on an input. It attempts to reduce the input as much as possible
/// while still causing the code generator to crash.
bool BugDriver::debugCodeGeneratorCrash() {
std::cerr << "*** Debugging code generator crash!\n";
return DebugACrash(*this, TestForCodeGenCrash);
}
Property changes on: llvm/trunk/tools/bugpoint/CrashDebugger.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.36
\ No newline at end of property
+1.37
\ No newline at end of property
Index: llvm/trunk/lib/CodeGen/IntrinsicLowering.cpp
===================================================================
--- llvm/trunk/lib/CodeGen/IntrinsicLowering.cpp (revision 15333)
+++ llvm/trunk/lib/CodeGen/IntrinsicLowering.cpp (revision 15334)
@@ -1,216 +1,216 @@
//===-- IntrinsicLowering.cpp - Intrinsic Lowering default implementation -===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the default intrinsic lowering implementation.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/IntrinsicLowering.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include <iostream>
using namespace llvm;
template <class ArgIt>
static Function *EnsureFunctionExists(Module &M, const char *Name,
ArgIt ArgBegin, ArgIt ArgEnd,
const Type *RetTy) {
if (Function *F = M.getNamedFunction(Name)) return F;
// It doesn't already exist in the program, insert a new definition now.
std::vector<const Type *> ParamTys;
for (ArgIt I = ArgBegin; I != ArgEnd; ++I)
ParamTys.push_back(I->getType());
return M.getOrInsertFunction(Name, FunctionType::get(RetTy, ParamTys, false));
}
/// ReplaceCallWith - This function is used when we want to lower an intrinsic
/// call to a call of an external function. This handles hard cases such as
/// when there was already a prototype for the external function, and if that
/// prototype doesn't match the arguments we expect to pass in.
template <class ArgIt>
static CallInst *ReplaceCallWith(const char *NewFn, CallInst *CI,
ArgIt ArgBegin, ArgIt ArgEnd,
const Type *RetTy, Function *&FCache) {
if (!FCache) {
// If we haven't already looked up this function, check to see if the
// program already contains a function with this name.
Module *M = CI->getParent()->getParent()->getParent();
FCache = M->getNamedFunction(NewFn);
if (!FCache) {
// It doesn't already exist in the program, insert a new definition now.
std::vector<const Type *> ParamTys;
for (ArgIt I = ArgBegin; I != ArgEnd; ++I)
ParamTys.push_back((*I)->getType());
FCache = M->getOrInsertFunction(NewFn,
FunctionType::get(RetTy, ParamTys, false));
}
}
const FunctionType *FT = FCache->getFunctionType();
std::vector<Value*> Operands;
unsigned ArgNo = 0;
for (ArgIt I = ArgBegin; I != ArgEnd && ArgNo != FT->getNumParams();
++I, ++ArgNo) {
Value *Arg = *I;
if (Arg->getType() != FT->getParamType(ArgNo))
Arg = new CastInst(Arg, FT->getParamType(ArgNo), Arg->getName(), CI);
Operands.push_back(Arg);
}
// Pass nulls into any additional arguments...
for (; ArgNo != FT->getNumParams(); ++ArgNo)
Operands.push_back(Constant::getNullValue(FT->getParamType(ArgNo)));
std::string Name = CI->getName(); CI->setName("");
if (FT->getReturnType() == Type::VoidTy) Name.clear();
CallInst *NewCI = new CallInst(FCache, Operands, Name, CI);
if (!CI->use_empty()) {
Value *V = NewCI;
if (CI->getType() != NewCI->getType())
V = new CastInst(NewCI, CI->getType(), Name, CI);
CI->replaceAllUsesWith(V);
}
return NewCI;
}
void DefaultIntrinsicLowering::AddPrototypes(Module &M) {
for (Module::iterator I = M.begin(), E = M.end(); I != E; ++I)
if (I->isExternal() && !I->use_empty())
switch (I->getIntrinsicID()) {
default: break;
case Intrinsic::setjmp:
EnsureFunctionExists(M, "setjmp", I->abegin(), I->aend(), Type::IntTy);
break;
case Intrinsic::longjmp:
EnsureFunctionExists(M, "longjmp", I->abegin(), I->aend(),Type::VoidTy);
break;
case Intrinsic::siglongjmp:
EnsureFunctionExists(M, "abort", I->aend(), I->aend(), Type::VoidTy);
break;
case Intrinsic::memcpy:
EnsureFunctionExists(M, "memcpy", I->abegin(), --I->aend(),
I->abegin()->getType());
break;
case Intrinsic::memmove:
EnsureFunctionExists(M, "memmove", I->abegin(), --I->aend(),
I->abegin()->getType());
break;
case Intrinsic::memset:
EnsureFunctionExists(M, "memset", I->abegin(), --I->aend(),
I->abegin()->getType());
break;
case Intrinsic::isunordered:
EnsureFunctionExists(M, "isunordered", I->abegin(), I->aend(), Type::BoolTy);
break;
}
}
void DefaultIntrinsicLowering::LowerIntrinsicCall(CallInst *CI) {
Function *Callee = CI->getCalledFunction();
assert(Callee && "Cannot lower an indirect call!");
switch (Callee->getIntrinsicID()) {
case Intrinsic::not_intrinsic:
std::cerr << "Cannot lower a call to a non-intrinsic function '"
<< Callee->getName() << "'!\n";
abort();
default:
std::cerr << "Error: Code generator does not support intrinsic function '"
<< Callee->getName() << "'!\n";
abort();
// The setjmp/longjmp intrinsics should only exist in the code if it was
// never optimized (ie, right out of the CFE), or if it has been hacked on
// by the lowerinvoke pass. In both cases, the right thing to do is to
// convert the call to an explicit setjmp or longjmp call.
case Intrinsic::setjmp: {
static Function *SetjmpFCache = 0;
Value *V = ReplaceCallWith("setjmp", CI, CI->op_begin()+1, CI->op_end(),
Type::IntTy, SetjmpFCache);
if (CI->getType() != Type::VoidTy)
CI->replaceAllUsesWith(V);
break;
}
case Intrinsic::sigsetjmp:
if (CI->getType() != Type::VoidTy)
CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
break;
case Intrinsic::longjmp: {
static Function *LongjmpFCache = 0;
ReplaceCallWith("longjmp", CI, CI->op_begin()+1, CI->op_end(),
Type::VoidTy, LongjmpFCache);
break;
}
case Intrinsic::siglongjmp: {
// Insert the call to abort
static Function *AbortFCache = 0;
ReplaceCallWith("abort", CI, CI->op_end(), CI->op_end(), Type::VoidTy,
AbortFCache);
break;
}
case Intrinsic::returnaddress:
case Intrinsic::frameaddress:
std::cerr << "WARNING: this target does not support the llvm."
<< (Callee->getIntrinsicID() == Intrinsic::returnaddress ?
"return" : "frame") << "address intrinsic.\n";
CI->replaceAllUsesWith(ConstantPointerNull::get(
cast<PointerType>(CI->getType())));
break;
case Intrinsic::dbg_stoppoint:
case Intrinsic::dbg_region_start:
case Intrinsic::dbg_region_end:
case Intrinsic::dbg_declare:
case Intrinsic::dbg_func_start:
if (CI->getType() != Type::VoidTy)
CI->replaceAllUsesWith(Constant::getNullValue(CI->getType()));
break; // Simply strip out debugging intrinsics
case Intrinsic::memcpy: {
// The memcpy intrinsic take an extra alignment argument that the memcpy
// libc function does not.
static Function *MemcpyFCache = 0;
ReplaceCallWith("memcpy", CI, CI->op_begin()+1, CI->op_end()-1,
(*(CI->op_begin()+1))->getType(), MemcpyFCache);
break;
}
case Intrinsic::memmove: {
// The memmove intrinsic take an extra alignment argument that the memmove
// libc function does not.
static Function *MemmoveFCache = 0;
ReplaceCallWith("memmove", CI, CI->op_begin()+1, CI->op_end()-1,
(*(CI->op_begin()+1))->getType(), MemmoveFCache);
break;
}
case Intrinsic::memset: {
// The memset intrinsic take an extra alignment argument that the memset
// libc function does not.
static Function *MemsetFCache = 0;
ReplaceCallWith("memset", CI, CI->op_begin()+1, CI->op_end()-1,
(*(CI->op_begin()+1))->getType(), MemsetFCache);
break;
}
case Intrinsic::isunordered: {
static Function *isunorderedFCache = 0;
ReplaceCallWith("isunordered", CI, CI->op_begin()+1, CI->op_end(),
Type::BoolTy, isunorderedFCache);
break;
}
}
assert(CI->use_empty() &&
"Lowering should have eliminated any uses of the intrinsic call!");
CI->getParent()->getInstList().erase(CI);
}
Property changes on: llvm/trunk/lib/CodeGen/IntrinsicLowering.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.20
\ No newline at end of property
+1.21
\ No newline at end of property
Index: llvm/trunk/lib/CodeGen/MachineFunction.cpp
===================================================================
--- llvm/trunk/lib/CodeGen/MachineFunction.cpp (revision 15333)
+++ llvm/trunk/lib/CodeGen/MachineFunction.cpp (revision 15334)
@@ -1,484 +1,484 @@
//===-- MachineFunction.cpp -----------------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Collect native machine code information for a function. This allows
// target-specific information about the generated code to be stored with each
// function.
//
//===----------------------------------------------------------------------===//
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/SSARegMap.h"
#include "llvm/CodeGen/MachineFunctionInfo.h"
#include "llvm/CodeGen/MachineFrameInfo.h"
#include "llvm/CodeGen/MachineConstantPool.h"
#include "llvm/CodeGen/Passes.h"
#include "llvm/Target/TargetMachine.h"
#include "llvm/Target/TargetFrameInfo.h"
#include "llvm/Function.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include "llvm/Type.h"
#include "Support/LeakDetector.h"
#include "Support/GraphWriter.h"
#include <fstream>
#include <iostream>
#include <sstream>
using namespace llvm;
static AnnotationID MF_AID(
AnnotationManager::getID("CodeGen::MachineCodeForFunction"));
namespace {
struct Printer : public MachineFunctionPass {
std::ostream *OS;
const std::string Banner;
Printer (std::ostream *_OS, const std::string &_Banner) :
OS (_OS), Banner (_Banner) { }
const char *getPassName() const { return "MachineFunction Printer"; }
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesAll();
}
bool runOnMachineFunction(MachineFunction &MF) {
(*OS) << Banner;
MF.print (*OS);
return false;
}
};
}
/// Returns a newly-created MachineFunction Printer pass. The default output
/// stream is std::cerr; the default banner is empty.
///
FunctionPass *llvm::createMachineFunctionPrinterPass(std::ostream *OS,
const std::string &Banner) {
return new Printer(OS, Banner);
}
namespace {
struct Deleter : public MachineFunctionPass {
const char *getPassName() const { return "Machine Code Deleter"; }
bool runOnMachineFunction(MachineFunction &MF) {
// Delete the annotation from the function now.
MachineFunction::destruct(MF.getFunction());
return true;
}
};
}
/// MachineCodeDeletion Pass - This pass deletes all of the machine code for
/// the current function, which should happen after the function has been
/// emitted to a .s file or to memory.
FunctionPass *llvm::createMachineCodeDeleter() {
return new Deleter();
}
//===---------------------------------------------------------------------===//
// MachineFunction implementation
//===---------------------------------------------------------------------===//
MachineBasicBlock* ilist_traits<MachineBasicBlock>::createNode()
{
MachineBasicBlock* dummy = new MachineBasicBlock();
LeakDetector::removeGarbageObject(dummy);
return dummy;
}
void ilist_traits<MachineBasicBlock>::transferNodesFromList(
iplist<MachineBasicBlock, ilist_traits<MachineBasicBlock> >& toList,
ilist_iterator<MachineBasicBlock> first,
ilist_iterator<MachineBasicBlock> last)
{
if (Parent != toList.Parent)
for (; first != last; ++first)
first->Parent = toList.Parent;
}
MachineFunction::MachineFunction(const Function *F,
const TargetMachine &TM)
: Annotation(MF_AID), Fn(F), Target(TM) {
SSARegMapping = new SSARegMap();
MFInfo = new MachineFunctionInfo(*this);
FrameInfo = new MachineFrameInfo();
ConstantPool = new MachineConstantPool();
BasicBlocks.Parent = this;
}
MachineFunction::~MachineFunction() {
BasicBlocks.clear();
delete SSARegMapping;
delete MFInfo;
delete FrameInfo;
delete ConstantPool;
}
void MachineFunction::dump() const { print(std::cerr); }
void MachineFunction::print(std::ostream &OS) const {
OS << "# Machine code for " << Fn->getName () << "():\n";
// Print Frame Information
getFrameInfo()->print(*this, OS);
// Print Constant Pool
getConstantPool()->print(OS);
for (const_iterator BB = begin(); BB != end(); ++BB)
BB->print(OS);
OS << "\n# End machine code for " << Fn->getName () << "().\n\n";
}
/// CFGOnly flag - This is used to control whether or not the CFG graph printer
/// prints out the contents of basic blocks or not. This is acceptable because
/// this code is only really used for debugging purposes.
///
static bool CFGOnly = false;
namespace llvm {
template<>
struct DOTGraphTraits<const MachineFunction*> : public DefaultDOTGraphTraits {
static std::string getGraphName(const MachineFunction *F) {
return "CFG for '" + F->getFunction()->getName() + "' function";
}
static std::string getNodeLabel(const MachineBasicBlock *Node,
const MachineFunction *Graph) {
if (CFGOnly && Node->getBasicBlock() &&
!Node->getBasicBlock()->getName().empty())
return Node->getBasicBlock()->getName() + ":";
std::ostringstream Out;
if (CFGOnly) {
Out << Node->getNumber() << ':';
return Out.str();
}
Node->print(Out);
std::string OutStr = Out.str();
if (OutStr[0] == '\n') OutStr.erase(OutStr.begin());
// Process string output to make it nicer...
for (unsigned i = 0; i != OutStr.length(); ++i)
if (OutStr[i] == '\n') { // Left justify
OutStr[i] = '\\';
OutStr.insert(OutStr.begin()+i+1, 'l');
}
return OutStr;
}
};
}
void MachineFunction::viewCFG() const
{
std::string Filename = "/tmp/cfg." + getFunction()->getName() + ".dot";
std::cerr << "Writing '" << Filename << "'... ";
std::ofstream F(Filename.c_str());
if (!F) {
std::cerr << " error opening file for writing!\n";
return;
}
WriteGraph(F, this);
F.close();
std::cerr << "\n";
std::cerr << "Running 'dot' program... " << std::flush;
if (system(("dot -Tps -Nfontname=Courier -Gsize=7.5,10 " + Filename
+ " > /tmp/cfg.tempgraph.ps").c_str())) {
std::cerr << "Error running dot: 'dot' not in path?\n";
} else {
std::cerr << "\n";
system("gv /tmp/cfg.tempgraph.ps");
}
system(("rm " + Filename + " /tmp/cfg.tempgraph.ps").c_str());
}
void MachineFunction::viewCFGOnly() const
{
CFGOnly = true;
viewCFG();
CFGOnly = false;
}
// The next two methods are used to construct and to retrieve
// the MachineCodeForFunction object for the given function.
// construct() -- Allocates and initializes for a given function and target
// get() -- Returns a handle to the object.
// This should not be called before "construct()"
// for a given Function.
//
MachineFunction&
MachineFunction::construct(const Function *Fn, const TargetMachine &Tar)
{
assert(Fn->getAnnotation(MF_AID) == 0 &&
"Object already exists for this function!");
MachineFunction* mcInfo = new MachineFunction(Fn, Tar);
Fn->addAnnotation(mcInfo);
return *mcInfo;
}
void MachineFunction::destruct(const Function *Fn) {
bool Deleted = Fn->deleteAnnotation(MF_AID);
assert(Deleted && "Machine code did not exist for function!");
}
MachineFunction& MachineFunction::get(const Function *F)
{
MachineFunction *mc = (MachineFunction*)F->getAnnotation(MF_AID);
assert(mc && "Call construct() method first to allocate the object");
return *mc;
}
void MachineFunction::clearSSARegMap() {
delete SSARegMapping;
SSARegMapping = 0;
}
//===----------------------------------------------------------------------===//
// MachineFrameInfo implementation
//===----------------------------------------------------------------------===//
/// CreateStackObject - Create a stack object for a value of the specified type.
///
int MachineFrameInfo::CreateStackObject(const Type *Ty, const TargetData &TD) {
return CreateStackObject(TD.getTypeSize(Ty), TD.getTypeAlignment(Ty));
}
int MachineFrameInfo::CreateStackObject(const TargetRegisterClass *RC) {
return CreateStackObject(RC->getSize(), RC->getAlignment());
}
void MachineFrameInfo::print(const MachineFunction &MF, std::ostream &OS) const{
int ValOffset = MF.getTarget().getFrameInfo()->getOffsetOfLocalArea();
for (unsigned i = 0, e = Objects.size(); i != e; ++i) {
const StackObject &SO = Objects[i];
OS << " <fi #" << (int)(i-NumFixedObjects) << "> is ";
if (SO.Size == 0)
OS << "variable sized";
else
OS << SO.Size << " byte" << (SO.Size != 1 ? "s" : " ");
if (i < NumFixedObjects)
OS << " fixed";
if (i < NumFixedObjects || SO.SPOffset != -1) {
int Off = SO.SPOffset - ValOffset;
OS << " at location [SP";
if (Off > 0)
OS << "+" << Off;
else if (Off < 0)
OS << Off;
OS << "]";
}
OS << "\n";
}
if (HasVarSizedObjects)
OS << " Stack frame contains variable sized objects\n";
}
void MachineFrameInfo::dump(const MachineFunction &MF) const {
print(MF, std::cerr);
}
//===----------------------------------------------------------------------===//
// MachineConstantPool implementation
//===----------------------------------------------------------------------===//
void MachineConstantPool::print(std::ostream &OS) const {
for (unsigned i = 0, e = Constants.size(); i != e; ++i)
OS << " <cp #" << i << "> is" << *(Value*)Constants[i] << "\n";
}
void MachineConstantPool::dump() const { print(std::cerr); }
//===----------------------------------------------------------------------===//
// MachineFunctionInfo implementation
//===----------------------------------------------------------------------===//
static unsigned
ComputeMaxOptionalArgsSize(const TargetMachine& target, const Function *F,
unsigned &maxOptionalNumArgs)
{
const TargetFrameInfo &frameInfo = *target.getFrameInfo();
unsigned maxSize = 0;
for (Function::const_iterator BB = F->begin(), BBE = F->end(); BB !=BBE; ++BB)
for (BasicBlock::const_iterator I = BB->begin(), E = BB->end(); I != E; ++I)
if (const CallInst *callInst = dyn_cast<CallInst>(I))
{
unsigned numOperands = callInst->getNumOperands() - 1;
int numExtra = (int)numOperands-frameInfo.getNumFixedOutgoingArgs();
if (numExtra <= 0)
continue;
unsigned sizeForThisCall;
if (frameInfo.argsOnStackHaveFixedSize())
{
int argSize = frameInfo.getSizeOfEachArgOnStack();
sizeForThisCall = numExtra * (unsigned) argSize;
}
else
{
assert(0 && "UNTESTED CODE: Size per stack argument is not "
"fixed on this architecture: use actual arg sizes to "
"compute MaxOptionalArgsSize");
sizeForThisCall = 0;
for (unsigned i = 0; i < numOperands; ++i)
sizeForThisCall += target.getTargetData().getTypeSize(callInst->
getOperand(i)->getType());
}
if (maxSize < sizeForThisCall)
maxSize = sizeForThisCall;
if ((int)maxOptionalNumArgs < numExtra)
maxOptionalNumArgs = (unsigned) numExtra;
}
return maxSize;
}
// Align data larger than one L1 cache line on L1 cache line boundaries.
// Align all smaller data on the next higher 2^x boundary (4, 8, ...),
// but not higher than the alignment of the largest type we support
// (currently a double word). -- see class TargetData).
//
// This function is similar to the corresponding function in EmitAssembly.cpp
// but they are unrelated. This one does not align at more than a
// double-word boundary whereas that one might.
//
inline unsigned
SizeToAlignment(unsigned size, const TargetMachine& target)
{
const unsigned short cacheLineSize = 16;
if (size > (unsigned) cacheLineSize / 2)
return cacheLineSize;
else
for (unsigned sz=1; /*no condition*/; sz *= 2)
if (sz >= size || sz >= target.getTargetData().getDoubleAlignment())
return sz;
}
void MachineFunctionInfo::CalculateArgSize() {
maxOptionalArgsSize = ComputeMaxOptionalArgsSize(MF.getTarget(),
MF.getFunction(),
maxOptionalNumArgs);
staticStackSize = maxOptionalArgsSize
+ MF.getTarget().getFrameInfo()->getMinStackFrameSize();
}
int
MachineFunctionInfo::computeOffsetforLocalVar(const Value* val,
unsigned &getPaddedSize,
unsigned sizeToUse)
{
if (sizeToUse == 0) {
// All integer types smaller than ints promote to 4 byte integers.
if (val->getType()->isIntegral() && val->getType()->getPrimitiveSize() < 4)
sizeToUse = 4;
else
sizeToUse = MF.getTarget().getTargetData().getTypeSize(val->getType());
}
unsigned align = SizeToAlignment(sizeToUse, MF.getTarget());
bool growUp;
int firstOffset = MF.getTarget().getFrameInfo()->getFirstAutomaticVarOffset(MF,
growUp);
int offset = growUp? firstOffset + getAutomaticVarsSize()
: firstOffset - (getAutomaticVarsSize() + sizeToUse);
int aligned = MF.getTarget().getFrameInfo()->adjustAlignment(offset, growUp, align);
getPaddedSize = sizeToUse + abs(aligned - offset);
return aligned;
}
int MachineFunctionInfo::allocateLocalVar(const Value* val,
unsigned sizeToUse) {
assert(! automaticVarsAreaFrozen &&
"Size of auto vars area has been used to compute an offset so "
"no more automatic vars should be allocated!");
// Check if we've allocated a stack slot for this value already
//
hash_map<const Value*, int>::const_iterator pair = offsets.find(val);
if (pair != offsets.end())
return pair->second;
unsigned getPaddedSize;
unsigned offset = computeOffsetforLocalVar(val, getPaddedSize, sizeToUse);
offsets[val] = offset;
incrementAutomaticVarsSize(getPaddedSize);
return offset;
}
int
MachineFunctionInfo::allocateSpilledValue(const Type* type)
{
assert(! spillsAreaFrozen &&
"Size of reg spills area has been used to compute an offset so "
"no more register spill slots should be allocated!");
unsigned size = MF.getTarget().getTargetData().getTypeSize(type);
unsigned char align = MF.getTarget().getTargetData().getTypeAlignment(type);
bool growUp;
int firstOffset = MF.getTarget().getFrameInfo()->getRegSpillAreaOffset(MF, growUp);
int offset = growUp? firstOffset + getRegSpillsSize()
: firstOffset - (getRegSpillsSize() + size);
int aligned = MF.getTarget().getFrameInfo()->adjustAlignment(offset, growUp, align);
size += abs(aligned - offset); // include alignment padding in size
incrementRegSpillsSize(size); // update size of reg. spills area
return aligned;
}
int
MachineFunctionInfo::pushTempValue(unsigned size)
{
unsigned align = SizeToAlignment(size, MF.getTarget());
bool growUp;
int firstOffset = MF.getTarget().getFrameInfo()->getTmpAreaOffset(MF, growUp);
int offset = growUp? firstOffset + currentTmpValuesSize
: firstOffset - (currentTmpValuesSize + size);
int aligned = MF.getTarget().getFrameInfo()->adjustAlignment(offset, growUp,
align);
size += abs(aligned - offset); // include alignment padding in size
incrementTmpAreaSize(size); // update "current" size of tmp area
return aligned;
}
void MachineFunctionInfo::popAllTempValues() {
resetTmpAreaSize(); // clear tmp area to reuse
}
Property changes on: llvm/trunk/lib/CodeGen/MachineFunction.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.64
\ No newline at end of property
+1.65
\ No newline at end of property
Index: llvm/trunk/lib/CodeGen/MachineInstrAnnot.cpp
===================================================================
--- llvm/trunk/lib/CodeGen/MachineInstrAnnot.cpp (revision 15333)
+++ llvm/trunk/lib/CodeGen/MachineInstrAnnot.cpp (revision 15334)
@@ -1,78 +1,78 @@
//===-- MachineInstrAnnot.cpp ---------------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines Annotations used to pass information between code
// generation phases.
//
//===----------------------------------------------------------------------===//
#include "../Target/SparcV9/MachineInstrAnnot.h"
#include "llvm/CodeGen/InstrSelection.h"
#include "llvm/CodeGen/MachineCodeForInstruction.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include "llvm/Type.h"
using namespace llvm;
CallArgsDescriptor::CallArgsDescriptor(CallInst* _callInstr,
TmpInstruction* _retAddrReg,
bool _isVarArgs, bool _noPrototype)
: callInstr(_callInstr),
funcPtr(isa<Function>(_callInstr->getCalledValue())
? NULL : _callInstr->getCalledValue()),
retAddrReg(_retAddrReg),
isVarArgs(_isVarArgs),
noPrototype(_noPrototype)
{
unsigned int numArgs = callInstr->getNumOperands();
argInfoVec.reserve(numArgs);
assert(callInstr->getOperand(0) == callInstr->getCalledValue()
&& "Operand 0 is ignored in the loop below!");
for (unsigned int i=1; i < numArgs; ++i)
argInfoVec.push_back(CallArgInfo(callInstr->getOperand(i)));
// Enter this object in the MachineCodeForInstr object of the CallInst.
// This transfers ownership of this object.
MachineCodeForInstruction::get(callInstr).setCallArgsDescriptor(this);
}
CallInst*
CallArgsDescriptor::getReturnValue() const
{
return (callInstr->getType() == Type::VoidTy? NULL : callInstr);
}
// Mechanism to get the descriptor for a CALL MachineInstr.
// We get the LLVM CallInstr from the ret. addr. register argument
// of the CALL MachineInstr (which is explicit operand #3 for indirect
// calls or the last implicit operand for direct calls). We then get
// the CallArgsDescriptor from the MachineCodeForInstruction object for
// the CallInstr.
// This is roundabout but avoids adding a new map or annotation just
// to keep track of CallArgsDescriptors.
//
CallArgsDescriptor *CallArgsDescriptor::get(const MachineInstr* MI)
{
const TmpInstruction* retAddrReg =
cast<TmpInstruction>(isa<Function>(MI->getOperand(0).getVRegValue())
? MI->getImplicitRef(MI->getNumImplicitRefs()-1)
: MI->getOperand(2).getVRegValue());
assert(retAddrReg->getNumOperands() == 1 &&
isa<CallInst>(retAddrReg->getOperand(0)) &&
"Location of callInstr arg for CALL instr. changed? FIX THIS CODE!");
const CallInst* callInstr = cast<CallInst>(retAddrReg->getOperand(0));
CallArgsDescriptor* desc =
MachineCodeForInstruction::get(callInstr).getCallArgsDescriptor();
assert(desc->getCallInst()==callInstr && "Incorrect call args descriptor?");
return desc;
}
Property changes on: llvm/trunk/lib/CodeGen/MachineInstrAnnot.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.12
\ No newline at end of property
+1.13
\ No newline at end of property
Index: llvm/trunk/lib/Linker/LinkModules.cpp
===================================================================
--- llvm/trunk/lib/Linker/LinkModules.cpp (revision 15333)
+++ llvm/trunk/lib/Linker/LinkModules.cpp (revision 15334)
@@ -1,926 +1,926 @@
//===- Linker.cpp - Module Linker Implementation --------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the LLVM module linker.
//
// Specifically, this:
// * Merges global variables between the two modules
// * Uninit + Uninit = Init, Init + Uninit = Init, Init + Init = Error if !=
// * Merges functions between two modules
//
//===----------------------------------------------------------------------===//
#include "llvm/Support/Linker.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/SymbolTable.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include "llvm/Assembly/Writer.h"
#include <iostream>
using namespace llvm;
// Error - Simple wrapper function to conditionally assign to E and return true.
// This just makes error return conditions a little bit simpler...
//
static inline bool Error(std::string *E, const std::string &Message) {
if (E) *E = Message;
return true;
}
//
// Function: ResolveTypes()
//
// Description:
// Attempt to link the two specified types together.
//
// Inputs:
// DestTy - The type to which we wish to resolve.
// SrcTy - The original type which we want to resolve.
// Name - The name of the type.
//
// Outputs:
// DestST - The symbol table in which the new type should be placed.
//
// Return value:
// true - There is an error and the types cannot yet be linked.
// false - No errors.
//
static bool ResolveTypes(const Type *DestTy, const Type *SrcTy,
SymbolTable *DestST, const std::string &Name) {
if (DestTy == SrcTy) return false; // If already equal, noop
// Does the type already exist in the module?
if (DestTy && !isa<OpaqueType>(DestTy)) { // Yup, the type already exists...
if (const OpaqueType *OT = dyn_cast<OpaqueType>(SrcTy)) {
const_cast<OpaqueType*>(OT)->refineAbstractTypeTo(DestTy);
} else {
return true; // Cannot link types... neither is opaque and not-equal
}
} else { // Type not in dest module. Add it now.
if (DestTy) // Type _is_ in module, just opaque...
const_cast<OpaqueType*>(cast<OpaqueType>(DestTy))
->refineAbstractTypeTo(SrcTy);
else if (!Name.empty())
DestST->insert(Name, const_cast<Type*>(SrcTy));
}
return false;
}
static const FunctionType *getFT(const PATypeHolder &TH) {
return cast<FunctionType>(TH.get());
}
static const StructType *getST(const PATypeHolder &TH) {
return cast<StructType>(TH.get());
}
// RecursiveResolveTypes - This is just like ResolveTypes, except that it
// recurses down into derived types, merging the used types if the parent types
// are compatible.
//
static bool RecursiveResolveTypesI(const PATypeHolder &DestTy,
const PATypeHolder &SrcTy,
SymbolTable *DestST, const std::string &Name,
std::vector<std::pair<PATypeHolder, PATypeHolder> > &Pointers) {
const Type *SrcTyT = SrcTy.get();
const Type *DestTyT = DestTy.get();
if (DestTyT == SrcTyT) return false; // If already equal, noop
// If we found our opaque type, resolve it now!
if (isa<OpaqueType>(DestTyT) || isa<OpaqueType>(SrcTyT))
return ResolveTypes(DestTyT, SrcTyT, DestST, Name);
// Two types cannot be resolved together if they are of different primitive
// type. For example, we cannot resolve an int to a float.
if (DestTyT->getTypeID() != SrcTyT->getTypeID()) return true;
// Otherwise, resolve the used type used by this derived type...
switch (DestTyT->getTypeID()) {
case Type::FunctionTyID: {
if (cast<FunctionType>(DestTyT)->isVarArg() !=
cast<FunctionType>(SrcTyT)->isVarArg() ||
cast<FunctionType>(DestTyT)->getNumContainedTypes() !=
cast<FunctionType>(SrcTyT)->getNumContainedTypes())
return true;
for (unsigned i = 0, e = getFT(DestTy)->getNumContainedTypes(); i != e; ++i)
if (RecursiveResolveTypesI(getFT(DestTy)->getContainedType(i),
getFT(SrcTy)->getContainedType(i), DestST, "",
Pointers))
return true;
return false;
}
case Type::StructTyID: {
if (getST(DestTy)->getNumContainedTypes() !=
getST(SrcTy)->getNumContainedTypes()) return 1;
for (unsigned i = 0, e = getST(DestTy)->getNumContainedTypes(); i != e; ++i)
if (RecursiveResolveTypesI(getST(DestTy)->getContainedType(i),
getST(SrcTy)->getContainedType(i), DestST, "",
Pointers))
return true;
return false;
}
case Type::ArrayTyID: {
const ArrayType *DAT = cast<ArrayType>(DestTy.get());
const ArrayType *SAT = cast<ArrayType>(SrcTy.get());
if (DAT->getNumElements() != SAT->getNumElements()) return true;
return RecursiveResolveTypesI(DAT->getElementType(), SAT->getElementType(),
DestST, "", Pointers);
}
case Type::PointerTyID: {
// If this is a pointer type, check to see if we have already seen it. If
// so, we are in a recursive branch. Cut off the search now. We cannot use
// an associative container for this search, because the type pointers (keys
// in the container) change whenever types get resolved...
//
for (unsigned i = 0, e = Pointers.size(); i != e; ++i)
if (Pointers[i].first == DestTy)
return Pointers[i].second != SrcTy;
// Otherwise, add the current pointers to the vector to stop recursion on
// this pair.
Pointers.push_back(std::make_pair(DestTyT, SrcTyT));
bool Result =
RecursiveResolveTypesI(cast<PointerType>(DestTy.get())->getElementType(),
cast<PointerType>(SrcTy.get())->getElementType(),
DestST, "", Pointers);
Pointers.pop_back();
return Result;
}
default: assert(0 && "Unexpected type!"); return true;
}
}
static bool RecursiveResolveTypes(const PATypeHolder &DestTy,
const PATypeHolder &SrcTy,
SymbolTable *DestST, const std::string &Name){
std::vector<std::pair<PATypeHolder, PATypeHolder> > PointerTypes;
return RecursiveResolveTypesI(DestTy, SrcTy, DestST, Name, PointerTypes);
}
// LinkTypes - Go through the symbol table of the Src module and see if any
// types are named in the src module that are not named in the Dst module.
// Make sure there are no type name conflicts.
//
static bool LinkTypes(Module *Dest, const Module *Src, std::string *Err) {
SymbolTable *DestST = &Dest->getSymbolTable();
const SymbolTable *SrcST = &Src->getSymbolTable();
// Look for a type plane for Type's...
SymbolTable::type_const_iterator TI = SrcST->type_begin();
SymbolTable::type_const_iterator TE = SrcST->type_end();
if (TI == TE) return false; // No named types, do nothing.
// Some types cannot be resolved immediately because they depend on other
// types being resolved to each other first. This contains a list of types we
// are waiting to recheck.
std::vector<std::string> DelayedTypesToResolve;
for ( ; TI != TE; ++TI ) {
const std::string &Name = TI->first;
const Type *RHS = TI->second;
// Check to see if this type name is already in the dest module...
Type *Entry = DestST->lookupType(Name);
if (ResolveTypes(Entry, RHS, DestST, Name)) {
// They look different, save the types 'till later to resolve.
DelayedTypesToResolve.push_back(Name);
}
}
// Iteratively resolve types while we can...
while (!DelayedTypesToResolve.empty()) {
// Loop over all of the types, attempting to resolve them if possible...
unsigned OldSize = DelayedTypesToResolve.size();
// Try direct resolution by name...
for (unsigned i = 0; i != DelayedTypesToResolve.size(); ++i) {
const std::string &Name = DelayedTypesToResolve[i];
Type *T1 = SrcST->lookupType(Name);
Type *T2 = DestST->lookupType(Name);
if (!ResolveTypes(T2, T1, DestST, Name)) {
// We are making progress!
DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i);
--i;
}
}
// Did we not eliminate any types?
if (DelayedTypesToResolve.size() == OldSize) {
// Attempt to resolve subelements of types. This allows us to merge these
// two types: { int* } and { opaque* }
for (unsigned i = 0, e = DelayedTypesToResolve.size(); i != e; ++i) {
const std::string &Name = DelayedTypesToResolve[i];
PATypeHolder T1(SrcST->lookupType(Name));
PATypeHolder T2(DestST->lookupType(Name));
if (!RecursiveResolveTypes(T2, T1, DestST, Name)) {
// We are making progress!
DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i);
// Go back to the main loop, perhaps we can resolve directly by name
// now...
break;
}
}
// If we STILL cannot resolve the types, then there is something wrong.
// Report the warning and delete one of the names.
if (DelayedTypesToResolve.size() == OldSize) {
const std::string &Name = DelayedTypesToResolve.back();
const Type *T1 = SrcST->lookupType(Name);
const Type *T2 = DestST->lookupType(Name);
std::cerr << "WARNING: Type conflict between types named '" << Name
<< "'.\n Src='";
WriteTypeSymbolic(std::cerr, T1, Src);
std::cerr << "'.\n Dest='";
WriteTypeSymbolic(std::cerr, T2, Dest);
std::cerr << "'\n";
// Remove the symbol name from the destination.
DelayedTypesToResolve.pop_back();
}
}
}
return false;
}
static void PrintMap(const std::map<const Value*, Value*> &M) {
for (std::map<const Value*, Value*>::const_iterator I = M.begin(), E =M.end();
I != E; ++I) {
std::cerr << " Fr: " << (void*)I->first << " ";
I->first->dump();
std::cerr << " To: " << (void*)I->second << " ";
I->second->dump();
std::cerr << "\n";
}
}
// RemapOperand - Use LocalMap and GlobalMap to convert references from one
// module to another. This is somewhat sophisticated in that it can
// automatically handle constant references correctly as well...
//
static Value *RemapOperand(const Value *In,
std::map<const Value*, Value*> &LocalMap,
std::map<const Value*, Value*> *GlobalMap) {
std::map<const Value*,Value*>::const_iterator I = LocalMap.find(In);
if (I != LocalMap.end()) return I->second;
if (GlobalMap) {
I = GlobalMap->find(In);
if (I != GlobalMap->end()) return I->second;
}
// Check to see if it's a constant that we are interesting in transforming...
if (const Constant *CPV = dyn_cast<Constant>(In)) {
if ((!isa<DerivedType>(CPV->getType()) && !isa<ConstantExpr>(CPV)) ||
isa<ConstantAggregateZero>(CPV))
return const_cast<Constant*>(CPV); // Simple constants stay identical...
Constant *Result = 0;
if (const ConstantArray *CPA = dyn_cast<ConstantArray>(CPV)) {
const std::vector<Use> &Ops = CPA->getValues();
std::vector<Constant*> Operands(Ops.size());
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
Operands[i] =
cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap));
Result = ConstantArray::get(cast<ArrayType>(CPA->getType()), Operands);
} else if (const ConstantStruct *CPS = dyn_cast<ConstantStruct>(CPV)) {
const std::vector<Use> &Ops = CPS->getValues();
std::vector<Constant*> Operands(Ops.size());
for (unsigned i = 0; i < Ops.size(); ++i)
Operands[i] =
cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap));
Result = ConstantStruct::get(cast<StructType>(CPS->getType()), Operands);
} else if (isa<ConstantPointerNull>(CPV)) {
Result = const_cast<Constant*>(CPV);
} else if (isa<GlobalValue>(CPV)) {
Result = cast<Constant>(RemapOperand(CPV, LocalMap, GlobalMap));
} else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) {
if (CE->getOpcode() == Instruction::GetElementPtr) {
Value *Ptr = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap);
std::vector<Constant*> Indices;
Indices.reserve(CE->getNumOperands()-1);
for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
Indices.push_back(cast<Constant>(RemapOperand(CE->getOperand(i),
LocalMap, GlobalMap)));
Result = ConstantExpr::getGetElementPtr(cast<Constant>(Ptr), Indices);
} else if (CE->getNumOperands() == 1) {
// Cast instruction
assert(CE->getOpcode() == Instruction::Cast);
Value *V = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap);
Result = ConstantExpr::getCast(cast<Constant>(V), CE->getType());
} else if (CE->getNumOperands() == 3) {
// Select instruction
assert(CE->getOpcode() == Instruction::Select);
Value *V1 = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap);
Value *V2 = RemapOperand(CE->getOperand(1), LocalMap, GlobalMap);
Value *V3 = RemapOperand(CE->getOperand(2), LocalMap, GlobalMap);
Result = ConstantExpr::getSelect(cast<Constant>(V1), cast<Constant>(V2),
cast<Constant>(V3));
} else if (CE->getNumOperands() == 2) {
// Binary operator...
Value *V1 = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap);
Value *V2 = RemapOperand(CE->getOperand(1), LocalMap, GlobalMap);
Result = ConstantExpr::get(CE->getOpcode(), cast<Constant>(V1),
cast<Constant>(V2));
} else {
assert(0 && "Unknown constant expr type!");
}
} else {
assert(0 && "Unknown type of derived type constant value!");
}
// Cache the mapping in our local map structure...
if (GlobalMap)
GlobalMap->insert(std::make_pair(In, Result));
else
LocalMap.insert(std::make_pair(In, Result));
return Result;
}
std::cerr << "XXX LocalMap: \n";
PrintMap(LocalMap);
if (GlobalMap) {
std::cerr << "XXX GlobalMap: \n";
PrintMap(*GlobalMap);
}
std::cerr << "Couldn't remap value: " << (void*)In << " " << *In << "\n";
assert(0 && "Couldn't remap value!");
return 0;
}
/// FindGlobalNamed - Look in the specified symbol table for a global with the
/// specified name and type. If an exactly matching global does not exist, see
/// if there is a global which is "type compatible" with the specified
/// name/type. This allows us to resolve things like '%x = global int*' with
/// '%x = global opaque*'.
///
static GlobalValue *FindGlobalNamed(const std::string &Name, const Type *Ty,
SymbolTable *ST) {
// See if an exact match exists in the symbol table...
if (Value *V = ST->lookup(Ty, Name)) return cast<GlobalValue>(V);
// It doesn't exist exactly, scan through all of the type planes in the symbol
// table, checking each of them for a type-compatible version.
//
for (SymbolTable::plane_iterator PI = ST->plane_begin(), PE = ST->plane_end();
PI != PE; ++PI) {
SymbolTable::ValueMap &VM = PI->second;
// Does this type plane contain an entry with the specified name?
SymbolTable::value_iterator VI = VM.find(Name);
if (VI != VM.end()) {
//
// Ensure that this type if placed correctly into the symbol table.
//
assert(VI->second->getType() == PI->first && "Type conflict!");
//
// Save a reference to the new type. Resolving the type can modify the
// symbol table, invalidating the TI variable.
//
Value *ValPtr = VI->second;
//
// Determine whether we can fold the two types together, resolving them.
// If so, we can use this value.
//
if (!RecursiveResolveTypes(Ty, PI->first, ST, ""))
return cast<GlobalValue>(ValPtr);
}
}
return 0; // Otherwise, nothing could be found.
}
// LinkGlobals - Loop through the global variables in the src module and merge
// them into the dest module.
//
static bool LinkGlobals(Module *Dest, const Module *Src,
std::map<const Value*, Value*> &ValueMap,
std::multimap<std::string, GlobalVariable *> &AppendingVars,
std::string *Err) {
// We will need a module level symbol table if the src module has a module
// level symbol table...
SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable();
// Loop over all of the globals in the src module, mapping them over as we go
//
for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){
const GlobalVariable *SGV = I;
GlobalVariable *DGV = 0;
if (SGV->hasName()) {
// A same named thing is a global variable, because the only two things
// that may be in a module level symbol table are Global Vars and
// Functions, and they both have distinct, nonoverlapping, possible types.
//
DGV = cast_or_null<GlobalVariable>(FindGlobalNamed(SGV->getName(),
SGV->getType(), ST));
}
assert(SGV->hasInitializer() || SGV->hasExternalLinkage() &&
"Global must either be external or have an initializer!");
bool SGExtern = SGV->isExternal();
bool DGExtern = DGV ? DGV->isExternal() : false;
if (!DGV || DGV->hasInternalLinkage() || SGV->hasInternalLinkage()) {
// No linking to be performed, simply create an identical version of the
// symbol over in the dest module... the initializer will be filled in
// later by LinkGlobalInits...
//
GlobalVariable *NewDGV =
new GlobalVariable(SGV->getType()->getElementType(),
SGV->isConstant(), SGV->getLinkage(), /*init*/0,
SGV->getName(), Dest);
// If the LLVM runtime renamed the global, but it is an externally visible
// symbol, DGV must be an existing global with internal linkage. Rename
// it.
if (NewDGV->getName() != SGV->getName() && !NewDGV->hasInternalLinkage()){
assert(DGV && DGV->getName() == SGV->getName() &&
DGV->hasInternalLinkage());
DGV->setName("");
NewDGV->setName(SGV->getName()); // Force the name back
DGV->setName(SGV->getName()); // This will cause a renaming
assert(NewDGV->getName() == SGV->getName() &&
DGV->getName() != SGV->getName());
}
// Make sure to remember this mapping...
ValueMap.insert(std::make_pair(SGV, NewDGV));
if (SGV->hasAppendingLinkage())
// Keep track that this is an appending variable...
AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV));
} else if (SGV->isExternal()) {
// If SGV is external or if both SGV & DGV are external.. Just link the
// external globals, we aren't adding anything.
ValueMap.insert(std::make_pair(SGV, DGV));
} else if (DGV->isExternal()) { // If DGV is external but SGV is not...
ValueMap.insert(std::make_pair(SGV, DGV));
DGV->setLinkage(SGV->getLinkage()); // Inherit linkage!
} else if (SGV->hasWeakLinkage() || SGV->hasLinkOnceLinkage()) {
// At this point we know that DGV has LinkOnce, Appending, Weak, or
// External linkage. If DGV is Appending, this is an error.
if (DGV->hasAppendingLinkage())
return Error(Err, "Linking globals named '" + SGV->getName() +
" ' with 'weak' and 'appending' linkage is not allowed!");
if (SGV->isConstant() != DGV->isConstant())
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() + " %" + SGV->getName() +
"' - Global variables differ in const'ness");
// Otherwise, just perform the link.
ValueMap.insert(std::make_pair(SGV, DGV));
// Linkonce+Weak = Weak
if (DGV->hasLinkOnceLinkage() && SGV->hasWeakLinkage())
DGV->setLinkage(SGV->getLinkage());
} else if (DGV->hasWeakLinkage() || DGV->hasLinkOnceLinkage()) {
// At this point we know that SGV has LinkOnce, Appending, or External
// linkage. If SGV is Appending, this is an error.
if (SGV->hasAppendingLinkage())
return Error(Err, "Linking globals named '" + SGV->getName() +
" ' with 'weak' and 'appending' linkage is not allowed!");
if (SGV->isConstant() != DGV->isConstant())
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() + " %" + SGV->getName() +
"' - Global variables differ in const'ness");
if (!SGV->hasLinkOnceLinkage())
DGV->setLinkage(SGV->getLinkage()); // Inherit linkage!
ValueMap.insert(std::make_pair(SGV, DGV));
} else if (SGV->getLinkage() != DGV->getLinkage()) {
return Error(Err, "Global variables named '" + SGV->getName() +
"' have different linkage specifiers!");
} else if (SGV->hasExternalLinkage()) {
// Allow linking two exactly identical external global variables...
if (SGV->isConstant() != DGV->isConstant())
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() + " %" + SGV->getName() +
"' - Global variables differ in const'ness");
if (SGV->getInitializer() != DGV->getInitializer())
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() + " %" + SGV->getName() +
"' - External linkage globals have different initializers");
ValueMap.insert(std::make_pair(SGV, DGV));
} else if (SGV->hasAppendingLinkage()) {
// No linking is performed yet. Just insert a new copy of the global, and
// keep track of the fact that it is an appending variable in the
// AppendingVars map. The name is cleared out so that no linkage is
// performed.
GlobalVariable *NewDGV =
new GlobalVariable(SGV->getType()->getElementType(),
SGV->isConstant(), SGV->getLinkage(), /*init*/0,
"", Dest);
// Make sure to remember this mapping...
ValueMap.insert(std::make_pair(SGV, NewDGV));
// Keep track that this is an appending variable...
AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV));
} else {
assert(0 && "Unknown linkage!");
}
}
return false;
}
// LinkGlobalInits - Update the initializers in the Dest module now that all
// globals that may be referenced are in Dest.
//
static bool LinkGlobalInits(Module *Dest, const Module *Src,
std::map<const Value*, Value*> &ValueMap,
std::string *Err) {
// Loop over all of the globals in the src module, mapping them over as we go
//
for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){
const GlobalVariable *SGV = I;
if (SGV->hasInitializer()) { // Only process initialized GV's
// Figure out what the initializer looks like in the dest module...
Constant *SInit =
cast<Constant>(RemapOperand(SGV->getInitializer(), ValueMap, 0));
GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[SGV]);
if (DGV->hasInitializer()) {
if (SGV->hasExternalLinkage()) {
if (DGV->getInitializer() != SInit)
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() +"':%"+SGV->getName()+
" - Global variables have different initializers");
} else if (DGV->hasLinkOnceLinkage() || DGV->hasWeakLinkage()) {
// Nothing is required, mapped values will take the new global
// automatically.
} else if (SGV->hasLinkOnceLinkage() || SGV->hasWeakLinkage()) {
// Nothing is required, mapped values will take the new global
// automatically.
} else if (DGV->hasAppendingLinkage()) {
assert(0 && "Appending linkage unimplemented!");
} else {
assert(0 && "Unknown linkage!");
}
} else {
// Copy the initializer over now...
DGV->setInitializer(SInit);
}
}
}
return false;
}
// LinkFunctionProtos - Link the functions together between the two modules,
// without doing function bodies... this just adds external function prototypes
// to the Dest function...
//
static bool LinkFunctionProtos(Module *Dest, const Module *Src,
std::map<const Value*, Value*> &ValueMap,
std::string *Err) {
SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable();
// Loop over all of the functions in the src module, mapping them over as we
// go
//
for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
const Function *SF = I; // SrcFunction
Function *DF = 0;
if (SF->hasName())
// The same named thing is a Function, because the only two things
// that may be in a module level symbol table are Global Vars and
// Functions, and they both have distinct, nonoverlapping, possible types.
//
DF = cast_or_null<Function>(FindGlobalNamed(SF->getName(), SF->getType(),
ST));
if (!DF || SF->hasInternalLinkage() || DF->hasInternalLinkage()) {
// Function does not already exist, simply insert an function signature
// identical to SF into the dest module...
Function *NewDF = new Function(SF->getFunctionType(), SF->getLinkage(),
SF->getName(), Dest);
// If the LLVM runtime renamed the function, but it is an externally
// visible symbol, DF must be an existing function with internal linkage.
// Rename it.
if (NewDF->getName() != SF->getName() && !NewDF->hasInternalLinkage()) {
assert(DF && DF->getName() == SF->getName() &&DF->hasInternalLinkage());
DF->setName("");
NewDF->setName(SF->getName()); // Force the name back
DF->setName(SF->getName()); // This will cause a renaming
assert(NewDF->getName() == SF->getName() &&
DF->getName() != SF->getName());
}
// ... and remember this mapping...
ValueMap.insert(std::make_pair(SF, NewDF));
} else if (SF->isExternal()) {
// If SF is external or if both SF & DF are external.. Just link the
// external functions, we aren't adding anything.
ValueMap.insert(std::make_pair(SF, DF));
} else if (DF->isExternal()) { // If DF is external but SF is not...
// Link the external functions, update linkage qualifiers
ValueMap.insert(std::make_pair(SF, DF));
DF->setLinkage(SF->getLinkage());
} else if (SF->hasWeakLinkage() || SF->hasLinkOnceLinkage()) {
// At this point we know that DF has LinkOnce, Weak, or External linkage.
ValueMap.insert(std::make_pair(SF, DF));
// Linkonce+Weak = Weak
if (DF->hasLinkOnceLinkage() && SF->hasWeakLinkage())
DF->setLinkage(SF->getLinkage());
} else if (DF->hasWeakLinkage() || DF->hasLinkOnceLinkage()) {
// At this point we know that SF has LinkOnce or External linkage.
ValueMap.insert(std::make_pair(SF, DF));
if (!SF->hasLinkOnceLinkage()) // Don't inherit linkonce linkage
DF->setLinkage(SF->getLinkage());
} else if (SF->getLinkage() != DF->getLinkage()) {
return Error(Err, "Functions named '" + SF->getName() +
"' have different linkage specifiers!");
} else if (SF->hasExternalLinkage()) {
// The function is defined in both modules!!
return Error(Err, "Function '" +
SF->getFunctionType()->getDescription() + "':\"" +
SF->getName() + "\" - Function is already defined!");
} else {
assert(0 && "Unknown linkage configuration found!");
}
}
return false;
}
// LinkFunctionBody - Copy the source function over into the dest function and
// fix up references to values. At this point we know that Dest is an external
// function, and that Src is not.
//
static bool LinkFunctionBody(Function *Dest, const Function *Src,
std::map<const Value*, Value*> &GlobalMap,
std::string *Err) {
assert(Src && Dest && Dest->isExternal() && !Src->isExternal());
std::map<const Value*, Value*> LocalMap; // Map for function local values
// Go through and convert function arguments over...
Function::aiterator DI = Dest->abegin();
for (Function::const_aiterator I = Src->abegin(), E = Src->aend();
I != E; ++I, ++DI) {
DI->setName(I->getName()); // Copy the name information over...
// Add a mapping to our local map
LocalMap.insert(std::make_pair(I, DI));
}
// Loop over all of the basic blocks, copying the instructions over...
//
for (Function::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
// Create new basic block and add to mapping and the Dest function...
BasicBlock *DBB = new BasicBlock(I->getName(), Dest);
LocalMap.insert(std::make_pair(I, DBB));
// Loop over all of the instructions in the src basic block, copying them
// over. Note that this is broken in a strict sense because the cloned
// instructions will still be referencing values in the Src module, not
// the remapped values. In our case, however, we will not get caught and
// so we can delay patching the values up until later...
//
for (BasicBlock::const_iterator II = I->begin(), IE = I->end();
II != IE; ++II) {
Instruction *DI = II->clone();
DI->setName(II->getName());
DBB->getInstList().push_back(DI);
LocalMap.insert(std::make_pair(II, DI));
}
}
// At this point, all of the instructions and values of the function are now
// copied over. The only problem is that they are still referencing values in
// the Source function as operands. Loop through all of the operands of the
// functions and patch them up to point to the local versions...
//
for (Function::iterator BB = Dest->begin(), BE = Dest->end(); BB != BE; ++BB)
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end();
OI != OE; ++OI)
*OI = RemapOperand(*OI, LocalMap, &GlobalMap);
return false;
}
// LinkFunctionBodies - Link in the function bodies that are defined in the
// source module into the DestModule. This consists basically of copying the
// function over and fixing up references to values.
//
static bool LinkFunctionBodies(Module *Dest, const Module *Src,
std::map<const Value*, Value*> &ValueMap,
std::string *Err) {
// Loop over all of the functions in the src module, mapping them over as we
// go
//
for (Module::const_iterator SF = Src->begin(), E = Src->end(); SF != E; ++SF){
if (!SF->isExternal()) { // No body if function is external
Function *DF = cast<Function>(ValueMap[SF]); // Destination function
// DF not external SF external?
if (DF->isExternal()) {
// Only provide the function body if there isn't one already.
if (LinkFunctionBody(DF, SF, ValueMap, Err))
return true;
}
}
}
return false;
}
// LinkAppendingVars - If there were any appending global variables, link them
// together now. Return true on error.
//
static bool LinkAppendingVars(Module *M,
std::multimap<std::string, GlobalVariable *> &AppendingVars,
std::string *ErrorMsg) {
if (AppendingVars.empty()) return false; // Nothing to do.
// Loop over the multimap of appending vars, processing any variables with the
// same name, forming a new appending global variable with both of the
// initializers merged together, then rewrite references to the old variables
// and delete them.
//
std::vector<Constant*> Inits;
while (AppendingVars.size() > 1) {
// Get the first two elements in the map...
std::multimap<std::string,
GlobalVariable*>::iterator Second = AppendingVars.begin(), First=Second++;
// If the first two elements are for different names, there is no pair...
// Otherwise there is a pair, so link them together...
if (First->first == Second->first) {
GlobalVariable *G1 = First->second, *G2 = Second->second;
const ArrayType *T1 = cast<ArrayType>(G1->getType()->getElementType());
const ArrayType *T2 = cast<ArrayType>(G2->getType()->getElementType());
// Check to see that they two arrays agree on type...
if (T1->getElementType() != T2->getElementType())
return Error(ErrorMsg,
"Appending variables with different element types need to be linked!");
if (G1->isConstant() != G2->isConstant())
return Error(ErrorMsg,
"Appending variables linked with different const'ness!");
unsigned NewSize = T1->getNumElements() + T2->getNumElements();
ArrayType *NewType = ArrayType::get(T1->getElementType(), NewSize);
// Create the new global variable...
GlobalVariable *NG =
new GlobalVariable(NewType, G1->isConstant(), G1->getLinkage(),
/*init*/0, First->first, M);
// Merge the initializer...
Inits.reserve(NewSize);
if (ConstantArray *I = dyn_cast<ConstantArray>(G1->getInitializer())) {
for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i)
Inits.push_back(cast<Constant>(I->getValues()[i]));
} else {
assert(isa<ConstantAggregateZero>(G1->getInitializer()));
Constant *CV = Constant::getNullValue(T1->getElementType());
for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i)
Inits.push_back(CV);
}
if (ConstantArray *I = dyn_cast<ConstantArray>(G2->getInitializer())) {
for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i)
Inits.push_back(cast<Constant>(I->getValues()[i]));
} else {
assert(isa<ConstantAggregateZero>(G2->getInitializer()));
Constant *CV = Constant::getNullValue(T2->getElementType());
for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i)
Inits.push_back(CV);
}
NG->setInitializer(ConstantArray::get(NewType, Inits));
Inits.clear();
// Replace any uses of the two global variables with uses of the new
// global...
// FIXME: This should rewrite simple/straight-forward uses such as
// getelementptr instructions to not use the Cast!
G1->replaceAllUsesWith(ConstantExpr::getCast(NG, G1->getType()));
G2->replaceAllUsesWith(ConstantExpr::getCast(NG, G2->getType()));
// Remove the two globals from the module now...
M->getGlobalList().erase(G1);
M->getGlobalList().erase(G2);
// Put the new global into the AppendingVars map so that we can handle
// linking of more than two vars...
Second->second = NG;
}
AppendingVars.erase(First);
}
return false;
}
// LinkModules - This function links two modules together, with the resulting
// left module modified to be the composite of the two input modules. If an
// error occurs, true is returned and ErrorMsg (if not null) is set to indicate
// the problem. Upon failure, the Dest module could be in a modified state, and
// shouldn't be relied on to be consistent.
//
bool llvm::LinkModules(Module *Dest, const Module *Src, std::string *ErrorMsg) {
if (Dest->getEndianness() == Module::AnyEndianness)
Dest->setEndianness(Src->getEndianness());
if (Dest->getPointerSize() == Module::AnyPointerSize)
Dest->setPointerSize(Src->getPointerSize());
if (Src->getEndianness() != Module::AnyEndianness &&
Dest->getEndianness() != Src->getEndianness())
std::cerr << "WARNING: Linking two modules of different endianness!\n";
if (Src->getPointerSize() != Module::AnyPointerSize &&
Dest->getPointerSize() != Src->getPointerSize())
std::cerr << "WARNING: Linking two modules of different pointer size!\n";
// LinkTypes - Go through the symbol table of the Src module and see if any
// types are named in the src module that are not named in the Dst module.
// Make sure there are no type name conflicts.
//
if (LinkTypes(Dest, Src, ErrorMsg)) return true;
// ValueMap - Mapping of values from what they used to be in Src, to what they
// are now in Dest.
//
std::map<const Value*, Value*> ValueMap;
// AppendingVars - Keep track of global variables in the destination module
// with appending linkage. After the module is linked together, they are
// appended and the module is rewritten.
//
std::multimap<std::string, GlobalVariable *> AppendingVars;
// Add all of the appending globals already in the Dest module to
// AppendingVars.
for (Module::giterator I = Dest->gbegin(), E = Dest->gend(); I != E; ++I)
if (I->hasAppendingLinkage())
AppendingVars.insert(std::make_pair(I->getName(), I));
// Insert all of the globals in src into the Dest module... without linking
// initializers (which could refer to functions not yet mapped over).
//
if (LinkGlobals(Dest, Src, ValueMap, AppendingVars, ErrorMsg)) return true;
// Link the functions together between the two modules, without doing function
// bodies... this just adds external function prototypes to the Dest
// function... We do this so that when we begin processing function bodies,
// all of the global values that may be referenced are available in our
// ValueMap.
//
if (LinkFunctionProtos(Dest, Src, ValueMap, ErrorMsg)) return true;
// Update the initializers in the Dest module now that all globals that may
// be referenced are in Dest.
//
if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true;
// Link in the function bodies that are defined in the source module into the
// DestModule. This consists basically of copying the function over and
// fixing up references to values.
//
if (LinkFunctionBodies(Dest, Src, ValueMap, ErrorMsg)) return true;
// If there were any appending global variables, link them together now.
//
if (LinkAppendingVars(Dest, AppendingVars, ErrorMsg)) return true;
return false;
}
// vim: sw=2
Property changes on: llvm/trunk/lib/Linker/LinkModules.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.74
\ No newline at end of property
+1.75
\ No newline at end of property
Index: llvm/trunk/lib/VMCore/Constants.cpp
===================================================================
--- llvm/trunk/lib/VMCore/Constants.cpp (revision 15333)
+++ llvm/trunk/lib/VMCore/Constants.cpp (revision 15334)
@@ -1,1172 +1,1172 @@
//===-- Constants.cpp - Implement Constant nodes --------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the Constant* classes...
//
//===----------------------------------------------------------------------===//
#include "llvm/Constants.h"
#include "ConstantFolding.h"
#include "llvm/DerivedTypes.h"
#include "llvm/GlobalValue.h"
-#include "llvm/iMemory.h"
+#include "llvm/Instructions.h"
#include "llvm/SymbolTable.h"
#include "llvm/Module.h"
#include "Support/StringExtras.h"
#include <algorithm>
#include <iostream>
using namespace llvm;
ConstantBool *ConstantBool::True = new ConstantBool(true);
ConstantBool *ConstantBool::False = new ConstantBool(false);
//===----------------------------------------------------------------------===//
// Constant Class
//===----------------------------------------------------------------------===//
// Specialize setName to take care of symbol table majik
void Constant::setName(const std::string &Name, SymbolTable *ST) {
assert(ST && "Type::setName - Must provide symbol table argument!");
if (Name.size()) ST->insert(Name, this);
}
void Constant::destroyConstantImpl() {
// When a Constant is destroyed, there may be lingering
// references to the constant by other constants in the constant pool. These
// constants are implicitly dependent on the module that is being deleted,
// but they don't know that. Because we only find out when the CPV is
// deleted, we must now notify all of our users (that should only be
// Constants) that they are, in fact, invalid now and should be deleted.
//
while (!use_empty()) {
Value *V = use_back();
#ifndef NDEBUG // Only in -g mode...
if (!isa<Constant>(V))
std::cerr << "While deleting: " << *this
<< "\n\nUse still stuck around after Def is destroyed: "
<< *V << "\n\n";
#endif
assert(isa<Constant>(V) && "References remain to Constant being destroyed");
Constant *CV = cast<Constant>(V);
CV->destroyConstant();
// The constant should remove itself from our use list...
assert((use_empty() || use_back() != V) && "Constant not removed!");
}
// Value has no outstanding references it is safe to delete it now...
delete this;
}
// Static constructor to create a '0' constant of arbitrary type...
Constant *Constant::getNullValue(const Type *Ty) {
switch (Ty->getTypeID()) {
case Type::BoolTyID: {
static Constant *NullBool = ConstantBool::get(false);
return NullBool;
}
case Type::SByteTyID: {
static Constant *NullSByte = ConstantSInt::get(Type::SByteTy, 0);
return NullSByte;
}
case Type::UByteTyID: {
static Constant *NullUByte = ConstantUInt::get(Type::UByteTy, 0);
return NullUByte;
}
case Type::ShortTyID: {
static Constant *NullShort = ConstantSInt::get(Type::ShortTy, 0);
return NullShort;
}
case Type::UShortTyID: {
static Constant *NullUShort = ConstantUInt::get(Type::UShortTy, 0);
return NullUShort;
}
case Type::IntTyID: {
static Constant *NullInt = ConstantSInt::get(Type::IntTy, 0);
return NullInt;
}
case Type::UIntTyID: {
static Constant *NullUInt = ConstantUInt::get(Type::UIntTy, 0);
return NullUInt;
}
case Type::LongTyID: {
static Constant *NullLong = ConstantSInt::get(Type::LongTy, 0);
return NullLong;
}
case Type::ULongTyID: {
static Constant *NullULong = ConstantUInt::get(Type::ULongTy, 0);
return NullULong;
}
case Type::FloatTyID: {
static Constant *NullFloat = ConstantFP::get(Type::FloatTy, 0);
return NullFloat;
}
case Type::DoubleTyID: {
static Constant *NullDouble = ConstantFP::get(Type::DoubleTy, 0);
return NullDouble;
}
case Type::PointerTyID:
return ConstantPointerNull::get(cast<PointerType>(Ty));
case Type::StructTyID:
case Type::ArrayTyID:
return ConstantAggregateZero::get(Ty);
default:
// Function, Label, or Opaque type?
assert(!"Cannot create a null constant of that type!");
return 0;
}
}
// Static constructor to create the maximum constant of an integral type...
ConstantIntegral *ConstantIntegral::getMaxValue(const Type *Ty) {
switch (Ty->getTypeID()) {
case Type::BoolTyID: return ConstantBool::True;
case Type::SByteTyID:
case Type::ShortTyID:
case Type::IntTyID:
case Type::LongTyID: {
// Calculate 011111111111111...
unsigned TypeBits = Ty->getPrimitiveSize()*8;
int64_t Val = INT64_MAX; // All ones
Val >>= 64-TypeBits; // Shift out unwanted 1 bits...
return ConstantSInt::get(Ty, Val);
}
case Type::UByteTyID:
case Type::UShortTyID:
case Type::UIntTyID:
case Type::ULongTyID: return getAllOnesValue(Ty);
default: return 0;
}
}
// Static constructor to create the minimum constant for an integral type...
ConstantIntegral *ConstantIntegral::getMinValue(const Type *Ty) {
switch (Ty->getTypeID()) {
case Type::BoolTyID: return ConstantBool::False;
case Type::SByteTyID:
case Type::ShortTyID:
case Type::IntTyID:
case Type::LongTyID: {
// Calculate 1111111111000000000000
unsigned TypeBits = Ty->getPrimitiveSize()*8;
int64_t Val = -1; // All ones
Val <<= TypeBits-1; // Shift over to the right spot
return ConstantSInt::get(Ty, Val);
}
case Type::UByteTyID:
case Type::UShortTyID:
case Type::UIntTyID:
case Type::ULongTyID: return ConstantUInt::get(Ty, 0);
default: return 0;
}
}
// Static constructor to create an integral constant with all bits set
ConstantIntegral *ConstantIntegral::getAllOnesValue(const Type *Ty) {
switch (Ty->getTypeID()) {
case Type::BoolTyID: return ConstantBool::True;
case Type::SByteTyID:
case Type::ShortTyID:
case Type::IntTyID:
case Type::LongTyID: return ConstantSInt::get(Ty, -1);
case Type::UByteTyID:
case Type::UShortTyID:
case Type::UIntTyID:
case Type::ULongTyID: {
// Calculate ~0 of the right type...
unsigned TypeBits = Ty->getPrimitiveSize()*8;
uint64_t Val = ~0ULL; // All ones
Val >>= 64-TypeBits; // Shift out unwanted 1 bits...
return ConstantUInt::get(Ty, Val);
}
default: return 0;
}
}
bool ConstantUInt::isAllOnesValue() const {
unsigned TypeBits = getType()->getPrimitiveSize()*8;
uint64_t Val = ~0ULL; // All ones
Val >>= 64-TypeBits; // Shift out inappropriate bits
return getValue() == Val;
}
//===----------------------------------------------------------------------===//
// ConstantXXX Classes
//===----------------------------------------------------------------------===//
//===----------------------------------------------------------------------===//
// Normal Constructors
ConstantIntegral::ConstantIntegral(const Type *Ty, uint64_t V)
: Constant(Ty) {
Val.Unsigned = V;
}
ConstantBool::ConstantBool(bool V) : ConstantIntegral(Type::BoolTy, V) {
}
ConstantInt::ConstantInt(const Type *Ty, uint64_t V) : ConstantIntegral(Ty, V) {
}
ConstantSInt::ConstantSInt(const Type *Ty, int64_t V) : ConstantInt(Ty, V) {
assert(Ty->isInteger() && Ty->isSigned() &&
"Illegal type for unsigned integer constant!");
assert(isValueValidForType(Ty, V) && "Value too large for type!");
}
ConstantUInt::ConstantUInt(const Type *Ty, uint64_t V) : ConstantInt(Ty, V) {
assert(Ty->isInteger() && Ty->isUnsigned() &&
"Illegal type for unsigned integer constant!");
assert(isValueValidForType(Ty, V) && "Value too large for type!");
}
ConstantFP::ConstantFP(const Type *Ty, double V) : Constant(Ty) {
assert(isValueValidForType(Ty, V) && "Value too large for type!");
Val = V;
}
ConstantArray::ConstantArray(const ArrayType *T,
const std::vector<Constant*> &V) : Constant(T) {
Operands.reserve(V.size());
for (unsigned i = 0, e = V.size(); i != e; ++i) {
assert(V[i]->getType() == T->getElementType() ||
(T->isAbstract() &&
V[i]->getType()->getTypeID() == T->getElementType()->getTypeID()));
Operands.push_back(Use(V[i], this));
}
}
ConstantStruct::ConstantStruct(const StructType *T,
const std::vector<Constant*> &V) : Constant(T) {
assert(V.size() == T->getNumElements() &&
"Invalid initializer vector for constant structure");
Operands.reserve(V.size());
for (unsigned i = 0, e = V.size(); i != e; ++i) {
assert((V[i]->getType() == T->getElementType(i) ||
((T->getElementType(i)->isAbstract() ||
V[i]->getType()->isAbstract()) &&
T->getElementType(i)->getTypeID() == V[i]->getType()->getTypeID())) &&
"Initializer for struct element doesn't match struct element type!");
Operands.push_back(Use(V[i], this));
}
}
ConstantExpr::ConstantExpr(unsigned Opcode, Constant *C, const Type *Ty)
: Constant(Ty, ConstantExprVal), iType(Opcode) {
Operands.reserve(1);
Operands.push_back(Use(C, this));
}
// Select instruction creation ctor
ConstantExpr::ConstantExpr(Constant *C, Constant *V1, Constant *V2)
: Constant(V1->getType(), ConstantExprVal), iType(Instruction::Select) {
Operands.reserve(3);
Operands.push_back(Use(C, this));
Operands.push_back(Use(V1, this));
Operands.push_back(Use(V2, this));
}
static bool isSetCC(unsigned Opcode) {
return Opcode == Instruction::SetEQ || Opcode == Instruction::SetNE ||
Opcode == Instruction::SetLT || Opcode == Instruction::SetGT ||
Opcode == Instruction::SetLE || Opcode == Instruction::SetGE;
}
ConstantExpr::ConstantExpr(unsigned Opcode, Constant *C1, Constant *C2)
: Constant(isSetCC(Opcode) ? Type::BoolTy : C1->getType(), ConstantExprVal),
iType(Opcode) {
Operands.reserve(2);
Operands.push_back(Use(C1, this));
Operands.push_back(Use(C2, this));
}
ConstantExpr::ConstantExpr(Constant *C, const std::vector<Constant*> &IdxList,
const Type *DestTy)
: Constant(DestTy, ConstantExprVal), iType(Instruction::GetElementPtr) {
Operands.reserve(1+IdxList.size());
Operands.push_back(Use(C, this));
for (unsigned i = 0, E = IdxList.size(); i != E; ++i)
Operands.push_back(Use(IdxList[i], this));
}
/// ConstantExpr::get* - Return some common constants without having to
/// specify the full Instruction::OPCODE identifier.
///
Constant *ConstantExpr::getNeg(Constant *C) {
if (!C->getType()->isFloatingPoint())
return get(Instruction::Sub, getNullValue(C->getType()), C);
else
return get(Instruction::Sub, ConstantFP::get(C->getType(), -0.0), C);
}
Constant *ConstantExpr::getNot(Constant *C) {
assert(isa<ConstantIntegral>(C) && "Cannot NOT a nonintegral type!");
return get(Instruction::Xor, C,
ConstantIntegral::getAllOnesValue(C->getType()));
}
Constant *ConstantExpr::getAdd(Constant *C1, Constant *C2) {
return get(Instruction::Add, C1, C2);
}
Constant *ConstantExpr::getSub(Constant *C1, Constant *C2) {
return get(Instruction::Sub, C1, C2);
}
Constant *ConstantExpr::getMul(Constant *C1, Constant *C2) {
return get(Instruction::Mul, C1, C2);
}
Constant *ConstantExpr::getDiv(Constant *C1, Constant *C2) {
return get(Instruction::Div, C1, C2);
}
Constant *ConstantExpr::getRem(Constant *C1, Constant *C2) {
return get(Instruction::Rem, C1, C2);
}
Constant *ConstantExpr::getAnd(Constant *C1, Constant *C2) {
return get(Instruction::And, C1, C2);
}
Constant *ConstantExpr::getOr(Constant *C1, Constant *C2) {
return get(Instruction::Or, C1, C2);
}
Constant *ConstantExpr::getXor(Constant *C1, Constant *C2) {
return get(Instruction::Xor, C1, C2);
}
Constant *ConstantExpr::getSetEQ(Constant *C1, Constant *C2) {
return get(Instruction::SetEQ, C1, C2);
}
Constant *ConstantExpr::getSetNE(Constant *C1, Constant *C2) {
return get(Instruction::SetNE, C1, C2);
}
Constant *ConstantExpr::getSetLT(Constant *C1, Constant *C2) {
return get(Instruction::SetLT, C1, C2);
}
Constant *ConstantExpr::getSetGT(Constant *C1, Constant *C2) {
return get(Instruction::SetGT, C1, C2);
}
Constant *ConstantExpr::getSetLE(Constant *C1, Constant *C2) {
return get(Instruction::SetLE, C1, C2);
}
Constant *ConstantExpr::getSetGE(Constant *C1, Constant *C2) {
return get(Instruction::SetGE, C1, C2);
}
Constant *ConstantExpr::getShl(Constant *C1, Constant *C2) {
return get(Instruction::Shl, C1, C2);
}
Constant *ConstantExpr::getShr(Constant *C1, Constant *C2) {
return get(Instruction::Shr, C1, C2);
}
Constant *ConstantExpr::getUShr(Constant *C1, Constant *C2) {
if (C1->getType()->isUnsigned()) return getShr(C1, C2);
return getCast(getShr(getCast(C1,
C1->getType()->getUnsignedVersion()), C2), C1->getType());
}
Constant *ConstantExpr::getSShr(Constant *C1, Constant *C2) {
if (C1->getType()->isSigned()) return getShr(C1, C2);
return getCast(getShr(getCast(C1,
C1->getType()->getSignedVersion()), C2), C1->getType());
}
//===----------------------------------------------------------------------===//
// isValueValidForType implementations
bool ConstantSInt::isValueValidForType(const Type *Ty, int64_t Val) {
switch (Ty->getTypeID()) {
default:
return false; // These can't be represented as integers!!!
// Signed types...
case Type::SByteTyID:
return (Val <= INT8_MAX && Val >= INT8_MIN);
case Type::ShortTyID:
return (Val <= INT16_MAX && Val >= INT16_MIN);
case Type::IntTyID:
return (Val <= int(INT32_MAX) && Val >= int(INT32_MIN));
case Type::LongTyID:
return true; // This is the largest type...
}
}
bool ConstantUInt::isValueValidForType(const Type *Ty, uint64_t Val) {
switch (Ty->getTypeID()) {
default:
return false; // These can't be represented as integers!!!
// Unsigned types...
case Type::UByteTyID:
return (Val <= UINT8_MAX);
case Type::UShortTyID:
return (Val <= UINT16_MAX);
case Type::UIntTyID:
return (Val <= UINT32_MAX);
case Type::ULongTyID:
return true; // This is the largest type...
}
}
bool ConstantFP::isValueValidForType(const Type *Ty, double Val) {
switch (Ty->getTypeID()) {
default:
return false; // These can't be represented as floating point!
// TODO: Figure out how to test if a double can be cast to a float!
case Type::FloatTyID:
case Type::DoubleTyID:
return true; // This is the largest type...
}
};
//===----------------------------------------------------------------------===//
// replaceUsesOfWithOnConstant implementations
void ConstantArray::replaceUsesOfWithOnConstant(Value *From, Value *To,
bool DisableChecking) {
assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
std::vector<Constant*> Values;
Values.reserve(getValues().size()); // Build replacement array...
for (unsigned i = 0, e = getValues().size(); i != e; ++i) {
Constant *Val = cast<Constant>(getValues()[i]);
if (Val == From) Val = cast<Constant>(To);
Values.push_back(Val);
}
Constant *Replacement = ConstantArray::get(getType(), Values);
assert(Replacement != this && "I didn't contain From!");
// Everyone using this now uses the replacement...
if (DisableChecking)
uncheckedReplaceAllUsesWith(Replacement);
else
replaceAllUsesWith(Replacement);
// Delete the old constant!
destroyConstant();
}
void ConstantStruct::replaceUsesOfWithOnConstant(Value *From, Value *To,
bool DisableChecking) {
assert(isa<Constant>(To) && "Cannot make Constant refer to non-constant!");
std::vector<Constant*> Values;
Values.reserve(getValues().size());
for (unsigned i = 0, e = getValues().size(); i != e; ++i) {
Constant *Val = cast<Constant>(getValues()[i]);
if (Val == From) Val = cast<Constant>(To);
Values.push_back(Val);
}
Constant *Replacement = ConstantStruct::get(getType(), Values);
assert(Replacement != this && "I didn't contain From!");
// Everyone using this now uses the replacement...
if (DisableChecking)
uncheckedReplaceAllUsesWith(Replacement);
else
replaceAllUsesWith(Replacement);
// Delete the old constant!
destroyConstant();
}
void ConstantExpr::replaceUsesOfWithOnConstant(Value *From, Value *ToV,
bool DisableChecking) {
assert(isa<Constant>(ToV) && "Cannot make Constant refer to non-constant!");
Constant *To = cast<Constant>(ToV);
Constant *Replacement = 0;
if (getOpcode() == Instruction::GetElementPtr) {
std::vector<Constant*> Indices;
Constant *Pointer = getOperand(0);
Indices.reserve(getNumOperands()-1);
if (Pointer == From) Pointer = To;
for (unsigned i = 1, e = getNumOperands(); i != e; ++i) {
Constant *Val = getOperand(i);
if (Val == From) Val = To;
Indices.push_back(Val);
}
Replacement = ConstantExpr::getGetElementPtr(Pointer, Indices);
} else if (getOpcode() == Instruction::Cast) {
assert(getOperand(0) == From && "Cast only has one use!");
Replacement = ConstantExpr::getCast(To, getType());
} else if (getOpcode() == Instruction::Select) {
Constant *C1 = getOperand(0);
Constant *C2 = getOperand(1);
Constant *C3 = getOperand(2);
if (C1 == From) C1 = To;
if (C2 == From) C2 = To;
if (C3 == From) C3 = To;
Replacement = ConstantExpr::getSelect(C1, C2, C3);
} else if (getNumOperands() == 2) {
Constant *C1 = getOperand(0);
Constant *C2 = getOperand(1);
if (C1 == From) C1 = To;
if (C2 == From) C2 = To;
Replacement = ConstantExpr::get(getOpcode(), C1, C2);
} else {
assert(0 && "Unknown ConstantExpr type!");
return;
}
assert(Replacement != this && "I didn't contain From!");
// Everyone using this now uses the replacement...
if (DisableChecking)
uncheckedReplaceAllUsesWith(Replacement);
else
replaceAllUsesWith(Replacement);
// Delete the old constant!
destroyConstant();
}
//===----------------------------------------------------------------------===//
// Factory Function Implementation
// ConstantCreator - A class that is used to create constants by
// ValueMap*. This class should be partially specialized if there is
// something strange that needs to be done to interface to the ctor for the
// constant.
//
namespace llvm {
template<class ConstantClass, class TypeClass, class ValType>
struct ConstantCreator {
static ConstantClass *create(const TypeClass *Ty, const ValType &V) {
return new ConstantClass(Ty, V);
}
};
template<class ConstantClass, class TypeClass>
struct ConvertConstantType {
static void convert(ConstantClass *OldC, const TypeClass *NewTy) {
assert(0 && "This type cannot be converted!\n");
abort();
}
};
}
namespace {
template<class ValType, class TypeClass, class ConstantClass>
class ValueMap : public AbstractTypeUser {
typedef std::pair<const TypeClass*, ValType> MapKey;
typedef std::map<MapKey, ConstantClass *> MapTy;
typedef typename MapTy::iterator MapIterator;
MapTy Map;
typedef std::map<const TypeClass*, MapIterator> AbstractTypeMapTy;
AbstractTypeMapTy AbstractTypeMap;
public:
// getOrCreate - Return the specified constant from the map, creating it if
// necessary.
ConstantClass *getOrCreate(const TypeClass *Ty, const ValType &V) {
MapKey Lookup(Ty, V);
MapIterator I = Map.lower_bound(Lookup);
if (I != Map.end() && I->first == Lookup)
return I->second; // Is it in the map?
// If no preexisting value, create one now...
ConstantClass *Result =
ConstantCreator<ConstantClass,TypeClass,ValType>::create(Ty, V);
/// FIXME: why does this assert fail when loading 176.gcc?
//assert(Result->getType() == Ty && "Type specified is not correct!");
I = Map.insert(I, std::make_pair(MapKey(Ty, V), Result));
// If the type of the constant is abstract, make sure that an entry exists
// for it in the AbstractTypeMap.
if (Ty->isAbstract()) {
typename AbstractTypeMapTy::iterator TI =
AbstractTypeMap.lower_bound(Ty);
if (TI == AbstractTypeMap.end() || TI->first != Ty) {
// Add ourselves to the ATU list of the type.
cast<DerivedType>(Ty)->addAbstractTypeUser(this);
AbstractTypeMap.insert(TI, std::make_pair(Ty, I));
}
}
return Result;
}
void remove(ConstantClass *CP) {
// FIXME: This should not use a linear scan. If this gets to be a
// performance problem, someone should look at this.
MapIterator I = Map.begin();
for (MapIterator E = Map.end(); I != E && I->second != CP; ++I)
/* empty */;
assert(I != Map.end() && "Constant not found in constant table!");
// Now that we found the entry, make sure this isn't the entry that
// the AbstractTypeMap points to.
const TypeClass *Ty = I->first.first;
if (Ty->isAbstract()) {
assert(AbstractTypeMap.count(Ty) &&
"Abstract type not in AbstractTypeMap?");
MapIterator &ATMEntryIt = AbstractTypeMap[Ty];
if (ATMEntryIt == I) {
// Yes, we are removing the representative entry for this type.
// See if there are any other entries of the same type.
MapIterator TmpIt = ATMEntryIt;
// First check the entry before this one...
if (TmpIt != Map.begin()) {
--TmpIt;
if (TmpIt->first.first != Ty) // Not the same type, move back...
++TmpIt;
}
// If we didn't find the same type, try to move forward...
if (TmpIt == ATMEntryIt) {
++TmpIt;
if (TmpIt == Map.end() || TmpIt->first.first != Ty)
--TmpIt; // No entry afterwards with the same type
}
// If there is another entry in the map of the same abstract type,
// update the AbstractTypeMap entry now.
if (TmpIt != ATMEntryIt) {
ATMEntryIt = TmpIt;
} else {
// Otherwise, we are removing the last instance of this type
// from the table. Remove from the ATM, and from user list.
cast<DerivedType>(Ty)->removeAbstractTypeUser(this);
AbstractTypeMap.erase(Ty);
}
}
}
Map.erase(I);
}
void refineAbstractType(const DerivedType *OldTy, const Type *NewTy) {
typename AbstractTypeMapTy::iterator I =
AbstractTypeMap.find(cast<TypeClass>(OldTy));
assert(I != AbstractTypeMap.end() &&
"Abstract type not in AbstractTypeMap?");
// Convert a constant at a time until the last one is gone. The last one
// leaving will remove() itself, causing the AbstractTypeMapEntry to be
// eliminated eventually.
do {
ConvertConstantType<ConstantClass,
TypeClass>::convert(I->second->second,
cast<TypeClass>(NewTy));
I = AbstractTypeMap.find(cast<TypeClass>(OldTy));
} while (I != AbstractTypeMap.end());
}
// If the type became concrete without being refined to any other existing
// type, we just remove ourselves from the ATU list.
void typeBecameConcrete(const DerivedType *AbsTy) {
AbsTy->removeAbstractTypeUser(this);
}
void dump() const {
std::cerr << "Constant.cpp: ValueMap\n";
}
};
}
//---- ConstantUInt::get() and ConstantSInt::get() implementations...
//
static ValueMap< int64_t, Type, ConstantSInt> SIntConstants;
static ValueMap<uint64_t, Type, ConstantUInt> UIntConstants;
ConstantSInt *ConstantSInt::get(const Type *Ty, int64_t V) {
return SIntConstants.getOrCreate(Ty, V);
}
ConstantUInt *ConstantUInt::get(const Type *Ty, uint64_t V) {
return UIntConstants.getOrCreate(Ty, V);
}
ConstantInt *ConstantInt::get(const Type *Ty, unsigned char V) {
assert(V <= 127 && "Can only be used with very small positive constants!");
if (Ty->isSigned()) return ConstantSInt::get(Ty, V);
return ConstantUInt::get(Ty, V);
}
//---- ConstantFP::get() implementation...
//
namespace llvm {
template<>
struct ConstantCreator<ConstantFP, Type, uint64_t> {
static ConstantFP *create(const Type *Ty, uint64_t V) {
assert(Ty == Type::DoubleTy);
union {
double F;
uint64_t I;
} T;
T.I = V;
return new ConstantFP(Ty, T.F);
}
};
template<>
struct ConstantCreator<ConstantFP, Type, uint32_t> {
static ConstantFP *create(const Type *Ty, uint32_t V) {
assert(Ty == Type::FloatTy);
union {
float F;
uint32_t I;
} T;
T.I = V;
return new ConstantFP(Ty, T.F);
}
};
}
static ValueMap<uint64_t, Type, ConstantFP> DoubleConstants;
static ValueMap<uint32_t, Type, ConstantFP> FloatConstants;
ConstantFP *ConstantFP::get(const Type *Ty, double V) {
if (Ty == Type::FloatTy) {
// Force the value through memory to normalize it.
union {
float F;
uint32_t I;
} T;
T.F = (float)V;
return FloatConstants.getOrCreate(Ty, T.I);
} else {
assert(Ty == Type::DoubleTy);
union {
double F;
uint64_t I;
} T;
T.F = V;
return DoubleConstants.getOrCreate(Ty, T.I);
}
}
//---- ConstantAggregateZero::get() implementation...
//
namespace llvm {
// ConstantAggregateZero does not take extra "value" argument...
template<class ValType>
struct ConstantCreator<ConstantAggregateZero, Type, ValType> {
static ConstantAggregateZero *create(const Type *Ty, const ValType &V){
return new ConstantAggregateZero(Ty);
}
};
template<>
struct ConvertConstantType<ConstantAggregateZero, Type> {
static void convert(ConstantAggregateZero *OldC, const Type *NewTy) {
// Make everyone now use a constant of the new type...
Constant *New = ConstantAggregateZero::get(NewTy);
assert(New != OldC && "Didn't replace constant??");
OldC->uncheckedReplaceAllUsesWith(New);
OldC->destroyConstant(); // This constant is now dead, destroy it.
}
};
}
static ValueMap<char, Type, ConstantAggregateZero> AggZeroConstants;
Constant *ConstantAggregateZero::get(const Type *Ty) {
return AggZeroConstants.getOrCreate(Ty, 0);
}
// destroyConstant - Remove the constant from the constant table...
//
void ConstantAggregateZero::destroyConstant() {
AggZeroConstants.remove(this);
destroyConstantImpl();
}
void ConstantAggregateZero::replaceUsesOfWithOnConstant(Value *From, Value *To,
bool DisableChecking) {
assert(0 && "No uses!");
abort();
}
//---- ConstantArray::get() implementation...
//
namespace llvm {
template<>
struct ConvertConstantType<ConstantArray, ArrayType> {
static void convert(ConstantArray *OldC, const ArrayType *NewTy) {
// Make everyone now use a constant of the new type...
std::vector<Constant*> C;
for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
C.push_back(cast<Constant>(OldC->getOperand(i)));
Constant *New = ConstantArray::get(NewTy, C);
assert(New != OldC && "Didn't replace constant??");
OldC->uncheckedReplaceAllUsesWith(New);
OldC->destroyConstant(); // This constant is now dead, destroy it.
}
};
}
static ValueMap<std::vector<Constant*>, ArrayType,
ConstantArray> ArrayConstants;
Constant *ConstantArray::get(const ArrayType *Ty,
const std::vector<Constant*> &V) {
// If this is an all-zero array, return a ConstantAggregateZero object
if (!V.empty()) {
Constant *C = V[0];
if (!C->isNullValue())
return ArrayConstants.getOrCreate(Ty, V);
for (unsigned i = 1, e = V.size(); i != e; ++i)
if (V[i] != C)
return ArrayConstants.getOrCreate(Ty, V);
}
return ConstantAggregateZero::get(Ty);
}
// destroyConstant - Remove the constant from the constant table...
//
void ConstantArray::destroyConstant() {
ArrayConstants.remove(this);
destroyConstantImpl();
}
// ConstantArray::get(const string&) - Return an array that is initialized to
// contain the specified string. A null terminator is added to the specified
// string so that it may be used in a natural way...
//
Constant *ConstantArray::get(const std::string &Str) {
std::vector<Constant*> ElementVals;
for (unsigned i = 0; i < Str.length(); ++i)
ElementVals.push_back(ConstantSInt::get(Type::SByteTy, Str[i]));
// Add a null terminator to the string...
ElementVals.push_back(ConstantSInt::get(Type::SByteTy, 0));
ArrayType *ATy = ArrayType::get(Type::SByteTy, Str.length()+1);
return ConstantArray::get(ATy, ElementVals);
}
/// isString - This method returns true if the array is an array of sbyte or
/// ubyte, and if the elements of the array are all ConstantInt's.
bool ConstantArray::isString() const {
// Check the element type for sbyte or ubyte...
if (getType()->getElementType() != Type::UByteTy &&
getType()->getElementType() != Type::SByteTy)
return false;
// Check the elements to make sure they are all integers, not constant
// expressions.
for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
if (!isa<ConstantInt>(getOperand(i)))
return false;
return true;
}
// getAsString - If the sub-element type of this array is either sbyte or ubyte,
// then this method converts the array to an std::string and returns it.
// Otherwise, it asserts out.
//
std::string ConstantArray::getAsString() const {
assert(isString() && "Not a string!");
std::string Result;
for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
Result += (char)cast<ConstantInt>(getOperand(i))->getRawValue();
return Result;
}
//---- ConstantStruct::get() implementation...
//
namespace llvm {
template<>
struct ConvertConstantType<ConstantStruct, StructType> {
static void convert(ConstantStruct *OldC, const StructType *NewTy) {
// Make everyone now use a constant of the new type...
std::vector<Constant*> C;
for (unsigned i = 0, e = OldC->getNumOperands(); i != e; ++i)
C.push_back(cast<Constant>(OldC->getOperand(i)));
Constant *New = ConstantStruct::get(NewTy, C);
assert(New != OldC && "Didn't replace constant??");
OldC->uncheckedReplaceAllUsesWith(New);
OldC->destroyConstant(); // This constant is now dead, destroy it.
}
};
}
static ValueMap<std::vector<Constant*>, StructType,
ConstantStruct> StructConstants;
Constant *ConstantStruct::get(const StructType *Ty,
const std::vector<Constant*> &V) {
// Create a ConstantAggregateZero value if all elements are zeros...
for (unsigned i = 0, e = V.size(); i != e; ++i)
if (!V[i]->isNullValue())
return StructConstants.getOrCreate(Ty, V);
return ConstantAggregateZero::get(Ty);
}
Constant *ConstantStruct::get(const std::vector<Constant*> &V) {
std::vector<const Type*> StructEls;
StructEls.reserve(V.size());
for (unsigned i = 0, e = V.size(); i != e; ++i)
StructEls.push_back(V[i]->getType());
return get(StructType::get(StructEls), V);
}
// destroyConstant - Remove the constant from the constant table...
//
void ConstantStruct::destroyConstant() {
StructConstants.remove(this);
destroyConstantImpl();
}
//---- ConstantPointerNull::get() implementation...
//
namespace llvm {
// ConstantPointerNull does not take extra "value" argument...
template<class ValType>
struct ConstantCreator<ConstantPointerNull, PointerType, ValType> {
static ConstantPointerNull *create(const PointerType *Ty, const ValType &V){
return new ConstantPointerNull(Ty);
}
};
template<>
struct ConvertConstantType<ConstantPointerNull, PointerType> {
static void convert(ConstantPointerNull *OldC, const PointerType *NewTy) {
// Make everyone now use a constant of the new type...
Constant *New = ConstantPointerNull::get(NewTy);
assert(New != OldC && "Didn't replace constant??");
OldC->uncheckedReplaceAllUsesWith(New);
OldC->destroyConstant(); // This constant is now dead, destroy it.
}
};
}
static ValueMap<char, PointerType, ConstantPointerNull> NullPtrConstants;
ConstantPointerNull *ConstantPointerNull::get(const PointerType *Ty) {
return NullPtrConstants.getOrCreate(Ty, 0);
}
// destroyConstant - Remove the constant from the constant table...
//
void ConstantPointerNull::destroyConstant() {
NullPtrConstants.remove(this);
destroyConstantImpl();
}
//---- ConstantExpr::get() implementations...
//
typedef std::pair<unsigned, std::vector<Constant*> > ExprMapKeyType;
namespace llvm {
template<>
struct ConstantCreator<ConstantExpr, Type, ExprMapKeyType> {
static ConstantExpr *create(const Type *Ty, const ExprMapKeyType &V) {
if (V.first == Instruction::Cast)
return new ConstantExpr(Instruction::Cast, V.second[0], Ty);
if ((V.first >= Instruction::BinaryOpsBegin &&
V.first < Instruction::BinaryOpsEnd) ||
V.first == Instruction::Shl || V.first == Instruction::Shr)
return new ConstantExpr(V.first, V.second[0], V.second[1]);
if (V.first == Instruction::Select)
return new ConstantExpr(V.second[0], V.second[1], V.second[2]);
assert(V.first == Instruction::GetElementPtr && "Invalid ConstantExpr!");
std::vector<Constant*> IdxList(V.second.begin()+1, V.second.end());
return new ConstantExpr(V.second[0], IdxList, Ty);
}
};
template<>
struct ConvertConstantType<ConstantExpr, Type> {
static void convert(ConstantExpr *OldC, const Type *NewTy) {
Constant *New;
switch (OldC->getOpcode()) {
case Instruction::Cast:
New = ConstantExpr::getCast(OldC->getOperand(0), NewTy);
break;
case Instruction::Select:
New = ConstantExpr::getSelectTy(NewTy, OldC->getOperand(0),
OldC->getOperand(1),
OldC->getOperand(2));
break;
case Instruction::Shl:
case Instruction::Shr:
New = ConstantExpr::getShiftTy(NewTy, OldC->getOpcode(),
OldC->getOperand(0), OldC->getOperand(1));
break;
default:
assert(OldC->getOpcode() >= Instruction::BinaryOpsBegin &&
OldC->getOpcode() < Instruction::BinaryOpsEnd);
New = ConstantExpr::getTy(NewTy, OldC->getOpcode(), OldC->getOperand(0),
OldC->getOperand(1));
break;
case Instruction::GetElementPtr:
// Make everyone now use a constant of the new type...
std::vector<Constant*> C;
for (unsigned i = 1, e = OldC->getNumOperands(); i != e; ++i)
C.push_back(cast<Constant>(OldC->getOperand(i)));
New = ConstantExpr::getGetElementPtrTy(NewTy, OldC->getOperand(0), C);
break;
}
assert(New != OldC && "Didn't replace constant??");
OldC->uncheckedReplaceAllUsesWith(New);
OldC->destroyConstant(); // This constant is now dead, destroy it.
}
};
} // end namespace llvm
static ValueMap<ExprMapKeyType, Type, ConstantExpr> ExprConstants;
Constant *ConstantExpr::getCast(Constant *C, const Type *Ty) {
assert(Ty->isFirstClassType() && "Cannot cast to an aggregate type!");
if (Constant *FC = ConstantFoldCastInstruction(C, Ty))
return FC; // Fold a few common cases...
// Look up the constant in the table first to ensure uniqueness
std::vector<Constant*> argVec(1, C);
ExprMapKeyType Key = std::make_pair(Instruction::Cast, argVec);
return ExprConstants.getOrCreate(Ty, Key);
}
Constant *ConstantExpr::getSignExtend(Constant *C, const Type *Ty) {
assert(C->getType()->isInteger() && Ty->isInteger() &&
C->getType()->getPrimitiveSize() <= Ty->getPrimitiveSize() &&
"This is an illegal sign extension!");
C = ConstantExpr::getCast(C, C->getType()->getSignedVersion());
return ConstantExpr::getCast(C, Ty);
}
Constant *ConstantExpr::getZeroExtend(Constant *C, const Type *Ty) {
assert(C->getType()->isInteger() && Ty->isInteger() &&
C->getType()->getPrimitiveSize() <= Ty->getPrimitiveSize() &&
"This is an illegal zero extension!");
C = ConstantExpr::getCast(C, C->getType()->getUnsignedVersion());
return ConstantExpr::getCast(C, Ty);
}
Constant *ConstantExpr::getTy(const Type *ReqTy, unsigned Opcode,
Constant *C1, Constant *C2) {
if (Opcode == Instruction::Shl || Opcode == Instruction::Shr)
return getShiftTy(ReqTy, Opcode, C1, C2);
// Check the operands for consistency first
assert((Opcode >= Instruction::BinaryOpsBegin &&
Opcode < Instruction::BinaryOpsEnd) &&
"Invalid opcode in binary constant expression");
assert(C1->getType() == C2->getType() &&
"Operand types in binary constant expression should match");
if (ReqTy == C1->getType())
if (Constant *FC = ConstantFoldBinaryInstruction(Opcode, C1, C2))
return FC; // Fold a few common cases...
std::vector<Constant*> argVec(1, C1); argVec.push_back(C2);
ExprMapKeyType Key = std::make_pair(Opcode, argVec);
return ExprConstants.getOrCreate(ReqTy, Key);
}
Constant *ConstantExpr::getSelectTy(const Type *ReqTy, Constant *C,
Constant *V1, Constant *V2) {
assert(C->getType() == Type::BoolTy && "Select condition must be bool!");
assert(V1->getType() == V2->getType() && "Select value types must match!");
assert(V1->getType()->isFirstClassType() && "Cannot select aggregate type!");
if (ReqTy == V1->getType())
if (Constant *SC = ConstantFoldSelectInstruction(C, V1, V2))
return SC; // Fold common cases
std::vector<Constant*> argVec(3, C);
argVec[1] = V1;
argVec[2] = V2;
ExprMapKeyType Key = std::make_pair(Instruction::Select, argVec);
return ExprConstants.getOrCreate(ReqTy, Key);
}
/// getShiftTy - Return a shift left or shift right constant expr
Constant *ConstantExpr::getShiftTy(const Type *ReqTy, unsigned Opcode,
Constant *C1, Constant *C2) {
// Check the operands for consistency first
assert((Opcode == Instruction::Shl ||
Opcode == Instruction::Shr) &&
"Invalid opcode in binary constant expression");
assert(C1->getType()->isIntegral() && C2->getType() == Type::UByteTy &&
"Invalid operand types for Shift constant expr!");
if (Constant *FC = ConstantFoldBinaryInstruction(Opcode, C1, C2))
return FC; // Fold a few common cases...
// Look up the constant in the table first to ensure uniqueness
std::vector<Constant*> argVec(1, C1); argVec.push_back(C2);
ExprMapKeyType Key = std::make_pair(Opcode, argVec);
return ExprConstants.getOrCreate(ReqTy, Key);
}
Constant *ConstantExpr::getGetElementPtrTy(const Type *ReqTy, Constant *C,
const std::vector<Constant*> &IdxList) {
assert(GetElementPtrInst::getIndexedType(C->getType(),
std::vector<Value*>(IdxList.begin(), IdxList.end()), true) &&
"GEP indices invalid!");
if (Constant *FC = ConstantFoldGetElementPtr(C, IdxList))
return FC; // Fold a few common cases...
assert(isa<PointerType>(C->getType()) &&
"Non-pointer type for constant GetElementPtr expression");
// Look up the constant in the table first to ensure uniqueness
std::vector<Constant*> argVec(1, C);
argVec.insert(argVec.end(), IdxList.begin(), IdxList.end());
const ExprMapKeyType &Key = std::make_pair(Instruction::GetElementPtr,argVec);
return ExprConstants.getOrCreate(ReqTy, Key);
}
Constant *ConstantExpr::getGetElementPtr(Constant *C,
const std::vector<Constant*> &IdxList){
// Get the result type of the getelementptr!
std::vector<Value*> VIdxList(IdxList.begin(), IdxList.end());
const Type *Ty = GetElementPtrInst::getIndexedType(C->getType(), VIdxList,
true);
assert(Ty && "GEP indices invalid!");
return getGetElementPtrTy(PointerType::get(Ty), C, IdxList);
}
// destroyConstant - Remove the constant from the constant table...
//
void ConstantExpr::destroyConstant() {
ExprConstants.remove(this);
destroyConstantImpl();
}
const char *ConstantExpr::getOpcodeName() const {
return Instruction::getOpcodeName(getOpcode());
}
Property changes on: llvm/trunk/lib/VMCore/Constants.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.96
\ No newline at end of property
+1.97
\ No newline at end of property
Index: llvm/trunk/lib/VMCore/InstrTypes.cpp
===================================================================
--- llvm/trunk/lib/VMCore/InstrTypes.cpp (revision 15333)
+++ llvm/trunk/lib/VMCore/InstrTypes.cpp (revision 15334)
@@ -1,65 +1,64 @@
//===-- InstrTypes.cpp - Implement Instruction subclasses -------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements
//
//===----------------------------------------------------------------------===//
-#include "llvm/iOther.h"
-#include "llvm/iPHINode.h"
+#include "llvm/Instructions.h"
#include "llvm/Function.h"
#include "llvm/SymbolTable.h"
#include "llvm/Constant.h"
#include "llvm/Type.h"
#include <algorithm> // find
using namespace llvm;
//===----------------------------------------------------------------------===//
// TerminatorInst Class
//===----------------------------------------------------------------------===//
TerminatorInst::TerminatorInst(Instruction::TermOps iType, Instruction *IB)
: Instruction(Type::VoidTy, iType, "", IB) {
}
TerminatorInst::TerminatorInst(Instruction::TermOps iType, BasicBlock *IAE)
: Instruction(Type::VoidTy, iType, "", IAE) {
}
//===----------------------------------------------------------------------===//
// PHINode Class
//===----------------------------------------------------------------------===//
PHINode::PHINode(const PHINode &PN)
: Instruction(PN.getType(), Instruction::PHI) {
Operands.reserve(PN.Operands.size());
for (unsigned i = 0; i < PN.Operands.size(); i+=2) {
Operands.push_back(Use(PN.Operands[i], this));
Operands.push_back(Use(PN.Operands[i+1], this));
}
}
// removeIncomingValue - Remove an incoming value. This is useful if a
// predecessor basic block is deleted.
Value *PHINode::removeIncomingValue(unsigned Idx, bool DeletePHIIfEmpty) {
assert(Idx*2 < Operands.size() && "BB not in PHI node!");
Value *Removed = Operands[Idx*2];
Operands.erase(Operands.begin()+Idx*2, // Erase Value and BasicBlock
Operands.begin()+Idx*2+2);
// If the PHI node is dead, because it has zero entries, nuke it now.
if (getNumOperands() == 0 && DeletePHIIfEmpty) {
// If anyone is using this PHI, make them use a dummy value instead...
replaceAllUsesWith(Constant::getNullValue(getType()));
getParent()->getInstList().erase(this);
}
return Removed;
}
Property changes on: llvm/trunk/lib/VMCore/InstrTypes.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.25
\ No newline at end of property
+1.26
\ No newline at end of property
Index: llvm/trunk/lib/VMCore/Linker.cpp
===================================================================
--- llvm/trunk/lib/VMCore/Linker.cpp (revision 15333)
+++ llvm/trunk/lib/VMCore/Linker.cpp (revision 15334)
@@ -1,926 +1,926 @@
//===- Linker.cpp - Module Linker Implementation --------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements the LLVM module linker.
//
// Specifically, this:
// * Merges global variables between the two modules
// * Uninit + Uninit = Init, Init + Uninit = Init, Init + Init = Error if !=
// * Merges functions between two modules
//
//===----------------------------------------------------------------------===//
#include "llvm/Support/Linker.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/SymbolTable.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include "llvm/Assembly/Writer.h"
#include <iostream>
using namespace llvm;
// Error - Simple wrapper function to conditionally assign to E and return true.
// This just makes error return conditions a little bit simpler...
//
static inline bool Error(std::string *E, const std::string &Message) {
if (E) *E = Message;
return true;
}
//
// Function: ResolveTypes()
//
// Description:
// Attempt to link the two specified types together.
//
// Inputs:
// DestTy - The type to which we wish to resolve.
// SrcTy - The original type which we want to resolve.
// Name - The name of the type.
//
// Outputs:
// DestST - The symbol table in which the new type should be placed.
//
// Return value:
// true - There is an error and the types cannot yet be linked.
// false - No errors.
//
static bool ResolveTypes(const Type *DestTy, const Type *SrcTy,
SymbolTable *DestST, const std::string &Name) {
if (DestTy == SrcTy) return false; // If already equal, noop
// Does the type already exist in the module?
if (DestTy && !isa<OpaqueType>(DestTy)) { // Yup, the type already exists...
if (const OpaqueType *OT = dyn_cast<OpaqueType>(SrcTy)) {
const_cast<OpaqueType*>(OT)->refineAbstractTypeTo(DestTy);
} else {
return true; // Cannot link types... neither is opaque and not-equal
}
} else { // Type not in dest module. Add it now.
if (DestTy) // Type _is_ in module, just opaque...
const_cast<OpaqueType*>(cast<OpaqueType>(DestTy))
->refineAbstractTypeTo(SrcTy);
else if (!Name.empty())
DestST->insert(Name, const_cast<Type*>(SrcTy));
}
return false;
}
static const FunctionType *getFT(const PATypeHolder &TH) {
return cast<FunctionType>(TH.get());
}
static const StructType *getST(const PATypeHolder &TH) {
return cast<StructType>(TH.get());
}
// RecursiveResolveTypes - This is just like ResolveTypes, except that it
// recurses down into derived types, merging the used types if the parent types
// are compatible.
//
static bool RecursiveResolveTypesI(const PATypeHolder &DestTy,
const PATypeHolder &SrcTy,
SymbolTable *DestST, const std::string &Name,
std::vector<std::pair<PATypeHolder, PATypeHolder> > &Pointers) {
const Type *SrcTyT = SrcTy.get();
const Type *DestTyT = DestTy.get();
if (DestTyT == SrcTyT) return false; // If already equal, noop
// If we found our opaque type, resolve it now!
if (isa<OpaqueType>(DestTyT) || isa<OpaqueType>(SrcTyT))
return ResolveTypes(DestTyT, SrcTyT, DestST, Name);
// Two types cannot be resolved together if they are of different primitive
// type. For example, we cannot resolve an int to a float.
if (DestTyT->getTypeID() != SrcTyT->getTypeID()) return true;
// Otherwise, resolve the used type used by this derived type...
switch (DestTyT->getTypeID()) {
case Type::FunctionTyID: {
if (cast<FunctionType>(DestTyT)->isVarArg() !=
cast<FunctionType>(SrcTyT)->isVarArg() ||
cast<FunctionType>(DestTyT)->getNumContainedTypes() !=
cast<FunctionType>(SrcTyT)->getNumContainedTypes())
return true;
for (unsigned i = 0, e = getFT(DestTy)->getNumContainedTypes(); i != e; ++i)
if (RecursiveResolveTypesI(getFT(DestTy)->getContainedType(i),
getFT(SrcTy)->getContainedType(i), DestST, "",
Pointers))
return true;
return false;
}
case Type::StructTyID: {
if (getST(DestTy)->getNumContainedTypes() !=
getST(SrcTy)->getNumContainedTypes()) return 1;
for (unsigned i = 0, e = getST(DestTy)->getNumContainedTypes(); i != e; ++i)
if (RecursiveResolveTypesI(getST(DestTy)->getContainedType(i),
getST(SrcTy)->getContainedType(i), DestST, "",
Pointers))
return true;
return false;
}
case Type::ArrayTyID: {
const ArrayType *DAT = cast<ArrayType>(DestTy.get());
const ArrayType *SAT = cast<ArrayType>(SrcTy.get());
if (DAT->getNumElements() != SAT->getNumElements()) return true;
return RecursiveResolveTypesI(DAT->getElementType(), SAT->getElementType(),
DestST, "", Pointers);
}
case Type::PointerTyID: {
// If this is a pointer type, check to see if we have already seen it. If
// so, we are in a recursive branch. Cut off the search now. We cannot use
// an associative container for this search, because the type pointers (keys
// in the container) change whenever types get resolved...
//
for (unsigned i = 0, e = Pointers.size(); i != e; ++i)
if (Pointers[i].first == DestTy)
return Pointers[i].second != SrcTy;
// Otherwise, add the current pointers to the vector to stop recursion on
// this pair.
Pointers.push_back(std::make_pair(DestTyT, SrcTyT));
bool Result =
RecursiveResolveTypesI(cast<PointerType>(DestTy.get())->getElementType(),
cast<PointerType>(SrcTy.get())->getElementType(),
DestST, "", Pointers);
Pointers.pop_back();
return Result;
}
default: assert(0 && "Unexpected type!"); return true;
}
}
static bool RecursiveResolveTypes(const PATypeHolder &DestTy,
const PATypeHolder &SrcTy,
SymbolTable *DestST, const std::string &Name){
std::vector<std::pair<PATypeHolder, PATypeHolder> > PointerTypes;
return RecursiveResolveTypesI(DestTy, SrcTy, DestST, Name, PointerTypes);
}
// LinkTypes - Go through the symbol table of the Src module and see if any
// types are named in the src module that are not named in the Dst module.
// Make sure there are no type name conflicts.
//
static bool LinkTypes(Module *Dest, const Module *Src, std::string *Err) {
SymbolTable *DestST = &Dest->getSymbolTable();
const SymbolTable *SrcST = &Src->getSymbolTable();
// Look for a type plane for Type's...
SymbolTable::type_const_iterator TI = SrcST->type_begin();
SymbolTable::type_const_iterator TE = SrcST->type_end();
if (TI == TE) return false; // No named types, do nothing.
// Some types cannot be resolved immediately because they depend on other
// types being resolved to each other first. This contains a list of types we
// are waiting to recheck.
std::vector<std::string> DelayedTypesToResolve;
for ( ; TI != TE; ++TI ) {
const std::string &Name = TI->first;
const Type *RHS = TI->second;
// Check to see if this type name is already in the dest module...
Type *Entry = DestST->lookupType(Name);
if (ResolveTypes(Entry, RHS, DestST, Name)) {
// They look different, save the types 'till later to resolve.
DelayedTypesToResolve.push_back(Name);
}
}
// Iteratively resolve types while we can...
while (!DelayedTypesToResolve.empty()) {
// Loop over all of the types, attempting to resolve them if possible...
unsigned OldSize = DelayedTypesToResolve.size();
// Try direct resolution by name...
for (unsigned i = 0; i != DelayedTypesToResolve.size(); ++i) {
const std::string &Name = DelayedTypesToResolve[i];
Type *T1 = SrcST->lookupType(Name);
Type *T2 = DestST->lookupType(Name);
if (!ResolveTypes(T2, T1, DestST, Name)) {
// We are making progress!
DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i);
--i;
}
}
// Did we not eliminate any types?
if (DelayedTypesToResolve.size() == OldSize) {
// Attempt to resolve subelements of types. This allows us to merge these
// two types: { int* } and { opaque* }
for (unsigned i = 0, e = DelayedTypesToResolve.size(); i != e; ++i) {
const std::string &Name = DelayedTypesToResolve[i];
PATypeHolder T1(SrcST->lookupType(Name));
PATypeHolder T2(DestST->lookupType(Name));
if (!RecursiveResolveTypes(T2, T1, DestST, Name)) {
// We are making progress!
DelayedTypesToResolve.erase(DelayedTypesToResolve.begin()+i);
// Go back to the main loop, perhaps we can resolve directly by name
// now...
break;
}
}
// If we STILL cannot resolve the types, then there is something wrong.
// Report the warning and delete one of the names.
if (DelayedTypesToResolve.size() == OldSize) {
const std::string &Name = DelayedTypesToResolve.back();
const Type *T1 = SrcST->lookupType(Name);
const Type *T2 = DestST->lookupType(Name);
std::cerr << "WARNING: Type conflict between types named '" << Name
<< "'.\n Src='";
WriteTypeSymbolic(std::cerr, T1, Src);
std::cerr << "'.\n Dest='";
WriteTypeSymbolic(std::cerr, T2, Dest);
std::cerr << "'\n";
// Remove the symbol name from the destination.
DelayedTypesToResolve.pop_back();
}
}
}
return false;
}
static void PrintMap(const std::map<const Value*, Value*> &M) {
for (std::map<const Value*, Value*>::const_iterator I = M.begin(), E =M.end();
I != E; ++I) {
std::cerr << " Fr: " << (void*)I->first << " ";
I->first->dump();
std::cerr << " To: " << (void*)I->second << " ";
I->second->dump();
std::cerr << "\n";
}
}
// RemapOperand - Use LocalMap and GlobalMap to convert references from one
// module to another. This is somewhat sophisticated in that it can
// automatically handle constant references correctly as well...
//
static Value *RemapOperand(const Value *In,
std::map<const Value*, Value*> &LocalMap,
std::map<const Value*, Value*> *GlobalMap) {
std::map<const Value*,Value*>::const_iterator I = LocalMap.find(In);
if (I != LocalMap.end()) return I->second;
if (GlobalMap) {
I = GlobalMap->find(In);
if (I != GlobalMap->end()) return I->second;
}
// Check to see if it's a constant that we are interesting in transforming...
if (const Constant *CPV = dyn_cast<Constant>(In)) {
if ((!isa<DerivedType>(CPV->getType()) && !isa<ConstantExpr>(CPV)) ||
isa<ConstantAggregateZero>(CPV))
return const_cast<Constant*>(CPV); // Simple constants stay identical...
Constant *Result = 0;
if (const ConstantArray *CPA = dyn_cast<ConstantArray>(CPV)) {
const std::vector<Use> &Ops = CPA->getValues();
std::vector<Constant*> Operands(Ops.size());
for (unsigned i = 0, e = Ops.size(); i != e; ++i)
Operands[i] =
cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap));
Result = ConstantArray::get(cast<ArrayType>(CPA->getType()), Operands);
} else if (const ConstantStruct *CPS = dyn_cast<ConstantStruct>(CPV)) {
const std::vector<Use> &Ops = CPS->getValues();
std::vector<Constant*> Operands(Ops.size());
for (unsigned i = 0; i < Ops.size(); ++i)
Operands[i] =
cast<Constant>(RemapOperand(Ops[i], LocalMap, GlobalMap));
Result = ConstantStruct::get(cast<StructType>(CPS->getType()), Operands);
} else if (isa<ConstantPointerNull>(CPV)) {
Result = const_cast<Constant*>(CPV);
} else if (isa<GlobalValue>(CPV)) {
Result = cast<Constant>(RemapOperand(CPV, LocalMap, GlobalMap));
} else if (const ConstantExpr *CE = dyn_cast<ConstantExpr>(CPV)) {
if (CE->getOpcode() == Instruction::GetElementPtr) {
Value *Ptr = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap);
std::vector<Constant*> Indices;
Indices.reserve(CE->getNumOperands()-1);
for (unsigned i = 1, e = CE->getNumOperands(); i != e; ++i)
Indices.push_back(cast<Constant>(RemapOperand(CE->getOperand(i),
LocalMap, GlobalMap)));
Result = ConstantExpr::getGetElementPtr(cast<Constant>(Ptr), Indices);
} else if (CE->getNumOperands() == 1) {
// Cast instruction
assert(CE->getOpcode() == Instruction::Cast);
Value *V = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap);
Result = ConstantExpr::getCast(cast<Constant>(V), CE->getType());
} else if (CE->getNumOperands() == 3) {
// Select instruction
assert(CE->getOpcode() == Instruction::Select);
Value *V1 = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap);
Value *V2 = RemapOperand(CE->getOperand(1), LocalMap, GlobalMap);
Value *V3 = RemapOperand(CE->getOperand(2), LocalMap, GlobalMap);
Result = ConstantExpr::getSelect(cast<Constant>(V1), cast<Constant>(V2),
cast<Constant>(V3));
} else if (CE->getNumOperands() == 2) {
// Binary operator...
Value *V1 = RemapOperand(CE->getOperand(0), LocalMap, GlobalMap);
Value *V2 = RemapOperand(CE->getOperand(1), LocalMap, GlobalMap);
Result = ConstantExpr::get(CE->getOpcode(), cast<Constant>(V1),
cast<Constant>(V2));
} else {
assert(0 && "Unknown constant expr type!");
}
} else {
assert(0 && "Unknown type of derived type constant value!");
}
// Cache the mapping in our local map structure...
if (GlobalMap)
GlobalMap->insert(std::make_pair(In, Result));
else
LocalMap.insert(std::make_pair(In, Result));
return Result;
}
std::cerr << "XXX LocalMap: \n";
PrintMap(LocalMap);
if (GlobalMap) {
std::cerr << "XXX GlobalMap: \n";
PrintMap(*GlobalMap);
}
std::cerr << "Couldn't remap value: " << (void*)In << " " << *In << "\n";
assert(0 && "Couldn't remap value!");
return 0;
}
/// FindGlobalNamed - Look in the specified symbol table for a global with the
/// specified name and type. If an exactly matching global does not exist, see
/// if there is a global which is "type compatible" with the specified
/// name/type. This allows us to resolve things like '%x = global int*' with
/// '%x = global opaque*'.
///
static GlobalValue *FindGlobalNamed(const std::string &Name, const Type *Ty,
SymbolTable *ST) {
// See if an exact match exists in the symbol table...
if (Value *V = ST->lookup(Ty, Name)) return cast<GlobalValue>(V);
// It doesn't exist exactly, scan through all of the type planes in the symbol
// table, checking each of them for a type-compatible version.
//
for (SymbolTable::plane_iterator PI = ST->plane_begin(), PE = ST->plane_end();
PI != PE; ++PI) {
SymbolTable::ValueMap &VM = PI->second;
// Does this type plane contain an entry with the specified name?
SymbolTable::value_iterator VI = VM.find(Name);
if (VI != VM.end()) {
//
// Ensure that this type if placed correctly into the symbol table.
//
assert(VI->second->getType() == PI->first && "Type conflict!");
//
// Save a reference to the new type. Resolving the type can modify the
// symbol table, invalidating the TI variable.
//
Value *ValPtr = VI->second;
//
// Determine whether we can fold the two types together, resolving them.
// If so, we can use this value.
//
if (!RecursiveResolveTypes(Ty, PI->first, ST, ""))
return cast<GlobalValue>(ValPtr);
}
}
return 0; // Otherwise, nothing could be found.
}
// LinkGlobals - Loop through the global variables in the src module and merge
// them into the dest module.
//
static bool LinkGlobals(Module *Dest, const Module *Src,
std::map<const Value*, Value*> &ValueMap,
std::multimap<std::string, GlobalVariable *> &AppendingVars,
std::string *Err) {
// We will need a module level symbol table if the src module has a module
// level symbol table...
SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable();
// Loop over all of the globals in the src module, mapping them over as we go
//
for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){
const GlobalVariable *SGV = I;
GlobalVariable *DGV = 0;
if (SGV->hasName()) {
// A same named thing is a global variable, because the only two things
// that may be in a module level symbol table are Global Vars and
// Functions, and they both have distinct, nonoverlapping, possible types.
//
DGV = cast_or_null<GlobalVariable>(FindGlobalNamed(SGV->getName(),
SGV->getType(), ST));
}
assert(SGV->hasInitializer() || SGV->hasExternalLinkage() &&
"Global must either be external or have an initializer!");
bool SGExtern = SGV->isExternal();
bool DGExtern = DGV ? DGV->isExternal() : false;
if (!DGV || DGV->hasInternalLinkage() || SGV->hasInternalLinkage()) {
// No linking to be performed, simply create an identical version of the
// symbol over in the dest module... the initializer will be filled in
// later by LinkGlobalInits...
//
GlobalVariable *NewDGV =
new GlobalVariable(SGV->getType()->getElementType(),
SGV->isConstant(), SGV->getLinkage(), /*init*/0,
SGV->getName(), Dest);
// If the LLVM runtime renamed the global, but it is an externally visible
// symbol, DGV must be an existing global with internal linkage. Rename
// it.
if (NewDGV->getName() != SGV->getName() && !NewDGV->hasInternalLinkage()){
assert(DGV && DGV->getName() == SGV->getName() &&
DGV->hasInternalLinkage());
DGV->setName("");
NewDGV->setName(SGV->getName()); // Force the name back
DGV->setName(SGV->getName()); // This will cause a renaming
assert(NewDGV->getName() == SGV->getName() &&
DGV->getName() != SGV->getName());
}
// Make sure to remember this mapping...
ValueMap.insert(std::make_pair(SGV, NewDGV));
if (SGV->hasAppendingLinkage())
// Keep track that this is an appending variable...
AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV));
} else if (SGV->isExternal()) {
// If SGV is external or if both SGV & DGV are external.. Just link the
// external globals, we aren't adding anything.
ValueMap.insert(std::make_pair(SGV, DGV));
} else if (DGV->isExternal()) { // If DGV is external but SGV is not...
ValueMap.insert(std::make_pair(SGV, DGV));
DGV->setLinkage(SGV->getLinkage()); // Inherit linkage!
} else if (SGV->hasWeakLinkage() || SGV->hasLinkOnceLinkage()) {
// At this point we know that DGV has LinkOnce, Appending, Weak, or
// External linkage. If DGV is Appending, this is an error.
if (DGV->hasAppendingLinkage())
return Error(Err, "Linking globals named '" + SGV->getName() +
" ' with 'weak' and 'appending' linkage is not allowed!");
if (SGV->isConstant() != DGV->isConstant())
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() + " %" + SGV->getName() +
"' - Global variables differ in const'ness");
// Otherwise, just perform the link.
ValueMap.insert(std::make_pair(SGV, DGV));
// Linkonce+Weak = Weak
if (DGV->hasLinkOnceLinkage() && SGV->hasWeakLinkage())
DGV->setLinkage(SGV->getLinkage());
} else if (DGV->hasWeakLinkage() || DGV->hasLinkOnceLinkage()) {
// At this point we know that SGV has LinkOnce, Appending, or External
// linkage. If SGV is Appending, this is an error.
if (SGV->hasAppendingLinkage())
return Error(Err, "Linking globals named '" + SGV->getName() +
" ' with 'weak' and 'appending' linkage is not allowed!");
if (SGV->isConstant() != DGV->isConstant())
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() + " %" + SGV->getName() +
"' - Global variables differ in const'ness");
if (!SGV->hasLinkOnceLinkage())
DGV->setLinkage(SGV->getLinkage()); // Inherit linkage!
ValueMap.insert(std::make_pair(SGV, DGV));
} else if (SGV->getLinkage() != DGV->getLinkage()) {
return Error(Err, "Global variables named '" + SGV->getName() +
"' have different linkage specifiers!");
} else if (SGV->hasExternalLinkage()) {
// Allow linking two exactly identical external global variables...
if (SGV->isConstant() != DGV->isConstant())
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() + " %" + SGV->getName() +
"' - Global variables differ in const'ness");
if (SGV->getInitializer() != DGV->getInitializer())
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() + " %" + SGV->getName() +
"' - External linkage globals have different initializers");
ValueMap.insert(std::make_pair(SGV, DGV));
} else if (SGV->hasAppendingLinkage()) {
// No linking is performed yet. Just insert a new copy of the global, and
// keep track of the fact that it is an appending variable in the
// AppendingVars map. The name is cleared out so that no linkage is
// performed.
GlobalVariable *NewDGV =
new GlobalVariable(SGV->getType()->getElementType(),
SGV->isConstant(), SGV->getLinkage(), /*init*/0,
"", Dest);
// Make sure to remember this mapping...
ValueMap.insert(std::make_pair(SGV, NewDGV));
// Keep track that this is an appending variable...
AppendingVars.insert(std::make_pair(SGV->getName(), NewDGV));
} else {
assert(0 && "Unknown linkage!");
}
}
return false;
}
// LinkGlobalInits - Update the initializers in the Dest module now that all
// globals that may be referenced are in Dest.
//
static bool LinkGlobalInits(Module *Dest, const Module *Src,
std::map<const Value*, Value*> &ValueMap,
std::string *Err) {
// Loop over all of the globals in the src module, mapping them over as we go
//
for (Module::const_giterator I = Src->gbegin(), E = Src->gend(); I != E; ++I){
const GlobalVariable *SGV = I;
if (SGV->hasInitializer()) { // Only process initialized GV's
// Figure out what the initializer looks like in the dest module...
Constant *SInit =
cast<Constant>(RemapOperand(SGV->getInitializer(), ValueMap, 0));
GlobalVariable *DGV = cast<GlobalVariable>(ValueMap[SGV]);
if (DGV->hasInitializer()) {
if (SGV->hasExternalLinkage()) {
if (DGV->getInitializer() != SInit)
return Error(Err, "Global Variable Collision on '" +
SGV->getType()->getDescription() +"':%"+SGV->getName()+
" - Global variables have different initializers");
} else if (DGV->hasLinkOnceLinkage() || DGV->hasWeakLinkage()) {
// Nothing is required, mapped values will take the new global
// automatically.
} else if (SGV->hasLinkOnceLinkage() || SGV->hasWeakLinkage()) {
// Nothing is required, mapped values will take the new global
// automatically.
} else if (DGV->hasAppendingLinkage()) {
assert(0 && "Appending linkage unimplemented!");
} else {
assert(0 && "Unknown linkage!");
}
} else {
// Copy the initializer over now...
DGV->setInitializer(SInit);
}
}
}
return false;
}
// LinkFunctionProtos - Link the functions together between the two modules,
// without doing function bodies... this just adds external function prototypes
// to the Dest function...
//
static bool LinkFunctionProtos(Module *Dest, const Module *Src,
std::map<const Value*, Value*> &ValueMap,
std::string *Err) {
SymbolTable *ST = (SymbolTable*)&Dest->getSymbolTable();
// Loop over all of the functions in the src module, mapping them over as we
// go
//
for (Module::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
const Function *SF = I; // SrcFunction
Function *DF = 0;
if (SF->hasName())
// The same named thing is a Function, because the only two things
// that may be in a module level symbol table are Global Vars and
// Functions, and they both have distinct, nonoverlapping, possible types.
//
DF = cast_or_null<Function>(FindGlobalNamed(SF->getName(), SF->getType(),
ST));
if (!DF || SF->hasInternalLinkage() || DF->hasInternalLinkage()) {
// Function does not already exist, simply insert an function signature
// identical to SF into the dest module...
Function *NewDF = new Function(SF->getFunctionType(), SF->getLinkage(),
SF->getName(), Dest);
// If the LLVM runtime renamed the function, but it is an externally
// visible symbol, DF must be an existing function with internal linkage.
// Rename it.
if (NewDF->getName() != SF->getName() && !NewDF->hasInternalLinkage()) {
assert(DF && DF->getName() == SF->getName() &&DF->hasInternalLinkage());
DF->setName("");
NewDF->setName(SF->getName()); // Force the name back
DF->setName(SF->getName()); // This will cause a renaming
assert(NewDF->getName() == SF->getName() &&
DF->getName() != SF->getName());
}
// ... and remember this mapping...
ValueMap.insert(std::make_pair(SF, NewDF));
} else if (SF->isExternal()) {
// If SF is external or if both SF & DF are external.. Just link the
// external functions, we aren't adding anything.
ValueMap.insert(std::make_pair(SF, DF));
} else if (DF->isExternal()) { // If DF is external but SF is not...
// Link the external functions, update linkage qualifiers
ValueMap.insert(std::make_pair(SF, DF));
DF->setLinkage(SF->getLinkage());
} else if (SF->hasWeakLinkage() || SF->hasLinkOnceLinkage()) {
// At this point we know that DF has LinkOnce, Weak, or External linkage.
ValueMap.insert(std::make_pair(SF, DF));
// Linkonce+Weak = Weak
if (DF->hasLinkOnceLinkage() && SF->hasWeakLinkage())
DF->setLinkage(SF->getLinkage());
} else if (DF->hasWeakLinkage() || DF->hasLinkOnceLinkage()) {
// At this point we know that SF has LinkOnce or External linkage.
ValueMap.insert(std::make_pair(SF, DF));
if (!SF->hasLinkOnceLinkage()) // Don't inherit linkonce linkage
DF->setLinkage(SF->getLinkage());
} else if (SF->getLinkage() != DF->getLinkage()) {
return Error(Err, "Functions named '" + SF->getName() +
"' have different linkage specifiers!");
} else if (SF->hasExternalLinkage()) {
// The function is defined in both modules!!
return Error(Err, "Function '" +
SF->getFunctionType()->getDescription() + "':\"" +
SF->getName() + "\" - Function is already defined!");
} else {
assert(0 && "Unknown linkage configuration found!");
}
}
return false;
}
// LinkFunctionBody - Copy the source function over into the dest function and
// fix up references to values. At this point we know that Dest is an external
// function, and that Src is not.
//
static bool LinkFunctionBody(Function *Dest, const Function *Src,
std::map<const Value*, Value*> &GlobalMap,
std::string *Err) {
assert(Src && Dest && Dest->isExternal() && !Src->isExternal());
std::map<const Value*, Value*> LocalMap; // Map for function local values
// Go through and convert function arguments over...
Function::aiterator DI = Dest->abegin();
for (Function::const_aiterator I = Src->abegin(), E = Src->aend();
I != E; ++I, ++DI) {
DI->setName(I->getName()); // Copy the name information over...
// Add a mapping to our local map
LocalMap.insert(std::make_pair(I, DI));
}
// Loop over all of the basic blocks, copying the instructions over...
//
for (Function::const_iterator I = Src->begin(), E = Src->end(); I != E; ++I) {
// Create new basic block and add to mapping and the Dest function...
BasicBlock *DBB = new BasicBlock(I->getName(), Dest);
LocalMap.insert(std::make_pair(I, DBB));
// Loop over all of the instructions in the src basic block, copying them
// over. Note that this is broken in a strict sense because the cloned
// instructions will still be referencing values in the Src module, not
// the remapped values. In our case, however, we will not get caught and
// so we can delay patching the values up until later...
//
for (BasicBlock::const_iterator II = I->begin(), IE = I->end();
II != IE; ++II) {
Instruction *DI = II->clone();
DI->setName(II->getName());
DBB->getInstList().push_back(DI);
LocalMap.insert(std::make_pair(II, DI));
}
}
// At this point, all of the instructions and values of the function are now
// copied over. The only problem is that they are still referencing values in
// the Source function as operands. Loop through all of the operands of the
// functions and patch them up to point to the local versions...
//
for (Function::iterator BB = Dest->begin(), BE = Dest->end(); BB != BE; ++BB)
for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
for (Instruction::op_iterator OI = I->op_begin(), OE = I->op_end();
OI != OE; ++OI)
*OI = RemapOperand(*OI, LocalMap, &GlobalMap);
return false;
}
// LinkFunctionBodies - Link in the function bodies that are defined in the
// source module into the DestModule. This consists basically of copying the
// function over and fixing up references to values.
//
static bool LinkFunctionBodies(Module *Dest, const Module *Src,
std::map<const Value*, Value*> &ValueMap,
std::string *Err) {
// Loop over all of the functions in the src module, mapping them over as we
// go
//
for (Module::const_iterator SF = Src->begin(), E = Src->end(); SF != E; ++SF){
if (!SF->isExternal()) { // No body if function is external
Function *DF = cast<Function>(ValueMap[SF]); // Destination function
// DF not external SF external?
if (DF->isExternal()) {
// Only provide the function body if there isn't one already.
if (LinkFunctionBody(DF, SF, ValueMap, Err))
return true;
}
}
}
return false;
}
// LinkAppendingVars - If there were any appending global variables, link them
// together now. Return true on error.
//
static bool LinkAppendingVars(Module *M,
std::multimap<std::string, GlobalVariable *> &AppendingVars,
std::string *ErrorMsg) {
if (AppendingVars.empty()) return false; // Nothing to do.
// Loop over the multimap of appending vars, processing any variables with the
// same name, forming a new appending global variable with both of the
// initializers merged together, then rewrite references to the old variables
// and delete them.
//
std::vector<Constant*> Inits;
while (AppendingVars.size() > 1) {
// Get the first two elements in the map...
std::multimap<std::string,
GlobalVariable*>::iterator Second = AppendingVars.begin(), First=Second++;
// If the first two elements are for different names, there is no pair...
// Otherwise there is a pair, so link them together...
if (First->first == Second->first) {
GlobalVariable *G1 = First->second, *G2 = Second->second;
const ArrayType *T1 = cast<ArrayType>(G1->getType()->getElementType());
const ArrayType *T2 = cast<ArrayType>(G2->getType()->getElementType());
// Check to see that they two arrays agree on type...
if (T1->getElementType() != T2->getElementType())
return Error(ErrorMsg,
"Appending variables with different element types need to be linked!");
if (G1->isConstant() != G2->isConstant())
return Error(ErrorMsg,
"Appending variables linked with different const'ness!");
unsigned NewSize = T1->getNumElements() + T2->getNumElements();
ArrayType *NewType = ArrayType::get(T1->getElementType(), NewSize);
// Create the new global variable...
GlobalVariable *NG =
new GlobalVariable(NewType, G1->isConstant(), G1->getLinkage(),
/*init*/0, First->first, M);
// Merge the initializer...
Inits.reserve(NewSize);
if (ConstantArray *I = dyn_cast<ConstantArray>(G1->getInitializer())) {
for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i)
Inits.push_back(cast<Constant>(I->getValues()[i]));
} else {
assert(isa<ConstantAggregateZero>(G1->getInitializer()));
Constant *CV = Constant::getNullValue(T1->getElementType());
for (unsigned i = 0, e = T1->getNumElements(); i != e; ++i)
Inits.push_back(CV);
}
if (ConstantArray *I = dyn_cast<ConstantArray>(G2->getInitializer())) {
for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i)
Inits.push_back(cast<Constant>(I->getValues()[i]));
} else {
assert(isa<ConstantAggregateZero>(G2->getInitializer()));
Constant *CV = Constant::getNullValue(T2->getElementType());
for (unsigned i = 0, e = T2->getNumElements(); i != e; ++i)
Inits.push_back(CV);
}
NG->setInitializer(ConstantArray::get(NewType, Inits));
Inits.clear();
// Replace any uses of the two global variables with uses of the new
// global...
// FIXME: This should rewrite simple/straight-forward uses such as
// getelementptr instructions to not use the Cast!
G1->replaceAllUsesWith(ConstantExpr::getCast(NG, G1->getType()));
G2->replaceAllUsesWith(ConstantExpr::getCast(NG, G2->getType()));
// Remove the two globals from the module now...
M->getGlobalList().erase(G1);
M->getGlobalList().erase(G2);
// Put the new global into the AppendingVars map so that we can handle
// linking of more than two vars...
Second->second = NG;
}
AppendingVars.erase(First);
}
return false;
}
// LinkModules - This function links two modules together, with the resulting
// left module modified to be the composite of the two input modules. If an
// error occurs, true is returned and ErrorMsg (if not null) is set to indicate
// the problem. Upon failure, the Dest module could be in a modified state, and
// shouldn't be relied on to be consistent.
//
bool llvm::LinkModules(Module *Dest, const Module *Src, std::string *ErrorMsg) {
if (Dest->getEndianness() == Module::AnyEndianness)
Dest->setEndianness(Src->getEndianness());
if (Dest->getPointerSize() == Module::AnyPointerSize)
Dest->setPointerSize(Src->getPointerSize());
if (Src->getEndianness() != Module::AnyEndianness &&
Dest->getEndianness() != Src->getEndianness())
std::cerr << "WARNING: Linking two modules of different endianness!\n";
if (Src->getPointerSize() != Module::AnyPointerSize &&
Dest->getPointerSize() != Src->getPointerSize())
std::cerr << "WARNING: Linking two modules of different pointer size!\n";
// LinkTypes - Go through the symbol table of the Src module and see if any
// types are named in the src module that are not named in the Dst module.
// Make sure there are no type name conflicts.
//
if (LinkTypes(Dest, Src, ErrorMsg)) return true;
// ValueMap - Mapping of values from what they used to be in Src, to what they
// are now in Dest.
//
std::map<const Value*, Value*> ValueMap;
// AppendingVars - Keep track of global variables in the destination module
// with appending linkage. After the module is linked together, they are
// appended and the module is rewritten.
//
std::multimap<std::string, GlobalVariable *> AppendingVars;
// Add all of the appending globals already in the Dest module to
// AppendingVars.
for (Module::giterator I = Dest->gbegin(), E = Dest->gend(); I != E; ++I)
if (I->hasAppendingLinkage())
AppendingVars.insert(std::make_pair(I->getName(), I));
// Insert all of the globals in src into the Dest module... without linking
// initializers (which could refer to functions not yet mapped over).
//
if (LinkGlobals(Dest, Src, ValueMap, AppendingVars, ErrorMsg)) return true;
// Link the functions together between the two modules, without doing function
// bodies... this just adds external function prototypes to the Dest
// function... We do this so that when we begin processing function bodies,
// all of the global values that may be referenced are available in our
// ValueMap.
//
if (LinkFunctionProtos(Dest, Src, ValueMap, ErrorMsg)) return true;
// Update the initializers in the Dest module now that all globals that may
// be referenced are in Dest.
//
if (LinkGlobalInits(Dest, Src, ValueMap, ErrorMsg)) return true;
// Link in the function bodies that are defined in the source module into the
// DestModule. This consists basically of copying the function over and
// fixing up references to values.
//
if (LinkFunctionBodies(Dest, Src, ValueMap, ErrorMsg)) return true;
// If there were any appending global variables, link them together now.
//
if (LinkAppendingVars(Dest, AppendingVars, ErrorMsg)) return true;
return false;
}
// vim: sw=2
Property changes on: llvm/trunk/lib/VMCore/Linker.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.74
\ No newline at end of property
+1.75
\ No newline at end of property
Index: llvm/trunk/lib/Transforms/Instrumentation/TraceBasicBlocks.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Instrumentation/TraceBasicBlocks.cpp (revision 15333)
+++ llvm/trunk/lib/Transforms/Instrumentation/TraceBasicBlocks.cpp (revision 15334)
@@ -1,76 +1,74 @@
//===- TraceBasicBlocks.cpp - Insert basic-block trace instrumentation ----===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This pass instruments the specified program with calls into a runtime
// library that cause it to output a trace of basic blocks as a side effect
// of normal execution.
//
//===----------------------------------------------------------------------===//
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
-#include "llvm/iOther.h"
-#include "llvm/iMemory.h"
-#include "llvm/iPHINode.h"
+#include "llvm/Instructions.h"
#include "ProfilingUtils.h"
#include "Support/Debug.h"
#include <set>
using namespace llvm;
namespace {
class TraceBasicBlocks : public Pass {
bool run(Module &M);
};
RegisterOpt<TraceBasicBlocks> X("trace-basic-blocks",
"Insert instrumentation for basic block tracing");
}
static void InsertInstrumentationCall (BasicBlock *BB,
const std::string FnName,
unsigned BBNumber) {
DEBUG (std::cerr << "InsertInstrumentationCall (\"" << BB->getName ()
<< "\", \"" << FnName << "\", " << BBNumber << ")\n");
Module &M = *BB->getParent ()->getParent ();
Function *InstrFn = M.getOrInsertFunction (FnName, Type::VoidTy,
Type::UIntTy, 0);
std::vector<Value*> Args (1);
Args[0] = ConstantUInt::get (Type::UIntTy, BBNumber);
// Insert the call after any alloca or PHI instructions...
BasicBlock::iterator InsertPos = BB->begin();
while (isa<AllocaInst>(InsertPos) || isa<PHINode>(InsertPos))
++InsertPos;
Instruction *InstrCall = new CallInst (InstrFn, Args, "", InsertPos);
}
bool TraceBasicBlocks::run(Module &M) {
Function *Main = M.getMainFunction();
if (Main == 0) {
std::cerr << "WARNING: cannot insert basic-block trace instrumentation"
<< " into a module with no main function!\n";
return false; // No main, no instrumentation!
}
unsigned BBNumber = 0;
for (Module::iterator F = M.begin(), E = M.end(); F != E; ++F)
for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) {
InsertInstrumentationCall (BB, "llvm_trace_basic_block", BBNumber);
++BBNumber;
}
// Add the initialization call to main.
InsertProfilingInitCall(Main, "llvm_start_basic_block_tracing");
return true;
}
Property changes on: llvm/trunk/lib/Transforms/Instrumentation/TraceBasicBlocks.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.6
\ No newline at end of property
+1.7
\ No newline at end of property
Index: llvm/trunk/lib/Transforms/Instrumentation/TraceValues.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Instrumentation/TraceValues.cpp (revision 15333)
+++ llvm/trunk/lib/Transforms/Instrumentation/TraceValues.cpp (revision 15334)
@@ -1,436 +1,434 @@
//===- TraceValues.cpp - Value Tracing for debugging ----------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Support for inserting LLVM code to print values at basic block and function
// exits.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Instrumentation.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
-#include "llvm/iMemory.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include "llvm/Module.h"
#include "llvm/Pass.h"
#include "llvm/Assembly/Writer.h"
#include "Support/CommandLine.h"
#include "Support/StringExtras.h"
#include <algorithm>
#include <sstream>
using namespace llvm;
static cl::opt<bool>
DisablePtrHashing("tracedisablehashdisable", cl::Hidden,
cl::desc("Disable pointer hashing in the -trace or -tracem "
"passes"));
static cl::list<std::string>
TraceFuncNames("tracefunc", cl::desc("Only trace specific functions in the "
"-trace or -tracem passes"),
cl::value_desc("function"), cl::Hidden);
static void TraceValuesAtBBExit(BasicBlock *BB,
Function *Printf, Function* HashPtrToSeqNum,
std::vector<Instruction*> *valuesStoredInFunction);
// We trace a particular function if no functions to trace were specified
// or if the function is in the specified list.
//
inline static bool
TraceThisFunction(Function &F)
{
if (TraceFuncNames.empty()) return true;
return std::find(TraceFuncNames.begin(), TraceFuncNames.end(), F.getName())
!= TraceFuncNames.end();
}
namespace {
struct ExternalFuncs {
Function *PrintfFunc, *HashPtrFunc, *ReleasePtrFunc;
Function *RecordPtrFunc, *PushOnEntryFunc, *ReleaseOnReturnFunc;
void doInitialization(Module &M); // Add prototypes for external functions
};
class InsertTraceCode : public FunctionPass {
protected:
ExternalFuncs externalFuncs;
public:
// Add a prototype for runtime functions not already in the program.
//
bool doInitialization(Module &M);
//--------------------------------------------------------------------------
// Function InsertCodeToTraceValues
//
// Inserts tracing code for all live values at basic block and/or function
// exits as specified by `traceBasicBlockExits' and `traceFunctionExits'.
//
bool doit(Function *M);
virtual void handleBasicBlock(BasicBlock *BB,
std::vector<Instruction*> &VI) = 0;
// runOnFunction - This method does the work.
//
bool runOnFunction(Function &F);
virtual void getAnalysisUsage(AnalysisUsage &AU) const {
AU.setPreservesCFG();
}
};
struct FunctionTracer : public InsertTraceCode {
// Ignore basic blocks here...
virtual void handleBasicBlock(BasicBlock *BB,
std::vector<Instruction*> &VI) {}
};
struct BasicBlockTracer : public InsertTraceCode {
// Trace basic blocks here...
virtual void handleBasicBlock(BasicBlock *BB,
std::vector<Instruction*> &VI) {
TraceValuesAtBBExit(BB, externalFuncs.PrintfFunc,
externalFuncs.HashPtrFunc, &VI);
}
};
// Register the passes...
RegisterOpt<FunctionTracer> X("tracem","Insert Function trace code only");
RegisterOpt<BasicBlockTracer> Y("trace","Insert BB and Function trace code");
} // end anonymous namespace
Pass *llvm::createTraceValuesPassForFunction() { // Just trace functions
return new FunctionTracer();
}
Pass *llvm::createTraceValuesPassForBasicBlocks() { // Trace BB's and functions
return new BasicBlockTracer();
}
// Add a prototype for external functions used by the tracing code.
//
void ExternalFuncs::doInitialization(Module &M) {
const Type *SBP = PointerType::get(Type::SByteTy);
const FunctionType *MTy =
FunctionType::get(Type::IntTy, std::vector<const Type*>(1, SBP), true);
PrintfFunc = M.getOrInsertFunction("printf", MTy);
// uint (sbyte*)
HashPtrFunc = M.getOrInsertFunction("HashPointerToSeqNum", Type::UIntTy, SBP,
0);
// void (sbyte*)
ReleasePtrFunc = M.getOrInsertFunction("ReleasePointerSeqNum",
Type::VoidTy, SBP, 0);
RecordPtrFunc = M.getOrInsertFunction("RecordPointer",
Type::VoidTy, SBP, 0);
PushOnEntryFunc = M.getOrInsertFunction("PushPointerSet", Type::VoidTy, 0);
ReleaseOnReturnFunc = M.getOrInsertFunction("ReleasePointersPopSet",
Type::VoidTy, 0);
}
// Add a prototype for external functions used by the tracing code.
//
bool InsertTraceCode::doInitialization(Module &M) {
externalFuncs.doInitialization(M);
return false;
}
static inline GlobalVariable *getStringRef(Module *M, const std::string &str) {
// Create a constant internal string reference...
Constant *Init = ConstantArray::get(str);
// Create the global variable and record it in the module
// The GV will be renamed to a unique name if needed.
GlobalVariable *GV = new GlobalVariable(Init->getType(), true,
GlobalValue::InternalLinkage, Init,
"trstr");
M->getGlobalList().push_back(GV);
return GV;
}
//
// Check if this instruction has any uses outside its basic block,
// or if it used by either a Call or Return instruction (ditto).
// (Values stored to memory within this BB are live at end of BB but are
// traced at the store instruction, not where they are computed.)
//
static inline bool LiveAtBBExit(const Instruction* I) {
const BasicBlock *BB = I->getParent();
for (Value::use_const_iterator U = I->use_begin(); U != I->use_end(); ++U)
if (const Instruction *UI = dyn_cast<Instruction>(*U))
if (UI->getParent() != BB || isa<ReturnInst>(UI))
return true;
return false;
}
static inline bool TraceThisOpCode(unsigned opCode) {
// Explicitly test for opCodes *not* to trace so that any new opcodes will
// be traced by default (VoidTy's are already excluded)
//
return (opCode < Instruction::OtherOpsBegin &&
opCode != Instruction::Alloca &&
opCode != Instruction::PHI &&
opCode != Instruction::Cast);
}
// Trace a value computed by an instruction if it is non-void, it is computed
// by a real computation, not just a copy (see TraceThisOpCode), and
// -- it is a load instruction: we want to check values read from memory
// -- or it is live at exit from the basic block (i.e., ignore local temps)
//
static bool ShouldTraceValue(const Instruction *I) {
return
I->getType() != Type::VoidTy &&
TraceThisOpCode(I->getOpcode()) &&
(isa<LoadInst>(I) || LiveAtBBExit(I));
}
static std::string getPrintfCodeFor(const Value *V) {
if (V == 0) return "";
if (V->getType()->isFloatingPoint())
return "%g";
else if (V->getType() == Type::LabelTy)
return "0x%p";
else if (isa<PointerType>(V->getType()))
return DisablePtrHashing ? "0x%p" : "%d";
else if (V->getType()->isIntegral())
return "%d";
assert(0 && "Illegal value to print out...");
return "";
}
static void InsertPrintInst(Value *V, BasicBlock *BB, Instruction *InsertBefore,
std::string Message,
Function *Printf, Function* HashPtrToSeqNum) {
// Escape Message by replacing all % characters with %% chars.
std::string Tmp;
std::swap(Tmp, Message);
std::string::iterator I = std::find(Tmp.begin(), Tmp.end(), '%');
while (I != Tmp.end()) {
Message.append(Tmp.begin(), I);
Message += "%%";
++I; // Make sure to erase the % as well...
Tmp.erase(Tmp.begin(), I);
I = std::find(Tmp.begin(), Tmp.end(), '%');
}
Message += Tmp;
Module *Mod = BB->getParent()->getParent();
// Turn the marker string into a global variable...
GlobalVariable *fmtVal = getStringRef(Mod, Message+getPrintfCodeFor(V)+"\n");
// Turn the format string into an sbyte *
Constant *GEP=ConstantExpr::getGetElementPtr(fmtVal,
std::vector<Constant*>(2,Constant::getNullValue(Type::LongTy)));
// Insert a call to the hash function if this is a pointer value
if (V && isa<PointerType>(V->getType()) && !DisablePtrHashing) {
const Type *SBP = PointerType::get(Type::SByteTy);
if (V->getType() != SBP) // Cast pointer to be sbyte*
V = new CastInst(V, SBP, "Hash_cast", InsertBefore);
std::vector<Value*> HashArgs(1, V);
V = new CallInst(HashPtrToSeqNum, HashArgs, "ptrSeqNum", InsertBefore);
}
// Insert the first print instruction to print the string flag:
std::vector<Value*> PrintArgs;
PrintArgs.push_back(GEP);
if (V) PrintArgs.push_back(V);
new CallInst(Printf, PrintArgs, "trace", InsertBefore);
}
static void InsertVerbosePrintInst(Value *V, BasicBlock *BB,
Instruction *InsertBefore,
const std::string &Message, Function *Printf,
Function* HashPtrToSeqNum) {
std::ostringstream OutStr;
if (V) WriteAsOperand(OutStr, V);
InsertPrintInst(V, BB, InsertBefore, Message+OutStr.str()+" = ",
Printf, HashPtrToSeqNum);
}
static void
InsertReleaseInst(Value *V, BasicBlock *BB,
Instruction *InsertBefore,
Function* ReleasePtrFunc) {
const Type *SBP = PointerType::get(Type::SByteTy);
if (V->getType() != SBP) // Cast pointer to be sbyte*
V = new CastInst(V, SBP, "RPSN_cast", InsertBefore);
std::vector<Value*> releaseArgs(1, V);
new CallInst(ReleasePtrFunc, releaseArgs, "", InsertBefore);
}
static void
InsertRecordInst(Value *V, BasicBlock *BB,
Instruction *InsertBefore,
Function* RecordPtrFunc) {
const Type *SBP = PointerType::get(Type::SByteTy);
if (V->getType() != SBP) // Cast pointer to be sbyte*
V = new CastInst(V, SBP, "RP_cast", InsertBefore);
std::vector<Value*> releaseArgs(1, V);
new CallInst(RecordPtrFunc, releaseArgs, "", InsertBefore);
}
// Look for alloca and free instructions. These are the ptrs to release.
// Release the free'd pointers immediately. Record the alloca'd pointers
// to be released on return from the current function.
//
static void
ReleasePtrSeqNumbers(BasicBlock *BB,
ExternalFuncs& externalFuncs) {
for (BasicBlock::iterator II=BB->begin(), IE = BB->end(); II != IE; ++II)
if (FreeInst *FI = dyn_cast<FreeInst>(II))
InsertReleaseInst(FI->getOperand(0), BB, FI,externalFuncs.ReleasePtrFunc);
else if (AllocaInst *AI = dyn_cast<AllocaInst>(II))
InsertRecordInst(AI, BB, AI->getNext(), externalFuncs.RecordPtrFunc);
}
// Insert print instructions at the end of basic block BB for each value
// computed in BB that is live at the end of BB,
// or that is stored to memory in BB.
// If the value is stored to memory, we load it back before printing it
// We also return all such loaded values in the vector valuesStoredInFunction
// for printing at the exit from the function. (Note that in each invocation
// of the function, this will only get the last value stored for each static
// store instruction).
//
static void TraceValuesAtBBExit(BasicBlock *BB,
Function *Printf, Function* HashPtrToSeqNum,
std::vector<Instruction*> *valuesStoredInFunction) {
// Get an iterator to point to the insertion location, which is
// just before the terminator instruction.
//
TerminatorInst *InsertPos = BB->getTerminator();
std::ostringstream OutStr;
WriteAsOperand(OutStr, BB, false);
InsertPrintInst(0, BB, InsertPos, "LEAVING BB:" + OutStr.str(),
Printf, HashPtrToSeqNum);
// Insert a print instruction for each instruction preceding InsertPos.
// The print instructions must go before InsertPos, so we use the
// instruction *preceding* InsertPos to check when to terminate the loop.
//
for (BasicBlock::iterator II = BB->begin(); &*II != InsertPos; ++II) {
if (StoreInst *SI = dyn_cast<StoreInst>(II)) {
// Trace the stored value and address
InsertVerbosePrintInst(SI->getOperand(0), BB, InsertPos,
" (store value) ", Printf, HashPtrToSeqNum);
InsertVerbosePrintInst(SI->getOperand(1), BB, InsertPos,
" (store addr ) ", Printf, HashPtrToSeqNum);
}
else if (ShouldTraceValue(II))
InsertVerbosePrintInst(II, BB, InsertPos, " ", Printf, HashPtrToSeqNum);
}
}
static inline void InsertCodeToShowFunctionEntry(Function &F, Function *Printf,
Function* HashPtrToSeqNum){
// Get an iterator to point to the insertion location
BasicBlock &BB = F.getEntryBlock();
Instruction *InsertPos = BB.begin();
std::ostringstream OutStr;
WriteAsOperand(OutStr, &F);
InsertPrintInst(0, &BB, InsertPos, "ENTERING FUNCTION: " + OutStr.str(),
Printf, HashPtrToSeqNum);
// Now print all the incoming arguments
unsigned ArgNo = 0;
for (Function::aiterator I = F.abegin(), E = F.aend(); I != E; ++I, ++ArgNo){
InsertVerbosePrintInst(I, &BB, InsertPos,
" Arg #" + utostr(ArgNo) + ": ", Printf,
HashPtrToSeqNum);
}
}
static inline void InsertCodeToShowFunctionExit(BasicBlock *BB,
Function *Printf,
Function* HashPtrToSeqNum) {
// Get an iterator to point to the insertion location
ReturnInst *Ret = cast<ReturnInst>(BB->getTerminator());
std::ostringstream OutStr;
WriteAsOperand(OutStr, BB->getParent(), true);
InsertPrintInst(0, BB, Ret, "LEAVING FUNCTION: " + OutStr.str(),
Printf, HashPtrToSeqNum);
// print the return value, if any
if (BB->getParent()->getReturnType() != Type::VoidTy)
InsertPrintInst(Ret->getReturnValue(), BB, Ret, " Returning: ",
Printf, HashPtrToSeqNum);
}
bool InsertTraceCode::runOnFunction(Function &F) {
if (!TraceThisFunction(F))
return false;
std::vector<Instruction*> valuesStoredInFunction;
std::vector<BasicBlock*> exitBlocks;
// Insert code to trace values at function entry
InsertCodeToShowFunctionEntry(F, externalFuncs.PrintfFunc,
externalFuncs.HashPtrFunc);
// Push a pointer set for recording alloca'd pointers at entry.
if (!DisablePtrHashing)
new CallInst(externalFuncs.PushOnEntryFunc, std::vector<Value*>(), "",
F.getEntryBlock().begin());
for (Function::iterator BB = F.begin(); BB != F.end(); ++BB) {
if (isa<ReturnInst>(BB->getTerminator()))
exitBlocks.push_back(BB); // record this as an exit block
// Insert trace code if this basic block is interesting...
handleBasicBlock(BB, valuesStoredInFunction);
if (!DisablePtrHashing) // release seq. numbers on free/ret
ReleasePtrSeqNumbers(BB, externalFuncs);
}
for (unsigned i=0; i != exitBlocks.size(); ++i)
{
// Insert code to trace values at function exit
InsertCodeToShowFunctionExit(exitBlocks[i], externalFuncs.PrintfFunc,
externalFuncs.HashPtrFunc);
// Release all recorded pointers before RETURN. Do this LAST!
if (!DisablePtrHashing)
new CallInst(externalFuncs.ReleaseOnReturnFunc, std::vector<Value*>(),
"", exitBlocks[i]->getTerminator());
}
return true;
}
Property changes on: llvm/trunk/lib/Transforms/Instrumentation/TraceValues.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.67
\ No newline at end of property
+1.68
\ No newline at end of property
Index: llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp (revision 15333)
+++ llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp (revision 15334)
@@ -1,372 +1,368 @@
//===-- EdgeCode.cpp - generate LLVM instrumentation code -----------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//It implements the class EdgeCode: which provides
//support for inserting "appropriate" instrumentation at
//designated points in the graph
//
//It also has methods to insert initialization code in
//top block of cfg
//===----------------------------------------------------------------------===//
#include "Graph.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
-#include "llvm/iMemory.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iOther.h"
-#include "llvm/iOperators.h"
-#include "llvm/iPHINode.h"
+#include "llvm/Instructions.h"
#include "llvm/Module.h"
#define INSERT_LOAD_COUNT
#define INSERT_STORE
using std::vector;
namespace llvm {
static void getTriggerCode(Module *M, BasicBlock *BB, int MethNo, Value *pathNo,
Value *cnt, Instruction *rInst){
vector<Value *> tmpVec;
tmpVec.push_back(Constant::getNullValue(Type::LongTy));
tmpVec.push_back(Constant::getNullValue(Type::LongTy));
Instruction *Idx = new GetElementPtrInst(cnt, tmpVec, "");//,
BB->getInstList().push_back(Idx);
const Type *PIntTy = PointerType::get(Type::IntTy);
Function *trigMeth = M->getOrInsertFunction("trigger", Type::VoidTy,
Type::IntTy, Type::IntTy,
PIntTy, PIntTy, 0);
assert(trigMeth && "trigger method could not be inserted!");
vector<Value *> trargs;
trargs.push_back(ConstantSInt::get(Type::IntTy,MethNo));
trargs.push_back(pathNo);
trargs.push_back(Idx);
trargs.push_back(rInst);
Instruction *callInst=new CallInst(trigMeth, trargs, "");//, BB->begin());
BB->getInstList().push_back(callInst);
//triggerInst = new CallInst(trigMeth, trargs, "");//, InsertPos);
}
//get the code to be inserted on the edge
//This is determined from cond (1-6)
void getEdgeCode::getCode(Instruction *rInst, Value *countInst,
Function *M, BasicBlock *BB,
vector<Value *> &retVec){
//Instruction *InsertPos = BB->getInstList().begin();
//now check for cdIn and cdOut
//first put cdOut
if(cdOut!=NULL){
cdOut->getCode(rInst, countInst, M, BB, retVec);
}
if(cdIn!=NULL){
cdIn->getCode(rInst, countInst, M, BB, retVec);
}
//case: r=k code to be inserted
switch(cond){
case 1:{
Value *val=ConstantSInt::get(Type::IntTy,inc);
#ifdef INSERT_STORE
Instruction *stInst=new StoreInst(val, rInst);//, InsertPos);
BB->getInstList().push_back(stInst);
#endif
break;
}
//case: r=0 to be inserted
case 2:{
#ifdef INSERT_STORE
Instruction *stInst = new StoreInst(ConstantSInt::getNullValue(Type::IntTy), rInst);//, InsertPos);
BB->getInstList().push_back(stInst);
#endif
break;
}
//r+=k
case 3:{
Instruction *ldInst = new LoadInst(rInst, "ti1");//, InsertPos);
BB->getInstList().push_back(ldInst);
Value *val = ConstantSInt::get(Type::IntTy,inc);
Instruction *addIn = BinaryOperator::create(Instruction::Add, ldInst, val,
"ti2");//, InsertPos);
BB->getInstList().push_back(addIn);
#ifdef INSERT_STORE
Instruction *stInst = new StoreInst(addIn, rInst);//, InsertPos);
BB->getInstList().push_back(stInst);
#endif
break;
}
//count[inc]++
case 4:{
vector<Value *> tmpVec;
tmpVec.push_back(Constant::getNullValue(Type::LongTy));
tmpVec.push_back(ConstantSInt::get(Type::LongTy, inc));
Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//,
//Instruction *Idx = new GetElementPtrInst(countInst,
// vector<Value*>(1,ConstantSInt::get(Type::LongTy, inc)),
// "");//, InsertPos);
BB->getInstList().push_back(Idx);
Instruction *ldInst=new LoadInst(Idx, "ti1");//, InsertPos);
BB->getInstList().push_back(ldInst);
Value *val = ConstantSInt::get(Type::IntTy, 1);
//Instruction *addIn =
Instruction *newCount =
BinaryOperator::create(Instruction::Add, ldInst, val,"ti2");
BB->getInstList().push_back(newCount);
#ifdef INSERT_STORE
//Instruction *stInst=new StoreInst(addIn, Idx, InsertPos);
Instruction *stInst=new StoreInst(newCount, Idx);//, InsertPos);
BB->getInstList().push_back(stInst);
#endif
Value *trAddIndex = ConstantSInt::get(Type::IntTy,inc);
retVec.push_back(newCount);
retVec.push_back(trAddIndex);
//insert trigger
//getTriggerCode(M->getParent(), BB, MethNo,
// ConstantSInt::get(Type::IntTy,inc), newCount, triggerInst);
//end trigger code
assert(inc>=0 && "IT MUST BE POSITIVE NOW");
break;
}
//case: count[r+inc]++
case 5:{
//ti1=inc+r
Instruction *ldIndex=new LoadInst(rInst, "ti1");//, InsertPos);
BB->getInstList().push_back(ldIndex);
Value *val=ConstantSInt::get(Type::IntTy,inc);
Instruction *addIndex=BinaryOperator::
create(Instruction::Add, ldIndex, val,"ti2");//, InsertPos);
BB->getInstList().push_back(addIndex);
//now load count[addIndex]
Instruction *castInst=new CastInst(addIndex,
Type::LongTy,"ctin");//, InsertPos);
BB->getInstList().push_back(castInst);
vector<Value *> tmpVec;
tmpVec.push_back(Constant::getNullValue(Type::LongTy));
tmpVec.push_back(castInst);
Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//,
// InsertPos);
BB->getInstList().push_back(Idx);
Instruction *ldInst=new LoadInst(Idx, "ti3");//, InsertPos);
BB->getInstList().push_back(ldInst);
Value *cons=ConstantSInt::get(Type::IntTy,1);
//count[addIndex]++
//std::cerr<<"Type ldInst:"<<ldInst->getType()<<"\t cons:"<<cons->getType()<<"\n";
Instruction *newCount = BinaryOperator::create(Instruction::Add, ldInst,
cons,"");
BB->getInstList().push_back(newCount);
#ifdef INSERT_STORE
Instruction *stInst = new StoreInst(newCount, Idx);//, InsertPos);
BB->getInstList().push_back(stInst);
#endif
retVec.push_back(newCount);
retVec.push_back(addIndex);
//insert trigger
//getTriggerCode(M->getParent(), BB, MethNo, addIndex, newCount, triggerInst);
//end trigger code
break;
}
//case: count[r]+
case 6:{
//ti1=inc+r
Instruction *ldIndex=new LoadInst(rInst, "ti1");//, InsertPos);
BB->getInstList().push_back(ldIndex);
//now load count[addIndex]
Instruction *castInst2=new CastInst(ldIndex, Type::LongTy,"ctin");
BB->getInstList().push_back(castInst2);
vector<Value *> tmpVec;
tmpVec.push_back(Constant::getNullValue(Type::LongTy));
tmpVec.push_back(castInst2);
Instruction *Idx = new GetElementPtrInst(countInst, tmpVec, "");//,
//Instruction *Idx = new GetElementPtrInst(countInst,
// vector<Value*>(1,castInst2), "");
BB->getInstList().push_back(Idx);
Instruction *ldInst=new LoadInst(Idx, "ti2");//, InsertPos);
BB->getInstList().push_back(ldInst);
Value *cons=ConstantSInt::get(Type::IntTy,1);
//count[addIndex]++
Instruction *newCount = BinaryOperator::create(Instruction::Add, ldInst,
cons,"ti3");
BB->getInstList().push_back(newCount);
#ifdef INSERT_STORE
Instruction *stInst = new StoreInst(newCount, Idx);//, InsertPos);
BB->getInstList().push_back(stInst);
#endif
retVec.push_back(newCount);
retVec.push_back(ldIndex);
break;
}
}
}
//Insert the initialization code in the top BB
//this includes initializing r, and count
//r is like an accumulator, that
//keeps on adding increments as we traverse along a path
//and at the end of the path, r contains the path
//number of that path
//Count is an array, where Count[k] represents
//the number of executions of path k
void insertInTopBB(BasicBlock *front,
int k,
Instruction *rVar, Value *threshold){
//rVar is variable r,
//countVar is count[]
Value *Int0 = ConstantInt::get(Type::IntTy, 0);
//now push all instructions in front of the BB
BasicBlock::iterator here=front->begin();
front->getInstList().insert(here, rVar);
//front->getInstList().insert(here,countVar);
//Initialize Count[...] with 0
//for (int i=0;i<k; i++){
//Value *GEP2 = new GetElementPtrInst(countVar,
// vector<Value *>(1,ConstantSInt::get(Type::LongTy, i)),
// "", here);
//new StoreInst(Int0, GEP2, here);
//}
//store uint 0, uint *%R
new StoreInst(Int0, rVar, here);
}
//insert a basic block with appropriate code
//along a given edge
void insertBB(Edge ed,
getEdgeCode *edgeCode,
Instruction *rInst,
Value *countInst,
int numPaths, int Methno, Value *threshold){
BasicBlock* BB1=ed.getFirst()->getElement();
BasicBlock* BB2=ed.getSecond()->getElement();
#ifdef DEBUG_PATH_PROFILES
//debugging info
cerr<<"Edges with codes ######################\n";
cerr<<BB1->getName()<<"->"<<BB2->getName()<<"\n";
cerr<<"########################\n";
#endif
//We need to insert a BB between BB1 and BB2
TerminatorInst *TI=BB1->getTerminator();
BasicBlock *newBB=new BasicBlock("counter", BB1->getParent());
//get code for the new BB
vector<Value *> retVec;
edgeCode->getCode(rInst, countInst, BB1->getParent(), newBB, retVec);
BranchInst *BI = cast<BranchInst>(TI);
//Is terminator a branch instruction?
//then we need to change branch destinations to include new BB
if(BI->isUnconditional()){
BI->setUnconditionalDest(newBB);
}
else{
if(BI->getSuccessor(0)==BB2)
BI->setSuccessor(0, newBB);
if(BI->getSuccessor(1)==BB2)
BI->setSuccessor(1, newBB);
}
BasicBlock *triggerBB = NULL;
if(retVec.size()>0){
triggerBB = new BasicBlock("trigger", BB1->getParent());
getTriggerCode(BB1->getParent()->getParent(), triggerBB, Methno,
retVec[1], countInst, rInst);//retVec[0]);
//Instruction *castInst = new CastInst(retVec[0], Type::IntTy, "");
Instruction *etr = new LoadInst(threshold, "threshold");
//std::cerr<<"type1: "<<etr->getType()<<" type2: "<<retVec[0]->getType()<<"\n";
Instruction *cmpInst = new SetCondInst(Instruction::SetLE, etr,
retVec[0], "");
Instruction *newBI2 = new BranchInst(triggerBB, BB2, cmpInst);
//newBB->getInstList().push_back(castInst);
newBB->getInstList().push_back(etr);
newBB->getInstList().push_back(cmpInst);
newBB->getInstList().push_back(newBI2);
//triggerBB->getInstList().push_back(triggerInst);
new BranchInst(BB2, 0, 0, triggerBB);
}
else{
new BranchInst(BB2, 0, 0, newBB);
}
//now iterate over BB2, and set its Phi nodes right
for(BasicBlock::iterator BB2Inst = BB2->begin(), BBend = BB2->end();
BB2Inst != BBend; ++BB2Inst){
if(PHINode *phiInst=dyn_cast<PHINode>(BB2Inst)){
int bbIndex=phiInst->getBasicBlockIndex(BB1);
assert(bbIndex>=0);
phiInst->setIncomingBlock(bbIndex, newBB);
///check if trigger!=null, then add value corresponding to it too!
if(retVec.size()>0){
assert(triggerBB && "BasicBlock with trigger should not be null!");
Value *vl = phiInst->getIncomingValue((unsigned int)bbIndex);
phiInst->addIncoming(vl, triggerBB);
}
}
}
}
} // End llvm namespace
Property changes on: llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/EdgeCode.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.27
\ No newline at end of property
+1.28
\ No newline at end of property
Index: llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp (revision 15333)
+++ llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp (revision 15334)
@@ -1,251 +1,249 @@
//===-- ProfilePaths.cpp - interface to insert instrumentation --*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This inserts instrumentation for counting execution of paths though a given
// function Its implemented as a "Function" Pass, and called using opt
//
// This pass is implemented by using algorithms similar to
// 1."Efficient Path Profiling": Ball, T. and Larus, J. R.,
// Proceedings of Micro-29, Dec 1996, Paris, France.
// 2."Efficiently Counting Program events with support for on-line
// "queries": Ball T., ACM Transactions on Programming Languages
// and systems, Sep 1994.
//
// The algorithms work on a Graph constructed over the nodes made from Basic
// Blocks: The transformations then take place on the constructed graph
// (implementation in Graph.cpp and GraphAuxiliary.cpp) and finally, appropriate
// instrumentation is placed over suitable edges. (code inserted through
// EdgeCode.cpp).
//
// The algorithm inserts code such that every acyclic path in the CFG of a
// function is identified through a unique number. the code insertion is optimal
// in the sense that its inserted over a minimal set of edges. Also, the
// algorithm makes sure than initialization, path increment and counter update
// can be collapsed into minimum number of edges.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Utils/UnifyFunctionExitNodes.h"
#include "llvm/Support/CFG.h"
#include "llvm/Constants.h"
#include "llvm/DerivedTypes.h"
-#include "llvm/iMemory.h"
-#include "llvm/iOperators.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include "llvm/Module.h"
#include "Graph.h"
#include <fstream>
#include <cstdio>
namespace llvm {
struct ProfilePaths : public FunctionPass {
bool runOnFunction(Function &F);
// Before this pass, make sure that there is only one
// entry and only one exit node for the function in the CFG of the function
//
void ProfilePaths::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<UnifyFunctionExitNodes>();
}
};
static RegisterOpt<ProfilePaths> X("paths", "Profile Paths");
static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
if(((*si)->getElement())==BB){
return *si;
}
}
return NULL;
}
//Per function pass for inserting counters and trigger code
bool ProfilePaths::runOnFunction(Function &F){
static int mn = -1;
static int CountCounter = 1;
if(F.isExternal()) {
return false;
}
//increment counter for instrumented functions. mn is now function#
mn++;
// Transform the cfg s.t. we have just one exit node
BasicBlock *ExitNode =
getAnalysis<UnifyFunctionExitNodes>().getReturnBlock();
//iterating over BBs and making graph
std::vector<Node *> nodes;
std::vector<Edge> edges;
Node *tmp;
Node *exitNode = 0, *startNode = 0;
// The nodes must be uniquely identified:
// That is, no two nodes must hav same BB*
for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB) {
Node *nd=new Node(BB);
nodes.push_back(nd);
if(&*BB == ExitNode)
exitNode=nd;
if(BB==F.begin())
startNode=nd;
}
// now do it again to insert edges
for (Function::iterator BB = F.begin(), BE = F.end(); BB != BE; ++BB){
Node *nd=findBB(nodes, BB);
assert(nd && "No node for this edge!");
for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){
Node *nd2=findBB(nodes,*s);
assert(nd2 && "No node for this edge!");
Edge ed(nd,nd2,0);
edges.push_back(ed);
}
}
Graph g(nodes,edges, startNode, exitNode);
#ifdef DEBUG_PATH_PROFILES
std::cerr<<"Original graph\n";
printGraph(g);
#endif
BasicBlock *fr = &F.front();
// The graph is made acyclic: this is done
// by removing back edges for now, and adding them later on
std::vector<Edge> be;
std::map<Node *, int> nodePriority; //it ranks nodes in depth first order traversal
g.getBackEdges(be, nodePriority);
#ifdef DEBUG_PATH_PROFILES
std::cerr<<"BackEdges-------------\n";
for (std::vector<Edge>::iterator VI=be.begin(); VI!=be.end(); ++VI){
printEdge(*VI);
cerr<<"\n";
}
std::cerr<<"------\n";
#endif
#ifdef DEBUG_PATH_PROFILES
cerr<<"Backedges:"<<be.size()<<endl;
#endif
//Now we need to reflect the effect of back edges
//This is done by adding dummy edges
//If a->b is a back edge
//Then we add 2 back edges for it:
//1. from root->b (in vector stDummy)
//and 2. from a->exit (in vector exDummy)
std::vector<Edge> stDummy;
std::vector<Edge> exDummy;
addDummyEdges(stDummy, exDummy, g, be);
#ifdef DEBUG_PATH_PROFILES
std::cerr<<"After adding dummy edges\n";
printGraph(g);
#endif
// Now, every edge in the graph is assigned a weight
// This weight later adds on to assign path
// numbers to different paths in the graph
// All paths for now are acyclic,
// since no back edges in the graph now
// numPaths is the number of acyclic paths in the graph
int numPaths=valueAssignmentToEdges(g, nodePriority, be);
//if(numPaths<=1) return false;
static GlobalVariable *threshold = NULL;
static bool insertedThreshold = false;
if(!insertedThreshold){
threshold = new GlobalVariable(Type::IntTy, false,
GlobalValue::ExternalLinkage, 0,
"reopt_threshold");
F.getParent()->getGlobalList().push_back(threshold);
insertedThreshold = true;
}
assert(threshold && "GlobalVariable threshold not defined!");
if(fr->getParent()->getName() == "main"){
//initialize threshold
// FIXME: THIS IS HORRIBLY BROKEN. FUNCTION PASSES CANNOT DO THIS, EXCEPT
// IN THEIR INITIALIZE METHOD!!
Function *initialize =
F.getParent()->getOrInsertFunction("reoptimizerInitialize", Type::VoidTy,
PointerType::get(Type::IntTy), 0);
std::vector<Value *> trargs;
trargs.push_back(threshold);
new CallInst(initialize, trargs, "", fr->begin());
}
if(numPaths<=1 || numPaths >5000) return false;
#ifdef DEBUG_PATH_PROFILES
printGraph(g);
#endif
//create instruction allocation r and count
//r is the variable that'll act like an accumulator
//all along the path, we just add edge values to r
//and at the end, r reflects the path number
//count is an array: count[x] would store
//the number of executions of path numbered x
Instruction *rVar=new
AllocaInst(Type::IntTy,
ConstantUInt::get(Type::UIntTy,1),"R");
//Instruction *countVar=new
//AllocaInst(Type::IntTy,
// ConstantUInt::get(Type::UIntTy, numPaths), "Count");
//initialize counter array!
std::vector<Constant*> arrayInitialize;
for(int xi=0; xi<numPaths; xi++)
arrayInitialize.push_back(ConstantSInt::get(Type::IntTy, 0));
const ArrayType *ATy = ArrayType::get(Type::IntTy, numPaths);
Constant *initializer = ConstantArray::get(ATy, arrayInitialize);
char tempChar[20];
sprintf(tempChar, "Count%d", CountCounter);
CountCounter++;
std::string countStr = tempChar;
GlobalVariable *countVar = new GlobalVariable(ATy, false,
GlobalValue::InternalLinkage,
initializer, countStr,
F.getParent());
// insert initialization code in first (entry) BB
// this includes initializing r and count
insertInTopBB(&F.getEntryBlock(), numPaths, rVar, threshold);
//now process the graph: get path numbers,
//get increments along different paths,
//and assign "increments" and "updates" (to r and count)
//"optimally". Finally, insert llvm code along various edges
processGraph(g, rVar, countVar, be, stDummy, exDummy, numPaths, mn,
threshold);
return true; // Always modifies function
}
} // End llvm namespace
Property changes on: llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/ProfilePaths.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.38
\ No newline at end of property
+1.39
\ No newline at end of property
Index: llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp (revision 15333)
+++ llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp (revision 15334)
@@ -1,569 +1,569 @@
//===-- Graph.cpp - Implements Graph class --------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This implements Graph for helping in trace generation This graph gets used by
// "ProfilePaths" class.
//
//===----------------------------------------------------------------------===//
#include "Graph.h"
-#include "llvm/iTerminators.h"
+#include "llvm/Instructions.h"
#include "Support/Debug.h"
#include <algorithm>
using std::vector;
namespace llvm {
const graphListElement *findNodeInList(const Graph::nodeList &NL,
Node *N) {
for(Graph::nodeList::const_iterator NI = NL.begin(), NE=NL.end(); NI != NE;
++NI)
if (*NI->element== *N)
return &*NI;
return 0;
}
graphListElement *findNodeInList(Graph::nodeList &NL, Node *N) {
for(Graph::nodeList::iterator NI = NL.begin(), NE=NL.end(); NI != NE; ++NI)
if (*NI->element== *N)
return &*NI;
return 0;
}
//graph constructor with root and exit specified
Graph::Graph(std::vector<Node*> n, std::vector<Edge> e,
Node *rt, Node *lt){
strt=rt;
ext=lt;
for(vector<Node* >::iterator x=n.begin(), en=n.end(); x!=en; ++x)
//nodes[*x] = list<graphListElement>();
nodes[*x] = vector<graphListElement>();
for(vector<Edge >::iterator x=e.begin(), en=e.end(); x!=en; ++x){
Edge ee=*x;
int w=ee.getWeight();
//nodes[ee.getFirst()].push_front(graphListElement(ee.getSecond(),w, ee.getRandId()));
nodes[ee.getFirst()].push_back(graphListElement(ee.getSecond(),w, ee.getRandId()));
}
}
//sorting edgelist, called by backEdgeVist ONLY!!!
Graph::nodeList &Graph::sortNodeList(Node *par, nodeList &nl, vector<Edge> &be){
assert(par && "null node pointer");
BasicBlock *bbPar = par->getElement();
if(nl.size()<=1) return nl;
if(getExit() == par) return nl;
for(nodeList::iterator NLI = nl.begin(), NLE = nl.end()-1; NLI != NLE; ++NLI){
nodeList::iterator min = NLI;
for(nodeList::iterator LI = NLI+1, LE = nl.end(); LI!=LE; ++LI){
//if LI < min, min = LI
if(min->element->getElement() == LI->element->getElement() &&
min->element == getExit()){
//same successors: so might be exit???
//if it is exit, then see which is backedge
//check if LI is a left back edge!
TerminatorInst *tti = par->getElement()->getTerminator();
BranchInst *ti = cast<BranchInst>(tti);
assert(ti && "not a branch");
assert(ti->getNumSuccessors()==2 && "less successors!");
BasicBlock *tB = ti->getSuccessor(0);
BasicBlock *fB = ti->getSuccessor(1);
//so one of LI or min must be back edge!
//Algo: if succ(0)!=LI (and so !=min) then succ(0) is backedge
//and then see which of min or LI is backedge
//THEN if LI is in be, then min=LI
if(LI->element->getElement() != tB){//so backedge must be made min!
for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end();
VBEI != VBEE; ++VBEI){
if(VBEI->getRandId() == LI->randId){
min = LI;
break;
}
else if(VBEI->getRandId() == min->randId)
break;
}
}
else{// if(LI->element->getElement() != fB)
for(vector<Edge>::iterator VBEI = be.begin(), VBEE = be.end();
VBEI != VBEE; ++VBEI){
if(VBEI->getRandId() == min->randId){
min = LI;
break;
}
else if(VBEI->getRandId() == LI->randId)
break;
}
}
}
else if (min->element->getElement() != LI->element->getElement()){
TerminatorInst *tti = par->getElement()->getTerminator();
BranchInst *ti = cast<BranchInst>(tti);
assert(ti && "not a branch");
if(ti->getNumSuccessors()<=1) continue;
assert(ti->getNumSuccessors()==2 && "less successors!");
BasicBlock *tB = ti->getSuccessor(0);
BasicBlock *fB = ti->getSuccessor(1);
if(tB == LI->element->getElement() || fB == min->element->getElement())
min = LI;
}
}
graphListElement tmpElmnt = *min;
*min = *NLI;
*NLI = tmpElmnt;
}
return nl;
}
//check whether graph has an edge
//having an edge simply means that there is an edge in the graph
//which has same endpoints as the given edge
bool Graph::hasEdge(Edge ed){
if(ed.isNull())
return false;
nodeList &nli= nodes[ed.getFirst()]; //getNodeList(ed.getFirst());
Node *nd2=ed.getSecond();
return (findNodeInList(nli,nd2)!=NULL);
}
//check whether graph has an edge, with a given wt
//having an edge simply means that there is an edge in the graph
//which has same endpoints as the given edge
//This function checks, moreover, that the wt of edge matches too
bool Graph::hasEdgeAndWt(Edge ed){
if(ed.isNull())
return false;
Node *nd2=ed.getSecond();
nodeList &nli = nodes[ed.getFirst()];//getNodeList(ed.getFirst());
for(nodeList::iterator NI=nli.begin(), NE=nli.end(); NI!=NE; ++NI)
if(*NI->element == *nd2 && ed.getWeight()==NI->weight)
return true;
return false;
}
//add a node
void Graph::addNode(Node *nd){
vector<Node *> lt=getAllNodes();
for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE;++LI){
if(**LI==*nd)
return;
}
//chng
nodes[nd] =vector<graphListElement>(); //list<graphListElement>();
}
//add an edge
//this adds an edge ONLY when
//the edge to be added does not already exist
//we "equate" two edges here only with their
//end points
void Graph::addEdge(Edge ed, int w){
nodeList &ndList = nodes[ed.getFirst()];
Node *nd2=ed.getSecond();
if(findNodeInList(nodes[ed.getFirst()], nd2))
return;
//ndList.push_front(graphListElement(nd2,w, ed.getRandId()));
ndList.push_back(graphListElement(nd2,w, ed.getRandId()));//chng
//sortNodeList(ed.getFirst(), ndList);
//sort(ndList.begin(), ndList.end(), NodeListSort());
}
//add an edge EVEN IF such an edge already exists
//this may make a multi-graph
//which does happen when we add dummy edges
//to the graph, for compensating for back-edges
void Graph::addEdgeForce(Edge ed){
//nodes[ed.getFirst()].push_front(graphListElement(ed.getSecond(),
//ed.getWeight(), ed.getRandId()));
nodes[ed.getFirst()].push_back
(graphListElement(ed.getSecond(), ed.getWeight(), ed.getRandId()));
//sortNodeList(ed.getFirst(), nodes[ed.getFirst()]);
//sort(nodes[ed.getFirst()].begin(), nodes[ed.getFirst()].end(), NodeListSort());
}
//remove an edge
//Note that it removes just one edge,
//the first edge that is encountered
void Graph::removeEdge(Edge ed){
nodeList &ndList = nodes[ed.getFirst()];
Node &nd2 = *ed.getSecond();
for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) {
if(*NI->element == nd2) {
ndList.erase(NI);
break;
}
}
}
//remove an edge with a given wt
//Note that it removes just one edge,
//the first edge that is encountered
void Graph::removeEdgeWithWt(Edge ed){
nodeList &ndList = nodes[ed.getFirst()];
Node &nd2 = *ed.getSecond();
for(nodeList::iterator NI=ndList.begin(), NE=ndList.end(); NI!=NE ;++NI) {
if(*NI->element == nd2 && NI->weight==ed.getWeight()) {
ndList.erase(NI);
break;
}
}
}
//set the weight of an edge
void Graph::setWeight(Edge ed){
graphListElement *El = findNodeInList(nodes[ed.getFirst()], ed.getSecond());
if (El)
El->weight=ed.getWeight();
}
//get the list of successor nodes
vector<Node *> Graph::getSuccNodes(Node *nd){
nodeMapTy::const_iterator nli = nodes.find(nd);
assert(nli != nodes.end() && "Node must be in nodes map");
const nodeList &nl = getNodeList(nd);//getSortedNodeList(nd);
vector<Node *> lt;
for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
lt.push_back(NI->element);
return lt;
}
//get the number of outgoing edges
int Graph::getNumberOfOutgoingEdges(Node *nd) const {
nodeMapTy::const_iterator nli = nodes.find(nd);
assert(nli != nodes.end() && "Node must be in nodes map");
const nodeList &nl = nli->second;
int count=0;
for(nodeList::const_iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI)
count++;
return count;
}
//get the list of predecessor nodes
vector<Node *> Graph::getPredNodes(Node *nd){
vector<Node *> lt;
for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
Node *lnode=EI->first;
const nodeList &nl = getNodeList(lnode);
const graphListElement *N = findNodeInList(nl, nd);
if (N) lt.push_back(lnode);
}
return lt;
}
//get the number of predecessor nodes
int Graph::getNumberOfIncomingEdges(Node *nd){
int count=0;
for(nodeMapTy::const_iterator EI=nodes.begin(), EE=nodes.end(); EI!=EE ;++EI){
Node *lnode=EI->first;
const nodeList &nl = getNodeList(lnode);
for(Graph::nodeList::const_iterator NI = nl.begin(), NE=nl.end(); NI != NE;
++NI)
if (*NI->element== *nd)
count++;
}
return count;
}
//get the list of all the vertices in graph
vector<Node *> Graph::getAllNodes() const{
vector<Node *> lt;
for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
lt.push_back(x->first);
return lt;
}
//get the list of all the vertices in graph
vector<Node *> Graph::getAllNodes(){
vector<Node *> lt;
for(nodeMapTy::const_iterator x=nodes.begin(), en=nodes.end(); x != en; ++x)
lt.push_back(x->first);
return lt;
}
//class to compare two nodes in graph
//based on their wt: this is used in
//finding the maximal spanning tree
struct compare_nodes {
bool operator()(Node *n1, Node *n2){
return n1->getWeight() < n2->getWeight();
}
};
static void printNode(Node *nd){
std::cerr<<"Node:"<<nd->getElement()->getName()<<"\n";
}
//Get the Maximal spanning tree (also a graph)
//of the graph
Graph* Graph::getMaxSpanningTree(){
//assume connected graph
Graph *st=new Graph();//max spanning tree, undirected edges
int inf=9999999;//largest key
vector<Node *> lt = getAllNodes();
//initially put all vertices in vector vt
//assign wt(root)=0
//wt(others)=infinity
//
//now:
//pull out u: a vertex frm vt of min wt
//for all vertices w in vt,
//if wt(w) greater than
//the wt(u->w), then assign
//wt(w) to be wt(u->w).
//
//make parent(u)=w in the spanning tree
//keep pulling out vertices from vt till it is empty
vector<Node *> vt;
std::map<Node*, Node* > parent;
std::map<Node*, int > ed_weight;
//initialize: wt(root)=0, wt(others)=infinity
//parent(root)=NULL, parent(others) not defined (but not null)
for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
Node *thisNode=*LI;
if(*thisNode == *getRoot()){
thisNode->setWeight(0);
parent[thisNode]=NULL;
ed_weight[thisNode]=0;
}
else{
thisNode->setWeight(inf);
}
st->addNode(thisNode);//add all nodes to spanning tree
//we later need to assign edges in the tree
vt.push_back(thisNode); //pushed all nodes in vt
}
//keep pulling out vertex of min wt from vt
while(!vt.empty()){
Node *u=*(min_element(vt.begin(), vt.end(), compare_nodes()));
DEBUG(std::cerr<<"popped wt"<<(u)->getWeight()<<"\n";
printNode(u));
if(parent[u]!=NULL){ //so not root
Edge edge(parent[u],u, ed_weight[u]); //assign edge in spanning tree
st->addEdge(edge,ed_weight[u]);
DEBUG(std::cerr<<"added:\n";
printEdge(edge));
}
//vt.erase(u);
//remove u frm vt
for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
if(**VI==*u){
vt.erase(VI);
break;
}
}
//assign wt(v) to all adjacent vertices v of u
//only if v is in vt
Graph::nodeList &nl = getNodeList(u);
for(nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
Node *v=NI->element;
int weight=-NI->weight;
//check if v is in vt
bool contains=false;
for(vector<Node *>::iterator VI=vt.begin(), VE=vt.end(); VI!=VE; ++VI){
if(**VI==*v){
contains=true;
break;
}
}
DEBUG(std::cerr<<"wt:v->wt"<<weight<<":"<<v->getWeight()<<"\n";
printNode(v);std::cerr<<"node wt:"<<(*v).weight<<"\n");
//so if v in in vt, change wt(v) to wt(u->v)
//only if wt(u->v)<wt(v)
if(contains && weight<v->getWeight()){
parent[v]=u;
ed_weight[v]=weight;
v->setWeight(weight);
DEBUG(std::cerr<<v->getWeight()<<":Set weight------\n";
printGraph();
printEdge(Edge(u,v,weight)));
}
}
}
return st;
}
//print the graph (for debugging)
void Graph::printGraph(){
vector<Node *> lt=getAllNodes();
std::cerr<<"Graph---------------------\n";
for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
std::cerr<<((*LI)->getElement())->getName()<<"->";
Graph::nodeList &nl = getNodeList(*LI);
for(Graph::nodeList::iterator NI=nl.begin(), NE=nl.end(); NI!=NE; ++NI){
std::cerr<<":"<<"("<<(NI->element->getElement())
->getName()<<":"<<NI->element->getWeight()<<","<<NI->weight<<")";
}
std::cerr<<"--------\n";
}
}
//get a list of nodes in the graph
//in r-topological sorted order
//note that we assumed graph to be connected
vector<Node *> Graph::reverseTopologicalSort(){
vector <Node *> toReturn;
vector<Node *> lt=getAllNodes();
for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
DFS_Visit(*LI, toReturn);
}
return toReturn;
}
//a private method for doing DFS traversal of graph
//this is used in determining the reverse topological sort
//of the graph
void Graph::DFS_Visit(Node *nd, vector<Node *> &toReturn){
nd->setWeight(GREY);
vector<Node *> lt=getSuccNodes(nd);
for(vector<Node *>::iterator LI=lt.begin(), LE=lt.end(); LI!=LE; ++LI){
if((*LI)->getWeight()!=GREY && (*LI)->getWeight()!=BLACK)
DFS_Visit(*LI, toReturn);
}
toReturn.push_back(nd);
}
//Ordinarily, the graph is directional
//this converts the graph into an
//undirectional graph
//This is done by adding an edge
//v->u for all existing edges u->v
void Graph::makeUnDirectional(){
vector<Node* > allNodes=getAllNodes();
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI) {
nodeList &nl = getNodeList(*NI);
for(nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE; ++NLI){
Edge ed(NLI->element, *NI, NLI->weight);
if(!hasEdgeAndWt(ed)){
DEBUG(std::cerr<<"######doesn't hv\n";
printEdge(ed));
addEdgeForce(ed);
}
}
}
}
//reverse the sign of weights on edges
//this way, max-spanning tree could be obtained
//using min-spanning tree, and vice versa
void Graph::reverseWts(){
vector<Node *> allNodes=getAllNodes();
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI) {
nodeList &node_list = getNodeList(*NI);
for(nodeList::iterator NLI=nodes[*NI].begin(), NLE=nodes[*NI].end();
NLI!=NLE; ++NLI)
NLI->weight=-NLI->weight;
}
}
//getting the backedges in a graph
//Its a variation of DFS to get the backedges in the graph
//We get back edges by associating a time
//and a color with each vertex.
//The time of a vertex is the time when it was first visited
//The color of a vertex is initially WHITE,
//Changes to GREY when it is first visited,
//and changes to BLACK when ALL its neighbors
//have been visited
//So we have a back edge when we meet a successor of
//a node with smaller time, and GREY color
void Graph::getBackEdges(vector<Edge > &be, std::map<Node *, int> &d){
std::map<Node *, Color > color;
int time=0;
getBackEdgesVisit(getRoot(), be, color, d, time);
}
//helper function to get back edges: it is called by
//the "getBackEdges" function above
void Graph::getBackEdgesVisit(Node *u, vector<Edge > &be,
std::map<Node *, Color > &color,
std::map<Node *, int > &d, int &time) {
color[u]=GREY;
time++;
d[u]=time;
vector<graphListElement> &succ_list = getNodeList(u);
for(vector<graphListElement>::iterator vl=succ_list.begin(),
ve=succ_list.end(); vl!=ve; ++vl){
Node *v=vl->element;
if(color[v]!=GREY && color[v]!=BLACK){
getBackEdgesVisit(v, be, color, d, time);
}
//now checking for d and f vals
if(color[v]==GREY){
//so v is ancestor of u if time of u > time of v
if(d[u] >= d[v]){
Edge *ed=new Edge(u, v,vl->weight, vl->randId);
if (!(*u == *getExit() && *v == *getRoot()))
be.push_back(*ed); // choose the forward edges
}
}
}
color[u]=BLACK;//done with visiting the node and its neighbors
}
} // End llvm namespace
Property changes on: llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/Graph.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.16
\ No newline at end of property
+1.17
\ No newline at end of property
Index: llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/RetracePath.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/RetracePath.cpp (revision 15333)
+++ llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/RetracePath.cpp (revision 15334)
@@ -1,310 +1,309 @@
//===- RetracePath.cpp ----------------------------------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// Retraces a path of BasicBlock, given a path number and a graph!
//
//===----------------------------------------------------------------------===//
#include "llvm/Module.h"
-#include "llvm/iTerminators.h"
-#include "llvm/iOther.h"
+#include "llvm/Instructions.h"
#include "llvm/Support/CFG.h"
#include "Graph.h"
#include <iostream>
using std::vector;
using std::map;
using std::cerr;
namespace llvm {
//Routines to get the path trace!
void getPathFrmNode(Node *n, vector<BasicBlock*> &vBB, int pathNo, Graph &g,
vector<Edge> &stDummy, vector<Edge> &exDummy,
vector<Edge> &be,
double strand){
Graph::nodeList &nlist = g.getNodeList(n);
//printGraph(g);
//std::cerr<<"Path No: "<<pathNo<<"\n";
int maxCount=-9999999;
bool isStart=false;
if(*n==*g.getRoot())//its root: so first node of path
isStart=true;
double edgeRnd=0;
Node *nextRoot=n;
for(Graph::nodeList::iterator NLI = nlist.begin(), NLE=nlist.end(); NLI!=NLE;
++NLI){
if(NLI->weight>maxCount && NLI->weight<=pathNo){
maxCount=NLI->weight;
nextRoot=NLI->element;
edgeRnd=NLI->randId;
if(isStart)
strand=NLI->randId;
}
}
if(!isStart)
assert(strand!=-1 && "strand not assigned!");
assert(!(*nextRoot==*n && pathNo>0) && "No more BBs to go");
assert(!(*nextRoot==*g.getExit() && pathNo-maxCount!=0) && "Reached exit");
vBB.push_back(n->getElement());
if(pathNo-maxCount==0 && *nextRoot==*g.getExit()){
//look for strnd and edgeRnd now:
bool has1=false, has2=false;
//check if exit has it
for(vector<Edge>::iterator VI=exDummy.begin(), VE=exDummy.end(); VI!=VE;
++VI){
if(VI->getRandId()==edgeRnd){
has2=true;
break;
}
}
//check if start has it
for(vector<Edge>::iterator VI=stDummy.begin(), VE=stDummy.end(); VI!=VE;
++VI){
if(VI->getRandId()==strand){
has1=true;
break;
}
}
if(has1){
//find backedge with endpoint vBB[1]
for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
assert(vBB.size()>0 && "vector too small");
if( VI->getSecond()->getElement() == vBB[1] ){
//vBB[0]=VI->getFirst()->getElement();
vBB.erase(vBB.begin());
break;
}
}
}
if(has2){
//find backedge with startpoint vBB[vBB.size()-1]
for(vector<Edge>::iterator VI=be.begin(), VE=be.end(); VI!=VE; ++VI){
assert(vBB.size()>0 && "vector too small");
if( VI->getFirst()->getElement() == vBB[vBB.size()-1] &&
VI->getSecond()->getElement() == vBB[0]){
//vBB.push_back(VI->getSecond()->getElement());
break;
}
}
}
else
vBB.push_back(nextRoot->getElement());
return;
}
assert(pathNo-maxCount>=0);
return getPathFrmNode(nextRoot, vBB, pathNo-maxCount, g, stDummy,
exDummy, be, strand);
}
static Node *findBB(std::vector<Node *> &st, BasicBlock *BB){
for(std::vector<Node *>::iterator si=st.begin(); si!=st.end(); ++si){
if(((*si)->getElement())==BB){
return *si;
}
}
return NULL;
}
void getBBtrace(vector<BasicBlock *> &vBB, int pathNo, Function *M){//,
// vector<Instruction *> &instToErase){
//step 1: create graph
//Transform the cfg s.t. we have just one exit node
std::vector<Node *> nodes;
std::vector<Edge> edges;
Node *tmp;
Node *exitNode=0, *startNode=0;
//Creat cfg just once for each function!
static std::map<Function *, Graph *> graphMap;
//get backedges, exit and start edges for the graphs and store them
static std::map<Function *, vector<Edge> > stMap, exMap, beMap;
static std::map<Function *, Value *> pathReg; //path register
if(!graphMap[M]){
BasicBlock *ExitNode = 0;
for (Function::iterator I = M->begin(), E = M->end(); I != E; ++I){
if (isa<ReturnInst>(I->getTerminator())) {
ExitNode = I;
break;
}
}
assert(ExitNode!=0 && "exitnode not found");
//iterating over BBs and making graph
//The nodes must be uniquely identified:
//That is, no two nodes must hav same BB*
//keep a map for trigger basicblocks!
std::map<BasicBlock *, unsigned char> triggerBBs;
//First enter just nodes: later enter edges
for(Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
bool cont = false;
if(BB->size()==3 || BB->size() ==2){
for(BasicBlock::iterator II = BB->begin(), IE = BB->end();
II != IE; ++II){
if(CallInst *callInst = dyn_cast<CallInst>(II)){
//std::cerr<<*callInst;
Function *calledFunction = callInst->getCalledFunction();
if(calledFunction && calledFunction->getName() == "trigger"){
triggerBBs[BB] = 9;
cont = true;
//std::cerr<<"Found trigger!\n";
break;
}
}
}
}
if(cont)
continue;
// const Instruction *inst = BB->getInstList().begin();
// if(isa<CallInst>(inst)){
// Instruction *ii1 = BB->getInstList().begin();
// CallInst *callInst = dyn_cast<CallInst>(ii1);
// if(callInst->getCalledFunction()->getName()=="trigger")
// continue;
// }
Node *nd=new Node(BB);
nodes.push_back(nd);
if(&*BB==ExitNode)
exitNode=nd;
if(&*BB==&M->front())
startNode=nd;
}
assert(exitNode!=0 && startNode!=0 && "Start or exit not found!");
for (Function::iterator BB = M->begin(), BE=M->end(); BB != BE; ++BB){
if(triggerBBs[BB] == 9)
continue;
//if(BB->size()==3)
//if(CallInst *callInst = dyn_cast<CallInst>(BB->getInstList().begin()))
//if(callInst->getCalledFunction()->getName() == "trigger")
//continue;
// if(BB->size()==2){
// const Instruction *inst = BB->getInstList().begin();
// if(isa<CallInst>(inst)){
// Instruction *ii1 = BB->getInstList().begin();
// CallInst *callInst = dyn_cast<CallInst>(ii1);
// if(callInst->getCalledFunction()->getName()=="trigger")
// continue;
// }
// }
Node *nd=findBB(nodes, BB);
assert(nd && "No node for this edge!");
for(succ_iterator s=succ_begin(BB), se=succ_end(BB); s!=se; ++s){
if(triggerBBs[*s] == 9){
//if(!pathReg[M]){ //Get the path register for this!
//if(BB->size()>8)
// if(LoadInst *ldInst = dyn_cast<LoadInst>(BB->getInstList().begin()))
// pathReg[M] = ldInst->getPointerOperand();
//}
continue;
}
//if((*s)->size()==3)
//if(CallInst *callInst =
// dyn_cast<CallInst>((*s)->getInstList().begin()))
// if(callInst->getCalledFunction()->getName() == "trigger")
// continue;
// if((*s)->size()==2){
// const Instruction *inst = (*s)->getInstList().begin();
// if(isa<CallInst>(inst)){
// Instruction *ii1 = (*s)->getInstList().begin();
// CallInst *callInst = dyn_cast<CallInst>(ii1);
// if(callInst->getCalledFunction()->getName()=="trigger")
// continue;
// }
// }
Node *nd2 = findBB(nodes,*s);
assert(nd2 && "No node for this edge!");
Edge ed(nd,nd2,0);
edges.push_back(ed);
}
}
graphMap[M]= new Graph(nodes,edges, startNode, exitNode);
Graph *g = graphMap[M];
if (M->size() <= 1) return; //uninstrumented
//step 2: getBackEdges
//vector<Edge> be;
std::map<Node *, int> nodePriority;
g->getBackEdges(beMap[M], nodePriority);
//step 3: add dummy edges
//vector<Edge> stDummy;
//vector<Edge> exDummy;
addDummyEdges(stMap[M], exMap[M], *g, beMap[M]);
//step 4: value assgn to edges
int numPaths = valueAssignmentToEdges(*g, nodePriority, beMap[M]);
}
//step 5: now travel from root, select max(edge) < pathNo,
//and go on until reach the exit
getPathFrmNode(graphMap[M]->getRoot(), vBB, pathNo, *graphMap[M],
stMap[M], exMap[M], beMap[M], -1);
//post process vBB to locate instructions to be erased
/*
if(pathReg[M]){
for(vector<BasicBlock *>::iterator VBI = vBB.begin(), VBE = vBB.end();
VBI != VBE; ++VBI){
for(BasicBlock::iterator BBI = (*VBI)->begin(), BBE = (*VBI)->end();
BBI != BBE; ++BBI){
if(LoadInst *ldInst = dyn_cast<LoadInst>(BBI)){
if(pathReg[M] == ldInst->getPointerOperand())
instToErase.push_back(ldInst);
}
else if(StoreInst *stInst = dyn_cast<StoreInst>(BBI)){
if(pathReg[M] == stInst->getPointerOperand())
instToErase.push_back(stInst);
}
}
}
}
*/
}
} // End llvm namespace
Property changes on: llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/RetracePath.cpp
___________________________________________________________________
Modified: cvs2svn:cvs-rev
## -1 +1 ##
-1.9
\ No newline at end of property
+1.10
\ No newline at end of property
Index: llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp (revision 15333)
+++ llvm/trunk/lib/Transforms/Instrumentation/ProfilePaths/GraphAuxiliary.cpp (revision 15334)
@@ -1,679 +1,679 @@
//===- GraphAuxiliary.cpp - Auxiliary functions on graph ------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// auxiliary function associated with graph: they all operate on graph, and help
// in inserting instrumentation for trace generation
//
//===----------------------------------------------------------------------===//
#include "llvm/Pass.h"
#include "llvm/Module.h"
-#include "llvm/iTerminators.h"
+#include "llvm/Instructions.h"
#include "Support/Debug.h"
#include <algorithm>
#include "Graph.h"
//using std::list;
using std::map;
using std::vector;
using std::cerr;
namespace llvm {
//check if 2 edges are equal (same endpoints and same weight)
static bool edgesEqual(Edge ed1, Edge ed2){
return ((ed1==ed2) && ed1.getWeight()==ed2.getWeight());
}
//Get the vector of edges that are to be instrumented in the graph
static void getChords(vector<Edge > &chords, Graph &g, Graph st){
//make sure the spanning tree is directional
//iterate over ALL the edges of the graph
vector<Node *> allNodes=g.getAllNodes();
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
Graph::nodeList node_list=g.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
NLI!=NLE; ++NLI){
Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
if(!(st.hasEdgeAndWt(f)))//addnl
chords.push_back(f);
}
}
}
//Given a tree t, and a "directed graph" g
//replace the edges in the tree t with edges that exist in graph
//The tree is formed from "undirectional" copy of graph
//So whatever edges the tree has, the undirectional graph
//would have too. This function corrects some of the directions in
//the tree so that now, all edge directions in the tree match
//the edge directions of corresponding edges in the directed graph
static void removeTreeEdges(Graph &g, Graph& t){
vector<Node* > allNodes=t.getAllNodes();
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
Graph::nodeList nl=t.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=nl.begin(), NLE=nl.end(); NLI!=NLE;++NLI){
Edge ed(NLI->element, *NI, NLI->weight);
if(!g.hasEdgeAndWt(ed)) t.removeEdge(ed);//tree has only one edge
//between any pair of vertices, so no need to delete by edge wt
}
}
}
//Assign a value to all the edges in the graph
//such that if we traverse along any path from root to exit, and
//add up the edge values, we get a path number that uniquely
//refers to the path we travelled
int valueAssignmentToEdges(Graph& g, map<Node *, int> nodePriority,
vector<Edge> &be){
vector<Node *> revtop=g.reverseTopologicalSort();
map<Node *,int > NumPaths;
for(vector<Node *>::iterator RI=revtop.begin(), RE=revtop.end();
RI!=RE; ++RI){
if(g.isLeaf(*RI))
NumPaths[*RI]=1;
else{
NumPaths[*RI]=0;
// Modified Graph::nodeList &nlist=g.getNodeList(*RI);
Graph::nodeList &nlist=g.getSortedNodeList(*RI, be);
//sort nodelist by increasing order of numpaths
int sz=nlist.size();
for(int i=0;i<sz-1; i++){
int min=i;
for(int j=i+1; j<sz; j++){
BasicBlock *bb1 = nlist[j].element->getElement();
BasicBlock *bb2 = nlist[min].element->getElement();
if(bb1 == bb2) continue;
if(*RI == g.getRoot()){
assert(nodePriority[nlist[min].element]!=
nodePriority[nlist[j].element]
&& "priorities can't be same!");
if(nodePriority[nlist[j].element] <
nodePriority[nlist[min].element])
min = j;
}
else{
TerminatorInst *tti = (*RI)->getElement()->getTerminator();
BranchInst *ti = cast<BranchInst>(tti);
assert(ti && "not a branch");
assert(ti->getNumSuccessors()==2 && "less successors!");
BasicBlock *tB = ti->getSuccessor(0);
BasicBlock *fB = ti->getSuccessor(1);
if(tB == bb1 || fB == bb2)
min = j;
}
}
graphListElement tempEl=nlist[min];
nlist[min]=nlist[i];
nlist[i]=tempEl;
}
//sorted now!
for(Graph::nodeList::iterator GLI=nlist.begin(), GLE=nlist.end();
GLI!=GLE; ++GLI){
GLI->weight=NumPaths[*RI];
NumPaths[*RI]+=NumPaths[GLI->element];
}
}
}
return NumPaths[g.getRoot()];
}
//This is a helper function to get the edge increments
//This is used in conjunction with inc_DFS
//to get the edge increments
//Edge increment implies assigning a value to all the edges in the graph
//such that if we traverse along any path from root to exit, and
//add up the edge values, we get a path number that uniquely
//refers to the path we travelled
//inc_Dir tells whether 2 edges are in same, or in different directions
//if same direction, return 1, else -1
static int inc_Dir(Edge e, Edge f){
if(e.isNull())
return 1;
//check that the edges must have at least one common endpoint
assert(*(e.getFirst())==*(f.getFirst()) ||
*(e.getFirst())==*(f.getSecond()) ||
*(e.getSecond())==*(f.getFirst()) ||
*(e.getSecond())==*(f.getSecond()));
if(*(e.getFirst())==*(f.getSecond()) ||
*(e.getSecond())==*(f.getFirst()))
return 1;
return -1;
}
//used for getting edge increments (read comments above in inc_Dir)
//inc_DFS is a modification of DFS
static void inc_DFS(Graph& g,Graph& t,map<Edge, int, EdgeCompare2>& Increment,
int events, Node *v, Edge e){
vector<Node *> allNodes=t.getAllNodes();
for(vector<Node *>::iterator NI=allNodes.begin(), NE=allNodes.end(); NI!=NE;
++NI){
Graph::nodeList node_list=t.getNodeList(*NI);
for(Graph::nodeList::iterator NLI=node_list.begin(), NLE=node_list.end();
NLI!= NLE; ++NLI){
Edge f(*NI, NLI->element,NLI->weight, NLI->randId);
if(!edgesEqual(f,e) && *v==*(f.getSecond())){
int dir_count=inc_Dir(e,f);
int wt=1*f.getWeight();
inc_DFS(g,t, Increment, dir_count*events+wt, f.getFirst(), f);
}
}
}
for(vector<