diff --git a/llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp b/llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp
--- a/llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp
+++ b/llvm/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp
@@ -13,6 +13,7 @@
 
 #include "llvm/Transforms/Instrumentation/HWAddressSanitizer.h"
 #include "llvm/ADT/MapVector.h"
+#include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringExtras.h"
 #include "llvm/ADT/StringRef.h"
@@ -1301,6 +1302,11 @@
   return true;
 }
 
+static bool isLifetimeIntrinsic(Value *V) {
+  auto *II = dyn_cast<IntrinsicInst>(V);
+  return II && II->isLifetimeStartOrEnd();
+}
+
 bool HWAddressSanitizer::instrumentStack(
     memtag::StackInfo &SInfo, Value *StackTag,
     llvm::function_ref<const DominatorTree &()> GetDT,
@@ -1326,8 +1332,32 @@
         AI->hasName() ? AI->getName().str() : "alloca." + itostr(N);
     Replacement->setName(Name + ".hwasan");
 
-    AI->replaceUsesWithIf(Replacement,
-                          [AILong](Use &U) { return U.getUser() != AILong; });
+    size_t Size = memtag::getAllocaSizeInBytes(*AI);
+    size_t AlignedSize = alignTo(Size, Mapping.getObjectAlignment());
+
+    Value *AICast = IRB.CreatePointerCast(AI, Int8PtrTy);
+
+    auto HandleLifetime = [&](IntrinsicInst *II) {
+      // Set the lifetime intrinsic to cover the whole alloca. This reduces the
+      // set of assumptions we need to make about the lifetime. Without this we
+      // would need to ensure that we can track the lifetime pointer to a
+      // constant offset from the alloca, and would still need to change the
+      // size to include the extra alignment we use for the untagging to make
+      // the size consistent.
+      //
+      // The check for standard lifetime below makes sure that we have exactly
+      // one set of start / end in any execution (i.e. the ends are not
+      // reachable from each other), so this will not cause any problems.
+      II->setArgOperand(0, ConstantInt::get(Int64Ty, AlignedSize));
+      II->setArgOperand(1, AICast);
+    };
+    llvm::for_each(Info.LifetimeStart, HandleLifetime);
+    llvm::for_each(Info.LifetimeEnd, HandleLifetime);
+
+    AI->replaceUsesWithIf(Replacement, [AICast, AILong](Use &U) {
+      auto *User = U.getUser();
+      return User != AILong && User != AICast && !isLifetimeIntrinsic(User);
+    });
 
     for (auto *DDI : Info.DbgVariableIntrinsics) {
       // Prepend "tag_offset, N" to the dwarf expression.
@@ -1341,8 +1371,6 @@
                                                           NewOps, LocNo));
     }
 
