Index: include/polly/CodeGen/CodegenCleanup.h
===================================================================
--- /dev/null
+++ include/polly/CodeGen/CodegenCleanup.h
@@ -0,0 +1,17 @@
+#ifndef POLLY_CODEGENCLEANUP_H
+#define POLLY_CODEGENCLEANUP_H
+
+namespace llvm {
+class FunctionPass;
+class PassRegistry;
+}
+
+namespace polly {
+llvm::FunctionPass *createCodegenCleanupPass();
+}
+
+namespace llvm {
+void initializeCodegenCleanupPass(llvm::PassRegistry &);
+}
+
+#endif
Index: lib/CMakeLists.txt
===================================================================
--- lib/CMakeLists.txt
+++ lib/CMakeLists.txt
@@ -37,6 +37,7 @@
   CodeGen/IRBuilder.cpp
   CodeGen/Utils.cpp
   CodeGen/RuntimeDebugBuilder.cpp
+  CodeGen/CodegenCleanup.cpp
   ${GPGPU_CODEGEN_FILES}
   Exchange/JSONExporter.cpp
   Support/GICHelper.cpp
Index: lib/CodeGen/CodeGeneration.cpp
===================================================================
--- lib/CodeGen/CodeGeneration.cpp
+++ lib/CodeGen/CodeGeneration.cpp
@@ -176,6 +176,12 @@
 
     assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) &&
            "Verification of generated function failed");
+
+    // Mark the function such that we run additional cleanup passes on this
+    // function (e.g. mem2reg to rediscover phi nodes).
+    Function *F = EnteringBB->getParent();
+    F->addFnAttr("polly-optimized");
+
     return true;
   }
 
