//-------------------------------------------------------------------------------------------------------

// Copyright (C) Microsoft. All rights reserved.

// Licensed under the MIT license. See LICENSE.txt file in the project root for full license information.

//-------------------------------------------------------------------------------------------------------

#include "Backend.h"

FlowGraph *

FlowGraph::New(Func * func, JitArenaAllocator * alloc)

{

FlowGraph * graph;

graph = JitAnew(alloc, FlowGraph, func, alloc);

return graph;

}

///----------------------------------------------------------------------------

///

/// FlowGraph::Build

///

/// Construct flow graph and loop structures for the current state of the function.

///

///----------------------------------------------------------------------------

void

FlowGraph::Build(void)

{

Func * func = this->func;

BEGIN_CODEGEN_PHASE(func, Js::FGPeepsPhase);

this->RunPeeps();

END_CODEGEN_PHASE(func, Js::FGPeepsPhase);

// We don't optimize fully with SimpleJit. But, when JIT loop body is enabled, we do support

// bailing out from a simple jitted function to do a full jit of a loop body in the function

// (BailOnSimpleJitToFullJitLoopBody). For that purpose, we need the flow from try to catch.

if (this->func->HasTry() &&

(this->func->DoOptimizeTryCatch() ||

(this->func->IsSimpleJit() && this->func->GetJITFunctionBody()->DoJITLoopBody())

)

)

{

this->catchLabelStack = JitAnew(this->alloc, SList<IR::LabelInstr*>, this->alloc);

}

IR::Instr * currLastInstr = nullptr;

BasicBlock * currBlock = nullptr;

BasicBlock * nextBlock = nullptr;

bool hasCall = false;

FOREACH_INSTR_IN_FUNC_BACKWARD_EDITING(instr, instrPrev, func)

{

if (currLastInstr == nullptr || instr->EndsBasicBlock())

{

// Start working on a new block.

// If we're currently processing a block, then wrap it up before beginning a new one.

if (currLastInstr != nullptr)

{

nextBlock = currBlock;

currBlock = this->AddBlock(instr->m_next, currLastInstr, nextBlock);

currBlock->hasCall = hasCall;

hasCall = false;

}

currLastInstr = instr;

}

if (instr->StartsBasicBlock())

{

// Insert a BrOnException after the loop top if we are in a try-catch. This is required to

// model flow from the loop to the catch block for loops that don't have a break condition.

if (instr->IsLabelInstr() && instr->AsLabelInstr()->m_isLoopTop &&

this->catchLabelStack && !this->catchLabelStack->Empty() &&

instr->m_next->m_opcode != Js::OpCode::BrOnException)

{

IR::BranchInstr * brOnException = IR::BranchInstr::New(Js::OpCode::BrOnException, this->catchLabelStack->Top(), instr->m_func);

instr->InsertAfter(brOnException);

instrPrev = brOnException; // process BrOnException before adding a new block for loop top label.

continue;

}

// Wrap up the current block and get ready to process a new one.

nextBlock = currBlock;

currBlock = this->AddBlock(instr, currLastInstr, nextBlock);

currBlock->hasCall = hasCall;

hasCall = false;

currLastInstr = nullptr;

}

switch (instr->m_opcode)

{

case Js::OpCode::Catch:

Assert(instr->m_prev->IsLabelInstr());

if (this->catchLabelStack)

{

this->catchLabelStack->Push(instr->m_prev->AsLabelInstr());

}

break;

case Js::OpCode::TryCatch:

if (this->catchLabelStack)

{

this->catchLabelStack->Pop();

}

break;

case Js::OpCode::CloneBlockScope:

case Js::OpCode::CloneInnerScopeSlots:

// It would be nice to do this in IRBuilder, but doing so gives us

// trouble when doing the DoSlotArrayCheck since it assume single def

// of the sym to do its check properly. So instead we assign the dst

// here in FlowGraph.

instr->SetDst(instr->GetSrc1());

break;

}

if (OpCodeAttr::UseAllFields(instr->m_opcode))

{

// UseAllFields opcode are call instruction or opcode that would call.

hasCall = true;

if (OpCodeAttr::CallInstr(instr->m_opcode))

{

if (!instr->isCallInstrProtectedByNoProfileBailout)

{

instr->m_func->SetHasCallsOnSelfAndParents();

}

// For ARM & X64 because of their register calling convention

// the ArgOuts need to be moved next to the call.

#if defined(_M_ARM) || defined(_M_X64)

IR::Instr* argInsertInstr = instr;

instr->IterateArgInstrs([&](IR::Instr* argInstr)

{

if (argInstr->m_opcode != Js::OpCode::LdSpreadIndices &&

argInstr->m_opcode != Js::OpCode::ArgOut_A_Dynamic &&

argInstr->m_opcode != Js::OpCode::ArgOut_A_FromStackArgs &&

argInstr->m_opcode != Js::OpCode::ArgOut_A_SpreadArg)

{

// don't have bailout in asm.js so we don't need BytecodeArgOutCapture

if (!argInstr->m_func->GetJITFunctionBody()->IsAsmJsMode())

{

// Need to always generate byte code arg out capture,

// because bailout can't restore from the arg out as it is

// replaced by new sym for register calling convention in lower

argInstr->GenerateBytecodeArgOutCapture();

}

// Check if the instruction is already next

if (argInstr != argInsertInstr->m_prev)

{

// It is not, move it.

argInstr->Move(argInsertInstr);

}

argInsertInstr = argInstr;

}

return false;

});

#endif

}

}

}

NEXT_INSTR_IN_FUNC_BACKWARD_EDITING;

this->func->isFlowGraphValid = true;

Assert(!this->catchLabelStack || this->catchLabelStack->Empty());

// We've been walking backward so that edge lists would be in the right order. Now walk the blocks

// forward to number the blocks in lexical order.

unsigned int blockNum = 0;

FOREACH_BLOCK(block, this)

{

block->SetBlockNum(blockNum++);

}NEXT_BLOCK;

AssertMsg(blockNum == this->blockCount, "Block count is out of whack");

this->RemoveUnreachableBlocks();

this->FindLoops();

bool breakBlocksRelocated = this->CanonicalizeLoops();

#if DBG

this->VerifyLoopGraph();

#endif

// Renumber the blocks. Break block remove code has likely inserted new basic blocks.

blockNum = 0;

// Regions need to be assigned before Globopt because:

// 1. FullJit: The Backward Pass will set the write-through symbols on the regions and the forward pass will

// use this information to insert ToVars for those symbols. Also, for a symbol determined as write-through

// in the try region to be restored correctly by the bailout, it should not be removed from the

// byteCodeUpwardExposedUsed upon a def in the try region (the def might be preempted by an exception).

//

// 2. SimpleJit: Same case of correct restoration as above applies in SimpleJit too. However, the only bailout

// we have in Simple Jitted code right now is BailOnSimpleJitToFullJitLoopBody, installed in IRBuilder. So,

// for now, we can just check if the func has a bailout to assign regions pre globopt while running SimpleJit.

bool assignRegionsBeforeGlobopt = this->func->HasTry() &&

(this->func->DoOptimizeTryCatch() || (this->func->IsSimpleJit() && this->func->hasBailout));

Region ** blockToRegion = nullptr;

if (assignRegionsBeforeGlobopt)

{

blockToRegion = JitAnewArrayZ(this->alloc, Region*, this->blockCount);

}

FOREACH_BLOCK_ALL(block, this)

{

block->SetBlockNum(blockNum++);

if (assignRegionsBeforeGlobopt)

{

if (block->isDeleted && !block->isDead)

{

continue;

}

this->UpdateRegionForBlock(block, blockToRegion);

}

} NEXT_BLOCK_ALL;

AssertMsg (blockNum == this->blockCount, "Block count is out of whack");

if (breakBlocksRelocated)

{

// Sort loop lists only if there is break block removal.

SortLoopLists();

}

#if DBG_DUMP

this->Dump(false, nullptr);

#endif

}

