diff --git a/src/compiler_llvm/backend_types.h b/src/compiler_llvm/backend_types.h
index bf5a413..ede21c1 100644
--- a/src/compiler_llvm/backend_types.h
+++ b/src/compiler_llvm/backend_types.h
@@ -55,6 +55,16 @@
 };
 
 
+enum TBAASpecialType {
+  kTBAARegister,
+  kTBAAStackTemp,
+  kTBAAMemory,
+  kTBAARuntimeInfo,
+  kTBAAConstJObject,
+  MAX_TBAA_SPECIAL_TYPE
+};
+
+
 inline JType GetJTypeFromShorty(char shorty_jty) {
   switch (shorty_jty) {
   case 'V':
diff --git a/src/compiler_llvm/dalvik_reg.cc b/src/compiler_llvm/dalvik_reg.cc
index 0ed6089..3d87a43 100644
--- a/src/compiler_llvm/dalvik_reg.cc
+++ b/src/compiler_llvm/dalvik_reg.cc
@@ -132,7 +132,7 @@
   switch (space) {
   case kReg:
   case kField:
-    return irb_.CreateLoad(GetAddr(jty, space));
+    return irb_.CreateLoad(GetAddr(jty, space), kTBAARegister);
 
   case kAccurate:
   case kArray:
@@ -148,7 +148,7 @@
       // NOTE: In array type space, boolean is truncated from i32 to i8, while
       // in accurate type space, boolean is truncated from i32 to i1.
       // For the other cases, array type space is equal to accurate type space.
-      return RegCat1Trunc(irb_.CreateLoad(GetAddr(jty, space)),
+      return RegCat1Trunc(irb_.CreateLoad(GetAddr(jty, space), kTBAARegister),
                           irb_.getJType(jty, space));
 
     case kInt:
@@ -156,7 +156,7 @@
     case kFloat:
     case kDouble:
     case kObject:
-      return irb_.CreateLoad(GetAddr(jty, space));
+      return irb_.CreateLoad(GetAddr(jty, space), kTBAARegister);
     }
   }
 
@@ -171,7 +171,7 @@
   switch (space) {
   case kReg:
   case kField:
-    irb_.CreateStore(value, GetAddr(jty, space));
+    irb_.CreateStore(value, GetAddr(jty, space), kTBAARegister);
     return;
 
   case kAccurate:
@@ -185,7 +185,7 @@
       // NOTE: In accurate type space, we have to zero extend boolean from
       // i1 to i32, and char from i16 to i32.  In array type space, we have
       // to zero extend boolean from i8 to i32, and char from i16 to i32.
-      irb_.CreateStore(RegCat1ZExt(value), GetAddr(jty, space));
+      irb_.CreateStore(RegCat1ZExt(value), GetAddr(jty, space), kTBAARegister);
       break;
 
     case kByte:
@@ -193,7 +193,7 @@
       // NOTE: In accurate type space, we have to signed extend byte from
       // i8 to i32, and short from i16 to i32.  In array type space, we have
       // to sign extend byte from i8 to i32, and short from i16 to i32.
-      irb_.CreateStore(RegCat1SExt(value), GetAddr(jty, space));
+      irb_.CreateStore(RegCat1SExt(value), GetAddr(jty, space), kTBAARegister);
       break;
 
     case kInt:
@@ -201,7 +201,7 @@
     case kFloat:
     case kDouble:
     case kObject:
-      irb_.CreateStore(value, GetAddr(jty, space));
+      irb_.CreateStore(value, GetAddr(jty, space), kTBAARegister);
       break;
     }
   }
@@ -242,7 +242,7 @@
   if (jty == kObject) {
     DCHECK_NE(reg_shadow_frame_, static_cast<llvm::Value*>(NULL))
       << "Didn't allocate shadow frame entry.";
-    irb_.CreateStore(value, reg_shadow_frame_);
+    irb_.CreateStore(value, reg_shadow_frame_, kTBAARuntimeInfo);
   }
 }
 
diff --git a/src/compiler_llvm/ir_builder.cc b/src/compiler_llvm/ir_builder.cc
index 4afb8bc..998ec04 100644
--- a/src/compiler_llvm/ir_builder.cc
+++ b/src/compiler_llvm/ir_builder.cc
@@ -28,7 +28,7 @@
 //----------------------------------------------------------------------------
 
 IRBuilder::IRBuilder(llvm::LLVMContext& context, llvm::Module& module)