Index: lib/CodeGen/CodegenCleanup.cpp
===================================================================
--- /dev/null
+++ lib/CodeGen/CodegenCleanup.cpp
@@ -0,0 +1,122 @@
+#include "polly/CodeGen/CodegenCleanup.h"
+
+#include "llvm/Analysis/CFLAliasAnalysis.h"
+#include "llvm/Analysis/ScopedNoAliasAA.h"
+#include "llvm/Analysis/TypeBasedAliasAnalysis.h"
+#include "llvm/IR/Function.h"
+#include "llvm/IR/LegacyPassManager.h"
+#include "llvm/PassInfo.h"
+#include "llvm/PassRegistry.h"
+#include "llvm/PassSupport.h"
+#include "llvm/Support/Debug.h"
+#include "llvm/Transforms/Scalar.h"
+#define DEBUG_TYPE "polly-cleanup"
+
+using namespace llvm;
+using namespace polly;
+
+namespace {
+
+class CodegenCleanup : public FunctionPass {
+private:
+  CodegenCleanup(const CodegenCleanup &) = delete;
+  const CodegenCleanup &operator=(const CodegenCleanup &) = delete;
+
+  llvm::legacy::FunctionPassManager *FPM;
+
+public:
+  static char ID;
+  explicit CodegenCleanup() : FunctionPass(ID), FPM(nullptr) {}
+
+  /// @name FunctionPass interface
+  //@{
+  virtual void getAnalysisUsage(llvm::AnalysisUsage &AU) const override {}
+
+  virtual bool doInitialization(Module &M) override {
+    assert(!FPM);
+
+    FPM = new llvm::legacy::FunctionPassManager(&M);
+
+    // TODO: How to make parent passes discoverable?
+    // TODO: Should be sensitive to compiler options in PassManagerBuilder, to
+    // which wo do not have access here.
+    FPM->add(createCFLAAWrapperPass());
+    FPM->add(createScopedNoAliasAAWrapperPass());
+    FPM->add(createTypeBasedAAWrapperPass());
+    FPM->add(createAAResultsWrapperPass());
+
+    // TODO: These are non-conditional passes that run between
+    // EP_ModuleOptimizerEarly and EP_VectorizerStart just to ensure we do not
+    // miss any optimization that would have run after Polly with
+    // -polly-position=early. This can probably be reduced to a more compact set
+    // of passes.
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createScalarReplAggregatesPass());
+    FPM->add(createEarlyCSEPass());
+    FPM->add(createInstructionCombiningPass());
+    FPM->add(createJumpThreadingPass());
+    FPM->add(createCorrelatedValuePropagationPass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createInstructionCombiningPass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createReassociatePass());
+    FPM->add(createLoopRotatePass());
+    FPM->add(createLICMPass());
+    FPM->add(createLoopUnswitchPass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createInstructionCombiningPass());
+    FPM->add(createIndVarSimplifyPass());
+    FPM->add(createLoopIdiomPass());
+    FPM->add(createLoopDeletionPass());
+    FPM->add(createLoopInterchangePass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createSimpleLoopUnrollPass());
+    FPM->add(createMergedLoadStoreMotionPass());
+    FPM->add(createMemCpyOptPass());
+    FPM->add(createBitTrackingDCEPass());
+    FPM->add(createInstructionCombiningPass());
+    FPM->add(createJumpThreadingPass());
+    FPM->add(createCorrelatedValuePropagationPass());
+    FPM->add(createDeadStoreEliminationPass());
+    FPM->add(createLICMPass());
+    FPM->add(createLoopRerollPass());
+    FPM->add(createLoadCombinePass());
+    FPM->add(createAggressiveDCEPass());
+    FPM->add(createCFGSimplificationPass());
+    FPM->add(createInstructionCombiningPass());
+
+    return FPM->doInitialization();
+  }
+
+  virtual bool doFinalization(Module &M) override {
+    bool Result = FPM->doFinalization();
+
+    delete FPM;
+    FPM = nullptr;
+
+    return Result;
+  }
+
+  virtual bool runOnFunction(llvm::Function &F) override {
+    if (!F.hasFnAttribute("polly-optimized")) {
+      DEBUG(dbgs() << F.getName()
+                   << ": Skipping cleanup because Polly did not optimize it.");
+      return false;
+    }
+
+    DEBUG(dbgs() << F.getName() << ": Running codegen cleanup...");
+    return FPM->run(F);
+  }
+  //@}
+};
+
+char CodegenCleanup::ID;
+}
+
+FunctionPass *polly::createCodegenCleanupPass() { return new CodegenCleanup(); }
+
+INITIALIZE_PASS_BEGIN(CodegenCleanup, "polly-cleanup",
+                      "Polly - Cleanup after code generation", false, false)
+INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
+INITIALIZE_PASS_END(CodegenCleanup, "polly-cleanup",
+                    "Polly - Cleanup after code generation", false, false)
Index: lib/Support/RegisterPasses.cpp
===================================================================
--- lib/Support/RegisterPasses.cpp
+++ lib/Support/RegisterPasses.cpp
@@ -22,6 +22,7 @@
 #include "polly/RegisterPasses.h"
 #include "polly/Canonicalization.h"
 #include "polly/CodeGen/CodeGeneration.h"
+#include "polly/CodeGen/CodegenCleanup.h"
 #include "polly/DependenceInfo.h"
 #include "polly/LinkAllPasses.h"
 #include "polly/Options.h"
@@ -153,6 +154,7 @@
   initializePollyCanonicalizePass(Registry);
   initializeScopDetectionPass(Registry);
   initializeScopInfoPass(Registry);
+  initializeCodegenCleanupPass(Registry);
 }
 
 /// @brief Register Polly passes such that they form a polyhedral optimizer.
@@ -263,7 +265,7 @@
 
   PM.add(polly::createCodePreparationPass());
   polly::registerPollyPasses(PM);
-  // TODO: Add some cleanup passes
+  PM.add(createCodegenCleanupPass());
 }
 
 static void
@@ -277,7 +279,7 @@
 
   PM.add(polly::createCodePreparationPass());
   polly::registerPollyPasses(PM);
-  // TODO: Add some cleanup passes
+  PM.add(createCodegenCleanupPass());
 }
 
 /// @brief Register Polly to be available as an optimizer