void

FlowGraph::SortLoopLists()

{

// Sort the blocks in loopList

for (Loop *loop = this->loopList; loop; loop = loop->next)

{

unsigned int lastBlockNumber = loop->GetHeadBlock()->GetBlockNum();

// Insertion sort as the blockList is almost sorted in the loop.

FOREACH_BLOCK_IN_LOOP_EDITING(block, loop, iter)

{

if (lastBlockNumber <= block->GetBlockNum())

{

lastBlockNumber = block->GetBlockNum();

}

else

{

iter.UnlinkCurrent();

FOREACH_BLOCK_IN_LOOP_EDITING(insertBlock,loop,newIter)

{

if (insertBlock->GetBlockNum() > block->GetBlockNum())

{

break;

}

}NEXT_BLOCK_IN_LOOP_EDITING;

newIter.InsertBefore(block);

}

}NEXT_BLOCK_IN_LOOP_EDITING;

}

}

void

FlowGraph::RunPeeps()

{

if (this->func->HasTry())

{

return;

}

if (PHASE_OFF(Js::FGPeepsPhase, this->func))

{

return;

}

IR::Instr * instrCm = nullptr;

bool tryUnsignedCmpPeep = false;

FOREACH_INSTR_IN_FUNC_EDITING(instr, instrNext, this->func)

{

switch(instr->m_opcode)

{

case Js::OpCode::Br:

case Js::OpCode::BrEq_I4:

case Js::OpCode::BrGe_I4:

case Js::OpCode::BrGt_I4:

case Js::OpCode::BrLt_I4:

case Js::OpCode::BrLe_I4:

case Js::OpCode::BrUnGe_I4:

case Js::OpCode::BrUnGt_I4:

case Js::OpCode::BrUnLt_I4:

case Js::OpCode::BrUnLe_I4:

case Js::OpCode::BrNeq_I4:

case Js::OpCode::BrEq_A:

case Js::OpCode::BrGe_A:

case Js::OpCode::BrGt_A:

case Js::OpCode::BrLt_A:

case Js::OpCode::BrLe_A:

case Js::OpCode::BrUnGe_A:

case Js::OpCode::BrUnGt_A:

case Js::OpCode::BrUnLt_A:

case Js::OpCode::BrUnLe_A:

case Js::OpCode::BrNotEq_A:

case Js::OpCode::BrNotNeq_A:

case Js::OpCode::BrSrNotEq_A:

case Js::OpCode::BrSrNotNeq_A:

case Js::OpCode::BrNotGe_A:

case Js::OpCode::BrNotGt_A:

case Js::OpCode::BrNotLt_A:

case Js::OpCode::BrNotLe_A:

case Js::OpCode::BrNeq_A:

case Js::OpCode::BrNotNull_A:

case Js::OpCode::BrNotAddr_A:

case Js::OpCode::BrAddr_A:

case Js::OpCode::BrSrEq_A:

case Js::OpCode::BrSrNeq_A:

case Js::OpCode::BrOnHasProperty:

case Js::OpCode::BrOnNoProperty:

case Js::OpCode::BrHasSideEffects:

case Js::OpCode::BrNotHasSideEffects:

case Js::OpCode::BrFncEqApply:

case Js::OpCode::BrFncNeqApply:

case Js::OpCode::BrOnEmpty:

case Js::OpCode::BrOnNotEmpty:

case Js::OpCode::BrFncCachedScopeEq:

case Js::OpCode::BrFncCachedScopeNeq:

case Js::OpCode::BrOnObject_A:

case Js::OpCode::BrOnClassConstructor:

case Js::OpCode::BrOnBaseConstructorKind:

if (tryUnsignedCmpPeep)

{

this->UnsignedCmpPeep(instr);

}

instrNext = Peeps::PeepBranch(instr->AsBranchInstr());

break;

case Js::OpCode::MultiBr:

// TODO: Run peeps on these as well...

break;

case Js::OpCode::BrTrue_I4:

case Js::OpCode::BrFalse_I4:

case Js::OpCode::BrTrue_A:

case Js::OpCode::BrFalse_A:

if (instrCm)

{

if (instrCm->GetDst()->IsInt32())

{

Assert(instr->m_opcode == Js::OpCode::BrTrue_I4 || instr->m_opcode == Js::OpCode::BrFalse_I4);

instrNext = this->PeepTypedCm(instrCm);

}

else

{

instrNext = this->PeepCm(instrCm);

}

instrCm = nullptr;

if (instrNext == nullptr)

{

// Set instrNext back to the current instr.

instrNext = instr;

}

}

else

{

instrNext = Peeps::PeepBranch(instr->AsBranchInstr());

}

break;

case Js::OpCode::CmEq_I4:

case Js::OpCode::CmGe_I4:

case Js::OpCode::CmGt_I4:

case Js::OpCode::CmLt_I4:

case Js::OpCode::CmLe_I4:

case Js::OpCode::CmNeq_I4:

case Js::OpCode::CmEq_A:

case Js::OpCode::CmGe_A:

case Js::OpCode::CmGt_A:

case Js::OpCode::CmLt_A:

case Js::OpCode::CmLe_A:

case Js::OpCode::CmNeq_A:

case Js::OpCode::CmSrEq_A:

case Js::OpCode::CmSrNeq_A:

if (tryUnsignedCmpPeep)

{

this->UnsignedCmpPeep(instr);

}

case Js::OpCode::CmUnGe_I4:

case Js::OpCode::CmUnGt_I4:

case Js::OpCode::CmUnLt_I4:

case Js::OpCode::CmUnLe_I4:

case Js::OpCode::CmUnGe_A:

case Js::OpCode::CmUnGt_A:

case Js::OpCode::CmUnLt_A:

case Js::OpCode::CmUnLe_A:

// There may be useless branches between the Cm instr and the branch that uses the result.

// So save the last Cm instr seen, and trigger the peep on the next BrTrue/BrFalse.

instrCm = instr;

break;

case Js::OpCode::Label:

if (instr->AsLabelInstr()->IsUnreferenced())

{

instrNext = Peeps::PeepUnreachableLabel(instr->AsLabelInstr(), false);

}

break;

case Js::OpCode::StatementBoundary:

instr->ClearByteCodeOffset();

instr->SetByteCodeOffset(instr->GetNextRealInstrOrLabel());

break;

case Js::OpCode::ShrU_I4:

case Js::OpCode::ShrU_A:

if (tryUnsignedCmpPeep)

{

break;

}

if (instr->GetDst()->AsRegOpnd()->m_sym->IsSingleDef()

&& instr->GetSrc2()->IsRegOpnd() && instr->GetSrc2()->AsRegOpnd()->m_sym->IsTaggableIntConst()

&& instr->GetSrc2()->AsRegOpnd()->m_sym->GetIntConstValue() == 0)

{

tryUnsignedCmpPeep = true;

}

break;

default:

Assert(!instr->IsBranchInstr());

}

} NEXT_INSTR_IN_FUNC_EDITING;

}

