More zero-check eliminator improvements
Gary Benson
gbenson at redhat.com
Mon Mar 23 06:43:10 PDT 2009
Gary Benson wrote:
> This patch allows Shark's zero-check eliminator to eliminate checks
> through phid states. Previously, zero-checked status was lost
> whenever the flow passed through a phi, meaning checks were
> performed unnecessarily.
*This* patch. Not the other one...
Cheers,
Gary
--
http://gbenson.net/
-------------- next part --------------
diff -r 371412771066 ChangeLog
--- a/ChangeLog Sat Mar 21 10:10:02 2009 +0100
+++ b/ChangeLog Mon Mar 23 09:33:03 2009 -0400
@@ -1,3 +1,41 @@
+2009-03-23 Gary Benson <gbenson at redhat.com>
+
+ * ports/hotspot/src/share/vm/shark/sharkFunction.hpp:
+ (SharkFunction::_deferred_zero_checks): New field.
+ (SharkFunction::deferred_zero_checks): New method.
+ (SharkFunction::add_deferred_zero_check): Likewise.
+ (SharkFunction::do_deferred_zero_checks): Likewise.
+ * ports/hotspot/src/share/vm/shark/sharkFunction.cpp:
+ (SharkFunction::DeferredZeroCheck): New class.
+ (SharkFunction::add_deferred_zero_check): New method.
+ (SharkFunction::do_deferred_zero_checks): Likewise.
+ (SharkFunction::initialize): Do deferred zero checks
+ after parsing blocks.
+
+ * ports/hotspot/src/share/vm/shark/sharkTopLevelBlock.hpp
+ (SharkBlock::zero_check_value): New method.
+ (SharkBlock::do_deferred_zero_check): Likewise.
+ * ports/hotspot/src/share/vm/shark/sharkTopLevelBlock.cpp
+ (SharkBlock::do_zero_check): Defer ambiguous zero checks.
+ (SharkBlock::zero_check_value): New method.
+ (SharkBlock::do_deferred_zero_check): Likewise.
+ (SharkTopLevelBlock::handle_exception): Don't copy state.
+ (SharkTopLevelBlock::do_if): Likewise.
+ (SharkTopLevelBlock::do_switch): Likewise.
+
+ * ports/hotspot/src/share/vm/shark/sharkValue.hpp
+ (SharkPHIValue): New class.
+ (SharkValue::is_phi): New method.
+ (SharkValue::as_phi): Likewise.
+ (SharkValue::create_phi): Likewise.
+ (SharkValue::merge): Likewise.
+ (SharkNormalValue::merge): Likewise.
+ (SharkAddressValue::merge): Likewise.
+
+ * ports/hotspot/src/share/vm/shark/sharkState.cpp
+ (SharkPHIState::SharkPHIState): Create SharkPHIValues.
+ (SharkState::merge): Defer to SharkValue::merge.
+
2009-03-21 Matthias Klose <doko at ubuntu.com>
* patches/hotspot/*/icedtea-text-relocations.patch: Build hotspot
diff -r 371412771066 ports/hotspot/src/share/vm/shark/sharkFunction.cpp
--- a/ports/hotspot/src/share/vm/shark/sharkFunction.cpp Sat Mar 21 10:10:02 2009 +0100
+++ b/ports/hotspot/src/share/vm/shark/sharkFunction.cpp Mon Mar 23 09:33:03 2009 -0400
@@ -123,6 +123,7 @@
block(i)->emit_IR();
}
+ do_deferred_zero_checks();
// Dump the bitcode, if requested
if (SharkPrintBitcodeOf != NULL) {
@@ -307,3 +308,80 @@
this,
builder()->CreateGEP(monitors_slots(), indexes, indexes + 2));
}
+
+class DeferredZeroCheck : public ResourceObj {
+ public:
+ DeferredZeroCheck(SharkTopLevelBlock* block, SharkValue* value)
+ : _block(block),
+ _value(value),
+ _bci(block->bci()),
+ _state(block->current_state()->copy()),
+ _check_block(builder()->GetInsertBlock()),
+ _continue_block(function()->CreateBlock("not_zero"))
+ {
+ builder()->SetInsertPoint(continue_block());
+ }
+
+ private:
+ SharkTopLevelBlock* _block;
+ SharkValue* _value;
+ int _bci;
+ SharkState* _state;
+ BasicBlock* _check_block;
+ BasicBlock* _continue_block;
+
+ public:
+ SharkTopLevelBlock* block() const
+ {
+ return _block;
+ }
+ SharkValue* value() const
+ {
+ return _value;
+ }
+ int bci() const
+ {
+ return _bci;
+ }
+ SharkState* state() const
+ {
+ return _state;
+ }
+ BasicBlock* check_block() const
+ {
+ return _check_block;
+ }
+ BasicBlock* continue_block() const
+ {
+ return _continue_block;
+ }
+
+ public:
+ SharkBuilder* builder() const
+ {
+ return block()->builder();
+ }
+ SharkFunction* function() const
+ {
+ return block()->function();
+ }
+
+ public:
+ void process() const
+ {
+ builder()->SetInsertPoint(check_block());
+ block()->do_deferred_zero_check(value(), bci(), state(), continue_block());
+ }
+};
+
+void SharkFunction::add_deferred_zero_check(SharkTopLevelBlock* block,
+ SharkValue* value)
+{
+ deferred_zero_checks()->append(new DeferredZeroCheck(block, value));
+}
+
+void SharkFunction::do_deferred_zero_checks()
+{
+ for (int i = 0; i < deferred_zero_checks()->length(); i++)
+ deferred_zero_checks()->at(i)->process();
+}
diff -r 371412771066 ports/hotspot/src/share/vm/shark/sharkFunction.hpp
--- a/ports/hotspot/src/share/vm/shark/sharkFunction.hpp Sat Mar 21 10:10:02 2009 +0100
+++ b/ports/hotspot/src/share/vm/shark/sharkFunction.hpp Mon Mar 23 09:33:03 2009 -0400
@@ -23,8 +23,10 @@
*
*/
+class SharkMonitor;
class SharkTopLevelBlock;
-class SharkMonitor;
+
+class DeferredZeroCheck;
class SharkFunction : public StackObj {
public:
@@ -44,16 +46,17 @@
void initialize();
private:
- SharkCompiler* _compiler;
- const char* _name;
- ciTypeFlow* _flow;
- ciBytecodeStream* _iter;
- MacroAssembler* _masm;
- llvm::Function* _function;
- SharkTopLevelBlock** _blocks;
- llvm::Value* _base_pc;
- llvm::Value* _thread;
- int _monitor_count;
+ SharkCompiler* _compiler;
+ const char* _name;
+ ciTypeFlow* _flow;
+ ciBytecodeStream* _iter;
+ MacroAssembler* _masm;
+ llvm::Function* _function;
+ SharkTopLevelBlock** _blocks;
+ llvm::Value* _base_pc;
+ llvm::Value* _thread;
+ int _monitor_count;
+ GrowableArray<DeferredZeroCheck*> _deferred_zero_checks;
public:
SharkCompiler* compiler() const
@@ -95,6 +98,10 @@
int monitor_count() const
{
return _monitor_count;
+ }
+ GrowableArray<DeferredZeroCheck*>* deferred_zero_checks()
+ {
+ return &_deferred_zero_checks;
}
public:
@@ -333,4 +340,12 @@
builder()->CreateStore(LLVMValue::null(), addr);
return result;
}
+
+ // Deferred zero checks
+ public:
+ void add_deferred_zero_check(SharkTopLevelBlock* block,
+ SharkValue* value);
+
+ private:
+ void do_deferred_zero_checks();
};
diff -r 371412771066 ports/hotspot/src/share/vm/shark/sharkState.cpp
--- a/ports/hotspot/src/share/vm/shark/sharkState.cpp Sat Mar 21 10:10:02 2009 +0100
+++ b/ports/hotspot/src/share/vm/shark/sharkState.cpp Mon Mar 23 09:33:03 2009 -0400
@@ -130,14 +130,11 @@
BasicBlock* other_block,
BasicBlock* this_block)
{
- PHINode *phi;
- char name[18];
-
// Method
Value *this_method = this->method();
Value *other_method = other->method();
if (this_method != other_method) {
- phi = builder()->CreatePHI(SharkType::methodOop_type(), "method");
+ PHINode *phi = builder()->CreatePHI(SharkType::methodOop_type(), "method");
phi->addIncoming(this_method, this_block);
phi->addIncoming(other_method, other_block);
set_method(phi);
@@ -149,20 +146,12 @@
SharkValue *this_value = this->local(i);
SharkValue *other_value = other->local(i);
assert((this_value == NULL) == (other_value == NULL), "should be");
- if (this_value == other_value)
- continue;
-
- ciType *this_type = this_value->type();
- assert(this_type == other_value->type(), "should be");
-
- bool this_checked = this_value->zero_checked();
- assert(this_checked == other_value->zero_checked(), "should be");
-
- snprintf(name, sizeof(name), "local_%d_", i);
- phi = builder()->CreatePHI(SharkType::to_stackType(this_type), name);
- phi->addIncoming(this_value->generic_value(), this_block);
- phi->addIncoming(other_value->generic_value(), other_block);
- set_local(i, SharkValue::create_generic(this_type, phi, this_checked));
+ if (this_value != NULL) {
+ char name[18];
+ snprintf(name, sizeof(name), "local_%d_", i);
+ set_local(i, this_value->merge(
+ builder(), other_value, other_block, this_block, name));
+ }
}
// Expression stack
@@ -171,20 +160,12 @@
SharkValue *this_value = this->stack(i);
SharkValue *other_value = other->stack(i);
assert((this_value == NULL) == (other_value == NULL), "should be");
- if (this_value == other_value)
- continue;
-
- ciType *this_type = this_value->type();
- assert(this_type == other_value->type(), "should be");
-
- bool this_checked = this_value->zero_checked();
- assert(this_checked == other_value->zero_checked(), "should be");
-
- snprintf(name, sizeof(name), "stack_%d_", i);
- phi = builder()->CreatePHI(SharkType::to_stackType(this_type), name);
- phi->addIncoming(this_value->generic_value(), this_block);
- phi->addIncoming(other_value->generic_value(), other_block);
- set_stack(i, SharkValue::create_generic(this_type, phi, this_checked));
+ if (this_value != NULL) {
+ char name[18];
+ snprintf(name, sizeof(name), "stack_%d_", i);
+ set_stack(i, this_value->merge(
+ builder(), other_value, other_block, this_block, name));
+ }
}
}
@@ -315,10 +296,8 @@
case T_OBJECT:
case T_ARRAY:
snprintf(name, sizeof(name), "local_%d_", i);
- value = SharkValue::create_generic(
- type,
- builder()->CreatePHI(SharkType::to_stackType(type), name),
- false);
+ value = SharkValue::create_phi(
+ type, builder()->CreatePHI(SharkType::to_stackType(type), name));
break;
case T_ADDRESS:
@@ -355,10 +334,8 @@
case T_OBJECT:
case T_ARRAY:
snprintf(name, sizeof(name), "stack_%d_", i);
- value = SharkValue::create_generic(
- type,
- builder()->CreatePHI(SharkType::to_stackType(type), name),
- false);
+ value = SharkValue::create_phi(
+ type, builder()->CreatePHI(SharkType::to_stackType(type), name));
break;
case T_ADDRESS:
diff -r 371412771066 ports/hotspot/src/share/vm/shark/sharkTopLevelBlock.cpp
--- a/ports/hotspot/src/share/vm/shark/sharkTopLevelBlock.cpp Sat Mar 21 10:10:02 2009 +0100
+++ b/ports/hotspot/src/share/vm/shark/sharkTopLevelBlock.cpp Mon Mar 23 09:33:03 2009 -0400
@@ -250,8 +250,40 @@
void SharkTopLevelBlock::do_zero_check(SharkValue *value)
{
- BasicBlock *zero = function()->CreateBlock("zero");
- BasicBlock *not_zero = function()->CreateBlock("not_zero");
+ if (value->is_phi() && value->as_phi()->all_incomers_zero_checked()) {
+ function()->add_deferred_zero_check(this, value);
+ }
+ else {
+ BasicBlock *continue_block = function()->CreateBlock("not_zero");
+ SharkState *saved_state = current_state();
+ set_current_state(saved_state->copy());
+ zero_check_value(value, continue_block);
+ builder()->SetInsertPoint(continue_block);
+ set_current_state(saved_state);
+ }
+
+ value->set_zero_checked(true);
+}
+
+void SharkTopLevelBlock::do_deferred_zero_check(SharkValue* value,
+ int bci,
+ SharkState* saved_state,
+ BasicBlock* continue_block)
+{
+ if (value->as_phi()->all_incomers_zero_checked()) {
+ builder()->CreateBr(continue_block);
+ }
+ else {
+ iter()->force_bci(start());
+ set_current_state(saved_state);
+ zero_check_value(value, continue_block);
+ }
+}
+
+void SharkTopLevelBlock::zero_check_value(SharkValue* value,
+ BasicBlock* continue_block)
+{
+ BasicBlock *zero_block = builder()->CreateBlock(continue_block, "zero");
Value *a, *b;
switch (value->basic_type()) {
@@ -276,10 +308,10 @@
ShouldNotReachHere();
}
- builder()->CreateCondBr(builder()->CreateICmpNE(a, b), not_zero, zero);
+ builder()->CreateCondBr(
+ builder()->CreateICmpNE(a, b), continue_block, zero_block);
- builder()->SetInsertPoint(zero);
- SharkState *saved_state = current_state()->copy();
+ builder()->SetInsertPoint(zero_block);
if (value->is_jobject()) {
call_vm_nocheck(
SharkRuntime::throw_NullPointerException(),
@@ -290,11 +322,6 @@
builder()->CreateUnimplemented(__FILE__, __LINE__);
}
handle_exception(function()->CreateGetPendingException());
- set_current_state(saved_state);
-
- builder()->SetInsertPoint(not_zero);
-
- value->set_zero_checked(true);
}
void SharkTopLevelBlock::check_bounds(SharkValue* array, SharkValue* index)
@@ -402,7 +429,7 @@
LLVMValue::jint_constant(i),
handler->entry_block());
- handler->add_incoming(current_state()->copy());
+ handler->add_incoming(current_state());
}
builder()->SetInsertPoint(no_handler);
@@ -776,8 +803,6 @@
// All propagation of state from one block to the next (via
// dest->add_incoming) is handled by the next three methods
// (do_branch, do_if and do_switch) and by handle_exception.
-// Where control flow forks, each successor must have its
-// own copy of the state.
void SharkTopLevelBlock::do_branch(int successor_index)
{
@@ -808,7 +833,7 @@
if_taken->entry_block(), not_taken->entry_block());
if_taken->add_incoming(current_state());
- not_taken->add_incoming(current_state()->copy());
+ not_taken->add_incoming(current_state());
}
void SharkTopLevelBlock::do_switch()
@@ -827,7 +852,7 @@
switchinst->addCase(
LLVMValue::jint_constant(switch_key(i)),
dest_block->entry_block());
- dest_block->add_incoming(current_state()->copy());
+ dest_block->add_incoming(current_state());
}
}
}
diff -r 371412771066 ports/hotspot/src/share/vm/shark/sharkTopLevelBlock.hpp
--- a/ports/hotspot/src/share/vm/shark/sharkTopLevelBlock.hpp Sat Mar 21 10:10:02 2009 +0100
+++ b/ports/hotspot/src/share/vm/shark/sharkTopLevelBlock.hpp Mon Mar 23 09:33:03 2009 -0400
@@ -185,10 +185,20 @@
// Helpers
private:
- void do_zero_check(SharkValue* value);
llvm::Value* lookup_for_ldc();
llvm::Value* lookup_for_field_access();
void do_branch(int successor_index);
+
+ // Zero checks
+ private:
+ void do_zero_check(SharkValue* value);
+ void zero_check_value(SharkValue* value, llvm::BasicBlock* continue_block);
+
+ public:
+ void do_deferred_zero_check(SharkValue* value,
+ int bci,
+ SharkState* saved_state,
+ llvm::BasicBlock* continue_block);
// VM calls
private:
diff -r 371412771066 ports/hotspot/src/share/vm/shark/sharkValue.cpp
--- a/ports/hotspot/src/share/vm/shark/sharkValue.cpp Sat Mar 21 10:10:02 2009 +0100
+++ b/ports/hotspot/src/share/vm/shark/sharkValue.cpp Mon Mar 23 09:33:03 2009 -0400
@@ -34,9 +34,32 @@
{
return SharkValue::create_generic(type(), generic_value(), zero_checked());
}
+SharkValue* SharkPHIValue::clone() const
+{
+ return SharkValue::create_phi(type(), (PHINode *) generic_value(), this);
+}
SharkValue* SharkAddressValue::clone() const
{
return SharkValue::address_constant(address_value());
+}
+
+// Casting
+
+bool SharkValue::is_phi() const
+{
+ return false;
+}
+bool SharkPHIValue::is_phi() const
+{
+ return true;
+}
+SharkPHIValue* SharkValue::as_phi()
+{
+ ShouldNotCallThis();
+}
+SharkPHIValue* SharkPHIValue::as_phi()
+{
+ return this;
}
// Comparison
@@ -225,17 +248,49 @@
return builder->CreatePtrToInt(jobject_value(), SharkType::intptr_type());
}
-// Phi-style stuff
+// Phi-style stuff for SharkPHIState::add_incoming
-void SharkNormalValue::addIncoming(SharkValue *value, BasicBlock* block)
+void SharkValue::addIncoming(SharkValue *value, BasicBlock* block)
{
- assert(llvm::isa<llvm::PHINode>(generic_value()), "should be");
+ ShouldNotCallThis();
+}
+void SharkPHIValue::addIncoming(SharkValue *value, BasicBlock* block)
+{
+ assert(!is_clone(), "shouldn't be");
((llvm::PHINode *) generic_value())->addIncoming(
value->generic_value(), block);
+ if (!value->zero_checked())
+ _all_incomers_zero_checked = false;
}
void SharkAddressValue::addIncoming(SharkValue *value, BasicBlock* block)
{
assert(this->equal_to(value), "should be");
+}
+
+// Phi-style stuff for SharkState::merge
+
+SharkValue* SharkNormalValue::merge(SharkBuilder* builder,
+ SharkValue* other,
+ BasicBlock* other_block,
+ BasicBlock* this_block,
+ const char* name)
+{
+ assert(type() == other->type(), "should be");
+ assert(zero_checked() == other->zero_checked(), "should be");
+
+ PHINode *phi = builder->CreatePHI(SharkType::to_stackType(type()), name);
+ phi->addIncoming(this->generic_value(), this_block);
+ phi->addIncoming(other->generic_value(), other_block);
+ return SharkValue::create_generic(type(), phi, zero_checked());
+}
+SharkValue* SharkAddressValue::merge(SharkBuilder* builder,
+ SharkValue* other,
+ BasicBlock* other_block,
+ BasicBlock* this_block,
+ const char* name)
+{
+ assert(this->equal_to(other), "should be");
+ return this;
}
// Repeated null and divide-by-zero check removal
diff -r 371412771066 ports/hotspot/src/share/vm/shark/sharkValue.hpp
--- a/ports/hotspot/src/share/vm/shark/sharkValue.hpp Sat Mar 21 10:10:02 2009 +0100
+++ b/ports/hotspot/src/share/vm/shark/sharkValue.hpp Mon Mar 23 09:33:03 2009 -0400
@@ -24,7 +24,9 @@
*/
// Items on the stack and in local variables are tracked using
-// SharkValue objects. There are two types, SharkNormalValue
+// SharkValue objects.
+//
+// All SharkValues are one of two core types, SharkNormalValue
// and SharkAddressValue, but no code outside this file should
// ever refer to those directly. The split is because of the
// way JSRs are handled: the typeflow pass expands them into
@@ -32,8 +34,14 @@
// popped by ret only exist at compile time. Having separate
// classes for these allows us to check that our jsr handling
// is correct, via assertions.
+//
+// There is one more type, SharkPHIValue, which is a subclass
+// of SharkNormalValue with a couple of extra methods. Use of
+// SharkPHIValue outside of this file is acceptable, so long
+// as it is obtained via SharkValue::as_phi().
class SharkBuilder;
+class SharkPHIValue;
class SharkValue : public ResourceObj {
protected:
@@ -42,6 +50,11 @@
// Cloning
public:
virtual SharkValue* clone() const = 0;
+
+ // Casting
+ public:
+ virtual bool is_phi() const;
+ virtual SharkPHIValue* as_phi();
// Comparison
public:
@@ -180,10 +193,18 @@
static inline SharkValue* create_generic(ciType* type,
llvm::Value* value,
bool zero_checked);
+ static inline SharkValue* create_phi(ciType* type,
+ llvm::PHINode* phi,
+ const SharkPHIValue* parent = NULL);
// Phi-style stuff
public:
- virtual void addIncoming(SharkValue *value, llvm::BasicBlock* block) = 0;
+ virtual void addIncoming(SharkValue* value, llvm::BasicBlock* block);
+ virtual SharkValue* merge(SharkBuilder* builder,
+ SharkValue* other,
+ llvm::BasicBlock* other_block,
+ llvm::BasicBlock* this_block,
+ const char* name) = 0;
// Repeated null and divide-by-zero check removal
public:
@@ -245,9 +266,13 @@
llvm::Value* generic_value() const;
llvm::Value* intptr_value(SharkBuilder* builder) const;
- // Wrapped PHINodes
+ // Phi-style stuff
public:
- void addIncoming(SharkValue *value, llvm::BasicBlock* block);
+ SharkValue* merge(SharkBuilder* builder,
+ SharkValue* other,
+ llvm::BasicBlock* other_block,
+ llvm::BasicBlock* this_block,
+ const char* name);
// Repeated null and divide-by-zero check removal
public:
@@ -255,12 +280,51 @@
void set_zero_checked(bool zero_checked);
};
-inline SharkValue* SharkValue::create_generic(ciType* type,
- llvm::Value* value,
- bool zero_checked)
-{
- return new SharkNormalValue(type, value, zero_checked);
-}
+class SharkPHIValue : public SharkNormalValue {
+ friend class SharkValue;
+
+ protected:
+ SharkPHIValue(ciType* type, llvm::PHINode* phi, const SharkPHIValue *parent)
+ : SharkNormalValue(type, phi, parent && parent->zero_checked()),
+ _parent(parent),
+ _all_incomers_zero_checked(true) {}
+
+ private:
+ const SharkPHIValue* _parent;
+ bool _all_incomers_zero_checked;
+
+ private:
+ const SharkPHIValue* parent() const
+ {
+ return _parent;
+ }
+ bool is_clone() const
+ {
+ return parent() != NULL;
+ }
+
+ public:
+ bool all_incomers_zero_checked() const
+ {
+ if (is_clone())
+ return parent()->all_incomers_zero_checked();
+
+ return _all_incomers_zero_checked;
+ }
+
+ // Cloning
+ public:
+ SharkValue* clone() const;
+
+ // Casting
+ public:
+ bool is_phi() const;
+ SharkPHIValue* as_phi();
+
+ // Phi-style stuff
+ public:
+ void addIncoming(SharkValue *value, llvm::BasicBlock* block);
+};
class SharkAddressValue : public SharkValue {
friend class SharkValue;
@@ -297,7 +361,28 @@
// Phi-style stuff
public:
void addIncoming(SharkValue *value, llvm::BasicBlock* block);
+ SharkValue* merge(SharkBuilder* builder,
+ SharkValue* other,
+ llvm::BasicBlock* other_block,
+ llvm::BasicBlock* this_block,
+ const char* name);
};
+
+// SharkValue methods that can't be declared above
+
+inline SharkValue* SharkValue::create_generic(ciType* type,
+ llvm::Value* value,
+ bool zero_checked)
+{
+ return new SharkNormalValue(type, value, zero_checked);
+}
+
+inline SharkValue* SharkValue::create_phi(ciType* type,
+ llvm::PHINode* phi,
+ const SharkPHIValue* parent)
+{
+ return new SharkPHIValue(type, phi, parent);
+}
inline SharkValue* SharkValue::address_constant(int bci)
{
More information about the distro-pkg-dev
mailing list