Index: lib/Target/X86/X86ISelDAGToDAG.cpp
===================================================================
--- lib/Target/X86/X86ISelDAGToDAG.cpp
+++ lib/Target/X86/X86ISelDAGToDAG.cpp
@@ -157,9 +157,13 @@
     /// performance.
     bool OptForSize;
 
+    /// If true, selector should try to optimize for minimum code size.
+    bool OptForMinSize;
+
   public:
     explicit X86DAGToDAGISel(X86TargetMachine &tm, CodeGenOpt::Level OptLevel)
-        : SelectionDAGISel(tm, OptLevel), OptForSize(false) {}
+        : SelectionDAGISel(tm, OptLevel), OptForSize(false),
+          OptForMinSize(false) {}
 
     const char *getPassName() const override {
       return "X86 DAG->DAG Instruction Selection";
@@ -530,8 +534,10 @@
 }
 
 void X86DAGToDAGISel::PreprocessISelDAG() {
-  // OptForSize is used in pattern predicates that isel is matching.
+  // OptFor[Min]Size are used in pattern predicates that isel is matching.
   OptForSize = MF->getFunction()->optForSize();
+  OptForMinSize = MF->getFunction()->optForMinSize();
+  assert((!OptForMinSize || OptForSize) && "OptForMinSize implies OptForSize");
 
   for (SelectionDAG::allnodes_iterator I = CurDAG->allnodes_begin(),
        E = CurDAG->allnodes_end(); I != E; ) {
Index: lib/Target/X86/X86InstrCompiler.td
===================================================================
--- lib/Target/X86/X86InstrCompiler.td
+++ lib/Target/X86/X86InstrCompiler.td
@@ -990,6 +990,18 @@
 // DAG Pattern Matching Rules
 //===----------------------------------------------------------------------===//
 
+// Use AND/OR to store 0/-1 in memory when optimizing for minsize. This saves
+// binary size compared to a regular MOV, but it introduces an unnecessary
+// load, so is not suitable for regular or optsize functions.
+let Predicates = [OptForMinSize] in {
+def : Pat<(store (i16 0), addr:$dst), (AND16mi8 addr:$dst, 0)>;
+def : Pat<(store (i32 0), addr:$dst), (AND32mi8 addr:$dst, 0)>;
+def : Pat<(store (i64 0), addr:$dst), (AND64mi8 addr:$dst, 0)>;
+def : Pat<(store (i16 -1), addr:$dst), (OR16mi8 addr:$dst, -1)>;
+def : Pat<(store (i32 -1), addr:$dst), (OR32mi8 addr:$dst, -1)>;
+def : Pat<(store (i64 -1), addr:$dst), (OR64mi8 addr:$dst, -1)>;
+}
+
 // ConstantPool GlobalAddress, ExternalSymbol, and JumpTable
 def : Pat<(i32 (X86Wrapper tconstpool  :$dst)), (MOV32ri tconstpool  :$dst)>;
 def : Pat<(i32 (X86Wrapper tjumptable  :$dst)), (MOV32ri tjumptable  :$dst)>;
Index: lib/Target/X86/X86InstrInfo.td
===================================================================
--- lib/Target/X86/X86InstrInfo.td
+++ lib/Target/X86/X86InstrInfo.td
@@ -878,6 +878,7 @@
 def IsStatic     : Predicate<"TM.getRelocationModel() == Reloc::Static">;
 def IsNotPIC     : Predicate<"TM.getRelocationModel() != Reloc::PIC_">;
 def OptForSize   : Predicate<"OptForSize">;
+def OptForMinSize : Predicate<"OptForMinSize">;
 def OptForSpeed  : Predicate<"!OptForSize">;
 def FastBTMem    : Predicate<"!Subtarget->isBTMemSlow()">;
 def CallImmAddr  : Predicate<"Subtarget->IsLegalToCallImmediateAddr(TM)">;
Index: test/CodeGen/X86/store-zero.ll
===================================================================
--- /dev/null
+++ test/CodeGen/X86/store-zero.ll
@@ -0,0 +1,88 @@
+; RUN: llc -mtriple=i686-unknown-linux-gnu %s -o - | FileCheck %s --check-prefix=CHECK32 --check-prefix=CHECK
+; RUN: llc -mtriple=x86_64-unknown-linux-gnu %s -o - | FileCheck %s --check-prefix=CHECK64 --check-prefix=CHECK
+
+define void @zero_optsize(i32* %p) optsize {
+entry:
+  store i32 0, i32* %p
+  ret void
+
+; CHECK-LABEL: zero_optsize:
+; CHECK: movl $0
+; CHECK: ret
+}
+
+define void @minus_one_optsize(i32* %p) optsize {
+entry:
+  store i32 -1, i32* %p
+  ret void
+
+; CHECK-LABEL: minus_one_optsize:
+; CHECK: movl $-1
+; CHECK: ret
+}
+
+
+define void @zero_64(i64* %p) minsize {
+entry:
+  store i64 0, i64* %p
+  ret void
+
+; CHECK-LABEL: zero_64:
+; CHECK32: andl $0
+; CHECK32: andl $0
+; CHECK64: andq $0
+; CHECK: ret
+}
+
+define void @zero_32(i32* %p) minsize {
+entry:
+  store i32 0, i32* %p
+  ret void
+
+; CHECK-LABEL: zero_32:
+; CHECK: andl $0
+; CHECK: ret
+}
+
+define void @zero_16(i16* %p) minsize {
+entry:
+  store i16 0, i16* %p
+  ret void
+
+; CHECK-LABEL: zero_16:
+; CHECK: andw $0
+; CHECK: ret
+}
+
+
+define void @minus_one_64(i64* %p) minsize {
+entry:
+  store i64 -1, i64* %p
+  ret void
+
+; CHECK-LABEL: minus_one_64:
+; CHECK32: orl $-1
+; CHECK32: orl $-1
+; CHECK64: orq $-1
+; CHECK: ret
+}
+
+define void @minus_one_32(i32* %p) minsize {
+entry:
+  store i32 -1, i32* %p
+  ret void
+
+; CHECK-LABEL: minus_one_32:
+; CHECK: orl $-1
+; CHECK: ret
+}
+
+define void @minus_one_16(i16* %p) minsize {
+entry:
+  store i16 -1, i16* %p
+  ret void
+
+; CHECK-LABEL: minus_one_16:
+; CHECK: orw $-1
+; CHECK: ret
+}
Index: test/CodeGen/X86/tail-opts.ll
===================================================================
--- test/CodeGen/X86/tail-opts.ll
+++ test/CodeGen/X86/tail-opts.ll
@@ -376,7 +376,7 @@
 ; CHECK-LABEL: two_minsize:
 ; CHECK-NOT: XYZ
 ; CHECK: ret
-; CHECK: movl $0, XYZ(%rip)
+; CHECK: andl $0, XYZ(%rip)
 ; CHECK: movl $1, XYZ(%rip)
 ; CHECK-NOT: XYZ