void

Loop::InsertLandingPad(FlowGraph *fg)

{

BasicBlock *headBlock = this->GetHeadBlock();

// Always create a landing pad. This allows globopt to easily hoist instructions

// and re-optimize the block if needed.

BasicBlock *landingPad = BasicBlock::New(fg);

this->landingPad = landingPad;

IR::Instr * headInstr = headBlock->GetFirstInstr();

IR::LabelInstr *landingPadLabel = IR::LabelInstr::New(Js::OpCode::Label, headInstr->m_func);

landingPadLabel->SetByteCodeOffset(headInstr);

headInstr->InsertBefore(landingPadLabel);

landingPadLabel->SetBasicBlock(landingPad);

landingPad->SetBlockNum(fg->blockCount++);

landingPad->SetFirstInstr(landingPadLabel);

landingPad->SetLastInstr(landingPadLabel);

landingPad->prev = headBlock->prev;

landingPad->prev->next = landingPad;

landingPad->next = headBlock;

headBlock->prev = landingPad;

Loop *parentLoop = this->parent;

landingPad->loop = parentLoop;

// We need to add this block to the block list of the parent loops

while (parentLoop)

{

// Find the head block in the block list of the parent loop

FOREACH_BLOCK_IN_LOOP_EDITING(block, parentLoop, iter)

{

if (block == headBlock)

{

// Add the landing pad to the block list

iter.InsertBefore(landingPad);

break;

}

} NEXT_BLOCK_IN_LOOP_EDITING;

parentLoop = parentLoop->parent;

}

// Fix predecessor flow edges

FOREACH_PREDECESSOR_EDGE_EDITING(edge, headBlock, iter)

{

// Make sure it isn't a back-edge

if (edge->GetPred()->loop != this && !this->IsDescendentOrSelf(edge->GetPred()->loop))

{

if (edge->GetPred()->GetLastInstr()->IsBranchInstr() && headBlock->GetFirstInstr()->IsLabelInstr())

{

IR::BranchInstr *branch = edge->GetPred()->GetLastInstr()->AsBranchInstr();

branch->ReplaceTarget(headBlock->GetFirstInstr()->AsLabelInstr(), landingPadLabel);

}

headBlock->UnlinkPred(edge->GetPred(), false);

landingPad->AddPred(edge, fg);

edge->SetSucc(landingPad);

}

} NEXT_PREDECESSOR_EDGE_EDITING;

fg->AddEdge(landingPad, headBlock);

}

