Source/JavaScriptCore/b3/B3HoistLoopInvariantValues.cpp - external/github.com/WebKit/webkit - Git at Google

 /*
  * Copyright (C) 2017 Apple Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
  *
  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 #include "config.h"
 #include "B3HoistLoopInvariantValues.h"

 #if ENABLE(B3_JIT)

 #include "B3BackwardsDominators.h"
 #include "B3Dominators.h"
 #include "B3EnsureLoopPreHeaders.h"
 #include "B3NaturalLoops.h"
 #include "B3PhaseScope.h"
 #include "B3ProcedureInlines.h"
 #include "B3ValueInlines.h"
 #include <wtf/RangeSet.h>

 namespace JSC { namespace B3 {

 // A load that can trap reports exitsSideways, which normally disqualifies it from hoisting. The
 // fault is its only escaping effect, so it can still move to a point where it is certain to run and
 // where nothing observable precedes it. WasmGC field and length loads depend on this: their null
 // check is a trap rather than a branch, which would otherwise be all that blocks hoisting them.
 static bool isTrappingLoad(const Value* value)
 {
     if (!value->traps())
         return false;
     switch (value->opcode()) {
     case Load8Z:
     case Load8S:
     case Load16Z:
     case Load16S:
     case Load:
         // A fenced load also orders memory, which is an effect that cannot move.
         return !value->as<MemoryValue>()->hasFence();
     case WasmStructGet:
     case WasmArrayLength:
         return true;
     default:
         return false;
     }
 }

 static bool isReachedWithoutTrapBarrier(const NaturalLoops& loops, const NaturalLoop& loop, BasicBlock* block, const IndexSet<BasicBlock*>& blockBarriers)
 {
     if (block == loop.header())
         return true;

     // Tracing ancestors from the block. If any blocks belonging to this loop has a trap,
     // then we cannot hoist since that trap needs to be executed before the hoisted value causes
     // a trap at a pre-header block.
     Vector<BasicBlock*, 8> worklist;
     IndexSet<BasicBlock*> seen;
     auto push = [&](BasicBlock* predecessor) {
         if (loops.belongsTo(predecessor, loop)) {
             if (seen.add(predecessor)) {
                 // Every value in these blocks runs before the one being hoisted.
                 if (blockBarriers.contains(predecessor))
                     return false;

                 // Stopping at the header is enough even though earlier iterations run other blocks:
                 // callers only reach here for a value whose block backwards-dominates the pre-header,
                 // and backwards dominance counts a back edge as a way for the procedure to end, so
                 // such a value always runs before any iteration completes.
                 if (predecessor == loop.header())
                     return true;

                 worklist.append(predecessor);
             }
         }
         return true;
     };

     for (BasicBlock* predecessor : block->predecessors()) {
         if (!push(predecessor))
             return false;
     }

     while (!worklist.isEmpty()) {
         BasicBlock* current = worklist.takeLast();
         for (BasicBlock* predecessor : current->predecessors()) {
             if (!push(predecessor))
                 return false;
         }
     }

     return true;
 }

 bool hoistLoopInvariantValues(Procedure& proc)
 {
     PhaseScope phaseScope(proc, "hoistLoopInvariantValues"_s);

     ensureLoopPreHeaders(proc);

     NaturalLoops& loops = proc.naturalLoops();
     if (!loops.numLoops())
         return false;

     proc.resetValueOwners();
     Dominators& dominators = proc.dominators();
     BackwardsDominators& backwardsDominators = proc.backwardsDominators();

     // FIXME: We should have a reusable B3::EffectsSet data structure.
     // https://bugs.webkit.org/show_bug.cgi?id=174762
     struct LoopData {
         RangeSet<HeapRange> writes;
         bool writesLocalState { false };
         bool writesPinned { false };
         bool exitsSideways { false };
         BasicBlock* preHeader { nullptr };
     };

     IndexMap<NaturalLoop, LoopData> data(loops.numLoops());
     IndexSet<BasicBlock*> blockBarriers;

     for (unsigned loopIndex = loops.numLoops(); loopIndex--;) {
         const NaturalLoop& loop = loops.loop(loopIndex);
         for (BasicBlock* predecessor : loop.header()->predecessors()) {
             if (loops.belongsTo(predecessor, loop))
                 continue;
             RELEASE_ASSERT(!data[loop].preHeader);
             data[loop].preHeader = predecessor;
         }
     }

     for (BasicBlock* block : proc) {
         const NaturalLoop* loop = loops.innerMostLoopOf(block);
         if (!loop)
             continue;
         for (Value* value : *block) {
             Effects effects = value->effects();
             data[*loop].writes.add(effects.writes);
             data[*loop].writesLocalState |= effects.writesLocalState;
             data[*loop].writesPinned |= effects.writesPinned;
             data[*loop].exitsSideways |= effects.exitsSideways;
             if (effects.isTrapBarrier())
                 blockBarriers.add(block);
         }
     }

     for (unsigned loopIndex = loops.numLoops(); loopIndex--;) {
         const NaturalLoop& loop = loops.loop(loopIndex);
         for (const NaturalLoop* current = loops.innerMostOuterLoop(loop); current; current = loops.innerMostOuterLoop(*current)) {
             data[*current].writes.addAll(data[loop].writes);
             data[*current].writesLocalState |= data[loop].writesLocalState;
             data[*current].writesPinned |= data[loop].writesPinned;
             data[*current].exitsSideways |= data[loop].exitsSideways;
         }
     }

     bool changed = false;

     // Pre-order ensures that we visit our dominators before we visit ourselves. Otherwise we'd miss some
     // hoisting opportunities in complex CFGs.
     for (BasicBlock* block : proc.blocksInPreOrder()) {
         Vector<const NaturalLoop*> blockLoops = loops.loopsOf(block);
         if (blockLoops.isEmpty())
             continue;

         // Values that stay in this block run before everything later in it, so once one of them is a
         // trap barrier nothing after it can be hoisted out on the strength of trapping first.
         bool trapBarrierInBlock = false;
         for (Value*& value : *block) {
             Effects effects = value->effects();
             bool trappingLoad = isTrappingLoad(value);
             bool hoisted = false;

             // We never hoist write effects or control constructs. A trapping load is allowed
             // through. The fault it reports as a side exit is its own, and the checks below decide
             // whether it may move.
             if (!effects.mustExecute() || trappingLoad) {
                 // Try outermost loop first.
                 for (unsigned i = blockLoops.size(); i--;) {
                     const NaturalLoop& loop = *blockLoops[i];

                     bool ok = true;
                     for (Value* child : value->children()) {
                         if (!dominators.dominates(child->owner, data[loop].preHeader)) {
                             ok = false;
                             break;
                         }
                     }
                     if (!ok)
                         continue;

                     if (effects.controlDependent || trappingLoad) {
                         // The block is backward-dominating the pre-header.
                         // The value needs to be guaranteed to run on every iteration.
                         if (!backwardsDominators.dominates(block, data[loop].preHeader))
                             continue;

                         if (data[loop].exitsSideways) {
                             // Even if the loop can exit (after this value for example), if we do not have
                             // any exit between pre-header to this value, we can still hoist a value because
                             // this can be a first value causing a trap.
                             if (trapBarrierInBlock || !isReachedWithoutTrapBarrier(loops, loop, block, blockBarriers))
                                 continue;
                         }
                     }

                     if (effects.readsPinned && data[loop].writesPinned)
                         continue;

                     if (effects.readsLocalState && data[loop].writesLocalState)
                         continue;

                     if (data[loop].writes.overlaps(effects.reads))
                         continue;

                     data[loop].preHeader->appendNonTerminal(value);
                     value = proc.add<Value>(Nop, Void, value->origin());
                     changed = true;
                     hoisted = true;
                 }
             }

             if (!hoisted)
                 trapBarrierInBlock |= effects.isTrapBarrier();
         }
     }

     return changed;
 }

 } } // namespace JSC::B3

 #endif // ENABLE(B3_JIT)
	/*
	* Copyright (C) 2017 Apple Inc. All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or without
	* modification, are permitted provided that the following conditions
	* are met:
	* 1. Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	* 2. Redistributions in binary form must reproduce the above copyright
	* notice, this list of conditions and the following disclaimer in the
	* documentation and/or other materials provided with the distribution.
	*
	* THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
	* EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
	* PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR
	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
	* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
	* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
	* PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
	* OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
	* (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
	* OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	#include "config.h"
	#include "B3HoistLoopInvariantValues.h"

	#if ENABLE(B3_JIT)

	#include "B3BackwardsDominators.h"
	#include "B3Dominators.h"
	#include "B3EnsureLoopPreHeaders.h"
	#include "B3NaturalLoops.h"
	#include "B3PhaseScope.h"
	#include "B3ProcedureInlines.h"
	#include "B3ValueInlines.h"
	#include <wtf/RangeSet.h>

	namespace JSC { namespace B3 {

	// A load that can trap reports exitsSideways, which normally disqualifies it from hoisting. The
	// fault is its only escaping effect, so it can still move to a point where it is certain to run and
	// where nothing observable precedes it. WasmGC field and length loads depend on this: their null
	// check is a trap rather than a branch, which would otherwise be all that blocks hoisting them.
	static bool isTrappingLoad(const Value* value)
	{
	if (!value->traps())
	return false;
	switch (value->opcode()) {
	case Load8Z:
	case Load8S:
	case Load16Z:
	case Load16S:
	case Load:
	// A fenced load also orders memory, which is an effect that cannot move.
	return !value->as<MemoryValue>()->hasFence();
	case WasmStructGet:
	case WasmArrayLength:
	return true;
	default:
	return false;
	}
	}

	static bool isReachedWithoutTrapBarrier(const NaturalLoops& loops, const NaturalLoop& loop, BasicBlock* block, const IndexSet<BasicBlock*>& blockBarriers)
	{
	if (block == loop.header())
	return true;

	// Tracing ancestors from the block. If any blocks belonging to this loop has a trap,
	// then we cannot hoist since that trap needs to be executed before the hoisted value causes
	// a trap at a pre-header block.
	Vector<BasicBlock*, 8> worklist;
	IndexSet<BasicBlock*> seen;
	auto push = [&](BasicBlock* predecessor) {
	if (loops.belongsTo(predecessor, loop)) {
	if (seen.add(predecessor)) {
	// Every value in these blocks runs before the one being hoisted.
	if (blockBarriers.contains(predecessor))
	return false;

	// Stopping at the header is enough even though earlier iterations run other blocks:
	// callers only reach here for a value whose block backwards-dominates the pre-header,
	// and backwards dominance counts a back edge as a way for the procedure to end, so
	// such a value always runs before any iteration completes.
	if (predecessor == loop.header())
	return true;

	worklist.append(predecessor);
	}
	}
	return true;
	};

	for (BasicBlock* predecessor : block->predecessors()) {
	if (!push(predecessor))
	return false;
	}

	while (!worklist.isEmpty()) {
	BasicBlock* current = worklist.takeLast();
	for (BasicBlock* predecessor : current->predecessors()) {
	if (!push(predecessor))
	return false;
	}
	}

	return true;
	}

	bool hoistLoopInvariantValues(Procedure& proc)
	{
	PhaseScope phaseScope(proc, "hoistLoopInvariantValues"_s);

	ensureLoopPreHeaders(proc);

	NaturalLoops& loops = proc.naturalLoops();
	if (!loops.numLoops())
	return false;

	proc.resetValueOwners();
	Dominators& dominators = proc.dominators();
	BackwardsDominators& backwardsDominators = proc.backwardsDominators();

	// FIXME: We should have a reusable B3::EffectsSet data structure.
	// https://bugs.webkit.org/show_bug.cgi?id=174762
	struct LoopData {
	RangeSet<HeapRange> writes;
	bool writesLocalState { false };
	bool writesPinned { false };
	bool exitsSideways { false };
	BasicBlock* preHeader { nullptr };
	};

	IndexMap<NaturalLoop, LoopData> data(loops.numLoops());
	IndexSet<BasicBlock*> blockBarriers;

	for (unsigned loopIndex = loops.numLoops(); loopIndex--;) {
	const NaturalLoop& loop = loops.loop(loopIndex);
	for (BasicBlock* predecessor : loop.header()->predecessors()) {
	if (loops.belongsTo(predecessor, loop))
	continue;
	RELEASE_ASSERT(!data[loop].preHeader);
	data[loop].preHeader = predecessor;
	}
	}

	for (BasicBlock* block : proc) {
	const NaturalLoop* loop = loops.innerMostLoopOf(block);
	if (!loop)
	continue;
	for (Value* value : *block) {
	Effects effects = value->effects();
	data[*loop].writes.add(effects.writes);
	data[*loop].writesLocalState \|= effects.writesLocalState;
	data[*loop].writesPinned \|= effects.writesPinned;
	data[*loop].exitsSideways \|= effects.exitsSideways;
	if (effects.isTrapBarrier())
	blockBarriers.add(block);
	}
	}

	for (unsigned loopIndex = loops.numLoops(); loopIndex--;) {
	const NaturalLoop& loop = loops.loop(loopIndex);
	for (const NaturalLoop* current = loops.innerMostOuterLoop(loop); current; current = loops.innerMostOuterLoop(*current)) {
	data[*current].writes.addAll(data[loop].writes);
	data[*current].writesLocalState \|= data[loop].writesLocalState;
	data[*current].writesPinned \|= data[loop].writesPinned;
	data[*current].exitsSideways \|= data[loop].exitsSideways;
	}
	}

	bool changed = false;

	// Pre-order ensures that we visit our dominators before we visit ourselves. Otherwise we'd miss some
	// hoisting opportunities in complex CFGs.
	for (BasicBlock* block : proc.blocksInPreOrder()) {
	Vector<const NaturalLoop*> blockLoops = loops.loopsOf(block);
	if (blockLoops.isEmpty())
	continue;

	// Values that stay in this block run before everything later in it, so once one of them is a
	// trap barrier nothing after it can be hoisted out on the strength of trapping first.
	bool trapBarrierInBlock = false;
	for (Value& value : block) {
	Effects effects = value->effects();
	bool trappingLoad = isTrappingLoad(value);
	bool hoisted = false;

	// We never hoist write effects or control constructs. A trapping load is allowed
	// through. The fault it reports as a side exit is its own, and the checks below decide
	// whether it may move.
	if (!effects.mustExecute() \|\| trappingLoad) {
	// Try outermost loop first.
	for (unsigned i = blockLoops.size(); i--;) {
	const NaturalLoop& loop = *blockLoops[i];

	bool ok = true;
	for (Value* child : value->children()) {
	if (!dominators.dominates(child->owner, data[loop].preHeader)) {
	ok = false;
	break;
	}
	}
	if (!ok)
	continue;

	if (effects.controlDependent \|\| trappingLoad) {
	// The block is backward-dominating the pre-header.
	// The value needs to be guaranteed to run on every iteration.
	if (!backwardsDominators.dominates(block, data[loop].preHeader))
	continue;

	if (data[loop].exitsSideways) {
	// Even if the loop can exit (after this value for example), if we do not have
	// any exit between pre-header to this value, we can still hoist a value because
	// this can be a first value causing a trap.
	if (trapBarrierInBlock \|\| !isReachedWithoutTrapBarrier(loops, loop, block, blockBarriers))
	continue;
	}
	}

	if (effects.readsPinned && data[loop].writesPinned)
	continue;

	if (effects.readsLocalState && data[loop].writesLocalState)
	continue;

	if (data[loop].writes.overlaps(effects.reads))
	continue;

	data[loop].preHeader->appendNonTerminal(value);
	value = proc.add<Value>(Nop, Void, value->origin());
	changed = true;
	hoisted = true;
	}
	}

	if (!hoisted)
	trapBarrierInBlock \|= effects.isTrapBarrier();
	}
	}

	return changed;
	}

	} } // namespace JSC::B3

	#endif // ENABLE(B3_JIT)