-: LLVMIRBuilder(context), module_(&module) {
+: LLVMIRBuilder(context), module_(&module), tbaa_(context) {
 
   // Get java object type from module
   llvm::Type* jobject_struct_type = module.getTypeByName("JavaObject");
diff --git a/src/compiler_llvm/ir_builder.h b/src/compiler_llvm/ir_builder.h
index 8a1bbc4..4dbc1b5 100644
--- a/src/compiler_llvm/ir_builder.h
+++ b/src/compiler_llvm/ir_builder.h
@@ -20,9 +20,11 @@
 #include "backend_types.h"
 #include "runtime_support_builder.h"
 #include "runtime_support_func.h"
+#include "tbaa_info.h"
 
 #include <llvm/Constants.h>
 #include <llvm/DerivedTypes.h>
+#include <llvm/LLVMContext.h>
 #include <llvm/Support/IRBuilder.h>
 #include <llvm/Type.h>
 
@@ -48,6 +50,53 @@
 
 
   //--------------------------------------------------------------------------
+  // Extend load & store for TBAA
+  //--------------------------------------------------------------------------
+
+  llvm::LoadInst* CreateLoad(llvm::Value* ptr, llvm::MDNode* tbaa_info) {
+    llvm::LoadInst* inst = LLVMIRBuilder::CreateLoad(ptr);
+    inst->setMetadata(llvm::LLVMContext::MD_tbaa, tbaa_info);
+    return inst;
+  }
+
+  llvm::StoreInst* CreateStore(llvm::Value* val, llvm::Value* ptr, llvm::MDNode* tbaa_info) {
+    llvm::StoreInst* inst = LLVMIRBuilder::CreateStore(val, ptr);
+    inst->setMetadata(llvm::LLVMContext::MD_tbaa, tbaa_info);
+    return inst;
+  }
+
+
+  //--------------------------------------------------------------------------
+  // TBAA
+  //--------------------------------------------------------------------------
+
+  // TODO: After we design the non-special TBAA info, re-design the TBAA interface.
+  llvm::LoadInst* CreateLoad(llvm::Value* ptr, TBAASpecialType special_ty) {
+    return CreateLoad(ptr, tbaa_.GetSpecialType(special_ty));
+  }
+
+  llvm::StoreInst* CreateStore(llvm::Value* val, llvm::Value* ptr, TBAASpecialType special_ty) {
+    DCHECK_NE(special_ty, kTBAAConstJObject) << "ConstJObject is read only!";
+    return CreateStore(val, ptr, tbaa_.GetSpecialType(special_ty));
+  }
+
+  llvm::Value* LoadFromObjectOffset(llvm::Value* object_addr,
+                                    int64_t offset,
+                                    llvm::Type* type,
+                                    TBAASpecialType special_ty) {
+    return LoadFromObjectOffset(object_addr, offset, type, tbaa_.GetSpecialType(special_ty));
+  }
+
+  void StoreToObjectOffset(llvm::Value* object_addr,
+                           int64_t offset,
+                           llvm::Value* new_value,
+                           TBAASpecialType special_ty) {
+    DCHECK_NE(special_ty, kTBAAConstJObject) << "ConstJObject is read only!";
+    StoreToObjectOffset(object_addr, offset, new_value, tbaa_.GetSpecialType(special_ty));
+  }
+
+
+  //--------------------------------------------------------------------------
   // Pointer Arithmetic Helper Function
   //--------------------------------------------------------------------------
 
@@ -90,16 +139,22 @@
     return CreatePtrDisp(base, total_offset, ret_ty);
   }
 
-  llvm::Value* LoadFromObjectOffset(llvm::Value* object_addr, int64_t offset, llvm::Type* type) {
+  llvm::Value* LoadFromObjectOffset(llvm::Value* object_addr,
+                                    int64_t offset,
+                                    llvm::Type* type,
+                                    llvm::MDNode* tbaa_info) {
     // Convert offset to llvm::value
     llvm::Value* llvm_offset = getPtrEquivInt(offset);
     // Calculate the value's address
     llvm::Value* value_addr = CreatePtrDisp(object_addr, llvm_offset, type->getPointerTo());
     // Load
-    return CreateLoad(value_addr);
+    return CreateLoad(value_addr, tbaa_info);
   }
 
-  void StoreToObjectOffset(llvm::Value* object_addr, int64_t offset, llvm::Value* new_value) {
+  void StoreToObjectOffset(llvm::Value* object_addr,
+                           int64_t offset,
+                           llvm::Value* new_value,
+                           llvm::MDNode* tbaa_info) {
     // Convert offset to llvm::value
     llvm::Value* llvm_offset = getPtrEquivInt(offset);
     // Calculate the value's address
@@ -107,7 +162,7 @@
                                             llvm_offset,
                                             new_value->getType()->getPointerTo());
     // Store
-    CreateStore(new_value, value_addr);
+    CreateStore(new_value, value_addr, tbaa_info);
   }
 
 
@@ -310,6 +365,8 @@
 
   llvm::StructType* art_frame_type_;
 
+  TBAAInfo tbaa_;
+
   RuntimeSupportBuilder* runtime_support_;
 
 };
diff --git a/src/compiler_llvm/jni_compiler.cc b/src/compiler_llvm/jni_compiler.cc
index 27fe6db..4994e69 100644
--- a/src/compiler_llvm/jni_compiler.cc
+++ b/src/compiler_llvm/jni_compiler.cc
@@ -89,7 +89,8 @@
     this_object_or_class_object =
         irb_.LoadFromObjectOffset(method_object_addr,
                                   Method::DeclaringClassOffset().Int32Value(),
-                                  irb_.getJObjectTy());
+                                  irb_.getJObjectTy(),
+                                  kTBAARuntimeInfo);
   }
   // Actual argument (ignore method and this object)
   arg_begin = arg_iter;
