Source/JavaScriptCore/ChangeLog

 12019-10-07 Robin Morisset <rmorisset@apple.com>
 2
 3 Optimize Air::TmpWidth analysis in IRC
 4 https://bugs.webkit.org/show_bug.cgi?id=152478
 5
 6 Reviewed by NOBODY (OOPS!).
 7
 8 AirTmpWidth currently uses a HashMap to map tmps to their width.
 9 Since tmps have consecutive indices, we can instead use vectors (one for GP and one for FP tmps).
 10 As a bonus, we can just compute the width of the tmps of the bank the register allocator is currently looking at.
 11 This cuts the time spent in the register allocator in JetStream2 by about 100ms out of 3.4s
 12 (or sometimes 80ms out of 2.4, the bimodality of the time spent is due to a huge function in tagcloud-SP which usually but not always reach the FTL, I'll check later if it can be fixed by tweaking the inliner).
 13
 14 * b3/air/AirAllocateRegistersByGraphColoring.cpp:
 15 (JSC::B3::Air::allocateRegistersByGraphColoring):
 16 * b3/air/AirTmpWidth.cpp:
 17 (JSC::B3::Air::TmpWidth::TmpWidth):
 18 (JSC::B3::Air::TmpWidth::recompute):
 19 * b3/air/AirTmpWidth.h:
 20 (JSC::B3::Air::TmpWidth::width const):
 21 (JSC::B3::Air::TmpWidth::requiredWidth):
 22 (JSC::B3::Air::TmpWidth::defWidth const):
 23 (JSC::B3::Air::TmpWidth::useWidth const):
 24 (JSC::B3::Air::TmpWidth::Widths::Widths):
 25 (JSC::B3::Air::TmpWidth::getWidths):
 26 (JSC::B3::Air::TmpWidth::getWidths const):
 27 (JSC::B3::Air::TmpWidth::addWidths):
 28 (JSC::B3::Air::TmpWidth::getWidthsVector):
 29
1302019-10-07 Matt Lewis <jlewis3@apple.com>
231
332 Unreviewed, rolling out r250750.

Source/JavaScriptCore/b3/air/AirAllocateRegistersByGraphColoring.cpp

@@private:
18401840 // possible that most of the TmpWidth overhead is from queries of TmpWidth rather than the
18411841 // recomputation, in which case speeding up the lookup would be a bigger win.
18421842 // https://bugs.webkit.org/show_bug.cgi?id=152478
1843  m_tmpWidth.recompute(m_code);
 1843 m_tmpWidth.recompute<bank>(m_code);
18441844
18451845 auto doAllocation = [&] (auto& allocator) -> bool {
18461846 allocator.allocate();

@@void allocateRegistersByGraphColoring(Code& code)
22052205{
22062206 PhaseScope phaseScope(code, "allocateRegistersByGraphColoring");
22072207
2208  if (false)
 2208 if (debug)
22092209 dataLog("Code before graph coloring:\n", code);
22102210
22112211 UseCounts<Tmp> useCounts(code);

Source/JavaScriptCore/b3/air/AirTmpWidth.cpp

@@TmpWidth::TmpWidth()
4040
4141TmpWidth::TmpWidth(Code& code)
4242{
43  recompute(code);
 43 recompute<GP>(code);
 44 recompute<FP>(code);
4445}
4546
4647TmpWidth::~TmpWidth()
4748{
4849}
4950
 51template <Bank bank>
5052void TmpWidth::recompute(Code& code)
5153{
5254 // Set this to true to cause this analysis to always return pessimistic results.

@@void TmpWidth::recompute(Code& code)
5557 const bool verbose = false;
5658
5759 if (verbose) {
58  dataLog("Code before TmpWidth:\n");
 60 dataLogLn("Code before TmpWidth:");
5961 dataLog(code);
6062 }
61 
62  m_width.clear();
 63
 64 auto& widthsVector = getWidthsVector(bank);
 65 widthsVector.clear();
 66 widthsVector.resize(AbsoluteTmpMapper<bank>::absoluteIndex(code.numTmps(bank)));
 67 for (unsigned i = 0; i < widthsVector.size(); ++i)
 68 widthsVector[i] = Widths(bank);
6369
6470 auto assumeTheWorst = [&] (Tmp tmp) {
65  Widths& widths = m_width.add(tmp, Widths()).iterator->value;
66  Bank bank = Arg(tmp).bank();
67  widths.use = conservativeWidth(bank);
68  widths.def = conservativeWidth(bank);
 71 if (bank == Arg(tmp).bank()) {
 72 Width conservative = conservativeWidth(bank);
 73 addWidths(tmp, { conservative, conservative });
 74 }
6975 };
7076
7177 // Assume the worst for registers.

@@void TmpWidth::recompute(Code& code)
8995 for (BasicBlock* block : code) {
9096 for (Inst& inst : *block) {
9197 if (inst.kind.opcode == Move && inst.args[1].isTmp()) {
 98 if (Arg(inst.args[1]).bank() != bank)
 99 continue;
 100
92101 if (inst.args[0].isTmp()) {
93  // Make sure that both sides of the Move have a width already initialized. The
94  // fixpoint below assumes that it never has to add things to the HashMap.
95  m_width.add(inst.args[0].tmp(), Widths(GP));
96  m_width.add(inst.args[1].tmp(), Widths(GP));
97 
98102 moves.append(&inst);
99103 continue;
100104 }
101  if (inst.args[0].isImm()
102  && inst.args[0].value() >= 0) {
 105 if (inst.args[0].isImm() && inst.args[0].value() >= 0) {
103106 Tmp tmp = inst.args[1].tmp();
104  Widths& widths = m_width.add(tmp, Widths(GP)).iterator->value;
105 
 107 Widths& widths = getWidths(tmp);
106108 if (inst.args[0].value() <= std::numeric_limits<int8_t>::max())
107109 widths.def = std::max(widths.def, Width8);
108110 else if (inst.args[0].value() <= std::numeric_limits<int16_t>::max())

@@void TmpWidth::recompute(Code& code)
116118 }
117119 }
118120 inst.forEachTmp(
119  [&] (Tmp& tmp, Arg::Role role, Bank bank, Width width) {
120  Widths& widths = m_width.add(tmp, Widths(bank)).iterator->value;
121 
 121 [&] (Tmp& tmp, Arg::Role role, Bank tmpBank, Width width) {
 122 if (Arg(tmp).bank() != bank)
 123 return;
 124
 125 Widths& widths = getWidths(tmp);
122126 if (Arg::isAnyUse(role))
123127 widths.use = std::max(widths.use, width);
124128
125129 if (Arg::isZDef(role))
126130 widths.def = std::max(widths.def, width);
127131 else if (Arg::isAnyDef(role))
128  widths.def = conservativeWidth(bank);
 132 widths.def = conservativeWidth(tmpBank);
129133 });
130134 }
131135 }

@@void TmpWidth::recompute(Code& code)
139143 ASSERT(move->args[0].isTmp());
140144 ASSERT(move->args[1].isTmp());
141145
142  // We already ensure that both tmps are added to the width map. That's important
143  // because you cannot add both tmps here while simultaneously getting a reference to
144  // their values, since the second add would invalidate the reference returned by the
145  // first one.
146  Widths& srcWidths = m_width.find(move->args[0].tmp())->value;
147  Widths& dstWidths = m_width.find(move->args[1].tmp())->value;
 146 Widths& srcWidths = getWidths(move->args[0].tmp());
 147 Widths& dstWidths = getWidths(move->args[1].tmp());
148148
149149 // Legend:
150150 //

@@void TmpWidth::recompute(Code& code)
168168 }
169169 }
170170
171  if (verbose)
172  dataLog("width: ", mapDump(m_width), "\n");
 171 if (verbose) {
 172 dataLogLn("bank: ", bank, ", widthsVector: ");
 173 for (unsigned i = 0; i < widthsVector.size(); ++i)
 174 dataLogLn("\t", i, " : ", widthsVector[i]);
 175 }
173176}
174177
175178void TmpWidth::Widths::dump(PrintStream& out) const

Source/JavaScriptCore/b3/air/AirTmpWidth.h

@@public:
3939 TmpWidth(Code&);
4040 ~TmpWidth();
4141
 42 template <Bank bank>
4243 void recompute(Code&);
4344
4445 // The width of a Tmp is the number of bits that you need to be able to track without some trivial

@@public:
5253 // methods.
5354 Width width(Tmp tmp) const
5455 {
55  auto iter = m_width.find(tmp);
56  if (iter == m_width.end())
57  return minimumWidth(Arg(tmp).bank());
58  return std::min(iter->value.use, iter->value.def);
 56 Widths widths = getWidths(tmp);
 57 return std::min(widths.use, widths.def);
5958 }
6059
6160 // Return the minimum required width for all defs/uses of this Tmp.
6261 Width requiredWidth(Tmp tmp)
6362 {
64  auto iter = m_width.find(tmp);
65  if (iter == m_width.end())
66  return minimumWidth(Arg(tmp).bank());
67  return std::max(iter->value.use, iter->value.def);
 63 Widths widths = getWidths(tmp);
 64 return std::max(widths.use, widths.def);
6865 }
6966
7067 // This indirectly tells you how much of the tmp's high bits are guaranteed to be zero. The number of

@@public:
7572 // Where TotalBits are the total number of bits in the register, so 64 on a 64-bit system.
7673 Width defWidth(Tmp tmp) const
7774 {
78  auto iter = m_width.find(tmp);
79  if (iter == m_width.end())
80  return minimumWidth(Arg(tmp).bank());
81  return iter->value.def;
 75 return getWidths(tmp).def;
8276 }
8377
8478 // This tells you how much of Tmp is going to be read.
8579 Width useWidth(Tmp tmp) const
8680 {
87  auto iter = m_width.find(tmp);
88  if (iter == m_width.end())
89  return minimumWidth(Arg(tmp).bank());
90  return iter->value.use;
 81 return getWidths(tmp).use;
9182 }
9283
9384private:

@@private:
10091 def = minimumWidth(bank);
10192 }
10293
 94 Widths(Width useArg, Width defArg)
 95 {
 96 use = useArg;
 97 def = defArg;
 98 }
 99
103100 void dump(PrintStream& out) const;
104101
105102 Width use;
106103 Width def;
107104 };
108 
109  HashMap<Tmp, Widths> m_width;
 105
 106 Widths& getWidths(Tmp tmp)
 107 {
 108 if (tmp.isGP()) {
 109 unsigned index = AbsoluteTmpMapper<GP>::absoluteIndex(tmp);
 110 ASSERT(index < m_widthGP.size());
 111 return m_widthGP[index];
 112 }
 113 unsigned index = AbsoluteTmpMapper<FP>::absoluteIndex(tmp);
 114 ASSERT(index < m_widthFP.size());
 115 return m_widthFP[index];
 116 }
 117 const Widths& getWidths(Tmp tmp) const
 118 {
 119 if (tmp.isGP()) {
 120 unsigned index = AbsoluteTmpMapper<GP>::absoluteIndex(tmp);
 121 ASSERT(index < m_widthGP.size());
 122 return m_widthGP[index];
 123 }
 124 unsigned index = AbsoluteTmpMapper<FP>::absoluteIndex(tmp);
 125 ASSERT(index < m_widthFP.size());
 126 return m_widthFP[index];
 127 }
 128
 129 void addWidths(Tmp tmp, Widths widths)
 130 {
 131 if (tmp.isGP()) {
 132 unsigned index = AbsoluteTmpMapper<GP>::absoluteIndex(tmp);
 133 ASSERT(index < m_widthGP.size());
 134 m_widthGP[index] = widths;
 135 } else {
 136 unsigned index = AbsoluteTmpMapper<FP>::absoluteIndex(tmp);
 137 ASSERT(index < m_widthFP.size());
 138 m_widthFP[index] = widths;
 139 }
 140 }
 141
 142 Vector<Widths>& getWidthsVector(Bank bank)
 143 {
 144 if (bank == GP)
 145 return m_widthGP;
 146 return m_widthFP;
 147 }
 148
 149 Vector<Widths> m_widthGP;
 150 Vector<Widths> m_widthFP;
110151};
111152
112153} } } // namespace JSC::B3::Air