Index: compiler-rt/trunk/lib/hwasan/hwasan_thread.cpp
===================================================================
--- compiler-rt/trunk/lib/hwasan/hwasan_thread.cpp
+++ compiler-rt/trunk/lib/hwasan/hwasan_thread.cpp
@@ -27,6 +27,11 @@
 
 void Thread::InitRandomState() {
   random_state_ = flags()->random_tags ? RandomSeed() : unique_id_;
+
+  // Push a random number of zeros onto the ring buffer so that the first stack
+  // tag base will be random.
+  for (tag_t i = 0, e = GenerateRandomTag(); i != e; ++i)
+    stack_allocations_->push(0);
 }
 
 void Thread::Init(uptr stack_buffer_start, uptr stack_buffer_size) {
Index: compiler-rt/trunk/test/hwasan/TestCases/random-align-right.c
===================================================================
--- compiler-rt/trunk/test/hwasan/TestCases/random-align-right.c
+++ compiler-rt/trunk/test/hwasan/TestCases/random-align-right.c
@@ -1,9 +1,11 @@
 // Tests malloc_align_right=1 and 8 (randomly aligning right).
 // RUN: %clang_hwasan  %s -o %t
 //
-// RUN: %run %t
-// RUN: %env_hwasan_opts=malloc_align_right=1 not %run %t 2>&1 | FileCheck %s --check-prefix=CHECK1
-// RUN: %env_hwasan_opts=malloc_align_right=8 not %run %t 2>&1 | FileCheck %s --check-prefix=CHECK8
+// RUN: %run %t 20
+// RUN: %run %t 30
+// RUN: %env_hwasan_opts=malloc_align_right=1 not %run %t 20 2>&1 | FileCheck %s --check-prefix=CHECK20
+// RUN: %env_hwasan_opts=malloc_align_right=1 not %run %t 30 2>&1 | FileCheck %s --check-prefix=CHECK30
+// RUN: %env_hwasan_opts=malloc_align_right=8 not %run %t 30 2>&1 | FileCheck %s --check-prefix=CHECK30
 
 // REQUIRES: stable-runtime
 
@@ -15,6 +17,7 @@
 
 int main(int argc, char **argv) {
   __hwasan_enable_allocator_tagging();
+  int index = atoi(argv[1]);
 
   // Perform 1000 buffer overflows within the 16-byte granule,
   // so that random right-alignment has a very high chance of
@@ -22,14 +25,11 @@
   for (int i = 0; i < 1000; i++) {
     char *p = (char*)malloc(20);
     sink = p;
-    fprintf(stderr, "[%d] p: %p; accessing p[20]:\n", i, p);
-    p[20 * argc] = 0;  // requires malloc_align_right=1 to catch
-    fprintf(stderr, "[%d] p: %p; accessing p[30]:\n", i, p);
-    p[30 * argc] = 0;  // requires malloc_align_right={1,8} to catch
-// CHECK1: accessing p[20]
-// CHECK1-NEXT: HWAddressSanitizer: tag-mismatch
-// CHECK8: accessing p[30]:
-// CHECK8-NEXT: HWAddressSanitizer: tag-mismatch
+    p[index] = 0;
+// index=20 requires malloc_align_right=1 to catch
+// CHECK20: HWAddressSanitizer: tag-mismatch
+// index=30 requires malloc_align_right={1,8} to catch
+// CHECK30: HWAddressSanitizer: tag-mismatch
   }
 }
 
Index: compiler-rt/trunk/test/hwasan/TestCases/stack-history-length.c
===================================================================
--- compiler-rt/trunk/test/hwasan/TestCases/stack-history-length.c
+++ compiler-rt/trunk/test/hwasan/TestCases/stack-history-length.c
@@ -1,5 +1,5 @@
 // RUN: %clang_hwasan -O1 %s -o %t
-// RUN: %env_hwasan_opts=stack_history_size=2048 not %run %t 2046 2>&1 | FileCheck %s --check-prefix=YES
+// RUN: %env_hwasan_opts=stack_history_size=2048 not %run %t 2045 2>&1 | FileCheck %s --check-prefix=YES
 // RUN: %env_hwasan_opts=stack_history_size=2048 not %run %t 2047 2>&1 | FileCheck %s --check-prefix=NO
 
 // REQUIRES: stable-runtime
@@ -22,6 +22,9 @@
   FUNC0();
   for (int i = 0; i < X; ++i)
     FUNC();
+  // Make at least one call to OOB where base tag != 0 so that the bug is caught
+  // at least once.
+  OOB();
   OOB();
 }
 
Index: compiler-rt/trunk/test/hwasan/lit.cfg
===================================================================
--- compiler-rt/trunk/test/hwasan/lit.cfg
+++ compiler-rt/trunk/test/hwasan/lit.cfg
@@ -11,7 +11,7 @@
 # Setup default compiler flags used with -fsanitize=memory option.
 clang_cflags = [config.target_cflags] + config.debug_info_flags
 clang_cxxflags = config.cxx_mode_flags + clang_cflags