bool

Loop::RemoveBreakBlocks(FlowGraph *fg)

{

bool breakBlockRelocated = false;

if (PHASE_OFF(Js::RemoveBreakBlockPhase, fg->GetFunc()))

{

return false;

}

BasicBlock *loopTailBlock = nullptr;

FOREACH_BLOCK_IN_LOOP(block, this)

{

loopTailBlock = block;

}NEXT_BLOCK_IN_LOOP;

AnalysisAssert(loopTailBlock);

FOREACH_BLOCK_BACKWARD_IN_RANGE_EDITING(breakBlockEnd, loopTailBlock, this->GetHeadBlock(), blockPrev)

{

while (!this->IsDescendentOrSelf(breakBlockEnd->loop))

{

// Found at least one break block;

breakBlockRelocated = true;

#if DBG

breakBlockEnd->isBreakBlock = true;

#endif

// Find the first block in this break block sequence.

BasicBlock *breakBlockStart = breakBlockEnd;

BasicBlock *breakBlockStartPrev = breakBlockEnd->GetPrev();

// Walk back the blocks until we find a block which belongs to that block.

// Note: We don't really care if there are break blocks corresponding to different loops. We move the blocks conservatively to the end of the loop.

// Algorithm works on one loop at a time.

while((breakBlockStartPrev->loop == breakBlockEnd->loop) || !this->IsDescendentOrSelf(breakBlockStartPrev->loop))

{

breakBlockStart = breakBlockStartPrev;

breakBlockStartPrev = breakBlockStartPrev->GetPrev();

}

#if DBG

breakBlockStart->isBreakBlock = true; // Mark the first block as well.

#endif

BasicBlock *exitLoopTail = loopTailBlock;

// Move these break blocks to the tail of the loop.

fg->MoveBlocksBefore(breakBlockStart, breakBlockEnd, exitLoopTail->next);

#if DBG_DUMP

fg->Dump(true /*needs verbose flag*/, _u("\n After Each iteration of canonicalization \n"));

#endif

// Again be conservative, there are edits to the loop graph. Start fresh for this loop.

breakBlockEnd = loopTailBlock;

blockPrev = breakBlockEnd->prev;

}

} NEXT_BLOCK_BACKWARD_IN_RANGE_EDITING;

return breakBlockRelocated;

}