@@ -119,17 +120,19 @@
     irb_.CreatePtrDisp(shadow_frame_,
                        irb_.getPtrEquivInt(ShadowFrame::MethodOffset()),
                        irb_.getJObjectTy()->getPointerTo());
-  irb_.CreateStore(method_object_addr, method_field_addr);
+  irb_.CreateStore(method_object_addr, method_field_addr, kTBAARuntimeInfo);
 
   // Store the dex pc
   irb_.StoreToObjectOffset(shadow_frame_,
                            ShadowFrame::DexPCOffset(),
-                           irb_.getInt32(0));
+                           irb_.getInt32(0),
+                           kTBAARuntimeInfo);
 
   // Store the number of the pointer slots
   irb_.StoreToObjectOffset(shadow_frame_,
                            ShadowFrame::NumberOfReferencesOffset(),
-                           irb_.getInt32(sirt_size));
+                           irb_.getInt32(sirt_size),
+                           kTBAARuntimeInfo);
 
   // Push the shadow frame
   llvm::Value* shadow_frame_upcast = irb_.CreateConstGEP2_32(shadow_frame_, 0, 0);
@@ -139,18 +142,21 @@
   llvm::Value* jni_env_object_addr =
       irb_.LoadFromObjectOffset(thread_object_addr,
                                 Thread::JniEnvOffset().Int32Value(),
-                                irb_.getJObjectTy());
+                                irb_.getJObjectTy(),
+                                kTBAARuntimeInfo);
 
   // Set thread state to kNative
   irb_.StoreToObjectOffset(thread_object_addr,
                            Thread::StateOffset().Int32Value(),
-                           irb_.getInt32(kNative));
+                           irb_.getInt32(kNative),
+                           kTBAARuntimeInfo);
 
   // Get callee code_addr
   llvm::Value* code_addr =
       irb_.LoadFromObjectOffset(method_object_addr,
                                 Method::NativeMethodOffset().Int32Value(),
-                                GetFunctionType(method_idx_, is_static, true)->getPointerTo());
+                                GetFunctionType(method_idx_, is_static, true)->getPointerTo(),
+                                kTBAARuntimeInfo);
 
   // Load actual parameters
   std::vector<llvm::Value*> args;
@@ -170,7 +176,7 @@
   // Store the "this object or class object" to SIRT
   gep_index[2] = irb_.getInt32(sirt_member_index++);
   llvm::Value* sirt_field_addr = irb_.CreateGEP(shadow_frame_, gep_index);
-  irb_.CreateStore(this_object_or_class_object, sirt_field_addr);
+  irb_.CreateStore(this_object_or_class_object, sirt_field_addr, kTBAARuntimeInfo);
   // Push the "this object or class object" to out args
   args.push_back(irb_.CreateBitCast(sirt_field_addr, irb_.getJObjectTy()));
   // Store arguments to SIRT, and push back to args
@@ -179,7 +185,7 @@
       // Store the reference type arguments to SIRT
       gep_index[2] = irb_.getInt32(sirt_member_index++);
       llvm::Value* sirt_field_addr = irb_.CreateGEP(shadow_frame_, gep_index);
-      irb_.CreateStore(arg_iter, sirt_field_addr);
+      irb_.CreateStore(arg_iter, sirt_field_addr, kTBAARuntimeInfo);
       // Note null is placed in the SIRT but the jobject passed to the native code must be null
       // (not a pointer into the SIRT as with regular references).
       llvm::Value* equal_null = irb_.CreateICmpEQ(arg_iter, irb_.getJNull());
@@ -205,16 +211,19 @@
   llvm::Value* saved_local_ref_cookie =
       irb_.LoadFromObjectOffset(jni_env_object_addr,
                                 JNIEnvExt::LocalRefCookieOffset().Int32Value(),
-                                irb_.getInt32Ty());
+                                irb_.getInt32Ty(),
+                                kTBAARuntimeInfo);
 
   // env->local_ref_cookie = env->locals.segment_state
   llvm::Value* segment_state =
       irb_.LoadFromObjectOffset(jni_env_object_addr,
                                 JNIEnvExt::SegmentStateOffset().Int32Value(),
-                                irb_.getInt32Ty());
+                                irb_.getInt32Ty(),
+                                kTBAARuntimeInfo);
   irb_.StoreToObjectOffset(jni_env_object_addr,
                            JNIEnvExt::LocalRefCookieOffset().Int32Value(),
-                           segment_state);
+                           segment_state,
+                           kTBAARuntimeInfo);
 
 
   // Call!!!
@@ -231,7 +240,8 @@
   // Set thread state to kRunnable
   irb_.StoreToObjectOffset(thread_object_addr,
                            Thread::StateOffset().Int32Value(),
-                           irb_.getInt32(kRunnable));
+                           irb_.getInt32(kRunnable),
+                           kTBAARuntimeInfo);
 
   // Do a suspend check
   irb_.CreateCall(irb_.GetRuntime(TestSuspend), thread_object_addr);
