aboutsummaryrefslogtreecommitdiff
path: root/lib/Transforms
diff options
context:
space:
mode:
Diffstat (limited to 'lib/Transforms')
-rw-r--r--lib/Transforms/Scalar/DeadStoreElimination.cpp10
-rw-r--r--lib/Transforms/Scalar/GVN.cpp8
-rw-r--r--lib/Transforms/Utils/BypassSlowDivision.cpp10
-rw-r--r--lib/Transforms/Utils/CMakeLists.txt1
-rw-r--r--lib/Transforms/Utils/MetaRenamer.cpp132
-rw-r--r--lib/Transforms/Utils/SimplifyCFG.cpp160
-rw-r--r--lib/Transforms/Utils/Utils.cpp1
7 files changed, 209 insertions, 113 deletions
diff --git a/lib/Transforms/Scalar/DeadStoreElimination.cpp b/lib/Transforms/Scalar/DeadStoreElimination.cpp
index 25a1dd770a..1ff4329c84 100644
--- a/lib/Transforms/Scalar/DeadStoreElimination.cpp
+++ b/lib/Transforms/Scalar/DeadStoreElimination.cpp
@@ -775,15 +775,15 @@ bool DSE::handleEndBlock(BasicBlock &BB) {
LiveAllocas.push_back(*I);
}
- for (SmallVector<Value*, 8>::iterator I = LiveAllocas.begin(),
- E = LiveAllocas.end(); I != E; ++I)
- DeadStackObjects.remove(*I);
-
// If all of the allocas were clobbered by the call then we're not going
// to find anything else to process.
- if (DeadStackObjects.empty())
+ if (DeadStackObjects.size() == LiveAllocas.size())
break;
+ for (SmallVector<Value*, 8>::iterator I = LiveAllocas.begin(),
+ E = LiveAllocas.end(); I != E; ++I)
+ DeadStackObjects.remove(*I);
+
continue;
}
diff --git a/lib/Transforms/Scalar/GVN.cpp b/lib/Transforms/Scalar/GVN.cpp
index bce43bbdae..16ae6add86 100644
--- a/lib/Transforms/Scalar/GVN.cpp
+++ b/lib/Transforms/Scalar/GVN.cpp
@@ -271,16 +271,16 @@ void ValueTable::add(Value *V, uint32_t num) {
valueNumbering.insert(std::make_pair(V, num));
}
-uint32_t ValueTable::lookup_or_add_call(CallInst* C) {
+uint32_t ValueTable::lookup_or_add_call(CallInst *C) {
if (AA->doesNotAccessMemory(C)) {
Expression exp = create_expression(C);
- uint32_t& e = expressionNumbering[exp];
+ uint32_t &e = expressionNumbering[exp];
if (!e) e = nextValueNumber++;
valueNumbering[C] = e;
return e;
} else if (AA->onlyReadsMemory(C)) {
Expression exp = create_expression(C);
- uint32_t& e = expressionNumbering[exp];
+ uint32_t &e = expressionNumbering[exp];
if (!e) {
e = nextValueNumber++;
valueNumbering[C] = e;
@@ -413,7 +413,7 @@ uint32_t ValueTable::lookup_or_add(Value *V) {
case Instruction::LShr:
case Instruction::AShr:
case Instruction::And:
- case Instruction::Or :
+ case Instruction::Or:
case Instruction::Xor:
case Instruction::ICmp:
case Instruction::FCmp:
diff --git a/lib/Transforms/Utils/BypassSlowDivision.cpp b/lib/Transforms/Utils/BypassSlowDivision.cpp
index b694779a53..30d60be277 100644
--- a/lib/Transforms/Utils/BypassSlowDivision.cpp
+++ b/lib/Transforms/Utils/BypassSlowDivision.cpp
@@ -24,7 +24,7 @@
using namespace llvm;
-namespace llvm {
+namespace {
struct DivOpInfo {
bool SignedOp;
Value *Dividend;
@@ -41,7 +41,9 @@ namespace llvm {
DivPhiNodes(PHINode *InQuotient, PHINode *InRemainder)
: Quotient(InQuotient), Remainder(InRemainder) {}
};
+}
+namespace llvm {
template<>
struct DenseMapInfo<DivOpInfo> {
static bool isEqual(const DivOpInfo &Val1, const DivOpInfo &Val2) {
@@ -217,9 +219,9 @@ static bool reuseOrInsertFastDiv(Function &F,
// bypassSlowDivision - This optimization identifies DIV instructions that can
// be profitably bypassed and carried out with a shorter, faster divide.
-bool bypassSlowDivision(Function &F,
- Function::iterator &I,
- const llvm::DenseMap<Type *, Type *> &BypassTypeMap) {
+bool llvm::bypassSlowDivision(Function &F,
+ Function::iterator &I,
+ const DenseMap<Type *, Type *> &BypassTypeMap) {
DivCacheTy DivCache;
bool MadeChange = false;
diff --git a/lib/Transforms/Utils/CMakeLists.txt b/lib/Transforms/Utils/CMakeLists.txt
index 215a16ff3f..aace75b745 100644
--- a/lib/Transforms/Utils/CMakeLists.txt
+++ b/lib/Transforms/Utils/CMakeLists.txt
@@ -20,6 +20,7 @@ add_llvm_library(LLVMTransformUtils
LowerInvoke.cpp
LowerSwitch.cpp
Mem2Reg.cpp
+ MetaRenamer.cpp
ModuleUtils.cpp
PromoteMemoryToRegister.cpp
SSAUpdater.cpp
diff --git a/lib/Transforms/Utils/MetaRenamer.cpp b/lib/Transforms/Utils/MetaRenamer.cpp
new file mode 100644
index 0000000000..60f031e16f
--- /dev/null
+++ b/lib/Transforms/Utils/MetaRenamer.cpp
@@ -0,0 +1,132 @@
+//===- MetaRenamer.cpp - Rename everything with metasyntatic names --------===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// This pass renames everything with metasyntatic names. The intent is to use
+// this pass after bugpoint reduction to conceal the nature of the original
+// program.
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/IPO.h"
+#include "llvm/Function.h"
+#include "llvm/Module.h"
+#include "llvm/Pass.h"
+#include "llvm/Type.h"
+#include "llvm/TypeFinder.h"
+#include "llvm/DerivedTypes.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallString.h"
+
+using namespace llvm;
+
+namespace {
+
+ // This PRNG is from the ISO C spec. It is intentionally simple and
+ // unsuitable for cryptographic use. We're just looking for enough
+ // variety to surprise and delight users.
+ struct PRNG {
+ unsigned long next;
+
+ void srand(unsigned int seed) {
+ next = seed;
+ }
+
+ int rand(void) {
+ next = next * 1103515245 + 12345;
+ return (unsigned int)(next / 65536) % 32768;
+ }
+ };
+
+ struct MetaRenamer : public ModulePass {
+ static char ID; // Pass identification, replacement for typeid
+ MetaRenamer() : ModulePass(ID) {
+ initializeMetaRenamerPass(*PassRegistry::getPassRegistry());
+ }
+
+ void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.setPreservesAll();
+ }
+
+ bool runOnModule(Module &M) {
+ static const char *metaNames[] = {
+ // See http://en.wikipedia.org/wiki/Metasyntactic_variable
+ "foo", "bar", "baz", "quux", "barney", "snork", "zot", "blam", "hoge",
+ "wibble", "wobble", "widget", "wombat", "ham", "eggs", "pluto", "spam"
+ };
+
+ // Seed our PRNG with simple additive sum of ModuleID. We're looking to
+ // simply avoid always having the same function names, and we need to
+ // remain deterministic.
+ unsigned int randSeed = 0;
+ for (std::string::const_iterator I = M.getModuleIdentifier().begin(),
+ E = M.getModuleIdentifier().end(); I != E; ++I)
+ randSeed += *I;
+
+ PRNG prng;
+ prng.srand(randSeed);
+
+ // Rename all aliases
+ for (Module::alias_iterator AI = M.alias_begin(), AE = M.alias_end();
+ AI != AE; ++AI)
+ AI->setName("alias");
+
+ // Rename all global variables
+ for (Module::global_iterator GI = M.global_begin(), GE = M.global_end();
+ GI != GE; ++GI)
+ GI->setName("global");
+
+ // Rename all struct types
+ TypeFinder StructTypes;
+ StructTypes.run(M, true);
+ for (unsigned i = 0, e = StructTypes.size(); i != e; ++i) {
+ StructType *STy = StructTypes[i];
+ if (STy->isLiteral() || STy->getName().empty()) continue;
+
+ SmallString<128> NameStorage;
+ STy->setName((Twine("struct.") + metaNames[prng.rand() %
+ array_lengthof(metaNames)]).toStringRef(NameStorage));
+ }
+
+ // Rename all functions
+ for (Module::iterator FI = M.begin(), FE = M.end();
+ FI != FE; ++FI) {
+ FI->setName(metaNames[prng.rand() % array_lengthof(metaNames)]);
+ runOnFunction(*FI);
+ }
+ return true;
+ }
+
+ bool runOnFunction(Function &F) {
+ for (Function::arg_iterator AI = F.arg_begin(), AE = F.arg_end();
+ AI != AE; ++AI)
+ if (!AI->getType()->isVoidTy())
+ AI->setName("arg");
+
+ for (Function::iterator BB = F.begin(), E = F.end(); BB != E; ++BB) {
+ BB->setName("bb");
+
+ for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I)
+ if (!I->getType()->isVoidTy())
+ I->setName("tmp");
+ }
+ return true;
+ }
+ };
+}
+
+char MetaRenamer::ID = 0;
+INITIALIZE_PASS(MetaRenamer, "metarenamer",
+ "Assign new names to everything", false, false)
+//===----------------------------------------------------------------------===//
+//
+// MetaRenamer - Rename everything with metasyntactic names.
+//
+ModulePass *llvm::createMetaRenamerPass() {
+ return new MetaRenamer();
+}
diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp
index 3df309958b..142f157c3c 100644
--- a/lib/Transforms/Utils/SimplifyCFG.cpp
+++ b/lib/Transforms/Utils/SimplifyCFG.cpp
@@ -752,38 +752,27 @@ static inline bool HasBranchWeights(const Instruction* I) {
return false;
}
-/// Tries to get a branch weight for the given instruction, returns NULL if it
-/// can't. Pos starts at 0.
-static ConstantInt* GetWeight(Instruction* I, int Pos) {
- MDNode* ProfMD = I->getMetadata(LLVMContext::MD_prof);
- if (ProfMD && ProfMD->getOperand(0)) {
- if (MDString* MDS = dyn_cast<MDString>(ProfMD->getOperand(0))) {
- if (MDS->getString().equals("branch_weights")) {
- assert(ProfMD->getNumOperands() >= 3);
- return dyn_cast<ConstantInt>(ProfMD->getOperand(1 + Pos));
- }
- }
- }
-
- return 0;
-}
-
-/// Scale the given weights based on the successor TI's metadata. Scaling is
-/// done by multiplying every weight by the sum of the successor's weights.
-static void ScaleWeights(Instruction* STI, MutableArrayRef<uint64_t> Weights) {
- // Sum the successor's weights
- assert(HasBranchWeights(STI));
- unsigned Scale = 0;
- MDNode* ProfMD = STI->getMetadata(LLVMContext::MD_prof);
- for (unsigned i = 1; i < ProfMD->getNumOperands(); ++i) {
- ConstantInt* CI = dyn_cast<ConstantInt>(ProfMD->getOperand(i));
+/// Get Weights of a given TerminatorInst, the default weight is at the front
+/// of the vector. If TI is a conditional eq, we need to swap the branch-weight
+/// metadata.
+static void GetBranchWeights(TerminatorInst *TI,
+ SmallVectorImpl<uint64_t> &Weights) {
+ MDNode* MD = TI->getMetadata(LLVMContext::MD_prof);
+ assert(MD);
+ for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) {
+ ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(i));
assert(CI);
- Scale += CI->getValue().getZExtValue();
+ Weights.push_back(CI->getValue().getZExtValue());
}
- // Skip default, as it's replaced during the folding
- for (unsigned i = 1; i < Weights.size(); ++i) {
- Weights[i] *= Scale;
+ // If TI is a conditional eq, the default case is the false case,
+ // and the corresponding branch-weight data is at index 2. We swap the
+ // default weight to be the first entry.
+ if (BranchInst* BI = dyn_cast<BranchInst>(TI)) {
+ assert(Weights.size() == 2);
+ ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
+ if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
+ std::swap(Weights.front(), Weights.back());
}
}
@@ -838,52 +827,22 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
// Update the branch weight metadata along the way
SmallVector<uint64_t, 8> Weights;
- uint64_t PredDefaultWeight = 0;
bool PredHasWeights = HasBranchWeights(PTI);
bool SuccHasWeights = HasBranchWeights(TI);
- if (PredHasWeights) {
- MDNode* MD = PTI->getMetadata(LLVMContext::MD_prof);
- assert(MD);
- for (unsigned i = 1, e = MD->getNumOperands(); i < e; ++i) {
- ConstantInt* CI = dyn_cast<ConstantInt>(MD->getOperand(i));
- assert(CI);
- Weights.push_back(CI->getValue().getZExtValue());
- }
-
- // If the predecessor is a conditional eq, then swap the default weight
- // to be the first entry.
- if (BranchInst* BI = dyn_cast<BranchInst>(PTI)) {
- assert(Weights.size() == 2);
- ICmpInst *ICI = cast<ICmpInst>(BI->getCondition());
-
- if (ICI->getPredicate() == ICmpInst::ICMP_EQ) {
- std::swap(Weights.front(), Weights.back());
- }
- }
-
- PredDefaultWeight = Weights.front();
- } else if (SuccHasWeights) {
+ if (PredHasWeights)
+ GetBranchWeights(PTI, Weights);
+ else if (SuccHasWeights)
// If there are no predecessor weights but there are successor weights,
// populate Weights with 1, which will later be scaled to the sum of
// successor's weights
Weights.assign(1 + PredCases.size(), 1);
- PredDefaultWeight = 1;
- }
-
- uint64_t SuccDefaultWeight = 0;
- if (SuccHasWeights) {
- int Index = 0;
- if (BranchInst* BI = dyn_cast<BranchInst>(TI)) {
- ICmpInst* ICI = dyn_cast<ICmpInst>(BI->getCondition());
- assert(ICI);
- if (ICI->getPredicate() == ICmpInst::ICMP_EQ)
- Index = 1;
- }
-
- SuccDefaultWeight = GetWeight(TI, Index)->getValue().getZExtValue();
- }
+ SmallVector<uint64_t, 8> SuccWeights;
+ if (SuccHasWeights)
+ GetBranchWeights(TI, SuccWeights);
+ else if (PredHasWeights)
+ SuccWeights.assign(1 + BBCases.size(), 1);
if (PredDefault == BB) {
// If this is the default destination from PTI, only the edges in TI
@@ -896,7 +855,9 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
// The default destination is BB, we don't need explicit targets.
std::swap(PredCases[i], PredCases.back());
- if (PredHasWeights) {
+ if (PredHasWeights || SuccHasWeights) {
+ // Increase weight for the default case.
+ Weights[0] += Weights[i+1];
std::swap(Weights[i+1], Weights.back());
Weights.pop_back();
}
@@ -912,28 +873,30 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(TerminatorInst *TI,
NewSuccessors.push_back(BBDefault);
}
- if (SuccHasWeights) {
- ScaleWeights(TI, Weights);
- Weights.front() *= SuccDefaultWeight;
- } else if (PredHasWeights) {
- Weights.front() /= (1 + BBCases.size());
- }
-
+ unsigned CasesFromPred = Weights.size();
+ uint64_t ValidTotalSuccWeight = 0;
for (unsigned i = 0, e = BBCases.size(); i != e; ++i)
if (!PTIHandled.count(BBCases[i].Value) &&
BBCases[i].Dest != BBDefault) {
PredCases.push_back(BBCases[i]);
NewSuccessors.push_back(BBCases[i].Dest);
- if (SuccHasWeights) {
- Weights.push_back(PredDefaultWeight *
- GetWeight(TI, i)->getValue().getZExtValue());
- } else if (PredHasWeights) {
- // Split the old default's weight amongst the children
- assert(PredDefaultWeight != 0);
- Weights.push_back(PredDefaultWeight / (1 + BBCases.size()));
+ if (SuccHasWeights || PredHasWeights) {
+ // The default weight is at index 0, so weight for the ith case
+ // should be at index i+1. Scale the cases from successor by
+ // PredDefaultWeight (Weights[0]).
+ Weights.push_back(Weights[0] * SuccWeights[i+1]);
+ ValidTotalSuccWeight += SuccWeights[i+1];
}
}
+ if (SuccHasWeights || PredHasWeights) {
+ ValidTotalSuccWeight += SuccWeights[0];
+ // Scale the cases from predecessor by ValidTotalSuccWeight.
+ for (unsigned i = 1; i < CasesFromPred; ++i)
+ Weights[i] *= ValidTotalSuccWeight;
+ // Scale the default weight by SuccDefaultWeight (SuccWeights[0]).
+ Weights[0] *= SuccWeights[0];
+ }
} else {
// FIXME: preserve branch weight metadata, similarly to the 'then'
// above. For now, drop it.
@@ -3046,13 +3009,12 @@ static bool GetCaseResults(SwitchInst *SI,
/// DefaultResult to fill the holes in the table. If the table ends up
/// containing the same result in each element, set *SingleResult to that value
/// and return NULL.
-static GlobalVariable *BuildLookupTable(
- Module &M,
- uint64_t TableSize,
- ConstantInt *Offset,
- const std::vector<std::pair<ConstantInt*,Constant*> >& Results,
- Constant *DefaultResult,
- Constant **SingleResult) {
+static GlobalVariable *BuildLookupTable(Module &M,
+ uint64_t TableSize,
+ ConstantInt *Offset,
+ const SmallVector<std::pair<ConstantInt*, Constant*>, 4>& Results,
+ Constant *DefaultResult,
+ Constant **SingleResult) {
assert(Results.size() && "Need values to build lookup table");
assert(TableSize >= Results.size() && "Table needs to hold all values");
@@ -3134,7 +3096,7 @@ static bool SwitchToLookupTable(SwitchInst *SI,
ConstantInt *MaxCaseVal = CI.getCaseValue();
BasicBlock *CommonDest = NULL;
- typedef std::vector<std::pair<ConstantInt*, Constant*> > ResultListTy;
+ typedef SmallVector<std::pair<ConstantInt*, Constant*>, 4> ResultListTy;
SmallDenseMap<PHINode*, ResultListTy> ResultLists;
SmallDenseMap<PHINode*, Constant*> DefaultResults;
SmallDenseMap<PHINode*, Type*> ResultTypes;
@@ -3162,16 +3124,14 @@ static bool SwitchToLookupTable(SwitchInst *SI,
}
// Get the resulting values for the default case.
- {
- SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList;
- if (!GetCaseResults(SI, SI->getDefaultDest(), &CommonDest, DefaultResultsList))
- return false;
- for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) {
- PHINode *PHI = DefaultResultsList[I].first;
- Constant *Result = DefaultResultsList[I].second;
- DefaultResults[PHI] = Result;
- ResultTypes[PHI] = Result->getType();
- }
+ SmallVector<std::pair<PHINode*, Constant*>, 4> DefaultResultsList;
+ if (!GetCaseResults(SI, SI->getDefaultDest(), &CommonDest, DefaultResultsList))
+ return false;
+ for (size_t I = 0, E = DefaultResultsList.size(); I != E; ++I) {
+ PHINode *PHI = DefaultResultsList[I].first;
+ Constant *Result = DefaultResultsList[I].second;
+ DefaultResults[PHI] = Result;
+ ResultTypes[PHI] = Result->getType();
}
APInt RangeSpread = MaxCaseVal->getValue() - MinCaseVal->getValue();
diff --git a/lib/Transforms/Utils/Utils.cpp b/lib/Transforms/Utils/Utils.cpp
index 24e8c8ff5c..5812d4607d 100644
--- a/lib/Transforms/Utils/Utils.cpp
+++ b/lib/Transforms/Utils/Utils.cpp
@@ -29,6 +29,7 @@ void llvm::initializeTransformUtils(PassRegistry &Registry) {
initializePromotePassPass(Registry);
initializeUnifyFunctionExitNodesPass(Registry);
initializeInstSimplifierPass(Registry);
+ initializeMetaRenamerPass(Registry);
}
/// LLVMInitializeTransformUtils - C binding for initializeTransformUtilsPasses.
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-08-03 08:04:18 +0000