void

FlowGraph::MoveBlocksBefore(BasicBlock *blockStart, BasicBlock *blockEnd, BasicBlock *insertBlock)

{

BasicBlock *srcPredBlock = blockStart->prev;

BasicBlock *srcNextBlock = blockEnd->next;

BasicBlock *dstPredBlock = insertBlock->prev;

IR::Instr* dstPredBlockLastInstr = dstPredBlock->GetLastInstr();

IR::Instr* blockEndLastInstr = blockEnd->GetLastInstr();

// Fix block linkage

srcPredBlock->next = srcNextBlock;

srcNextBlock->prev = srcPredBlock;

dstPredBlock->next = blockStart;

insertBlock->prev = blockEnd;

blockStart->prev = dstPredBlock;

blockEnd->next = insertBlock;

// Fix instruction linkage

IR::Instr::MoveRangeAfter(blockStart->GetFirstInstr(), blockEndLastInstr, dstPredBlockLastInstr);

// Fix instruction flow

IR::Instr *srcLastInstr = srcPredBlock->GetLastInstr();

if (srcLastInstr->IsBranchInstr() && srcLastInstr->AsBranchInstr()->HasFallThrough())

{

// There was a fallthrough in the break blocks original position.

IR::BranchInstr *srcBranch = srcLastInstr->AsBranchInstr();

IR::Instr *srcBranchNextInstr = srcBranch->GetNextRealInstrOrLabel();

// Save the target and invert the branch.

IR::LabelInstr *srcBranchTarget = srcBranch->GetTarget();

srcPredBlock->InvertBranch(srcBranch);

IR::LabelInstr *srcLabel = blockStart->GetFirstInstr()->AsLabelInstr();

// Point the inverted branch to break block.

srcBranch->SetTarget(srcLabel);

if (srcBranchNextInstr != srcBranchTarget)

{

FlowEdge *srcEdge = this->FindEdge(srcPredBlock, srcBranchTarget->GetBasicBlock());

Assert(srcEdge);

BasicBlock *compensationBlock = this->InsertCompensationCodeForBlockMove(srcEdge, true /*insert compensation block to loop list*/, false /*At source*/);

Assert(compensationBlock);

}

}

IR::Instr *dstLastInstr = dstPredBlockLastInstr;

if (dstLastInstr->IsBranchInstr() && dstLastInstr->AsBranchInstr()->HasFallThrough())

{

//There is a fallthrough in the block after which break block is inserted.

FlowEdge *dstEdge = this->FindEdge(dstPredBlock, blockEnd->GetNext());

Assert(dstEdge);

BasicBlock *compensationBlock = this->InsertCompensationCodeForBlockMove(dstEdge, true /*insert compensation block to loop list*/, true /*At sink*/);

Assert(compensationBlock);

}

}

