1 //===-- MipsConstantIslandPass.cpp - Emit Pc Relative loads----------------===// 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 // 11 // This pass is used to make Pc relative loads of constants. 12 // For now, only Mips16 will use this. 13 // 14 // Loading constants inline is expensive on Mips16 and it's in general better 15 // to place the constant nearby in code space and then it can be loaded with a 16 // simple 16 bit load instruction. 17 // 18 // The constants can be not just numbers but addresses of functions and labels. 19 // This can be particularly helpful in static relocation mode for embedded 20 // non-linux targets. 21 // 22 // 23 24 #include "Mips.h" 25 #include "MCTargetDesc/MipsBaseInfo.h" 26 #include "Mips16InstrInfo.h" 27 #include "MipsMachineFunction.h" 28 #include "MipsTargetMachine.h" 29 #include "llvm/ADT/Statistic.h" 30 #include "llvm/CodeGen/MachineBasicBlock.h" 31 #include "llvm/CodeGen/MachineConstantPool.h" 32 #include "llvm/CodeGen/MachineFunctionPass.h" 33 #include "llvm/CodeGen/MachineInstrBuilder.h" 34 #include "llvm/CodeGen/MachineRegisterInfo.h" 35 #include "llvm/IR/Function.h" 36 #include "llvm/IR/InstIterator.h" 37 #include "llvm/Support/CommandLine.h" 38 #include "llvm/Support/Debug.h" 39 #include "llvm/Support/Format.h" 40 #include "llvm/Support/MathExtras.h" 41 #include "llvm/Support/raw_ostream.h" 42 #include "llvm/Target/TargetInstrInfo.h" 43 #include "llvm/Target/TargetMachine.h" 44 #include "llvm/Target/TargetRegisterInfo.h" 45 #include <algorithm> 46 47 using namespace llvm; 48 49 #define DEBUG_TYPE "mips-constant-islands" 50 51 STATISTIC(NumCPEs, "Number of constpool entries"); 52 STATISTIC(NumSplit, "Number of uncond branches inserted"); 53 STATISTIC(NumCBrFixed, "Number of cond branches fixed"); 54 STATISTIC(NumUBrFixed, "Number of uncond branches fixed"); 55 56 // FIXME: This option should be removed once it has received sufficient testing. 57 static cl::opt<bool> 58 AlignConstantIslands("mips-align-constant-islands", cl::Hidden, cl::init(true), 59 cl::desc("Align constant islands in code")); 60 61 62 // Rather than do make check tests with huge amounts of code, we force 63 // the test to use this amount. 64 // 65 static cl::opt<int> ConstantIslandsSmallOffset( 66 "mips-constant-islands-small-offset", 67 cl::init(0), 68 cl::desc("Make small offsets be this amount for testing purposes"), 69 cl::Hidden); 70 71 // 72 // For testing purposes we tell it to not use relaxed load forms so that it 73 // will split blocks. 74 // 75 static cl::opt<bool> NoLoadRelaxation( 76 "mips-constant-islands-no-load-relaxation", 77 cl::init(false), 78 cl::desc("Don't relax loads to long loads - for testing purposes"), 79 cl::Hidden); 80 81 static unsigned int branchTargetOperand(MachineInstr *MI) { 82 switch (MI->getOpcode()) { 83 case Mips::Bimm16: 84 case Mips::BimmX16: 85 case Mips::Bteqz16: 86 case Mips::BteqzX16: 87 case Mips::Btnez16: 88 case Mips::BtnezX16: 89 case Mips::JalB16: 90 return 0; 91 case Mips::BeqzRxImm16: 92 case Mips::BeqzRxImmX16: 93 case Mips::BnezRxImm16: 94 case Mips::BnezRxImmX16: 95 return 1; 96 } 97 llvm_unreachable("Unknown branch type"); 98 } 99 100 static unsigned int longformBranchOpcode(unsigned int Opcode) { 101 switch (Opcode) { 102 case Mips::Bimm16: 103 case Mips::BimmX16: 104 return Mips::BimmX16; 105 case Mips::Bteqz16: 106 case Mips::BteqzX16: 107 return Mips::BteqzX16; 108 case Mips::Btnez16: 109 case Mips::BtnezX16: 110 return Mips::BtnezX16; 111 case Mips::JalB16: 112 return Mips::JalB16; 113 case Mips::BeqzRxImm16: 114 case Mips::BeqzRxImmX16: 115 return Mips::BeqzRxImmX16; 116 case Mips::BnezRxImm16: 117 case Mips::BnezRxImmX16: 118 return Mips::BnezRxImmX16; 119 } 120 llvm_unreachable("Unknown branch type"); 121 } 122 123 // 124 // FIXME: need to go through this whole constant islands port and check the math 125 // for branch ranges and clean this up and make some functions to calculate things 126 // that are done many times identically. 127 // Need to refactor some of the code to call this routine. 128 // 129 static unsigned int branchMaxOffsets(unsigned int Opcode) { 130 unsigned Bits, Scale; 131 switch (Opcode) { 132 case Mips::Bimm16: 133 Bits = 11; 134 Scale = 2; 135 break; 136 case Mips::BimmX16: 137 Bits = 16; 138 Scale = 2; 139 break; 140 case Mips::BeqzRxImm16: 141 Bits = 8; 142 Scale = 2; 143 break; 144 case Mips::BeqzRxImmX16: 145 Bits = 16; 146 Scale = 2; 147 break; 148 case Mips::BnezRxImm16: 149 Bits = 8; 150 Scale = 2; 151 break; 152 case Mips::BnezRxImmX16: 153 Bits = 16; 154 Scale = 2; 155 break; 156 case Mips::Bteqz16: 157 Bits = 8; 158 Scale = 2; 159 break; 160 case Mips::BteqzX16: 161 Bits = 16; 162 Scale = 2; 163 break; 164 case Mips::Btnez16: 165 Bits = 8; 166 Scale = 2; 167 break; 168 case Mips::BtnezX16: 169 Bits = 16; 170 Scale = 2; 171 break; 172 default: 173 llvm_unreachable("Unknown branch type"); 174 } 175 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 176 return MaxOffs; 177 } 178 179 namespace { 180 181 182 typedef MachineBasicBlock::iterator Iter; 183 typedef MachineBasicBlock::reverse_iterator ReverseIter; 184 185 /// MipsConstantIslands - Due to limited PC-relative displacements, Mips 186 /// requires constant pool entries to be scattered among the instructions 187 /// inside a function. To do this, it completely ignores the normal LLVM 188 /// constant pool; instead, it places constants wherever it feels like with 189 /// special instructions. 190 /// 191 /// The terminology used in this pass includes: 192 /// Islands - Clumps of constants placed in the function. 193 /// Water - Potential places where an island could be formed. 194 /// CPE - A constant pool entry that has been placed somewhere, which 195 /// tracks a list of users. 196 197 class MipsConstantIslands : public MachineFunctionPass { 198 199 /// BasicBlockInfo - Information about the offset and size of a single 200 /// basic block. 201 struct BasicBlockInfo { 202 /// Offset - Distance from the beginning of the function to the beginning 203 /// of this basic block. 204 /// 205 /// Offsets are computed assuming worst case padding before an aligned 206 /// block. This means that subtracting basic block offsets always gives a 207 /// conservative estimate of the real distance which may be smaller. 208 /// 209 /// Because worst case padding is used, the computed offset of an aligned 210 /// block may not actually be aligned. 211 unsigned Offset; 212 213 /// Size - Size of the basic block in bytes. If the block contains 214 /// inline assembly, this is a worst case estimate. 215 /// 216 /// The size does not include any alignment padding whether from the 217 /// beginning of the block, or from an aligned jump table at the end. 218 unsigned Size; 219 220 // FIXME: ignore LogAlign for this patch 221 // 222 unsigned postOffset(unsigned LogAlign = 0) const { 223 unsigned PO = Offset + Size; 224 return PO; 225 } 226 227 BasicBlockInfo() : Offset(0), Size(0) {} 228 229 }; 230 231 std::vector<BasicBlockInfo> BBInfo; 232 233 /// WaterList - A sorted list of basic blocks where islands could be placed 234 /// (i.e. blocks that don't fall through to the following block, due 235 /// to a return, unreachable, or unconditional branch). 236 std::vector<MachineBasicBlock*> WaterList; 237 238 /// NewWaterList - The subset of WaterList that was created since the 239 /// previous iteration by inserting unconditional branches. 240 SmallSet<MachineBasicBlock*, 4> NewWaterList; 241 242 typedef std::vector<MachineBasicBlock*>::iterator water_iterator; 243 244 /// CPUser - One user of a constant pool, keeping the machine instruction 245 /// pointer, the constant pool being referenced, and the max displacement 246 /// allowed from the instruction to the CP. The HighWaterMark records the 247 /// highest basic block where a new CPEntry can be placed. To ensure this 248 /// pass terminates, the CP entries are initially placed at the end of the 249 /// function and then move monotonically to lower addresses. The 250 /// exception to this rule is when the current CP entry for a particular 251 /// CPUser is out of range, but there is another CP entry for the same 252 /// constant value in range. We want to use the existing in-range CP 253 /// entry, but if it later moves out of range, the search for new water 254 /// should resume where it left off. The HighWaterMark is used to record 255 /// that point. 256 struct CPUser { 257 MachineInstr *MI; 258 MachineInstr *CPEMI; 259 MachineBasicBlock *HighWaterMark; 260 private: 261 unsigned MaxDisp; 262 unsigned LongFormMaxDisp; // mips16 has 16/32 bit instructions 263 // with different displacements 264 unsigned LongFormOpcode; 265 public: 266 bool NegOk; 267 CPUser(MachineInstr *mi, MachineInstr *cpemi, unsigned maxdisp, 268 bool neg, 269 unsigned longformmaxdisp, unsigned longformopcode) 270 : MI(mi), CPEMI(cpemi), MaxDisp(maxdisp), 271 LongFormMaxDisp(longformmaxdisp), LongFormOpcode(longformopcode), 272 NegOk(neg){ 273 HighWaterMark = CPEMI->getParent(); 274 } 275 /// getMaxDisp - Returns the maximum displacement supported by MI. 276 unsigned getMaxDisp() const { 277 unsigned xMaxDisp = ConstantIslandsSmallOffset? 278 ConstantIslandsSmallOffset: MaxDisp; 279 return xMaxDisp; 280 } 281 void setMaxDisp(unsigned val) { 282 MaxDisp = val; 283 } 284 unsigned getLongFormMaxDisp() const { 285 return LongFormMaxDisp; 286 } 287 unsigned getLongFormOpcode() const { 288 return LongFormOpcode; 289 } 290 }; 291 292 /// CPUsers - Keep track of all of the machine instructions that use various 293 /// constant pools and their max displacement. 294 std::vector<CPUser> CPUsers; 295 296 /// CPEntry - One per constant pool entry, keeping the machine instruction 297 /// pointer, the constpool index, and the number of CPUser's which 298 /// reference this entry. 299 struct CPEntry { 300 MachineInstr *CPEMI; 301 unsigned CPI; 302 unsigned RefCount; 303 CPEntry(MachineInstr *cpemi, unsigned cpi, unsigned rc = 0) 304 : CPEMI(cpemi), CPI(cpi), RefCount(rc) {} 305 }; 306 307 /// CPEntries - Keep track of all of the constant pool entry machine 308 /// instructions. For each original constpool index (i.e. those that 309 /// existed upon entry to this pass), it keeps a vector of entries. 310 /// Original elements are cloned as we go along; the clones are 311 /// put in the vector of the original element, but have distinct CPIs. 312 std::vector<std::vector<CPEntry> > CPEntries; 313 314 /// ImmBranch - One per immediate branch, keeping the machine instruction 315 /// pointer, conditional or unconditional, the max displacement, 316 /// and (if isCond is true) the corresponding unconditional branch 317 /// opcode. 318 struct ImmBranch { 319 MachineInstr *MI; 320 unsigned MaxDisp : 31; 321 bool isCond : 1; 322 int UncondBr; 323 ImmBranch(MachineInstr *mi, unsigned maxdisp, bool cond, int ubr) 324 : MI(mi), MaxDisp(maxdisp), isCond(cond), UncondBr(ubr) {} 325 }; 326 327 /// ImmBranches - Keep track of all the immediate branch instructions. 328 /// 329 std::vector<ImmBranch> ImmBranches; 330 331 /// HasFarJump - True if any far jump instruction has been emitted during 332 /// the branch fix up pass. 333 bool HasFarJump; 334 335 const MipsSubtarget *STI; 336 const Mips16InstrInfo *TII; 337 MipsFunctionInfo *MFI; 338 MachineFunction *MF; 339 MachineConstantPool *MCP; 340 341 unsigned PICLabelUId; 342 bool PrescannedForConstants; 343 344 void initPICLabelUId(unsigned UId) { 345 PICLabelUId = UId; 346 } 347 348 349 unsigned createPICLabelUId() { 350 return PICLabelUId++; 351 } 352 353 public: 354 static char ID; 355 MipsConstantIslands() 356 : MachineFunctionPass(ID), STI(nullptr), MF(nullptr), MCP(nullptr), 357 PrescannedForConstants(false) {} 358 359 const char *getPassName() const override { 360 return "Mips Constant Islands"; 361 } 362 363 bool runOnMachineFunction(MachineFunction &F) override; 364 365 MachineFunctionProperties getRequiredProperties() const override { 366 return MachineFunctionProperties().set( 367 MachineFunctionProperties::Property::AllVRegsAllocated); 368 } 369 370 void doInitialPlacement(std::vector<MachineInstr*> &CPEMIs); 371 CPEntry *findConstPoolEntry(unsigned CPI, const MachineInstr *CPEMI); 372 unsigned getCPELogAlign(const MachineInstr &CPEMI); 373 void initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs); 374 unsigned getOffsetOf(MachineInstr *MI) const; 375 unsigned getUserOffset(CPUser&) const; 376 void dumpBBs(); 377 378 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, 379 unsigned Disp, bool NegativeOK); 380 bool isOffsetInRange(unsigned UserOffset, unsigned TrialOffset, 381 const CPUser &U); 382 383 void computeBlockSize(MachineBasicBlock *MBB); 384 MachineBasicBlock *splitBlockBeforeInstr(MachineInstr &MI); 385 void updateForInsertedWaterBlock(MachineBasicBlock *NewBB); 386 void adjustBBOffsetsAfter(MachineBasicBlock *BB); 387 bool decrementCPEReferenceCount(unsigned CPI, MachineInstr* CPEMI); 388 int findInRangeCPEntry(CPUser& U, unsigned UserOffset); 389 int findLongFormInRangeCPEntry(CPUser& U, unsigned UserOffset); 390 bool findAvailableWater(CPUser&U, unsigned UserOffset, 391 water_iterator &WaterIter); 392 void createNewWater(unsigned CPUserIndex, unsigned UserOffset, 393 MachineBasicBlock *&NewMBB); 394 bool handleConstantPoolUser(unsigned CPUserIndex); 395 void removeDeadCPEMI(MachineInstr *CPEMI); 396 bool removeUnusedCPEntries(); 397 bool isCPEntryInRange(MachineInstr *MI, unsigned UserOffset, 398 MachineInstr *CPEMI, unsigned Disp, bool NegOk, 399 bool DoDump = false); 400 bool isWaterInRange(unsigned UserOffset, MachineBasicBlock *Water, 401 CPUser &U, unsigned &Growth); 402 bool isBBInRange(MachineInstr *MI, MachineBasicBlock *BB, unsigned Disp); 403 bool fixupImmediateBr(ImmBranch &Br); 404 bool fixupConditionalBr(ImmBranch &Br); 405 bool fixupUnconditionalBr(ImmBranch &Br); 406 407 void prescanForConstants(); 408 409 private: 410 411 }; 412 413 char MipsConstantIslands::ID = 0; 414 } // end of anonymous namespace 415 416 bool MipsConstantIslands::isOffsetInRange 417 (unsigned UserOffset, unsigned TrialOffset, 418 const CPUser &U) { 419 return isOffsetInRange(UserOffset, TrialOffset, 420 U.getMaxDisp(), U.NegOk); 421 } 422 /// print block size and offset information - debugging 423 void MipsConstantIslands::dumpBBs() { 424 DEBUG({ 425 for (unsigned J = 0, E = BBInfo.size(); J !=E; ++J) { 426 const BasicBlockInfo &BBI = BBInfo[J]; 427 dbgs() << format("%08x BB#%u\t", BBI.Offset, J) 428 << format(" size=%#x\n", BBInfo[J].Size); 429 } 430 }); 431 } 432 /// Returns a pass that converts branches to long branches. 433 FunctionPass *llvm::createMipsConstantIslandPass() { 434 return new MipsConstantIslands(); 435 } 436 437 bool MipsConstantIslands::runOnMachineFunction(MachineFunction &mf) { 438 // The intention is for this to be a mips16 only pass for now 439 // FIXME: 440 MF = &mf; 441 MCP = mf.getConstantPool(); 442 STI = &static_cast<const MipsSubtarget &>(mf.getSubtarget()); 443 DEBUG(dbgs() << "constant island machine function " << "\n"); 444 if (!STI->inMips16Mode() || !MipsSubtarget::useConstantIslands()) { 445 return false; 446 } 447 TII = (const Mips16InstrInfo *)STI->getInstrInfo(); 448 MFI = MF->getInfo<MipsFunctionInfo>(); 449 DEBUG(dbgs() << "constant island processing " << "\n"); 450 // 451 // will need to make predermination if there is any constants we need to 452 // put in constant islands. TBD. 453 // 454 if (!PrescannedForConstants) prescanForConstants(); 455 456 HasFarJump = false; 457 // This pass invalidates liveness information when it splits basic blocks. 458 MF->getRegInfo().invalidateLiveness(); 459 460 // Renumber all of the machine basic blocks in the function, guaranteeing that 461 // the numbers agree with the position of the block in the function. 462 MF->RenumberBlocks(); 463 464 bool MadeChange = false; 465 466 // Perform the initial placement of the constant pool entries. To start with, 467 // we put them all at the end of the function. 468 std::vector<MachineInstr*> CPEMIs; 469 if (!MCP->isEmpty()) 470 doInitialPlacement(CPEMIs); 471 472 /// The next UID to take is the first unused one. 473 initPICLabelUId(CPEMIs.size()); 474 475 // Do the initial scan of the function, building up information about the 476 // sizes of each block, the location of all the water, and finding all of the 477 // constant pool users. 478 initializeFunctionInfo(CPEMIs); 479 CPEMIs.clear(); 480 DEBUG(dumpBBs()); 481 482 /// Remove dead constant pool entries. 483 MadeChange |= removeUnusedCPEntries(); 484 485 // Iteratively place constant pool entries and fix up branches until there 486 // is no change. 487 unsigned NoCPIters = 0, NoBRIters = 0; 488 (void)NoBRIters; 489 while (true) { 490 DEBUG(dbgs() << "Beginning CP iteration #" << NoCPIters << '\n'); 491 bool CPChange = false; 492 for (unsigned i = 0, e = CPUsers.size(); i != e; ++i) 493 CPChange |= handleConstantPoolUser(i); 494 if (CPChange && ++NoCPIters > 30) 495 report_fatal_error("Constant Island pass failed to converge!"); 496 DEBUG(dumpBBs()); 497 498 // Clear NewWaterList now. If we split a block for branches, it should 499 // appear as "new water" for the next iteration of constant pool placement. 500 NewWaterList.clear(); 501 502 DEBUG(dbgs() << "Beginning BR iteration #" << NoBRIters << '\n'); 503 bool BRChange = false; 504 for (unsigned i = 0, e = ImmBranches.size(); i != e; ++i) 505 BRChange |= fixupImmediateBr(ImmBranches[i]); 506 if (BRChange && ++NoBRIters > 30) 507 report_fatal_error("Branch Fix Up pass failed to converge!"); 508 DEBUG(dumpBBs()); 509 if (!CPChange && !BRChange) 510 break; 511 MadeChange = true; 512 } 513 514 DEBUG(dbgs() << '\n'; dumpBBs()); 515 516 BBInfo.clear(); 517 WaterList.clear(); 518 CPUsers.clear(); 519 CPEntries.clear(); 520 ImmBranches.clear(); 521 return MadeChange; 522 } 523 524 /// doInitialPlacement - Perform the initial placement of the constant pool 525 /// entries. To start with, we put them all at the end of the function. 526 void 527 MipsConstantIslands::doInitialPlacement(std::vector<MachineInstr*> &CPEMIs) { 528 // Create the basic block to hold the CPE's. 529 MachineBasicBlock *BB = MF->CreateMachineBasicBlock(); 530 MF->push_back(BB); 531 532 533 // MachineConstantPool measures alignment in bytes. We measure in log2(bytes). 534 unsigned MaxAlign = Log2_32(MCP->getConstantPoolAlignment()); 535 536 // Mark the basic block as required by the const-pool. 537 // If AlignConstantIslands isn't set, use 4-byte alignment for everything. 538 BB->setAlignment(AlignConstantIslands ? MaxAlign : 2); 539 540 // The function needs to be as aligned as the basic blocks. The linker may 541 // move functions around based on their alignment. 542 MF->ensureAlignment(BB->getAlignment()); 543 544 // Order the entries in BB by descending alignment. That ensures correct 545 // alignment of all entries as long as BB is sufficiently aligned. Keep 546 // track of the insertion point for each alignment. We are going to bucket 547 // sort the entries as they are created. 548 SmallVector<MachineBasicBlock::iterator, 8> InsPoint(MaxAlign + 1, BB->end()); 549 550 // Add all of the constants from the constant pool to the end block, use an 551 // identity mapping of CPI's to CPE's. 552 const std::vector<MachineConstantPoolEntry> &CPs = MCP->getConstants(); 553 554 const DataLayout &TD = MF->getDataLayout(); 555 for (unsigned i = 0, e = CPs.size(); i != e; ++i) { 556 unsigned Size = TD.getTypeAllocSize(CPs[i].getType()); 557 assert(Size >= 4 && "Too small constant pool entry"); 558 unsigned Align = CPs[i].getAlignment(); 559 assert(isPowerOf2_32(Align) && "Invalid alignment"); 560 // Verify that all constant pool entries are a multiple of their alignment. 561 // If not, we would have to pad them out so that instructions stay aligned. 562 assert((Size % Align) == 0 && "CP Entry not multiple of 4 bytes!"); 563 564 // Insert CONSTPOOL_ENTRY before entries with a smaller alignment. 565 unsigned LogAlign = Log2_32(Align); 566 MachineBasicBlock::iterator InsAt = InsPoint[LogAlign]; 567 568 MachineInstr *CPEMI = 569 BuildMI(*BB, InsAt, DebugLoc(), TII->get(Mips::CONSTPOOL_ENTRY)) 570 .addImm(i).addConstantPoolIndex(i).addImm(Size); 571 572 CPEMIs.push_back(CPEMI); 573 574 // Ensure that future entries with higher alignment get inserted before 575 // CPEMI. This is bucket sort with iterators. 576 for (unsigned a = LogAlign + 1; a <= MaxAlign; ++a) 577 if (InsPoint[a] == InsAt) 578 InsPoint[a] = CPEMI; 579 // Add a new CPEntry, but no corresponding CPUser yet. 580 CPEntries.emplace_back(1, CPEntry(CPEMI, i)); 581 ++NumCPEs; 582 DEBUG(dbgs() << "Moved CPI#" << i << " to end of function, size = " 583 << Size << ", align = " << Align <<'\n'); 584 } 585 DEBUG(BB->dump()); 586 } 587 588 /// BBHasFallthrough - Return true if the specified basic block can fallthrough 589 /// into the block immediately after it. 590 static bool BBHasFallthrough(MachineBasicBlock *MBB) { 591 // Get the next machine basic block in the function. 592 MachineFunction::iterator MBBI = MBB->getIterator(); 593 // Can't fall off end of function. 594 if (std::next(MBBI) == MBB->getParent()->end()) 595 return false; 596 597 MachineBasicBlock *NextBB = &*std::next(MBBI); 598 for (MachineBasicBlock::succ_iterator I = MBB->succ_begin(), 599 E = MBB->succ_end(); I != E; ++I) 600 if (*I == NextBB) 601 return true; 602 603 return false; 604 } 605 606 /// findConstPoolEntry - Given the constpool index and CONSTPOOL_ENTRY MI, 607 /// look up the corresponding CPEntry. 608 MipsConstantIslands::CPEntry 609 *MipsConstantIslands::findConstPoolEntry(unsigned CPI, 610 const MachineInstr *CPEMI) { 611 std::vector<CPEntry> &CPEs = CPEntries[CPI]; 612 // Number of entries per constpool index should be small, just do a 613 // linear search. 614 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 615 if (CPEs[i].CPEMI == CPEMI) 616 return &CPEs[i]; 617 } 618 return nullptr; 619 } 620 621 /// getCPELogAlign - Returns the required alignment of the constant pool entry 622 /// represented by CPEMI. Alignment is measured in log2(bytes) units. 623 unsigned MipsConstantIslands::getCPELogAlign(const MachineInstr &CPEMI) { 624 assert(CPEMI.getOpcode() == Mips::CONSTPOOL_ENTRY); 625 626 // Everything is 4-byte aligned unless AlignConstantIslands is set. 627 if (!AlignConstantIslands) 628 return 2; 629 630 unsigned CPI = CPEMI.getOperand(1).getIndex(); 631 assert(CPI < MCP->getConstants().size() && "Invalid constant pool index."); 632 unsigned Align = MCP->getConstants()[CPI].getAlignment(); 633 assert(isPowerOf2_32(Align) && "Invalid CPE alignment"); 634 return Log2_32(Align); 635 } 636 637 /// initializeFunctionInfo - Do the initial scan of the function, building up 638 /// information about the sizes of each block, the location of all the water, 639 /// and finding all of the constant pool users. 640 void MipsConstantIslands:: 641 initializeFunctionInfo(const std::vector<MachineInstr*> &CPEMIs) { 642 BBInfo.clear(); 643 BBInfo.resize(MF->getNumBlockIDs()); 644 645 // First thing, compute the size of all basic blocks, and see if the function 646 // has any inline assembly in it. If so, we have to be conservative about 647 // alignment assumptions, as we don't know for sure the size of any 648 // instructions in the inline assembly. 649 for (MachineFunction::iterator I = MF->begin(), E = MF->end(); I != E; ++I) 650 computeBlockSize(&*I); 651 652 653 // Compute block offsets. 654 adjustBBOffsetsAfter(&MF->front()); 655 656 // Now go back through the instructions and build up our data structures. 657 for (MachineBasicBlock &MBB : *MF) { 658 // If this block doesn't fall through into the next MBB, then this is 659 // 'water' that a constant pool island could be placed. 660 if (!BBHasFallthrough(&MBB)) 661 WaterList.push_back(&MBB); 662 for (MachineInstr &MI : MBB) { 663 if (MI.isDebugValue()) 664 continue; 665 666 int Opc = MI.getOpcode(); 667 if (MI.isBranch()) { 668 bool isCond = false; 669 unsigned Bits = 0; 670 unsigned Scale = 1; 671 int UOpc = Opc; 672 switch (Opc) { 673 default: 674 continue; // Ignore other branches for now 675 case Mips::Bimm16: 676 Bits = 11; 677 Scale = 2; 678 isCond = false; 679 break; 680 case Mips::BimmX16: 681 Bits = 16; 682 Scale = 2; 683 isCond = false; 684 break; 685 case Mips::BeqzRxImm16: 686 UOpc=Mips::Bimm16; 687 Bits = 8; 688 Scale = 2; 689 isCond = true; 690 break; 691 case Mips::BeqzRxImmX16: 692 UOpc=Mips::Bimm16; 693 Bits = 16; 694 Scale = 2; 695 isCond = true; 696 break; 697 case Mips::BnezRxImm16: 698 UOpc=Mips::Bimm16; 699 Bits = 8; 700 Scale = 2; 701 isCond = true; 702 break; 703 case Mips::BnezRxImmX16: 704 UOpc=Mips::Bimm16; 705 Bits = 16; 706 Scale = 2; 707 isCond = true; 708 break; 709 case Mips::Bteqz16: 710 UOpc=Mips::Bimm16; 711 Bits = 8; 712 Scale = 2; 713 isCond = true; 714 break; 715 case Mips::BteqzX16: 716 UOpc=Mips::Bimm16; 717 Bits = 16; 718 Scale = 2; 719 isCond = true; 720 break; 721 case Mips::Btnez16: 722 UOpc=Mips::Bimm16; 723 Bits = 8; 724 Scale = 2; 725 isCond = true; 726 break; 727 case Mips::BtnezX16: 728 UOpc=Mips::Bimm16; 729 Bits = 16; 730 Scale = 2; 731 isCond = true; 732 break; 733 } 734 // Record this immediate branch. 735 unsigned MaxOffs = ((1 << (Bits-1))-1) * Scale; 736 ImmBranches.push_back(ImmBranch(&MI, MaxOffs, isCond, UOpc)); 737 } 738 739 if (Opc == Mips::CONSTPOOL_ENTRY) 740 continue; 741 742 743 // Scan the instructions for constant pool operands. 744 for (unsigned op = 0, e = MI.getNumOperands(); op != e; ++op) 745 if (MI.getOperand(op).isCPI()) { 746 747 // We found one. The addressing mode tells us the max displacement 748 // from the PC that this instruction permits. 749 750 // Basic size info comes from the TSFlags field. 751 unsigned Bits = 0; 752 unsigned Scale = 1; 753 bool NegOk = false; 754 unsigned LongFormBits = 0; 755 unsigned LongFormScale = 0; 756 unsigned LongFormOpcode = 0; 757 switch (Opc) { 758 default: 759 llvm_unreachable("Unknown addressing mode for CP reference!"); 760 case Mips::LwRxPcTcp16: 761 Bits = 8; 762 Scale = 4; 763 LongFormOpcode = Mips::LwRxPcTcpX16; 764 LongFormBits = 14; 765 LongFormScale = 1; 766 break; 767 case Mips::LwRxPcTcpX16: 768 Bits = 14; 769 Scale = 1; 770 NegOk = true; 771 break; 772 } 773 // Remember that this is a user of a CP entry. 774 unsigned CPI = MI.getOperand(op).getIndex(); 775 MachineInstr *CPEMI = CPEMIs[CPI]; 776 unsigned MaxOffs = ((1 << Bits)-1) * Scale; 777 unsigned LongFormMaxOffs = ((1 << LongFormBits)-1) * LongFormScale; 778 CPUsers.push_back(CPUser(&MI, CPEMI, MaxOffs, NegOk, LongFormMaxOffs, 779 LongFormOpcode)); 780 781 // Increment corresponding CPEntry reference count. 782 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 783 assert(CPE && "Cannot find a corresponding CPEntry!"); 784 CPE->RefCount++; 785 786 // Instructions can only use one CP entry, don't bother scanning the 787 // rest of the operands. 788 break; 789 790 } 791 792 } 793 } 794 795 } 796 797 /// computeBlockSize - Compute the size and some alignment information for MBB. 798 /// This function updates BBInfo directly. 799 void MipsConstantIslands::computeBlockSize(MachineBasicBlock *MBB) { 800 BasicBlockInfo &BBI = BBInfo[MBB->getNumber()]; 801 BBI.Size = 0; 802 803 for (const MachineInstr &MI : *MBB) 804 BBI.Size += TII->GetInstSizeInBytes(MI); 805 } 806 807 /// getOffsetOf - Return the current offset of the specified machine instruction 808 /// from the start of the function. This offset changes as stuff is moved 809 /// around inside the function. 810 unsigned MipsConstantIslands::getOffsetOf(MachineInstr *MI) const { 811 MachineBasicBlock *MBB = MI->getParent(); 812 813 // The offset is composed of two things: the sum of the sizes of all MBB's 814 // before this instruction's block, and the offset from the start of the block 815 // it is in. 816 unsigned Offset = BBInfo[MBB->getNumber()].Offset; 817 818 // Sum instructions before MI in MBB. 819 for (MachineBasicBlock::iterator I = MBB->begin(); &*I != MI; ++I) { 820 assert(I != MBB->end() && "Didn't find MI in its own basic block?"); 821 Offset += TII->GetInstSizeInBytes(*I); 822 } 823 return Offset; 824 } 825 826 /// CompareMBBNumbers - Little predicate function to sort the WaterList by MBB 827 /// ID. 828 static bool CompareMBBNumbers(const MachineBasicBlock *LHS, 829 const MachineBasicBlock *RHS) { 830 return LHS->getNumber() < RHS->getNumber(); 831 } 832 833 /// updateForInsertedWaterBlock - When a block is newly inserted into the 834 /// machine function, it upsets all of the block numbers. Renumber the blocks 835 /// and update the arrays that parallel this numbering. 836 void MipsConstantIslands::updateForInsertedWaterBlock 837 (MachineBasicBlock *NewBB) { 838 // Renumber the MBB's to keep them consecutive. 839 NewBB->getParent()->RenumberBlocks(NewBB); 840 841 // Insert an entry into BBInfo to align it properly with the (newly 842 // renumbered) block numbers. 843 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo()); 844 845 // Next, update WaterList. Specifically, we need to add NewMBB as having 846 // available water after it. 847 water_iterator IP = 848 std::lower_bound(WaterList.begin(), WaterList.end(), NewBB, 849 CompareMBBNumbers); 850 WaterList.insert(IP, NewBB); 851 } 852 853 unsigned MipsConstantIslands::getUserOffset(CPUser &U) const { 854 return getOffsetOf(U.MI); 855 } 856 857 /// Split the basic block containing MI into two blocks, which are joined by 858 /// an unconditional branch. Update data structures and renumber blocks to 859 /// account for this change and returns the newly created block. 860 MachineBasicBlock * 861 MipsConstantIslands::splitBlockBeforeInstr(MachineInstr &MI) { 862 MachineBasicBlock *OrigBB = MI.getParent(); 863 864 // Create a new MBB for the code after the OrigBB. 865 MachineBasicBlock *NewBB = 866 MF->CreateMachineBasicBlock(OrigBB->getBasicBlock()); 867 MachineFunction::iterator MBBI = ++OrigBB->getIterator(); 868 MF->insert(MBBI, NewBB); 869 870 // Splice the instructions starting with MI over to NewBB. 871 NewBB->splice(NewBB->end(), OrigBB, MI, OrigBB->end()); 872 873 // Add an unconditional branch from OrigBB to NewBB. 874 // Note the new unconditional branch is not being recorded. 875 // There doesn't seem to be meaningful DebugInfo available; this doesn't 876 // correspond to anything in the source. 877 BuildMI(OrigBB, DebugLoc(), TII->get(Mips::Bimm16)).addMBB(NewBB); 878 ++NumSplit; 879 880 // Update the CFG. All succs of OrigBB are now succs of NewBB. 881 NewBB->transferSuccessors(OrigBB); 882 883 // OrigBB branches to NewBB. 884 OrigBB->addSuccessor(NewBB); 885 886 // Update internal data structures to account for the newly inserted MBB. 887 // This is almost the same as updateForInsertedWaterBlock, except that 888 // the Water goes after OrigBB, not NewBB. 889 MF->RenumberBlocks(NewBB); 890 891 // Insert an entry into BBInfo to align it properly with the (newly 892 // renumbered) block numbers. 893 BBInfo.insert(BBInfo.begin() + NewBB->getNumber(), BasicBlockInfo()); 894 895 // Next, update WaterList. Specifically, we need to add OrigMBB as having 896 // available water after it (but not if it's already there, which happens 897 // when splitting before a conditional branch that is followed by an 898 // unconditional branch - in that case we want to insert NewBB). 899 water_iterator IP = 900 std::lower_bound(WaterList.begin(), WaterList.end(), OrigBB, 901 CompareMBBNumbers); 902 MachineBasicBlock* WaterBB = *IP; 903 if (WaterBB == OrigBB) 904 WaterList.insert(std::next(IP), NewBB); 905 else 906 WaterList.insert(IP, OrigBB); 907 NewWaterList.insert(OrigBB); 908 909 // Figure out how large the OrigBB is. As the first half of the original 910 // block, it cannot contain a tablejump. The size includes 911 // the new jump we added. (It should be possible to do this without 912 // recounting everything, but it's very confusing, and this is rarely 913 // executed.) 914 computeBlockSize(OrigBB); 915 916 // Figure out how large the NewMBB is. As the second half of the original 917 // block, it may contain a tablejump. 918 computeBlockSize(NewBB); 919 920 // All BBOffsets following these blocks must be modified. 921 adjustBBOffsetsAfter(OrigBB); 922 923 return NewBB; 924 } 925 926 927 928 /// isOffsetInRange - Checks whether UserOffset (the location of a constant pool 929 /// reference) is within MaxDisp of TrialOffset (a proposed location of a 930 /// constant pool entry). 931 bool MipsConstantIslands::isOffsetInRange(unsigned UserOffset, 932 unsigned TrialOffset, unsigned MaxDisp, 933 bool NegativeOK) { 934 if (UserOffset <= TrialOffset) { 935 // User before the Trial. 936 if (TrialOffset - UserOffset <= MaxDisp) 937 return true; 938 } else if (NegativeOK) { 939 if (UserOffset - TrialOffset <= MaxDisp) 940 return true; 941 } 942 return false; 943 } 944 945 /// isWaterInRange - Returns true if a CPE placed after the specified 946 /// Water (a basic block) will be in range for the specific MI. 947 /// 948 /// Compute how much the function will grow by inserting a CPE after Water. 949 bool MipsConstantIslands::isWaterInRange(unsigned UserOffset, 950 MachineBasicBlock* Water, CPUser &U, 951 unsigned &Growth) { 952 unsigned CPELogAlign = getCPELogAlign(*U.CPEMI); 953 unsigned CPEOffset = BBInfo[Water->getNumber()].postOffset(CPELogAlign); 954 unsigned NextBlockOffset, NextBlockAlignment; 955 MachineFunction::const_iterator NextBlock = ++Water->getIterator(); 956 if (NextBlock == MF->end()) { 957 NextBlockOffset = BBInfo[Water->getNumber()].postOffset(); 958 NextBlockAlignment = 0; 959 } else { 960 NextBlockOffset = BBInfo[NextBlock->getNumber()].Offset; 961 NextBlockAlignment = NextBlock->getAlignment(); 962 } 963 unsigned Size = U.CPEMI->getOperand(2).getImm(); 964 unsigned CPEEnd = CPEOffset + Size; 965 966 // The CPE may be able to hide in the alignment padding before the next 967 // block. It may also cause more padding to be required if it is more aligned 968 // that the next block. 969 if (CPEEnd > NextBlockOffset) { 970 Growth = CPEEnd - NextBlockOffset; 971 // Compute the padding that would go at the end of the CPE to align the next 972 // block. 973 Growth += OffsetToAlignment(CPEEnd, 1ULL << NextBlockAlignment); 974 975 // If the CPE is to be inserted before the instruction, that will raise 976 // the offset of the instruction. Also account for unknown alignment padding 977 // in blocks between CPE and the user. 978 if (CPEOffset < UserOffset) 979 UserOffset += Growth; 980 } else 981 // CPE fits in existing padding. 982 Growth = 0; 983 984 return isOffsetInRange(UserOffset, CPEOffset, U); 985 } 986 987 /// isCPEntryInRange - Returns true if the distance between specific MI and 988 /// specific ConstPool entry instruction can fit in MI's displacement field. 989 bool MipsConstantIslands::isCPEntryInRange 990 (MachineInstr *MI, unsigned UserOffset, 991 MachineInstr *CPEMI, unsigned MaxDisp, 992 bool NegOk, bool DoDump) { 993 unsigned CPEOffset = getOffsetOf(CPEMI); 994 995 if (DoDump) { 996 DEBUG({ 997 unsigned Block = MI->getParent()->getNumber(); 998 const BasicBlockInfo &BBI = BBInfo[Block]; 999 dbgs() << "User of CPE#" << CPEMI->getOperand(0).getImm() 1000 << " max delta=" << MaxDisp 1001 << format(" insn address=%#x", UserOffset) 1002 << " in BB#" << Block << ": " 1003 << format("%#x-%x\t", BBI.Offset, BBI.postOffset()) << *MI 1004 << format("CPE address=%#x offset=%+d: ", CPEOffset, 1005 int(CPEOffset-UserOffset)); 1006 }); 1007 } 1008 1009 return isOffsetInRange(UserOffset, CPEOffset, MaxDisp, NegOk); 1010 } 1011 1012 #ifndef NDEBUG 1013 /// BBIsJumpedOver - Return true of the specified basic block's only predecessor 1014 /// unconditionally branches to its only successor. 1015 static bool BBIsJumpedOver(MachineBasicBlock *MBB) { 1016 if (MBB->pred_size() != 1 || MBB->succ_size() != 1) 1017 return false; 1018 MachineBasicBlock *Succ = *MBB->succ_begin(); 1019 MachineBasicBlock *Pred = *MBB->pred_begin(); 1020 MachineInstr *PredMI = &Pred->back(); 1021 if (PredMI->getOpcode() == Mips::Bimm16) 1022 return PredMI->getOperand(0).getMBB() == Succ; 1023 return false; 1024 } 1025 #endif 1026 1027 void MipsConstantIslands::adjustBBOffsetsAfter(MachineBasicBlock *BB) { 1028 unsigned BBNum = BB->getNumber(); 1029 for(unsigned i = BBNum + 1, e = MF->getNumBlockIDs(); i < e; ++i) { 1030 // Get the offset and known bits at the end of the layout predecessor. 1031 // Include the alignment of the current block. 1032 unsigned Offset = BBInfo[i - 1].Offset + BBInfo[i - 1].Size; 1033 BBInfo[i].Offset = Offset; 1034 } 1035 } 1036 1037 /// decrementCPEReferenceCount - find the constant pool entry with index CPI 1038 /// and instruction CPEMI, and decrement its refcount. If the refcount 1039 /// becomes 0 remove the entry and instruction. Returns true if we removed 1040 /// the entry, false if we didn't. 1041 1042 bool MipsConstantIslands::decrementCPEReferenceCount(unsigned CPI, 1043 MachineInstr *CPEMI) { 1044 // Find the old entry. Eliminate it if it is no longer used. 1045 CPEntry *CPE = findConstPoolEntry(CPI, CPEMI); 1046 assert(CPE && "Unexpected!"); 1047 if (--CPE->RefCount == 0) { 1048 removeDeadCPEMI(CPEMI); 1049 CPE->CPEMI = nullptr; 1050 --NumCPEs; 1051 return true; 1052 } 1053 return false; 1054 } 1055 1056 /// LookForCPEntryInRange - see if the currently referenced CPE is in range; 1057 /// if not, see if an in-range clone of the CPE is in range, and if so, 1058 /// change the data structures so the user references the clone. Returns: 1059 /// 0 = no existing entry found 1060 /// 1 = entry found, and there were no code insertions or deletions 1061 /// 2 = entry found, and there were code insertions or deletions 1062 int MipsConstantIslands::findInRangeCPEntry(CPUser& U, unsigned UserOffset) 1063 { 1064 MachineInstr *UserMI = U.MI; 1065 MachineInstr *CPEMI = U.CPEMI; 1066 1067 // Check to see if the CPE is already in-range. 1068 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, U.getMaxDisp(), U.NegOk, 1069 true)) { 1070 DEBUG(dbgs() << "In range\n"); 1071 return 1; 1072 } 1073 1074 // No. Look for previously created clones of the CPE that are in range. 1075 unsigned CPI = CPEMI->getOperand(1).getIndex(); 1076 std::vector<CPEntry> &CPEs = CPEntries[CPI]; 1077 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 1078 // We already tried this one 1079 if (CPEs[i].CPEMI == CPEMI) 1080 continue; 1081 // Removing CPEs can leave empty entries, skip 1082 if (CPEs[i].CPEMI == nullptr) 1083 continue; 1084 if (isCPEntryInRange(UserMI, UserOffset, CPEs[i].CPEMI, U.getMaxDisp(), 1085 U.NegOk)) { 1086 DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" 1087 << CPEs[i].CPI << "\n"); 1088 // Point the CPUser node to the replacement 1089 U.CPEMI = CPEs[i].CPEMI; 1090 // Change the CPI in the instruction operand to refer to the clone. 1091 for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) 1092 if (UserMI->getOperand(j).isCPI()) { 1093 UserMI->getOperand(j).setIndex(CPEs[i].CPI); 1094 break; 1095 } 1096 // Adjust the refcount of the clone... 1097 CPEs[i].RefCount++; 1098 // ...and the original. If we didn't remove the old entry, none of the 1099 // addresses changed, so we don't need another pass. 1100 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1; 1101 } 1102 } 1103 return 0; 1104 } 1105 1106 /// LookForCPEntryInRange - see if the currently referenced CPE is in range; 1107 /// This version checks if the longer form of the instruction can be used to 1108 /// to satisfy things. 1109 /// if not, see if an in-range clone of the CPE is in range, and if so, 1110 /// change the data structures so the user references the clone. Returns: 1111 /// 0 = no existing entry found 1112 /// 1 = entry found, and there were no code insertions or deletions 1113 /// 2 = entry found, and there were code insertions or deletions 1114 int MipsConstantIslands::findLongFormInRangeCPEntry 1115 (CPUser& U, unsigned UserOffset) 1116 { 1117 MachineInstr *UserMI = U.MI; 1118 MachineInstr *CPEMI = U.CPEMI; 1119 1120 // Check to see if the CPE is already in-range. 1121 if (isCPEntryInRange(UserMI, UserOffset, CPEMI, 1122 U.getLongFormMaxDisp(), U.NegOk, 1123 true)) { 1124 DEBUG(dbgs() << "In range\n"); 1125 UserMI->setDesc(TII->get(U.getLongFormOpcode())); 1126 U.setMaxDisp(U.getLongFormMaxDisp()); 1127 return 2; // instruction is longer length now 1128 } 1129 1130 // No. Look for previously created clones of the CPE that are in range. 1131 unsigned CPI = CPEMI->getOperand(1).getIndex(); 1132 std::vector<CPEntry> &CPEs = CPEntries[CPI]; 1133 for (unsigned i = 0, e = CPEs.size(); i != e; ++i) { 1134 // We already tried this one 1135 if (CPEs[i].CPEMI == CPEMI) 1136 continue; 1137 // Removing CPEs can leave empty entries, skip 1138 if (CPEs[i].CPEMI == nullptr) 1139 continue; 1140 if (isCPEntryInRange(UserMI, UserOffset, CPEs[i].CPEMI, 1141 U.getLongFormMaxDisp(), U.NegOk)) { 1142 DEBUG(dbgs() << "Replacing CPE#" << CPI << " with CPE#" 1143 << CPEs[i].CPI << "\n"); 1144 // Point the CPUser node to the replacement 1145 U.CPEMI = CPEs[i].CPEMI; 1146 // Change the CPI in the instruction operand to refer to the clone. 1147 for (unsigned j = 0, e = UserMI->getNumOperands(); j != e; ++j) 1148 if (UserMI->getOperand(j).isCPI()) { 1149 UserMI->getOperand(j).setIndex(CPEs[i].CPI); 1150 break; 1151 } 1152 // Adjust the refcount of the clone... 1153 CPEs[i].RefCount++; 1154 // ...and the original. If we didn't remove the old entry, none of the 1155 // addresses changed, so we don't need another pass. 1156 return decrementCPEReferenceCount(CPI, CPEMI) ? 2 : 1; 1157 } 1158 } 1159 return 0; 1160 } 1161 1162 /// getUnconditionalBrDisp - Returns the maximum displacement that can fit in 1163 /// the specific unconditional branch instruction. 1164 static inline unsigned getUnconditionalBrDisp(int Opc) { 1165 switch (Opc) { 1166 case Mips::Bimm16: 1167 return ((1<<10)-1)*2; 1168 case Mips::BimmX16: 1169 return ((1<<16)-1)*2; 1170 default: 1171 break; 1172 } 1173 return ((1<<16)-1)*2; 1174 } 1175 1176 /// findAvailableWater - Look for an existing entry in the WaterList in which 1177 /// we can place the CPE referenced from U so it's within range of U's MI. 1178 /// Returns true if found, false if not. If it returns true, WaterIter 1179 /// is set to the WaterList entry. 1180 /// To ensure that this pass 1181 /// terminates, the CPE location for a particular CPUser is only allowed to 1182 /// move to a lower address, so search backward from the end of the list and 1183 /// prefer the first water that is in range. 1184 bool MipsConstantIslands::findAvailableWater(CPUser &U, unsigned UserOffset, 1185 water_iterator &WaterIter) { 1186 if (WaterList.empty()) 1187 return false; 1188 1189 unsigned BestGrowth = ~0u; 1190 for (water_iterator IP = std::prev(WaterList.end()), B = WaterList.begin();; 1191 --IP) { 1192 MachineBasicBlock* WaterBB = *IP; 1193 // Check if water is in range and is either at a lower address than the 1194 // current "high water mark" or a new water block that was created since 1195 // the previous iteration by inserting an unconditional branch. In the 1196 // latter case, we want to allow resetting the high water mark back to 1197 // this new water since we haven't seen it before. Inserting branches 1198 // should be relatively uncommon and when it does happen, we want to be 1199 // sure to take advantage of it for all the CPEs near that block, so that 1200 // we don't insert more branches than necessary. 1201 unsigned Growth; 1202 if (isWaterInRange(UserOffset, WaterBB, U, Growth) && 1203 (WaterBB->getNumber() < U.HighWaterMark->getNumber() || 1204 NewWaterList.count(WaterBB)) && Growth < BestGrowth) { 1205 // This is the least amount of required padding seen so far. 1206 BestGrowth = Growth; 1207 WaterIter = IP; 1208 DEBUG(dbgs() << "Found water after BB#" << WaterBB->getNumber() 1209 << " Growth=" << Growth << '\n'); 1210 1211 // Keep looking unless it is perfect. 1212 if (BestGrowth == 0) 1213 return true; 1214 } 1215 if (IP == B) 1216 break; 1217 } 1218 return BestGrowth != ~0u; 1219 } 1220 1221 /// createNewWater - No existing WaterList entry will work for 1222 /// CPUsers[CPUserIndex], so create a place to put the CPE. The end of the 1223 /// block is used if in range, and the conditional branch munged so control 1224 /// flow is correct. Otherwise the block is split to create a hole with an 1225 /// unconditional branch around it. In either case NewMBB is set to a 1226 /// block following which the new island can be inserted (the WaterList 1227 /// is not adjusted). 1228 void MipsConstantIslands::createNewWater(unsigned CPUserIndex, 1229 unsigned UserOffset, 1230 MachineBasicBlock *&NewMBB) { 1231 CPUser &U = CPUsers[CPUserIndex]; 1232 MachineInstr *UserMI = U.MI; 1233 MachineInstr *CPEMI = U.CPEMI; 1234 unsigned CPELogAlign = getCPELogAlign(*CPEMI); 1235 MachineBasicBlock *UserMBB = UserMI->getParent(); 1236 const BasicBlockInfo &UserBBI = BBInfo[UserMBB->getNumber()]; 1237 1238 // If the block does not end in an unconditional branch already, and if the 1239 // end of the block is within range, make new water there. 1240 if (BBHasFallthrough(UserMBB)) { 1241 // Size of branch to insert. 1242 unsigned Delta = 2; 1243 // Compute the offset where the CPE will begin. 1244 unsigned CPEOffset = UserBBI.postOffset(CPELogAlign) + Delta; 1245 1246 if (isOffsetInRange(UserOffset, CPEOffset, U)) { 1247 DEBUG(dbgs() << "Split at end of BB#" << UserMBB->getNumber() 1248 << format(", expected CPE offset %#x\n", CPEOffset)); 1249 NewMBB = &*++UserMBB->getIterator(); 1250 // Add an unconditional branch from UserMBB to fallthrough block. Record 1251 // it for branch lengthening; this new branch will not get out of range, 1252 // but if the preceding conditional branch is out of range, the targets 1253 // will be exchanged, and the altered branch may be out of range, so the 1254 // machinery has to know about it. 1255 int UncondBr = Mips::Bimm16; 1256 BuildMI(UserMBB, DebugLoc(), TII->get(UncondBr)).addMBB(NewMBB); 1257 unsigned MaxDisp = getUnconditionalBrDisp(UncondBr); 1258 ImmBranches.push_back(ImmBranch(&UserMBB->back(), 1259 MaxDisp, false, UncondBr)); 1260 BBInfo[UserMBB->getNumber()].Size += Delta; 1261 adjustBBOffsetsAfter(UserMBB); 1262 return; 1263 } 1264 } 1265 1266 // What a big block. Find a place within the block to split it. 1267 1268 // Try to split the block so it's fully aligned. Compute the latest split 1269 // point where we can add a 4-byte branch instruction, and then align to 1270 // LogAlign which is the largest possible alignment in the function. 1271 unsigned LogAlign = MF->getAlignment(); 1272 assert(LogAlign >= CPELogAlign && "Over-aligned constant pool entry"); 1273 unsigned BaseInsertOffset = UserOffset + U.getMaxDisp(); 1274 DEBUG(dbgs() << format("Split in middle of big block before %#x", 1275 BaseInsertOffset)); 1276 1277 // The 4 in the following is for the unconditional branch we'll be inserting 1278 // Alignment of the island is handled 1279 // inside isOffsetInRange. 1280 BaseInsertOffset -= 4; 1281 1282 DEBUG(dbgs() << format(", adjusted to %#x", BaseInsertOffset) 1283 << " la=" << LogAlign << '\n'); 1284 1285 // This could point off the end of the block if we've already got constant 1286 // pool entries following this block; only the last one is in the water list. 1287 // Back past any possible branches (allow for a conditional and a maximally 1288 // long unconditional). 1289 if (BaseInsertOffset + 8 >= UserBBI.postOffset()) { 1290 BaseInsertOffset = UserBBI.postOffset() - 8; 1291 DEBUG(dbgs() << format("Move inside block: %#x\n", BaseInsertOffset)); 1292 } 1293 unsigned EndInsertOffset = BaseInsertOffset + 4 + 1294 CPEMI->getOperand(2).getImm(); 1295 MachineBasicBlock::iterator MI = UserMI; 1296 ++MI; 1297 unsigned CPUIndex = CPUserIndex+1; 1298 unsigned NumCPUsers = CPUsers.size(); 1299 //MachineInstr *LastIT = 0; 1300 for (unsigned Offset = UserOffset + TII->GetInstSizeInBytes(*UserMI); 1301 Offset < BaseInsertOffset; 1302 Offset += TII->GetInstSizeInBytes(*MI), MI = std::next(MI)) { 1303 assert(MI != UserMBB->end() && "Fell off end of block"); 1304 if (CPUIndex < NumCPUsers && 1305 CPUsers[CPUIndex].MI == static_cast<MachineInstr *>(MI)) { 1306 CPUser &U = CPUsers[CPUIndex]; 1307 if (!isOffsetInRange(Offset, EndInsertOffset, U)) { 1308 // Shift intertion point by one unit of alignment so it is within reach. 1309 BaseInsertOffset -= 1u << LogAlign; 1310 EndInsertOffset -= 1u << LogAlign; 1311 } 1312 // This is overly conservative, as we don't account for CPEMIs being 1313 // reused within the block, but it doesn't matter much. Also assume CPEs 1314 // are added in order with alignment padding. We may eventually be able 1315 // to pack the aligned CPEs better. 1316 EndInsertOffset += U.CPEMI->getOperand(2).getImm(); 1317 CPUIndex++; 1318 } 1319 } 1320 1321 NewMBB = splitBlockBeforeInstr(*--MI); 1322 } 1323 1324 /// handleConstantPoolUser - Analyze the specified user, checking to see if it 1325 /// is out-of-range. If so, pick up the constant pool value and move it some 1326 /// place in-range. Return true if we changed any addresses (thus must run 1327 /// another pass of branch lengthening), false otherwise. 1328 bool MipsConstantIslands::handleConstantPoolUser(unsigned CPUserIndex) { 1329 CPUser &U = CPUsers[CPUserIndex]; 1330 MachineInstr *UserMI = U.MI; 1331 MachineInstr *CPEMI = U.CPEMI; 1332 unsigned CPI = CPEMI->getOperand(1).getIndex(); 1333 unsigned Size = CPEMI->getOperand(2).getImm(); 1334 // Compute this only once, it's expensive. 1335 unsigned UserOffset = getUserOffset(U); 1336 1337 // See if the current entry is within range, or there is a clone of it 1338 // in range. 1339 int result = findInRangeCPEntry(U, UserOffset); 1340 if (result==1) return false; 1341 else if (result==2) return true; 1342 1343 1344 // Look for water where we can place this CPE. 1345 MachineBasicBlock *NewIsland = MF->CreateMachineBasicBlock(); 1346 MachineBasicBlock *NewMBB; 1347 water_iterator IP; 1348 if (findAvailableWater(U, UserOffset, IP)) { 1349 DEBUG(dbgs() << "Found water in range\n"); 1350 MachineBasicBlock *WaterBB = *IP; 1351 1352 // If the original WaterList entry was "new water" on this iteration, 1353 // propagate that to the new island. This is just keeping NewWaterList 1354 // updated to match the WaterList, which will be updated below. 1355 if (NewWaterList.erase(WaterBB)) 1356 NewWaterList.insert(NewIsland); 1357 1358 // The new CPE goes before the following block (NewMBB). 1359 NewMBB = &*++WaterBB->getIterator(); 1360 } else { 1361 // No water found. 1362 // we first see if a longer form of the instrucion could have reached 1363 // the constant. in that case we won't bother to split 1364 if (!NoLoadRelaxation) { 1365 result = findLongFormInRangeCPEntry(U, UserOffset); 1366 if (result != 0) return true; 1367 } 1368 DEBUG(dbgs() << "No water found\n"); 1369 createNewWater(CPUserIndex, UserOffset, NewMBB); 1370 1371 // splitBlockBeforeInstr adds to WaterList, which is important when it is 1372 // called while handling branches so that the water will be seen on the 1373 // next iteration for constant pools, but in this context, we don't want 1374 // it. Check for this so it will be removed from the WaterList. 1375 // Also remove any entry from NewWaterList. 1376 MachineBasicBlock *WaterBB = &*--NewMBB->getIterator(); 1377 IP = std::find(WaterList.begin(), WaterList.end(), WaterBB); 1378 if (IP != WaterList.end()) 1379 NewWaterList.erase(WaterBB); 1380 1381 // We are adding new water. Update NewWaterList. 1382 NewWaterList.insert(NewIsland); 1383 } 1384 1385 // Remove the original WaterList entry; we want subsequent insertions in 1386 // this vicinity to go after the one we're about to insert. This 1387 // considerably reduces the number of times we have to move the same CPE 1388 // more than once and is also important to ensure the algorithm terminates. 1389 if (IP != WaterList.end()) 1390 WaterList.erase(IP); 1391 1392 // Okay, we know we can put an island before NewMBB now, do it! 1393 MF->insert(NewMBB->getIterator(), NewIsland); 1394 1395 // Update internal data structures to account for the newly inserted MBB. 1396 updateForInsertedWaterBlock(NewIsland); 1397 1398 // Decrement the old entry, and remove it if refcount becomes 0. 1399 decrementCPEReferenceCount(CPI, CPEMI); 1400 1401 // No existing clone of this CPE is within range. 1402 // We will be generating a new clone. Get a UID for it. 1403 unsigned ID = createPICLabelUId(); 1404 1405 // Now that we have an island to add the CPE to, clone the original CPE and 1406 // add it to the island. 1407 U.HighWaterMark = NewIsland; 1408 U.CPEMI = BuildMI(NewIsland, DebugLoc(), TII->get(Mips::CONSTPOOL_ENTRY)) 1409 .addImm(ID).addConstantPoolIndex(CPI).addImm(Size); 1410 CPEntries[CPI].push_back(CPEntry(U.CPEMI, ID, 1)); 1411 ++NumCPEs; 1412 1413 // Mark the basic block as aligned as required by the const-pool entry. 1414 NewIsland->setAlignment(getCPELogAlign(*U.CPEMI)); 1415 1416 // Increase the size of the island block to account for the new entry. 1417 BBInfo[NewIsland->getNumber()].Size += Size; 1418 adjustBBOffsetsAfter(&*--NewIsland->getIterator()); 1419 1420 // Finally, change the CPI in the instruction operand to be ID. 1421 for (unsigned i = 0, e = UserMI->getNumOperands(); i != e; ++i) 1422 if (UserMI->getOperand(i).isCPI()) { 1423 UserMI->getOperand(i).setIndex(ID); 1424 break; 1425 } 1426 1427 DEBUG(dbgs() << " Moved CPE to #" << ID << " CPI=" << CPI 1428 << format(" offset=%#x\n", BBInfo[NewIsland->getNumber()].Offset)); 1429 1430 return true; 1431 } 1432 1433 /// removeDeadCPEMI - Remove a dead constant pool entry instruction. Update 1434 /// sizes and offsets of impacted basic blocks. 1435 void MipsConstantIslands::removeDeadCPEMI(MachineInstr *CPEMI) { 1436 MachineBasicBlock *CPEBB = CPEMI->getParent(); 1437 unsigned Size = CPEMI->getOperand(2).getImm(); 1438 CPEMI->eraseFromParent(); 1439 BBInfo[CPEBB->getNumber()].Size -= Size; 1440 // All succeeding offsets have the current size value added in, fix this. 1441 if (CPEBB->empty()) { 1442 BBInfo[CPEBB->getNumber()].Size = 0; 1443 1444 // This block no longer needs to be aligned. 1445 CPEBB->setAlignment(0); 1446 } else 1447 // Entries are sorted by descending alignment, so realign from the front. 1448 CPEBB->setAlignment(getCPELogAlign(*CPEBB->begin())); 1449 1450 adjustBBOffsetsAfter(CPEBB); 1451 // An island has only one predecessor BB and one successor BB. Check if 1452 // this BB's predecessor jumps directly to this BB's successor. This 1453 // shouldn't happen currently. 1454 assert(!BBIsJumpedOver(CPEBB) && "How did this happen?"); 1455 // FIXME: remove the empty blocks after all the work is done? 1456 } 1457 1458 /// removeUnusedCPEntries - Remove constant pool entries whose refcounts 1459 /// are zero. 1460 bool MipsConstantIslands::removeUnusedCPEntries() { 1461 unsigned MadeChange = false; 1462 for (unsigned i = 0, e = CPEntries.size(); i != e; ++i) { 1463 std::vector<CPEntry> &CPEs = CPEntries[i]; 1464 for (unsigned j = 0, ee = CPEs.size(); j != ee; ++j) { 1465 if (CPEs[j].RefCount == 0 && CPEs[j].CPEMI) { 1466 removeDeadCPEMI(CPEs[j].CPEMI); 1467 CPEs[j].CPEMI = nullptr; 1468 MadeChange = true; 1469 } 1470 } 1471 } 1472 return MadeChange; 1473 } 1474 1475 /// isBBInRange - Returns true if the distance between specific MI and 1476 /// specific BB can fit in MI's displacement field. 1477 bool MipsConstantIslands::isBBInRange 1478 (MachineInstr *MI,MachineBasicBlock *DestBB, unsigned MaxDisp) { 1479 1480 unsigned PCAdj = 4; 1481 1482 unsigned BrOffset = getOffsetOf(MI) + PCAdj; 1483 unsigned DestOffset = BBInfo[DestBB->getNumber()].Offset; 1484 1485 DEBUG(dbgs() << "Branch of destination BB#" << DestBB->getNumber() 1486 << " from BB#" << MI->getParent()->getNumber() 1487 << " max delta=" << MaxDisp 1488 << " from " << getOffsetOf(MI) << " to " << DestOffset 1489 << " offset " << int(DestOffset-BrOffset) << "\t" << *MI); 1490 1491 if (BrOffset <= DestOffset) { 1492 // Branch before the Dest. 1493 if (DestOffset-BrOffset <= MaxDisp) 1494 return true; 1495 } else { 1496 if (BrOffset-DestOffset <= MaxDisp) 1497 return true; 1498 } 1499 return false; 1500 } 1501 1502 /// fixupImmediateBr - Fix up an immediate branch whose destination is too far 1503 /// away to fit in its displacement field. 1504 bool MipsConstantIslands::fixupImmediateBr(ImmBranch &Br) { 1505 MachineInstr *MI = Br.MI; 1506 unsigned TargetOperand = branchTargetOperand(MI); 1507 MachineBasicBlock *DestBB = MI->getOperand(TargetOperand).getMBB(); 1508 1509 // Check to see if the DestBB is already in-range. 1510 if (isBBInRange(MI, DestBB, Br.MaxDisp)) 1511 return false; 1512 1513 if (!Br.isCond) 1514 return fixupUnconditionalBr(Br); 1515 return fixupConditionalBr(Br); 1516 } 1517 1518 /// fixupUnconditionalBr - Fix up an unconditional branch whose destination is 1519 /// too far away to fit in its displacement field. If the LR register has been 1520 /// spilled in the epilogue, then we can use BL to implement a far jump. 1521 /// Otherwise, add an intermediate branch instruction to a branch. 1522 bool 1523 MipsConstantIslands::fixupUnconditionalBr(ImmBranch &Br) { 1524 MachineInstr *MI = Br.MI; 1525 MachineBasicBlock *MBB = MI->getParent(); 1526 MachineBasicBlock *DestBB = MI->getOperand(0).getMBB(); 1527 // Use BL to implement far jump. 1528 unsigned BimmX16MaxDisp = ((1 << 16)-1) * 2; 1529 if (isBBInRange(MI, DestBB, BimmX16MaxDisp)) { 1530 Br.MaxDisp = BimmX16MaxDisp; 1531 MI->setDesc(TII->get(Mips::BimmX16)); 1532 } 1533 else { 1534 // need to give the math a more careful look here 1535 // this is really a segment address and not 1536 // a PC relative address. FIXME. But I think that 1537 // just reducing the bits by 1 as I've done is correct. 1538 // The basic block we are branching too much be longword aligned. 1539 // we know that RA is saved because we always save it right now. 1540 // this requirement will be relaxed later but we also have an alternate 1541 // way to implement this that I will implement that does not need jal. 1542 // We should have a way to back out this alignment restriction if we "can" later. 1543 // but it is not harmful. 1544 // 1545 DestBB->setAlignment(2); 1546 Br.MaxDisp = ((1<<24)-1) * 2; 1547 MI->setDesc(TII->get(Mips::JalB16)); 1548 } 1549 BBInfo[MBB->getNumber()].Size += 2; 1550 adjustBBOffsetsAfter(MBB); 1551 HasFarJump = true; 1552 ++NumUBrFixed; 1553 1554 DEBUG(dbgs() << " Changed B to long jump " << *MI); 1555 1556 return true; 1557 } 1558 1559 1560 /// fixupConditionalBr - Fix up a conditional branch whose destination is too 1561 /// far away to fit in its displacement field. It is converted to an inverse 1562 /// conditional branch + an unconditional branch to the destination. 1563 bool 1564 MipsConstantIslands::fixupConditionalBr(ImmBranch &Br) { 1565 MachineInstr *MI = Br.MI; 1566 unsigned TargetOperand = branchTargetOperand(MI); 1567 MachineBasicBlock *DestBB = MI->getOperand(TargetOperand).getMBB(); 1568 unsigned Opcode = MI->getOpcode(); 1569 unsigned LongFormOpcode = longformBranchOpcode(Opcode); 1570 unsigned LongFormMaxOff = branchMaxOffsets(LongFormOpcode); 1571 1572 // Check to see if the DestBB is already in-range. 1573 if (isBBInRange(MI, DestBB, LongFormMaxOff)) { 1574 Br.MaxDisp = LongFormMaxOff; 1575 MI->setDesc(TII->get(LongFormOpcode)); 1576 return true; 1577 } 1578 1579 // Add an unconditional branch to the destination and invert the branch 1580 // condition to jump over it: 1581 // bteqz L1 1582 // => 1583 // bnez L2 1584 // b L1 1585 // L2: 1586 1587 // If the branch is at the end of its MBB and that has a fall-through block, 1588 // direct the updated conditional branch to the fall-through block. Otherwise, 1589 // split the MBB before the next instruction. 1590 MachineBasicBlock *MBB = MI->getParent(); 1591 MachineInstr *BMI = &MBB->back(); 1592 bool NeedSplit = (BMI != MI) || !BBHasFallthrough(MBB); 1593 unsigned OppositeBranchOpcode = TII->getOppositeBranchOpc(Opcode); 1594 1595 ++NumCBrFixed; 1596 if (BMI != MI) { 1597 if (std::next(MachineBasicBlock::iterator(MI)) == std::prev(MBB->end()) && 1598 BMI->isUnconditionalBranch()) { 1599 // Last MI in the BB is an unconditional branch. Can we simply invert the 1600 // condition and swap destinations: 1601 // beqz L1 1602 // b L2 1603 // => 1604 // bnez L2 1605 // b L1 1606 unsigned BMITargetOperand = branchTargetOperand(BMI); 1607 MachineBasicBlock *NewDest = 1608 BMI->getOperand(BMITargetOperand).getMBB(); 1609 if (isBBInRange(MI, NewDest, Br.MaxDisp)) { 1610 DEBUG(dbgs() << " Invert Bcc condition and swap its destination with " 1611 << *BMI); 1612 MI->setDesc(TII->get(OppositeBranchOpcode)); 1613 BMI->getOperand(BMITargetOperand).setMBB(DestBB); 1614 MI->getOperand(TargetOperand).setMBB(NewDest); 1615 return true; 1616 } 1617 } 1618 } 1619 1620 1621 if (NeedSplit) { 1622 splitBlockBeforeInstr(*MI); 1623 // No need for the branch to the next block. We're adding an unconditional 1624 // branch to the destination. 1625 int delta = TII->GetInstSizeInBytes(MBB->back()); 1626 BBInfo[MBB->getNumber()].Size -= delta; 1627 MBB->back().eraseFromParent(); 1628 // BBInfo[SplitBB].Offset is wrong temporarily, fixed below 1629 } 1630 MachineBasicBlock *NextBB = &*++MBB->getIterator(); 1631 1632 DEBUG(dbgs() << " Insert B to BB#" << DestBB->getNumber() 1633 << " also invert condition and change dest. to BB#" 1634 << NextBB->getNumber() << "\n"); 1635 1636 // Insert a new conditional branch and a new unconditional branch. 1637 // Also update the ImmBranch as well as adding a new entry for the new branch. 1638 if (MI->getNumExplicitOperands() == 2) { 1639 BuildMI(MBB, DebugLoc(), TII->get(OppositeBranchOpcode)) 1640 .addReg(MI->getOperand(0).getReg()) 1641 .addMBB(NextBB); 1642 } else { 1643 BuildMI(MBB, DebugLoc(), TII->get(OppositeBranchOpcode)) 1644 .addMBB(NextBB); 1645 } 1646 Br.MI = &MBB->back(); 1647 BBInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(MBB->back()); 1648 BuildMI(MBB, DebugLoc(), TII->get(Br.UncondBr)).addMBB(DestBB); 1649 BBInfo[MBB->getNumber()].Size += TII->GetInstSizeInBytes(MBB->back()); 1650 unsigned MaxDisp = getUnconditionalBrDisp(Br.UncondBr); 1651 ImmBranches.push_back(ImmBranch(&MBB->back(), MaxDisp, false, Br.UncondBr)); 1652 1653 // Remove the old conditional branch. It may or may not still be in MBB. 1654 BBInfo[MI->getParent()->getNumber()].Size -= TII->GetInstSizeInBytes(*MI); 1655 MI->eraseFromParent(); 1656 adjustBBOffsetsAfter(MBB); 1657 return true; 1658 } 1659 1660 1661 void MipsConstantIslands::prescanForConstants() { 1662 unsigned J = 0; 1663 (void)J; 1664 for (MachineFunction::iterator B = 1665 MF->begin(), E = MF->end(); B != E; ++B) { 1666 for (MachineBasicBlock::instr_iterator I = 1667 B->instr_begin(), EB = B->instr_end(); I != EB; ++I) { 1668 switch(I->getDesc().getOpcode()) { 1669 case Mips::LwConstant32: { 1670 PrescannedForConstants = true; 1671 DEBUG(dbgs() << "constant island constant " << *I << "\n"); 1672 J = I->getNumOperands(); 1673 DEBUG(dbgs() << "num operands " << J << "\n"); 1674 MachineOperand& Literal = I->getOperand(1); 1675 if (Literal.isImm()) { 1676 int64_t V = Literal.getImm(); 1677 DEBUG(dbgs() << "literal " << V << "\n"); 1678 Type *Int32Ty = 1679 Type::getInt32Ty(MF->getFunction()->getContext()); 1680 const Constant *C = ConstantInt::get(Int32Ty, V); 1681 unsigned index = MCP->getConstantPoolIndex(C, 4); 1682 I->getOperand(2).ChangeToImmediate(index); 1683 DEBUG(dbgs() << "constant island constant " << *I << "\n"); 1684 I->setDesc(TII->get(Mips::LwRxPcTcp16)); 1685 I->RemoveOperand(1); 1686 I->RemoveOperand(1); 1687 I->addOperand(MachineOperand::CreateCPI(index, 0)); 1688 I->addOperand(MachineOperand::CreateImm(4)); 1689 } 1690 break; 1691 } 1692 default: 1693 break; 1694 } 1695 } 1696 } 1697 } 1698