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