| // Copyright (c) 2012, the Dart project authors. Please see the AUTHORS file |
| // for details. All rights reserved. Use of this source code is governed by a |
| // BSD-style license that can be found in the LICENSE file. |
| |
| import '../constants/values.dart'; |
| import '../elements/entities.dart'; |
| import '../js_backend/js_backend.dart'; |
| import '../js_backend/interceptor_data.dart'; |
| import '../options.dart'; |
| import '../types/abstract_value_domain.dart'; |
| import '../universe/selector.dart' show Selector; |
| import '../world.dart' show JClosedWorld; |
| import 'nodes.dart'; |
| |
| /** |
| * Replaces some instructions with specialized versions to make codegen easier. |
| * Caches codegen information on nodes. |
| */ |
| class SsaInstructionSelection extends HBaseVisitor { |
| final JClosedWorld _closedWorld; |
| final InterceptorData _interceptorData; |
| HGraph graph; |
| |
| SsaInstructionSelection(this._closedWorld, this._interceptorData); |
| |
| AbstractValueDomain get _abstractValueDomain => |
| _closedWorld.abstractValueDomain; |
| |
| void visitGraph(HGraph graph) { |
| this.graph = graph; |
| visitDominatorTree(graph); |
| } |
| |
| visitBasicBlock(HBasicBlock block) { |
| HInstruction instruction = block.first; |
| while (instruction != null) { |
| HInstruction next = instruction.next; |
| HInstruction replacement = instruction.accept(this); |
| if (replacement != instruction && replacement != null) { |
| block.rewrite(instruction, replacement); |
| |
| // If the replacement instruction does not know its source element, use |
| // the source element of the instruction. |
| if (replacement.sourceElement == null) { |
| replacement.sourceElement = instruction.sourceElement; |
| } |
| if (replacement.sourceInformation == null) { |
| replacement.sourceInformation = instruction.sourceInformation; |
| } |
| if (!replacement.isInBasicBlock()) { |
| // The constant folding can return an instruction that is already |
| // part of the graph (like an input), so we only add the replacement |
| // if necessary. |
| block.addAfter(instruction, replacement); |
| // Visit the replacement as the next instruction in case it can also |
| // be constant folded away. |
| next = replacement; |
| } |
| block.remove(instruction); |
| } |
| instruction = next; |
| } |
| } |
| |
| HInstruction visitInstruction(HInstruction node) { |
| return node; |
| } |
| |
| HInstruction visitIs(HIs node) { |
| if (node.kind == HIs.RAW_CHECK) { |
| HInstruction interceptor = node.interceptor; |
| if (interceptor != null) { |
| return new HIsViaInterceptor( |
| node.typeExpression, interceptor, _abstractValueDomain.boolType); |
| } |
| } |
| return node; |
| } |
| |
| HInstruction visitIdentity(HIdentity node) { |
| node.singleComparisonOp = simpleOp(node.left, node.right); |
| return node; |
| } |
| |
| /// Returns the single JavaScript comparison (`==` or `===`) if that |
| /// implements `identical(left, right)`, or returns `null` if a more complex |
| /// expression is needed. |
| String simpleOp(HInstruction left, HInstruction right) { |
| AbstractValue leftType = left.instructionType; |
| AbstractValue rightType = right.instructionType; |
| if (_abstractValueDomain.canBeNull(leftType) && |
| _abstractValueDomain.canBeNull(rightType)) { |
| // Can't use `===` on Dart `null` since it is implemented by JavaScript |
| // `null` and `undefined`. |
| if (left.isConstantNull() || right.isConstantNull()) { |
| return '=='; |
| } |
| if (_abstractValueDomain.isNumberOrNull(leftType) && |
| _abstractValueDomain.isNumberOrNull(rightType)) { |
| return '=='; |
| } |
| if (_abstractValueDomain.isStringOrNull(leftType) && |
| _abstractValueDomain.isStringOrNull(rightType)) { |
| return '=='; |
| } |
| if (_abstractValueDomain.isBooleanOrNull(leftType) && |
| _abstractValueDomain.isBooleanOrNull(rightType)) { |
| return '=='; |
| } |
| |
| // TODO(34439): There are more cases that can compile to `==` without |
| // triggering a conversion in the JavaScript evaluation. `==` will work |
| // for most Dart objects, but we have to ensure neither side can be a |
| // JavaScript Number, String, Symbol or Boolean. |
| return null; |
| } |
| return '==='; |
| } |
| |
| HInstruction visitInvokeDynamic(HInvokeDynamic node) { |
| if (node.isInterceptedCall) { |
| tryReplaceInterceptorWithDummy(node, node.selector, node.mask); |
| } |
| return node; |
| } |
| |
| HInstruction visitInvokeSuper(HInvokeSuper node) { |
| if (node.isInterceptedCall) { |
| AbstractValue mask = node.getDartReceiver(_closedWorld).instructionType; |
| tryReplaceInterceptorWithDummy(node, node.selector, mask); |
| } |
| return node; |
| } |
| |
| void tryReplaceInterceptorWithDummy( |
| HInvoke node, Selector selector, AbstractValue mask) { |
| // Calls of the form |
| // |
| // a.foo$1(a, x) |
| // |
| // where the interceptor calling convention is used come from recognizing |
| // that 'a' is a 'self-interceptor'. If the selector matches only methods |
| // that ignore the explicit receiver parameter, replace occurences of the |
| // receiver argument with a dummy receiver '0': |
| // |
| // a.foo$1(a, x) ---> a.foo$1(0, x) |
| // |
| // This often reduces the number of references to 'a' to one, allowing 'a' |
| // to be generated at use to avoid a temporary, e.g. |
| // |
| // t1 = b.get$thing(); |
| // t1.foo$1(t1, x) |
| // ---> |
| // b.get$thing().foo$1(0, x) |
| // |
| |
| // TODO(15933): Make automatically generated property extraction closures |
| // work with the dummy receiver optimization. |
| if (selector.isGetter) return; |
| |
| // This assignment of inputs is uniform for HInvokeDynamic and HInvokeSuper. |
| HInstruction interceptor = node.inputs[0]; |
| HInstruction receiverArgument = node.inputs[1]; |
| |
| if (interceptor.nonCheck() == receiverArgument.nonCheck()) { |
| if (_interceptorData.isInterceptedSelector(selector) && |
| !_interceptorData.isInterceptedMixinSelector( |
| selector, mask, _closedWorld)) { |
| ConstantValue constant = new SyntheticConstantValue( |
| SyntheticConstantKind.DUMMY_INTERCEPTOR, |
| receiverArgument.instructionType); |
| HConstant dummy = graph.addConstant(constant, _closedWorld); |
| receiverArgument.usedBy.remove(node); |
| node.inputs[1] = dummy; |
| dummy.usedBy.add(node); |
| } |
| } |
| } |
| |
| HInstruction visitFieldSet(HFieldSet setter) { |
| // Pattern match |
| // t1 = x.f; t2 = t1 + 1; x.f = t2; use(t2) --> ++x.f |
| // t1 = x.f; t2 = t1 op y; x.f = t2; use(t2) --> x.f op= y |
| // t1 = x.f; t2 = t1 + 1; x.f = t2; use(t1) --> x.f++ |
| HBasicBlock block = setter.block; |
| HInstruction op = setter.value; |
| HInstruction receiver = setter.receiver; |
| |
| bool isMatchingRead(HInstruction candidate) { |
| if (candidate is HFieldGet) { |
| if (candidate.element != setter.element) return false; |
| if (candidate.receiver != setter.receiver) return false; |
| // Recognize only three instructions in sequence in the same block. This |
| // could be broadened to allow non-interfering interleaved instructions. |
| if (op.block != block) return false; |
| if (candidate.block != block) return false; |
| if (setter.previous != op) return false; |
| if (op.previous != candidate) return false; |
| return true; |
| } |
| return false; |
| } |
| |
| HInstruction noMatchingRead() { |
| // If we have other HFieldSet optimizations, they go here. |
| return null; |
| } |
| |
| HInstruction replaceOp(HInstruction replacement, HInstruction getter) { |
| block.addBefore(setter, replacement); |
| block.remove(setter); |
| block.rewrite(op, replacement); |
| block.remove(op); |
| block.remove(getter); |
| return null; |
| } |
| |
| HInstruction plusOrMinus(String assignOp, String incrementOp) { |
| HInvokeBinary binary = op; |
| HInstruction left = binary.left; |
| HInstruction right = binary.right; |
| if (isMatchingRead(left)) { |
| if (left.usedBy.length == 1) { |
| if (right is HConstant && right.constant.isOne) { |
| HInstruction rmw = new HReadModifyWrite.preOp( |
| setter.element, incrementOp, receiver, op.instructionType); |
| return replaceOp(rmw, left); |
| } else { |
| HInstruction rmw = new HReadModifyWrite.assignOp( |
| setter.element, assignOp, receiver, right, op.instructionType); |
| return replaceOp(rmw, left); |
| } |
| } else if (op.usedBy.length == 1 && |
| right is HConstant && |
| right.constant.isOne) { |
| HInstruction rmw = new HReadModifyWrite.postOp( |
| setter.element, incrementOp, receiver, op.instructionType); |
| block.addAfter(left, rmw); |
| block.remove(setter); |
| block.remove(op); |
| block.rewrite(left, rmw); |
| block.remove(left); |
| return null; |
| } |
| } |
| return noMatchingRead(); |
| } |
| |
| HInstruction simple( |
| String assignOp, HInstruction left, HInstruction right) { |
| if (isMatchingRead(left)) { |
| if (left.usedBy.length == 1) { |
| HInstruction rmw = new HReadModifyWrite.assignOp( |
| setter.element, assignOp, receiver, right, op.instructionType); |
| return replaceOp(rmw, left); |
| } |
| } |
| return noMatchingRead(); |
| } |
| |
| HInstruction simpleBinary(String assignOp) { |
| HInvokeBinary binary = op; |
| return simple(assignOp, binary.left, binary.right); |
| } |
| |
| HInstruction bitop(String assignOp) { |
| // HBitAnd, HBitOr etc. are more difficult because HBitAnd(a.x, y) |
| // sometimes needs to be forced to unsigned: a.x = (a.x & y) >>> 0. |
| if (op.isUInt31(_abstractValueDomain)) return simpleBinary(assignOp); |
| return noMatchingRead(); |
| } |
| |
| if (op is HAdd) return plusOrMinus('+', '++'); |
| if (op is HSubtract) return plusOrMinus('-', '--'); |
| |
| if (op is HStringConcat) return simple('+', op.left, op.right); |
| |
| if (op is HMultiply) return simpleBinary('*'); |
| if (op is HDivide) return simpleBinary('/'); |
| |
| if (op is HBitAnd) return bitop('&'); |
| if (op is HBitOr) return bitop('|'); |
| if (op is HBitXor) return bitop('^'); |
| |
| return noMatchingRead(); |
| } |
| } |
| |
| /** |
| * Remove [HTypeKnown] instructions from the graph, to make codegen |
| * analysis easier. |
| */ |
| class SsaTypeKnownRemover extends HBaseVisitor { |
| void visitGraph(HGraph graph) { |
| visitDominatorTree(graph); |
| } |
| |
| void visitBasicBlock(HBasicBlock block) { |
| HInstruction instruction = block.first; |
| while (instruction != null) { |
| HInstruction next = instruction.next; |
| instruction.accept(this); |
| instruction = next; |
| } |
| } |
| |
| void visitTypeKnown(HTypeKnown instruction) { |
| for (HInstruction user in instruction.usedBy) { |
| if (user is HTypeConversion) { |
| user.inputType = instruction.instructionType; |
| } |
| } |
| instruction.block.rewrite(instruction, instruction.checkedInput); |
| instruction.block.remove(instruction); |
| } |
| } |
| |
| /** |
| * Remove [HTypeConversion] instructions from the graph in '--trust-primitives' |
| * mode. |
| */ |
| class SsaTrustedCheckRemover extends HBaseVisitor { |
| final CompilerOptions _options; |
| |
| SsaTrustedCheckRemover(this._options); |
| |
| void visitGraph(HGraph graph) { |
| if (!_options.trustPrimitives) return; |
| visitDominatorTree(graph); |
| } |
| |
| void visitBasicBlock(HBasicBlock block) { |
| HInstruction instruction = block.first; |
| while (instruction != null) { |
| HInstruction next = instruction.next; |
| instruction.accept(this); |
| instruction = next; |
| } |
| } |
| |
| void visitTypeConversion(HTypeConversion instruction) { |
| if (instruction.isReceiverTypeCheck || instruction.isArgumentTypeCheck) { |
| instruction.block.rewrite(instruction, instruction.checkedInput); |
| instruction.block.remove(instruction); |
| } |
| } |
| } |
| |
| /** |
| * Instead of emitting each SSA instruction with a temporary variable |
| * mark instructions that can be emitted at their use-site. |
| * For example, in: |
| * t0 = 4; |
| * t1 = 3; |
| * t2 = add(t0, t1); |
| * t0 and t1 would be marked and the resulting code would then be: |
| * t2 = add(4, 3); |
| */ |
| class SsaInstructionMerger extends HBaseVisitor { |
| final AbstractValueDomain _abstractValueDomain; |
| final SuperMemberData _superMemberData; |
| /** |
| * List of [HInstruction] that the instruction merger expects in |
| * order when visiting the inputs of an instruction. |
| */ |
| List<HInstruction> expectedInputs; |
| /** |
| * Set of pure [HInstruction] that the instruction merger expects to |
| * find. The order of pure instructions do not matter, as they will |
| * not be affected by side effects. |
| */ |
| Set<HInstruction> pureInputs; |
| Set<HInstruction> generateAtUseSite; |
| |
| void markAsGenerateAtUseSite(HInstruction instruction) { |
| assert(!instruction.isJsStatement()); |
| generateAtUseSite.add(instruction); |
| } |
| |
| SsaInstructionMerger( |
| this._abstractValueDomain, this.generateAtUseSite, this._superMemberData); |
| |
| void visitGraph(HGraph graph) { |
| visitDominatorTree(graph); |
| } |
| |
| void analyzeInputs(HInstruction user, int start) { |
| List<HInstruction> inputs = user.inputs; |
| for (int i = start; i < inputs.length; i++) { |
| HInstruction input = inputs[i]; |
| if (!generateAtUseSite.contains(input) && |
| !input.isCodeMotionInvariant() && |
| input.usedBy.length == 1 && |
| input is! HPhi && |
| input is! HLocalValue && |
| !input.isJsStatement()) { |
| if (isEffectivelyPure(input)) { |
| // Only consider a pure input if it is in the same loop. |
| // Otherwise, we might move GVN'ed instruction back into the |
| // loop. |
| if (user.hasSameLoopHeaderAs(input)) { |
| // Move it closer to [user], so that instructions in |
| // between do not prevent making it generate at use site. |
| input.moveBefore(user); |
| pureInputs.add(input); |
| // Previous computations done on [input] are now invalid |
| // because we moved [input] to another place. So all |
| // non code motion invariant instructions need |
| // to be removed from the [generateAtUseSite] set. |
| input.inputs.forEach((instruction) { |
| if (!instruction.isCodeMotionInvariant()) { |
| generateAtUseSite.remove(instruction); |
| } |
| }); |
| // Visit the pure input now so that the expected inputs |
| // are after the expected inputs of [user]. |
| input.accept(this); |
| } |
| } else { |
| expectedInputs.add(input); |
| } |
| } |
| } |
| } |
| |
| // Some non-pure instructions may be treated as pure. HLocalGet depends on |
| // assignments, but we can ignore the initializing assignment since it will by |
| // construction always precede a use. |
| bool isEffectivelyPure(HInstruction instruction) { |
| if (instruction is HLocalGet) return !isAssignedLocal(instruction.local); |
| return instruction.isPure(_abstractValueDomain); |
| } |
| |
| bool isAssignedLocal(HLocalValue local) { |
| // [HLocalValue]s have an initializing assignment which is guaranteed to |
| // precede the use, except for [HParameterValue]s which are 'assigned' at |
| // entry. |
| int initializingAssignmentCount = (local is HParameterValue) ? 0 : 1; |
| return local.usedBy |
| .where((user) => user is HLocalSet) |
| .skip(initializingAssignmentCount) |
| .isNotEmpty; |
| } |
| |
| void visitInstruction(HInstruction instruction) { |
| // A code motion invariant instruction is dealt before visiting it. |
| assert(!instruction.isCodeMotionInvariant()); |
| analyzeInputs(instruction, 0); |
| } |
| |
| void visitInvokeSuper(HInvokeSuper instruction) { |
| MemberEntity superMethod = instruction.element; |
| Selector selector = instruction.selector; |
| // If aliased super members cannot be used, we will generate code like |
| // |
| // C.prototype.method.call(instance) |
| // |
| // where instance is the [this] object for the method. In such a case, the |
| // get of prototype might be evaluated before instance is created if we |
| // generate instance at use site, which in turn might update the prototype |
| // after first access if we use lazy initialization. |
| // In this case, we therefore don't allow the receiver (the first argument) |
| // to be generated at use site, and only analyze all other arguments. |
| if (!_superMemberData.canUseAliasedSuperMember(superMethod, selector)) { |
| analyzeInputs(instruction, 1); |
| } else { |
| super.visitInvokeSuper(instruction); |
| } |
| } |
| |
| void visitIs(HIs instruction) { |
| // In the general case the input might be used multple multiple times, so it |
| // must not be set generate at use site. |
| |
| // If the code will generate 'instanceof' then we can generate at use site. |
| if (instruction.useInstanceOf) { |
| analyzeInputs(instruction, 0); |
| } |
| |
| // Compound and variable checks use a separate instruction to compute the |
| // result. |
| if (instruction.isCompoundCheck || instruction.isVariableCheck) { |
| analyzeInputs(instruction, 0); |
| } |
| } |
| |
| // A bounds check method must not have its first input generated at use site, |
| // because it's using it twice. |
| void visitBoundsCheck(HBoundsCheck instruction) { |
| analyzeInputs(instruction, 1); |
| } |
| |
| // An identity operation must only have its inputs generated at use site if |
| // does not require an expression with multiple uses (because of null / |
| // undefined). |
| void visitIdentity(HIdentity instruction) { |
| if (instruction.singleComparisonOp != null) { |
| super.visitIdentity(instruction); |
| } |
| // Do nothing. |
| } |
| |
| void visitTypeConversion(HTypeConversion instruction) { |
| if (!instruction.isArgumentTypeCheck && !instruction.isReceiverTypeCheck) { |
| assert(instruction.isCheckedModeCheck || instruction.isCastTypeCheck); |
| // Checked mode checks and cast checks compile to code that |
| // only use their input once, so we can safely visit them |
| // and try to merge the input. |
| visitInstruction(instruction); |
| } |
| } |
| |
| void visitTypeKnown(HTypeKnown instruction) { |
| // [HTypeKnown] instructions are removed before code generation. |
| assert(false); |
| } |
| |
| void tryGenerateAtUseSite(HInstruction instruction) { |
| if (instruction.isControlFlow()) return; |
| markAsGenerateAtUseSite(instruction); |
| } |
| |
| bool isBlockSinglePredecessor(HBasicBlock block) { |
| return block.successors.length == 1 && |
| block.successors[0].predecessors.length == 1; |
| } |
| |
| void visitBasicBlock(HBasicBlock block) { |
| // Compensate from not merging blocks: if the block is the |
| // single predecessor of its single successor, let the successor |
| // visit it. |
| if (isBlockSinglePredecessor(block)) return; |
| |
| tryMergingExpressions(block); |
| } |
| |
| void tryMergingExpressions(HBasicBlock block) { |
| // Visit each instruction of the basic block in last-to-first order. |
| // Keep a list of expected inputs of the current "expression" being |
| // merged. If instructions occur in the expected order, they are |
| // included in the expression. |
| |
| // The expectedInputs list holds non-trivial instructions that may |
| // be generated at their use site, if they occur in the correct order. |
| if (expectedInputs == null) expectedInputs = new List<HInstruction>(); |
| if (pureInputs == null) pureInputs = new Set<HInstruction>(); |
| |
| // Pop instructions from expectedInputs until instruction is found. |
| // Return true if it is found, or false if not. |
| bool findInInputsAndPopNonMatching(HInstruction instruction) { |
| assert(!isEffectivelyPure(instruction)); |
| while (!expectedInputs.isEmpty) { |
| HInstruction nextInput = expectedInputs.removeLast(); |
| assert(!generateAtUseSite.contains(nextInput)); |
| assert(nextInput.usedBy.length == 1); |
| if (identical(nextInput, instruction)) { |
| return true; |
| } |
| } |
| return false; |
| } |
| |
| block.last.accept(this); |
| for (HInstruction instruction = block.last.previous; |
| instruction != null; |
| instruction = instruction.previous) { |
| if (generateAtUseSite.contains(instruction)) { |
| continue; |
| } |
| if (instruction.isCodeMotionInvariant()) { |
| markAsGenerateAtUseSite(instruction); |
| continue; |
| } |
| if (isEffectivelyPure(instruction)) { |
| if (pureInputs.contains(instruction)) { |
| tryGenerateAtUseSite(instruction); |
| } else { |
| // If the input is not in the [pureInputs] set, it has not |
| // been visited or should not be generated at use-site. The most |
| // likely reason for the latter, is that the instruction is used |
| // in more than one location. |
| // We must either clear the expectedInputs, or move the pure |
| // instruction's inputs in front of the existing ones. |
| // Example: |
| // t1 = foo(); // side-effect. |
| // t2 = bar(); // side-effect. |
| // t3 = pure(t2); // used more than once. |
| // f(t1, t3); // expected inputs of 'f': t1. |
| // use(t3); |
| // |
| // If we don't clear the expected inputs we end up in a situation |
| // where pure pushes "t2" on top of "t1" leading to: |
| // t3 = pure(bar()); |
| // f(foo(), t3); |
| // use(t3); |
| // |
| // If we clear the expected-inputs list we have the correct |
| // output: |
| // t1 = foo(); |
| // t3 = pure(bar()); |
| // f(t1, t3); |
| // use(t3); |
| // |
| // Clearing is, however, not optimal. |
| // Example: |
| // t1 = foo(); // t1 is now used by `pure`. |
| // t2 = bar(); // t2 is now used by `f`. |
| // t3 = pure(t1); |
| // f(t2, t3); |
| // use(t3); |
| // |
| // If we clear the expected-inputs we can't generate-at-use any of |
| // the instructions. |
| // |
| // The optimal solution is to move the inputs of 'pure' in |
| // front of the expectedInputs list. This makes sense, since we |
| // push expected-inputs from left-to right, and the `pure` function |
| // invocation is "more left" (i.e. before) the first argument of `f`. |
| // With that approach we end up with: |
| // t3 = pure(foo()); |
| // f(bar(), t3); |
| // use(t3); |
| // |
| int oldLength = expectedInputs.length; |
| instruction.accept(this); |
| if (oldLength != 0 && oldLength != expectedInputs.length) { |
| // Move the pure instruction's inputs to the front. |
| List<HInstruction> newInputs = expectedInputs.sublist(oldLength); |
| int newCount = newInputs.length; |
| expectedInputs.setRange( |
| newCount, newCount + oldLength, expectedInputs); |
| expectedInputs.setRange(0, newCount, newInputs); |
| } |
| } |
| } else { |
| if (findInInputsAndPopNonMatching(instruction)) { |
| // The current instruction is the next non-trivial |
| // expected input. |
| tryGenerateAtUseSite(instruction); |
| } else { |
| assert(expectedInputs.isEmpty); |
| } |
| instruction.accept(this); |
| } |
| } |
| |
| if (block.predecessors.length == 1 && |
| isBlockSinglePredecessor(block.predecessors[0])) { |
| assert(block.phis.isEmpty); |
| tryMergingExpressions(block.predecessors[0]); |
| } else { |
| expectedInputs = null; |
| pureInputs = null; |
| } |
| } |
| } |
| |
| /** |
| * Detect control flow arising from short-circuit logical and |
| * conditional operators, and prepare the program to be generated |
| * using these operators instead of nested ifs and boolean variables. |
| */ |
| class SsaConditionMerger extends HGraphVisitor { |
| Set<HInstruction> generateAtUseSite; |
| Set<HInstruction> controlFlowOperators; |
| |
| void markAsGenerateAtUseSite(HInstruction instruction) { |
| assert(!instruction.isJsStatement()); |
| generateAtUseSite.add(instruction); |
| } |
| |
| SsaConditionMerger(this.generateAtUseSite, this.controlFlowOperators); |
| |
| void visitGraph(HGraph graph) { |
| visitPostDominatorTree(graph); |
| } |
| |
| /** |
| * Check if a block has at least one statement other than |
| * [instruction]. |
| */ |
| bool hasAnyStatement(HBasicBlock block, HInstruction instruction) { |
| // If [instruction] is not in [block], then if the block is not |
| // empty, we know there will be a statement to emit. |
| if (!identical(instruction.block, block)) { |
| return !identical(block.last, block.first); |
| } |
| |
| // If [instruction] is not the last instruction of the block |
| // before the control flow instruction, or the last instruction, |
| // then we will have to emit a statement for that last instruction. |
| if (instruction != block.last && |
| !identical(instruction, block.last.previous)) return true; |
| |
| // If one of the instructions in the block until [instruction] is |
| // not generated at use site, then we will have to emit a |
| // statement for it. |
| // TODO(ngeoffray): we could generate a comma separated |
| // list of expressions. |
| for (HInstruction temp = block.first; |
| !identical(temp, instruction); |
| temp = temp.next) { |
| if (!generateAtUseSite.contains(temp)) return true; |
| } |
| |
| return false; |
| } |
| |
| bool isSafeToGenerateAtUseSite(HInstruction user, HInstruction input) { |
| // HCreate evaluates arguments in order and passes them to a constructor. |
| if (user is HCreate) return true; |
| // A [HForeign] instruction uses operators and if we generate [input] at use |
| // site, the precedence or evaluation order might be wrong. |
| if (user is HForeign) return false; |
| // A [HCheck] instruction with control flow uses its input |
| // multiple times, so we avoid generating it at use site. |
| if (user is HCheck && user.isControlFlow()) return false; |
| // A [HIs] instruction uses its input multiple times, so we |
| // avoid generating it at use site. |
| if (user is HIs) return false; |
| // Avoid code motion into a loop. |
| return user.hasSameLoopHeaderAs(input); |
| } |
| |
| void visitBasicBlock(HBasicBlock block) { |
| if (block.last is! HIf) return; |
| HIf startIf = block.last; |
| HBasicBlock end = startIf.joinBlock; |
| |
| // We check that the structure is the following: |
| // If |
| // / \ |
| // / \ |
| // 1 expr goto |
| // goto / |
| // \ / |
| // \ / |
| // phi(expr, true|false) |
| // |
| // and the same for nested nodes: |
| // |
| // If |
| // / \ |
| // / \ |
| // 1 expr1 \ |
| // If \ |
| // / \ \ |
| // / \ goto |
| // 1 expr2 | |
| // goto goto | |
| // \ / | |
| // \ / | |
| // phi1(expr2, true|false) |
| // \ | |
| // \ | |
| // phi(phi1, true|false) |
| |
| if (end == null) return; |
| if (end.phis.isEmpty) return; |
| if (!identical(end.phis.first, end.phis.last)) return; |
| HBasicBlock elseBlock = startIf.elseBlock; |
| |
| if (!identical(end.predecessors[1], elseBlock)) return; |
| HPhi phi = end.phis.first; |
| HInstruction thenInput = phi.inputs[0]; |
| HInstruction elseInput = phi.inputs[1]; |
| if (thenInput.isJsStatement() || elseInput.isJsStatement()) return; |
| |
| if (hasAnyStatement(elseBlock, elseInput)) return; |
| assert(elseBlock.successors.length == 1); |
| assert(end.predecessors.length == 2); |
| |
| HBasicBlock thenBlock = startIf.thenBlock; |
| // Skip trivial goto blocks. |
| while (thenBlock.successors[0] != end && thenBlock.first is HGoto) { |
| thenBlock = thenBlock.successors[0]; |
| } |
| |
| // If the [thenBlock] is already a control flow operation, and does not |
| // have any statement and its join block is [end], we can emit a |
| // sequence of control flow operation. |
| if (controlFlowOperators.contains(thenBlock.last)) { |
| HIf otherIf = thenBlock.last; |
| if (!identical(otherIf.joinBlock, end)) { |
| // This could be a join block that just feeds into our join block. |
| HBasicBlock otherJoin = otherIf.joinBlock; |
| if (otherJoin.first != otherJoin.last) return; |
| if (otherJoin.successors.length != 1) return; |
| if (otherJoin.successors[0] != end) return; |
| if (otherJoin.phis.isEmpty) return; |
| if (!identical(otherJoin.phis.first, otherJoin.phis.last)) return; |
| HPhi otherPhi = otherJoin.phis.first; |
| if (thenInput != otherPhi) return; |
| if (elseInput != otherPhi.inputs[1]) return; |
| } |
| if (hasAnyStatement(thenBlock, otherIf)) return; |
| } else { |
| if (!identical(end.predecessors[0], thenBlock)) return; |
| if (hasAnyStatement(thenBlock, thenInput)) return; |
| assert(thenBlock.successors.length == 1); |
| } |
| |
| // From now on, we have recognized a control flow operation built from |
| // the builder. Mark the if instruction as such. |
| controlFlowOperators.add(startIf); |
| |
| // Find the next non-HGoto instruction following the phi. |
| HInstruction nextInstruction = phi.block.first; |
| while (nextInstruction is HGoto) { |
| nextInstruction = nextInstruction.block.successors[0].first; |
| } |
| |
| // If the operation is only used by the first instruction |
| // of its block and is safe to be generated at use site, mark it |
| // so. |
| if (phi.usedBy.length == 1 && |
| phi.usedBy[0] == nextInstruction && |
| isSafeToGenerateAtUseSite(phi.usedBy[0], phi)) { |
| markAsGenerateAtUseSite(phi); |
| } |
| |
| if (identical(elseInput.block, elseBlock)) { |
| assert(elseInput.usedBy.length == 1); |
| markAsGenerateAtUseSite(elseInput); |
| } |
| |
| // If [thenInput] is defined in the first predecessor, then it is only used |
| // by [phi] and can be generated at use site. |
| if (identical(thenInput.block, end.predecessors[0])) { |
| assert(thenInput.usedBy.length == 1); |
| markAsGenerateAtUseSite(thenInput); |
| } |
| } |
| } |