@@ -247,15 +257,18 @@
   llvm::Value* local_ref_cookie =
       irb_.LoadFromObjectOffset(jni_env_object_addr,
                                 JNIEnvExt::LocalRefCookieOffset().Int32Value(),
-                                irb_.getInt32Ty());
+                                irb_.getInt32Ty(),
+                                kTBAARuntimeInfo);
   irb_.StoreToObjectOffset(jni_env_object_addr,
                            JNIEnvExt::SegmentStateOffset().Int32Value(),
-                           local_ref_cookie);
+                           local_ref_cookie,
+                           kTBAARuntimeInfo);
 
   // env->local_ref_cookie = saved_local_ref_cookie
   irb_.StoreToObjectOffset(jni_env_object_addr,
                            JNIEnvExt::LocalRefCookieOffset().Int32Value(),
-                           saved_local_ref_cookie);
+                           saved_local_ref_cookie,
+                           kTBAARuntimeInfo);
 
   // Pop the shadow frame
   irb_.CreateCall(irb_.GetRuntime(PopShadowFrame));
diff --git a/src/compiler_llvm/method_compiler.cc b/src/compiler_llvm/method_compiler.cc
index 9d0d3f4..6430620 100644
--- a/src/compiler_llvm/method_compiler.cc
+++ b/src/compiler_llvm/method_compiler.cc
@@ -202,7 +202,8 @@
   llvm::Value* stack_end =
     irb_.LoadFromObjectOffset(thread_object_addr,
                               Thread::StackEndOffset().Int32Value(),
-                              irb_.getPtrEquivIntTy());
+                              irb_.getPtrEquivIntTy(),
+                              kTBAARuntimeInfo);
 
   // Check the frame address < thread.stack_end_ ?
   llvm::Value* is_stack_overflow = irb_.CreateICmpULT(frame_address, stack_end);
@@ -261,7 +262,7 @@
   llvm::ConstantAggregateZero* zero_initializer =
     llvm::ConstantAggregateZero::get(shadow_frame_type);
 
-  irb_.CreateStore(zero_initializer, shadow_frame_);
+  irb_.CreateStore(zero_initializer, shadow_frame_, kTBAARuntimeInfo);
 
   // Get method object
   llvm::Value* method_object_addr = EmitLoadMethodObjectAddr();
@@ -269,12 +270,14 @@
   // Store the method pointer
   irb_.StoreToObjectOffset(shadow_frame_,
                            ShadowFrame::MethodOffset(),
-                           method_object_addr);
+                           method_object_addr,
+                           kTBAARuntimeInfo);
 
   // Store the number of the pointer slots
   irb_.StoreToObjectOffset(shadow_frame_,
                            ShadowFrame::NumberOfReferencesOffset(),
-                           irb_.getJInt(sirt_size));
+                           irb_.getJInt(sirt_size),
+                           kTBAARuntimeInfo);
 
   // Push the shadow frame
   llvm::Value* shadow_frame_upcast =
@@ -1238,12 +1241,14 @@
   llvm::Value* exception_object_addr =
     irb_.LoadFromObjectOffset(thread_object_addr,
                               Thread::ExceptionOffset().Int32Value(),
-                              irb_.getJObjectTy());
+                              irb_.getJObjectTy(),
+                              kTBAARuntimeInfo);
 
   // Set thread-local exception field address to NULL
   irb_.StoreToObjectOffset(thread_object_addr,
                            Thread::ExceptionOffset().Int32Value(),
-                           irb_.getJNull());
+                           irb_.getJNull(),
+                           kTBAARuntimeInfo);
 
   // Keep the exception object in the Dalvik register
   EmitStoreDalvikReg(dec_insn.vA, kObject, kAccurate, exception_object_addr);
@@ -1384,7 +1389,7 @@
 
   llvm::Value* string_field_addr = EmitLoadDexCacheStringFieldAddr(string_idx);
 
