1 // Copyright (c) 2017, the R8 project authors. Please see the AUTHORS file 2 // for details. All rights reserved. Use of this source code is governed by a 3 // BSD-style license that can be found in the LICENSE file. 4 package com.android.tools.r8.ir.regalloc; 5 6 import com.android.tools.r8.ir.code.ConstNumber; 7 import com.android.tools.r8.ir.code.FixedRegisterValue; 8 import com.android.tools.r8.ir.code.Instruction; 9 import com.android.tools.r8.ir.code.InstructionListIterator; 10 import com.android.tools.r8.ir.code.Move; 11 import com.android.tools.r8.ir.code.MoveType; 12 import com.android.tools.r8.ir.code.Value; 13 import java.util.ArrayList; 14 import java.util.Deque; 15 import java.util.HashMap; 16 import java.util.Iterator; 17 import java.util.LinkedHashSet; 18 import java.util.LinkedList; 19 import java.util.List; 20 import java.util.Map; 21 import java.util.Set; 22 23 public class RegisterMoveScheduler { 24 // The set of moves to schedule. 25 private Set<RegisterMove> moveSet = new LinkedHashSet<>(); 26 // Mapping to keep track of which values currently corresponds to each other. 27 // This is initially an identity map but changes as we insert moves. 28 private Map<Integer, Integer> valueMap = new HashMap<>(); 29 // Number of temp registers used to schedule the moves. 30 private int usedTempRegisters = 0; 31 // Location at which to insert the scheduled moves. 32 private final InstructionListIterator insertAt; 33 // The first available temporary register. 34 private final int tempRegister; 35 RegisterMoveScheduler(InstructionListIterator insertAt, int tempRegister)36 public RegisterMoveScheduler(InstructionListIterator insertAt, int tempRegister) { 37 this.insertAt = insertAt; 38 this.tempRegister = tempRegister; 39 } 40 addMove(RegisterMove move)41 public void addMove(RegisterMove move) { 42 moveSet.add(move); 43 if (move.src != LinearScanRegisterAllocator.NO_REGISTER) { 44 valueMap.put(move.src, move.src); 45 } 46 valueMap.put(move.dst, move.dst); 47 } 48 schedule()49 public void schedule() { 50 // Worklist of moves that are ready to be inserted. 51 Deque<RegisterMove> worklist = new LinkedList<>(); 52 53 // Initialize worklist with the moves that do not interfere with other moves. 54 Iterator<RegisterMove> iterator = moveSet.iterator(); 55 while (iterator.hasNext()) { 56 RegisterMove move = iterator.next(); 57 if (!move.isBlocked(moveSet, valueMap)) { 58 worklist.addLast(move); 59 iterator.remove(); 60 } 61 } 62 63 // Process the worklist generating moves. If the worklist becomes empty while the move set 64 // still contains elements we need to use a temporary to break cycles. 65 while (!worklist.isEmpty() || !moveSet.isEmpty()) { 66 while (!worklist.isEmpty()) { 67 RegisterMove move = worklist.removeFirst(); 68 assert !move.isBlocked(moveSet, valueMap); 69 // Insert the move. 70 Integer generatedDest = createMove(move); 71 // Update the value map with the information that dest can be used instead of 72 // src starting now. 73 if (move.src != LinearScanRegisterAllocator.NO_REGISTER) { 74 valueMap.put(move.src, generatedDest); 75 } 76 // Iterate and find the moves that were blocked because they need to write to 77 // one of the move src. That is now valid because the move src is preserved in dest. 78 iterator = moveSet.iterator(); 79 while (iterator.hasNext()) { 80 RegisterMove other = iterator.next(); 81 if (!other.isBlocked(moveSet, valueMap)) { 82 worklist.addLast(other); 83 iterator.remove(); 84 } 85 } 86 } 87 if (!moveSet.isEmpty()) { 88 // The remaining moves are conflicting. Chose a move and unblock it by generating moves to 89 // temporary registers for its destination value(s). 90 RegisterMove move = pickMoveToUnblock(); 91 createMoveDestToTemp(move); 92 worklist.addLast(move); 93 } 94 } 95 } 96 getUsedTempRegisters()97 public int getUsedTempRegisters() { 98 return usedTempRegisters; 99 } 100 findMovesWithSrc(int src, MoveType type)101 private List<RegisterMove> findMovesWithSrc(int src, MoveType type) { 102 List<RegisterMove> result = new ArrayList<>(); 103 assert src != LinearScanRegisterAllocator.NO_REGISTER; 104 for (RegisterMove move : moveSet) { 105 if (move.src == LinearScanRegisterAllocator.NO_REGISTER) { 106 continue; 107 } 108 int moveSrc = valueMap.get(move.src); 109 if (moveSrc == src) { 110 result.add(move); 111 } else if (move.type == MoveType.WIDE && (moveSrc + 1) == src) { 112 result.add(move); 113 } else if (type == MoveType.WIDE && (moveSrc - 1) == src) { 114 result.add(move); 115 } 116 } 117 return result; 118 } 119 createMove(RegisterMove move)120 private Integer createMove(RegisterMove move) { 121 Instruction instruction; 122 Value to = new FixedRegisterValue(move.type, move.dst); 123 if (move.definition != null) { 124 ConstNumber number = move.definition.asConstNumber(); 125 instruction = new ConstNumber(number.type, to, number.getRawValue()); 126 } else { 127 Value from = new FixedRegisterValue(move.type, valueMap.get(move.src)); 128 instruction = new Move(to, from); 129 } 130 insertAt.add(instruction); 131 return move.dst; 132 133 } 134 createMoveDestToTemp(RegisterMove move)135 private void createMoveDestToTemp(RegisterMove move) { 136 // In order to unblock this move we might have to move more than one value to temporary 137 // registers if we are unlucky with the overlap for values that use two registers. 138 List<RegisterMove> movesWithSrc = findMovesWithSrc(move.dst, move.type); 139 assert movesWithSrc.size() > 0; 140 for (RegisterMove moveWithSrc : movesWithSrc) { 141 // TODO(ager): For now we always use a new temporary register whenever we have to unblock 142 // a move. The move scheduler can have multiple unblocking temps live at the same time 143 // and therefore we cannot have just one tempRegister (pair). However, we could check here 144 // if the previously used tempRegisters is still needed by any of the moves in the move set 145 // (taking the value map into account). If not, we can reuse the temp register instead 146 // of generating a new one. 147 Value to = new FixedRegisterValue(moveWithSrc.type, tempRegister + usedTempRegisters); 148 Value from = new FixedRegisterValue(moveWithSrc.type, valueMap.get(moveWithSrc.src)); 149 insertAt.add(new Move(to, from)); 150 valueMap.put(moveWithSrc.src, tempRegister + usedTempRegisters); 151 usedTempRegisters += moveWithSrc.type == MoveType.WIDE ? 2 : 1; 152 } 153 } 154 pickMoveToUnblock()155 private RegisterMove pickMoveToUnblock() { 156 Iterator<RegisterMove> iterator = moveSet.iterator(); 157 RegisterMove move = null; 158 // Pick a non-wide move to unblock if possible. 159 while (iterator.hasNext()) { 160 move = iterator.next(); 161 if (move.type != MoveType.WIDE) { 162 break; 163 } 164 } 165 iterator.remove(); 166 return move; 167 } 168 } 169