-    size_t Size = memtag::getAllocaSizeInBytes(*AI);
-    size_t AlignedSize = alignTo(Size, Mapping.getObjectAlignment());
     auto TagEnd = [&](Instruction *Node) {
       IRB.SetInsertPoint(Node);
       Value *UARTag = getUARTag(IRB, StackTag);
diff --git a/llvm/test/Instrumentation/HWAddressSanitizer/exception-lifetime.ll b/llvm/test/Instrumentation/HWAddressSanitizer/exception-lifetime.ll
--- a/llvm/test/Instrumentation/HWAddressSanitizer/exception-lifetime.ll
+++ b/llvm/test/Instrumentation/HWAddressSanitizer/exception-lifetime.ll
@@ -21,11 +21,13 @@
   %0 = bitcast i32* %x to i8*
   call void @llvm.lifetime.start.p0i8(i64 8, i8* %0)
   invoke void @mayFail(i32* %x) to label %invoke.cont unwind label %lpad
+; CHECK: [[CAST:%.*]] = bitcast { i32, [12 x i8] }* %x to i32*
+; CHECK: [[TMP1:%.*]] = bitcast i32* {{.*}}[[CAST]] to i8*
 
 invoke.cont:                                      ; preds = %entry
 ; CHECK: invoke.cont:
-; CHECK:  call void @llvm.memset.p0i8.i64(i8* align 1 %31, i8 0, i64 1, i1 false)
-; CHECK:  call void @llvm.lifetime.end.p0i8(i64 8, i8* %28)
+; CHECK:  call void @llvm.memset.p0i8.i64(i8* align 1 %{{.*}}, i8 0, i64 1, i1 false)
+; CHECK:  call void @llvm.lifetime.end.p0i8(i64 16, i8* {{.*}}[[TMP1]])
 ; CHECK:  ret void
 
   %1 = bitcast i32* %x to i8*
@@ -34,9 +36,8 @@
 
 lpad:                                             ; preds = %entry
 ; CHECK: lpad
-; CHECK:  %41 = getelementptr i8, i8* %17, i64 %40
-; CHECK:  call void @llvm.memset.p0i8.i64(i8* align 1 %41, i8 0, i64 1, i1 false)
-; CHECK:  call void @llvm.lifetime.end.p0i8(i64 8, i8* %38)
+; CHECK:  call void @llvm.memset.p0i8.i64(i8* align 1 %{{.*}}, i8 0, i64 1, i1 false)
+; CHECK:  call void @llvm.lifetime.end.p0i8(i64 16, i8* {{.*}}[[TMP1]])
 ; CHECK:  br label %eh.resume
 
   %2 = landingpad { i8*, i32 }
diff --git a/llvm/test/Instrumentation/HWAddressSanitizer/stack-coloring.ll b/llvm/test/Instrumentation/HWAddressSanitizer/stack-coloring.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/Instrumentation/HWAddressSanitizer/stack-coloring.ll
@@ -0,0 +1,41 @@
+; Test that storage for allocas with disjoint lifetimes is reused with
+; use-after-scope.
+
+; RUN: opt -S -passes=hwasan %s -hwasan-use-after-scope -o - | \
+; RUN:   llc -no-stack-coloring=false -o - | \
+; RUN:   FileCheck %s --check-prefix=COLOR
+; RUN: opt -S -passes=hwasan -hwasan-use-after-scope %s -o - | \
+; RUN:   llc -no-stack-coloring=true -o - | \
+; RUN:   FileCheck %s --check-prefix=NOCOLOR
+
+target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
+target triple = "aarch64-unknown-linux-android29"
+
+; COLOR: sub	sp, sp, #240
+; NOCOLOR: sub	sp, sp, #368
+
+define i32 @myCall_w2(i32 %in) sanitize_hwaddress {
+entry:
+  %a = alloca [17 x i8*], align 8
+  %a2 = alloca [16 x i8*], align 8
+  %b = bitcast [17 x i8*]* %a to i8*
+  %b2 = bitcast [16 x i8*]* %a2 to i8*
+  call void @llvm.lifetime.start.p0i8(i64 136, i8* %b)
+  %t1 = call i32 @foo(i32 %in, i8* %b)
+  %t2 = call i32 @foo(i32 %in, i8* %b)
+  call void @llvm.lifetime.end.p0i8(i64 136, i8* %b)
+  call void @llvm.lifetime.start.p0i8(i64 128, i8* %b2)
+  %t3 = call i32 @foo(i32 %in, i8* %b2)
+  %t4 = call i32 @foo(i32 %in, i8* %b2)
+  call void @llvm.lifetime.end.p0i8(i64 128, i8* %b2)
+  %t5 = add i32 %t1, %t2
+  %t6 = add i32 %t3, %t4
+  %t7 = add i32 %t5, %t6
+  ret i32 %t7
+}
+
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture) nounwind
+
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture) nounwind
+
+declare i32 @foo(i32, i8*)
diff --git a/llvm/test/Instrumentation/HWAddressSanitizer/use-after-scope.ll b/llvm/test/Instrumentation/HWAddressSanitizer/use-after-scope.ll
--- a/llvm/test/Instrumentation/HWAddressSanitizer/use-after-scope.ll
+++ b/llvm/test/Instrumentation/HWAddressSanitizer/use-after-scope.ll
@@ -35,12 +35,12 @@
 ; X86-SCOPE-NEXT:    [[ALLOCA_0_HWASAN:%.*]] = inttoptr i64 [[TMP7]] to i8*
 ; X86-SCOPE-NEXT:    br label [[TMP8:%.*]]
 ; X86-SCOPE:       8:
-; X86-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; X86-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[TMP2]])
 ; X86-SCOPE-NEXT:    [[TMP9:%.*]] = trunc i64 [[TMP4]] to i8
 ; X86-SCOPE-NEXT:    call void @__hwasan_tag_memory(i8* [[TMP2]], i8 [[TMP9]], i64 16)
 ; X86-SCOPE-NEXT:    [[TMP10:%.*]] = tail call i1 (...) @cond()
 ; X86-SCOPE-NEXT:    call void @__hwasan_tag_memory(i8* [[TMP2]], i8 0, i64 16)
-; X86-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; X86-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull [[TMP2]])
 ; X86-SCOPE-NEXT:    br i1 [[TMP10]], label [[TMP11:%.*]], label [[TMP8]]
 ; X86-SCOPE:       11:
 ; X86-SCOPE-NEXT:    call void @use(i8* nonnull [[ALLOCA_0_HWASAN]])