-  llvm::Value* string_addr = irb_.CreateLoad(string_field_addr);
+  llvm::Value* string_addr = irb_.CreateLoad(string_field_addr, kTBAARuntimeInfo);
 
   if (!compiler_->CanAssumeStringIsPresentInDexCache(dex_cache_, string_idx)) {
     llvm::BasicBlock* block_str_exist =
@@ -1454,7 +1459,7 @@
     llvm::Value* type_field_addr =
       EmitLoadDexCacheResolvedTypeFieldAddr(type_idx);
 
-    llvm::Value* type_object_addr = irb_.CreateLoad(type_field_addr);
+    llvm::Value* type_object_addr = irb_.CreateLoad(type_field_addr, kTBAARuntimeInfo);
 
     if (compiler_->CanAssumeTypeIsPresentInDexCache(dex_cache_, type_idx)) {
       return type_object_addr;
@@ -1595,7 +1600,7 @@
     irb_.CreateBitCast(object_addr, jobject_ptr_ty->getPointerTo());
 
   llvm::Value* object_type_object_addr =
-    irb_.CreateLoad(object_type_field_addr);
+    irb_.CreateLoad(object_type_field_addr, kTBAARuntimeInfo);
 
   llvm::Value* equal_class =
     irb_.CreateICmpEQ(type_object_addr, object_type_object_addr);
@@ -1664,7 +1669,7 @@
     irb_.CreateBitCast(object_addr, jobject_ptr_ty->getPointerTo());
 
   llvm::Value* object_type_object_addr =
-    irb_.CreateLoad(object_type_field_addr);
+    irb_.CreateLoad(object_type_field_addr, kTBAARuntimeInfo);
 
   llvm::Value* equal_class =
     irb_.CreateICmpEQ(type_object_addr, object_type_object_addr);
@@ -1692,7 +1697,8 @@
   // Load array length
   return irb_.LoadFromObjectOffset(array,
                                    Array::LengthOffset().Int32Value(),
-                                   irb_.getJIntTy());
+                                   irb_.getJIntTy(),
+                                   kTBAARuntimeInfo);
 }
 
 
@@ -1860,7 +1866,7 @@
         reg_value = EmitLoadDalvikReg(reg_index, kObject, kAccurate);
       }
 
-      irb_.CreateStore(reg_value, data_field_addr);
+      irb_.CreateStore(reg_value, data_field_addr, kTBAAMemory);
 
       data_field_addr =
         irb_.CreatePtrDisp(data_field_addr, elem_size, field_type);
@@ -2277,7 +2283,7 @@
   llvm::Value* array_elem_addr =
     EmitArrayGEP(array_addr, index_value, elem_type, elem_jty);
 
-  llvm::Value* array_elem_value = irb_.CreateLoad(array_elem_addr);
+  llvm::Value* array_elem_value = irb_.CreateLoad(array_elem_addr, kTBAAMemory);
 
   EmitStoreDalvikReg(dec_insn.vA, elem_jty, kArray, array_elem_value);
 
@@ -2313,7 +2319,7 @@
     EmitMarkGCCard(new_value, array_addr);
   }
 
-  irb_.CreateStore(new_value, array_elem_addr);
+  irb_.CreateStore(new_value, array_elem_addr, kTBAAMemory);
 
   irb_.CreateBr(GetNextBasicBlock(dex_pc));
 }
@@ -2374,7 +2380,7 @@
 
     // TODO: Check is_volatile.  We need to generate atomic load instruction
     // when is_volatile is true.
-    field_value = irb_.CreateLoad(field_addr);
+    field_value = irb_.CreateLoad(field_addr, kTBAAMemory);
   }
 
   EmitStoreDalvikReg(dec_insn.vA, field_jty, kField, field_value);
@@ -2438,7 +2444,7 @@
 
     // TODO: Check is_volatile.  We need to generate atomic store instruction
     // when is_volatile is true.
-    irb_.CreateStore(new_value, field_addr);
+    irb_.CreateStore(new_value, field_addr, kTBAAMemory);
 
     if (field_jty == kObject) { // If put an object, mark the GC card table.
       EmitMarkGCCard(new_value, object_addr);
@@ -2460,7 +2466,7 @@
   llvm::Value* storage_field_addr =
     EmitLoadDexCacheStaticStorageFieldAddr(type_idx);
 
-  llvm::Value* storage_object_addr = irb_.CreateLoad(storage_field_addr);
+  llvm::Value* storage_object_addr = irb_.CreateLoad(storage_field_addr, kTBAARuntimeInfo);
 
   llvm::BasicBlock* block_original = irb_.GetInsertBlock();
 
@@ -2558,7 +2564,8 @@
       static_storage_addr =
         irb_.LoadFromObjectOffset(method_object_addr,
                                   Method::DeclaringClassOffset().Int32Value(),
-                                  irb_.getJObjectTy());
+                                  irb_.getJObjectTy(),
+                                  kTBAARuntimeInfo);
     } else {
       // Medium path, static storage base in a different class which
       // requires checks that the other class is initialized
@@ -2574,7 +2581,7 @@
 
     // TODO: Check is_volatile.  We need to generate atomic load instruction
     // when is_volatile is true.
-    static_field_value = irb_.CreateLoad(static_field_addr);
+    static_field_value = irb_.CreateLoad(static_field_addr, kTBAAMemory);
   }
 
   EmitStoreDalvikReg(dec_insn.vA, field_jty, kField, static_field_value);
