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 { 80 printv(unsigned r) : R(r) {} 81 82 unsigned R; 83 }; 84 85 raw_ostream &operator<< (raw_ostream &OS, const printv &PV) { 86 if (PV.R) 87 OS << 'v' << TargetRegisterInfo::virtReg2Index(PV.R); 88 else 89 OS << 's'; 90 return OS; 91 } 92 93 } // end anonymous namespace 94 95 namespace llvm { 96 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 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 182 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 187 BitTracker::BitTracker(const MachineEvaluator &E, MachineFunction &F) 188 : ME(E), MF(F), MRI(F.getRegInfo()), Map(*new CellMapType), Trace(false) { 189 } 190 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. 201 bool BT::RegisterCell::meet(const RegisterCell &RC, unsigned 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 || TargetRegisterInfo::isVirtualRegister(SelfR)); 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. 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 // Sanity: M must be a valid mask for *this. 218 assert(B < W && E < W); 219 // Sanity: 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 235 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 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 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 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 292 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 301 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 310 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 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 329 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 (TargetRegisterInfo::isVirtualRegister(RR.Reg)) { 339 const auto &VC = composeWithSubRegIndex(*MRI.getRegClass(RR.Reg), RR.Sub); 340 return TRI.getRegSizeInBits(VC); 341 } 342 assert(TargetRegisterInfo::isPhysicalRegister(RR.Reg)); 343 unsigned PhysR = (RR.Sub == 0) ? RR.Reg : TRI.getSubReg(RR.Reg, RR.Sub); 344 return getPhysRegBitWidth(PhysR); 345 } 346 347 BT::RegisterCell BT::MachineEvaluator::getCell(const RegisterRef &RR, 348 const CellMapType &M) const { 349 uint16_t BW = getRegBitWidth(RR); 350 351 // Physical registers are assumed to be present in the map with an unknown 352 // value. Don't actually insert anything in the map, just return the cell. 353 if (TargetRegisterInfo::isPhysicalRegister(RR.Reg)) 354 return RegisterCell::self(0, BW); 355 356 assert(TargetRegisterInfo::isVirtualRegister(RR.Reg)); 357 // For virtual registers that belong to a class that is not tracked, 358 // generate an "unknown" value as well. 359 const TargetRegisterClass *C = MRI.getRegClass(RR.Reg); 360 if (!track(C)) 361 return RegisterCell::self(0, BW); 362 363 CellMapType::const_iterator F = M.find(RR.Reg); 364 if (F != M.end()) { 365 if (!RR.Sub) 366 return F->second; 367 BitMask M = mask(RR.Reg, RR.Sub); 368 return F->second.extract(M); 369 } 370 // If not found, create a "top" entry, but do not insert it in the map. 371 return RegisterCell::top(BW); 372 } 373 374 void BT::MachineEvaluator::putCell(const RegisterRef &RR, RegisterCell RC, 375 CellMapType &M) const { 376 // While updating the cell map can be done in a meaningful way for 377 // a part of a register, it makes little sense to implement it as the 378 // SSA representation would never contain such "partial definitions". 379 if (!TargetRegisterInfo::isVirtualRegister(RR.Reg)) 380 return; 381 assert(RR.Sub == 0 && "Unexpected sub-register in definition"); 382 // Eliminate all ref-to-reg-0 bit values: replace them with "self". 383 M[RR.Reg] = RC.regify(RR.Reg); 384 } 385 386 // Check if the cell represents a compile-time integer value. 387 bool BT::MachineEvaluator::isInt(const RegisterCell &A) const { 388 uint16_t W = A.width(); 389 for (uint16_t i = 0; i < W; ++i) 390 if (!A[i].is(0) && !A[i].is(1)) 391 return false; 392 return true; 393 } 394 395 // Convert a cell to the integer value. The result must fit in uint64_t. 396 uint64_t BT::MachineEvaluator::toInt(const RegisterCell &A) const { 397 assert(isInt(A)); 398 uint64_t Val = 0; 399 uint16_t W = A.width(); 400 for (uint16_t i = 0; i < W; ++i) { 401 Val <<= 1; 402 Val |= A[i].is(1); 403 } 404 return Val; 405 } 406 407 // Evaluator helper functions. These implement some common operation on 408 // register cells that can be used to implement target-specific instructions 409 // in a target-specific evaluator. 410 411 BT::RegisterCell BT::MachineEvaluator::eIMM(int64_t V, uint16_t W) const { 412 RegisterCell Res(W); 413 // For bits beyond the 63rd, this will generate the sign bit of V. 414 for (uint16_t i = 0; i < W; ++i) { 415 Res[i] = BitValue(V & 1); 416 V >>= 1; 417 } 418 return Res; 419 } 420 421 BT::RegisterCell BT::MachineEvaluator::eIMM(const ConstantInt *CI) const { 422 const APInt &A = CI->getValue(); 423 uint16_t BW = A.getBitWidth(); 424 assert((unsigned)BW == A.getBitWidth() && "BitWidth overflow"); 425 RegisterCell Res(BW); 426 for (uint16_t i = 0; i < BW; ++i) 427 Res[i] = A[i]; 428 return Res; 429 } 430 431 BT::RegisterCell BT::MachineEvaluator::eADD(const RegisterCell &A1, 432 const RegisterCell &A2) const { 433 uint16_t W = A1.width(); 434 assert(W == A2.width()); 435 RegisterCell Res(W); 436 bool Carry = false; 437 uint16_t I; 438 for (I = 0; I < W; ++I) { 439 const BitValue &V1 = A1[I]; 440 const BitValue &V2 = A2[I]; 441 if (!V1.num() || !V2.num()) 442 break; 443 unsigned S = bool(V1) + bool(V2) + Carry; 444 Res[I] = BitValue(S & 1); 445 Carry = (S > 1); 446 } 447 for (; I < W; ++I) { 448 const BitValue &V1 = A1[I]; 449 const BitValue &V2 = A2[I]; 450 // If the next bit is same as Carry, the result will be 0 plus the 451 // other bit. The Carry bit will remain unchanged. 452 if (V1.is(Carry)) 453 Res[I] = BitValue::ref(V2); 454 else if (V2.is(Carry)) 455 Res[I] = BitValue::ref(V1); 456 else 457 break; 458 } 459 for (; I < W; ++I) 460 Res[I] = BitValue::self(); 461 return Res; 462 } 463 464 BT::RegisterCell BT::MachineEvaluator::eSUB(const RegisterCell &A1, 465 const RegisterCell &A2) const { 466 uint16_t W = A1.width(); 467 assert(W == A2.width()); 468 RegisterCell Res(W); 469 bool Borrow = false; 470 uint16_t I; 471 for (I = 0; I < W; ++I) { 472 const BitValue &V1 = A1[I]; 473 const BitValue &V2 = A2[I]; 474 if (!V1.num() || !V2.num()) 475 break; 476 unsigned S = bool(V1) - bool(V2) - Borrow; 477 Res[I] = BitValue(S & 1); 478 Borrow = (S > 1); 479 } 480 for (; I < W; ++I) { 481 const BitValue &V1 = A1[I]; 482 const BitValue &V2 = A2[I]; 483 if (V1.is(Borrow)) { 484 Res[I] = BitValue::ref(V2); 485 break; 486 } 487 if (V2.is(Borrow)) 488 Res[I] = BitValue::ref(V1); 489 else 490 break; 491 } 492 for (; I < W; ++I) 493 Res[I] = BitValue::self(); 494 return Res; 495 } 496 497 BT::RegisterCell BT::MachineEvaluator::eMLS(const RegisterCell &A1, 498 const RegisterCell &A2) const { 499 uint16_t W = A1.width() + A2.width(); 500 uint16_t Z = A1.ct(false) + A2.ct(false); 501 RegisterCell Res(W); 502 Res.fill(0, Z, BitValue::Zero); 503 Res.fill(Z, W, BitValue::self()); 504 return Res; 505 } 506 507 BT::RegisterCell BT::MachineEvaluator::eMLU(const RegisterCell &A1, 508 const RegisterCell &A2) const { 509 uint16_t W = A1.width() + A2.width(); 510 uint16_t Z = A1.ct(false) + A2.ct(false); 511 RegisterCell Res(W); 512 Res.fill(0, Z, BitValue::Zero); 513 Res.fill(Z, W, BitValue::self()); 514 return Res; 515 } 516 517 BT::RegisterCell BT::MachineEvaluator::eASL(const RegisterCell &A1, 518 uint16_t Sh) const { 519 assert(Sh <= A1.width()); 520 RegisterCell Res = RegisterCell::ref(A1); 521 Res.rol(Sh); 522 Res.fill(0, Sh, BitValue::Zero); 523 return Res; 524 } 525 526 BT::RegisterCell BT::MachineEvaluator::eLSR(const RegisterCell &A1, 527 uint16_t Sh) const { 528 uint16_t W = A1.width(); 529 assert(Sh <= W); 530 RegisterCell Res = RegisterCell::ref(A1); 531 Res.rol(W-Sh); 532 Res.fill(W-Sh, W, BitValue::Zero); 533 return Res; 534 } 535 536 BT::RegisterCell BT::MachineEvaluator::eASR(const RegisterCell &A1, 537 uint16_t Sh) const { 538 uint16_t W = A1.width(); 539 assert(Sh <= W); 540 RegisterCell Res = RegisterCell::ref(A1); 541 BitValue Sign = Res[W-1]; 542 Res.rol(W-Sh); 543 Res.fill(W-Sh, W, Sign); 544 return Res; 545 } 546 547 BT::RegisterCell BT::MachineEvaluator::eAND(const RegisterCell &A1, 548 const RegisterCell &A2) const { 549 uint16_t W = A1.width(); 550 assert(W == A2.width()); 551 RegisterCell Res(W); 552 for (uint16_t i = 0; i < W; ++i) { 553 const BitValue &V1 = A1[i]; 554 const BitValue &V2 = A2[i]; 555 if (V1.is(1)) 556 Res[i] = BitValue::ref(V2); 557 else if (V2.is(1)) 558 Res[i] = BitValue::ref(V1); 559 else if (V1.is(0) || V2.is(0)) 560 Res[i] = BitValue::Zero; 561 else if (V1 == V2) 562 Res[i] = V1; 563 else 564 Res[i] = BitValue::self(); 565 } 566 return Res; 567 } 568 569 BT::RegisterCell BT::MachineEvaluator::eORL(const RegisterCell &A1, 570 const RegisterCell &A2) const { 571 uint16_t W = A1.width(); 572 assert(W == A2.width()); 573 RegisterCell Res(W); 574 for (uint16_t i = 0; i < W; ++i) { 575 const BitValue &V1 = A1[i]; 576 const BitValue &V2 = A2[i]; 577 if (V1.is(1) || V2.is(1)) 578 Res[i] = BitValue::One; 579 else if (V1.is(0)) 580 Res[i] = BitValue::ref(V2); 581 else if (V2.is(0)) 582 Res[i] = BitValue::ref(V1); 583 else if (V1 == V2) 584 Res[i] = V1; 585 else 586 Res[i] = BitValue::self(); 587 } 588 return Res; 589 } 590 591 BT::RegisterCell BT::MachineEvaluator::eXOR(const RegisterCell &A1, 592 const RegisterCell &A2) const { 593 uint16_t W = A1.width(); 594 assert(W == A2.width()); 595 RegisterCell Res(W); 596 for (uint16_t i = 0; i < W; ++i) { 597 const BitValue &V1 = A1[i]; 598 const BitValue &V2 = A2[i]; 599 if (V1.is(0)) 600 Res[i] = BitValue::ref(V2); 601 else if (V2.is(0)) 602 Res[i] = BitValue::ref(V1); 603 else if (V1 == V2) 604 Res[i] = BitValue::Zero; 605 else 606 Res[i] = BitValue::self(); 607 } 608 return Res; 609 } 610 611 BT::RegisterCell BT::MachineEvaluator::eNOT(const RegisterCell &A1) const { 612 uint16_t W = A1.width(); 613 RegisterCell Res(W); 614 for (uint16_t i = 0; i < W; ++i) { 615 const BitValue &V = A1[i]; 616 if (V.is(0)) 617 Res[i] = BitValue::One; 618 else if (V.is(1)) 619 Res[i] = BitValue::Zero; 620 else 621 Res[i] = BitValue::self(); 622 } 623 return Res; 624 } 625 626 BT::RegisterCell BT::MachineEvaluator::eSET(const RegisterCell &A1, 627 uint16_t BitN) const { 628 assert(BitN < A1.width()); 629 RegisterCell Res = RegisterCell::ref(A1); 630 Res[BitN] = BitValue::One; 631 return Res; 632 } 633 634 BT::RegisterCell BT::MachineEvaluator::eCLR(const RegisterCell &A1, 635 uint16_t BitN) const { 636 assert(BitN < A1.width()); 637 RegisterCell Res = RegisterCell::ref(A1); 638 Res[BitN] = BitValue::Zero; 639 return Res; 640 } 641 642 BT::RegisterCell BT::MachineEvaluator::eCLB(const RegisterCell &A1, bool B, 643 uint16_t W) const { 644 uint16_t C = A1.cl(B), AW = A1.width(); 645 // If the last leading non-B bit is not a constant, then we don't know 646 // the real count. 647 if ((C < AW && A1[AW-1-C].num()) || C == AW) 648 return eIMM(C, W); 649 return RegisterCell::self(0, W); 650 } 651 652 BT::RegisterCell BT::MachineEvaluator::eCTB(const RegisterCell &A1, bool B, 653 uint16_t W) const { 654 uint16_t C = A1.ct(B), AW = A1.width(); 655 // If the last trailing non-B bit is not a constant, then we don't know 656 // the real count. 657 if ((C < AW && A1[C].num()) || C == AW) 658 return eIMM(C, W); 659 return RegisterCell::self(0, W); 660 } 661 662 BT::RegisterCell BT::MachineEvaluator::eSXT(const RegisterCell &A1, 663 uint16_t FromN) const { 664 uint16_t W = A1.width(); 665 assert(FromN <= W); 666 RegisterCell Res = RegisterCell::ref(A1); 667 BitValue Sign = Res[FromN-1]; 668 // Sign-extend "inreg". 669 Res.fill(FromN, W, Sign); 670 return Res; 671 } 672 673 BT::RegisterCell BT::MachineEvaluator::eZXT(const RegisterCell &A1, 674 uint16_t FromN) const { 675 uint16_t W = A1.width(); 676 assert(FromN <= W); 677 RegisterCell Res = RegisterCell::ref(A1); 678 Res.fill(FromN, W, BitValue::Zero); 679 return Res; 680 } 681 682 BT::RegisterCell BT::MachineEvaluator::eXTR(const RegisterCell &A1, 683 uint16_t B, uint16_t E) const { 684 uint16_t W = A1.width(); 685 assert(B < W && E <= W); 686 if (B == E) 687 return RegisterCell(0); 688 uint16_t Last = (E > 0) ? E-1 : W-1; 689 RegisterCell Res = RegisterCell::ref(A1).extract(BT::BitMask(B, Last)); 690 // Return shorter cell. 691 return Res; 692 } 693 694 BT::RegisterCell BT::MachineEvaluator::eINS(const RegisterCell &A1, 695 const RegisterCell &A2, uint16_t AtN) const { 696 uint16_t W1 = A1.width(), W2 = A2.width(); 697 (void)W1; 698 assert(AtN < W1 && AtN+W2 <= W1); 699 // Copy bits from A1, insert A2 at position AtN. 700 RegisterCell Res = RegisterCell::ref(A1); 701 if (W2 > 0) 702 Res.insert(RegisterCell::ref(A2), BT::BitMask(AtN, AtN+W2-1)); 703 return Res; 704 } 705 706 BT::BitMask BT::MachineEvaluator::mask(unsigned Reg, unsigned Sub) const { 707 assert(Sub == 0 && "Generic BitTracker::mask called for Sub != 0"); 708 uint16_t W = getRegBitWidth(Reg); 709 assert(W > 0 && "Cannot generate mask for empty register"); 710 return BitMask(0, W-1); 711 } 712 713 uint16_t BT::MachineEvaluator::getPhysRegBitWidth(unsigned Reg) const { 714 assert(TargetRegisterInfo::isPhysicalRegister(Reg)); 715 const TargetRegisterClass &PC = *TRI.getMinimalPhysRegClass(Reg); 716 return TRI.getRegSizeInBits(PC); 717 } 718 719 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 765 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 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 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 (unsigned i = 0, n = MI.getNumOperands(); i < n; ++i) { 854 const MachineOperand &MO = MI.getOperand(i); 855 if (!MO.isReg() || !MO.isUse()) 856 continue; 857 RegisterRef RU(MO); 858 dbgs() << " input reg: " << printReg(RU.Reg, &ME.TRI, RU.Sub) 859 << " cell: " << ME.getCell(RU, Map) << "\n"; 860 } 861 dbgs() << "Outputs:\n"; 862 for (const std::pair<unsigned, RegisterCell> &P : ResMap) { 863 RegisterRef RD(P.first); 864 dbgs() << " " << printReg(P.first, &ME.TRI) << " cell: " 865 << ME.getCell(RD, ResMap) << "\n"; 866 } 867 } 868 869 // Iterate over all definitions of the instruction, and update the 870 // cells accordingly. 871 for (const MachineOperand &MO : MI.operands()) { 872 // Visit register defs only. 873 if (!MO.isReg() || !MO.isDef()) 874 continue; 875 RegisterRef RD(MO); 876 assert(RD.Sub == 0 && "Unexpected sub-register in definition"); 877 if (!TargetRegisterInfo::isVirtualRegister(RD.Reg)) 878 continue; 879 880 bool Changed = false; 881 if (!Eval || ResMap.count(RD.Reg) == 0) { 882 // Set to "ref" (aka "bottom"). 883 uint16_t DefBW = ME.getRegBitWidth(RD); 884 RegisterCell RefC = RegisterCell::self(RD.Reg, DefBW); 885 if (RefC != ME.getCell(RD, Map)) { 886 ME.putCell(RD, RefC, Map); 887 Changed = true; 888 } 889 } else { 890 RegisterCell DefC = ME.getCell(RD, Map); 891 RegisterCell ResC = ME.getCell(RD, ResMap); 892 // This is a non-phi instruction, so the values of the inputs come 893 // from the same registers each time this instruction is evaluated. 894 // During the propagation, the values of the inputs can become lowered 895 // in the sense of the lattice operation, which may cause different 896 // results to be calculated in subsequent evaluations. This should 897 // not cause the bottoming of the result in the map, since the new 898 // result is already reflecting the lowered inputs. 899 for (uint16_t i = 0, w = DefC.width(); i < w; ++i) { 900 BitValue &V = DefC[i]; 901 // Bits that are already "bottom" should not be updated. 902 if (V.Type == BitValue::Ref && V.RefI.Reg == RD.Reg) 903 continue; 904 // Same for those that are identical in DefC and ResC. 905 if (V == ResC[i]) 906 continue; 907 V = ResC[i]; 908 Changed = true; 909 } 910 if (Changed) 911 ME.putCell(RD, DefC, Map); 912 } 913 if (Changed) 914 visitUsesOf(RD.Reg); 915 } 916 } 917 918 void BT::visitBranchesFrom(const MachineInstr &BI) { 919 const MachineBasicBlock &B = *BI.getParent(); 920 MachineBasicBlock::const_iterator It = BI, End = B.end(); 921 BranchTargetList Targets, BTs; 922 bool FallsThrough = true, DefaultToAll = false; 923 int ThisN = B.getNumber(); 924 925 do { 926 BTs.clear(); 927 const MachineInstr &MI = *It; 928 if (Trace) 929 dbgs() << "Visit BR(" << printMBBReference(B) << "): " << MI; 930 assert(MI.isBranch() && "Expecting branch instruction"); 931 InstrExec.insert(&MI); 932 bool Eval = ME.evaluate(MI, Map, BTs, FallsThrough); 933 if (!Eval) { 934 // If the evaluation failed, we will add all targets. Keep going in 935 // the loop to mark all executable branches as such. 936 DefaultToAll = true; 937 FallsThrough = true; 938 if (Trace) 939 dbgs() << " failed to evaluate: will add all CFG successors\n"; 940 } else if (!DefaultToAll) { 941 // If evaluated successfully add the targets to the cumulative list. 942 if (Trace) { 943 dbgs() << " adding targets:"; 944 for (unsigned i = 0, n = BTs.size(); i < n; ++i) 945 dbgs() << " " << printMBBReference(*BTs[i]); 946 if (FallsThrough) 947 dbgs() << "\n falls through\n"; 948 else 949 dbgs() << "\n does not fall through\n"; 950 } 951 Targets.insert(BTs.begin(), BTs.end()); 952 } 953 ++It; 954 } while (FallsThrough && It != End); 955 956 if (!DefaultToAll) { 957 // Need to add all CFG successors that lead to EH landing pads. 958 // There won't be explicit branches to these blocks, but they must 959 // be processed. 960 for (const MachineBasicBlock *SB : B.successors()) { 961 if (SB->isEHPad()) 962 Targets.insert(SB); 963 } 964 if (FallsThrough) { 965 MachineFunction::const_iterator BIt = B.getIterator(); 966 MachineFunction::const_iterator Next = std::next(BIt); 967 if (Next != MF.end()) 968 Targets.insert(&*Next); 969 } 970 } else { 971 for (const MachineBasicBlock *SB : B.successors()) 972 Targets.insert(SB); 973 } 974 975 for (const MachineBasicBlock *TB : Targets) 976 FlowQ.push(CFGEdge(ThisN, TB->getNumber())); 977 } 978 979 void BT::visitUsesOf(unsigned Reg) { 980 if (Trace) 981 dbgs() << "queuing uses of modified reg " << printReg(Reg, &ME.TRI) 982 << " cell: " << ME.getCell(Reg, Map) << '\n'; 983 984 for (MachineInstr &UseI : MRI.use_nodbg_instructions(Reg)) 985 UseQ.push(&UseI); 986 } 987 988 BT::RegisterCell BT::get(RegisterRef RR) const { 989 return ME.getCell(RR, Map); 990 } 991 992 void BT::put(RegisterRef RR, const RegisterCell &RC) { 993 ME.putCell(RR, RC, Map); 994 } 995 996 // Replace all references to bits from OldRR with the corresponding bits 997 // in NewRR. 998 void BT::subst(RegisterRef OldRR, RegisterRef NewRR) { 999 assert(Map.count(OldRR.Reg) > 0 && "OldRR not present in map"); 1000 BitMask OM = ME.mask(OldRR.Reg, OldRR.Sub); 1001 BitMask NM = ME.mask(NewRR.Reg, NewRR.Sub); 1002 uint16_t OMB = OM.first(), OME = OM.last(); 1003 uint16_t NMB = NM.first(), NME = NM.last(); 1004 (void)NME; 1005 assert((OME-OMB == NME-NMB) && 1006 "Substituting registers of different lengths"); 1007 for (std::pair<const unsigned, RegisterCell> &P : Map) { 1008 RegisterCell &RC = P.second; 1009 for (uint16_t i = 0, w = RC.width(); i < w; ++i) { 1010 BitValue &V = RC[i]; 1011 if (V.Type != BitValue::Ref || V.RefI.Reg != OldRR.Reg) 1012 continue; 1013 if (V.RefI.Pos < OMB || V.RefI.Pos > OME) 1014 continue; 1015 V.RefI.Reg = NewRR.Reg; 1016 V.RefI.Pos += NMB-OMB; 1017 } 1018 } 1019 } 1020 1021 // Check if the block has been "executed" during propagation. (If not, the 1022 // block is dead, but it may still appear to be reachable.) 1023 bool BT::reached(const MachineBasicBlock *B) const { 1024 int BN = B->getNumber(); 1025 assert(BN >= 0); 1026 return ReachedBB.count(BN); 1027 } 1028 1029 // Visit an individual instruction. This could be a newly added instruction, 1030 // or one that has been modified by an optimization. 1031 void BT::visit(const MachineInstr &MI) { 1032 assert(!MI.isBranch() && "Only non-branches are allowed"); 1033 InstrExec.insert(&MI); 1034 visitNonBranch(MI); 1035 // Make sure to flush all the pending use updates. 1036 runUseQueue(); 1037 // The call to visitNonBranch could propagate the changes until a branch 1038 // is actually visited. This could result in adding CFG edges to the flow 1039 // queue. Since the queue won't be processed, clear it. 1040 while (!FlowQ.empty()) 1041 FlowQ.pop(); 1042 } 1043 1044 void BT::reset() { 1045 EdgeExec.clear(); 1046 InstrExec.clear(); 1047 Map.clear(); 1048 ReachedBB.clear(); 1049 ReachedBB.reserve(MF.size()); 1050 } 1051 1052 void BT::runEdgeQueue(BitVector &BlockScanned) { 1053 while (!FlowQ.empty()) { 1054 CFGEdge Edge = FlowQ.front(); 1055 FlowQ.pop(); 1056 1057 if (EdgeExec.count(Edge)) 1058 return; 1059 EdgeExec.insert(Edge); 1060 ReachedBB.insert(Edge.second); 1061 1062 const MachineBasicBlock &B = *MF.getBlockNumbered(Edge.second); 1063 MachineBasicBlock::const_iterator It = B.begin(), End = B.end(); 1064 // Visit PHI nodes first. 1065 while (It != End && It->isPHI()) { 1066 const MachineInstr &PI = *It++; 1067 InstrExec.insert(&PI); 1068 visitPHI(PI); 1069 } 1070 1071 // If this block has already been visited through a flow graph edge, 1072 // then the instructions have already been processed. Any updates to 1073 // the cells would now only happen through visitUsesOf... 1074 if (BlockScanned[Edge.second]) 1075 return; 1076 BlockScanned[Edge.second] = true; 1077 1078 // Visit non-branch instructions. 1079 while (It != End && !It->isBranch()) { 1080 const MachineInstr &MI = *It++; 1081 InstrExec.insert(&MI); 1082 visitNonBranch(MI); 1083 } 1084 // If block end has been reached, add the fall-through edge to the queue. 1085 if (It == End) { 1086 MachineFunction::const_iterator BIt = B.getIterator(); 1087 MachineFunction::const_iterator Next = std::next(BIt); 1088 if (Next != MF.end() && B.isSuccessor(&*Next)) { 1089 int ThisN = B.getNumber(); 1090 int NextN = Next->getNumber(); 1091 FlowQ.push(CFGEdge(ThisN, NextN)); 1092 } 1093 } else { 1094 // Handle the remaining sequence of branches. This function will update 1095 // the work queue. 1096 visitBranchesFrom(*It); 1097 } 1098 } // while (!FlowQ->empty()) 1099 } 1100 1101 void BT::runUseQueue() { 1102 while (!UseQ.empty()) { 1103 MachineInstr &UseI = *UseQ.front(); 1104 UseQ.pop(); 1105 1106 if (!InstrExec.count(&UseI)) 1107 continue; 1108 if (UseI.isPHI()) 1109 visitPHI(UseI); 1110 else if (!UseI.isBranch()) 1111 visitNonBranch(UseI); 1112 else 1113 visitBranchesFrom(UseI); 1114 } 1115 } 1116 1117 void BT::run() { 1118 reset(); 1119 assert(FlowQ.empty()); 1120 1121 using MachineFlowGraphTraits = GraphTraits<const MachineFunction*>; 1122 const MachineBasicBlock *Entry = MachineFlowGraphTraits::getEntryNode(&MF); 1123 1124 unsigned MaxBN = 0; 1125 for (const MachineBasicBlock &B : MF) { 1126 assert(B.getNumber() >= 0 && "Disconnected block"); 1127 unsigned BN = B.getNumber(); 1128 if (BN > MaxBN) 1129 MaxBN = BN; 1130 } 1131 1132 // Keep track of visited blocks. 1133 BitVector BlockScanned(MaxBN+1); 1134 1135 int EntryN = Entry->getNumber(); 1136 // Generate a fake edge to get something to start with. 1137 FlowQ.push(CFGEdge(-1, EntryN)); 1138 1139 while (!FlowQ.empty() || !UseQ.empty()) { 1140 runEdgeQueue(BlockScanned); 1141 runUseQueue(); 1142 } 1143 UseQ.reset(); 1144 1145 if (Trace) 1146 print_cells(dbgs() << "Cells after propagation:\n"); 1147 } 1148