-clang_hwasan_cflags = ["-fsanitize=hwaddress", "-mllvm", "-hwasan-generate-tags-with-calls"] + clang_cflags
+clang_hwasan_cflags = ["-fsanitize=hwaddress"] + clang_cflags
 clang_hwasan_cxxflags = config.cxx_mode_flags + clang_hwasan_cflags
 
 def build_invocation(compile_flags):
Index: llvm/trunk/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp
===================================================================
--- llvm/trunk/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp
+++ llvm/trunk/lib/Transforms/Instrumentation/HWAddressSanitizer.cpp
@@ -218,7 +218,7 @@
   Value *getUARTag(IRBuilder<> &IRB, Value *StackTag);
 
   Value *getHwasanThreadSlotPtr(IRBuilder<> &IRB, Type *Ty);
-  Value *emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord);
+  void emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord);
 
 private:
   LLVMContext *C;
@@ -284,6 +284,7 @@
   Constant *ShadowGlobal;
 
   Value *LocalDynamicShadow = nullptr;
+  Value *StackBaseTag = nullptr;
   GlobalValue *ThreadPtrGlobal = nullptr;
 };
 
@@ -750,10 +751,16 @@
   // x = x ^ (mask << 56) can be encoded as a single armv8 instruction for these
   // masks.
   // The list does not include the value 255, which is used for UAR.
-  static unsigned FastMasks[] = {
-      0,   1,   2,   3,   4,   6,   7,   8,   12,  14,  15, 16,  24,
-      28,  30,  31,  32,  48,  56,  60,  62,  63,  64,  96, 112, 120,
-      124, 126, 127, 128, 192, 224, 240, 248, 252, 254};
+  //
+  // Because we are more likely to use earlier elements of this list than later
+  // ones, it is sorted in increasing order of probability of collision with a
+  // mask allocated (temporally) nearby. The program that generated this list
+  // can be found at:
+  // https://github.com/google/sanitizers/blob/master/hwaddress-sanitizer/sort_masks.py
+  static unsigned FastMasks[] = {0,  128, 64,  192, 32,  96,  224, 112, 240,
+                                 48, 16,  120, 248, 56,  24,  8,   124, 252,
+                                 60, 28,  12,  4,   126, 254, 62,  30,  14,
+                                 6,  2,   127, 63,  31,  15,  7,   3,   1};
   return FastMasks[AllocaNo % (sizeof(FastMasks) / sizeof(FastMasks[0]))];
 }
 
@@ -764,6 +771,8 @@
 Value *HWAddressSanitizer::getStackBaseTag(IRBuilder<> &IRB) {
   if (ClGenerateTagsWithCalls)
     return getNextTagWithCall(IRB);
+  if (StackBaseTag)
+    return StackBaseTag;
   // FIXME: use addressofreturnaddress (but implement it in aarch64 backend
   // first).
   Module *M = IRB.GetInsertBlock()->getParent()->getParent();
@@ -881,13 +890,16 @@
     GV->setComdat(Comdat);
 }
 