@@ -99,7 +99,7 @@
 ; AARCH64-SCOPE-NEXT:    [[ALLOCA_0_HWASAN:%.*]] = inttoptr i64 [[TMP25]] to i8*
 ; AARCH64-SCOPE-NEXT:    br label [[TMP26:%.*]]
 ; AARCH64-SCOPE:       26:
-; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SCOPE-NEXT:    [[TMP27:%.*]] = trunc i64 [[TMP22]] to i8
 ; AARCH64-SCOPE-NEXT:    [[TMP28:%.*]] = ptrtoint i8* [[TMP20]] to i64
 ; AARCH64-SCOPE-NEXT:    [[TMP29:%.*]] = lshr i64 [[TMP28]], 4
@@ -110,7 +110,7 @@
 ; AARCH64-SCOPE-NEXT:    [[TMP33:%.*]] = lshr i64 [[TMP32]], 4
 ; AARCH64-SCOPE-NEXT:    [[TMP34:%.*]] = getelementptr i8, i8* [[TMP18]], i64 [[TMP33]]
 ; AARCH64-SCOPE-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[TMP34]], i8 0, i64 1, i1 false)
-; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SCOPE-NEXT:    br i1 [[TMP31]], label [[TMP35:%.*]], label [[TMP26]]
 ; AARCH64-SCOPE:       35:
 ; AARCH64-SCOPE-NEXT:    call void @use(i8* nonnull [[ALLOCA_0_HWASAN]])
@@ -195,7 +195,7 @@
 ; AARCH64-SHORT-SCOPE-NEXT:    [[ALLOCA_0_HWASAN:%.*]] = inttoptr i64 [[TMP25]] to i8*
 ; AARCH64-SHORT-SCOPE-NEXT:    br label [[TMP26:%.*]]
 ; AARCH64-SHORT-SCOPE:       26:
-; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP27:%.*]] = trunc i64 [[TMP22]] to i8
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP28:%.*]] = ptrtoint i8* [[TMP20]] to i64
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP29:%.*]] = lshr i64 [[TMP28]], 4
@@ -209,7 +209,7 @@
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP35:%.*]] = lshr i64 [[TMP34]], 4
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP36:%.*]] = getelementptr i8, i8* [[TMP18]], i64 [[TMP35]]
 ; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[TMP36]], i8 0, i64 1, i1 false)
-; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SHORT-SCOPE-NEXT:    br i1 [[TMP33]], label [[TMP37:%.*]], label [[TMP26]]
 ; AARCH64-SHORT-SCOPE:       37:
 ; AARCH64-SHORT-SCOPE-NEXT:    call void @use(i8* nonnull [[ALLOCA_0_HWASAN]])
@@ -294,12 +294,12 @@
 ; X86-SCOPE-NEXT:    [[ALLOCA_0_HWASAN:%.*]] = inttoptr i64 [[TMP7]] to i8*
 ; X86-SCOPE-NEXT:    br label [[TMP8:%.*]]
 ; X86-SCOPE:       8:
-; X86-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; X86-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[TMP2]])
 ; X86-SCOPE-NEXT:    [[TMP9:%.*]] = trunc i64 [[TMP4]] to i8
 ; X86-SCOPE-NEXT:    call void @__hwasan_tag_memory(i8* [[TMP2]], i8 [[TMP9]], i64 16)
 ; X86-SCOPE-NEXT:    [[TMP10:%.*]] = tail call i1 (...) @cond()
 ; X86-SCOPE-NEXT:    call void @__hwasan_tag_memory(i8* [[TMP2]], i8 0, i64 16)
-; X86-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; X86-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull [[TMP2]])
 ; X86-SCOPE-NEXT:    br i1 [[TMP10]], label [[TMP11:%.*]], label [[TMP8]]
 ; X86-SCOPE:       11:
 ; X86-SCOPE-NEXT:    call void @use(i8* nonnull [[ALLOCA_0_HWASAN]])
@@ -358,7 +358,7 @@
 ; AARCH64-SCOPE-NEXT:    [[ALLOCA_0_HWASAN:%.*]] = inttoptr i64 [[TMP25]] to i8*
 ; AARCH64-SCOPE-NEXT:    br label [[TMP26:%.*]]
 ; AARCH64-SCOPE:       26:
-; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SCOPE-NEXT:    [[TMP27:%.*]] = trunc i64 [[TMP22]] to i8
 ; AARCH64-SCOPE-NEXT:    [[TMP28:%.*]] = ptrtoint i8* [[TMP20]] to i64
 ; AARCH64-SCOPE-NEXT:    [[TMP29:%.*]] = lshr i64 [[TMP28]], 4
