lib/CodeGen/RegAllocLinearScan.cpp

   1 //===-- RegAllocLinearScan.cpp - Linear Scan register allocator -----------===//
   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 // This file implements a linear scan register allocator.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "regalloc"
  15 #include "PhysRegTracker.h"
  16 #include "VirtRegMap.h"
  17 #include "Spiller.h"
  18 #include "llvm/Function.h"
  19 #include "llvm/CodeGen/LiveIntervalAnalysis.h"
  20 #include "llvm/CodeGen/LiveStackAnalysis.h"
  21 #include "llvm/CodeGen/MachineFunctionPass.h"
  22 #include "llvm/CodeGen/MachineInstr.h"
  23 #include "llvm/CodeGen/MachineLoopInfo.h"
  24 #include "llvm/CodeGen/MachineRegisterInfo.h"
  25 #include "llvm/CodeGen/Passes.h"
  26 #include "llvm/CodeGen/RegAllocRegistry.h"
  27 #include "llvm/CodeGen/RegisterCoalescer.h"
  28 #include "llvm/Target/TargetRegisterInfo.h"
  29 #include "llvm/Target/TargetMachine.h"
  30 #include "llvm/Target/TargetOptions.h"
  31 #include "llvm/Target/TargetInstrInfo.h"
  32 #include "llvm/ADT/EquivalenceClasses.h"
  33 #include "llvm/ADT/SmallSet.h"
  34 #include "llvm/ADT/Statistic.h"
  35 #include "llvm/ADT/STLExtras.h"
  36 #include "llvm/Support/Debug.h"
  37 #include "llvm/Support/Compiler.h"
  38 #include <algorithm>
  39 #include <set>
  40 #include <queue>
  41 #include <memory>
  42 #include <cmath>
  43 using namespace llvm;
  44
  45 STATISTIC(NumIters     , "Number of iterations performed");
  46 STATISTIC(NumBacktracks, "Number of times we had to backtrack");
  47 STATISTIC(NumCoalesce,   "Number of copies coalesced");
  48
  49 static cl::opt<bool>
  50 NewHeuristic("new-spilling-heuristic",
  51              cl::desc("Use new spilling heuristic"),
  52              cl::init(false), cl::Hidden);
  53
  54 static cl::opt<bool>
  55 PreSplitIntervals("pre-alloc-split",
  56                   cl::desc("Pre-register allocation live interval splitting"),
  57                   cl::init(false), cl::Hidden);
  58
  59 static RegisterRegAlloc
  60 linearscanRegAlloc("linearscan", "linear scan register allocator",
  61                    createLinearScanRegisterAllocator);
  62
  63 namespace {
  64   struct VISIBILITY_HIDDEN RALinScan : public MachineFunctionPass {
  65     static char ID;
  66     RALinScan() : MachineFunctionPass(&ID) {}
  67
  68     typedef std::pair<LiveInterval*, LiveInterval::iterator> IntervalPtr;
  69     typedef SmallVector<IntervalPtr, 32> IntervalPtrs;
  70   private:
  71     /// RelatedRegClasses - This structure is built the first time a function is
  72     /// compiled, and keeps track of which register classes have registers that
  73     /// belong to multiple classes or have aliases that are in other classes.
  74     EquivalenceClasses<const TargetRegisterClass*> RelatedRegClasses;
  75     DenseMap<unsigned, const TargetRegisterClass*> OneClassForEachPhysReg;
  76
  77     MachineFunction* mf_;
  78     MachineRegisterInfo* mri_;
  79     const TargetMachine* tm_;
  80     const TargetRegisterInfo* tri_;
  81     const TargetInstrInfo* tii_;
  82     BitVector allocatableRegs_;
  83     LiveIntervals* li_;
  84     LiveStacks* ls_;
  85     const MachineLoopInfo *loopInfo;
  86
  87     /// handled_ - Intervals are added to the handled_ set in the order of their
  88     /// start value.  This is uses for backtracking.
  89     std::vector<LiveInterval*> handled_;
  90
  91     /// fixed_ - Intervals that correspond to machine registers.
  92     ///
  93     IntervalPtrs fixed_;
  94
  95     /// active_ - Intervals that are currently being processed, and which have a
  96     /// live range active for the current point.
  97     IntervalPtrs active_;
  98
  99     /// inactive_ - Intervals that are currently being processed, but which have
 100     /// a hold at the current point.
 101     IntervalPtrs inactive_;
 102
 103     typedef std::priority_queue<LiveInterval*,
 104                                 SmallVector<LiveInterval*, 64>,
 105                                 greater_ptr<LiveInterval> > IntervalHeap;
 106     IntervalHeap unhandled_;
 107     std::auto_ptr<PhysRegTracker> prt_;
 108     std::auto_ptr<VirtRegMap> vrm_;
 109     std::auto_ptr<Spiller> spiller_;
 110
 111   public:
 112     virtual const char* getPassName() const {
 113       return "Linear Scan Register Allocator";
 114     }
 115
 116     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
 117       AU.addRequired<LiveIntervals>();
 118       if (StrongPHIElim)
 119         AU.addRequiredID(StrongPHIEliminationID);
 120       // Make sure PassManager knows which analyses to make available
 121       // to coalescing and which analyses coalescing invalidates.
 122       AU.addRequiredTransitive<RegisterCoalescer>();
 123       if (PreSplitIntervals)
 124         AU.addRequiredID(PreAllocSplittingID);
 125       AU.addRequired<LiveStacks>();
 126       AU.addPreserved<LiveStacks>();
 127       AU.addRequired<MachineLoopInfo>();
 128       AU.addPreserved<MachineLoopInfo>();
 129       AU.addPreservedID(MachineDominatorsID);
 130       MachineFunctionPass::getAnalysisUsage(AU);
 131     }
 132
 133     /// runOnMachineFunction - register allocate the whole function
 134     bool runOnMachineFunction(MachineFunction&);
 135
 136   private:
 137     /// linearScan - the linear scan algorithm
 138     void linearScan();
 139
 140     /// initIntervalSets - initialize the interval sets.
 141     ///
 142     void initIntervalSets();
 143
 144     /// processActiveIntervals - expire old intervals and move non-overlapping
 145     /// ones to the inactive list.
 146     void processActiveIntervals(unsigned CurPoint);
 147
 148     /// processInactiveIntervals - expire old intervals and move overlapping
 149     /// ones to the active list.
 150     void processInactiveIntervals(unsigned CurPoint);
 151
 152     /// assignRegOrStackSlotAtInterval - assign a register if one
 153     /// is available, or spill.
 154     void assignRegOrStackSlotAtInterval(LiveInterval* cur);
 155
 156     /// findIntervalsToSpill - Determine the intervals to spill for the
 157     /// specified interval. It's passed the physical registers whose spill
 158     /// weight is the lowest among all the registers whose live intervals
 159     /// conflict with the interval.
 160     void findIntervalsToSpill(LiveInterval *cur,
 161                             std::vector<std::pair<unsigned,float> > &Candidates,
 162                             unsigned NumCands,
 163                             SmallVector<LiveInterval*, 8> &SpillIntervals);
 164
 165     /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
 166     /// try allocate the definition the same register as the source register
 167     /// if the register is not defined during live time of the interval. This
 168     /// eliminate a copy. This is used to coalesce copies which were not
 169     /// coalesced away before allocation either due to dest and src being in
 170     /// different register classes or because the coalescer was overly
 171     /// conservative.
 172     unsigned attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg);
 173
 174     ///
 175     /// register handling helpers
 176     ///
 177
 178     /// getFreePhysReg - return a free physical register for this virtual
 179     /// register interval if we have one, otherwise return 0.
 180     unsigned getFreePhysReg(LiveInterval* cur);
 181
 182     /// assignVirt2StackSlot - assigns this virtual register to a
 183     /// stack slot. returns the stack slot
 184     int assignVirt2StackSlot(unsigned virtReg);
 185
 186     void ComputeRelatedRegClasses();
 187
 188     template <typename ItTy>
 189     void printIntervals(const char* const str, ItTy i, ItTy e) const {
 190       if (str) DOUT << str << " intervals:\n";
 191       for (; i != e; ++i) {
 192         DOUT << "\t" << *i->first << " -> ";
 193         unsigned reg = i->first->reg;
 194         if (TargetRegisterInfo::isVirtualRegister(reg)) {
 195           reg = vrm_->getPhys(reg);
 196         }
 197         DOUT << tri_->getName(reg) << '\n';
 198       }
 199     }
 200   };
 201   char RALinScan::ID = 0;
 202 }
 203
 204 static RegisterPass<RALinScan>
 205 X("linearscan-regalloc", "Linear Scan Register Allocator");
 206
 207 void RALinScan::ComputeRelatedRegClasses() {
 208   const TargetRegisterInfo &TRI = *tri_;
 209
 210   // First pass, add all reg classes to the union, and determine at least one
 211   // reg class that each register is in.
 212   bool HasAliases = false;
 213   for (TargetRegisterInfo::regclass_iterator RCI = TRI.regclass_begin(),
 214        E = TRI.regclass_end(); RCI != E; ++RCI) {
 215     RelatedRegClasses.insert(*RCI);
 216     for (TargetRegisterClass::iterator I = (*RCI)->begin(), E = (*RCI)->end();
 217          I != E; ++I) {
 218       HasAliases = HasAliases || *TRI.getAliasSet(*I) != 0;
 219
 220       const TargetRegisterClass *&PRC = OneClassForEachPhysReg[*I];
 221       if (PRC) {
 222         // Already processed this register.  Just make sure we know that
 223         // multiple register classes share a register.
 224         RelatedRegClasses.unionSets(PRC, *RCI);
 225       } else {
 226         PRC = *RCI;
 227       }
 228     }
 229   }
 230
 231   // Second pass, now that we know conservatively what register classes each reg
 232   // belongs to, add info about aliases.  We don't need to do this for targets
 233   // without register aliases.
 234   if (HasAliases)
 235     for (DenseMap<unsigned, const TargetRegisterClass*>::iterator
 236          I = OneClassForEachPhysReg.begin(), E = OneClassForEachPhysReg.end();
 237          I != E; ++I)
 238       for (const unsigned *AS = TRI.getAliasSet(I->first); *AS; ++AS)
 239         RelatedRegClasses.unionSets(I->second, OneClassForEachPhysReg[*AS]);
 240 }
 241
 242 /// attemptTrivialCoalescing - If a simple interval is defined by a copy,
 243 /// try allocate the definition the same register as the source register
 244 /// if the register is not defined during live time of the interval. This
 245 /// eliminate a copy. This is used to coalesce copies which were not
 246 /// coalesced away before allocation either due to dest and src being in
 247 /// different register classes or because the coalescer was overly
 248 /// conservative.
 249 unsigned RALinScan::attemptTrivialCoalescing(LiveInterval &cur, unsigned Reg) {
 250   if ((cur.preference && cur.preference == Reg) || !cur.containsOneValue())
 251     return Reg;
 252
 253   VNInfo *vni = cur.begin()->valno;
 254   if (!vni->def || vni->def == ~1U || vni->def == ~0U)
 255     return Reg;
 256   MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
 257   unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 258   if (!CopyMI ||
 259       !tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg))
 260     return Reg;
 261   if (TargetRegisterInfo::isVirtualRegister(SrcReg)) {
 262     if (!vrm_->isAssignedReg(SrcReg))
 263       return Reg;
 264     else
 265       SrcReg = vrm_->getPhys(SrcReg);
 266   }
 267   if (Reg == SrcReg)
 268     return Reg;
 269
 270   const TargetRegisterClass *RC = mri_->getRegClass(cur.reg);
 271   if (!RC->contains(SrcReg))
 272     return Reg;
 273
 274   // Try to coalesce.
 275   if (!li_->conflictsWithPhysRegDef(cur, *vrm_, SrcReg)) {
 276     DOUT << "Coalescing: " << cur << " -> " << tri_->getName(SrcReg)
 277          << '\n';
 278     vrm_->clearVirt(cur.reg);
 279     vrm_->assignVirt2Phys(cur.reg, SrcReg);
 280     ++NumCoalesce;
 281     return SrcReg;
 282   }
 283
 284   return Reg;
 285 }
 286
 287 bool RALinScan::runOnMachineFunction(MachineFunction &fn) {
 288   mf_ = &fn;
 289   mri_ = &fn.getRegInfo();
 290   tm_ = &fn.getTarget();
 291   tri_ = tm_->getRegisterInfo();
 292   tii_ = tm_->getInstrInfo();
 293   allocatableRegs_ = tri_->getAllocatableSet(fn);
 294   li_ = &getAnalysis<LiveIntervals>();
 295   ls_ = &getAnalysis<LiveStacks>();
 296   loopInfo = &getAnalysis<MachineLoopInfo>();
 297
 298   // We don't run the coalescer here because we have no reason to
 299   // interact with it.  If the coalescer requires interaction, it
 300   // won't do anything.  If it doesn't require interaction, we assume
 301   // it was run as a separate pass.
 302
 303   // If this is the first function compiled, compute the related reg classes.
 304   if (RelatedRegClasses.empty())
 305     ComputeRelatedRegClasses();
 306
 307   if (!prt_.get()) prt_.reset(new PhysRegTracker(*tri_));
 308   vrm_.reset(new VirtRegMap(*mf_));
 309   if (!spiller_.get()) spiller_.reset(createSpiller());
 310
 311   initIntervalSets();
 312
 313   linearScan();
 314
 315   // Rewrite spill code and update the PhysRegsUsed set.
 316   spiller_->runOnMachineFunction(*mf_, *vrm_);
 317   vrm_.reset();  // Free the VirtRegMap
 318
 319   assert(unhandled_.empty() && "Unhandled live intervals remain!");
 320   fixed_.clear();
 321   active_.clear();
 322   inactive_.clear();
 323   handled_.clear();
 324
 325   return true;
 326 }
 327
 328 /// initIntervalSets - initialize the interval sets.
 329 ///
 330 void RALinScan::initIntervalSets()
 331 {
 332   assert(unhandled_.empty() && fixed_.empty() &&
 333          active_.empty() && inactive_.empty() &&
 334          "interval sets should be empty on initialization");
 335
 336   handled_.reserve(li_->getNumIntervals());
 337
 338   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
 339     if (TargetRegisterInfo::isPhysicalRegister(i->second->reg)) {
 340       mri_->setPhysRegUsed(i->second->reg);
 341       fixed_.push_back(std::make_pair(i->second, i->second->begin()));
 342     } else
 343       unhandled_.push(i->second);
 344   }
 345 }
 346
 347 void RALinScan::linearScan()
 348 {
 349   // linear scan algorithm
 350   DOUT << "********** LINEAR SCAN **********\n";
 351   DOUT << "********** Function: " << mf_->getFunction()->getName() << '\n';
 352
 353   DEBUG(printIntervals("fixed", fixed_.begin(), fixed_.end()));
 354
 355   while (!unhandled_.empty()) {
 356     // pick the interval with the earliest start point
 357     LiveInterval* cur = unhandled_.top();
 358     unhandled_.pop();
 359     ++NumIters;
 360     DOUT << "\n*** CURRENT ***: " << *cur << '\n';
 361
 362     if (!cur->empty()) {
 363       processActiveIntervals(cur->beginNumber());
 364       processInactiveIntervals(cur->beginNumber());
 365
 366       assert(TargetRegisterInfo::isVirtualRegister(cur->reg) &&
 367              "Can only allocate virtual registers!");
 368     }
 369
 370     // Allocating a virtual register. try to find a free
 371     // physical register or spill an interval (possibly this one) in order to
 372     // assign it one.
 373     assignRegOrStackSlotAtInterval(cur);
 374
 375     DEBUG(printIntervals("active", active_.begin(), active_.end()));
 376     DEBUG(printIntervals("inactive", inactive_.begin(), inactive_.end()));
 377   }
 378
 379   // expire any remaining active intervals
 380   while (!active_.empty()) {
 381     IntervalPtr &IP = active_.back();
 382     unsigned reg = IP.first->reg;
 383     DOUT << "\tinterval " << *IP.first << " expired\n";
 384     assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 385            "Can only allocate virtual registers!");
 386     reg = vrm_->getPhys(reg);
 387     prt_->delRegUse(reg);
 388     active_.pop_back();
 389   }
 390
 391   // expire any remaining inactive intervals
 392   DEBUG(for (IntervalPtrs::reverse_iterator
 393                i = inactive_.rbegin(); i != inactive_.rend(); ++i)
 394         DOUT << "\tinterval " << *i->first << " expired\n");
 395   inactive_.clear();
 396
 397   // Add live-ins to every BB except for entry. Also perform trivial coalescing.
 398   MachineFunction::iterator EntryMBB = mf_->begin();
 399   SmallVector<MachineBasicBlock*, 8> LiveInMBBs;
 400   for (LiveIntervals::iterator i = li_->begin(), e = li_->end(); i != e; ++i) {
 401     LiveInterval &cur = *i->second;
 402     unsigned Reg = 0;
 403     bool isPhys = TargetRegisterInfo::isPhysicalRegister(cur.reg);
 404     if (isPhys)
 405       Reg = cur.reg;
 406     else if (vrm_->isAssignedReg(cur.reg))
 407       Reg = attemptTrivialCoalescing(cur, vrm_->getPhys(cur.reg));
 408     if (!Reg)
 409       continue;
 410     // Ignore splited live intervals.
 411     if (!isPhys && vrm_->getPreSplitReg(cur.reg))
 412       continue;
 413     for (LiveInterval::Ranges::const_iterator I = cur.begin(), E = cur.end();
 414          I != E; ++I) {
 415       const LiveRange &LR = *I;
 416       if (li_->findLiveInMBBs(LR.start, LR.end, LiveInMBBs)) {
 417         for (unsigned i = 0, e = LiveInMBBs.size(); i != e; ++i)
 418           if (LiveInMBBs[i] != EntryMBB)
 419             LiveInMBBs[i]->addLiveIn(Reg);
 420         LiveInMBBs.clear();
 421       }
 422     }
 423   }
 424
 425   DOUT << *vrm_;
 426 }
 427
 428 /// processActiveIntervals - expire old intervals and move non-overlapping ones
 429 /// to the inactive list.
 430 void RALinScan::processActiveIntervals(unsigned CurPoint)
 431 {
 432   DOUT << "\tprocessing active intervals:\n";
 433
 434   for (unsigned i = 0, e = active_.size(); i != e; ++i) {
 435     LiveInterval *Interval = active_[i].first;
 436     LiveInterval::iterator IntervalPos = active_[i].second;
 437     unsigned reg = Interval->reg;
 438
 439     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 440
 441     if (IntervalPos == Interval->end()) {     // Remove expired intervals.
 442       DOUT << "\t\tinterval " << *Interval << " expired\n";
 443       assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 444              "Can only allocate virtual registers!");
 445       reg = vrm_->getPhys(reg);
 446       prt_->delRegUse(reg);
 447
 448       // Pop off the end of the list.
 449       active_[i] = active_.back();
 450       active_.pop_back();
 451       --i; --e;
 452
 453     } else if (IntervalPos->start > CurPoint) {
 454       // Move inactive intervals to inactive list.
 455       DOUT << "\t\tinterval " << *Interval << " inactive\n";
 456       assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 457              "Can only allocate virtual registers!");
 458       reg = vrm_->getPhys(reg);
 459       prt_->delRegUse(reg);
 460       // add to inactive.
 461       inactive_.push_back(std::make_pair(Interval, IntervalPos));
 462
 463       // Pop off the end of the list.
 464       active_[i] = active_.back();
 465       active_.pop_back();
 466       --i; --e;
 467     } else {
 468       // Otherwise, just update the iterator position.
 469       active_[i].second = IntervalPos;
 470     }
 471   }
 472 }
 473
 474 /// processInactiveIntervals - expire old intervals and move overlapping
 475 /// ones to the active list.
 476 void RALinScan::processInactiveIntervals(unsigned CurPoint)
 477 {
 478   DOUT << "\tprocessing inactive intervals:\n";
 479
 480   for (unsigned i = 0, e = inactive_.size(); i != e; ++i) {
 481     LiveInterval *Interval = inactive_[i].first;
 482     LiveInterval::iterator IntervalPos = inactive_[i].second;
 483     unsigned reg = Interval->reg;
 484
 485     IntervalPos = Interval->advanceTo(IntervalPos, CurPoint);
 486
 487     if (IntervalPos == Interval->end()) {       // remove expired intervals.
 488       DOUT << "\t\tinterval " << *Interval << " expired\n";
 489
 490       // Pop off the end of the list.
 491       inactive_[i] = inactive_.back();
 492       inactive_.pop_back();
 493       --i; --e;
 494     } else if (IntervalPos->start <= CurPoint) {
 495       // move re-activated intervals in active list
 496       DOUT << "\t\tinterval " << *Interval << " active\n";
 497       assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 498              "Can only allocate virtual registers!");
 499       reg = vrm_->getPhys(reg);
 500       prt_->addRegUse(reg);
 501       // add to active
 502       active_.push_back(std::make_pair(Interval, IntervalPos));
 503
 504       // Pop off the end of the list.
 505       inactive_[i] = inactive_.back();
 506       inactive_.pop_back();
 507       --i; --e;
 508     } else {
 509       // Otherwise, just update the iterator position.
 510       inactive_[i].second = IntervalPos;
 511     }
 512   }
 513 }
 514
 515 /// updateSpillWeights - updates the spill weights of the specifed physical
 516 /// register and its weight.
 517 static void updateSpillWeights(std::vector<float> &Weights,
 518                                unsigned reg, float weight,
 519                                const TargetRegisterInfo *TRI) {
 520   Weights[reg] += weight;
 521   for (const unsigned* as = TRI->getAliasSet(reg); *as; ++as)
 522     Weights[*as] += weight;
 523 }
 524
 525 static
 526 RALinScan::IntervalPtrs::iterator
 527 FindIntervalInVector(RALinScan::IntervalPtrs &IP, LiveInterval *LI) {
 528   for (RALinScan::IntervalPtrs::iterator I = IP.begin(), E = IP.end();
 529        I != E; ++I)
 530     if (I->first == LI) return I;
 531   return IP.end();
 532 }
 533
 534 static void RevertVectorIteratorsTo(RALinScan::IntervalPtrs &V, unsigned Point){
 535   for (unsigned i = 0, e = V.size(); i != e; ++i) {
 536     RALinScan::IntervalPtr &IP = V[i];
 537     LiveInterval::iterator I = std::upper_bound(IP.first->begin(),
 538                                                 IP.second, Point);
 539     if (I != IP.first->begin()) --I;
 540     IP.second = I;
 541   }
 542 }
 543
 544 /// addStackInterval - Create a LiveInterval for stack if the specified live
 545 /// interval has been spilled.
 546 static void addStackInterval(LiveInterval *cur, LiveStacks *ls_,
 547                              LiveIntervals *li_, float &Weight,
 548                              VirtRegMap &vrm_) {
 549   int SS = vrm_.getStackSlot(cur->reg);
 550   if (SS == VirtRegMap::NO_STACK_SLOT)
 551     return;
 552   LiveInterval &SI = ls_->getOrCreateInterval(SS);
 553   SI.weight += Weight;
 554
 555   VNInfo *VNI;
 556   if (SI.hasAtLeastOneValue())
 557     VNI = SI.getValNumInfo(0);
 558   else
 559     VNI = SI.getNextValue(~0U, 0, ls_->getVNInfoAllocator());
 560
 561   LiveInterval &RI = li_->getInterval(cur->reg);
 562   // FIXME: This may be overly conservative.
 563   SI.MergeRangesInAsValue(RI, VNI);
 564 }
 565
 566 /// getConflictWeight - Return the number of conflicts between cur
 567 /// live interval and defs and uses of Reg weighted by loop depthes.
 568 static float getConflictWeight(LiveInterval *cur, unsigned Reg,
 569                                   LiveIntervals *li_,
 570                                   MachineRegisterInfo *mri_,
 571                                   const MachineLoopInfo *loopInfo) {
 572   float Conflicts = 0;
 573   for (MachineRegisterInfo::reg_iterator I = mri_->reg_begin(Reg),
 574          E = mri_->reg_end(); I != E; ++I) {
 575     MachineInstr *MI = &*I;
 576     if (cur->liveAt(li_->getInstructionIndex(MI))) {
 577       unsigned loopDepth = loopInfo->getLoopDepth(MI->getParent());
 578       Conflicts += powf(10.0f, (float)loopDepth);
 579     }
 580   }
 581   return Conflicts;
 582 }
 583
 584 /// findIntervalsToSpill - Determine the intervals to spill for the
 585 /// specified interval. It's passed the physical registers whose spill
 586 /// weight is the lowest among all the registers whose live intervals
 587 /// conflict with the interval.
 588 void RALinScan::findIntervalsToSpill(LiveInterval *cur,
 589                             std::vector<std::pair<unsigned,float> > &Candidates,
 590                             unsigned NumCands,
 591                             SmallVector<LiveInterval*, 8> &SpillIntervals) {
 592   // We have figured out the *best* register to spill. But there are other
 593   // registers that are pretty good as well (spill weight within 3%). Spill
 594   // the one that has fewest defs and uses that conflict with cur.
 595   float Conflicts[3] = { 0.0f, 0.0f, 0.0f };
 596   SmallVector<LiveInterval*, 8> SLIs[3];
 597
 598   DOUT << "\tConsidering " << NumCands << " candidates: ";
 599   DEBUG(for (unsigned i = 0; i != NumCands; ++i)
 600           DOUT << tri_->getName(Candidates[i].first) << " ";
 601         DOUT << "\n";);
 602
 603   // Calculate the number of conflicts of each candidate.
 604   for (IntervalPtrs::iterator i = active_.begin(); i != active_.end(); ++i) {
 605     unsigned Reg = i->first->reg;
 606     unsigned PhysReg = vrm_->getPhys(Reg);
 607     if (!cur->overlapsFrom(*i->first, i->second))
 608       continue;
 609     for (unsigned j = 0; j < NumCands; ++j) {
 610       unsigned Candidate = Candidates[j].first;
 611       if (tri_->regsOverlap(PhysReg, Candidate)) {
 612         if (NumCands > 1)
 613           Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
 614         SLIs[j].push_back(i->first);
 615       }
 616     }
 617   }
 618
 619   for (IntervalPtrs::iterator i = inactive_.begin(); i != inactive_.end(); ++i){
 620     unsigned Reg = i->first->reg;
 621     unsigned PhysReg = vrm_->getPhys(Reg);
 622     if (!cur->overlapsFrom(*i->first, i->second-1))
 623       continue;
 624     for (unsigned j = 0; j < NumCands; ++j) {
 625       unsigned Candidate = Candidates[j].first;
 626       if (tri_->regsOverlap(PhysReg, Candidate)) {
 627         if (NumCands > 1)
 628           Conflicts[j] += getConflictWeight(cur, Reg, li_, mri_, loopInfo);
 629         SLIs[j].push_back(i->first);
 630       }
 631     }
 632   }
 633
 634   // Which is the best candidate?
 635   unsigned BestCandidate = 0;
 636   float MinConflicts = Conflicts[0];
 637   for (unsigned i = 1; i != NumCands; ++i) {
 638     if (Conflicts[i] < MinConflicts) {
 639       BestCandidate = i;
 640       MinConflicts = Conflicts[i];
 641     }
 642   }
 643
 644   std::copy(SLIs[BestCandidate].begin(), SLIs[BestCandidate].end(),
 645             std::back_inserter(SpillIntervals));
 646 }
 647
 648 namespace {
 649   struct WeightCompare {
 650     typedef std::pair<unsigned, float> RegWeightPair;
 651     bool operator()(const RegWeightPair &LHS, const RegWeightPair &RHS) const {
 652       return LHS.second < RHS.second;
 653     }
 654   };
 655 }
 656
 657 static bool weightsAreClose(float w1, float w2) {
 658   if (!NewHeuristic)
 659     return false;
 660
 661   float diff = w1 - w2;
 662   if (diff <= 0.02f)  // Within 0.02f
 663     return true;
 664   return (diff / w2) <= 0.05f;  // Within 5%.
 665 }
 666
 667 /// assignRegOrStackSlotAtInterval - assign a register if one is available, or
 668 /// spill.
 669 void RALinScan::assignRegOrStackSlotAtInterval(LiveInterval* cur)
 670 {
 671   DOUT << "\tallocating current interval: ";
 672
 673   // This is an implicitly defined live interval, just assign any register.
 674   const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
 675   if (cur->empty()) {
 676     unsigned physReg = cur->preference;
 677     if (!physReg)
 678       physReg = *RC->allocation_order_begin(*mf_);
 679     DOUT <<  tri_->getName(physReg) << '\n';
 680     // Note the register is not really in use.
 681     vrm_->assignVirt2Phys(cur->reg, physReg);
 682     return;
 683   }
 684
 685   PhysRegTracker backupPrt = *prt_;
 686
 687   std::vector<std::pair<unsigned, float> > SpillWeightsToAdd;
 688   unsigned StartPosition = cur->beginNumber();
 689   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
 690
 691   // If start of this live interval is defined by a move instruction and its
 692   // source is assigned a physical register that is compatible with the target
 693   // register class, then we should try to assign it the same register.
 694   // This can happen when the move is from a larger register class to a smaller
 695   // one, e.g. X86::mov32to32_. These move instructions are not coalescable.
 696   if (!cur->preference && cur->hasAtLeastOneValue()) {
 697     VNInfo *vni = cur->begin()->valno;
 698     if (vni->def && vni->def != ~1U && vni->def != ~0U) {
 699       MachineInstr *CopyMI = li_->getInstructionFromIndex(vni->def);
 700       unsigned SrcReg, DstReg, SrcSubReg, DstSubReg;
 701       if (CopyMI &&
 702           tii_->isMoveInstr(*CopyMI, SrcReg, DstReg, SrcSubReg, DstSubReg)) {
 703         unsigned Reg = 0;
 704         if (TargetRegisterInfo::isPhysicalRegister(SrcReg))
 705           Reg = SrcReg;
 706         else if (vrm_->isAssignedReg(SrcReg))
 707           Reg = vrm_->getPhys(SrcReg);
 708         if (Reg && allocatableRegs_[Reg] && RC->contains(Reg))
 709           cur->preference = Reg;
 710       }
 711     }
 712   }
 713
 714   // for every interval in inactive we overlap with, mark the
 715   // register as not free and update spill weights.
 716   for (IntervalPtrs::const_iterator i = inactive_.begin(),
 717          e = inactive_.end(); i != e; ++i) {
 718     unsigned Reg = i->first->reg;
 719     assert(TargetRegisterInfo::isVirtualRegister(Reg) &&
 720            "Can only allocate virtual registers!");
 721     const TargetRegisterClass *RegRC = mri_->getRegClass(Reg);
 722     // If this is not in a related reg class to the register we're allocating,
 723     // don't check it.
 724     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
 725         cur->overlapsFrom(*i->first, i->second-1)) {
 726       Reg = vrm_->getPhys(Reg);
 727       prt_->addRegUse(Reg);
 728       SpillWeightsToAdd.push_back(std::make_pair(Reg, i->first->weight));
 729     }
 730   }
 731
 732   // Speculatively check to see if we can get a register right now.  If not,
 733   // we know we won't be able to by adding more constraints.  If so, we can
 734   // check to see if it is valid.  Doing an exhaustive search of the fixed_ list
 735   // is very bad (it contains all callee clobbered registers for any functions
 736   // with a call), so we want to avoid doing that if possible.
 737   unsigned physReg = getFreePhysReg(cur);
 738   unsigned BestPhysReg = physReg;
 739   if (physReg) {
 740     // We got a register.  However, if it's in the fixed_ list, we might
 741     // conflict with it.  Check to see if we conflict with it or any of its
 742     // aliases.
 743     SmallSet<unsigned, 8> RegAliases;
 744     for (const unsigned *AS = tri_->getAliasSet(physReg); *AS; ++AS)
 745       RegAliases.insert(*AS);
 746
 747     bool ConflictsWithFixed = false;
 748     for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
 749       IntervalPtr &IP = fixed_[i];
 750       if (physReg == IP.first->reg || RegAliases.count(IP.first->reg)) {
 751         // Okay, this reg is on the fixed list.  Check to see if we actually
 752         // conflict.
 753         LiveInterval *I = IP.first;
 754         if (I->endNumber() > StartPosition) {
 755           LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
 756           IP.second = II;
 757           if (II != I->begin() && II->start > StartPosition)
 758             --II;
 759           if (cur->overlapsFrom(*I, II)) {
 760             ConflictsWithFixed = true;
 761             break;
 762           }
 763         }
 764       }
 765     }
 766
 767     // Okay, the register picked by our speculative getFreePhysReg call turned
 768     // out to be in use.  Actually add all of the conflicting fixed registers to
 769     // prt so we can do an accurate query.
 770     if (ConflictsWithFixed) {
 771       // For every interval in fixed we overlap with, mark the register as not
 772       // free and update spill weights.
 773       for (unsigned i = 0, e = fixed_.size(); i != e; ++i) {
 774         IntervalPtr &IP = fixed_[i];
 775         LiveInterval *I = IP.first;
 776
 777         const TargetRegisterClass *RegRC = OneClassForEachPhysReg[I->reg];
 778         if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader &&
 779             I->endNumber() > StartPosition) {
 780           LiveInterval::iterator II = I->advanceTo(IP.second, StartPosition);
 781           IP.second = II;
 782           if (II != I->begin() && II->start > StartPosition)
 783             --II;
 784           if (cur->overlapsFrom(*I, II)) {
 785             unsigned reg = I->reg;
 786             prt_->addRegUse(reg);
 787             SpillWeightsToAdd.push_back(std::make_pair(reg, I->weight));
 788           }
 789         }
 790       }
 791
 792       // Using the newly updated prt_ object, which includes conflicts in the
 793       // future, see if there are any registers available.
 794       physReg = getFreePhysReg(cur);
 795     }
 796   }
 797
 798   // Restore the physical register tracker, removing information about the
 799   // future.
 800   *prt_ = backupPrt;
 801
 802   // if we find a free register, we are done: assign this virtual to
 803   // the free physical register and add this interval to the active
 804   // list.
 805   if (physReg) {
 806     DOUT <<  tri_->getName(physReg) << '\n';
 807     vrm_->assignVirt2Phys(cur->reg, physReg);
 808     prt_->addRegUse(physReg);
 809     active_.push_back(std::make_pair(cur, cur->begin()));
 810     handled_.push_back(cur);
 811     return;
 812   }
 813   DOUT << "no free registers\n";
 814
 815   // Compile the spill weights into an array that is better for scanning.
 816   std::vector<float> SpillWeights(tri_->getNumRegs(), 0.0f);
 817   for (std::vector<std::pair<unsigned, float> >::iterator
 818        I = SpillWeightsToAdd.begin(), E = SpillWeightsToAdd.end(); I != E; ++I)
 819     updateSpillWeights(SpillWeights, I->first, I->second, tri_);
 820
 821   // for each interval in active, update spill weights.
 822   for (IntervalPtrs::const_iterator i = active_.begin(), e = active_.end();
 823        i != e; ++i) {
 824     unsigned reg = i->first->reg;
 825     assert(TargetRegisterInfo::isVirtualRegister(reg) &&
 826            "Can only allocate virtual registers!");
 827     reg = vrm_->getPhys(reg);
 828     updateSpillWeights(SpillWeights, reg, i->first->weight, tri_);
 829   }
 830
 831   DOUT << "\tassigning stack slot at interval "<< *cur << ":\n";
 832
 833   // Find a register to spill.
 834   float minWeight = HUGE_VALF;
 835   unsigned minReg = 0; /*cur->preference*/;  // Try the preferred register first.
 836
 837   bool Found = false;
 838   std::vector<std::pair<unsigned,float> > RegsWeights;
 839   if (!minReg || SpillWeights[minReg] == HUGE_VALF)
 840     for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
 841            e = RC->allocation_order_end(*mf_); i != e; ++i) {
 842       unsigned reg = *i;
 843       float regWeight = SpillWeights[reg];
 844       if (minWeight > regWeight)
 845         Found = true;
 846       RegsWeights.push_back(std::make_pair(reg, regWeight));
 847     }
 848
 849   // If we didn't find a register that is spillable, try aliases?
 850   if (!Found) {
 851     for (TargetRegisterClass::iterator i = RC->allocation_order_begin(*mf_),
 852            e = RC->allocation_order_end(*mf_); i != e; ++i) {
 853       unsigned reg = *i;
 854       // No need to worry about if the alias register size < regsize of RC.
 855       // We are going to spill all registers that alias it anyway.
 856       for (const unsigned* as = tri_->getAliasSet(reg); *as; ++as)
 857         RegsWeights.push_back(std::make_pair(*as, SpillWeights[*as]));
 858     }
 859   }
 860
 861   // Sort all potential spill candidates by weight.
 862   std::sort(RegsWeights.begin(), RegsWeights.end(), WeightCompare());
 863   minReg = RegsWeights[0].first;
 864   minWeight = RegsWeights[0].second;
 865   if (minWeight == HUGE_VALF) {
 866     // All registers must have inf weight. Just grab one!
 867     minReg = BestPhysReg ? BestPhysReg : *RC->allocation_order_begin(*mf_);
 868     if (cur->weight == HUGE_VALF ||
 869         li_->getApproximateInstructionCount(*cur) == 0) {
 870       // Spill a physical register around defs and uses.
 871       li_->spillPhysRegAroundRegDefsUses(*cur, minReg, *vrm_);
 872       assignRegOrStackSlotAtInterval(cur);
 873       return;
 874     }
 875   }
 876
 877   // Find up to 3 registers to consider as spill candidates.
 878   unsigned LastCandidate = RegsWeights.size() >= 3 ? 3 : 1;
 879   while (LastCandidate > 1) {
 880     if (weightsAreClose(RegsWeights[LastCandidate-1].second, minWeight))
 881       break;
 882     --LastCandidate;
 883   }
 884
 885   DOUT << "\t\tregister(s) with min weight(s): ";
 886   DEBUG(for (unsigned i = 0; i != LastCandidate; ++i)
 887           DOUT << tri_->getName(RegsWeights[i].first)
 888                << " (" << RegsWeights[i].second << ")\n");
 889
 890   // if the current has the minimum weight, we need to spill it and
 891   // add any added intervals back to unhandled, and restart
 892   // linearscan.
 893   if (cur->weight != HUGE_VALF && cur->weight <= minWeight) {
 894     DOUT << "\t\t\tspilling(c): " << *cur << '\n';
 895     float SSWeight;
 896     SmallVector<LiveInterval*, 8> spillIs;
 897     std::vector<LiveInterval*> added =
 898       li_->addIntervalsForSpills(*cur, spillIs, loopInfo, *vrm_, SSWeight);
 899     addStackInterval(cur, ls_, li_, SSWeight, *vrm_);
 900     if (added.empty())
 901       return;  // Early exit if all spills were folded.
 902
 903     // Merge added with unhandled.  Note that we know that
 904     // addIntervalsForSpills returns intervals sorted by their starting
 905     // point.
 906     for (unsigned i = 0, e = added.size(); i != e; ++i)
 907       unhandled_.push(added[i]);
 908     return;
 909   }
 910
 911   ++NumBacktracks;
 912
 913   // push the current interval back to unhandled since we are going
 914   // to re-run at least this iteration. Since we didn't modify it it
 915   // should go back right in the front of the list
 916   unhandled_.push(cur);
 917
 918   assert(TargetRegisterInfo::isPhysicalRegister(minReg) &&
 919          "did not choose a register to spill?");
 920
 921   // We spill all intervals aliasing the register with
 922   // minimum weight, rollback to the interval with the earliest
 923   // start point and let the linear scan algorithm run again
 924   SmallVector<LiveInterval*, 8> spillIs;
 925
 926   // Determine which intervals have to be spilled.
 927   findIntervalsToSpill(cur, RegsWeights, LastCandidate, spillIs);
 928
 929   // Set of spilled vregs (used later to rollback properly)
 930   SmallSet<unsigned, 8> spilled;
 931
 932   // The earliest start of a Spilled interval indicates up to where
 933   // in handled we need to roll back
 934   unsigned earliestStart = cur->beginNumber();
 935
 936   // Spill live intervals of virtual regs mapped to the physical register we
 937   // want to clear (and its aliases).  We only spill those that overlap with the
 938   // current interval as the rest do not affect its allocation. we also keep
 939   // track of the earliest start of all spilled live intervals since this will
 940   // mark our rollback point.
 941   std::vector<LiveInterval*> added;
 942   while (!spillIs.empty()) {
 943     LiveInterval *sli = spillIs.back();
 944     spillIs.pop_back();
 945     DOUT << "\t\t\tspilling(a): " << *sli << '\n';
 946     earliestStart = std::min(earliestStart, sli->beginNumber());
 947     float SSWeight;
 948     std::vector<LiveInterval*> newIs =
 949       li_->addIntervalsForSpills(*sli, spillIs, loopInfo, *vrm_, SSWeight);
 950     addStackInterval(sli, ls_, li_, SSWeight, *vrm_);
 951     std::copy(newIs.begin(), newIs.end(), std::back_inserter(added));
 952     spilled.insert(sli->reg);
 953   }
 954
 955   DOUT << "\t\trolling back to: " << earliestStart << '\n';
 956
 957   // Scan handled in reverse order up to the earliest start of a
 958   // spilled live interval and undo each one, restoring the state of
 959   // unhandled.
 960   while (!handled_.empty()) {
 961     LiveInterval* i = handled_.back();
 962     // If this interval starts before t we are done.
 963     if (i->beginNumber() < earliestStart)
 964       break;
 965     DOUT << "\t\t\tundo changes for: " << *i << '\n';
 966     handled_.pop_back();
 967
 968     // When undoing a live interval allocation we must know if it is active or
 969     // inactive to properly update the PhysRegTracker and the VirtRegMap.
 970     IntervalPtrs::iterator it;
 971     if ((it = FindIntervalInVector(active_, i)) != active_.end()) {
 972       active_.erase(it);
 973       assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
 974       if (!spilled.count(i->reg))
 975         unhandled_.push(i);
 976       prt_->delRegUse(vrm_->getPhys(i->reg));
 977       vrm_->clearVirt(i->reg);
 978     } else if ((it = FindIntervalInVector(inactive_, i)) != inactive_.end()) {
 979       inactive_.erase(it);
 980       assert(!TargetRegisterInfo::isPhysicalRegister(i->reg));
 981       if (!spilled.count(i->reg))
 982         unhandled_.push(i);
 983       vrm_->clearVirt(i->reg);
 984     } else {
 985       assert(TargetRegisterInfo::isVirtualRegister(i->reg) &&
 986              "Can only allocate virtual registers!");
 987       vrm_->clearVirt(i->reg);
 988       unhandled_.push(i);
 989     }
 990
 991     // It interval has a preference, it must be defined by a copy. Clear the
 992     // preference now since the source interval allocation may have been undone
 993     // as well.
 994     i->preference = 0;
 995   }
 996
 997   // Rewind the iterators in the active, inactive, and fixed lists back to the
 998   // point we reverted to.
 999   RevertVectorIteratorsTo(active_, earliestStart);
