ralloc_util.cc revision 089142cf1d0c028b5a7c703baf0b97f4a4ada3f7
1/*
2 * Copyright (C) 2011 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17/* This file contains register alloction support. */
18
19#include "dex/compiler_ir.h"
20#include "dex/compiler_internals.h"
21#include "mir_to_lir-inl.h"
22
23namespace art {
24
25/*
26 * Free all allocated temps in the temp pools.  Note that this does
27 * not affect the "liveness" of a temp register, which will stay
28 * live until it is either explicitly killed or reallocated.
29 */
30void Mir2Lir::ResetRegPool() {
31  GrowableArray<RegisterInfo*>::Iterator iter(&tempreg_info_);
32  for (RegisterInfo* info = iter.Next(); info != NULL; info = iter.Next()) {
33    info->MarkFree();
34  }
35  // Reset temp tracking sanity check.
36  if (kIsDebugBuild) {
37    live_sreg_ = INVALID_SREG;
38  }
39}
40
41Mir2Lir::RegisterInfo::RegisterInfo(RegStorage r, uint64_t mask)
42  : reg_(r), is_temp_(false), wide_value_(false), dirty_(false), aliased_(false), partner_(r),
43    s_reg_(INVALID_SREG), def_use_mask_(mask), master_(this), def_start_(nullptr),
44    def_end_(nullptr), alias_chain_(nullptr) {
45  switch (r.StorageSize()) {
46    case 0: storage_mask_ = 0xffffffff; break;
47    case 4: storage_mask_ = 0x00000001; break;
48    case 8: storage_mask_ = 0x00000003; break;
49    case 16: storage_mask_ = 0x0000000f; break;
50    case 32: storage_mask_ = 0x000000ff; break;
51    case 64: storage_mask_ = 0x0000ffff; break;
52    case 128: storage_mask_ = 0xffffffff; break;
53  }
54  used_storage_ = r.Valid() ? ~storage_mask_ : storage_mask_;
55  liveness_ = used_storage_;
56}
57
58Mir2Lir::RegisterPool::RegisterPool(Mir2Lir* m2l, ArenaAllocator* arena,
59                                    const ArrayRef<const RegStorage>& core_regs,
60                                    const ArrayRef<const RegStorage>& core64_regs,
61                                    const ArrayRef<const RegStorage>& sp_regs,
62                                    const ArrayRef<const RegStorage>& dp_regs,
63                                    const ArrayRef<const RegStorage>& reserved_regs,
64                                    const ArrayRef<const RegStorage>& reserved64_regs,
65                                    const ArrayRef<const RegStorage>& core_temps,
66                                    const ArrayRef<const RegStorage>& core64_temps,
67                                    const ArrayRef<const RegStorage>& sp_temps,
68                                    const ArrayRef<const RegStorage>& dp_temps) :
69    core_regs_(arena, core_regs.size()), next_core_reg_(0),
70    core64_regs_(arena, core64_regs.size()), next_core64_reg_(0),
71    sp_regs_(arena, sp_regs.size()), next_sp_reg_(0),
72    dp_regs_(arena, dp_regs.size()), next_dp_reg_(0), m2l_(m2l)  {
73  // Initialize the fast lookup map.
74  m2l_->reginfo_map_.Reset();
75  if (kIsDebugBuild) {
76    m2l_->reginfo_map_.Resize(RegStorage::kMaxRegs);
77    for (unsigned i = 0; i < RegStorage::kMaxRegs; i++) {
78      m2l_->reginfo_map_.Insert(nullptr);
79    }
80  } else {
81    m2l_->reginfo_map_.SetSize(RegStorage::kMaxRegs);
82  }
83
84  // Construct the register pool.
85  for (RegStorage reg : core_regs) {
86    RegisterInfo* info = new (arena) RegisterInfo(reg, m2l_->GetRegMaskCommon(reg));
87    m2l_->reginfo_map_.Put(reg.GetReg(), info);
88    core_regs_.Insert(info);
89  }
90  for (RegStorage reg : core64_regs) {
91    RegisterInfo* info = new (arena) RegisterInfo(reg, m2l_->GetRegMaskCommon(reg));
92    m2l_->reginfo_map_.Put(reg.GetReg(), info);
93    core64_regs_.Insert(info);
94  }
95  for (RegStorage reg : sp_regs) {
96    RegisterInfo* info = new (arena) RegisterInfo(reg, m2l_->GetRegMaskCommon(reg));
97    m2l_->reginfo_map_.Put(reg.GetReg(), info);
98    sp_regs_.Insert(info);
99  }
100  for (RegStorage reg : dp_regs) {
101    RegisterInfo* info = new (arena) RegisterInfo(reg, m2l_->GetRegMaskCommon(reg));
102    m2l_->reginfo_map_.Put(reg.GetReg(), info);
103    dp_regs_.Insert(info);
104  }
105
106  // Keep special registers from being allocated.
107  for (RegStorage reg : reserved_regs) {
108    m2l_->MarkInUse(reg);
109  }
110  for (RegStorage reg : reserved64_regs) {
111    m2l_->MarkInUse(reg);
112  }
113
114  // Mark temp regs - all others not in use can be used for promotion
115  for (RegStorage reg : core_temps) {
116    m2l_->MarkTemp(reg);
117  }
118  for (RegStorage reg : core64_temps) {
119    m2l_->MarkTemp(reg);
120  }
121  for (RegStorage reg : sp_temps) {
122    m2l_->MarkTemp(reg);
123  }
124  for (RegStorage reg : dp_temps) {
125    m2l_->MarkTemp(reg);
126  }
127
128  // Add an entry for InvalidReg with zero'd mask.
129  RegisterInfo* invalid_reg = new (arena) RegisterInfo(RegStorage::InvalidReg(), 0);
130  m2l_->reginfo_map_.Put(RegStorage::InvalidReg().GetReg(), invalid_reg);
131
132  // Existence of core64 registers implies wide references.
133  if (core64_regs_.Size() != 0) {
134    ref_regs_ = &core64_regs_;
135    next_ref_reg_ = &next_core64_reg_;
136  } else {
137    ref_regs_ = &core_regs_;
138    next_ref_reg_ = &next_core_reg_;
139  }
140}
141
142void Mir2Lir::DumpRegPool(GrowableArray<RegisterInfo*>* regs) {
143  LOG(INFO) << "================================================";
144  GrowableArray<RegisterInfo*>::Iterator it(regs);
145  for (RegisterInfo* info = it.Next(); info != nullptr; info = it.Next()) {
146    LOG(INFO) << StringPrintf(
147        "R[%d:%d:%c]: T:%d, U:%d, W:%d, p:%d, LV:%d, D:%d, SR:%d, DEF:%d",
148        info->GetReg().GetReg(), info->GetReg().GetRegNum(), info->GetReg().IsFloat() ?  'f' : 'c',
149        info->IsTemp(), info->InUse(), info->IsWide(), info->Partner().GetReg(), info->IsLive(),
150        info->IsDirty(), info->SReg(), info->DefStart() != nullptr);
151  }
152  LOG(INFO) << "================================================";
153}
154
155void Mir2Lir::DumpCoreRegPool() {
156  DumpRegPool(&reg_pool_->core_regs_);
157  DumpRegPool(&reg_pool_->core64_regs_);
158}
159
160void Mir2Lir::DumpFpRegPool() {
161  DumpRegPool(&reg_pool_->sp_regs_);
162  DumpRegPool(&reg_pool_->dp_regs_);
163}
164
165void Mir2Lir::DumpRegPools() {
166  LOG(INFO) << "Core registers";
167  DumpCoreRegPool();
168  LOG(INFO) << "FP registers";
169  DumpFpRegPool();
170}
171
172void Mir2Lir::Clobber(RegStorage reg) {
173  if (UNLIKELY(reg.IsPair())) {
174    DCHECK(!GetRegInfo(reg.GetLow())->IsAliased());
175    Clobber(reg.GetLow());
176    DCHECK(!GetRegInfo(reg.GetHigh())->IsAliased());
177    Clobber(reg.GetHigh());
178  } else {
179    RegisterInfo* info = GetRegInfo(reg);
180    if (info->IsTemp() && !info->IsDead()) {
181      if (info->GetReg() != info->Partner()) {
182        ClobberBody(GetRegInfo(info->Partner()));
183      }
184      ClobberBody(info);
185      if (info->IsAliased()) {
186        ClobberAliases(info, info->StorageMask());
187      } else {
188        RegisterInfo* master = info->Master();
189        if (info != master) {
190          ClobberBody(info->Master());
191          ClobberAliases(info->Master(), info->StorageMask());
192        }
193      }
194    }
195  }
196}
197
198void Mir2Lir::ClobberAliases(RegisterInfo* info, uint32_t clobber_mask) {
199  for (RegisterInfo* alias = info->GetAliasChain(); alias != nullptr;
200       alias = alias->GetAliasChain()) {
201    DCHECK(!alias->IsAliased());  // Only the master should be marked as alised.
202    // Only clobber if we have overlap.
203    if ((alias->StorageMask() & clobber_mask) != 0) {
204      ClobberBody(alias);
205    }
206  }
207}
208
209/*
210 * Break the association between a Dalvik vreg and a physical temp register of either register
211 * class.
212 * TODO: Ideally, the public version of this code should not exist.  Besides its local usage
213 * in the register utilities, is is also used by code gen routines to work around a deficiency in
214 * local register allocation, which fails to distinguish between the "in" and "out" identities
215 * of Dalvik vregs.  This can result in useless register copies when the same Dalvik vreg
216 * is used both as the source and destination register of an operation in which the type
217 * changes (for example: INT_TO_FLOAT v1, v1).  Revisit when improved register allocation is
218 * addressed.
219 */
220void Mir2Lir::ClobberSReg(int s_reg) {
221  if (s_reg != INVALID_SREG) {
222    if (kIsDebugBuild && s_reg == live_sreg_) {
223      live_sreg_ = INVALID_SREG;
224    }
225    GrowableArray<RegisterInfo*>::Iterator iter(&tempreg_info_);
226    for (RegisterInfo* info = iter.Next(); info != NULL; info = iter.Next()) {
227      if (info->SReg() == s_reg) {
228        if (info->GetReg() != info->Partner()) {
229          // Dealing with a pair - clobber the other half.
230          DCHECK(!info->IsAliased());
231          ClobberBody(GetRegInfo(info->Partner()));
232        }
233        ClobberBody(info);
234        if (info->IsAliased()) {
235          ClobberAliases(info, info->StorageMask());
236        }
237      }
238    }
239  }
240}
241
242/*
243 * SSA names associated with the initial definitions of Dalvik
244 * registers are the same as the Dalvik register number (and
245 * thus take the same position in the promotion_map.  However,
246 * the special Method* and compiler temp resisters use negative
247 * v_reg numbers to distinguish them and can have an arbitrary
248 * ssa name (above the last original Dalvik register).  This function
249 * maps SSA names to positions in the promotion_map array.
250 */
251int Mir2Lir::SRegToPMap(int s_reg) {
252  DCHECK_LT(s_reg, mir_graph_->GetNumSSARegs());
253  DCHECK_GE(s_reg, 0);
254  int v_reg = mir_graph_->SRegToVReg(s_reg);
255  if (v_reg >= 0) {
256    DCHECK_LT(v_reg, cu_->num_dalvik_registers);
257    return v_reg;
258  } else {
259    /*
260     * It must be the case that the v_reg for temporary is less than or equal to the
261     * base reg for temps. For that reason, "position" must be zero or positive.
262     */
263    unsigned int position = std::abs(v_reg) - std::abs(static_cast<int>(kVRegTempBaseReg));
264
265    // The temporaries are placed after dalvik registers in the promotion map
266    DCHECK_LT(position, mir_graph_->GetNumUsedCompilerTemps());
267    return cu_->num_dalvik_registers + position;
268  }
269}
270
271// TODO: refactor following Alloc/Record routines - much commonality.
272void Mir2Lir::RecordCorePromotion(RegStorage reg, int s_reg) {
273  int p_map_idx = SRegToPMap(s_reg);
274  int v_reg = mir_graph_->SRegToVReg(s_reg);
275  int reg_num = reg.GetRegNum();
276  GetRegInfo(reg)->MarkInUse();
277  core_spill_mask_ |= (1 << reg_num);
278  // Include reg for later sort
279  core_vmap_table_.push_back(reg_num << VREG_NUM_WIDTH | (v_reg & ((1 << VREG_NUM_WIDTH) - 1)));
280  num_core_spills_++;
281  promotion_map_[p_map_idx].core_location = kLocPhysReg;
282  promotion_map_[p_map_idx].core_reg = reg_num;
283}
284
285/* Reserve a callee-save register.  Return InvalidReg if none available */
286RegStorage Mir2Lir::AllocPreservedCoreReg(int s_reg) {
287  // TODO: 64-bit and refreg update
288  RegStorage res;
289  GrowableArray<RegisterInfo*>::Iterator it(&reg_pool_->core_regs_);
290  for (RegisterInfo* info = it.Next(); info != nullptr; info = it.Next()) {
291    if (!info->IsTemp() && !info->InUse()) {
292      res = info->GetReg();
293      RecordCorePromotion(res, s_reg);
294      break;
295    }
296  }
297  return res;
298}
299
300void Mir2Lir::RecordSinglePromotion(RegStorage reg, int s_reg) {
301  int p_map_idx = SRegToPMap(s_reg);
302  int v_reg = mir_graph_->SRegToVReg(s_reg);
303  GetRegInfo(reg)->MarkInUse();
304  MarkPreservedSingle(v_reg, reg);
305  promotion_map_[p_map_idx].fp_location = kLocPhysReg;
306  promotion_map_[p_map_idx].FpReg = reg.GetReg();
307}
308
309// Reserve a callee-save sp single register.
310RegStorage Mir2Lir::AllocPreservedSingle(int s_reg) {
311  RegStorage res;
312  GrowableArray<RegisterInfo*>::Iterator it(&reg_pool_->sp_regs_);
313  for (RegisterInfo* info = it.Next(); info != nullptr; info = it.Next()) {
314    if (!info->IsTemp() && !info->InUse()) {
315      res = info->GetReg();
316      RecordSinglePromotion(res, s_reg);
317      break;
318    }
319  }
320  return res;
321}
322
323void Mir2Lir::RecordDoublePromotion(RegStorage reg, int s_reg) {
324  int p_map_idx = SRegToPMap(s_reg);
325  int v_reg = mir_graph_->SRegToVReg(s_reg);
326  GetRegInfo(reg)->MarkInUse();
327  MarkPreservedDouble(v_reg, reg);
328  promotion_map_[p_map_idx].fp_location = kLocPhysReg;
329  promotion_map_[p_map_idx].FpReg = reg.GetReg();
330}
331
332// Reserve a callee-save dp solo register.
333RegStorage Mir2Lir::AllocPreservedDouble(int s_reg) {
334  RegStorage res;
335  GrowableArray<RegisterInfo*>::Iterator it(&reg_pool_->dp_regs_);
336  for (RegisterInfo* info = it.Next(); info != nullptr; info = it.Next()) {
337    if (!info->IsTemp() && !info->InUse()) {
338      res = info->GetReg();
339      RecordDoublePromotion(res, s_reg);
340      break;
341    }
342  }
343  return res;
344}
345
346
347RegStorage Mir2Lir::AllocTempBody(GrowableArray<RegisterInfo*> &regs, int* next_temp, bool required) {
348  int num_regs = regs.Size();
349  int next = *next_temp;
350  for (int i = 0; i< num_regs; i++) {
351    if (next >= num_regs)
352      next = 0;
353    RegisterInfo* info = regs.Get(next);
354    // Try to allocate a register that doesn't hold a live value.
355    if (info->IsTemp() && !info->InUse() && info->IsDead()) {
356      Clobber(info->GetReg());
357      info->MarkInUse();
358      /*
359       * NOTE: "wideness" is an attribute of how the container is used, not its physical size.
360       * The caller will set wideness as appropriate.
361       */
362      info->SetIsWide(false);
363      *next_temp = next + 1;
364      return info->GetReg();
365    }
366    next++;
367  }
368  next = *next_temp;
369  // No free non-live regs.  Anything we can kill?
370  for (int i = 0; i< num_regs; i++) {
371    if (next >= num_regs)
372      next = 0;
373    RegisterInfo* info = regs.Get(next);
374    if (info->IsTemp() && !info->InUse()) {
375      // Got one.  Kill it.
376      ClobberSReg(info->SReg());
377      Clobber(info->GetReg());
378      info->MarkInUse();
379      if (info->IsWide()) {
380        RegisterInfo* partner = GetRegInfo(info->Partner());
381        DCHECK_EQ(info->GetReg().GetRegNum(), partner->Partner().GetRegNum());
382        DCHECK(partner->IsWide());
383        info->SetIsWide(false);
384        partner->SetIsWide(false);
385      }
386      *next_temp = next + 1;
387      return info->GetReg();
388    }
389    next++;
390  }
391  if (required) {
392    CodegenDump();
393    DumpRegPools();
394    LOG(FATAL) << "No free temp registers";
395  }
396  return RegStorage::InvalidReg();  // No register available
397}
398
399/* Return a temp if one is available, -1 otherwise */
400RegStorage Mir2Lir::AllocFreeTemp() {
401  return AllocTempBody(reg_pool_->core_regs_, &reg_pool_->next_core_reg_, false);
402}
403
404RegStorage Mir2Lir::AllocTemp() {
405  return AllocTempBody(reg_pool_->core_regs_, &reg_pool_->next_core_reg_, true);
406}
407
408RegStorage Mir2Lir::AllocTempWide() {
409  RegStorage res;
410  if (reg_pool_->core64_regs_.Size() != 0) {
411    res = AllocTempBody(reg_pool_->core64_regs_, &reg_pool_->next_core64_reg_, true);
412  } else {
413    RegStorage low_reg = AllocTemp();
414    RegStorage high_reg = AllocTemp();
415    res = RegStorage::MakeRegPair(low_reg, high_reg);
416  }
417  return res;
418}
419
420RegStorage Mir2Lir::AllocTempRef() {
421  RegStorage res = AllocTempBody(*reg_pool_->ref_regs_, reg_pool_->next_ref_reg_, true);
422  DCHECK(!res.IsPair());
423  return res;
424}
425
426RegStorage Mir2Lir::AllocTempSingle() {
427  RegStorage res = AllocTempBody(reg_pool_->sp_regs_, &reg_pool_->next_sp_reg_, true);
428  DCHECK(res.IsSingle()) << "Reg: 0x" << std::hex << res.GetRawBits();
429  return res;
430}
431
432RegStorage Mir2Lir::AllocTempDouble() {
433  RegStorage res = AllocTempBody(reg_pool_->dp_regs_, &reg_pool_->next_dp_reg_, true);
434  DCHECK(res.IsDouble()) << "Reg: 0x" << std::hex << res.GetRawBits();
435  return res;
436}
437
438RegStorage Mir2Lir::AllocTypedTempWide(bool fp_hint, int reg_class) {
439  DCHECK_NE(reg_class, kRefReg);  // NOTE: the Dalvik width of a reference is always 32 bits.
440  if (((reg_class == kAnyReg) && fp_hint) || (reg_class == kFPReg)) {
441    return AllocTempDouble();
442  }
443  return AllocTempWide();
444}
445
446RegStorage Mir2Lir::AllocTypedTemp(bool fp_hint, int reg_class) {
447  if (((reg_class == kAnyReg) && fp_hint) || (reg_class == kFPReg)) {
448    return AllocTempSingle();
449  } else if (reg_class == kRefReg) {
450    return AllocTempRef();
451  }
452  return AllocTemp();
453}
454
455RegStorage Mir2Lir::FindLiveReg(GrowableArray<RegisterInfo*> &regs, int s_reg) {
456  RegStorage res;
457  GrowableArray<RegisterInfo*>::Iterator it(&regs);
458  for (RegisterInfo* info = it.Next(); info != nullptr; info = it.Next()) {
459    if ((info->SReg() == s_reg) && info->IsLive()) {
460      res = info->GetReg();
461      break;
462    }
463  }
464  return res;
465}
466
467RegStorage Mir2Lir::AllocLiveReg(int s_reg, int reg_class, bool wide) {
468  RegStorage reg;
469  if (reg_class == kRefReg) {
470    reg = FindLiveReg(*reg_pool_->ref_regs_, s_reg);
471  }
472  if (!reg.Valid() && ((reg_class == kAnyReg) || (reg_class == kFPReg))) {
473    reg = FindLiveReg(wide ? reg_pool_->dp_regs_ : reg_pool_->sp_regs_, s_reg);
474  }
475  if (!reg.Valid() && (reg_class != kFPReg)) {
476    if (Is64BitInstructionSet(cu_->instruction_set)) {
477      reg = FindLiveReg(wide ? reg_pool_->core64_regs_ : reg_pool_->core_regs_, s_reg);
478    } else {
479      reg = FindLiveReg(reg_pool_->core_regs_, s_reg);
480    }
481  }
482  if (reg.Valid()) {
483    if (wide && !reg.IsFloat() && !Is64BitInstructionSet(cu_->instruction_set)) {
484      // Only allow reg pairs for core regs on 32-bit targets.
485      RegStorage high_reg = FindLiveReg(reg_pool_->core_regs_, s_reg + 1);
486      if (high_reg.Valid()) {
487        reg = RegStorage::MakeRegPair(reg, high_reg);
488        MarkWide(reg);
489      } else {
490        // Only half available.
491        reg = RegStorage::InvalidReg();
492      }
493    }
494    if (reg.Valid() && (wide != GetRegInfo(reg)->IsWide())) {
495      // Width mismatch - don't try to reuse.
496      reg = RegStorage::InvalidReg();
497    }
498  }
499  if (reg.Valid()) {
500    if (reg.IsPair()) {
501      RegisterInfo* info_low = GetRegInfo(reg.GetLow());
502      RegisterInfo* info_high = GetRegInfo(reg.GetHigh());
503      if (info_low->IsTemp()) {
504        info_low->MarkInUse();
505      }
506      if (info_high->IsTemp()) {
507        info_high->MarkInUse();
508      }
509    } else {
510      RegisterInfo* info = GetRegInfo(reg);
511      if (info->IsTemp()) {
512        info->MarkInUse();
513      }
514    }
515  } else {
516    // Either not found, or something didn't match up. Clobber to prevent any stale instances.
517    ClobberSReg(s_reg);
518    if (wide) {
519      ClobberSReg(s_reg + 1);
520    }
521  }
522  return reg;
523}
524
525void Mir2Lir::FreeTemp(RegStorage reg) {
526  if (reg.IsPair()) {
527    FreeTemp(reg.GetLow());
528    FreeTemp(reg.GetHigh());
529  } else {
530    RegisterInfo* p = GetRegInfo(reg);
531    if (p->IsTemp()) {
532      p->MarkFree();
533      p->SetIsWide(false);
534      p->SetPartner(reg);
535    }
536  }
537}
538
539void Mir2Lir::FreeRegLocTemps(RegLocation rl_keep, RegLocation rl_free) {
540  DCHECK(rl_keep.wide);
541  DCHECK(rl_free.wide);
542  int free_low = rl_free.reg.GetLowReg();
543  int free_high = rl_free.reg.GetHighReg();
544  int keep_low = rl_keep.reg.GetLowReg();
545  int keep_high = rl_keep.reg.GetHighReg();
546  if ((free_low != keep_low) && (free_low != keep_high) &&
547      (free_high != keep_low) && (free_high != keep_high)) {
548    // No overlap, free both
549    FreeTemp(rl_free.reg);
550  }
551}
552
553bool Mir2Lir::IsLive(RegStorage reg) {
554  bool res;
555  if (reg.IsPair()) {
556    RegisterInfo* p_lo = GetRegInfo(reg.GetLow());
557    RegisterInfo* p_hi = GetRegInfo(reg.GetHigh());
558    DCHECK_EQ(p_lo->IsLive(), p_hi->IsLive());
559    res = p_lo->IsLive() || p_hi->IsLive();
560  } else {
561    RegisterInfo* p = GetRegInfo(reg);
562    res = p->IsLive();
563  }
564  return res;
565}
566
567bool Mir2Lir::IsTemp(RegStorage reg) {
568  bool res;
569  if (reg.IsPair()) {
570    RegisterInfo* p_lo = GetRegInfo(reg.GetLow());
571    RegisterInfo* p_hi = GetRegInfo(reg.GetHigh());
572    res = p_lo->IsTemp() || p_hi->IsTemp();
573  } else {
574    RegisterInfo* p = GetRegInfo(reg);
575    res = p->IsTemp();
576  }
577  return res;
578}
579
580bool Mir2Lir::IsPromoted(RegStorage reg) {
581  bool res;
582  if (reg.IsPair()) {
583    RegisterInfo* p_lo = GetRegInfo(reg.GetLow());
584    RegisterInfo* p_hi = GetRegInfo(reg.GetHigh());
585    res = !p_lo->IsTemp() || !p_hi->IsTemp();
586  } else {
587    RegisterInfo* p = GetRegInfo(reg);
588    res = !p->IsTemp();
589  }
590  return res;
591}
592
593bool Mir2Lir::IsDirty(RegStorage reg) {
594  bool res;
595  if (reg.IsPair()) {
596    RegisterInfo* p_lo = GetRegInfo(reg.GetLow());
597    RegisterInfo* p_hi = GetRegInfo(reg.GetHigh());
598    res = p_lo->IsDirty() || p_hi->IsDirty();
599  } else {
600    RegisterInfo* p = GetRegInfo(reg);
601    res = p->IsDirty();
602  }
603  return res;
604}
605
606/*
607 * Similar to AllocTemp(), but forces the allocation of a specific
608 * register.  No check is made to see if the register was previously
609 * allocated.  Use with caution.
610 */
611void Mir2Lir::LockTemp(RegStorage reg) {
612  DCHECK(IsTemp(reg));
613  if (reg.IsPair()) {
614    RegisterInfo* p_lo = GetRegInfo(reg.GetLow());
615    RegisterInfo* p_hi = GetRegInfo(reg.GetHigh());
616    p_lo->MarkInUse();
617    p_lo->MarkDead();
618    p_hi->MarkInUse();
619    p_hi->MarkDead();
620  } else {
621    RegisterInfo* p = GetRegInfo(reg);
622    p->MarkInUse();
623    p->MarkDead();
624  }
625}
626
627void Mir2Lir::ResetDef(RegStorage reg) {
628  if (reg.IsPair()) {
629    GetRegInfo(reg.GetLow())->ResetDefBody();
630    GetRegInfo(reg.GetHigh())->ResetDefBody();
631  } else {
632    GetRegInfo(reg)->ResetDefBody();
633  }
634}
635
636void Mir2Lir::NullifyRange(RegStorage reg, int s_reg) {
637  RegisterInfo* info = nullptr;
638  RegStorage rs = reg.IsPair() ? reg.GetLow() : reg;
639  if (IsTemp(rs)) {
640    info = GetRegInfo(reg);
641  }
642  if ((info != nullptr) && (info->DefStart() != nullptr) && (info->DefEnd() != nullptr)) {
643    DCHECK_EQ(info->SReg(), s_reg);  // Make sure we're on the same page.
644    for (LIR* p = info->DefStart();; p = p->next) {
645      NopLIR(p);
646      if (p == info->DefEnd()) {
647        break;
648      }
649    }
650  }
651}
652
653/*
654 * Mark the beginning and end LIR of a def sequence.  Note that
655 * on entry start points to the LIR prior to the beginning of the
656 * sequence.
657 */
658void Mir2Lir::MarkDef(RegLocation rl, LIR *start, LIR *finish) {
659  DCHECK(!rl.wide);
660  DCHECK(start && start->next);
661  DCHECK(finish);
662  RegisterInfo* p = GetRegInfo(rl.reg);
663  p->SetDefStart(start->next);
664  p->SetDefEnd(finish);
665}
666
667/*
668 * Mark the beginning and end LIR of a def sequence.  Note that
669 * on entry start points to the LIR prior to the beginning of the
670 * sequence.
671 */
672void Mir2Lir::MarkDefWide(RegLocation rl, LIR *start, LIR *finish) {
673  DCHECK(rl.wide);
674  DCHECK(start && start->next);
675  DCHECK(finish);
676  RegisterInfo* p;
677  if (rl.reg.IsPair()) {
678    p = GetRegInfo(rl.reg.GetLow());
679    ResetDef(rl.reg.GetHigh());  // Only track low of pair
680  } else {
681    p = GetRegInfo(rl.reg);
682  }
683  p->SetDefStart(start->next);
684  p->SetDefEnd(finish);
685}
686
687void Mir2Lir::ResetDefLoc(RegLocation rl) {
688  DCHECK(!rl.wide);
689  if (IsTemp(rl.reg) && !(cu_->disable_opt & (1 << kSuppressLoads))) {
690    NullifyRange(rl.reg, rl.s_reg_low);
691  }
692  ResetDef(rl.reg);
693}
694
695void Mir2Lir::ResetDefLocWide(RegLocation rl) {
696  DCHECK(rl.wide);
697  // If pair, only track low reg of pair.
698  RegStorage rs = rl.reg.IsPair() ? rl.reg.GetLow() : rl.reg;
699  if (IsTemp(rs) && !(cu_->disable_opt & (1 << kSuppressLoads))) {
700    NullifyRange(rs, rl.s_reg_low);
701  }
702  ResetDef(rs);
703}
704
705void Mir2Lir::ResetDefTracking() {
706  GrowableArray<RegisterInfo*>::Iterator iter(&tempreg_info_);
707  for (RegisterInfo* info = iter.Next(); info != NULL; info = iter.Next()) {
708    info->ResetDefBody();
709  }
710}
711
712void Mir2Lir::ClobberAllTemps() {
713  GrowableArray<RegisterInfo*>::Iterator iter(&tempreg_info_);
714  for (RegisterInfo* info = iter.Next(); info != NULL; info = iter.Next()) {
715    ClobberBody(info);
716  }
717}
718
719void Mir2Lir::FlushRegWide(RegStorage reg) {
720  if (reg.IsPair()) {
721    RegisterInfo* info1 = GetRegInfo(reg.GetLow());
722    RegisterInfo* info2 = GetRegInfo(reg.GetHigh());
723    DCHECK(info1 && info2 && info1->IsWide() && info2->IsWide() &&
724         (info1->Partner() == info2->GetReg()) && (info2->Partner() == info1->GetReg()));
725    if ((info1->IsLive() && info1->IsDirty()) || (info2->IsLive() && info2->IsDirty())) {
726      if (!(info1->IsTemp() && info2->IsTemp())) {
727        /* Should not happen.  If it does, there's a problem in eval_loc */
728        LOG(FATAL) << "Long half-temp, half-promoted";
729      }
730
731      info1->SetIsDirty(false);
732      info2->SetIsDirty(false);
733      if (mir_graph_->SRegToVReg(info2->SReg()) < mir_graph_->SRegToVReg(info1->SReg())) {
734        info1 = info2;
735      }
736      int v_reg = mir_graph_->SRegToVReg(info1->SReg());
737      StoreBaseDisp(TargetReg(kSp), VRegOffset(v_reg), reg, k64);
738    }
739  } else {
740    RegisterInfo* info = GetRegInfo(reg);
741    if (info->IsLive() && info->IsDirty()) {
742      info->SetIsDirty(false);
743      int v_reg = mir_graph_->SRegToVReg(info->SReg());
744      StoreBaseDisp(TargetReg(kSp), VRegOffset(v_reg), reg, k64);
745    }
746  }
747}
748
749void Mir2Lir::FlushReg(RegStorage reg) {
750  DCHECK(!reg.IsPair());
751  RegisterInfo* info = GetRegInfo(reg);
752  if (info->IsLive() && info->IsDirty()) {
753    info->SetIsDirty(false);
754    int v_reg = mir_graph_->SRegToVReg(info->SReg());
755    StoreBaseDisp(TargetReg(kSp), VRegOffset(v_reg), reg, kWord);
756  }
757}
758
759void Mir2Lir::FlushSpecificReg(RegisterInfo* info) {
760  if (info->IsWide()) {
761    FlushRegWide(info->GetReg());
762  } else {
763    FlushReg(info->GetReg());
764  }
765}
766
767void Mir2Lir::FlushAllRegs() {
768  GrowableArray<RegisterInfo*>::Iterator it(&tempreg_info_);
769  for (RegisterInfo* info = it.Next(); info != nullptr; info = it.Next()) {
770    if (info->IsDirty() && info->IsLive()) {
771      FlushSpecificReg(info);
772    }
773    info->MarkDead();
774    info->SetIsWide(false);
775  }
776}
777
778
779bool Mir2Lir::RegClassMatches(int reg_class, RegStorage reg) {
780  if (reg_class == kAnyReg) {
781    return true;
782  } else if ((reg_class == kCoreReg) || (reg_class == kRefReg)) {
783    /*
784     * For this purpose, consider Core and Ref to be the same class. We aren't dealing
785     * with width here - that should be checked at a higher level (if needed).
786     */
787    return !reg.IsFloat();
788  } else {
789    return reg.IsFloat();
790  }
791}
792
793void Mir2Lir::MarkLive(RegLocation loc) {
794  RegStorage reg = loc.reg;
795  if (!IsTemp(reg)) {
796    return;
797  }
798  int s_reg = loc.s_reg_low;
799  if (s_reg == INVALID_SREG) {
800    // Can't be live if no associated sreg.
801    if (reg.IsPair()) {
802      GetRegInfo(reg.GetLow())->MarkDead();
803      GetRegInfo(reg.GetHigh())->MarkDead();
804    } else {
805      GetRegInfo(reg)->MarkDead();
806    }
807  } else {
808    if (reg.IsPair()) {
809      RegisterInfo* info_lo = GetRegInfo(reg.GetLow());
810      RegisterInfo* info_hi = GetRegInfo(reg.GetHigh());
811      if (info_lo->IsLive() && (info_lo->SReg() == s_reg) && info_hi->IsLive() &&
812          (info_hi->SReg() == s_reg)) {
813        return;  // Already live.
814      }
815      ClobberSReg(s_reg);
816      ClobberSReg(s_reg + 1);
817      info_lo->MarkLive(s_reg);
818      info_hi->MarkLive(s_reg + 1);
819    } else {
820      RegisterInfo* info = GetRegInfo(reg);
821      if (info->IsLive() && (info->SReg() == s_reg)) {
822        return;  // Already live.
823      }
824      ClobberSReg(s_reg);
825      if (loc.wide) {
826        ClobberSReg(s_reg + 1);
827      }
828      info->MarkLive(s_reg);
829    }
830    if (loc.wide) {
831      MarkWide(reg);
832    } else {
833      MarkNarrow(reg);
834    }
835  }
836}
837
838void Mir2Lir::MarkTemp(RegStorage reg) {
839  DCHECK(!reg.IsPair());
840  RegisterInfo* info = GetRegInfo(reg);
841  tempreg_info_.Insert(info);
842  info->SetIsTemp(true);
843}
844
845void Mir2Lir::UnmarkTemp(RegStorage reg) {
846  DCHECK(!reg.IsPair());
847  RegisterInfo* info = GetRegInfo(reg);
848  tempreg_info_.Delete(info);
849  info->SetIsTemp(false);
850}
851
852void Mir2Lir::MarkWide(RegStorage reg) {
853  if (reg.IsPair()) {
854    RegisterInfo* info_lo = GetRegInfo(reg.GetLow());
855    RegisterInfo* info_hi = GetRegInfo(reg.GetHigh());
856    // Unpair any old partners.
857    if (info_lo->IsWide() && info_lo->Partner() != info_hi->GetReg()) {
858      GetRegInfo(info_lo->Partner())->SetIsWide(false);
859    }
860    if (info_hi->IsWide() && info_hi->Partner() != info_lo->GetReg()) {
861      GetRegInfo(info_hi->Partner())->SetIsWide(false);
862    }
863    info_lo->SetIsWide(true);
864    info_hi->SetIsWide(true);
865    info_lo->SetPartner(reg.GetHigh());
866    info_hi->SetPartner(reg.GetLow());
867  } else {
868    RegisterInfo* info = GetRegInfo(reg);
869    info->SetIsWide(true);
870    info->SetPartner(reg);
871  }
872}
873
874void Mir2Lir::MarkNarrow(RegStorage reg) {
875  DCHECK(!reg.IsPair());
876  RegisterInfo* info = GetRegInfo(reg);
877  info->SetIsWide(false);
878  info->SetPartner(reg);
879}
880
881void Mir2Lir::MarkClean(RegLocation loc) {
882  if (loc.reg.IsPair()) {
883    RegisterInfo* info = GetRegInfo(loc.reg.GetLow());
884    info->SetIsDirty(false);
885    info = GetRegInfo(loc.reg.GetHigh());
886    info->SetIsDirty(false);
887  } else {
888    RegisterInfo* info = GetRegInfo(loc.reg);
889    info->SetIsDirty(false);
890  }
891}
892
893// FIXME: need to verify rules/assumptions about how wide values are treated in 64BitSolos.
894void Mir2Lir::MarkDirty(RegLocation loc) {
895  if (loc.home) {
896    // If already home, can't be dirty
897    return;
898  }
899  if (loc.reg.IsPair()) {
900    RegisterInfo* info = GetRegInfo(loc.reg.GetLow());
901    info->SetIsDirty(true);
902    info = GetRegInfo(loc.reg.GetHigh());
903    info->SetIsDirty(true);
904  } else {
905    RegisterInfo* info = GetRegInfo(loc.reg);
906    info->SetIsDirty(true);
907  }
908}
909
910void Mir2Lir::MarkInUse(RegStorage reg) {
911  if (reg.IsPair()) {
912    GetRegInfo(reg.GetLow())->MarkInUse();
913    GetRegInfo(reg.GetHigh())->MarkInUse();
914  } else {
915    GetRegInfo(reg)->MarkInUse();
916  }
917}
918
919bool Mir2Lir::CheckCorePoolSanity() {
920  GrowableArray<RegisterInfo*>::Iterator it(&tempreg_info_);
921  for (RegisterInfo* info = it.Next(); info != nullptr; info = it.Next()) {
922    if (info->IsTemp() && info->IsLive() && info->IsWide()) {
923      RegStorage my_reg = info->GetReg();
924      int my_sreg = info->SReg();
925      RegStorage partner_reg = info->Partner();
926      RegisterInfo* partner = GetRegInfo(partner_reg);
927      DCHECK(partner != NULL);
928      DCHECK(partner->IsWide());
929      DCHECK_EQ(my_reg.GetReg(), partner->Partner().GetReg());
930      DCHECK(partner->IsLive());
931      int partner_sreg = partner->SReg();
932      if (my_sreg == INVALID_SREG) {
933        DCHECK_EQ(partner_sreg, INVALID_SREG);
934      } else {
935        int diff = my_sreg - partner_sreg;
936        DCHECK((diff == 0) || (diff == -1) || (diff == 1));
937      }
938    }
939    if (info->Master() != info) {
940      // Aliased.
941      if (info->IsLive() && (info->SReg() != INVALID_SREG)) {
942        // If I'm live, master should not be live, but should show liveness in alias set.
943        DCHECK_EQ(info->Master()->SReg(), INVALID_SREG);
944        DCHECK(!info->Master()->IsDead());
945      }
946// TODO: Add checks in !info->IsDead() case to ensure every live bit is owned by exactly 1 reg.
947    }
948    if (info->IsAliased()) {
949      // Has child aliases.
950      DCHECK_EQ(info->Master(), info);
951      if (info->IsLive() && (info->SReg() != INVALID_SREG)) {
952        // Master live, no child should be dead - all should show liveness in set.
953        for (RegisterInfo* p = info->GetAliasChain(); p != nullptr; p = p->GetAliasChain()) {
954          DCHECK(!p->IsDead());
955          DCHECK_EQ(p->SReg(), INVALID_SREG);
956        }
957      } else if (!info->IsDead()) {
958        // Master not live, one or more aliases must be.
959        bool live_alias = false;
960        for (RegisterInfo* p = info->GetAliasChain(); p != nullptr; p = p->GetAliasChain()) {
961          live_alias |= p->IsLive();
962        }
963        DCHECK(live_alias);
964      }
965    }
966    if (info->IsLive() && (info->SReg() == INVALID_SREG)) {
967      // If not fully live, should have INVALID_SREG and def's should be null.
968      DCHECK(info->DefStart() == nullptr);
969      DCHECK(info->DefEnd() == nullptr);
970    }
971  }
972  return true;
973}
974
975/*
976 * Return an updated location record with current in-register status.
977 * If the value lives in live temps, reflect that fact.  No code
978 * is generated.  If the live value is part of an older pair,
979 * clobber both low and high.
980 * TUNING: clobbering both is a bit heavy-handed, but the alternative
981 * is a bit complex when dealing with FP regs.  Examine code to see
982 * if it's worthwhile trying to be more clever here.
983 */
984RegLocation Mir2Lir::UpdateLoc(RegLocation loc) {
985  DCHECK(!loc.wide);
986  DCHECK(CheckCorePoolSanity());
987  if (loc.location != kLocPhysReg) {
988    DCHECK((loc.location == kLocDalvikFrame) ||
989         (loc.location == kLocCompilerTemp));
990    RegStorage reg = AllocLiveReg(loc.s_reg_low, kAnyReg, false);
991    if (reg.Valid()) {
992      bool match = true;
993      RegisterInfo* info = GetRegInfo(reg);
994      match &= !reg.IsPair();
995      match &= !info->IsWide();
996      if (match) {
997        loc.location = kLocPhysReg;
998        loc.reg = reg;
999      } else {
1000        Clobber(reg);
1001        FreeTemp(reg);
1002      }
1003    }
1004  }
1005  return loc;
1006}
1007
1008RegLocation Mir2Lir::UpdateLocWide(RegLocation loc) {
1009  DCHECK(loc.wide);
1010  DCHECK(CheckCorePoolSanity());
1011  if (loc.location != kLocPhysReg) {
1012    DCHECK((loc.location == kLocDalvikFrame) ||
1013         (loc.location == kLocCompilerTemp));
1014    RegStorage reg = AllocLiveReg(loc.s_reg_low, kAnyReg, true);
1015    if (reg.Valid()) {
1016      bool match = true;
1017      if (reg.IsPair()) {
1018        // If we've got a register pair, make sure that it was last used as the same pair.
1019        RegisterInfo* info_lo = GetRegInfo(reg.GetLow());
1020        RegisterInfo* info_hi = GetRegInfo(reg.GetHigh());
1021        match &= info_lo->IsWide();
1022        match &= info_hi->IsWide();
1023        match &= (info_lo->Partner() == info_hi->GetReg());
1024        match &= (info_hi->Partner() == info_lo->GetReg());
1025      } else {
1026        RegisterInfo* info = GetRegInfo(reg);
1027        match &= info->IsWide();
1028        match &= (info->GetReg() == info->Partner());
1029      }
1030      if (match) {
1031        loc.location = kLocPhysReg;
1032        loc.reg = reg;
1033      } else {
1034        Clobber(reg);
1035        FreeTemp(reg);
1036      }
1037    }
1038  }
1039  return loc;
1040}
1041
1042/* For use in cases we don't know (or care) width */
1043RegLocation Mir2Lir::UpdateRawLoc(RegLocation loc) {
1044  if (loc.wide)
1045    return UpdateLocWide(loc);
1046  else
1047    return UpdateLoc(loc);
1048}
1049
1050RegLocation Mir2Lir::EvalLocWide(RegLocation loc, int reg_class, bool update) {
1051  DCHECK(loc.wide);
1052
1053  loc = UpdateLocWide(loc);
1054
1055  /* If already in registers, we can assume proper form.  Right reg class? */
1056  if (loc.location == kLocPhysReg) {
1057    if (!RegClassMatches(reg_class, loc.reg)) {
1058      // Wrong register class.  Reallocate and transfer ownership.
1059      RegStorage new_regs = AllocTypedTempWide(loc.fp, reg_class);
1060      // Clobber the old regs.
1061      Clobber(loc.reg);
1062      // ...and mark the new ones live.
1063      loc.reg = new_regs;
1064      MarkWide(loc.reg);
1065      MarkLive(loc);
1066    }
1067    return loc;
1068  }
1069
1070  DCHECK_NE(loc.s_reg_low, INVALID_SREG);
1071  DCHECK_NE(GetSRegHi(loc.s_reg_low), INVALID_SREG);
1072
1073  loc.reg = AllocTypedTempWide(loc.fp, reg_class);
1074  MarkWide(loc.reg);
1075
1076  if (update) {
1077    loc.location = kLocPhysReg;
1078    MarkLive(loc);
1079  }
1080  return loc;
1081}
1082
1083RegLocation Mir2Lir::EvalLoc(RegLocation loc, int reg_class, bool update) {
1084  if (loc.wide) {
1085    return EvalLocWide(loc, reg_class, update);
1086  }
1087
1088  loc = UpdateLoc(loc);
1089
1090  if (loc.location == kLocPhysReg) {
1091    if (!RegClassMatches(reg_class, loc.reg)) {
1092      // Wrong register class.  Reallocate and transfer ownership.
1093      RegStorage new_reg = AllocTypedTemp(loc.fp, reg_class);
1094      // Clobber the old reg.
1095      Clobber(loc.reg);
1096      // ...and mark the new one live.
1097      loc.reg = new_reg;
1098      MarkLive(loc);
1099    }
1100    return loc;
1101  }
1102
1103  DCHECK_NE(loc.s_reg_low, INVALID_SREG);
1104
1105  loc.reg = AllocTypedTemp(loc.fp, reg_class);
1106
1107  if (update) {
1108    loc.location = kLocPhysReg;
1109    MarkLive(loc);
1110  }
1111  return loc;
1112}
1113
1114/* USE SSA names to count references of base Dalvik v_regs. */
1115void Mir2Lir::CountRefs(RefCounts* core_counts, RefCounts* fp_counts, size_t num_regs) {
1116  for (int i = 0; i < mir_graph_->GetNumSSARegs(); i++) {
1117    RegLocation loc = mir_graph_->reg_location_[i];
1118    RefCounts* counts = loc.fp ? fp_counts : core_counts;
1119    int p_map_idx = SRegToPMap(loc.s_reg_low);
1120    if (loc.fp) {
1121      if (loc.wide) {
1122        // Treat doubles as a unit, using upper half of fp_counts array.
1123        counts[p_map_idx + num_regs].count += mir_graph_->GetUseCount(i);
1124        i++;
1125      } else {
1126        counts[p_map_idx].count += mir_graph_->GetUseCount(i);
1127      }
1128    } else if (!IsInexpensiveConstant(loc)) {
1129      counts[p_map_idx].count += mir_graph_->GetUseCount(i);
1130    }
1131  }
1132}
1133
1134/* qsort callback function, sort descending */
1135static int SortCounts(const void *val1, const void *val2) {
1136  const Mir2Lir::RefCounts* op1 = reinterpret_cast<const Mir2Lir::RefCounts*>(val1);
1137  const Mir2Lir::RefCounts* op2 = reinterpret_cast<const Mir2Lir::RefCounts*>(val2);
1138  // Note that we fall back to sorting on reg so we get stable output
1139  // on differing qsort implementations (such as on host and target or
1140  // between local host and build servers).
1141  return (op1->count == op2->count)
1142          ? (op1->s_reg - op2->s_reg)
1143          : (op1->count < op2->count ? 1 : -1);
1144}
1145
1146void Mir2Lir::DumpCounts(const RefCounts* arr, int size, const char* msg) {
1147  LOG(INFO) << msg;
1148  for (int i = 0; i < size; i++) {
1149    if ((arr[i].s_reg & STARTING_DOUBLE_SREG) != 0) {
1150      LOG(INFO) << "s_reg[D" << (arr[i].s_reg & ~STARTING_DOUBLE_SREG) << "]: " << arr[i].count;
1151    } else {
1152      LOG(INFO) << "s_reg[" << arr[i].s_reg << "]: " << arr[i].count;
1153    }
1154  }
1155}
1156
1157/*
1158 * Note: some portions of this code required even if the kPromoteRegs
1159 * optimization is disabled.
1160 */
1161void Mir2Lir::DoPromotion() {
1162  int dalvik_regs = cu_->num_dalvik_registers;
1163  int num_regs = dalvik_regs + mir_graph_->GetNumUsedCompilerTemps();
1164  const int promotion_threshold = 1;
1165  // Allocate the promotion map - one entry for each Dalvik vReg or compiler temp
1166  promotion_map_ = static_cast<PromotionMap*>
1167      (arena_->Alloc(num_regs * sizeof(promotion_map_[0]), kArenaAllocRegAlloc));
1168
1169  // Allow target code to add any special registers
1170  AdjustSpillMask();
1171
1172  /*
1173   * Simple register promotion. Just do a static count of the uses
1174   * of Dalvik registers.  Note that we examine the SSA names, but
1175   * count based on original Dalvik register name.  Count refs
1176   * separately based on type in order to give allocation
1177   * preference to fp doubles - which must be allocated sequential
1178   * physical single fp registers starting with an even-numbered
1179   * reg.
1180   * TUNING: replace with linear scan once we have the ability
1181   * to describe register live ranges for GC.
1182   */
1183  RefCounts *core_regs =
1184      static_cast<RefCounts*>(arena_->Alloc(sizeof(RefCounts) * num_regs,
1185                                            kArenaAllocRegAlloc));
1186  RefCounts *FpRegs =
1187      static_cast<RefCounts *>(arena_->Alloc(sizeof(RefCounts) * num_regs * 2,
1188                                             kArenaAllocRegAlloc));
1189  // Set ssa names for original Dalvik registers
1190  for (int i = 0; i < dalvik_regs; i++) {
1191    core_regs[i].s_reg = FpRegs[i].s_reg = i;
1192  }
1193
1194  // Set ssa names for compiler temporaries
1195  for (unsigned int ct_idx = 0; ct_idx < mir_graph_->GetNumUsedCompilerTemps(); ct_idx++) {
1196    CompilerTemp* ct = mir_graph_->GetCompilerTemp(ct_idx);
1197    core_regs[dalvik_regs + ct_idx].s_reg = ct->s_reg_low;
1198    FpRegs[dalvik_regs + ct_idx].s_reg = ct->s_reg_low;
1199    FpRegs[num_regs + dalvik_regs + ct_idx].s_reg = ct->s_reg_low;
1200  }
1201
1202  // Duplicate in upper half to represent possible fp double starting sregs.
1203  for (int i = 0; i < num_regs; i++) {
1204    FpRegs[num_regs + i].s_reg = FpRegs[i].s_reg | STARTING_DOUBLE_SREG;
1205  }
1206
1207  // Sum use counts of SSA regs by original Dalvik vreg.
1208  CountRefs(core_regs, FpRegs, num_regs);
1209
1210
1211  // Sort the count arrays
1212  qsort(core_regs, num_regs, sizeof(RefCounts), SortCounts);
1213  qsort(FpRegs, num_regs * 2, sizeof(RefCounts), SortCounts);
1214
1215  if (cu_->verbose) {
1216    DumpCounts(core_regs, num_regs, "Core regs after sort");
1217    DumpCounts(FpRegs, num_regs * 2, "Fp regs after sort");
1218  }
1219
1220  if (!(cu_->disable_opt & (1 << kPromoteRegs))) {
1221    // Promote FpRegs
1222    for (int i = 0; (i < (num_regs * 2)) && (FpRegs[i].count >= promotion_threshold); i++) {
1223      int p_map_idx = SRegToPMap(FpRegs[i].s_reg & ~STARTING_DOUBLE_SREG);
1224      if ((FpRegs[i].s_reg & STARTING_DOUBLE_SREG) != 0) {
1225        if ((promotion_map_[p_map_idx].fp_location != kLocPhysReg) &&
1226            (promotion_map_[p_map_idx + 1].fp_location != kLocPhysReg)) {
1227          int low_sreg = FpRegs[i].s_reg & ~STARTING_DOUBLE_SREG;
1228          // Ignore result - if can't alloc double may still be able to alloc singles.
1229          AllocPreservedDouble(low_sreg);
1230        }
1231      } else if (promotion_map_[p_map_idx].fp_location != kLocPhysReg) {
1232        RegStorage reg = AllocPreservedSingle(FpRegs[i].s_reg);
1233        if (!reg.Valid()) {
1234          break;  // No more left.
1235        }
1236      }
1237    }
1238
1239    // Promote core regs
1240    for (int i = 0; (i < num_regs) &&
1241            (core_regs[i].count >= promotion_threshold); i++) {
1242      int p_map_idx = SRegToPMap(core_regs[i].s_reg);
1243      if (promotion_map_[p_map_idx].core_location !=
1244          kLocPhysReg) {
1245        RegStorage reg = AllocPreservedCoreReg(core_regs[i].s_reg);
1246        if (!reg.Valid()) {
1247           break;  // No more left
1248        }
1249      }
1250    }
1251  }
1252
1253  // Now, update SSA names to new home locations
1254  for (int i = 0; i < mir_graph_->GetNumSSARegs(); i++) {
1255    RegLocation *curr = &mir_graph_->reg_location_[i];
1256    int p_map_idx = SRegToPMap(curr->s_reg_low);
1257    if (!curr->wide) {
1258      if (curr->fp) {
1259        if (promotion_map_[p_map_idx].fp_location == kLocPhysReg) {
1260          curr->location = kLocPhysReg;
1261          curr->reg = RegStorage::Solo32(promotion_map_[p_map_idx].FpReg);
1262          curr->home = true;
1263        }
1264      } else {
1265        if (promotion_map_[p_map_idx].core_location == kLocPhysReg) {
1266          curr->location = kLocPhysReg;
1267          curr->reg = RegStorage::Solo32(promotion_map_[p_map_idx].core_reg);
1268          curr->home = true;
1269        }
1270      }
1271    } else {
1272      if (curr->high_word) {
1273        continue;
1274      }
1275      if (curr->fp) {
1276        if ((promotion_map_[p_map_idx].fp_location == kLocPhysReg) &&
1277            (promotion_map_[p_map_idx+1].fp_location == kLocPhysReg)) {
1278          int low_reg = promotion_map_[p_map_idx].FpReg;
1279          int high_reg = promotion_map_[p_map_idx+1].FpReg;
1280          // Doubles require pair of singles starting at even reg
1281          // TODO: move target-specific restrictions out of here.
1282          if (((low_reg & 0x1) == 0) && ((low_reg + 1) == high_reg)) {
1283            curr->location = kLocPhysReg;
1284            if (cu_->instruction_set == kThumb2) {
1285              curr->reg = RegStorage::FloatSolo64(RegStorage::RegNum(low_reg) >> 1);
1286            } else {
1287              curr->reg = RegStorage(RegStorage::k64BitPair, low_reg, high_reg);
1288            }
1289            curr->home = true;
1290          }
1291        }
1292      } else {
1293        if ((promotion_map_[p_map_idx].core_location == kLocPhysReg)
1294           && (promotion_map_[p_map_idx+1].core_location ==
1295           kLocPhysReg)) {
1296          curr->location = kLocPhysReg;
1297          curr->reg = RegStorage(RegStorage::k64BitPair, promotion_map_[p_map_idx].core_reg,
1298                                 promotion_map_[p_map_idx+1].core_reg);
1299          curr->home = true;
1300        }
1301      }
1302    }
1303  }
1304  if (cu_->verbose) {
1305    DumpPromotionMap();
1306  }
1307}
1308
1309/* Returns sp-relative offset in bytes for a VReg */
1310int Mir2Lir::VRegOffset(int v_reg) {
1311  return StackVisitor::GetVRegOffset(cu_->code_item, core_spill_mask_,
1312                                     fp_spill_mask_, frame_size_, v_reg,
1313                                     cu_->instruction_set);
1314}
1315
1316/* Returns sp-relative offset in bytes for a SReg */
1317int Mir2Lir::SRegOffset(int s_reg) {
1318  return VRegOffset(mir_graph_->SRegToVReg(s_reg));
1319}
1320
1321/* Mark register usage state and return long retloc */
1322RegLocation Mir2Lir::GetReturnWide(RegisterClass reg_class) {
1323  RegLocation res;
1324  switch (reg_class) {
1325    case kRefReg: LOG(FATAL); break;
1326    case kFPReg: res = LocCReturnDouble(); break;
1327    default: res = LocCReturnWide(); break;
1328  }
1329  Clobber(res.reg);
1330  LockTemp(res.reg);
1331  MarkWide(res.reg);
1332  return res;
1333}
1334
1335RegLocation Mir2Lir::GetReturn(RegisterClass reg_class) {
1336  RegLocation res;
1337  switch (reg_class) {
1338    case kRefReg: res = LocCReturnRef(); break;
1339    case kFPReg: res = LocCReturnFloat(); break;
1340    default: res = LocCReturn(); break;
1341  }
1342  Clobber(res.reg);
1343  if (cu_->instruction_set == kMips) {
1344    MarkInUse(res.reg);
1345  } else {
1346    LockTemp(res.reg);
1347  }
1348  return res;
1349}
1350
1351void Mir2Lir::SimpleRegAlloc() {
1352  DoPromotion();
1353
1354  if (cu_->verbose && !(cu_->disable_opt & (1 << kPromoteRegs))) {
1355    LOG(INFO) << "After Promotion";
1356    mir_graph_->DumpRegLocTable(mir_graph_->reg_location_, mir_graph_->GetNumSSARegs());
1357  }
1358
1359  /* Set the frame size */
1360  frame_size_ = ComputeFrameSize();
1361}
1362
1363/*
1364 * Get the "real" sreg number associated with an s_reg slot.  In general,
1365 * s_reg values passed through codegen are the SSA names created by
1366 * dataflow analysis and refer to slot numbers in the mir_graph_->reg_location
1367 * array.  However, renaming is accomplished by simply replacing RegLocation
1368 * entries in the reglocation[] array.  Therefore, when location
1369 * records for operands are first created, we need to ask the locRecord
1370 * identified by the dataflow pass what it's new name is.
1371 */
1372int Mir2Lir::GetSRegHi(int lowSreg) {
1373  return (lowSreg == INVALID_SREG) ? INVALID_SREG : lowSreg + 1;
1374}
1375
1376bool Mir2Lir::LiveOut(int s_reg) {
1377  // For now.
1378  return true;
1379}
1380
1381}  // namespace art
1382