@@ -369,7 +369,7 @@
 ; AARCH64-SCOPE-NEXT:    [[TMP33:%.*]] = lshr i64 [[TMP32]], 4
 ; AARCH64-SCOPE-NEXT:    [[TMP34:%.*]] = getelementptr i8, i8* [[TMP18]], i64 [[TMP33]]
 ; AARCH64-SCOPE-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[TMP34]], i8 0, i64 1, i1 false)
-; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SCOPE-NEXT:    br i1 [[TMP31]], label [[TMP35:%.*]], label [[TMP26]]
 ; AARCH64-SCOPE:       35:
 ; AARCH64-SCOPE-NEXT:    call void @use(i8* nonnull [[ALLOCA_0_HWASAN]])
@@ -454,7 +454,7 @@
 ; AARCH64-SHORT-SCOPE-NEXT:    [[ALLOCA_0_HWASAN:%.*]] = inttoptr i64 [[TMP25]] to i8*
 ; AARCH64-SHORT-SCOPE-NEXT:    br label [[TMP26:%.*]]
 ; AARCH64-SHORT-SCOPE:       26:
-; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP27:%.*]] = trunc i64 [[TMP22]] to i8
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP28:%.*]] = ptrtoint i8* [[TMP20]] to i64
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP29:%.*]] = lshr i64 [[TMP28]], 4
@@ -468,7 +468,7 @@
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP35:%.*]] = lshr i64 [[TMP34]], 4
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP36:%.*]] = getelementptr i8, i8* [[TMP18]], i64 [[TMP35]]
 ; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.memset.p0i8.i64(i8* align 1 [[TMP36]], i8 0, i64 1, i1 false)
-; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.end.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SHORT-SCOPE-NEXT:    br i1 [[TMP33]], label [[TMP37:%.*]], label [[TMP26]]
 ; AARCH64-SHORT-SCOPE:       37:
 ; AARCH64-SHORT-SCOPE-NEXT:    call void @use(i8* nonnull [[ALLOCA_0_HWASAN]])
@@ -776,7 +776,7 @@
 ; X86-SCOPE-NEXT:    [[TMP6:%.*]] = shl i64 [[TMP4]], 57
 ; X86-SCOPE-NEXT:    [[TMP7:%.*]] = or i64 [[TMP5]], [[TMP6]]
 ; X86-SCOPE-NEXT:    [[ALLOCA_0_HWASAN:%.*]] = inttoptr i64 [[TMP7]] to i8*
-; X86-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; X86-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[TMP2]])
 ; X86-SCOPE-NEXT:    [[TMP8:%.*]] = trunc i64 [[TMP4]] to i8
 ; X86-SCOPE-NEXT:    call void @__hwasan_tag_memory(i8* [[TMP2]], i8 [[TMP8]], i64 16)
 ; X86-SCOPE-NEXT:    [[TMP9:%.*]] = tail call i1 (...) @cond()
@@ -841,7 +841,7 @@
 ; AARCH64-SCOPE-NEXT:    [[TMP24:%.*]] = shl i64 [[TMP22]], 56
 ; AARCH64-SCOPE-NEXT:    [[TMP25:%.*]] = or i64 [[TMP23]], [[TMP24]]
 ; AARCH64-SCOPE-NEXT:    [[ALLOCA_0_HWASAN:%.*]] = inttoptr i64 [[TMP25]] to i8*
-; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SCOPE-NEXT:    [[TMP26:%.*]] = trunc i64 [[TMP22]] to i8
 ; AARCH64-SCOPE-NEXT:    [[TMP27:%.*]] = ptrtoint i8* [[TMP20]] to i64
 ; AARCH64-SCOPE-NEXT:    [[TMP28:%.*]] = lshr i64 [[TMP27]], 4
@@ -944,7 +944,7 @@
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP24:%.*]] = shl i64 [[TMP22]], 56
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP25:%.*]] = or i64 [[TMP23]], [[TMP24]]
 ; AARCH64-SHORT-SCOPE-NEXT:    [[ALLOCA_0_HWASAN:%.*]] = inttoptr i64 [[TMP25]] to i8*
-; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 1, i8* nonnull [[ALLOCA_0_HWASAN]])
+; AARCH64-SHORT-SCOPE-NEXT:    call void @llvm.lifetime.start.p0i8(i64 16, i8* nonnull [[TMP20]])
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP26:%.*]] = trunc i64 [[TMP22]] to i8
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP27:%.*]] = ptrtoint i8* [[TMP20]] to i64
 ; AARCH64-SHORT-SCOPE-NEXT:    [[TMP28:%.*]] = lshr i64 [[TMP27]], 4