- Revision
- 215365
- Author
- fpi...@apple.com
- Date
- 2017-04-14 10:43:42 -0700 (Fri, 14 Apr 2017)
Log Message
Air::RegLiveness should be constraint-based
https://bugs.webkit.org/show_bug.cgi?id=170817
Reviewed by Saam Barati.
Previously, I changed the Air liveness analyses based on Air::Liveness<> to be
constraint-based and this was a significant speed-up. Now I'm adding the same
functionality to RegLiveness.
This is a 1% speed-up on wasm B3 -O1 compile times.
* b3/air/AirAllocateRegistersAndStackByLinearScan.cpp:
* b3/air/AirLivenessAdapter.h:
(JSC::B3::Air::LivenessAdapter::LivenessAdapter):
(JSC::B3::Air::LivenessAdapter::prepareToCompute):
(JSC::B3::Air::LivenessAdapter::actionsAt):
* b3/air/AirRegLiveness.cpp:
(JSC::B3::Air::RegLiveness::RegLiveness):
(JSC::B3::Air::RegLiveness::LocalCalcForUnifiedTmpLiveness::LocalCalcForUnifiedTmpLiveness):
(JSC::B3::Air::RegLiveness::LocalCalcForUnifiedTmpLiveness::execute):
(JSC::B3::Air::RegLiveness::LocalCalc::execute): Deleted.
* b3/air/AirRegLiveness.h:
(JSC::B3::Air::RegLiveness::Actions::Actions):
(JSC::B3::Air::RegLiveness::LocalCalcBase::LocalCalcBase):
(JSC::B3::Air::RegLiveness::LocalCalcBase::live):
(JSC::B3::Air::RegLiveness::LocalCalcBase::isLive):
(JSC::B3::Air::RegLiveness::LocalCalc::LocalCalc):
(JSC::B3::Air::RegLiveness::LocalCalc::execute):
(JSC::B3::Air::RegLiveness::LocalCalc::live): Deleted.
(JSC::B3::Air::RegLiveness::LocalCalc::isLive): Deleted.
Modified Paths
Diff
Modified: trunk/Source/_javascript_Core/ChangeLog (215364 => 215365)
--- trunk/Source/_javascript_Core/ChangeLog 2017-04-14 17:31:50 UTC (rev 215364)
+++ trunk/Source/_javascript_Core/ChangeLog 2017-04-14 17:43:42 UTC (rev 215365)
@@ -1,3 +1,36 @@
+2017-04-13 Filip Pizlo <fpi...@apple.com>
+
+ Air::RegLiveness should be constraint-based
+ https://bugs.webkit.org/show_bug.cgi?id=170817
+
+ Reviewed by Saam Barati.
+
+ Previously, I changed the Air liveness analyses based on Air::Liveness<> to be
+ constraint-based and this was a significant speed-up. Now I'm adding the same
+ functionality to RegLiveness.
+
+ This is a 1% speed-up on wasm B3 -O1 compile times.
+
+ * b3/air/AirAllocateRegistersAndStackByLinearScan.cpp:
+ * b3/air/AirLivenessAdapter.h:
+ (JSC::B3::Air::LivenessAdapter::LivenessAdapter):
+ (JSC::B3::Air::LivenessAdapter::prepareToCompute):
+ (JSC::B3::Air::LivenessAdapter::actionsAt):
+ * b3/air/AirRegLiveness.cpp:
+ (JSC::B3::Air::RegLiveness::RegLiveness):
+ (JSC::B3::Air::RegLiveness::LocalCalcForUnifiedTmpLiveness::LocalCalcForUnifiedTmpLiveness):
+ (JSC::B3::Air::RegLiveness::LocalCalcForUnifiedTmpLiveness::execute):
+ (JSC::B3::Air::RegLiveness::LocalCalc::execute): Deleted.
+ * b3/air/AirRegLiveness.h:
+ (JSC::B3::Air::RegLiveness::Actions::Actions):
+ (JSC::B3::Air::RegLiveness::LocalCalcBase::LocalCalcBase):
+ (JSC::B3::Air::RegLiveness::LocalCalcBase::live):
+ (JSC::B3::Air::RegLiveness::LocalCalcBase::isLive):
+ (JSC::B3::Air::RegLiveness::LocalCalc::LocalCalc):
+ (JSC::B3::Air::RegLiveness::LocalCalc::execute):
+ (JSC::B3::Air::RegLiveness::LocalCalc::live): Deleted.
+ (JSC::B3::Air::RegLiveness::LocalCalc::isLive): Deleted.
+
2017-04-13 JF Bastien <jfbast...@apple.com>
WebAssembly: fix windows build
Modified: trunk/Source/_javascript_Core/b3/air/AirAllocateRegistersAndStackByLinearScan.cpp (215364 => 215365)
--- trunk/Source/_javascript_Core/b3/air/AirAllocateRegistersAndStackByLinearScan.cpp 2017-04-14 17:31:50 UTC (rev 215364)
+++ trunk/Source/_javascript_Core/b3/air/AirAllocateRegistersAndStackByLinearScan.cpp 2017-04-14 17:43:42 UTC (rev 215365)
@@ -221,6 +221,10 @@
for (unsigned instIndex = 0; instIndex < block->size(); ++instIndex) {
Inst& inst = block->at(instIndex);
size_t indexOfEarly = indexOfHead + instIndex * 2;
+ // FIXME: We can get this information from the liveness constraints. Except of
+ // course we want to separate the earlies of one instruction from the lates of
+ // the next.
+ // https://bugs.webkit.org/show_bug.cgi?id=170850
inst.forEachTmp(
[&] (Tmp& tmp, Arg::Role role, Bank, Width) {
if (tmp.isReg())
@@ -229,10 +233,15 @@
});
}
- RegLiveness::LocalCalc localCalc(liveness, block);
+ RegLiveness::LocalCalcForUnifiedTmpLiveness localCalc(liveness, block);
auto record = [&] (unsigned instIndex) {
- RegisterSet regs = localCalc.live();
+ // FIXME: This could get the register sets from somewhere else, like the
+ // liveness constraints. Except we want those constraints to be laid out like
+ // how they would have been by RegLiveness, since we want to separate the lates
+ // of one inst from the earlies of the next.
+ // https://bugs.webkit.org/show_bug.cgi?id=170850
+ const RegisterSet& regs = localCalc.live();
if (Inst* prev = block->get(instIndex - 1)) {
RegisterSet prevRegs = regs;
prev->forEach<Reg>(
Modified: trunk/Source/_javascript_Core/b3/air/AirLivenessAdapter.h (215364 => 215365)
--- trunk/Source/_javascript_Core/b3/air/AirLivenessAdapter.h 2017-04-14 17:31:50 UTC (rev 215364)
+++ trunk/Source/_javascript_Core/b3/air/AirLivenessAdapter.h 2017-04-14 17:43:42 UTC (rev 215365)
@@ -33,6 +33,7 @@
#include "AirInstInlines.h"
#include "AirStackSlot.h"
#include "AirTmpInlines.h"
+#include <wtf/IndexMap.h>
namespace JSC { namespace B3 { namespace Air {
@@ -53,7 +54,7 @@
LivenessAdapter(Code& code)
: code(code)
- , m_actions(code.size())
+ , actions(code.size())
{
}
@@ -65,7 +66,7 @@
void prepareToCompute()
{
for (BasicBlock* block : code) {
- ActionsForBoundary& actionsForBoundary = m_actions[block];
+ ActionsForBoundary& actionsForBoundary = actions[block];
actionsForBoundary.resize(block->size() + 1);
for (size_t instIndex = block->size(); instIndex--;) {
@@ -92,7 +93,7 @@
Actions& actionsAt(BasicBlock* block, unsigned instBoundaryIndex)
{
- return m_actions[block][instBoundaryIndex];
+ return actions[block][instBoundaryIndex];
}
unsigned blockSize(BasicBlock* block)
@@ -115,7 +116,7 @@
}
Code& code;
- IndexMap<BasicBlock*, ActionsForBoundary> m_actions;
+ IndexMap<BasicBlock*, ActionsForBoundary> actions;
};
template<Bank adapterBank, Arg::Temperature minimumTemperature = Arg::Cold>
Modified: trunk/Source/_javascript_Core/b3/air/AirRegLiveness.cpp (215364 => 215365)
--- trunk/Source/_javascript_Core/b3/air/AirRegLiveness.cpp 2017-04-14 17:31:50 UTC (rev 215364)
+++ trunk/Source/_javascript_Core/b3/air/AirRegLiveness.cpp 2017-04-14 17:43:42 UTC (rev 215365)
@@ -36,7 +36,29 @@
RegLiveness::RegLiveness(Code& code)
: m_liveAtHead(code.size())
, m_liveAtTail(code.size())
+ , m_actions(code.size())
{
+ // Compute constraints.
+ for (BasicBlock* block : code) {
+ ActionsForBoundary& actionsForBoundary = m_actions[block];
+ actionsForBoundary.resize(block->size() + 1);
+
+ for (size_t instIndex = block->size(); instIndex--;) {
+ Inst& inst = block->at(instIndex);
+ inst.forEach<Reg>(
+ [&] (Reg& reg, Arg::Role role, Bank, Width) {
+ if (Arg::isEarlyUse(role))
+ actionsForBoundary[instIndex].use.add(reg);
+ if (Arg::isEarlyDef(role))
+ actionsForBoundary[instIndex].def.add(reg);
+ if (Arg::isLateUse(role))
+ actionsForBoundary[instIndex + 1].use.add(reg);
+ if (Arg::isLateDef(role))
+ actionsForBoundary[instIndex + 1].def.add(reg);
+ });
+ }
+ }
+
// The liveAtTail of each block automatically contains the LateUse's of the terminal.
for (BasicBlock* block : code) {
RegisterSet& liveAtTail = m_liveAtTail[block];
@@ -98,43 +120,29 @@
{
}
-void RegLiveness::LocalCalc::execute(unsigned instIndex)
+RegLiveness::LocalCalcForUnifiedTmpLiveness::LocalCalcForUnifiedTmpLiveness(UnifiedTmpLiveness& liveness, BasicBlock* block)
+ : LocalCalcBase(block)
+ , m_code(liveness.code)
+ , m_actions(liveness.actions[block])
{
- Inst& inst = m_block->at(instIndex);
-
- // First handle the early def's of the next instruction.
- if (instIndex + 1 < m_block->size()) {
- Inst& nextInst = m_block->at(instIndex + 1);
- nextInst.forEach<Reg>(
- [&] (Reg& reg, Arg::Role role, Bank, Width) {
- if (Arg::isEarlyDef(role))
- m_workset.remove(reg);
- });
+ for (Tmp tmp : liveness.liveAtTail(block)) {
+ if (tmp.isReg())
+ m_workset.add(tmp.reg());
}
-
- // Then handle def's.
- inst.forEach<Reg>(
- [&] (Reg& reg, Arg::Role role, Bank, Width) {
- if (Arg::isLateDef(role))
- m_workset.remove(reg);
- });
-
- // Then handle use's.
- inst.forEach<Reg>(
- [&] (Reg& reg, Arg::Role role, Bank, Width) {
- if (Arg::isEarlyUse(role))
- m_workset.add(reg);
- });
-
- // And finally, handle the late use's of the previous instruction.
- if (instIndex) {
- Inst& prevInst = m_block->at(instIndex - 1);
- prevInst.forEach<Reg>(
- [&] (Reg& reg, Arg::Role role, Bank, Width) {
- if (Arg::isLateUse(role))
- m_workset.add(reg);
- });
+}
+
+void RegLiveness::LocalCalcForUnifiedTmpLiveness::execute(unsigned instIndex)
+{
+ for (unsigned index : m_actions[instIndex + 1].def) {
+ Tmp tmp = Tmp::tmpForLinearIndex(m_code, index);
+ if (tmp.isReg())
+ m_workset.remove(tmp.reg());
}
+ for (unsigned index : m_actions[instIndex].use) {
+ Tmp tmp = Tmp::tmpForLinearIndex(m_code, index);
+ if (tmp.isReg())
+ m_workset.add(tmp.reg());
+ }
}
} } } // namespace JSC::B3::Air
Modified: trunk/Source/_javascript_Core/b3/air/AirRegLiveness.h (215364 => 215365)
--- trunk/Source/_javascript_Core/b3/air/AirRegLiveness.h 2017-04-14 17:31:50 UTC (rev 215364)
+++ trunk/Source/_javascript_Core/b3/air/AirRegLiveness.h 2017-04-14 17:43:42 UTC (rev 215365)
@@ -32,6 +32,7 @@
#include "AirInst.h"
#include "AirLiveness.h"
#include "RegisterSet.h"
+#include <wtf/IndexMap.h>
namespace JSC { namespace B3 { namespace Air {
@@ -40,6 +41,15 @@
// register liveness. This is a specialization of Liveness<> that uses bitvectors directly.
// This makes the code sufficiently different that it didn't make sense to try to share code.
class RegLiveness {
+ struct Actions {
+ Actions() { }
+
+ RegisterSet use;
+ RegisterSet def;
+ };
+
+ typedef Vector<Actions, 0, UnsafeVectorOverflow> ActionsForBoundary;
+
public:
typedef Reg Thing;
@@ -46,56 +56,61 @@
RegLiveness(Code& code);
~RegLiveness();
- // This calculator has to be run in reverse.
- class LocalCalc {
+ class LocalCalcBase {
public:
- LocalCalc(RegLiveness& liveness, BasicBlock* block)
+ LocalCalcBase(BasicBlock* block)
: m_block(block)
- , m_workset(liveness.m_liveAtTail[block])
{
}
- // If you computed Tmp liveness for some bank, you can use reg liveness to fill in the blanks.
- // Note that what happens to the registers not belonging to the bank is arbitrary - they may get
- // set or not.
- template<Bank bank>
- LocalCalc(TmpLiveness<bank>& liveness, BasicBlock* block)
- : m_block(block)
+ const RegisterSet& live() const
{
- for (Tmp tmp : liveness.liveAtTail(block)) {
- if (tmp.isReg())
- m_workset.set(tmp.reg());
- }
+ return m_workset;
}
- LocalCalc(UnifiedTmpLiveness& liveness, BasicBlock* block)
- : m_block(block)
+ bool isLive(Reg reg) const
{
- for (Tmp tmp : liveness.liveAtTail(block)) {
- if (tmp.isReg())
- m_workset.set(tmp.reg());
- }
+ return m_workset.contains(reg);
}
- const RegisterSet& live() const
+ protected:
+ BasicBlock* m_block;
+ RegisterSet m_workset;
+ };
+
+ // This calculator has to be run in reverse.
+ class LocalCalc : public LocalCalcBase {
+ public:
+ LocalCalc(RegLiveness& liveness, BasicBlock* block)
+ : LocalCalcBase(block)
+ , m_actions(liveness.m_actions[block])
{
- return m_workset;
+ m_workset = liveness.m_liveAtTail[block];
}
- bool isLive(Reg reg) const
+ void execute(unsigned instIndex)
{
- return m_workset.contains(reg);
+ m_workset.exclude(m_actions[instIndex + 1].def);
+ m_workset.merge(m_actions[instIndex].use);
}
- void execute(unsigned instIndex);
-
private:
friend class RegLiveness;
- BasicBlock* m_block;
- RegisterSet m_workset;
+ ActionsForBoundary& m_actions;
};
+ class LocalCalcForUnifiedTmpLiveness : public LocalCalcBase {
+ public:
+ LocalCalcForUnifiedTmpLiveness(UnifiedTmpLiveness& liveness, BasicBlock* block);
+
+ void execute(unsigned instIndex);
+
+ private:
+ Code& m_code;
+ UnifiedTmpLiveness::ActionsForBoundary& m_actions;
+ };
+
const RegisterSet& liveAtHead(BasicBlock* block) const
{
return m_liveAtHead[block];
@@ -109,6 +124,7 @@
private:
IndexMap<BasicBlock*, RegisterSet> m_liveAtHead;
IndexMap<BasicBlock*, RegisterSet> m_liveAtTail;
+ IndexMap<BasicBlock*, ActionsForBoundary> m_actions;
};
} } } // namespace JSC::B3::Air