FlowEdge *

FlowGraph::FindEdge(BasicBlock *predBlock, BasicBlock *succBlock)

{

FlowEdge *srcEdge = nullptr;

FOREACH_SUCCESSOR_EDGE(edge, predBlock)

{

if (edge->GetSucc() == succBlock)

{

srcEdge = edge;

break;

}

} NEXT_SUCCESSOR_EDGE;

return srcEdge;

}

void

BasicBlock::InvertBranch(IR::BranchInstr *branch)

{

Assert(this->GetLastInstr() == branch);

Assert(this->GetSuccList()->HasTwo());

branch->Invert();

this->GetSuccList()->Reverse();

}

bool

FlowGraph::CanonicalizeLoops()

{

if (this->func->HasProfileInfo())

{

this->implicitCallFlags = this->func->GetReadOnlyProfileInfo()->GetImplicitCallFlags();

for (Loop *loop = this->loopList; loop; loop = loop->next)

{

this->implicitCallFlags = (Js::ImplicitCallFlags)(this->implicitCallFlags | loop->GetImplicitCallFlags());

}

}

#if DBG_DUMP

this->Dump(true, _u("\n Before canonicalizeLoops \n"));

#endif

bool breakBlockRelocated = false;

for (Loop *loop = this->loopList; loop; loop = loop->next)

{

loop->InsertLandingPad(this);

if (!this->func->HasTry() || this->func->DoOptimizeTryCatch())

{

bool relocated = loop->RemoveBreakBlocks(this);

if (!breakBlockRelocated && relocated)

{

breakBlockRelocated = true;

}

}

}

#if DBG_DUMP

this->Dump(true, _u("\n After canonicalizeLoops \n"));

#endif

return breakBlockRelocated;

}

// Find the loops in this function, build the loop structure, and build a linked

// list of the basic blocks in this loop (including blocks of inner loops). The

// list preserves the reverse post-order of the blocks in the flowgraph block list.

void

FlowGraph::FindLoops()

{

if (!this->hasLoop)

{

return;

}

Func * func = this->func;

FOREACH_BLOCK_BACKWARD_IN_FUNC(block, func)

{

if (block->loop != nullptr)

{

// Block already visited

continue;

}

FOREACH_SUCCESSOR_BLOCK(succ, block)

{

if (succ->isLoopHeader && succ->loop == nullptr)

{

// Found a loop back-edge

BuildLoop(succ, block);

}

} NEXT_SUCCESSOR_BLOCK;

if (block->isLoopHeader && block->loop == nullptr)

{

// We would have built a loop for it if it was a loop...

block->isLoopHeader = false;

block->GetFirstInstr()->AsLabelInstr()->m_isLoopTop = false;

}

} NEXT_BLOCK_BACKWARD_IN_FUNC;

}

void

FlowGraph::BuildLoop(BasicBlock *headBlock, BasicBlock *tailBlock, Loop *parentLoop)

