Index: lib/Transforms/InstCombine/InstCombineInternal.h
===================================================================
--- lib/Transforms/InstCombine/InstCombineInternal.h
+++ lib/Transforms/InstCombine/InstCombineInternal.h
@@ -357,6 +357,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,6 +39,7 @@
 #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/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
@@ -59,6 +60,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 +118,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 +140,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 +2272,75 @@
   return &FI;
 }
 
+bool InstCombiner::eliminateSmallAllocations(Value *Op, CallInst &FI) {
+  static MapVector<Function *, unsigned> Eliminations;
+  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;
+
+  if (LI->getLoopFor(Malloc->getParent())) {
+    // Do not optimize if malloc is in loop
+    return false;
+  }
+
+  // Check for constant size
+  ConstantInt *Size = dyn_cast<ConstantInt>(Malloc->getOperand(0));
+  if (!Size)
+    return false;
+
+  if (Eliminations[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;
+  ++Eliminations[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.