1 /* 2 * Copyright (c) 2014, 2015, 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 24 25 package org.graalvm.compiler.lir.constopt; 26 27 import static org.graalvm.compiler.lir.LIRValueUtil.isVariable; 28 import static org.graalvm.compiler.lir.phases.LIRPhase.Options.LIROptimization; 29 30 import java.util.ArrayDeque; 31 import java.util.ArrayList; 32 import java.util.BitSet; 33 import java.util.Collections; 34 import java.util.Deque; 35 import java.util.EnumSet; 36 import java.util.List; 37 38 import org.graalvm.compiler.core.common.cfg.AbstractBlockBase; 39 import org.graalvm.compiler.core.common.cfg.BlockMap; 40 import org.graalvm.compiler.debug.CounterKey; 41 import org.graalvm.compiler.debug.DebugContext; 42 import org.graalvm.compiler.debug.Indent; 43 import org.graalvm.compiler.lir.InstructionValueConsumer; 44 import org.graalvm.compiler.lir.LIR; 45 import org.graalvm.compiler.lir.LIRInsertionBuffer; 46 import org.graalvm.compiler.lir.LIRInstruction; 47 import org.graalvm.compiler.lir.LIRInstruction.OperandFlag; 48 import org.graalvm.compiler.lir.LIRInstruction.OperandMode; 49 import org.graalvm.compiler.lir.StandardOp.LoadConstantOp; 50 import org.graalvm.compiler.lir.ValueConsumer; 51 import org.graalvm.compiler.lir.Variable; 52 import org.graalvm.compiler.lir.constopt.ConstantTree.Flags; 53 import org.graalvm.compiler.lir.constopt.ConstantTree.NodeCost; 54 import org.graalvm.compiler.lir.gen.LIRGenerationResult; 55 import org.graalvm.compiler.lir.gen.LIRGeneratorTool; 56 import org.graalvm.compiler.lir.phases.PreAllocationOptimizationPhase; 57 import org.graalvm.compiler.options.NestedBooleanOptionKey; 58 import org.graalvm.compiler.options.Option; 59 import org.graalvm.compiler.options.OptionType; 60 61 import jdk.vm.ci.code.TargetDescription; 62 import jdk.vm.ci.meta.Constant; 63 import jdk.vm.ci.meta.Value; 64 import jdk.vm.ci.meta.ValueKind; 65 66 /** 67 * This optimization tries to improve the handling of constants by replacing a single definition of 68 * a constant, which is potentially scheduled into a block with high frequency, with one or more 69 * definitions in blocks with a lower frequency. 70 */ 71 public final class ConstantLoadOptimization extends PreAllocationOptimizationPhase { 72 73 public static class Options { 74 // @formatter:off 75 @Option(help = "Enable constant load optimization.", type = OptionType.Debug) 76 public static final NestedBooleanOptionKey LIROptConstantLoadOptimization = new NestedBooleanOptionKey(LIROptimization, true); 77 // @formatter:on 78 } 79 80 @Override 81 protected void run(TargetDescription target, LIRGenerationResult lirGenRes, PreAllocationOptimizationContext context) { 82 LIRGeneratorTool lirGen = context.lirGen; 83 new Optimization(lirGenRes.getLIR(), lirGen).apply(); 84 } 85 86 private static final CounterKey constantsTotal = DebugContext.counter("ConstantLoadOptimization[total]"); 87 private static final CounterKey phiConstantsSkipped = DebugContext.counter("ConstantLoadOptimization[PhisSkipped]"); 88 private static final CounterKey singleUsageConstantsSkipped = DebugContext.counter("ConstantLoadOptimization[SingleUsageSkipped]"); 89 private static final CounterKey usageAtDefinitionSkipped = DebugContext.counter("ConstantLoadOptimization[UsageAtDefinitionSkipped]"); 90 private static final CounterKey materializeAtDefinitionSkipped = DebugContext.counter("ConstantLoadOptimization[MaterializeAtDefinitionSkipped]"); 91 private static final CounterKey constantsOptimized = DebugContext.counter("ConstantLoadOptimization[optimized]"); 92 93 private static final class Optimization { 94 private final LIR lir; 95 private final LIRGeneratorTool lirGen; 96 private final VariableMap<DefUseTree> map; 97 private final BitSet phiConstants; 98 private final BitSet defined; 99 private final BlockMap<List<UseEntry>> blockMap; 100 private final BlockMap<LIRInsertionBuffer> insertionBuffers; 101 private final DebugContext debug; 102 103 private Optimization(LIR lir, LIRGeneratorTool lirGen) { 104 this.lir = lir; 105 this.debug = lir.getDebug(); 106 this.lirGen = lirGen; 107 this.map = new VariableMap<>(); 108 this.phiConstants = new BitSet(); 109 this.defined = new BitSet(); 110 this.insertionBuffers = new BlockMap<>(lir.getControlFlowGraph()); 111 this.blockMap = new BlockMap<>(lir.getControlFlowGraph()); 112 } 113 114 @SuppressWarnings("try") 115 private void apply() { 116 try (Indent indent = debug.logAndIndent("ConstantLoadOptimization")) { 117 try (DebugContext.Scope s = debug.scope("BuildDefUseTree")) { 118 // build DefUseTree 119 for (AbstractBlockBase<?> b : lir.getControlFlowGraph().getBlocks()) { 120 this.analyzeBlock(b); 121 } 122 // remove all with only one use 123 map.filter(t -> { 124 if (t.usageCount() > 1) { 125 return true; 126 } else { 127 singleUsageConstantsSkipped.increment(debug); 128 return false; 129 } 130 }); 131 // collect block map 132 map.forEach(tree -> tree.forEach(this::addUsageToBlockMap)); 133 } catch (Throwable e) { 134 throw debug.handle(e); 135 } 136 137 try (DebugContext.Scope s = debug.scope("BuildConstantTree")) { 138 // create ConstantTree 139 map.forEach(this::createConstantTree); 140 141 // insert moves, delete null instructions and reset instruction ids 142 for (AbstractBlockBase<?> b : lir.getControlFlowGraph().getBlocks()) { 143 this.rewriteBlock(b); 144 } 145 146 assert verifyStates(); 147 } catch (Throwable e) { 148 throw debug.handle(e); 149 } 150 } 151 } 152 153 private boolean verifyStates() { 154 map.forEach(this::verifyStateUsage); 155 return true; 156 } 157 158 private void verifyStateUsage(DefUseTree tree) { 159 Variable var = tree.getVariable(); 160 ValueConsumer stateConsumer = new ValueConsumer() { 161 162 @Override 163 public void visitValue(Value operand, OperandMode mode, EnumSet<OperandFlag> flags) { 164 assert !operand.equals(var) : "constant usage through variable in frame state " + var; 165 } 166 }; 167 for (AbstractBlockBase<?> block : lir.getControlFlowGraph().getBlocks()) { 168 for (LIRInstruction inst : lir.getLIRforBlock(block)) { 169 // set instruction id to the index in the lir instruction list 170 inst.visitEachState(stateConsumer); 171 } 172 } 173 } 174 175 private static boolean isConstantLoad(LIRInstruction inst) { 176 if (!LoadConstantOp.isLoadConstantOp(inst)) { 177 return false; 178 } 179 return isVariable(LoadConstantOp.asLoadConstantOp(inst).getResult()); 180 } 181 182 private void addUsageToBlockMap(UseEntry entry) { 183 AbstractBlockBase<?> block = entry.getBlock(); 184 List<UseEntry> list = blockMap.get(block); 185 if (list == null) { 186 list = new ArrayList<>(); 187 blockMap.put(block, list); 188 } 189 list.add(entry); 190 } 191 192 /** 193 * Collects def-use information for a {@code block}. 194 */ 195 @SuppressWarnings("try") 196 private void analyzeBlock(AbstractBlockBase<?> block) { 197 try (Indent indent = debug.logAndIndent("Block: %s", block)) { 198 199 InstructionValueConsumer loadConsumer = (instruction, value, mode, flags) -> { 200 if (isVariable(value)) { 201 Variable var = (Variable) value; 202 203 if (!phiConstants.get(var.index)) { 204 if (!defined.get(var.index)) { 205 defined.set(var.index); 206 if (isConstantLoad(instruction)) { 207 debug.log("constant load: %s", instruction); 208 map.put(var, new DefUseTree(instruction, block)); 209 constantsTotal.increment(debug); 210 } 211 } else { 212 // Variable is redefined, this only happens for constant loads 213 // introduced by phi resolution -> ignore. 214 DefUseTree removed = map.remove(var); 215 if (removed != null) { 216 phiConstantsSkipped.increment(debug); 217 } 218 phiConstants.set(var.index); 219 debug.log(DebugContext.VERBOSE_LEVEL, "Removing phi variable: %s", var); 220 } 221 } else { 222 assert defined.get(var.index) : "phi but not defined? " + var; 223 } 224 } 225 }; 226 227 InstructionValueConsumer useConsumer = (instruction, value, mode, flags) -> { 228 if (isVariable(value)) { 229 Variable var = (Variable) value; 230 if (!phiConstants.get(var.index)) { 231 DefUseTree tree = map.get(var); 232 if (tree != null) { 233 tree.addUsage(block, instruction, value); 234 debug.log("usage of %s : %s", var, instruction); 235 } 236 } 237 } 238 }; 239 240 int opId = 0; 241 for (LIRInstruction inst : lir.getLIRforBlock(block)) { 242 // set instruction id to the index in the lir instruction list 243 inst.setId(opId++); 244 inst.visitEachOutput(loadConsumer); 245 inst.visitEachInput(useConsumer); 246 inst.visitEachAlive(useConsumer); 247 248 } 249 } 250 } 251 252 /** 253 * Creates the dominator tree and searches for an solution. 254 */ 255 @SuppressWarnings("try") 256 private void createConstantTree(DefUseTree tree) { 257 ConstantTree constTree = new ConstantTree(lir.getControlFlowGraph(), tree); 258 constTree.set(Flags.SUBTREE, tree.getBlock()); 259 tree.forEach(u -> constTree.set(Flags.USAGE, u.getBlock())); 260 261 if (constTree.get(Flags.USAGE, tree.getBlock())) { 262 // usage in the definition block -> no optimization 263 usageAtDefinitionSkipped.increment(debug); 264 return; 265 } 266 267 constTree.markBlocks(); 268 269 NodeCost cost = ConstantTreeAnalyzer.analyze(debug, constTree, tree.getBlock()); 270 int usageCount = cost.getUsages().size(); 271 assert usageCount == tree.usageCount() : "Usage count differs: " + usageCount + " vs. " + tree.usageCount(); 272 273 if (debug.isLogEnabled()) { 274 try (Indent i = debug.logAndIndent("Variable: %s, Block: %s, freq.: %f", tree.getVariable(), tree.getBlock(), tree.getBlock().getRelativeFrequency())) { 275 debug.log("Usages result: %s", cost); 276 } 277 278 } 279 280 if (cost.getNumMaterializations() > 1 || cost.getBestCost() < tree.getBlock().getRelativeFrequency()) { 281 try (DebugContext.Scope s = debug.scope("CLOmodify", constTree); Indent i = debug.logAndIndent("Replacing %s = %s", tree.getVariable(), tree.getConstant().toValueString())) { 282 // mark original load for removal 283 deleteInstruction(tree); 284 constantsOptimized.increment(debug); 285 286 // collect result 287 createLoads(tree, constTree, tree.getBlock()); 288 289 } catch (Throwable e) { 290 throw debug.handle(e); 291 } 292 } else { 293 // no better solution found 294 materializeAtDefinitionSkipped.increment(debug); 295 } 296 debug.dump(DebugContext.DETAILED_LEVEL, constTree, "ConstantTree for %s", tree.getVariable()); 297 } 298 299 private void createLoads(DefUseTree tree, ConstantTree constTree, AbstractBlockBase<?> startBlock) { 300 Deque<AbstractBlockBase<?>> worklist = new ArrayDeque<>(); 301 worklist.add(startBlock); 302 while (!worklist.isEmpty()) { 303 AbstractBlockBase<?> block = worklist.pollLast(); 304 if (constTree.get(Flags.CANDIDATE, block)) { 305 constTree.set(Flags.MATERIALIZE, block); 306 // create and insert load 307 insertLoad(tree.getConstant(), tree.getVariable().getValueKind(), block, constTree.getCost(block).getUsages()); 308 } else { 309 AbstractBlockBase<?> dominated = block.getFirstDominated(); 310 while (dominated != null) { 311 if (constTree.isMarked(dominated)) { 312 worklist.addLast(dominated); 313 } 314 dominated = dominated.getDominatedSibling(); 315 } 316 } 317 } 318 } 319 320 private void insertLoad(Constant constant, ValueKind<?> kind, AbstractBlockBase<?> block, List<UseEntry> usages) { 321 assert usages != null && usages.size() > 0 : String.format("No usages %s %s %s", constant, block, usages); 322 // create variable 323 Variable variable = lirGen.newVariable(kind); 324 // create move 325 LIRInstruction move = lirGen.getSpillMoveFactory().createLoad(variable, constant); 326 // insert instruction 327 getInsertionBuffer(block).append(1, move); 328 debug.log("new move (%s) and inserted in block %s", move, block); 329 // update usages 330 for (UseEntry u : usages) { 331 u.setValue(variable); 332 debug.log("patched instruction %s", u.getInstruction()); 333 } 334 } 335 336 /** 337 * Inserts the constant loads created in {@link #createConstantTree} and deletes the 338 * original definition. 339 */ 340 private void rewriteBlock(AbstractBlockBase<?> block) { 341 // insert moves 342 LIRInsertionBuffer buffer = insertionBuffers.get(block); 343 if (buffer != null) { 344 assert buffer.initialized() : "not initialized?"; 345 buffer.finish(); 346 } 347 348 // delete instructions 349 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block); 350 boolean hasDead = false; 351 for (LIRInstruction inst : instructions) { 352 if (inst == null) { 353 hasDead = true; 354 } else { 355 inst.setId(-1); 356 } 357 } 358 if (hasDead) { 359 // Remove null values from the list. 360 instructions.removeAll(Collections.singleton(null)); 361 } 362 } 363 364 private void deleteInstruction(DefUseTree tree) { 365 AbstractBlockBase<?> block = tree.getBlock(); 366 LIRInstruction instruction = tree.getInstruction(); 367 debug.log("deleting instruction %s from block %s", instruction, block); 368 lir.getLIRforBlock(block).set(instruction.id(), null); 369 } 370 371 private LIRInsertionBuffer getInsertionBuffer(AbstractBlockBase<?> block) { 372 LIRInsertionBuffer insertionBuffer = insertionBuffers.get(block); 373 if (insertionBuffer == null) { 374 insertionBuffer = new LIRInsertionBuffer(); 375 insertionBuffers.put(block, insertionBuffer); 376 assert !insertionBuffer.initialized() : "already initialized?"; 377 ArrayList<LIRInstruction> instructions = lir.getLIRforBlock(block); 378 insertionBuffer.init(instructions); 379 } 380 return insertionBuffer; 381 } 382 } 383 }