-Value *HWAddressSanitizer::emitPrologue(IRBuilder<> &IRB,
-                                        bool WithFrameRecord) {
-  if (!Mapping.InTls)
-    return getDynamicShadowNonTls(IRB);
+void HWAddressSanitizer::emitPrologue(IRBuilder<> &IRB, bool WithFrameRecord) {
+  if (!Mapping.InTls) {
+    LocalDynamicShadow = getDynamicShadowNonTls(IRB);
+    return;
+  }
 
-  if (!WithFrameRecord && TargetTriple.isAndroid())
-    return getDynamicShadowIfunc(IRB);
+  if (!WithFrameRecord && TargetTriple.isAndroid()) {
+    LocalDynamicShadow = getDynamicShadowIfunc(IRB);
+    return;
+  }
 
   Value *SlotPtr = getHwasanThreadSlotPtr(IRB, IntptrTy);
   assert(SlotPtr);
@@ -920,6 +932,8 @@
       TargetTriple.isAArch64() ? ThreadLong : untagPointer(IRB, ThreadLong);
 
   if (WithFrameRecord) {
+    StackBaseTag = IRB.CreateAShr(ThreadLong, 3);
+
     // Prepare ring buffer data.
     auto PC = IRB.CreatePtrToInt(F, IntptrTy);
     auto GetStackPointerFn =
@@ -928,7 +942,7 @@
         IRB.CreateCall(GetStackPointerFn,
                        {Constant::getNullValue(IRB.getInt32Ty())}),
         IntptrTy);
-    // Mix SP and PC. TODO: also add the tag to the mix.
+    // Mix SP and PC.
     // Assumptions:
     // PC is 0x0000PPPPPPPPPPPP  (48 bits are meaningful, others are zero)
     // SP is 0xsssssssssssSSSS0  (4 lower bits are zero)
@@ -959,13 +973,12 @@
   // Get shadow base address by aligning RecordPtr up.
   // Note: this is not correct if the pointer is already aligned.
   // Runtime library will make sure this never happens.
-  Value *ShadowBase = IRB.CreateAdd(
+  LocalDynamicShadow = IRB.CreateAdd(
       IRB.CreateOr(
           ThreadLongMaybeUntagged,
           ConstantInt::get(IntptrTy, (1ULL << kShadowBaseAlignment) - 1)),
       ConstantInt::get(IntptrTy, 1), "hwasan.shadow");
-  ShadowBase = IRB.CreateIntToPtr(ShadowBase, Int8PtrTy);
-  return ShadowBase;
+  LocalDynamicShadow = IRB.CreateIntToPtr(LocalDynamicShadow, Int8PtrTy);
 }
 
 bool HWAddressSanitizer::instrumentLandingPads(
@@ -1115,9 +1128,9 @@
 
   Instruction *InsertPt = &*F.getEntryBlock().begin();
   IRBuilder<> EntryIRB(InsertPt);
-  LocalDynamicShadow = emitPrologue(EntryIRB,
-                                    /*WithFrameRecord*/ ClRecordStackHistory &&
-                                        !AllocasToInstrument.empty());
+  emitPrologue(EntryIRB,
+               /*WithFrameRecord*/ ClRecordStackHistory &&
+                   !AllocasToInstrument.empty());
 
   bool Changed = false;
   if (!AllocasToInstrument.empty()) {
@@ -1146,6 +1159,7 @@
     Changed |= instrumentMemAccess(Inst);
 
   LocalDynamicShadow = nullptr;
+  StackBaseTag = nullptr;
 
   return Changed;
 }
Index: llvm/trunk/test/Instrumentation/HWAddressSanitizer/dbg-declare-tag-offset.ll
===================================================================
--- llvm/trunk/test/Instrumentation/HWAddressSanitizer/dbg-declare-tag-offset.ll
+++ llvm/trunk/test/Instrumentation/HWAddressSanitizer/dbg-declare-tag-offset.ll
@@ -13,13 +13,13 @@
   %nodebug3 = alloca i8*
   %a = alloca i8*
   %b = alloca i8*
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 4)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 32)
   call void @llvm.dbg.declare(metadata i8** %a, metadata !12, metadata !DIExpression()), !dbg !14
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 4)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 32)
   call void @llvm.dbg.declare(metadata i8** %a, metadata !12, metadata !DIExpression()), !dbg !14
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 6)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 96)
   call void @llvm.dbg.declare(metadata i8** %b, metadata !13, metadata !DIExpression()), !dbg !14
-  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 6)
+  ; CHECK: @llvm.dbg.declare{{.*}} !DIExpression(DW_OP_LLVM_tag_offset, 96)
   call void @llvm.dbg.declare(metadata i8** %b, metadata !13, metadata !DIExpression()), !dbg !14
   call void @g(i8** %nodebug0, i8** %nodebug1, i8** %nodebug2, i8** %nodebug3, i8** %a, i8** %b)
   ret void, !dbg !15
Index: llvm/trunk/test/Instrumentation/HWAddressSanitizer/prologue.ll
===================================================================
--- llvm/trunk/test/Instrumentation/HWAddressSanitizer/prologue.ll
+++ llvm/trunk/test/Instrumentation/HWAddressSanitizer/prologue.ll
@@ -56,6 +56,7 @@
 ; CHECK-TLS:   %[[B:[^ ]*]] = getelementptr i8, i8* %[[A]], i32 48
 ; CHECK-TLS:   %[[C:[^ ]*]] = bitcast i8* %[[B]] to i64*
 ; CHECK-TLS:   %[[D:[^ ]*]] = load i64, i64* %[[C]]
+; CHECK-TLS:   %[[E:[^ ]*]] = ashr i64 %[[D]], 3
 
 ; CHECK-NOHISTORY-NOT: store i64
 
@@ -68,8 +69,10 @@
 ; CHECK-HISTORY: %[[D5:[^ ]*]] = and i64 %[[D4]], %[[D3]]
 ; CHECK-HISTORY: store i64 %[[D5]], i64* %[[C]]
 
-; CHECK-TLS:   %[[E:[^ ]*]] = or i64 %[[D]], 4294967295
-; CHECK-TLS:   = add i64 %[[E]], 1
+; CHECK-TLS:   %[[F:[^ ]*]] = or i64 %[[D]], 4294967295
+; CHECK-TLS:   = add i64 %[[F]], 1
+
+; CHECK-HISTORY: = xor i64 %[[E]], 0
 
 ; CHECK-NOHISTORY-NOT: store i64