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