@@ -2636,7 +2643,8 @@
       static_storage_addr =
         irb_.LoadFromObjectOffset(method_object_addr,
                                   Method::DeclaringClassOffset().Int32Value(),
-                                  irb_.getJObjectTy());
+                                  irb_.getJObjectTy(),
+                                  kTBAARuntimeInfo);
     } else {
       // Medium path, static storage base in a different class which
       // requires checks that the other class is initialized
@@ -2652,7 +2660,7 @@
 
     // TODO: Check is_volatile.  We need to generate atomic store instruction
     // when is_volatile is true.
-    irb_.CreateStore(new_value, static_field_addr);
+    irb_.CreateStore(new_value, static_field_addr, kTBAAMemory);
 
     if (field_jty == kObject) { // If put an object, mark the GC card table.
       EmitMarkGCCard(new_value, static_storage_addr);
@@ -2792,7 +2800,8 @@
   llvm::Value* code_addr =
     irb_.LoadFromObjectOffset(callee_method_object_addr,
                               Method::GetCodeOffset().Int32Value(),
-                              GetFunctionType(callee_method_idx, is_static)->getPointerTo());
+                              GetFunctionType(callee_method_idx, is_static)->getPointerTo(),
+                              kTBAARuntimeInfo);
 
   // Load the actual parameter
   std::vector<llvm::Value*> args;
@@ -2895,7 +2904,7 @@
       if (ret_shorty != 'V') {
         llvm::Value* result_addr =
             irb_.CreateBitCast(temp_space_addr, accurate_ret_type->getPointerTo());
-        llvm::Value* retval = irb_.CreateLoad(result_addr);
+        llvm::Value* retval = irb_.CreateLoad(result_addr, kTBAAStackTemp);
         EmitStoreDalvikRetValReg(ret_shorty, kAccurate, retval);
       }
     }
@@ -2917,7 +2926,7 @@
   llvm::Value* callee_method_object_field_addr =
     EmitLoadDexCacheResolvedMethodFieldAddr(callee_method_idx);
 
-  return irb_.CreateLoad(callee_method_object_field_addr);
+  return irb_.CreateLoad(callee_method_object_field_addr, kTBAARuntimeInfo);
 }
 
 
@@ -2928,13 +2937,15 @@
   llvm::Value* class_object_addr =
     irb_.LoadFromObjectOffset(this_addr,
                               Object::ClassOffset().Int32Value(),
-                              irb_.getJObjectTy());
+                              irb_.getJObjectTy(),
+                              kTBAARuntimeInfo);
 
   // Load vtable address
   llvm::Value* vtable_addr =
     irb_.LoadFromObjectOffset(class_object_addr,
                               Class::VTableOffset().Int32Value(),
-                              irb_.getJObjectTy());
+                              irb_.getJObjectTy(),
+                              kTBAARuntimeInfo);
 
   // Load callee method object
   llvm::Value* vtable_idx_value =
@@ -2943,7 +2954,7 @@
   llvm::Value* method_field_addr =
     EmitArrayGEP(vtable_addr, vtable_idx_value, irb_.getJObjectTy(), kObject);
 
-  return irb_.CreateLoad(method_field_addr);
+  return irb_.CreateLoad(method_field_addr, kTBAARuntimeInfo);
 }
 
 
@@ -3316,7 +3327,7 @@
     // Everything modulo -1 will be 0.
     eq_result = zero;
   }
-  irb_.CreateStore(eq_result, result);
+  irb_.CreateStore(eq_result, result, kTBAAStackTemp);
   irb_.CreateBr(neg_one_cont);
 
   // If divisor != -1, just do the division.
@@ -3327,11 +3338,11 @@
   } else {
     ne_result = irb_.CreateSRem(dividend, divisor);
   }
-  irb_.CreateStore(ne_result, result);
+  irb_.CreateStore(ne_result, result, kTBAAStackTemp);
   irb_.CreateBr(neg_one_cont);
 
   irb_.SetInsertPoint(neg_one_cont);
-  return irb_.CreateLoad(result);
+  return irb_.CreateLoad(result, kTBAAStackTemp);
 }
 
 
@@ -3543,7 +3554,8 @@
 
   return irb_.LoadFromObjectOffset(method_object_addr,
                                    offset.Int32Value(),
-                                   irb_.getJObjectTy());
+                                   irb_.getJObjectTy(),
+                                   kTBAARuntimeInfo);
 }
 
 
@@ -3911,7 +3923,8 @@
 void MethodCompiler::EmitUpdateDexPC(uint32_t dex_pc) {
   irb_.StoreToObjectOffset(shadow_frame_,
                            ShadowFrame::DexPCOffset(),
-                           irb_.getInt32(dex_pc));
+                           irb_.getInt32(dex_pc),
+                           kTBAARuntimeInfo);
 }
 
 
diff --git a/src/compiler_llvm/runtime_support_builder.cc b/src/compiler_llvm/runtime_support_builder.cc
index c5ff6d7..2eef771 100644
--- a/src/compiler_llvm/runtime_support_builder.cc
+++ b/src/compiler_llvm/runtime_support_builder.cc
@@ -91,13 +91,16 @@
     Value* new_shadow_frame = func->arg_begin();
     Value* old_shadow_frame = irb_.LoadFromObjectOffset(thread,
                                                         Thread::TopShadowFrameOffset().Int32Value(),
-                                                        irb_.getJObjectTy());
+                                                        irb_.getJObjectTy(),
+                                                        kTBAARuntimeInfo);
     irb_.StoreToObjectOffset(new_shadow_frame,
                              ShadowFrame::LinkOffset(),
-                             old_shadow_frame);
+                             old_shadow_frame,
+                             kTBAARuntimeInfo);
     irb_.StoreToObjectOffset(thread,
                              Thread::TopShadowFrameOffset().Int32Value(),
-                             new_shadow_frame);
+                             new_shadow_frame,
+                             kTBAARuntimeInfo);
     irb_.CreateRetVoid();
 
     VERIFY_LLVM_FUNCTION(*func);
