Supporting de-virtualization for precise types.
Sharpening invoke-virtual and invoke-interface calls to invoke-direct for cases
where the type of "this" pointer in the invoke- params is precisely known.
Instructions that have an invoke opcode are marked as interesting, for each invoke-virtual/interface
we come across with a precise type for "this" we mark the location as a candidate for sharpening,
resolve the concrete method and save its method reference <DexFile, DexMethodIndex> to be sharpened
in CompilerDriver::ComputeInvokeInfo().
Added a new entry to AOT statistics showing the percentage of sharpened calls that were based on
type analysis.
Fix a minor bug in type creation for GetSuperClass(). Previously super class of a precise reference
had precise types created which is not necessarily the case.
Fixed DCHECK in Class::FindVirtualMethodForVirtual to handle cases for Miranda methods.
Sharpening only takes place for cases where no soft failures happen at verification time.
Change-Id: Ic027d0226d6f95260c1918014cb6313f2e0ca455
diff --git a/src/verifier/instruction_flags.cc b/src/verifier/instruction_flags.cc
index 823edde..358791d 100644
--- a/src/verifier/instruction_flags.cc
+++ b/src/verifier/instruction_flags.cc
@@ -29,7 +29,7 @@
strncpy(encoding, "-----", sizeof(encoding));
if (IsInTry()) encoding[kInTry] = 'T';
if (IsBranchTarget()) encoding[kBranchTarget] = 'B';
- if (IsGcPoint()) encoding[kGcPoint] = 'G';
+ if (IsCompileTimeInfoPoint()) encoding[kCompileTimeInfoPoint] = 'G';
if (IsVisited()) encoding[kVisited] = 'V';
if (IsChanged()) encoding[kChanged] = 'C';
}
diff --git a/src/verifier/instruction_flags.h b/src/verifier/instruction_flags.h
index 7f0d240..9dc3ea7 100644
--- a/src/verifier/instruction_flags.h
+++ b/src/verifier/instruction_flags.h
@@ -59,15 +59,14 @@
bool IsBranchTarget() const {
return (flags_ & (1 << kBranchTarget)) != 0;
}
-
- void SetGcPoint() {
- flags_ |= 1 << kGcPoint;
+ void SetCompileTimeInfoPoint() {
+ flags_ |= 1 << kCompileTimeInfoPoint;
}
- void ClearGcPoint() {
- flags_ &= ~(1 << kGcPoint);
+ void ClearCompileTimeInfoPoint() {
+ flags_ &= ~(1 << kCompileTimeInfoPoint);
}
- bool IsGcPoint() const {
- return (flags_ & (1 << kGcPoint)) != 0;
+ bool IsCompileTimeInfoPoint() const {
+ return (flags_ & (1 << kCompileTimeInfoPoint)) != 0;
}
void SetVisited() {
@@ -100,7 +99,8 @@
enum {
kInTry,
kBranchTarget,
- kGcPoint,
+ kCompileTimeInfoPoint, // Location of interest to the compiler for GC maps and
+ // verifier based method sharpening.
kVisited,
kChanged,
};
diff --git a/src/verifier/method_verifier.cc b/src/verifier/method_verifier.cc
index 2b70e26..2eb0c20 100644
--- a/src/verifier/method_verifier.cc
+++ b/src/verifier/method_verifier.cc
@@ -56,8 +56,8 @@
case kTrackRegsAll:
interesting = flags[i].IsOpcode();
break;
- case kTrackRegsGcPoints:
- interesting = flags[i].IsGcPoint() || flags[i].IsBranchTarget();
+ case kTrackCompilerInterestPoints:
+ interesting = flags[i].IsCompileTimeInfoPoint() || flags[i].IsBranchTarget() ;
break;
case kTrackRegsBranches:
interesting = flags[i].IsBranchTarget();
@@ -496,7 +496,7 @@
/* Flag the start of the method as a branch target, and a GC point due to stack overflow errors */
insn_flags_[0].SetBranchTarget();
- insn_flags_[0].SetGcPoint();
+ insn_flags_[0].SetCompileTimeInfoPoint();
uint32_t insns_size = code_item_->insns_size_in_code_units_;
for (uint32_t dex_pc = 0; dex_pc < insns_size;) {
@@ -505,8 +505,10 @@
return false;
}
/* Flag instructions that are garbage collection points */
+ // All invoke points are marked as "Throw" points already.
+ // We are relying on this to also count all the invokes as interesting.
if (inst->IsBranch() || inst->IsSwitch() || inst->IsThrow() || inst->IsReturn()) {
- insn_flags_[dex_pc].SetGcPoint();
+ insn_flags_[dex_pc].SetCompileTimeInfoPoint();
}
dex_pc += inst->SizeInCodeUnits();
inst = inst->Next();
@@ -918,7 +920,8 @@
<< " insns_size=" << insns_size << ")";
}
/* Create and initialize table holding register status */
- reg_table_.Init(kTrackRegsGcPoints, insn_flags_.get(), insns_size, registers_size, this);
+ reg_table_.Init(kTrackCompilerInterestPoints, insn_flags_.get(), insns_size, registers_size, this);
+
work_line_.reset(new RegisterLine(registers_size, this));
saved_line_.reset(new RegisterLine(registers_size, this));
@@ -952,6 +955,10 @@
const std::vector<uint8_t>* dex_gc_map = CreateLengthPrefixedDexGcMap(*(map.get()));
verifier::MethodVerifier::SetDexGcMap(ref, *dex_gc_map);
+ MethodVerifier::PcToConreteMethod* pc_to_conrete_method = GenerateDevirtMap();
+ if(pc_to_conrete_method != NULL ) {
+ SetDevirtMap(ref, pc_to_conrete_method);
+ }
return true;
}
@@ -3137,7 +3144,7 @@
size_t max_insn = 0;
size_t max_ref_reg = -1;
for (size_t i = 0; i < code_item_->insns_size_in_code_units_; i++) {
- if (insn_flags_[i].IsGcPoint()) {
+ if (insn_flags_[i].IsCompileTimeInfoPoint()) {
local_gc_points++;
max_insn = i;
RegisterLine* line = reg_table_.GetLine(i);
@@ -3153,6 +3160,84 @@
*log2_max_gc_pc = i;
}
+MethodVerifier::PcToConreteMethod* MethodVerifier::GenerateDevirtMap() {
+
+ // It is risky to rely on reg_types for sharpening in cases of soft
+ // verification, we might end up sharpening to a wrong implementation. Just abort.
+ if (!failure_messages_.empty()) {
+ return NULL;
+ }
+
+ PcToConreteMethod* pc_to_concrete_method = new PcToConreteMethod();
+ uint32_t dex_pc = 0;
+ const uint16_t* insns = code_item_->insns_ ;
+ const Instruction* inst = Instruction::At(insns);
+
+ for (; dex_pc < code_item_->insns_size_in_code_units_;
+ dex_pc += insn_flags_[dex_pc].GetLengthInCodeUnits(), inst = inst->Next()) {
+
+ bool is_virtual = (inst->Opcode() == Instruction::INVOKE_VIRTUAL) ||
+ (inst->Opcode() == Instruction::INVOKE_VIRTUAL_RANGE);
+ bool is_interface = (inst->Opcode() == Instruction::INVOKE_INTERFACE) ||
+ (inst->Opcode() == Instruction::INVOKE_INTERFACE_RANGE);
+
+ if(!(is_interface || is_virtual))
+ continue;
+
+ // Check if vC ("this" pointer in the instruction) has a precise type.
+ RegisterLine* line = reg_table_.GetLine(dex_pc);
+ DecodedInstruction dec_insn(inst);
+ const RegType& reg_type(line->GetRegisterType(dec_insn.vC));
+
+ if (!reg_type.IsPreciseReference()) {
+ continue;
+ }
+
+ CHECK(!(reg_type.GetClass()->IsInterface()));
+ // If the class is an array class, it can be both Abstract and final and so
+ // the reg_type will be created as precise.
+ CHECK(!(reg_type.GetClass()->IsAbstract()) || reg_type.GetClass()->IsArrayClass());
+ // Find the abstract method.
+ // vB has the method index.
+ mirror::AbstractMethod* abstract_method = NULL ;
+ abstract_method = dex_cache_->GetResolvedMethod(dec_insn.vB);
+ if(abstract_method == NULL) {
+ // If the method is not found in the cache this means that it was never found
+ // by ResolveMethodAndCheckAccess() called when verifying invoke_*.
+ continue;
+ }
+ // Find the concrete method.
+ mirror::AbstractMethod* concrete_method = NULL;
+ if (is_interface) {
+ concrete_method = reg_type.GetClass()->FindVirtualMethodForInterface(abstract_method);
+ }
+ if (is_virtual) {
+ concrete_method = reg_type.GetClass()->FindVirtualMethodForVirtual(abstract_method);
+ }
+
+ if(concrete_method == NULL) {
+ // In cases where concrete_method is not found continue to the next invoke instead
+ // of crashing.
+ continue;
+ }
+
+ CHECK(!concrete_method->IsAbstract()) << PrettyMethod(concrete_method);
+ // Build method reference.
+ CompilerDriver::MethodReference concrete_ref(
+ concrete_method->GetDeclaringClass()->GetDexCache()->GetDexFile(),
+ concrete_method->GetDexMethodIndex());
+ // Now Save the current PC and the concrete method reference to be used
+ // in compiler driver.
+ pc_to_concrete_method->Put(dex_pc, concrete_ref );
+ }
+
+ if (pc_to_concrete_method->size() == 0) {
+ delete pc_to_concrete_method;
+ return NULL ;
+ }
+ return pc_to_concrete_method;
+}
+
const std::vector<uint8_t>* MethodVerifier::GenerateGcMap() {
size_t num_entries, ref_bitmap_bits, pc_bits;
ComputeGcMapSizes(&num_entries, &ref_bitmap_bits, &pc_bits);
@@ -3199,7 +3284,7 @@
table->push_back((num_entries >> 8) & 0xFF);
// Write table data
for (size_t i = 0; i < code_item_->insns_size_in_code_units_; i++) {
- if (insn_flags_[i].IsGcPoint()) {
+ if (insn_flags_[i].IsCompileTimeInfoPoint()) {
table->push_back(i & 0xFF);
if (pc_bytes == 2) {
table->push_back((i >> 8) & 0xFF);
@@ -3219,7 +3304,7 @@
size_t map_index = 0;
for (size_t i = 0; i < code_item_->insns_size_in_code_units_; i++) {
const uint8_t* reg_bitmap = map.FindBitMap(i, false);
- if (insn_flags_[i].IsGcPoint()) {
+ if (insn_flags_[i].IsCompileTimeInfoPoint()) {
CHECK_LT(map_index, map.NumEntries());
CHECK_EQ(map.GetDexPc(map_index), i);
CHECK_EQ(map.GetBitMap(map_index), reg_bitmap);
@@ -3254,6 +3339,19 @@
CHECK(GetDexGcMap(ref) != NULL);
}
+void MethodVerifier::SetDevirtMap(CompilerDriver::MethodReference ref, const PcToConreteMethod* devirt_map) {
+
+ MutexLock mu(Thread::Current(), *devirt_maps_lock_);
+ DevirtualizationMapTable::iterator it = devirt_maps_->find(ref);
+ if (it != devirt_maps_->end()) {
+ delete it->second;
+ devirt_maps_->erase(it);
+ }
+
+ devirt_maps_->Put(ref, devirt_map);
+ CHECK(devirt_maps_->find(ref) != devirt_maps_->end());
+}
+
const std::vector<uint8_t>* MethodVerifier::GetDexGcMap(CompilerDriver::MethodReference ref) {
MutexLock mu(Thread::Current(), *dex_gc_maps_lock_);
DexGcMapTable::const_iterator it = dex_gc_maps_->find(ref);
@@ -3265,6 +3363,22 @@
return it->second;
}
+const CompilerDriver::MethodReference* MethodVerifier::GetDevirtMap(CompilerDriver::MethodReference ref, uint32_t pc) {
+ MutexLock mu(Thread::Current(), *devirt_maps_lock_);
+ DevirtualizationMapTable::const_iterator it = devirt_maps_->find(ref);
+ if (it == devirt_maps_->end()) {
+ return NULL;
+ }
+
+ // Look up the PC in the map, get the concrete method to execute and return its reference.
+ MethodVerifier::PcToConreteMethod::const_iterator pc_to_concrete_method = it->second->find(pc);
+ if(pc_to_concrete_method != it->second->end()) {
+ return &(pc_to_concrete_method->second);
+ } else {
+ return NULL;
+ }
+}
+
std::vector<int32_t> MethodVerifier::DescribeVRegs(uint32_t dex_pc) {
RegisterLine* line = reg_table_.GetLine(dex_pc);
std::vector<int32_t> result;
@@ -3312,6 +3426,9 @@
Mutex* MethodVerifier::dex_gc_maps_lock_ = NULL;
MethodVerifier::DexGcMapTable* MethodVerifier::dex_gc_maps_ = NULL;
+Mutex* MethodVerifier::devirt_maps_lock_ = NULL;
+MethodVerifier::DevirtualizationMapTable* MethodVerifier::devirt_maps_ = NULL;
+
Mutex* MethodVerifier::rejected_classes_lock_ = NULL;
MethodVerifier::RejectedClassesTable* MethodVerifier::rejected_classes_ = NULL;
@@ -3323,6 +3440,12 @@
dex_gc_maps_ = new MethodVerifier::DexGcMapTable;
}
+ devirt_maps_lock_ = new Mutex("verifier Devirtualization lock");
+ {
+ MutexLock mu(self, *devirt_maps_lock_);
+ devirt_maps_ = new MethodVerifier::DevirtualizationMapTable();
+ }
+
rejected_classes_lock_ = new Mutex("verifier rejected classes lock");
{
MutexLock mu(self, *rejected_classes_lock_);
@@ -3343,6 +3466,15 @@
dex_gc_maps_lock_ = NULL;
{
+ MutexLock mu(self, *devirt_maps_lock_);
+ STLDeleteValues(devirt_maps_);
+ delete devirt_maps_;
+ devirt_maps_ = NULL;
+ }
+ delete devirt_maps_lock_;
+ devirt_maps_lock_ = NULL;
+
+ {
MutexLock mu(self, *rejected_classes_lock_);
delete rejected_classes_;
rejected_classes_ = NULL;
diff --git a/src/verifier/method_verifier.h b/src/verifier/method_verifier.h
index 7570b50..b7e1cf2 100644
--- a/src/verifier/method_verifier.h
+++ b/src/verifier/method_verifier.h
@@ -101,7 +101,7 @@
// type-precise register analysis).
enum RegisterTrackingMode {
kTrackRegsBranches,
- kTrackRegsGcPoints,
+ kTrackCompilerInterestPoints,
kTrackRegsAll,
};
@@ -187,6 +187,9 @@
static const std::vector<uint8_t>* GetDexGcMap(CompilerDriver::MethodReference ref)
LOCKS_EXCLUDED(dex_gc_maps_lock_);
+ static const CompilerDriver::MethodReference* GetDevirtMap(CompilerDriver::MethodReference ref, uint32_t pc)
+ LOCKS_EXCLUDED(devirt_maps_lock_);
+
// Fills 'monitor_enter_dex_pcs' with the dex pcs of the monitor-enter instructions corresponding
// to the locks held at 'dex_pc' in 'm'.
static void FindLocksAtDexPc(mirror::AbstractMethod* m, uint32_t dex_pc,
@@ -577,6 +580,16 @@
static void SetDexGcMap(CompilerDriver::MethodReference ref, const std::vector<uint8_t>& dex_gc_map)
LOCKS_EXCLUDED(dex_gc_maps_lock_);
+
+ // Devirtualization map.
+ typedef SafeMap<const uint32_t, CompilerDriver::MethodReference> PcToConreteMethod;
+ typedef SafeMap<const CompilerDriver::MethodReference, const PcToConreteMethod*> DevirtualizationMapTable;
+ MethodVerifier::PcToConreteMethod* GenerateDevirtMap();
+
+ static Mutex* devirt_maps_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
+ static DevirtualizationMapTable* devirt_maps_ GUARDED_BY(devirt_maps_lock_);
+ static void SetDevirtMap(CompilerDriver::MethodReference ref, const PcToConreteMethod* pc_method_map);
+ LOCKS_EXCLUDED(devirt_maps_lock_);
typedef std::set<CompilerDriver::ClassReference> RejectedClassesTable;
static Mutex* rejected_classes_lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
static RejectedClassesTable* rejected_classes_;
diff --git a/src/verifier/reg_type.cc b/src/verifier/reg_type.cc
index 774c2b2..32679f6 100644
--- a/src/verifier/reg_type.cc
+++ b/src/verifier/reg_type.cc
@@ -494,6 +494,7 @@
PreciseReferenceType::PreciseReferenceType(mirror::Class* klass, std::string& descriptor,
uint16_t cache_id)
: RegType(klass, descriptor, cache_id) {
+ DCHECK(klass->IsInstantiable());
}
UnresolvedUninitialisedThisRefType::UnresolvedUninitialisedThisRefType(std::string& descriptor,
@@ -609,7 +610,9 @@
if (!IsUnresolvedTypes()) {
mirror::Class* super_klass = GetClass()->GetSuperClass();
if (super_klass != NULL) {
- return cache->FromClass(super_klass, IsPreciseReference());
+ // A super class of a precise type isn't precise as a precise type indicates the register
+ // holds exactly that type.
+ return cache->FromClass(super_klass, false);
} else {
return cache->Zero();
}
diff --git a/src/verifier/reg_type_cache.cc b/src/verifier/reg_type_cache.cc
index 8e23b74..7153768 100644
--- a/src/verifier/reg_type_cache.cc
+++ b/src/verifier/reg_type_cache.cc
@@ -179,7 +179,7 @@
//To pass the verification, the type should be imprecise,
// instantiable or an interface with the precise type set to false.
- CHECK(!precise || klass->IsInstantiable());
+ DCHECK(!precise || klass->IsInstantiable());
// Create a precise type if:
// 1- Class is final and NOT an interface. a precise interface
@@ -189,10 +189,9 @@
RegType* entry;
// Create an imprecise type if we can't tell for a fact that it is precise.
if ((klass->IsFinal()) || precise) {
- CHECK(!(klass->IsAbstract()) || klass->IsArrayClass());
- CHECK(!klass->IsInterface());
+ DCHECK(!(klass->IsAbstract()) || klass->IsArrayClass());
+ DCHECK(!klass->IsInterface());
entry = new PreciseReferenceType(klass, descriptor, entries_.size());
-
} else {
entry = new ReferenceType(klass, descriptor, entries_.size());
}
@@ -372,7 +371,7 @@
return *cur_entry;
}
}
- std::string descriptor = "";
+ std::string descriptor("");
entry = new UninitialisedReferenceType(klass, descriptor, allocation_pc, entries_.size());
}
entries_.push_back(entry);
@@ -401,17 +400,34 @@
return *cur_entry;
}
}
- std::string descriptor = "";
+ std::string descriptor("");
entry = new ReferenceType(klass, descriptor, entries_.size());
} else {
- for (size_t i = primitive_count_; i < entries_.size(); i++) {
- RegType* cur_entry = entries_[i];
- if (cur_entry->IsPreciseReference() && cur_entry->GetClass() == klass) {
- return *cur_entry;
+ std::string descriptor;
+ if (klass->IsFinal()) {
+ if (klass->IsInstantiable()) {
+ for (size_t i = primitive_count_; i < entries_.size(); i++) {
+ RegType* cur_entry = entries_[i];
+ if (cur_entry->IsPreciseReference() && cur_entry->GetClass() == klass) {
+ return *cur_entry;
+ }
+ }
+ // Precise type was not found , create one !
+ entry = new PreciseReferenceType(klass, descriptor, entries_.size());
+ } else {
+ return Conflict();
+ }
+ } else {
+ // Not a final class, create an imprecise reference. Look up if we have it in the cache first.
+ for (size_t i = primitive_count_; i < entries_.size(); i++) {
+ RegType* cur_entry = entries_[i];
+ if (cur_entry->IsReference() && !(cur_entry->IsPrecise()) &&
+ cur_entry->GetClass() == klass) {
+ return *cur_entry;
+ }
}
+ entry = new ReferenceType(klass, descriptor, entries_.size());
}
- std::string descriptor = "";
- entry = new PreciseReferenceType(klass, descriptor, entries_.size());
}
}
entries_.push_back(entry);
@@ -447,7 +463,7 @@
return *cur_entry;
}
}
- std::string descriptor = "";
+ std::string descriptor("");
entry = new UninitialisedThisReferenceType(klass, descriptor, entries_.size());
}
entries_.push_back(entry);