{

// This function is recursive, so when jitting in the foreground, probe the stack

if(!func->IsBackgroundJIT())

{

PROBE_STACK(func->GetScriptContext(), Js::Constants::MinStackDefault);

}

if (tailBlock->number < headBlock->number)

{

// Not a loop. We didn't see any back-edge.

headBlock->isLoopHeader = false;

headBlock->GetFirstInstr()->AsLabelInstr()->m_isLoopTop = false;

return;

}

Assert(headBlock->isLoopHeader);

Loop *loop = JitAnewZ(this->GetFunc()->m_alloc, Loop, this->GetFunc()->m_alloc, this->GetFunc());

loop->next = this->loopList;

this->loopList = loop;

headBlock->loop = loop;

loop->headBlock = headBlock;

loop->int32SymsOnEntry = nullptr;

loop->lossyInt32SymsOnEntry = nullptr;

// If parentLoop is a parent of loop, it's headBlock better appear first.

if (parentLoop && loop->headBlock->number > parentLoop->headBlock->number)

{

loop->parent = parentLoop;

parentLoop->isLeaf = false;

}

loop->hasDeadStoreCollectionPass = false;

loop->hasDeadStorePrepass = false;

loop->memOpInfo = nullptr;

loop->doMemOp = true;

NoRecoverMemoryJitArenaAllocator tempAlloc(_u("BE-LoopBuilder"), this->func->m_alloc->GetPageAllocator(), Js::Throw::OutOfMemory);

WalkLoopBlocks(tailBlock, loop, &tempAlloc);

Assert(loop->GetHeadBlock() == headBlock);

IR::LabelInstr * firstInstr = loop->GetLoopTopInstr();

firstInstr->SetLoop(loop);

if (firstInstr->IsProfiledLabelInstr())

{

loop->SetImplicitCallFlags(firstInstr->AsProfiledLabelInstr()->loopImplicitCallFlags);

if (this->func->HasProfileInfo() && this->func->GetReadOnlyProfileInfo()->IsLoopImplicitCallInfoDisabled())

{

loop->SetImplicitCallFlags(this->func->GetReadOnlyProfileInfo()->GetImplicitCallFlags());

}

loop->SetLoopFlags(firstInstr->AsProfiledLabelInstr()->loopFlags);

}

else

{

// Didn't collect profile information, don't do optimizations

loop->SetImplicitCallFlags(Js::ImplicitCall_All);

}

}

Loop::MemCopyCandidate* Loop::MemOpCandidate::AsMemCopy()

{

Assert(this->IsMemCopy());

return (Loop::MemCopyCandidate*)this;

}

Loop::MemSetCandidate* Loop::MemOpCandidate::AsMemSet()

{

Assert(this->IsMemSet());

return (Loop::MemSetCandidate*)this;

}

void

Loop::EnsureMemOpVariablesInitialized()

{

Assert(this->doMemOp);

if (this->memOpInfo == nullptr)

{

JitArenaAllocator *allocator = this->GetFunc()->GetTopFunc()->m_fg->alloc;

this->memOpInfo = JitAnewStruct(allocator, Loop::MemOpInfo);

this->memOpInfo->inductionVariablesUsedAfterLoop = nullptr;

this->memOpInfo->startIndexOpndCache[0] = nullptr;

this->memOpInfo->startIndexOpndCache[1] = nullptr;

this->memOpInfo->startIndexOpndCache[2] = nullptr;

this->memOpInfo->startIndexOpndCache[3] = nullptr;

this->memOpInfo->inductionVariableChangeInfoMap = JitAnew(allocator, Loop::InductionVariableChangeInfoMap, allocator);

this->memOpInfo->inductionVariableOpndPerUnrollMap = JitAnew(allocator, Loop::InductionVariableOpndPerUnrollMap, allocator);

this->memOpInfo->candidates = JitAnew(allocator, Loop::MemOpList, allocator);

}

}

// Walk the basic blocks backwards until we find the loop header.

// Mark basic blocks in the loop by looking at the predecessors

// of blocks known to be in the loop.

// Recurse on inner loops.

void

FlowGraph::WalkLoopBlocks(BasicBlock *block, Loop *loop, JitArenaAllocator *tempAlloc)

