Index: lib/Transforms/InstCombine/InstCombineInternal.h
===================================================================
--- lib/Transforms/InstCombine/InstCombineInternal.h
+++ lib/Transforms/InstCombine/InstCombineInternal.h
@@ -17,6 +17,7 @@
 #define LLVM_LIB_TRANSFORMS_INSTCOMBINE_INSTCOMBINEINTERNAL_H
 
 #include "llvm/ADT/ArrayRef.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/Analysis/AliasAnalysis.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/TargetFolder.h"
@@ -24,6 +25,7 @@
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Argument.h"
 #include "llvm/IR/BasicBlock.h"
+#include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DerivedTypes.h"
@@ -251,6 +253,8 @@
 
   bool MadeIRChange = false;
 
+  MapVector<Function *, unsigned> HeapAllocEliminations;
+
 public:
   InstCombiner(InstCombineWorklist &Worklist, BuilderTy &Builder,
                bool MinimizeSize, bool ExpensiveCombines, AliasAnalysis *AA,
@@ -357,6 +361,9 @@
   /// Specify what to return for unhandled instructions.
   Instruction *visitInstruction(Instruction &I) { return nullptr; }
 
+  /// Eliminate small allocations
+  bool eliminateSmallAllocations(Value *Op, CallInst &FI);
+
   /// True when DB dominates all uses of DI except UI.
   /// UI must be in the same block as DI.
   /// The routine checks that the DI parent and DB are different.
Index: lib/Transforms/InstCombine/InstructionCombining.cpp
===================================================================
--- lib/Transforms/InstCombine/InstructionCombining.cpp
+++ lib/Transforms/InstCombine/InstructionCombining.cpp
@@ -39,7 +39,9 @@
 #include "llvm/ADT/APInt.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseMap.h"
+#include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/None.h"
+#include "llvm/ADT/PostOrderIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
@@ -59,6 +61,7 @@
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/Utils/Local.h"
 #include "llvm/Analysis/ValueTracking.h"
+#include "llvm/Analysis/CaptureTracking.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Constant.h"
@@ -116,6 +119,7 @@
 STATISTIC(NumExpand,    "Number of expansions");
 STATISTIC(NumFactor   , "Number of factorizations");
 STATISTIC(NumReassoc  , "Number of reassociations");
+STATISTIC(NumMallocElim, "Number of mallocs eliminated");
 DEBUG_COUNTER(VisitCounter, "instcombine-visit",
               "Controls which instructions are visited");
 
@@ -137,6 +141,15 @@
 static cl::opt<unsigned> ShouldLowerDbgDeclare("instcombine-lower-dbg-declare",
                                                cl::Hidden, cl::init(true));
 
+static cl::opt<unsigned>
+    HeapAllocSize("heap-alloc-size", cl::init(256),
+                 cl::desc("Maximum size of heap allocation to be replaced with alloca"));
+
+static cl::opt<unsigned>
+    HeapAllocCount("heap-alloc-count", cl::init(1),
+                  cl::desc("Maximum count of heap allocation to be replaced "
+                           "with alloca per function"));
+
 Value *InstCombiner::EmitGEPOffset(User *GEP) {
   return llvm::EmitGEPOffset(&Builder, DL, GEP);
 }
@@ -2260,9 +2273,78 @@
   return &FI;
 }
 
+bool InstCombiner::eliminateSmallAllocations(Value *Op, CallInst &FI) {
+  Function *F = FI.getFunction();
+
+  Function *FreeFn = FI.getCalledFunction();
+  if (!FreeFn)
+    return false;
+
+  LibFunc Func;
+  if (!TLI.getLibFunc(*FreeFn, Func) || !TLI.has(Func))
+    return false;
+
+  if (Func != LibFunc_free)
+    return false;
+
+  CallInst *Malloc = dyn_cast<CallInst>(Op);
+  if (!Malloc)
+    return false;
+
+  // Is the inner call really malloc?
+  Function *MallocFn = Malloc->getCalledFunction();
+  if (!MallocFn)
+    return false;
+
+  if (!TLI.getLibFunc(*MallocFn, Func) || !TLI.has(Func))
+    return false;
+
+  if (Func != LibFunc_malloc)
+    return false;
+
+  // Check if alloced pointer is captured
+  if (PointerMayBeCaptured(Malloc, true, true))
+    return false;
+
+  BasicBlock *BB = Malloc->getParent();
+  // Do not optimize if malloc is in loop
+  if (LI->getLoopFor(BB))
+    return false;
+
+  ReversePostOrderTraversal<BasicBlock *> RPOT(&*BB);
+  if (containsIrreducibleCFG<BasicBlock *>(RPOT, *LI))
+    return false;
+
+  // Check for constant size
+  ConstantInt *Size = dyn_cast<ConstantInt>(Malloc->getOperand(0));
+  if (!Size)
+    return false;
+
+  if (HeapAllocEliminations[F] == HeapAllocCount)
+    return false;
+
+  uint64_t N = Size->getZExtValue();
+  if (N > HeapAllocSize)
+    return false;
+
+  Builder.SetInsertPoint(&F->getEntryBlock(), F->getEntryBlock().begin());
+  Value *LocAlloc = Builder.CreateAlloca(Builder.getInt8Ty(), Size);
+  Malloc->replaceAllUsesWith(LocAlloc);
+  Malloc->eraseFromParent();
+
+  ++NumMallocElim;
+  ++HeapAllocEliminations[F];
+
+  return true;
+}
+
 Instruction *InstCombiner::visitFree(CallInst &FI) {
   Value *Op = FI.getArgOperand(0);
 
+  // Small "malloc"ation -> create new local variable
+  if (eliminateSmallAllocations(Op, FI))
+    return eraseInstFromFunction(FI);
+
   // free undef -> unreachable.
   if (isa<UndefValue>(Op)) {
     // Insert a new store to null because we cannot modify the CFG here.