1 /* 2 * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 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.alloc.trace.TraceUtil.isTrivialTrace; 26 27 import java.util.ArrayList; 28 29 import org.graalvm.compiler.core.common.alloc.BiDirectionalTraceBuilder; 30 import org.graalvm.compiler.core.common.alloc.SingleBlockTraceBuilder; 31 import org.graalvm.compiler.core.common.alloc.Trace; 32 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult; 33 import org.graalvm.compiler.core.common.alloc.TraceBuilderResult.TrivialTracePredicate; 34 import org.graalvm.compiler.core.common.alloc.TraceStatisticsPrinter; 35 import org.graalvm.compiler.core.common.alloc.UniDirectionalTraceBuilder; 36 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 37 import org.graalvm.compiler.debug.DebugContext; 38 import org.graalvm.compiler.debug.GraalError; 39 import org.graalvm.compiler.lir.LIR; 40 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 41 import org.graalvm.compiler.lir.phases.AllocationPhase; 42 import org.graalvm.compiler.options.EnumOptionKey; 43 import org.graalvm.compiler.options.Option; 44 import org.graalvm.compiler.options.OptionKey; 45 import org.graalvm.compiler.options.OptionType; 46 import org.graalvm.compiler.options.OptionValues; 47 48 import jdk.vm.ci.code.TargetDescription; 49 50 public class TraceBuilderPhase extends AllocationPhase { 51 52 public enum TraceBuilder { 53 UniDirectional, 54 BiDirectional, 55 SingleBlock 56 } 57 58 public static class Options { 59 // @formatter:off 60 @Option(help = "Trace building algorithm.", type = OptionType.Debug) 61 public static final EnumOptionKey<TraceBuilder> TraceBuilding = new EnumOptionKey<>(TraceBuilder.UniDirectional); 62 @Option(help = "Schedule trivial traces as early as possible.", type = OptionType.Debug) 63 public static final OptionKey<Boolean> TraceRAScheduleTrivialTracesEarly = new OptionKey<>(true); 64 // @formatter:on 65 } 66 67 @Override 68 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, AllocationContext context) { 69 AbstractBlockBase<?>[] linearScanOrder = lirGenRes.getLIR().linearScanOrder(); 70 AbstractBlockBase<?> startBlock = linearScanOrder[0]; 71 LIR lir = lirGenRes.getLIR(); 72 assert startBlock.equals(lir.getControlFlowGraph().getStartBlock()); 73 74 final TraceBuilderResult traceBuilderResult = getTraceBuilderResult(lir, startBlock, linearScanOrder); 75 76 DebugContext debug = lir.getDebug(); 77 if (debug.isLogEnabled(DebugContext.BASIC_LEVEL)) { 78 ArrayList<Trace> traces = traceBuilderResult.getTraces(); 79 for (int i = 0; i < traces.size(); i++) { 80 Trace trace = traces.get(i); 81 debug.log(DebugContext.BASIC_LEVEL, "Trace %5d: %s%s", i, trace, isTrivialTrace(lirGenRes.getLIR(), trace) ? " (trivial)" : ""); 82 } 83 } 84 TraceStatisticsPrinter.printTraceStatistics(debug, traceBuilderResult, lirGenRes.getCompilationUnitName()); 85 debug.dump(DebugContext.VERBOSE_LEVEL, traceBuilderResult, "TraceBuilderResult"); 86 context.contextAdd(traceBuilderResult); 87 } 88 89 private static TraceBuilderResult getTraceBuilderResult(LIR lir, AbstractBlockBase<?> startBlock, AbstractBlockBase<?>[] linearScanOrder) { 90 TraceBuilderResult.TrivialTracePredicate pred = getTrivialTracePredicate(lir); 91 92 OptionValues options = lir.getOptions(); 93 TraceBuilder selectedTraceBuilder = Options.TraceBuilding.getValue(options); 94 DebugContext debug = lir.getDebug(); 95 debug.log(DebugContext.BASIC_LEVEL, "Building Traces using %s", selectedTraceBuilder); 96 switch (Options.TraceBuilding.getValue(options)) { 97 case SingleBlock: 98 return SingleBlockTraceBuilder.computeTraces(debug, startBlock, linearScanOrder, pred); 99 case BiDirectional: 100 return BiDirectionalTraceBuilder.computeTraces(debug, startBlock, linearScanOrder, pred); 101 case UniDirectional: 102 return UniDirectionalTraceBuilder.computeTraces(debug, startBlock, linearScanOrder, pred); 103 } 104 throw GraalError.shouldNotReachHere("Unknown trace building algorithm: " + Options.TraceBuilding.getValue(options)); 105 } 106 107 public static TraceBuilderResult.TrivialTracePredicate getTrivialTracePredicate(LIR lir) { 108 if (!Options.TraceRAScheduleTrivialTracesEarly.getValue(lir.getOptions())) { 109 return null; 110 } 111 return new TrivialTracePredicate() { 112 @Override 113 public boolean isTrivialTrace(Trace trace) { 114 return TraceUtil.isTrivialTrace(lir, trace); 115 } 116 }; 117 } 118 }