1000   RevertVectorIteratorsTo(inactive_, earliestStart);
1001   RevertVectorIteratorsTo(fixed_, earliestStart);
1002
1003   // scan the rest and undo each interval that expired after t and
1004   // insert it in active (the next iteration of the algorithm will
1005   // put it in inactive if required)
1006   for (unsigned i = 0, e = handled_.size(); i != e; ++i) {
1007     LiveInterval *HI = handled_[i];
1008     if (!HI->expiredAt(earliestStart) &&
1009         HI->expiredAt(cur->beginNumber())) {
1010       DOUT << "\t\t\tundo changes for: " << *HI << '\n';
1011       active_.push_back(std::make_pair(HI, HI->begin()));
1012       assert(!TargetRegisterInfo::isPhysicalRegister(HI->reg));
1013       prt_->addRegUse(vrm_->getPhys(HI->reg));
1014     }
1015   }
1016
1017   // merge added with unhandled
1018   for (unsigned i = 0, e = added.size(); i != e; ++i)
1019     unhandled_.push(added[i]);
1020 }
1021
1022 /// getFreePhysReg - return a free physical register for this virtual register
1023 /// interval if we have one, otherwise return 0.
1024 unsigned RALinScan::getFreePhysReg(LiveInterval *cur) {
1025   SmallVector<unsigned, 256> inactiveCounts;
1026   unsigned MaxInactiveCount = 0;
1027
1028   const TargetRegisterClass *RC = mri_->getRegClass(cur->reg);
1029   const TargetRegisterClass *RCLeader = RelatedRegClasses.getLeaderValue(RC);
1030
1031   for (IntervalPtrs::iterator i = inactive_.begin(), e = inactive_.end();
1032        i != e; ++i) {
1033     unsigned reg = i->first->reg;
1034     assert(TargetRegisterInfo::isVirtualRegister(reg) &&
1035            "Can only allocate virtual registers!");
1036
1037     // If this is not in a related reg class to the register we're allocating,
1038     // don't check it.
1039     const TargetRegisterClass *RegRC = mri_->getRegClass(reg);
1040     if (RelatedRegClasses.getLeaderValue(RegRC) == RCLeader) {
1041       reg = vrm_->getPhys(reg);
1042       if (inactiveCounts.size() <= reg)
1043         inactiveCounts.resize(reg+1);
1044       ++inactiveCounts[reg];
1045       MaxInactiveCount = std::max(MaxInactiveCount, inactiveCounts[reg]);
1046     }
1047   }
1048
1049   unsigned FreeReg = 0;
1050   unsigned FreeRegInactiveCount = 0;
1051
1052   // If copy coalescer has assigned a "preferred" register, check if it's
1053   // available first.
1054   if (cur->preference) {
1055     if (prt_->isRegAvail(cur->preference) &&
1056         RC->contains(cur->preference)) {
1057       DOUT << "\t\tassigned the preferred register: "
1058            << tri_->getName(cur->preference) << "\n";
1059       return cur->preference;
1060     } else
1061       DOUT << "\t\tunable to assign the preferred register: "
1062            << tri_->getName(cur->preference) << "\n";
1063   }
1064
1065   // Scan for the first available register.
1066   TargetRegisterClass::iterator I = RC->allocation_order_begin(*mf_);
1067   TargetRegisterClass::iterator E = RC->allocation_order_end(*mf_);
1068   assert(I != E && "No allocatable register in this register class!");
1069   for (; I != E; ++I)
1070     if (prt_->isRegAvail(*I)) {
1071       FreeReg = *I;
1072       if (FreeReg < inactiveCounts.size())
1073         FreeRegInactiveCount = inactiveCounts[FreeReg];
1074       else
1075         FreeRegInactiveCount = 0;
1076       break;
1077     }
1078
1079   // If there are no free regs, or if this reg has the max inactive count,
1080   // return this register.
1081   if (FreeReg == 0 || FreeRegInactiveCount == MaxInactiveCount) return FreeReg;
1082
1083   // Continue scanning the registers, looking for the one with the highest
1084   // inactive count.  Alkis found that this reduced register pressure very
1085   // slightly on X86 (in rev 1.94 of this file), though this should probably be
1086   // reevaluated now.
1087   for (; I != E; ++I) {
1088     unsigned Reg = *I;
1089     if (prt_->isRegAvail(Reg) && Reg < inactiveCounts.size() &&
1090         FreeRegInactiveCount < inactiveCounts[Reg]) {
1091       FreeReg = Reg;
1092       FreeRegInactiveCount = inactiveCounts[Reg];
1093       if (FreeRegInactiveCount == MaxInactiveCount)
1094         break;    // We found the one with the max inactive count.
1095     }
1096   }
1097
1098   return FreeReg;
1099 }
1100
1101 FunctionPass* llvm::createLinearScanRegisterAllocator() {
1102   return new RALinScan();
1103 }