5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.lir.alloc.trace;
  24 
  25 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
  26 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.asShadowedRegisterValue;
  27 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.isShadowedRegisterValue;
  28 import static jdk.vm.ci.code.ValueUtil.asRegisterValue;
  29 import static jdk.vm.ci.code.ValueUtil.isIllegal;
  30 import static jdk.vm.ci.code.ValueUtil.isRegister;




  31 
  32 import java.util.List;

  33 
  34 import org.graalvm.compiler.core.common.alloc.Trace;
  35 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
  36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  37 import org.graalvm.compiler.debug.Debug;
  38 import org.graalvm.compiler.debug.Indent;
  39 import org.graalvm.compiler.lir.LIR;
  40 import org.graalvm.compiler.lir.LIRInstruction;


  41 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext;
  42 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
  43 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
  44 import org.graalvm.compiler.lir.phases.LIRPhase;
  45 import org.graalvm.compiler.lir.ssa.SSAUtil.PhiValueVisitor;
  46 import org.graalvm.compiler.lir.ssi.SSIUtil;
  47 
  48 import jdk.vm.ci.code.Architecture;
  49 import jdk.vm.ci.code.RegisterValue;
  50 import jdk.vm.ci.code.TargetDescription;
  51 import jdk.vm.ci.meta.AllocatableValue;
  52 import jdk.vm.ci.meta.Value;
  53 
  54 public final class TraceGlobalMoveResolutionPhase extends LIRPhase<TraceAllocationPhase.TraceAllocationContext> {
  55 
  56     /**
  57      * Abstract move resolver interface for testing.
  58      */
  59     public abstract static class MoveResolver {
  60         public abstract void addMapping(Value src, AllocatableValue dst, Value fromStack);
  61     }
  62 
  63     @Override
  64     protected void run(TargetDescription target, LIRGenerationResult lirGenRes, TraceAllocationContext context) {
  65         MoveFactory spillMoveFactory = context.spillMoveFactory;
  66         resolveGlobalDataFlow(context.resultTraces, lirGenRes, spillMoveFactory, target.arch);
  67     }
  68 
  69     @SuppressWarnings("try")
  70     private static void resolveGlobalDataFlow(TraceBuilderResult resultTraces, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory, Architecture arch) {
  71         LIR lir = lirGenRes.getLIR();
  72         /* Resolve trace global data-flow mismatch. */
  73         TraceGlobalMoveResolver moveResolver = new TraceGlobalMoveResolver(lirGenRes, spillMoveFactory, arch);
  74         PhiValueVisitor visitor = (Value phiIn, Value phiOut) -> {
  75             if (!isIllegal(phiIn)) {
  76                 addMapping(moveResolver, phiOut, phiIn);
  77             }
  78         };
  79 
  80         try (Indent indent = Debug.logAndIndent("Trace global move resolution")) {
  81             for (Trace trace : resultTraces.getTraces()) {
  82                 for (AbstractBlockBase<?> fromBlock : trace.getBlocks()) {
  83                     for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) {
  84                         if (resultTraces.getTraceForBlock(fromBlock) != resultTraces.getTraceForBlock(toBlock)) {
  85                             try (Indent indent0 = Debug.logAndIndent("Handle trace edge from %s (Trace%d) to %s (Trace%d)", fromBlock, resultTraces.getTraceForBlock(fromBlock).getId(), toBlock,
  86                                             resultTraces.getTraceForBlock(toBlock).getId())) {
  87 
  88                                 final List<LIRInstruction> instructions;
  89                                 final int insertIdx;
  90                                 if (fromBlock.getSuccessorCount() == 1) {
  91                                     instructions = lir.getLIRforBlock(fromBlock);
  92                                     insertIdx = instructions.size() - 1;
  93                                 } else {
  94                                     assert toBlock.getPredecessorCount() == 1;
  95                                     instructions = lir.getLIRforBlock(toBlock);
  96                                     insertIdx = 1;
  97                                 }
  98 
  99                                 moveResolver.setInsertPosition(instructions, insertIdx);
 100                                 SSIUtil.forEachValuePair(lir, toBlock, fromBlock, visitor);
 101                                 moveResolver.resolveAndAppendMoves();
 102                             }
 103                         }
 104                     }
 105                 }
 106             }
 107         }
 108     }
 109 







































 110     public static void addMapping(MoveResolver moveResolver, Value from, Value to) {
 111         assert !isIllegal(to);


 112         if (isShadowedRegisterValue(to)) {
 113             ShadowedRegisterValue toSh = asShadowedRegisterValue(to);
 114             addMappingToRegister(moveResolver, from, toSh.getRegister());
 115             addMappingToStackSlot(moveResolver, from, toSh.getStackSlot());
 116         } else {
 117             if (isRegister(to)) {
 118                 addMappingToRegister(moveResolver, from, asRegisterValue(to));
 119             } else {
 120                 assert isStackSlotValue(to) : "Expected stack slot: " + to;
 121                 addMappingToStackSlot(moveResolver, from, (AllocatableValue) to);
 122             }
 123         }
 124     }
 125 
 126     private static void addMappingToRegister(MoveResolver moveResolver, Value from, RegisterValue register) {
 127         if (isShadowedRegisterValue(from)) {
 128             RegisterValue fromReg = asShadowedRegisterValue(from).getRegister();
 129             AllocatableValue fromStack = asShadowedRegisterValue(from).getStackSlot();
 130             checkAndAddMapping(moveResolver, fromReg, register, fromStack);
 131         } else {

   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  */
  23 package org.graalvm.compiler.lir.alloc.trace;
  24 



  25 import static jdk.vm.ci.code.ValueUtil.asRegisterValue;
  26 import static jdk.vm.ci.code.ValueUtil.isIllegal;
  27 import static jdk.vm.ci.code.ValueUtil.isRegister;
  28 import static org.graalvm.compiler.lir.LIRValueUtil.isConstantValue;
  29 import static org.graalvm.compiler.lir.LIRValueUtil.isStackSlotValue;
  30 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.asShadowedRegisterValue;
  31 import static org.graalvm.compiler.lir.alloc.trace.TraceUtil.isShadowedRegisterValue;
  32 
  33 import java.util.ArrayList;
  34 import java.util.Arrays;
  35 
  36 import org.graalvm.compiler.core.common.alloc.Trace;
  37 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult;
  38 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase;
  39 import org.graalvm.compiler.debug.Debug;
  40 import org.graalvm.compiler.debug.Indent;
  41 import org.graalvm.compiler.lir.LIR;
  42 import org.graalvm.compiler.lir.LIRInstruction;
  43 import org.graalvm.compiler.lir.StandardOp.JumpOp;
  44 import org.graalvm.compiler.lir.StandardOp.LabelOp;
  45 import org.graalvm.compiler.lir.alloc.trace.TraceAllocationPhase.TraceAllocationContext;
  46 import org.graalvm.compiler.lir.gen.LIRGenerationResult;
  47 import org.graalvm.compiler.lir.gen.LIRGeneratorTool.MoveFactory;
  48 import org.graalvm.compiler.lir.phases.LIRPhase;
  49 import org.graalvm.compiler.lir.ssa.SSAUtil;

  50 
  51 import jdk.vm.ci.code.Architecture;
  52 import jdk.vm.ci.code.RegisterValue;
  53 import jdk.vm.ci.code.TargetDescription;
  54 import jdk.vm.ci.meta.AllocatableValue;
  55 import jdk.vm.ci.meta.Value;
  56 
  57 public final class TraceGlobalMoveResolutionPhase extends LIRPhase<TraceAllocationPhase.TraceAllocationContext> {
  58 
  59     /**
  60      * Abstract move resolver interface for testing.
  61      */
  62     public abstract static class MoveResolver {
  63         public abstract void addMapping(Value src, AllocatableValue dst, Value fromStack);
  64     }
  65 
  66     @Override
  67     protected void run(TargetDescription target, LIRGenerationResult lirGenRes, TraceAllocationContext context) {
  68         MoveFactory spillMoveFactory = context.spillMoveFactory;
  69         resolveGlobalDataFlow(context.resultTraces, lirGenRes, spillMoveFactory, target.arch, context.livenessInfo);
  70     }
  71 
  72     @SuppressWarnings("try")
  73     private static void resolveGlobalDataFlow(TraceBuilderResult resultTraces, LIRGenerationResult lirGenRes, MoveFactory spillMoveFactory, Architecture arch, GlobalLivenessInfo livenessInfo) {
  74         LIR lir = lirGenRes.getLIR();
  75         /* Resolve trace global data-flow mismatch. */
  76         TraceGlobalMoveResolver moveResolver = new TraceGlobalMoveResolver(lirGenRes, spillMoveFactory, arch);





  77 
  78         try (Indent indent = Debug.logAndIndent("Trace global move resolution")) {
  79             for (Trace trace : resultTraces.getTraces()) {
  80                 for (AbstractBlockBase<?> fromBlock : trace.getBlocks()) {
  81                     for (AbstractBlockBase<?> toBlock : fromBlock.getSuccessors()) {
  82                         if (resultTraces.getTraceForBlock(fromBlock) != resultTraces.getTraceForBlock(toBlock)) {
  83                             try (Indent indent0 = Debug.logAndIndent("Handle trace edge from %s (Trace%d) to %s (Trace%d)", fromBlock, resultTraces.getTraceForBlock(fromBlock).getId(), toBlock,
  84                                             resultTraces.getTraceForBlock(toBlock).getId())) {
  85 
  86                                 final ArrayList<LIRInstruction> instructions;
  87                                 final int insertIdx;
  88                                 if (fromBlock.getSuccessorCount() == 1) {
  89                                     instructions = lir.getLIRforBlock(fromBlock);
  90                                     insertIdx = instructions.size() - 1;
  91                                 } else {
  92                                     assert toBlock.getPredecessorCount() == 1;
  93                                     instructions = lir.getLIRforBlock(toBlock);
  94                                     insertIdx = 1;
  95                                 }
  96 
  97                                 moveResolver.setInsertPosition(instructions, insertIdx);
  98                                 resolveEdge(lir, livenessInfo, moveResolver, fromBlock, toBlock);
  99                                 moveResolver.resolveAndAppendMoves();
 100                             }
 101                         }
 102                     }
 103                 }
 104             }
 105         }
 106     }
 107 
 108     private static void resolveEdge(LIR lir, GlobalLivenessInfo livenessInfo, TraceGlobalMoveResolver moveResolver, AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock) {
 109         assert verifyEdge(fromBlock, toBlock);
 110 
 111         if (SSAUtil.isMerge(toBlock)) {
 112             // PHI
 113             JumpOp blockEnd = SSAUtil.phiOut(lir, fromBlock);
 114             LabelOp label = SSAUtil.phiIn(lir, toBlock);
 115 
 116             for (int i = 0; i < label.getPhiSize(); i++) {
 117                 Value in = label.getIncomingValue(i);
 118                 Value out = blockEnd.getOutgoingValue(i);
 119                 addMapping(moveResolver, out, in);
 120             }
 121         }
 122         // GLI
 123         Value[] locFrom = livenessInfo.getOutLocation(fromBlock);
 124         Value[] locTo = livenessInfo.getInLocation(toBlock);
 125         assert locFrom.length == locTo.length;
 126 
 127         for (int i = 0; i < locFrom.length; i++) {
 128             addMapping(moveResolver, locFrom[i], locTo[i]);
 129         }
 130     }
 131 
 132     private static boolean isIllegalDestination(Value to) {
 133         return isIllegal(to) || isConstantValue(to);
 134     }
 135 
 136     private static boolean verifyEdge(AbstractBlockBase<?> fromBlock, AbstractBlockBase<?> toBlock) {
 137         assert Arrays.asList(toBlock.getPredecessors()).contains(fromBlock) : String.format("%s not in predecessor list: %s", fromBlock,
 138                         Arrays.toString(toBlock.getPredecessors()));
 139         assert fromBlock.getSuccessorCount() == 1 || toBlock.getPredecessorCount() == 1 : String.format("Critical Edge? %s has %d successors and %s has %d predecessors",
 140                         fromBlock,
 141                         fromBlock.getSuccessorCount(), toBlock, toBlock.getPredecessorCount());
 142         assert Arrays.asList(fromBlock.getSuccessors()).contains(toBlock) : String.format("Predecessor block %s has wrong successor: %s, should contain: %s", fromBlock,
 143                         Arrays.toString(fromBlock.getSuccessors()), toBlock);
 144         return true;
 145     }
 146 
 147     public static void addMapping(MoveResolver moveResolver, Value from, Value to) {
 148         if (isIllegalDestination(to)) {
 149             return;
 150         }
 151         if (isShadowedRegisterValue(to)) {
 152             ShadowedRegisterValue toSh = asShadowedRegisterValue(to);
 153             addMappingToRegister(moveResolver, from, toSh.getRegister());
 154             addMappingToStackSlot(moveResolver, from, toSh.getStackSlot());
 155         } else {
 156             if (isRegister(to)) {
 157                 addMappingToRegister(moveResolver, from, asRegisterValue(to));
 158             } else {
 159                 assert isStackSlotValue(to) : "Expected stack slot: " + to;
 160                 addMappingToStackSlot(moveResolver, from, (AllocatableValue) to);
 161             }
 162         }
 163     }
 164 
 165     private static void addMappingToRegister(MoveResolver moveResolver, Value from, RegisterValue register) {
 166         if (isShadowedRegisterValue(from)) {
 167             RegisterValue fromReg = asShadowedRegisterValue(from).getRegister();
 168             AllocatableValue fromStack = asShadowedRegisterValue(from).getStackSlot();
 169             checkAndAddMapping(moveResolver, fromReg, register, fromStack);
 170         } else {