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
@@ -59,6 +59,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 +117,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");
 
@@ -2260,9 +2262,83 @@
   return &FI;
 }
 
+bool InstCombiner::eliminateSmallAllocations(Value *Op, CallInst &FI) {
+  // Threshold to switch between optimization based on local/global variable
+  static unsigned FoldTreshold = 256;
+
+  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 for constant size
+  ConstantInt *Size = dyn_cast<ConstantInt>(Malloc->getOperand(0));
+  if (!Size)
+    return false;
+
+  uint64_t N = Size->getZExtValue();
+  Value *Ret;
+  Builder.SetInsertPoint(Malloc->getParent(), ++Malloc->getIterator());
+
+  if (N > FoldTreshold) {
+    // Create global variable 
+    static unsigned Cnt = 0;
+    ArrayType *arrayType = ArrayType::get(Builder.getInt8Ty(), N);
+    GlobalVariable *GV = new GlobalVariable(
+        *FI.getModule(), arrayType, false, GlobalVariable::CommonLinkage,
+        nullptr, Twine(++Cnt) + Malloc->getName());
+
+    GV->setInitializer(ConstantAggregateZero::get(arrayType));
+    Ret = Builder.CreateConstInBoundsGEP2_64(GV, 0, 0);
+  } else {
+    // Stack based, create local variable
+    if (LI->getLoopFor(Malloc->getParent())) {
+      // Do not optimize if malloc is in loop
+      return false;
+    }
+
+    // Check if alloced pointer is captured
+    if (PointerMayBeCaptured(Op, true, true))
+      return false;
+
+    Ret = Builder.CreateAlloca(Builder.getInt8Ty(), Size);
+  }
+
+  Malloc->replaceAllUsesWith(Ret);
+  Malloc->eraseFromParent();
+
+  ++NumMallocElim;
+  return true;
+}
+
 Instruction *InstCombiner::visitFree(CallInst &FI) {
   Value *Op = FI.getArgOperand(0);
 
+  // Small "malloc"ation -> use local/global 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.