summaryrefslogtreecommitdiffstats
path: root/compiler/optimizing/parallel_move_resolver.cc
blob: 7d0641ec13645fcbd029ab60d95853052518c541 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
/*
 * Copyright (C) 2014 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

#include "parallel_move_resolver.h"
#include "nodes.h"
#include "locations.h"

namespace art {

void ParallelMoveResolver::EmitNativeCode(HParallelMove* parallel_move) {
  DCHECK(moves_.IsEmpty());
  // Build up a worklist of moves.
  BuildInitialMoveList(parallel_move);

  for (size_t i = 0; i < moves_.Size(); ++i) {
    const MoveOperands& move = *moves_.Get(i);
    // Skip constants to perform them last.  They don't block other moves
    // and skipping such moves with register destinations keeps those
    // registers free for the whole algorithm.
    if (!move.IsEliminated() && !move.GetSource().IsConstant()) {
      PerformMove(i);
    }
  }

  // Perform the moves with constant sources.
  for (size_t i = 0; i < moves_.Size(); ++i) {
    MoveOperands* move = moves_.Get(i);
    if (!move->IsEliminated()) {
      DCHECK(move->GetSource().IsConstant());
      EmitMove(i);
      // Eliminate the move, in case following moves need a scratch register.
      move->Eliminate();
    }
  }

  moves_.Reset();
}


void ParallelMoveResolver::BuildInitialMoveList(HParallelMove* parallel_move) {
  // Perform a linear sweep of the moves to add them to the initial list of
  // moves to perform, ignoring any move that is redundant (the source is
  // the same as the destination, the destination is ignored and
  // unallocated, or the move was already eliminated).
  for (size_t i = 0; i < parallel_move->NumMoves(); ++i) {
    MoveOperands* move = parallel_move->MoveOperandsAt(i);
    if (!move->IsRedundant()) {
      moves_.Add(move);
    }
  }
}

// Update the source of `move`, knowing that `updated_location` has been swapped
// with `new_source`. Note that `updated_location` can be a pair, therefore if
// `move` is non-pair, we need to extract which register to use.
static void UpdateSourceOf(MoveOperands* move, Location updated_location, Location new_source) {
  Location source = move->GetSource();
  if (new_source.GetKind() == source.GetKind()) {
    DCHECK(updated_location.Equals(source));
    move->SetSource(new_source);
  } else if (new_source.IsStackSlot()
             || new_source.IsDoubleStackSlot()
             || source.IsStackSlot()
             || source.IsDoubleStackSlot()) {
    // Stack slots never take part of a pair/non-pair swap.
    DCHECK(updated_location.Equals(source));
    move->SetSource(new_source);
  } else if (source.IsRegister()) {
    DCHECK(new_source.IsRegisterPair()) << new_source;
    DCHECK(updated_location.IsRegisterPair()) << updated_location;
    if (updated_location.low() == source.reg()) {
      move->SetSource(Location::RegisterLocation(new_source.low()));
    } else {
      DCHECK_EQ(updated_location.high(), source.reg());
      move->SetSource(Location::RegisterLocation(new_source.high()));
    }
  } else if (source.IsFpuRegister()) {
    DCHECK(new_source.IsFpuRegisterPair()) << new_source;
    DCHECK(updated_location.IsFpuRegisterPair()) << updated_location;
    if (updated_location.low() == source.reg()) {
      move->SetSource(Location::FpuRegisterLocation(new_source.low()));
    } else {
      DCHECK_EQ(updated_location.high(), source.reg());
      move->SetSource(Location::FpuRegisterLocation(new_source.high()));
    }
  }
}

MoveOperands* ParallelMoveResolver::PerformMove(size_t index) {
  // Each call to this function performs a move and deletes it from the move
  // graph.  We first recursively perform any move blocking this one.  We
  // mark a move as "pending" on entry to PerformMove in order to detect
  // cycles in the move graph.  We use operand swaps to resolve cycles,
  // which means that a call to PerformMove could change any source operand
  // in the move graph.

  MoveOperands* move = moves_.Get(index);
  DCHECK(!move->IsPending());
  if (move->IsRedundant()) {
    // Because we swap register pairs first, following, un-pending
    // moves may become redundant.
    move->Eliminate();
    return nullptr;
  }

  // Clear this move's destination to indicate a pending move.  The actual
  // destination is saved in a stack-allocated local.  Recursion may allow
  // multiple moves to be pending.
  DCHECK(!move->GetSource().IsInvalid());
  Location destination = move->MarkPending();

  // Perform a depth-first traversal of the move graph to resolve
  // dependencies.  Any unperformed, unpending move with a source the same
  // as this one's destination blocks this one so recursively perform all
  // such moves.
  MoveOperands* required_swap = nullptr;
  for (size_t i = 0; i < moves_.Size(); ++i) {
    const MoveOperands& other_move = *moves_.Get(i);
    if (other_move.Blocks(destination) && !other_move.IsPending()) {
      // Though PerformMove can change any source operand in the move graph,
      // calling `PerformMove` cannot create a blocking move via a swap
      // (this loop does not miss any).
      // For example, assume there is a non-blocking move with source A
      // and this move is blocked on source B and there is a swap of A and
      // B.  Then A and B must be involved in the same cycle (or they would
      // not be swapped).  Since this move's destination is B and there is
      // only a single incoming edge to an operand, this move must also be
      // involved in the same cycle.  In that case, the blocking move will
      // be created but will be "pending" when we return from PerformMove.
      required_swap = PerformMove(i);

      if (required_swap == move) {
        // If this move is required to swap, we do so without looking
        // at the next moves. Swapping is not blocked by anything, it just
        // updates other moves's source.
        break;
      } else if (required_swap == moves_.Get(i)) {
        // If `other_move` was swapped, we iterate again to find a new
        // potential cycle.
        required_swap = nullptr;
        i = 0;
      } else if (required_swap != nullptr) {
        // A move is required to swap. We walk back the cycle to find the
        // move by just returning from this `PerforrmMove`.
        moves_.Get(index)->ClearPending(destination);
        return required_swap;
      }
    }
  }

  // We are about to resolve this move and don't need it marked as
  // pending, so restore its destination.
  move->ClearPending(destination);

  // This move's source may have changed due to swaps to resolve cycles and
  // so it may now be the last move in the cycle.  If so remove it.
  if (move->GetSource().Equals(destination)) {
    move->Eliminate();
    DCHECK(required_swap == nullptr);
    return nullptr;
  }

  // The move may be blocked on a (at most one) pending move, in which case
  // we have a cycle.  Search for such a blocking move and perform a swap to
  // resolve it.
  bool do_swap = false;
  if (required_swap != nullptr) {
    DCHECK_EQ(required_swap, move);
    do_swap = true;
  } else {
    for (size_t i = 0; i < moves_.Size(); ++i) {
      const MoveOperands& other_move = *moves_.Get(i);
      if (other_move.Blocks(destination)) {
        DCHECK(other_move.IsPending());
        if (!destination.IsPair() && other_move.GetSource().IsPair()) {
          // We swap pairs before swapping non-pairs. Go back from the
          // cycle by returning the pair that must be swapped.
          return moves_.Get(i);
        }
        do_swap = true;
        break;
      }
    }
  }

  if (do_swap) {
    EmitSwap(index);
    // Any unperformed (including pending) move with a source of either
    // this move's source or destination needs to have their source
    // changed to reflect the state of affairs after the swap.
    Location source = move->GetSource();
    Location swap_destination = move->GetDestination();
    move->Eliminate();
    for (size_t i = 0; i < moves_.Size(); ++i) {
      const MoveOperands& other_move = *moves_.Get(i);
      if (other_move.Blocks(source)) {
        UpdateSourceOf(moves_.Get(i), source, swap_destination);
      } else if (other_move.Blocks(swap_destination)) {
        UpdateSourceOf(moves_.Get(i), swap_destination, source);
      }
    }
    // If the swap was required because of a pair in the middle of a cycle,
    // we return the swapped move, so that the caller knows it needs to re-iterate
    // its dependency loop.
    return required_swap;
  } else {
    // This move is not blocked.
    EmitMove(index);
    move->Eliminate();
    DCHECK(required_swap == nullptr);
    return nullptr;
  }
}

bool ParallelMoveResolver::IsScratchLocation(Location loc) {
  for (size_t i = 0; i < moves_.Size(); ++i) {
    if (moves_.Get(i)->Blocks(loc)) {
      return false;
    }
  }

  for (size_t i = 0; i < moves_.Size(); ++i) {
    if (moves_.Get(i)->GetDestination().Equals(loc)) {
      return true;
    }
  }

  return false;
}

int ParallelMoveResolver::AllocateScratchRegister(int blocked,
                                                  int register_count,
                                                  int if_scratch,
                                                  bool* spilled) {
  DCHECK_NE(blocked, if_scratch);
  int scratch = -1;
  for (int reg = 0; reg < register_count; ++reg) {
    if ((blocked != reg) && IsScratchLocation(Location::RegisterLocation(reg))) {
      scratch = reg;
      break;
    }
  }

  if (scratch == -1) {
    *spilled = true;
    scratch = if_scratch;
  } else {
    *spilled = false;
  }

  return scratch;
}


ParallelMoveResolver::ScratchRegisterScope::ScratchRegisterScope(
    ParallelMoveResolver* resolver, int blocked, int if_scratch, int number_of_registers)
    : resolver_(resolver),
      reg_(kNoRegister),
      spilled_(false) {
  reg_ = resolver_->AllocateScratchRegister(blocked, number_of_registers, if_scratch, &spilled_);

  if (spilled_) {
    resolver->SpillScratch(reg_);
  }
}


ParallelMoveResolver::ScratchRegisterScope::~ScratchRegisterScope() {
  if (spilled_) {
    resolver_->RestoreScratch(reg_);
  }
}

}  // namespace art