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

2 files changed, 61 insertions, 23 deletions

diff --git a/lib/Transforms/Scalar/Scalar.cpp b/lib/Transforms/Scalar/Scalar.cpp
index 758334d..18cdcfe 100644
--- a/lib/Transforms/Scalar/Scalar.cpp
+++ b/lib/Transforms/Scalar/Scalar.cpp
@@ -57,7 +57,8 @@ void llvm::initializeScalarOpts(PassRegistry &Registry) {
   initializeSROAPass(Registry);
   initializeSROA_DTPass(Registry);
   initializeSROA_SSAUpPass(Registry);
-  initializeCFGSimplifyPassPass(Registry);
+  initializeCFGCanonicalizePass(Registry);
+  initializeCFGOptimizePass(Registry);
   initializeStructurizeCFGPass(Registry);
   initializeSinkingPass(Registry);
   initializeTailCallElimPass(Registry);
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 @@ using namespace llvm;
 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());
-    }
-
-    virtual bool runOnFunction(Function &F);
+struct CFGSimplifyPass : public FunctionPass {
+  CFGSimplifyPass(char &ID, bool isTargetAware)
+      : FunctionPass(ID), IsTargetAware(isTargetAware) {}
+  virtual bool runOnFunction(Function &F);
 
-    virtual void getAnalysisUsage(AnalysisUsage &AU) const {
-      AU.addRequired<TargetTransformInfo>();
-    }
-  };
+  virtual void getAnalysisUsage(AnalysisUsage &AU) const {
+    AU.addRequired<TargetTransformInfo>();
+  }
+private:
+  AliasAnalysis *AA;
+  bool IsTargetAware; // Should the pass be target-aware?
+};
+
+// 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(CFGCanonicalize, "simplifycfg", "Simplify the CFG", false,
+                    false)
+INITIALIZE_PASS_BEGIN(CFGOptimize, "optimizecfg", "optimize the CFG", false,
+                      false)
 INITIALIZE_AG_DEPENDENCY(TargetTransformInfo)
-INITIALIZE_PASS_END(CFGSimplifyPass, "simplifycfg", "Simplify the CFG",
-                    false, false)
+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 @@ static bool mergeEmptyReturnBlocks(Function &F) {
 /// 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 @@ static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
     // 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 @@ static bool iterativelySimplifyCFG(Function &F, const TargetTransformInfo &TTI,
 // 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 @@ bool CFGSimplifyPass::runOnFunction(Function &F) {
     return true;
 
   do {
-    EverChanged = iterativelySimplifyCFG(F, TTI, TD);
+    EverChanged = iterativelySimplifyCFG(F, TTI, TD, AA);
     EverChanged |= removeUnreachableBlocksFromFn(F);
   } while (EverChanged);