@@ -113,13 +116,16 @@
     Value* thread = irb_.CreateCall(get_thread);
     Value* new_shadow_frame = irb_.LoadFromObjectOffset(thread,
                                                         Thread::TopShadowFrameOffset().Int32Value(),
-                                                        irb_.getJObjectTy());
+                                                        irb_.getJObjectTy(),
+                                                        kTBAARuntimeInfo);
     Value* old_shadow_frame = irb_.LoadFromObjectOffset(new_shadow_frame,
                                                         ShadowFrame::LinkOffset(),
-                                                        irb_.getJObjectTy());
+                                                        irb_.getJObjectTy(),
+                                                        kTBAARuntimeInfo);
     irb_.StoreToObjectOffset(thread,
                              Thread::TopShadowFrameOffset().Int32Value(),
-                             old_shadow_frame);
+                             old_shadow_frame,
+                             kTBAARuntimeInfo);
     irb_.CreateRetVoid();
 
     VERIFY_LLVM_FUNCTION(*func);
@@ -135,7 +141,8 @@
     Value* thread = irb_.CreateCall(get_thread);
     Value* exception = irb_.LoadFromObjectOffset(thread,
                                                  Thread::ExceptionOffset().Int32Value(),
-                                                 irb_.getJObjectTy());
+                                                 irb_.getJObjectTy(),
+                                                 kTBAARuntimeInfo);
     Value* is_exception_not_null = irb_.CreateICmpNE(exception, irb_.getJNull());
     irb_.CreateRet(is_exception_not_null);
 
@@ -156,7 +163,8 @@
     Value* thread = func->arg_begin();
     Value* suspend_count = irb_.LoadFromObjectOffset(thread,
                                                      Thread::SuspendCountOffset().Int32Value(),
-                                                     irb_.getJIntTy());
+                                                     irb_.getJIntTy(),
+                                                     kTBAARuntimeInfo);
     Value* is_suspend = irb_.CreateICmpNE(suspend_count, irb_.getJInt(0));
 
     BasicBlock* basic_block_suspend = BasicBlock::Create(context_, "suspend", func);
@@ -199,11 +207,12 @@
     Value* thread = irb_.CreateCall(get_thread);
     Value* card_table = irb_.LoadFromObjectOffset(thread,
                                                   Thread::CardTableOffset().Int32Value(),
-                                                  irb_.getInt8Ty()->getPointerTo());
+                                                  irb_.getInt8Ty()->getPointerTo(),
+                                                  kTBAARuntimeInfo);
     Value* target_addr_int = irb_.CreatePtrToInt(target_addr, irb_.getPtrEquivIntTy());
     Value* card_no = irb_.CreateLShr(target_addr_int, irb_.getPtrEquivInt(GC_CARD_SHIFT));
     Value* card_table_entry = irb_.CreateGEP(card_table, card_no);
-    irb_.CreateStore(irb_.getInt8(GC_CARD_DIRTY), card_table_entry);
+    irb_.CreateStore(irb_.getInt8(GC_CARD_DIRTY), card_table_entry, kTBAARuntimeInfo);
     irb_.CreateRetVoid();
 
     VERIFY_LLVM_FUNCTION(*func);