{

AnalysisAssert(loop);

BVSparse<JitArenaAllocator> *loopBlocksBv = JitAnew(tempAlloc, BVSparse<JitArenaAllocator>, tempAlloc);

BasicBlock *tailBlock = block;

BasicBlock *lastBlock;

loopBlocksBv->Set(block->GetBlockNum());

this->AddBlockToLoop(block, loop);

if (block == loop->headBlock)

{

// Single block loop, we're done

return;

}

do

{

BOOL isInLoop = loopBlocksBv->Test(block->GetBlockNum());

FOREACH_SUCCESSOR_BLOCK(succ, block)

{

if (succ->isLoopHeader)

{

// Found a loop back-edge

if (loop->headBlock == succ)

{

isInLoop = true;

}

else if (succ->loop == nullptr || succ->loop->headBlock != succ)

{

// Recurse on inner loop

BuildLoop(succ, block, isInLoop ? loop : nullptr);

}

}

} NEXT_SUCCESSOR_BLOCK;

if (isInLoop)

{

// This block is in the loop. All of it's predecessors should be contained in the loop as well.

FOREACH_PREDECESSOR_BLOCK(pred, block)

{

// Fix up loop parent if it isn't set already.

// If pred->loop != loop, we're looking at an inner loop, which was already visited.

// If pred->loop->parent == nullptr, this is the first time we see this loop from an outer

// loop, so this must be an immediate child.

if (pred->loop && pred->loop != loop && loop->headBlock->number < pred->loop->headBlock->number

&& (pred->loop->parent == nullptr || pred->loop->parent->headBlock->number < loop->headBlock->number))

{

pred->loop->parent = loop;

loop->isLeaf = false;

if (pred->loop->hasCall)

{

loop->SetHasCall();

}

loop->SetImplicitCallFlags(pred->loop->GetImplicitCallFlags());

}

// Add pred to loop bit vector

loopBlocksBv->Set(pred->GetBlockNum());

} NEXT_PREDECESSOR_BLOCK;

if (block->loop == nullptr || block->loop->IsDescendentOrSelf(loop))

{

block->loop = loop;

}

if (block != tailBlock)

{

this->AddBlockToLoop(block, loop);

}

}

lastBlock = block;

block = block->GetPrev();

} while (lastBlock != loop->headBlock);

}

// Add block to this loop, and it's parent loops.

void

FlowGraph::AddBlockToLoop(BasicBlock *block, Loop *loop)

{

loop->blockList.Prepend(block);

if (block->hasCall)

{

loop->SetHasCall();

}

}

///----------------------------------------------------------------------------

///

/// FlowGraph::AddBlock

///

/// Finish processing of a new block: hook up successor arcs, note loops, etc.

///

///----------------------------------------------------------------------------

BasicBlock *

FlowGraph::AddBlock(

IR::Instr * firstInstr,

IR::Instr * lastInstr,

BasicBlock * nextBlock)

{

BasicBlock * block;

IR::LabelInstr * labelInstr;

if (firstInstr->IsLabelInstr())

{

labelInstr = firstInstr->AsLabelInstr();

}

else

{

labelInstr = IR::LabelInstr::New(Js::OpCode::Label, firstInstr->m_func);

labelInstr->SetByteCodeOffset(firstInstr);

if (firstInstr->IsEntryInstr())

{

firstInstr->InsertAfter(labelInstr);

}

else

{

firstInstr->InsertBefore(labelInstr);

}

firstInstr = labelInstr;

}

block = labelInstr->GetBasicBlock();

if (block == nullptr)

{

block = BasicBlock::New(this);

labelInstr->SetBasicBlock(block);

// Remember last block in function to target successor of RETs.

if (!this->tailBlock)

{

this->tailBlock = block;

}

}

// Hook up the successor edges

if (lastInstr->EndsBasicBlock())

{

BasicBlock * blockTarget = nullptr;

if (lastInstr->IsBranchInstr())

{

// Hook up a successor edge to the branch target.

IR::BranchInstr * branchInstr = lastInstr->AsBranchInstr();

if(branchInstr->IsMultiBranch())

{

BasicBlock * blockMultiBrTarget;

IR::MultiBranchInstr * multiBranchInstr = branchInstr->AsMultiBrInstr();

multiBranchInstr->MapUniqueMultiBrLabels([&](IR::LabelInstr * labelInstr) -> void

{

blockMultiBrTarget = SetBlockTargetAndLoopFlag(labelInstr);

this->AddEdge(block, blockMultiBrTarget);

});

}

else

{

IR::LabelInstr * targetLabelInstr = branchInstr->GetTarget();

blockTarget = SetBlockTargetAndLoopFlag(targetLabelInstr);

if (branchInstr->IsConditional())

{

IR::Instr *instrNext = branchInstr->GetNextRealInstrOrLabel();

if (instrNext->IsLabelInstr())

{

SetBlockTargetAndLoopFlag(instrNext->AsLabelInstr());

}

}

}

}

else if (lastInstr->m_opcode == Js::OpCode::Ret && block != this->tailBlock)

{

blockTarget = this->tailBlock;

}

if (blockTarget)

{

this->AddEdge(block, blockTarget);

}

}

if (lastInstr->HasFallThrough())

{

// Add a branch to next instruction so that we don't have to update the flow graph