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 }