diff --git a/src/compiler_llvm/tbaa_info.cc b/src/compiler_llvm/tbaa_info.cc
new file mode 100644
index 0000000..2b8f983
--- /dev/null
+++ b/src/compiler_llvm/tbaa_info.cc
@@ -0,0 +1,77 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+
+#include "tbaa_info.h"
+
+#include <llvm/ADT/SmallVector.h>
+#include <llvm/ADT/StringRef.h>
+#include <llvm/Constants.h>
+#include <llvm/Metadata.h>
+#include <llvm/Type.h>
+
+
+namespace art {
+namespace compiler_llvm {
+
+
+llvm::MDNode* TBAAInfo::GetRootType() {
+  if (root_ == NULL) {
+    root_ = GenTBAANode("Art TBAA Root");
+  }
+  return root_;
+}
+
+llvm::MDNode* TBAAInfo::GetSpecialType(TBAASpecialType sty_id) {
+  DCHECK_GE(sty_id, 0) << "Unknown TBAA special type: " << sty_id;
+  DCHECK_LT(sty_id, MAX_TBAA_SPECIAL_TYPE) << "Unknown TBAA special type: " << sty_id;
+
+  llvm::MDNode*& spec_ty = special_type_[sty_id];
+  if (spec_ty == NULL) {
+    switch (sty_id) {
+    case kTBAARegister:         spec_ty = GenTBAANode("Register", GetRootType()); break;
+    case kTBAAStackTemp:        spec_ty = GenTBAANode("StackTemp", GetRootType()); break;
+    case kTBAAMemory:           spec_ty = GenTBAANode("Memory", GetRootType()); break;
+    case kTBAAMemoryArray:      spec_ty = GenTBAANode("MemoryArray", GetRootType()); break;
+    case kTBAAMemoryIdentified: spec_ty = GenTBAANode("MemoryIdentified", GetRootType()); break;
+    case kTBAAMemoryStatic:     spec_ty = GenTBAANode("MemoryStatic", GetRootType()); break;
+    case kTBAARuntimeInfo:      spec_ty = GenTBAANode("RuntimeInfo", GetRootType()); break;
+    case kTBAAConstJObject:     spec_ty = GenTBAANode("ConstJObject", GetRootType(), true); break;
+    default:
+      LOG(FATAL) << "Unknown TBAA special type: " << sty_id;
+      break;
+    }
+  }
+  return spec_ty;
+}
+
+llvm::MDNode* TBAAInfo::GenTBAANode(llvm::StringRef name, llvm::MDNode* parent, bool read_only) {
+  llvm::SmallVector<llvm::Value*, 3> array_ref;
+
+  array_ref.push_back(llvm::MDString::get(context_, name));
+  if (parent != NULL) {
+    array_ref.push_back(parent);
+  }
+  if (read_only != false) {
+    array_ref.push_back(llvm::ConstantInt::get(llvm::Type::getInt1Ty(context_), read_only));
+  }
+
+  return llvm::MDNode::get(context_, array_ref);
+}
+
+
+} // namespace compiler_llvm
+} // namespace art
diff --git a/src/compiler_llvm/tbaa_info.h b/src/compiler_llvm/tbaa_info.h
new file mode 100644
index 0000000..0df732b
--- /dev/null
+++ b/src/compiler_llvm/tbaa_info.h
@@ -0,0 +1,58 @@
+/*
+ * Copyright (C) 2012 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#ifndef ART_SRC_COMPILER_LLVM_TBAA_INFO_H_
+#define ART_SRC_COMPILER_LLVM_TBAA_INFO_H_
+
+#include "backend_types.h"
+
+#include <cstring>
+
+namespace llvm {
+  class LLVMContext;
+  class MDNode;
+  class StringRef;
+}
+
+namespace art {
+namespace compiler_llvm {
+
+
+class TBAAInfo {
+ public:
+  TBAAInfo(llvm::LLVMContext& context) : context_(context), root_(NULL) {
+    std::memset(special_type_, 0, sizeof(special_type_));
+  }
+
+  llvm::MDNode* GetRootType();
+
+  llvm::MDNode* GetSpecialType(TBAASpecialType special_ty);
+
+  llvm::MDNode* GenTBAANode(llvm::StringRef name,
+                            llvm::MDNode* parent = NULL,
+                            bool readonly = false);
+
+ private:
+  llvm::LLVMContext& context_;
+  llvm::MDNode* root_;
+  llvm::MDNode* special_type_[MAX_TBAA_SPECIAL_TYPE];
+};
+
+
+} // namespace compiler_llvm
+} // namespace art
+
+#endif // ART_SRC_COMPILER_LLVM_TBAA_INFO_H_
diff --git a/src/compiler_llvm/upcall_compiler.cc b/src/compiler_llvm/upcall_compiler.cc
index 11d50ff..fd2e59d 100644
--- a/src/compiler_llvm/upcall_compiler.cc
+++ b/src/compiler_llvm/upcall_compiler.cc
@@ -135,7 +135,7 @@
 
       llvm::Value* arg_addr = irb_.CreateBitCast(arg_jvalue_addr, arg_type);
 
-      args.push_back(irb_.CreateLoad(arg_addr));
+      args.push_back(irb_.CreateLoad(arg_addr, kTBAAStackTemp));
 
     } else {
       LOG(FATAL) << "Unexpected arg shorty for invoke stub: " << shorty[i];
@@ -152,7 +152,7 @@
     irb_.CreatePtrDisp(method_object_addr, code_field_offset_value,
                        accurate_func_type->getPointerTo()->getPointerTo());
 
-  llvm::Value* code_addr = irb_.CreateLoad(code_field_addr);
+  llvm::Value* code_addr = irb_.CreateLoad(code_field_addr, kTBAARuntimeInfo);
 #else
   llvm::Value* result = irb_.CreateCall(irb_.GetRuntime(FixStub), method_object_addr);
   llvm::Value* code_addr = irb_.CreatePointerCast(result, accurate_func_type->getPointerTo());
@@ -174,7 +174,7 @@
     llvm::Value* ret_addr =
       irb_.CreateBitCast(retval_addr, accurate_ret_type->getPointerTo());
 
-    irb_.CreateStore(retval, ret_addr);
+    irb_.CreateStore(retval, ret_addr, kTBAAStackTemp);
   }
 
   irb_.CreateRetVoid();