SimplifyCFG: Use parallel-and and parallel-or mode to consolidate branch conditions
Merge consecutive if-regions if they contain identical statements.
Both transformations reduce number of branches. The transformation
is guarded by a target-hook, and is currently enabled only for +R600,
but the correctness has been tested on X86 target using a variety of
CPU benchmarks.
Patch by: Mei Ye
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@187278 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/Transforms/Scalar/SimplifyCFGPass.cpp b/lib/Transforms/Scalar/SimplifyCFGPass.cpp
index c243d34..9ab5f45 100644
--- a/lib/Transforms/Scalar/SimplifyCFGPass.cpp
+++ b/lib/Transforms/Scalar/SimplifyCFGPass.cpp
@@ -27,6 +27,7 @@
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/DataLayout.h"
@@ -41,30 +42,62 @@
STATISTIC(NumSimpl, "Number of blocks simplified");
namespace {
- struct CFGSimplifyPass : public FunctionPass {
- static char ID; // Pass identification, replacement for typeid
- CFGSimplifyPass() : FunctionPass(ID) {
- initializeCFGSimplifyPassPass(*PassRegistry::getPassRegistry());
- }
+struct CFGSimplifyPass : public FunctionPass {
+ CFGSimplifyPass(char &ID, bool isTargetAware)
+ : FunctionPass(ID), IsTargetAware(isTargetAware) {}
+ virtual bool runOnFunction(Function &F);
- virtual bool runOnFunction(Function &F);
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<TargetTransformInfo>();
+ }
+private:
+ AliasAnalysis *AA;
+ bool IsTargetAware; // Should the pass be target-aware?
+};
- virtual void getAnalysisUsage(AnalysisUsage &AU) const {
- AU.addRequired<TargetTransformInfo>();
- }
- };
+// CFGSimplifyPass that does optimizations.
+struct CFGOptimize : public CFGSimplifyPass {
+ static char ID; // Pass identification, replacement for typeid
+public:
+ CFGOptimize() : CFGSimplifyPass(ID, true) {
+ initializeCFGOptimizePass(*PassRegistry::getPassRegistry());
+ }
+ virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+ AU.addRequired<TargetTransformInfo>();
+ AU.addRequired<AliasAnalysis>();
+ }
+};
+
+// CFGSimplifyPass that does canonicalizations.
+struct CFGCanonicalize : public CFGSimplifyPass {
+ static char ID; // Pass identification, replacement for typeid
+public:
+ CFGCanonicalize() : CFGSimplifyPass(ID, false) {
+ initializeCFGCanonicalizePass(*PassRegistry::getPassRegistry());
+ }
+};
}
-char CFGSimplifyPass::ID = 0;
-INITIALIZE_PASS_BEGIN(CFGSimplifyPass, "simplifycfg", "Simplify the CFG",
- false, false)
+char CFGCanonicalize::ID = 0;
+char CFGOptimize::ID = 0;
+INITIALIZE_PASS_BEGIN(CFGCanonicalize, "simplifycfg", "Simplify the CFG", false,
+ false)
INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
-INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG",
- false, false)
+INITIALIZE_PASS_END(CFGCanonicalize, "simplifycfg", "Simplify the CFG", false,
+ false)
+INITIALIZE_PASS_BEGIN(CFGOptimize, "optimizecfg", "optimize the CFG", false,
+ false)
+INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
+INITIALIZE_AG_DEPENDENCY(AliasAnalysis)
+INITIALIZE_PASS_END(CFGOptimize, "optimizecfg", "Optimize the CFG", false,
+ false)
// Public interface to the CFGSimplification pass
-FunctionPass *llvm::createCFGSimplificationPass() {
- return new CFGSimplifyPass();
+FunctionPass *llvm::createCFGSimplificationPass(bool IsTargetAware) {
+ if (IsTargetAware)
+ return new CFGOptimize();
+ else
+ return new CFGCanonicalize();
}
/// changeToUnreachable - Insert an unreachable instruction before the specified
@@ -301,7 +334,7 @@
/// iterativelySimplifyCFG - Call SimplifyCFG on all the blocks in the function,
/// iterating until no more changes are made.
static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
- const DataLayout *TD) {
+ const DataLayout *TD, AliasAnalysis *AA) {
bool Changed = false;
bool LocalChange = true;
while (LocalChange) {
@@ -310,7 +343,7 @@
// Loop over all of the basic blocks and remove them if they are unneeded...
//
for (Function::iterator BBIt = F.begin(); BBIt != F.end(); ) {
- if (SimplifyCFG(BBIt++, TTI, TD)) {
+ if (SimplifyCFG(BBIt++, TTI, TD, AA)) {
LocalChange = true;
++NumSimpl;
}
@@ -324,11 +357,15 @@
// simplify the CFG.
//
bool CFGSimplifyPass::runOnFunction(Function &F) {
+ if (IsTargetAware)
+ AA = &getAnalysis<AliasAnalysis>();
+ else
+ AA = NULL;
const TargetTransformInfo &TTI = getAnalysis<TargetTransformInfo>();
const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
bool EverChanged = removeUnreachableBlocksFromFn(F);
EverChanged |= mergeEmptyReturnBlocks(F);
- EverChanged |= iterativelySimplifyCFG(F, TTI, TD);
+ EverChanged |= iterativelySimplifyCFG(F, TTI, TD, AA);
// If neither pass changed anything, we're done.
if (!EverChanged) return false;
@@ -342,7 +379,7 @@
return true;
do {
- EverChanged = iterativelySimplifyCFG(F, TTI, TD);
+ EverChanged = iterativelySimplifyCFG(F, TTI, TD, AA);
EverChanged |= removeUnreachableBlocksFromFn(F);
} while (EverChanged);