Add support for llvm static branch prediction.

Change-Id: I8025db404d59a7ef17e4f8b878d0ab5c8cf7dab4

5 files changed, 57 insertions, 13 deletions

diff --git a/src/compiler_llvm/backend_types.h b/src/compiler_llvm/backend_types.h
index 24703b8c24..ae226d62e6 100644
--- a/src/compiler_llvm/backend_types.h
+++ b/src/compiler_llvm/backend_types.h
@@ -70,6 +70,13 @@ enum TBAASpecialType {
 };
 
 
+enum ExpectCond {
+  kLikely,
+  kUnlikely,
+  MAX_EXPECT
+};
+
+
 inline JType GetJTypeFromShorty(char shorty_jty) {
   switch (shorty_jty) {
   case 'V':
diff --git a/src/compiler_llvm/ir_builder.cc b/src/compiler_llvm/ir_builder.cc
index 8b2f0f7d96..d93b5885d0 100644
--- a/src/compiler_llvm/ir_builder.cc
+++ b/src/compiler_llvm/ir_builder.cc
@@ -19,6 +19,8 @@
 
 #include <llvm/Module.h>
 
+#include <algorithm>
+
 namespace art {
 namespace compiler_llvm {
 
@@ -44,6 +46,22 @@ IRBuilder::IRBuilder(llvm::LLVMContext& context, llvm::Module& module)
   CHECK(art_frame_type_ != NULL);
 
   runtime_support_ = NULL;
+
+
+  // Pre-generate the MDNode for static branch prediction
+  llvm::Type* int32ty = llvm::Type::getInt32Ty(context);
+  llvm::MDString* branch_weights = llvm::MDString::get(context, "branch_weights");
+  llvm::Constant* likely = llvm::ConstantInt::get(int32ty, 64);
+  llvm::Constant* unlikely = llvm::ConstantInt::get(int32ty, 4);
+  llvm::Value *opts[] = {
+    branch_weights,
+    likely,
+    unlikely
+  };
+
+  expect_cond_[kLikely] = llvm::MDNode::get(context, opts);
+  std::swap(opts[1], opts[2]);
+  expect_cond_[kUnlikely] = llvm::MDNode::get(context, opts);
 }
 
 
diff --git a/src/compiler_llvm/ir_builder.h b/src/compiler_llvm/ir_builder.h
index a700c69a65..aa261c3bb6 100644
--- a/src/compiler_llvm/ir_builder.h
+++ b/src/compiler_llvm/ir_builder.h
@@ -111,6 +111,24 @@ class IRBuilder : public LLVMIRBuilder {
 
 
   //--------------------------------------------------------------------------
+  // Static Branch Prediction
+  //--------------------------------------------------------------------------
+
+  // Import the orignal conditional branch
+  using LLVMIRBuilder::CreateCondBr;
+  llvm::BranchInst* CreateCondBr(llvm::Value *cond,
+                                 llvm::BasicBlock* true_bb,
+                                 llvm::BasicBlock* false_bb,
+                                 ExpectCond expect) {
+    DCHECK_NE(expect, MAX_EXPECT) << "MAX_EXPECT is not for branch weight";
+
+    llvm::BranchInst* branch_inst = LLVMIRBuilder::CreateCondBr(cond, true_bb, false_bb);
+    branch_inst->setMetadata(llvm::LLVMContext::MD_prof, expect_cond_[expect]);
+    return branch_inst;
+  }
+
+
+  //--------------------------------------------------------------------------
   // Pointer Arithmetic Helper Function
   //--------------------------------------------------------------------------
 
@@ -384,6 +402,7 @@ class IRBuilder : public LLVMIRBuilder {
 
   RuntimeSupportBuilder* runtime_support_;
 
+  llvm::MDNode* expect_cond_[MAX_EXPECT];
 };
 
 
diff --git a/src/compiler_llvm/method_compiler.cc b/src/compiler_llvm/method_compiler.cc
index b3ae1a6a02..6b6192f509 100644
--- a/src/compiler_llvm/method_compiler.cc
+++ b/src/compiler_llvm/method_compiler.cc
@@ -214,7 +214,7 @@ void MethodCompiler::EmitStackOverflowCheck() {
   llvm::BasicBlock* block_continue =
       llvm::BasicBlock::Create(*context_, "stack_overflow_cont", func_);
 
-  irb_.CreateCondBr(is_stack_overflow, block_exception, block_continue);
+  irb_.CreateCondBr(is_stack_overflow, block_exception, block_continue, kUnlikely);
 
   // If stack overflow, throw exception.
   irb_.SetInsertPoint(block_exception);
@@ -1401,7 +1401,7 @@ void MethodCompiler::EmitInsn_LoadConstantString(uint32_t dex_pc,
     // Test: Is the string resolved and in the dex cache?
     llvm::Value* equal_null = irb_.CreateICmpEQ(string_addr, irb_.getJNull());
 
-    irb_.CreateCondBr(equal_null, block_str_resolve, block_str_exist);
+    irb_.CreateCondBr(equal_null, block_str_resolve, block_str_exist, kUnlikely);
 
     // String is resolved, go to next basic block.
     irb_.SetInsertPoint(block_str_exist);
@@ -1477,7 +1477,7 @@ llvm::Value* MethodCompiler::EmitLoadConstantClass(uint32_t dex_pc,
     llvm::BasicBlock* block_load_class =
       CreateBasicBlockWithDexPC(dex_pc, "load_class");
 
-    irb_.CreateCondBr(equal_null, block_load_class, block_cont);
+    irb_.CreateCondBr(equal_null, block_load_class, block_cont, kUnlikely);
 
     // Failback routine to load the class object
     irb_.SetInsertPoint(block_load_class);
@@ -2222,7 +2222,7 @@ MethodCompiler::EmitGuard_ArrayIndexOutOfBoundsException(uint32_t dex_pc,
   llvm::BasicBlock* block_continue =
     CreateBasicBlockWithDexPC(dex_pc, "cont");
 
-  irb_.CreateCondBr(cmp, block_exception, block_continue);
+  irb_.CreateCondBr(cmp, block_exception, block_continue, kUnlikely);
 
   irb_.SetInsertPoint(block_exception);
 
@@ -2474,7 +2474,7 @@ llvm::Value* MethodCompiler::EmitLoadStaticStorage(uint32_t dex_pc,
   llvm::Value* equal_null =
     irb_.CreateICmpEQ(storage_object_addr, irb_.getJNull());
 
-  irb_.CreateCondBr(equal_null, block_load_static, block_cont);
+  irb_.CreateCondBr(equal_null, block_load_static, block_cont, kUnlikely);
 
   // Failback routine to load the class object
   irb_.SetInsertPoint(block_load_static);
@@ -2848,7 +2848,7 @@ void MethodCompiler::EmitInsn_Invoke(uint32_t dex_pc,
   llvm::Value* code_addr_int = irb_.CreatePtrToInt(code_addr, irb_.getPtrEquivIntTy());
   llvm::Value* max_stub_int = irb_.getPtrEquivInt(special_stub::kMaxSpecialStub);
   llvm::Value* is_stub = irb_.CreateICmpULT(code_addr_int, max_stub_int);
-  irb_.CreateCondBr(is_stub, block_stub, block_normal);
+  irb_.CreateCondBr(is_stub, block_stub, block_normal, kUnlikely);
 
 
   irb_.SetInsertPoint(block_normal);
@@ -2869,7 +2869,7 @@ void MethodCompiler::EmitInsn_Invoke(uint32_t dex_pc,
       llvm::BasicBlock* block_proxy_stub = CreateBasicBlockWithDexPC(dex_pc, "proxy");
       llvm::BasicBlock* block_link = CreateBasicBlockWithDexPC(dex_pc, "link");
 
-      irb_.CreateCondBr(irb_.CreateIsNull(code_addr), block_link, block_proxy_stub);
+      irb_.CreateCondBr(irb_.CreateIsNull(code_addr), block_link, block_proxy_stub, kUnlikely);
 
 
       irb_.SetInsertPoint(block_link);
@@ -3302,7 +3302,7 @@ MethodCompiler::EmitIntDivRemResultComputation(uint32_t dex_pc,
   llvm::BasicBlock* neg_one_cont = CreateBasicBlockWithDexPC(dex_pc, "neg_one_cont");
 
   llvm::Value* is_equal_neg_one = EmitConditionResult(divisor, neg_one, kCondBranch_EQ);
-  irb_.CreateCondBr(is_equal_neg_one, eq_neg_one, ne_neg_one);
+  irb_.CreateCondBr(is_equal_neg_one, eq_neg_one, ne_neg_one, kUnlikely);
 
   // If divisor == -1
   irb_.SetInsertPoint(eq_neg_one);
@@ -3511,7 +3511,7 @@ void MethodCompiler::EmitGuard_DivZeroException(uint32_t dex_pc,
 
   llvm::BasicBlock* block_continue = CreateBasicBlockWithDexPC(dex_pc, "cont");
 
-  irb_.CreateCondBr(equal_zero, block_exception, block_continue);
+  irb_.CreateCondBr(equal_zero, block_exception, block_continue, kUnlikely);
 
   irb_.SetInsertPoint(block_exception);
   EmitUpdateDexPC(dex_pc);
@@ -3532,7 +3532,7 @@ void MethodCompiler::EmitGuard_NullPointerException(uint32_t dex_pc,
   llvm::BasicBlock* block_continue =
     CreateBasicBlockWithDexPC(dex_pc, "cont");
 
-  irb_.CreateCondBr(equal_null, block_exception, block_continue);
+  irb_.CreateCondBr(equal_null, block_exception, block_continue, kUnlikely);
 
   irb_.SetInsertPoint(block_exception);
   EmitUpdateDexPC(dex_pc);
@@ -3650,9 +3650,9 @@ void MethodCompiler::EmitGuard_ExceptionLandingPad(uint32_t dex_pc) {
   llvm::BasicBlock* block_cont = CreateBasicBlockWithDexPC(dex_pc, "cont");
 
   if (llvm::BasicBlock* lpad = GetLandingPadBasicBlock(dex_pc)) {
-    irb_.CreateCondBr(exception_pending, lpad, block_cont);
+    irb_.CreateCondBr(exception_pending, lpad, block_cont, kUnlikely);
   } else {
-    irb_.CreateCondBr(exception_pending, GetUnwindBasicBlock(), block_cont);
+    irb_.CreateCondBr(exception_pending, GetUnwindBasicBlock(), block_cont, kUnlikely);
   }
 
   irb_.SetInsertPoint(block_cont);
diff --git a/src/compiler_llvm/runtime_support_builder.cc b/src/compiler_llvm/runtime_support_builder.cc
index c5a44abaf8..c1643ece62 100644
--- a/src/compiler_llvm/runtime_support_builder.cc
+++ b/src/compiler_llvm/runtime_support_builder.cc
@@ -161,7 +161,7 @@ void RuntimeSupportBuilder::OptimizeRuntimeSupport() {
 
     BasicBlock* basic_block_suspend = BasicBlock::Create(context_, "suspend", func);
     BasicBlock* basic_block_else = BasicBlock::Create(context_, "else", func);
-    irb_.CreateCondBr(is_suspend, basic_block_suspend, basic_block_else);
+    irb_.CreateCondBr(is_suspend, basic_block_suspend, basic_block_else, kUnlikely);
 
     irb_.SetInsertPoint(basic_block_suspend);
     CallInst* call_inst = irb_.CreateCall(slow_func, thread);