1 //===- BitTracker.cpp -----------------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 // SSA-based bit propagation.
10 //
11 // The purpose of this code is, for a given virtual register, to provide
12 // information about the value of each bit in the register. The values
13 // of bits are represented by the class BitValue, and take one of four
14 // cases: 0, 1, "ref" and "bottom". The 0 and 1 are rather clear, the
15 // "ref" value means that the bit is a copy of another bit (which itself
16 // cannot be a copy of yet another bit---such chains are not allowed).
17 // A "ref" value is associated with a BitRef structure, which indicates
18 // which virtual register, and which bit in that register is the origin
19 // of the value. For example, given an instruction
20 // %2 = ASL %1, 1
21 // assuming that nothing is known about bits of %1, bit 1 of %2
22 // will be a "ref" to (%1, 0). If there is a subsequent instruction
23 // %3 = ASL %2, 2
24 // then bit 3 of %3 will be a "ref" to (%1, 0) as well.
25 // The "bottom" case means that the bit's value cannot be determined,
26 // and that this virtual register actually defines it. The "bottom" case
27 // is discussed in detail in BitTracker.h. In fact, "bottom" is a "ref
28 // to self", so for the %1 above, the bit 0 of it will be a "ref" to
29 // (%1, 0), bit 1 will be a "ref" to (%1, 1), etc.
30 //
31 // The tracker implements the Wegman-Zadeck algorithm, originally developed
32 // for SSA-based constant propagation. Each register is represented as
33 // a sequence of bits, with the convention that bit 0 is the least signi-
34 // ficant bit. Each bit is propagated individually. The class RegisterCell
35 // implements the register's representation, and is also the subject of
36 // the lattice operations in the tracker.
37 //
38 // The intended usage of the bit tracker is to create a target-specific
39 // machine instruction evaluator, pass the evaluator to the BitTracker
40 // object, and run the tracker. The tracker will then collect the bit
41 // value information for a given machine function. After that, it can be
42 // queried for the cells for each virtual register.
43 // Sample code:
44 // const TargetSpecificEvaluator TSE(TRI, MRI);
45 // BitTracker BT(TSE, MF);
46 // BT.run();
47 // ...
48 // unsigned Reg = interestingRegister();
49 // RegisterCell RC = BT.get(Reg);
50 // if (RC[3].is(1))
51 // Reg0bit3 = 1;
52 //
53 // The code below is intended to be fully target-independent.
54
55 #include "BitTracker.h"
56 #include "llvm/ADT/APInt.h"
57 #include "llvm/ADT/BitVector.h"
58 #include "llvm/CodeGen/MachineBasicBlock.h"
59 #include "llvm/CodeGen/MachineFunction.h"
60 #include "llvm/CodeGen/MachineInstr.h"
61 #include "llvm/CodeGen/MachineOperand.h"
62 #include "llvm/CodeGen/MachineRegisterInfo.h"
63 #include "llvm/CodeGen/TargetRegisterInfo.h"
64 #include "llvm/IR/Constants.h"
65 #include "llvm/Support/Debug.h"
66 #include "llvm/Support/raw_ostream.h"
67 #include <cassert>
68 #include <cstdint>
69 #include <iterator>
70
71 using namespace llvm;
72
73 using BT = BitTracker;
74
75 namespace {
76
77 // Local trickery to pretty print a register (without the whole "%number"
78 // business).
79 struct printv {
printv__anon9cb3ed6a0111::printv80 printv(unsigned r) : R(r) {}
81
82 unsigned R;
83 };
84
operator <<(raw_ostream & OS,const printv & PV)85 raw_ostream &operator<< (raw_ostream &OS, const printv &PV) {
86 if (PV.R)
87 OS << 'v' << Register::virtReg2Index(PV.R);
88 else
89 OS << 's';
90 return OS;
91 }
92
93 } // end anonymous namespace
94
95 namespace llvm {
96
operator <<(raw_ostream & OS,const BT::BitValue & BV)97 raw_ostream &operator<<(raw_ostream &OS, const BT::BitValue &BV) {
98 switch (BV.Type) {
99 case BT::BitValue::Top:
100 OS << 'T';
101 break;
102 case BT::BitValue::Zero:
103 OS << '0';
104 break;
105 case BT::BitValue::One:
106 OS << '1';
107 break;
108 case BT::BitValue::Ref:
109 OS << printv(BV.RefI.Reg) << '[' << BV.RefI.Pos << ']';
110 break;
111 }
112 return OS;
113 }
114
operator <<(raw_ostream & OS,const BT::RegisterCell & RC)115 raw_ostream &operator<<(raw_ostream &OS, const BT::RegisterCell &RC) {
116 unsigned n = RC.Bits.size();
117 OS << "{ w:" << n;
118 // Instead of printing each bit value individually, try to group them
119 // into logical segments, such as sequences of 0 or 1 bits or references
120 // to consecutive bits (e.g. "bits 3-5 are same as bits 7-9 of reg xyz").
121 // "Start" will be the index of the beginning of the most recent segment.
122 unsigned Start = 0;
123 bool SeqRef = false; // A sequence of refs to consecutive bits.
124 bool ConstRef = false; // A sequence of refs to the same bit.
125
126 for (unsigned i = 1, n = RC.Bits.size(); i < n; ++i) {
127 const BT::BitValue &V = RC[i];
128 const BT::BitValue &SV = RC[Start];
129 bool IsRef = (V.Type == BT::BitValue::Ref);
130 // If the current value is the same as Start, skip to the next one.
131 if (!IsRef && V == SV)
132 continue;
133 if (IsRef && SV.Type == BT::BitValue::Ref && V.RefI.Reg == SV.RefI.Reg) {
134 if (Start+1 == i) {
135 SeqRef = (V.RefI.Pos == SV.RefI.Pos+1);
136 ConstRef = (V.RefI.Pos == SV.RefI.Pos);
137 }
138 if (SeqRef && V.RefI.Pos == SV.RefI.Pos+(i-Start))
139 continue;
140 if (ConstRef && V.RefI.Pos == SV.RefI.Pos)
141 continue;
142 }
143
144 // The current value is different. Print the previous one and reset
145 // the Start.
146 OS << " [" << Start;
147 unsigned Count = i - Start;
148 if (Count == 1) {
149 OS << "]:" << SV;
150 } else {
151 OS << '-' << i-1 << "]:";
152 if (SV.Type == BT::BitValue::Ref && SeqRef)
153 OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
154 << SV.RefI.Pos+(Count-1) << ']';
155 else
156 OS << SV;
157 }
158 Start = i;
159 SeqRef = ConstRef = false;
160 }
161
162 OS << " [" << Start;
163 unsigned Count = n - Start;
164 if (n-Start == 1) {
165 OS << "]:" << RC[Start];
166 } else {
167 OS << '-' << n-1 << "]:";
168 const BT::BitValue &SV = RC[Start];
169 if (SV.Type == BT::BitValue::Ref && SeqRef)
170 OS << printv(SV.RefI.Reg) << '[' << SV.RefI.Pos << '-'
171 << SV.RefI.Pos+(Count-1) << ']';
172 else
173 OS << SV;
174 }
175 OS << " }";
176
177 return OS;
178 }
179
180 } // end namespace llvm
181
print_cells(raw_ostream & OS) const182 void BitTracker::print_cells(raw_ostream &OS) const {
183 for (const std::pair<unsigned, RegisterCell> P : Map)
184 dbgs() << printReg(P.first, &ME.TRI) << " -> " << P.second << "\n";
185 }
186
BitTracker(const MachineEvaluator & E,MachineFunction & F)187 BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F)
188 : ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType), Trace(false) {
189 }
190
~BitTracker()191 BitTracker::~BitTracker() {
192 delete ⤅
193 }
194
195 // If we were allowed to update a cell for a part of a register, the meet
196 // operation would need to be parametrized by the register number and the
197 // exact part of the register, so that the computer BitRefs correspond to
198 // the actual bits of the "self" register.
199 // While this cannot happen in the current implementation, I'm not sure
200 // if this should be ruled out in the future.
meet(const RegisterCell & RC,Register SelfR)201 bool BT::RegisterCell::meet(const RegisterCell &RC, Register SelfR) {
202 // An example when "meet" can be invoked with SelfR == 0 is a phi node
203 // with a physical register as an operand.
204 assert(SelfR == 0 || SelfR.isVirtual());
205 bool Changed = false;
206 for (uint16_t i = 0, n = Bits.size(); i < n; ++i) {
207 const BitValue &RCV = RC[i];
208 Changed |= Bits[i].meet(RCV, BitRef(SelfR, i));
209 }
210 return Changed;
211 }
212
213 // Insert the entire cell RC into the current cell at position given by M.
insert(const BT::RegisterCell & RC,const BitMask & M)214 BT::RegisterCell &BT::RegisterCell::insert(const BT::RegisterCell &RC,
215 const BitMask &M) {
216 uint16_t B = M.first(), E = M.last(), W = width();
217 // M must be a valid mask for *this.
218 assert(B < W && E < W);
219 // The masked part of *this must have the same number of bits
220 // as the source.
221 assert(B > E || E-B+1 == RC.width()); // B <= E => E-B+1 = |RC|.
222 assert(B <= E || E+(W-B)+1 == RC.width()); // E < B => E+(W-B)+1 = |RC|.
223 if (B <= E) {
224 for (uint16_t i = 0; i <= E-B; ++i)
225 Bits[i+B] = RC[i];
226 } else {
227 for (uint16_t i = 0; i < W-B; ++i)
228 Bits[i+B] = RC[i];
229 for (uint16_t i = 0; i <= E; ++i)
230 Bits[i] = RC[i+(W-B)];
231 }
232 return *this;
233 }
234
extract(const BitMask & M) const235 BT::RegisterCell BT::RegisterCell::extract(const BitMask &M) const {
236 uint16_t B = M.first(), E = M.last(), W = width();
237 assert(B < W && E < W);
238 if (B <= E) {
239 RegisterCell RC(E-B+1);
240 for (uint16_t i = B; i <= E; ++i)
241 RC.Bits[i-B] = Bits[i];
242 return RC;
243 }
244
245 RegisterCell RC(E+(W-B)+1);
246 for (uint16_t i = 0; i < W-B; ++i)
247 RC.Bits[i] = Bits[i+B];
248 for (uint16_t i = 0; i <= E; ++i)
249 RC.Bits[i+(W-B)] = Bits[i];
250 return RC;
251 }
252
rol(uint16_t Sh)253 BT::RegisterCell &BT::RegisterCell::rol(uint16_t Sh) {
254 // Rotate left (i.e. towards increasing bit indices).
255 // Swap the two parts: [0..W-Sh-1] [W-Sh..W-1]
256 uint16_t W = width();
257 Sh = Sh % W;
258 if (Sh == 0)
259 return *this;
260
261 RegisterCell Tmp(W-Sh);
262 // Tmp = [0..W-Sh-1].
263 for (uint16_t i = 0; i < W-Sh; ++i)
264 Tmp[i] = Bits[i];
265 // Shift [W-Sh..W-1] to [0..Sh-1].
266 for (uint16_t i = 0; i < Sh; ++i)
267 Bits[i] = Bits[W-Sh+i];
268 // Copy Tmp to [Sh..W-1].
269 for (uint16_t i = 0; i < W-Sh; ++i)
270 Bits[i+Sh] = Tmp.Bits[i];
271 return *this;
272 }
273
fill(uint16_t B,uint16_t E,const BitValue & V)274 BT::RegisterCell &BT::RegisterCell::fill(uint16_t B, uint16_t E,
275 const BitValue &V) {
276 assert(B <= E);
277 while (B < E)
278 Bits[B++] = V;
279 return *this;
280 }
281
cat(const RegisterCell & RC)282 BT::RegisterCell &BT::RegisterCell::cat(const RegisterCell &RC) {
283 // Append the cell given as the argument to the "this" cell.
284 // Bit 0 of RC becomes bit W of the result, where W is this->width().
285 uint16_t W = width(), WRC = RC.width();
286 Bits.resize(W+WRC);
287 for (uint16_t i = 0; i < WRC; ++i)
288 Bits[i+W] = RC.Bits[i];
289 return *this;
290 }
291
ct(bool B) const292 uint16_t BT::RegisterCell::ct(bool B) const {
293 uint16_t W = width();
294 uint16_t C = 0;
295 BitValue V = B;
296 while (C < W && Bits[C] == V)
297 C++;
298 return C;
299 }
300
cl(bool B) const301 uint16_t BT::RegisterCell::cl(bool B) const {
302 uint16_t W = width();
303 uint16_t C = 0;
304 BitValue V = B;
305 while (C < W && Bits[W-(C+1)] == V)
306 C++;
307 return C;
308 }
309
operator ==(const RegisterCell & RC) const310 bool BT::RegisterCell::operator== (const RegisterCell &RC) const {
311 uint16_t W = Bits.size();
312 if (RC.Bits.size() != W)
313 return false;
314 for (uint16_t i = 0; i < W; ++i)
315 if (Bits[i] != RC[i])
316 return false;
317 return true;
318 }
319
regify(unsigned R)320 BT::RegisterCell &BT::RegisterCell::regify(unsigned R) {
321 for (unsigned i = 0, n = width(); i < n; ++i) {
322 const BitValue &V = Bits[i];
323 if (V.Type == BitValue::Ref && V.RefI.Reg == 0)
324 Bits[i].RefI = BitRef(R, i);
325 }
326 return *this;
327 }
328
getRegBitWidth(const RegisterRef & RR) const329 uint16_t BT::MachineEvaluator::getRegBitWidth(const RegisterRef &RR) const {
330 // The general problem is with finding a register class that corresponds
331 // to a given reference reg:sub. There can be several such classes, and
332 // since we only care about the register size, it does not matter which
333 // such class we would find.
334 // The easiest way to accomplish what we want is to
335 // 1. find a physical register PhysR from the same class as RR.Reg,
336 // 2. find a physical register PhysS that corresponds to PhysR:RR.Sub,
337 // 3. find a register class that contains PhysS.
338 if (RR.Reg.isVirtual()) {
339 const auto &VC = composeWithSubRegIndex(*MRI.getRegClass(RR.Reg), RR.Sub);
340 return TRI.getRegSizeInBits(VC);
341 }
342 assert(RR.Reg.isPhysical());
343 MCRegister PhysR =
344 (RR.Sub == 0) ? RR.Reg.asMCReg() : TRI.getSubReg(RR.Reg, RR.Sub);
345 return getPhysRegBitWidth(PhysR);
346 }
347
getCell(const RegisterRef & RR,const CellMapType & M) const348 BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR,
349 const CellMapType &M) const {
350 uint16_t BW = getRegBitWidth(RR);
351
352 // Physical registers are assumed to be present in the map with an unknown
353 // value. Don't actually insert anything in the map, just return the cell.
354 if (RR.Reg.isPhysical())
355 return RegisterCell::self(0, BW);
356
357 assert(RR.Reg.isVirtual());
358 // For virtual registers that belong to a class that is not tracked,
359 // generate an "unknown" value as well.
360 const TargetRegisterClass *C = MRI.getRegClass(RR.Reg);
361 if (!track(C))
362 return RegisterCell::self(0, BW);
363
364 CellMapType::const_iterator F = M.find(RR.Reg);
365 if (F != M.end()) {
366 if (!RR.Sub)
367 return F->second;
368 BitMask M = mask(RR.Reg, RR.Sub);
369 return F->second.extract(M);
370 }
371 // If not found, create a "top" entry, but do not insert it in the map.
372 return RegisterCell::top(BW);
373 }
374
putCell(const RegisterRef & RR,RegisterCell RC,CellMapType & M) const375 void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC,
376 CellMapType &M) const {
377 // While updating the cell map can be done in a meaningful way for
378 // a part of a register, it makes little sense to implement it as the
379 // SSA representation would never contain such "partial definitions".
380 if (!RR.Reg.isVirtual())
381 return;
382 assert(RR.Sub == 0 && "Unexpected sub-register in definition");
383 // Eliminate all ref-to-reg-0 bit values: replace them with "self".
384 M[RR.Reg] = RC.regify(RR.Reg);
385 }
386
387 // Check if the cell represents a compile-time integer value.
isInt(const RegisterCell & A) const388 bool BT::MachineEvaluator::isInt(const RegisterCell &A) const {
389 uint16_t W = A.width();
390 for (uint16_t i = 0; i < W; ++i)
391 if (!A[i].is(0) && !A[i].is(1))
392 return false;
393 return true;
394 }
395
396 // Convert a cell to the integer value. The result must fit in uint64_t.
toInt(const RegisterCell & A) const397 uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const {
398 assert(isInt(A));
399 uint64_t Val = 0;
400 uint16_t W = A.width();
401 for (uint16_t i = 0; i < W; ++i) {
402 Val <<= 1;
403 Val |= A[i].is(1);
404 }
405 return Val;
406 }
407
408 // Evaluator helper functions. These implement some common operation on
409 // register cells that can be used to implement target-specific instructions
410 // in a target-specific evaluator.
411
eIMM(int64_t V,uint16_t W) const412 BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const {
413 RegisterCell Res(W);
414 // For bits beyond the 63rd, this will generate the sign bit of V.
415 for (uint16_t i = 0; i < W; ++i) {
416 Res[i] = BitValue(V & 1);
417 V >>= 1;
418 }
419 return Res;
420 }
421
eIMM(const ConstantInt * CI) const422 BT::RegisterCell BT::MachineEvaluator::eIMM(const ConstantInt *CI) const {
423 const APInt &A = CI->getValue();
424 uint16_t BW = A.getBitWidth();
425 assert((unsigned)BW == A.getBitWidth() && "BitWidth overflow");
426 RegisterCell Res(BW);
427 for (uint16_t i = 0; i < BW; ++i)
428 Res[i] = A[i];
429 return Res;
430 }
431
eADD(const RegisterCell & A1,const RegisterCell & A2) const432 BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1,
433 const RegisterCell &A2) const {
434 uint16_t W = A1.width();
435 assert(W == A2.width());
436 RegisterCell Res(W);
437 bool Carry = false;
438 uint16_t I;
439 for (I = 0; I < W; ++I) {
440 const BitValue &V1 = A1[I];
441 const BitValue &V2 = A2[I];
442 if (!V1.num() || !V2.num())
443 break;
444 unsigned S = bool(V1) + bool(V2) + Carry;
445 Res[I] = BitValue(S & 1);
446 Carry = (S > 1);
447 }
448 for (; I < W; ++I) {
449 const BitValue &V1 = A1[I];
450 const BitValue &V2 = A2[I];
451 // If the next bit is same as Carry, the result will be 0 plus the
452 // other bit. The Carry bit will remain unchanged.
453 if (V1.is(Carry))
454 Res[I] = BitValue::ref(V2);
455 else if (V2.is(Carry))
456 Res[I] = BitValue::ref(V1);
457 else
458 break;
459 }
460 for (; I < W; ++I)
461 Res[I] = BitValue::self();
462 return Res;
463 }
464
eSUB(const RegisterCell & A1,const RegisterCell & A2) const465 BT::RegisterCell BT::MachineEvaluator::eSUB(const RegisterCell &A1,
466 const RegisterCell &A2) const {
467 uint16_t W = A1.width();
468 assert(W == A2.width());
469 RegisterCell Res(W);
470 bool Borrow = false;
471 uint16_t I;
472 for (I = 0; I < W; ++I) {
473 const BitValue &V1 = A1[I];
474 const BitValue &V2 = A2[I];
475 if (!V1.num() || !V2.num())
476 break;
477 unsigned S = bool(V1) - bool(V2) - Borrow;
478 Res[I] = BitValue(S & 1);
479 Borrow = (S > 1);
480 }
481 for (; I < W; ++I) {
482 const BitValue &V1 = A1[I];
483 const BitValue &V2 = A2[I];
484 if (V1.is(Borrow)) {
485 Res[I] = BitValue::ref(V2);
486 break;
487 }
488 if (V2.is(Borrow))
489 Res[I] = BitValue::ref(V1);
490 else
491 break;
492 }
493 for (; I < W; ++I)
494 Res[I] = BitValue::self();
495 return Res;
496 }
497
eMLS(const RegisterCell & A1,const RegisterCell & A2) const498 BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1,
499 const RegisterCell &A2) const {
500 uint16_t W = A1.width() + A2.width();
501 uint16_t Z = A1.ct(false) + A2.ct(false);
502 RegisterCell Res(W);
503 Res.fill(0, Z, BitValue::Zero);
504 Res.fill(Z, W, BitValue::self());
505 return Res;
506 }
507
eMLU(const RegisterCell & A1,const RegisterCell & A2) const508 BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1,
509 const RegisterCell &A2) const {
510 uint16_t W = A1.width() + A2.width();
511 uint16_t Z = A1.ct(false) + A2.ct(false);
512 RegisterCell Res(W);
513 Res.fill(0, Z, BitValue::Zero);
514 Res.fill(Z, W, BitValue::self());
515 return Res;
516 }
517
eASL(const RegisterCell & A1,uint16_t Sh) const518 BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1,
519 uint16_t Sh) const {
520 assert(Sh <= A1.width());
521 RegisterCell Res = RegisterCell::ref(A1);
522 Res.rol(Sh);
523 Res.fill(0, Sh, BitValue::Zero);
524 return Res;
525 }
526
eLSR(const RegisterCell & A1,uint16_t Sh) const527 BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1,
528 uint16_t Sh) const {
529 uint16_t W = A1.width();
530 assert(Sh <= W);
531 RegisterCell Res = RegisterCell::ref(A1);
532 Res.rol(W-Sh);
533 Res.fill(W-Sh, W, BitValue::Zero);
534 return Res;
535 }
536
eASR(const RegisterCell & A1,uint16_t Sh) const537 BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1,
538 uint16_t Sh) const {
539 uint16_t W = A1.width();
540 assert(Sh <= W);
541 RegisterCell Res = RegisterCell::ref(A1);
542 BitValue Sign = Res[W-1];
543 Res.rol(W-Sh);
544 Res.fill(W-Sh, W, Sign);
545 return Res;
546 }
547
eAND(const RegisterCell & A1,const RegisterCell & A2) const548 BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1,
549 const RegisterCell &A2) const {
550 uint16_t W = A1.width();
551 assert(W == A2.width());
552 RegisterCell Res(W);
553 for (uint16_t i = 0; i < W; ++i) {
554 const BitValue &V1 = A1[i];
555 const BitValue &V2 = A2[i];
556 if (V1.is(1))
557 Res[i] = BitValue::ref(V2);
558 else if (V2.is(1))
559 Res[i] = BitValue::ref(V1);
560 else if (V1.is(0) || V2.is(0))
561 Res[i] = BitValue::Zero;
562 else if (V1 == V2)
563 Res[i] = V1;
564 else
565 Res[i] = BitValue::self();
566 }
567 return Res;
568 }
569
eORL(const RegisterCell & A1,const RegisterCell & A2) const570 BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1,
571 const RegisterCell &A2) const {
572 uint16_t W = A1.width();
573 assert(W == A2.width());
574 RegisterCell Res(W);
575 for (uint16_t i = 0; i < W; ++i) {
576 const BitValue &V1 = A1[i];
577 const BitValue &V2 = A2[i];
578 if (V1.is(1) || V2.is(1))
579 Res[i] = BitValue::One;
580 else if (V1.is(0))
581 Res[i] = BitValue::ref(V2);
582 else if (V2.is(0))
583 Res[i] = BitValue::ref(V1);
584 else if (V1 == V2)
585 Res[i] = V1;
586 else
587 Res[i] = BitValue::self();
588 }
589 return Res;
590 }
591
eXOR(const RegisterCell & A1,const RegisterCell & A2) const592 BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1,
593 const RegisterCell &A2) const {
594 uint16_t W = A1.width();
595 assert(W == A2.width());
596 RegisterCell Res(W);
597 for (uint16_t i = 0; i < W; ++i) {
598 const BitValue &V1 = A1[i];
599 const BitValue &V2 = A2[i];
600 if (V1.is(0))
601 Res[i] = BitValue::ref(V2);
602 else if (V2.is(0))
603 Res[i] = BitValue::ref(V1);
604 else if (V1 == V2)
605 Res[i] = BitValue::Zero;
606 else
607 Res[i] = BitValue::self();
608 }
609 return Res;
610 }
611
eNOT(const RegisterCell & A1) const612 BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const {
613 uint16_t W = A1.width();
614 RegisterCell Res(W);
615 for (uint16_t i = 0; i < W; ++i) {
616 const BitValue &V = A1[i];
617 if (V.is(0))
618 Res[i] = BitValue::One;
619 else if (V.is(1))
620 Res[i] = BitValue::Zero;
621 else
622 Res[i] = BitValue::self();
623 }
624 return Res;
625 }
626
eSET(const RegisterCell & A1,uint16_t BitN) const627 BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1,
628 uint16_t BitN) const {
629 assert(BitN < A1.width());
630 RegisterCell Res = RegisterCell::ref(A1);
631 Res[BitN] = BitValue::One;
632 return Res;
633 }
634
eCLR(const RegisterCell & A1,uint16_t BitN) const635 BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1,
636 uint16_t BitN) const {
637 assert(BitN < A1.width());
638 RegisterCell Res = RegisterCell::ref(A1);
639 Res[BitN] = BitValue::Zero;
640 return Res;
641 }
642
eCLB(const RegisterCell & A1,bool B,uint16_t W) const643 BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B,
644 uint16_t W) const {
645 uint16_t C = A1.cl(B), AW = A1.width();
646 // If the last leading non-B bit is not a constant, then we don't know
647 // the real count.
648 if ((C < AW && A1[AW-1-C].num()) || C == AW)
649 return eIMM(C, W);
650 return RegisterCell::self(0, W);
651 }
652
eCTB(const RegisterCell & A1,bool B,uint16_t W) const653 BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B,
654 uint16_t W) const {
655 uint16_t C = A1.ct(B), AW = A1.width();
656 // If the last trailing non-B bit is not a constant, then we don't know
657 // the real count.
658 if ((C < AW && A1[C].num()) || C == AW)
659 return eIMM(C, W);
660 return RegisterCell::self(0, W);
661 }
662
eSXT(const RegisterCell & A1,uint16_t FromN) const663 BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1,
664 uint16_t FromN) const {
665 uint16_t W = A1.width();
666 assert(FromN <= W);
667 RegisterCell Res = RegisterCell::ref(A1);
668 BitValue Sign = Res[FromN-1];
669 // Sign-extend "inreg".
670 Res.fill(FromN, W, Sign);
671 return Res;
672 }
673
eZXT(const RegisterCell & A1,uint16_t FromN) const674 BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1,
675 uint16_t FromN) const {
676 uint16_t W = A1.width();
677 assert(FromN <= W);
678 RegisterCell Res = RegisterCell::ref(A1);
679 Res.fill(FromN, W, BitValue::Zero);
680 return Res;
681 }
682
eXTR(const RegisterCell & A1,uint16_t B,uint16_t E) const683 BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1,
684 uint16_t B, uint16_t E) const {
685 uint16_t W = A1.width();
686 assert(B < W && E <= W);
687 if (B == E)
688 return RegisterCell(0);
689 uint16_t Last = (E > 0) ? E-1 : W-1;
690 RegisterCell Res = RegisterCell::ref(A1).extract(BT::BitMask(B, Last));
691 // Return shorter cell.
692 return Res;
693 }
694
eINS(const RegisterCell & A1,const RegisterCell & A2,uint16_t AtN) const695 BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1,
696 const RegisterCell &A2, uint16_t AtN) const {
697 uint16_t W1 = A1.width(), W2 = A2.width();
698 (void)W1;
699 assert(AtN < W1 && AtN+W2 <= W1);
700 // Copy bits from A1, insert A2 at position AtN.
701 RegisterCell Res = RegisterCell::ref(A1);
702 if (W2 > 0)
703 Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1));
704 return Res;
705 }
706
mask(Register Reg,unsigned Sub) const707 BT::BitMask BT::MachineEvaluator::mask(Register Reg, unsigned Sub) const {
708 assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0");
709 uint16_t W = getRegBitWidth(Reg);
710 assert(W > 0 && "Cannot generate mask for empty register");
711 return BitMask(0, W-1);
712 }
713
getPhysRegBitWidth(MCRegister Reg) const714 uint16_t BT::MachineEvaluator::getPhysRegBitWidth(MCRegister Reg) const {
715 const TargetRegisterClass &PC = *TRI.getMinimalPhysRegClass(Reg);
716 return TRI.getRegSizeInBits(PC);
717 }
718
evaluate(const MachineInstr & MI,const CellMapType & Inputs,CellMapType & Outputs) const719 bool BT::MachineEvaluator::evaluate(const MachineInstr &MI,
720 const CellMapType &Inputs,
721 CellMapType &Outputs) const {
722 unsigned Opc = MI.getOpcode();
723 switch (Opc) {
724 case TargetOpcode::REG_SEQUENCE: {
725 RegisterRef RD = MI.getOperand(0);
726 assert(RD.Sub == 0);
727 RegisterRef RS = MI.getOperand(1);
728 unsigned SS = MI.getOperand(2).getImm();
729 RegisterRef RT = MI.getOperand(3);
730 unsigned ST = MI.getOperand(4).getImm();
731 assert(SS != ST);
732
733 uint16_t W = getRegBitWidth(RD);
734 RegisterCell Res(W);
735 Res.insert(RegisterCell::ref(getCell(RS, Inputs)), mask(RD.Reg, SS));
736 Res.insert(RegisterCell::ref(getCell(RT, Inputs)), mask(RD.Reg, ST));
737 putCell(RD, Res, Outputs);
738 break;
739 }
740
741 case TargetOpcode::COPY: {
742 // COPY can transfer a smaller register into a wider one.
743 // If that is the case, fill the remaining high bits with 0.
744 RegisterRef RD = MI.getOperand(0);
745 RegisterRef RS = MI.getOperand(1);
746 assert(RD.Sub == 0);
747 uint16_t WD = getRegBitWidth(RD);
748 uint16_t WS = getRegBitWidth(RS);
749 assert(WD >= WS);
750 RegisterCell Src = getCell(RS, Inputs);
751 RegisterCell Res(WD);
752 Res.insert(Src, BitMask(0, WS-1));
753 Res.fill(WS, WD, BitValue::Zero);
754 putCell(RD, Res, Outputs);
755 break;
756 }
757
758 default:
759 return false;
760 }
761
762 return true;
763 }
764
operator ()(const MachineInstr * InstA,const MachineInstr * InstB) const765 bool BT::UseQueueType::Cmp::operator()(const MachineInstr *InstA,
766 const MachineInstr *InstB) const {
767 // This is a comparison function for a priority queue: give higher priority
768 // to earlier instructions.
769 // This operator is used as "less", so returning "true" gives InstB higher
770 // priority (because then InstA < InstB).
771 if (InstA == InstB)
772 return false;
773 const MachineBasicBlock *BA = InstA->getParent();
774 const MachineBasicBlock *BB = InstB->getParent();
775 if (BA != BB) {
776 // If the blocks are different, ideally the dominating block would
777 // have a higher priority, but it may be too expensive to check.
778 return BA->getNumber() > BB->getNumber();
779 }
780
781 auto getDist = [this] (const MachineInstr *MI) {
782 auto F = Dist.find(MI);
783 if (F != Dist.end())
784 return F->second;
785 MachineBasicBlock::const_iterator I = MI->getParent()->begin();
786 MachineBasicBlock::const_iterator E = MI->getIterator();
787 unsigned D = std::distance(I, E);
788 Dist.insert(std::make_pair(MI, D));
789 return D;
790 };
791
792 return getDist(InstA) > getDist(InstB);
793 }
794
795 // Main W-Z implementation.
796
visitPHI(const MachineInstr & PI)797 void BT::visitPHI(const MachineInstr &PI) {
798 int ThisN = PI.getParent()->getNumber();
799 if (Trace)
800 dbgs() << "Visit FI(" << printMBBReference(*PI.getParent()) << "): " << PI;
801
802 const MachineOperand &MD = PI.getOperand(0);
803 assert(MD.getSubReg() == 0 && "Unexpected sub-register in definition");
804 RegisterRef DefRR(MD);
805 uint16_t DefBW = ME.getRegBitWidth(DefRR);
806
807 RegisterCell DefC = ME.getCell(DefRR, Map);
808 if (DefC == RegisterCell::self(DefRR.Reg, DefBW)) // XXX slow
809 return;
810
811 bool Changed = false;
812
813 for (unsigned i = 1, n = PI.getNumOperands(); i < n; i += 2) {
814 const MachineBasicBlock *PB = PI.getOperand(i + 1).getMBB();
815 int PredN = PB->getNumber();
816 if (Trace)
817 dbgs() << " edge " << printMBBReference(*PB) << "->"
818 << printMBBReference(*PI.getParent());
819 if (!EdgeExec.count(CFGEdge(PredN, ThisN))) {
820 if (Trace)
821 dbgs() << " not executable\n";
822 continue;
823 }
824
825 RegisterRef RU = PI.getOperand(i);
826 RegisterCell ResC = ME.getCell(RU, Map);
827 if (Trace)
828 dbgs() << " input reg: " << printReg(RU.Reg, &ME.TRI, RU.Sub)
829 << " cell: " << ResC << "\n";
830 Changed |= DefC.meet(ResC, DefRR.Reg);
831 }
832
833 if (Changed) {
834 if (Trace)
835 dbgs() << "Output: " << printReg(DefRR.Reg, &ME.TRI, DefRR.Sub)
836 << " cell: " << DefC << "\n";
837 ME.putCell(DefRR, DefC, Map);
838 visitUsesOf(DefRR.Reg);
839 }
840 }
841
visitNonBranch(const MachineInstr & MI)842 void BT::visitNonBranch(const MachineInstr &MI) {
843 if (Trace)
844 dbgs() << "Visit MI(" << printMBBReference(*MI.getParent()) << "): " << MI;
845 if (MI.isDebugInstr())
846 return;
847 assert(!MI.isBranch() && "Unexpected branch instruction");
848
849 CellMapType ResMap;
850 bool Eval = ME.evaluate(MI, Map, ResMap);
851
852 if (Trace && Eval) {
853 for (const MachineOperand &MO : MI.operands()) {
854 if (!MO.isReg() || !MO.isUse())
855 continue;
856 RegisterRef RU(MO);
857 dbgs() << " input reg: " << printReg(RU.Reg, &ME.TRI, RU.Sub)
858 << " cell: " << ME.getCell(RU, Map) << "\n";
859 }
860 dbgs() << "Outputs:\n";
861 for (const std::pair<const unsigned, RegisterCell> &P : ResMap) {
862 RegisterRef RD(P.first);
863 dbgs() << " " << printReg(P.first, &ME.TRI) << " cell: "
864 << ME.getCell(RD, ResMap) << "\n";
865 }
866 }
867
868 // Iterate over all definitions of the instruction, and update the
869 // cells accordingly.
870 for (const MachineOperand &MO : MI.operands()) {
871 // Visit register defs only.
872 if (!MO.isReg() || !MO.isDef())
873 continue;
874 RegisterRef RD(MO);
875 assert(RD.Sub == 0 && "Unexpected sub-register in definition");
876 if (!RD.Reg.isVirtual())
877 continue;
878
879 bool Changed = false;
880 if (!Eval || ResMap.count(RD.Reg) == 0) {
881 // Set to "ref" (aka "bottom").
882 uint16_t DefBW = ME.getRegBitWidth(RD);
883 RegisterCell RefC = RegisterCell::self(RD.Reg, DefBW);
884 if (RefC != ME.getCell(RD, Map)) {
885 ME.putCell(RD, RefC, Map);
886 Changed = true;
887 }
888 } else {
889 RegisterCell DefC = ME.getCell(RD, Map);
890 RegisterCell ResC = ME.getCell(RD, ResMap);
891 // This is a non-phi instruction, so the values of the inputs come
892 // from the same registers each time this instruction is evaluated.
893 // During the propagation, the values of the inputs can become lowered
894 // in the sense of the lattice operation, which may cause different
895 // results to be calculated in subsequent evaluations. This should
896 // not cause the bottoming of the result in the map, since the new
897 // result is already reflecting the lowered inputs.
898 for (uint16_t i = 0, w = DefC.width(); i < w; ++i) {
899 BitValue &V = DefC[i];
900 // Bits that are already "bottom" should not be updated.
901 if (V.Type == BitValue::Ref && V.RefI.Reg == RD.Reg)
902 continue;
903 // Same for those that are identical in DefC and ResC.
904 if (V == ResC[i])
905 continue;
906 V = ResC[i];
907 Changed = true;
908 }
909 if (Changed)
910 ME.putCell(RD, DefC, Map);
911 }
912 if (Changed)
913 visitUsesOf(RD.Reg);
914 }
915 }
916
visitBranchesFrom(const MachineInstr & BI)917 void BT::visitBranchesFrom(const MachineInstr &BI) {
918 const MachineBasicBlock &B = *BI.getParent();
919 MachineBasicBlock::const_iterator It = BI, End = B.end();
920 BranchTargetList Targets, BTs;
921 bool FallsThrough = true, DefaultToAll = false;
922 int ThisN = B.getNumber();
923
924 do {
925 BTs.clear();
926 const MachineInstr &MI = *It;
927 if (Trace)
928 dbgs() << "Visit BR(" << printMBBReference(B) << "): " << MI;
929 assert(MI.isBranch() && "Expecting branch instruction");
930 InstrExec.insert(&MI);
931 bool Eval = ME.evaluate(MI, Map, BTs, FallsThrough);
932 if (!Eval) {
933 // If the evaluation failed, we will add all targets. Keep going in
934 // the loop to mark all executable branches as such.
935 DefaultToAll = true;
936 FallsThrough = true;
937 if (Trace)
938 dbgs() << " failed to evaluate: will add all CFG successors\n";
939 } else if (!DefaultToAll) {
940 // If evaluated successfully add the targets to the cumulative list.
941 if (Trace) {
942 dbgs() << " adding targets:";
943 for (const MachineBasicBlock *BT : BTs)
944 dbgs() << " " << printMBBReference(*BT);
945 if (FallsThrough)
946 dbgs() << "\n falls through\n";
947 else
948 dbgs() << "\n does not fall through\n";
949 }
950 Targets.insert(BTs.begin(), BTs.end());
951 }
952 ++It;
953 } while (FallsThrough && It != End);
954
955 if (B.mayHaveInlineAsmBr())
956 DefaultToAll = true;
957
958 if (!DefaultToAll) {
959 // Need to add all CFG successors that lead to EH landing pads.
960 // There won't be explicit branches to these blocks, but they must
961 // be processed.
962 for (const MachineBasicBlock *SB : B.successors()) {
963 if (SB->isEHPad())
964 Targets.insert(SB);
965 }
966 if (FallsThrough) {
967 MachineFunction::const_iterator BIt = B.getIterator();
968 MachineFunction::const_iterator Next = std::next(BIt);
969 if (Next != MF.end())
970 Targets.insert(&*Next);
971 }
972 } else {
973 for (const MachineBasicBlock *SB : B.successors())
974 Targets.insert(SB);
975 }
976
977 for (const MachineBasicBlock *TB : Targets)
978 FlowQ.push(CFGEdge(ThisN, TB->getNumber()));
979 }
980
visitUsesOf(Register Reg)981 void BT::visitUsesOf(Register Reg) {
982 if (Trace)
983 dbgs() << "queuing uses of modified reg " << printReg(Reg, &ME.TRI)
984 << " cell: " << ME.getCell(Reg, Map) << '\n';
985
986 for (MachineInstr &UseI : MRI.use_nodbg_instructions(Reg))
987 UseQ.push(&UseI);
988 }
989
get(RegisterRef RR) const990 BT::RegisterCell BT::get(RegisterRef RR) const {
991 return ME.getCell(RR, Map);
992 }
993
put(RegisterRef RR,const RegisterCell & RC)994 void BT::put(RegisterRef RR, const RegisterCell &RC) {
995 ME.putCell(RR, RC, Map);
996 }
997
998 // Replace all references to bits from OldRR with the corresponding bits
999 // in NewRR.
subst(RegisterRef OldRR,RegisterRef NewRR)1000 void BT::subst(RegisterRef OldRR, RegisterRef NewRR) {
1001 assert(Map.count(OldRR.Reg) > 0 && "OldRR not present in map");
1002 BitMask OM = ME.mask(OldRR.Reg, OldRR.Sub);
1003 BitMask NM = ME.mask(NewRR.Reg, NewRR.Sub);
1004 uint16_t OMB = OM.first(), OME = OM.last();
1005 uint16_t NMB = NM.first(), NME = NM.last();
1006 (void)NME;
1007 assert((OME-OMB == NME-NMB) &&
1008 "Substituting registers of different lengths");
1009 for (std::pair<const unsigned, RegisterCell> &P : Map) {
1010 RegisterCell &RC = P.second;
1011 for (uint16_t i = 0, w = RC.width(); i < w; ++i) {
1012 BitValue &V = RC[i];
1013 if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg)
1014 continue;
1015 if (V.RefI.Pos < OMB || V.RefI.Pos > OME)
1016 continue;
1017 V.RefI.Reg = NewRR.Reg;
1018 V.RefI.Pos += NMB-OMB;
1019 }
1020 }
1021 }
1022
1023 // Check if the block has been "executed" during propagation. (If not, the
1024 // block is dead, but it may still appear to be reachable.)
reached(const MachineBasicBlock * B) const1025 bool BT::reached(const MachineBasicBlock *B) const {
1026 int BN = B->getNumber();
1027 assert(BN >= 0);
1028 return ReachedBB.count(BN);
1029 }
1030
1031 // Visit an individual instruction. This could be a newly added instruction,
1032 // or one that has been modified by an optimization.
visit(const MachineInstr & MI)1033 void BT::visit(const MachineInstr &MI) {
1034 assert(!MI.isBranch() && "Only non-branches are allowed");
1035 InstrExec.insert(&MI);
1036 visitNonBranch(MI);
1037 // Make sure to flush all the pending use updates.
1038 runUseQueue();
1039 // The call to visitNonBranch could propagate the changes until a branch
1040 // is actually visited. This could result in adding CFG edges to the flow
1041 // queue. Since the queue won't be processed, clear it.
1042 while (!FlowQ.empty())
1043 FlowQ.pop();
1044 }
1045
reset()1046 void BT::reset() {
1047 EdgeExec.clear();
1048 InstrExec.clear();
1049 Map.clear();
1050 ReachedBB.clear();
1051 ReachedBB.reserve(MF.size());
1052 }
1053
runEdgeQueue(BitVector & BlockScanned)1054 void BT::runEdgeQueue(BitVector &BlockScanned) {
1055 while (!FlowQ.empty()) {
1056 CFGEdge Edge = FlowQ.front();
1057 FlowQ.pop();
1058
1059 if (!EdgeExec.insert(Edge).second)
1060 return;
1061 ReachedBB.insert(Edge.second);
1062
1063 const MachineBasicBlock &B = *MF.getBlockNumbered(Edge.second);
1064 MachineBasicBlock::const_iterator It = B.begin(), End = B.end();
1065 // Visit PHI nodes first.
1066 while (It != End && It->isPHI()) {
1067 const MachineInstr &PI = *It++;
1068 InstrExec.insert(&PI);
1069 visitPHI(PI);
1070 }
1071
1072 // If this block has already been visited through a flow graph edge,
1073 // then the instructions have already been processed. Any updates to
1074 // the cells would now only happen through visitUsesOf...
1075 if (BlockScanned[Edge.second])
1076 return;
1077 BlockScanned[Edge.second] = true;
1078
1079 // Visit non-branch instructions.
1080 while (It != End && !It->isBranch()) {
1081 const MachineInstr &MI = *It++;
1082 InstrExec.insert(&MI);
1083 visitNonBranch(MI);
1084 }
1085 // If block end has been reached, add the fall-through edge to the queue.
1086 if (It == End) {
1087 MachineFunction::const_iterator BIt = B.getIterator();
1088 MachineFunction::const_iterator Next = std::next(BIt);
1089 if (Next != MF.end() && B.isSuccessor(&*Next)) {
1090 int ThisN = B.getNumber();
1091 int NextN = Next->getNumber();
1092 FlowQ.push(CFGEdge(ThisN, NextN));
1093 }
1094 } else {
1095 // Handle the remaining sequence of branches. This function will update
1096 // the work queue.
1097 visitBranchesFrom(*It);
1098 }
1099 } // while (!FlowQ->empty())
1100 }
1101
runUseQueue()1102 void BT::runUseQueue() {
1103 while (!UseQ.empty()) {
1104 MachineInstr &UseI = *UseQ.front();
1105 UseQ.pop();
1106
1107 if (!InstrExec.count(&UseI))
1108 continue;
1109 if (UseI.isPHI())
1110 visitPHI(UseI);
1111 else if (!UseI.isBranch())
1112 visitNonBranch(UseI);
1113 else
1114 visitBranchesFrom(UseI);
1115 }
1116 }
1117
run()1118 void BT::run() {
1119 reset();
1120 assert(FlowQ.empty());
1121
1122 using MachineFlowGraphTraits = GraphTraits<const MachineFunction*>;
1123 const MachineBasicBlock *Entry = MachineFlowGraphTraits::getEntryNode(&MF);
1124
1125 unsigned MaxBN = 0;
1126 for (const MachineBasicBlock &B : MF) {
1127 assert(B.getNumber() >= 0 && "Disconnected block");
1128 unsigned BN = B.getNumber();
1129 if (BN > MaxBN)
1130 MaxBN = BN;
1131 }
1132
1133 // Keep track of visited blocks.
1134 BitVector BlockScanned(MaxBN+1);
1135
1136 int EntryN = Entry->getNumber();
1137 // Generate a fake edge to get something to start with.
1138 FlowQ.push(CFGEdge(-1, EntryN));
1139
1140 while (!FlowQ.empty() || !UseQ.empty()) {
1141 runEdgeQueue(BlockScanned);
1142 runUseQueue();
1143 }
1144 UseQ.reset();
1145
1146 if (Trace)
1147 print_cells(dbgs() << "Cells after propagation:\n");
1148 }
1149