Do dependency computation checks for OpenCL and...
software interpreter like in CPU threading.
This patch also reworks the cycle detection
to make it more robust.
Since the dependency computation also does
cycle detection, there is no need to disable
group-calc(threaded/OpenCL/SW Interpreter)
for non-leaf nodes in recursive interpret.
The rework of cycle detection ensures that
it fixes tdf#95748 correctly.
Change-Id: I460addb768eedc0914491a3d24ae7220c3afbb20
Reviewed-on: https://gerrit.libreoffice.org/55665
Reviewed-by: Michael Meeks <michael.meeks@collabora.com>
Tested-by: Jenkins
diff --git a/sc/inc/column.hxx b/sc/inc/column.hxx
index bff5e62..5da3490 100644
--- a/sc/inc/column.hxx
+++ b/sc/inc/column.hxx
@@ -576,7 +576,7 @@ public:
bool ResolveStaticReference( ScMatrix& rMat, SCCOL nMatCol, SCROW nRow1, SCROW nRow2 );
void FillMatrix( ScMatrix& rMat, size_t nMatCol, SCROW nRow1, SCROW nRow2, svl::SharedStringPool* pPool ) const;
formula::VectorRefArray FetchVectorRefArray( SCROW nRow1, SCROW nRow2 );
bool HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2 );
bool HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2, const ScFormulaCellGroupRef& mxGroup );
void SetFormulaResults( SCROW nRow, const double* pResults, size_t nLen );
void SetFormulaResults( SCROW nRow, const formula::FormulaConstTokenRef* pResults, size_t nLen );
diff --git a/sc/inc/document.hxx b/sc/inc/document.hxx
index ad371bd7..86079dd 100644
--- a/sc/inc/document.hxx
+++ b/sc/inc/document.hxx
@@ -2384,7 +2384,7 @@ public:
formula::FormulaTokenRef ResolveStaticReference( const ScRange& rRange );
formula::VectorRefArray FetchVectorRefArray( const ScAddress& rPos, SCROW nLength );
bool HandleRefArrayForParallelism( const ScAddress& rPos, SCROW nLength );
bool HandleRefArrayForParallelism( const ScAddress& rPos, SCROW nLength, const ScFormulaCellGroupRef& mxGroup );
/**
* Call this before any operations that might trigger one or more formula
diff --git a/sc/inc/formulacell.hxx b/sc/inc/formulacell.hxx
index 78eb1f6..a9df1a3 100644
--- a/sc/inc/formulacell.hxx
+++ b/sc/inc/formulacell.hxx
@@ -68,6 +68,7 @@ public:
bool mbInvariant:1;
bool mbSubTotal:1;
bool mbSeenInPath:1; // For detecting cycle of formula groups
bool mbPartOfCycle:1; // To flag FG's part of a cycle
sal_uInt8 meCalcState;
@@ -142,8 +143,13 @@ private:
ScFormulaCell( const ScFormulaCell& ) = delete;
bool InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope& aScope);
bool InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& aScope);
bool CheckComputeDependencies(sc::FormulaLogger::GroupScope& rScope);
bool InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope& aScope,
bool& bDependencyComputed,
bool& bDependencyCheckFailed);
bool InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& aScope,
bool& bDependencyComputed,
bool& bDependencyCheckFailed);
bool InterpretInvariantFormulaGroup();
public:
diff --git a/sc/inc/recursionhelper.hxx b/sc/inc/recursionhelper.hxx
index b8ca1d0..030e52c 100644
--- a/sc/inc/recursionhelper.hxx
+++ b/sc/inc/recursionhelper.hxx
@@ -104,6 +104,19 @@ public:
void PopFormulaGroup();
};
/** A class to wrap ScRecursionHelper::PushFormulaGroup(),
ScRecursionHelper::PopFormulaGroup() and make these calls
exception safe. */
class ScFormulaGroupCycleCheckGuard
{
ScRecursionHelper& mrRecHelper;
bool mbShouldPop;
public:
ScFormulaGroupCycleCheckGuard() = delete;
ScFormulaGroupCycleCheckGuard(ScRecursionHelper& rRecursionHelper, ScFormulaCellGroup* pGrp);
~ScFormulaGroupCycleCheckGuard();
};
#endif // INCLUDED_SC_INC_RECURSIONHELPER_HXX
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
diff --git a/sc/inc/table.hxx b/sc/inc/table.hxx
index e7886b1..a097812 100644
--- a/sc/inc/table.hxx
+++ b/sc/inc/table.hxx
@@ -987,7 +987,7 @@ public:
formula::FormulaTokenRef ResolveStaticReference( SCCOL nCol, SCROW nRow );
formula::FormulaTokenRef ResolveStaticReference( SCCOL nCol1, SCROW nRow1, SCCOL nCol2, SCROW nRow2 );
formula::VectorRefArray FetchVectorRefArray( SCCOL nCol, SCROW nRow1, SCROW nRow2 );
bool HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2 );
bool HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2, const ScFormulaCellGroupRef& mxGroup );
void SplitFormulaGroups( SCCOL nCol, std::vector<SCROW>& rRows );
void UnshareFormulaCells( SCCOL nCol, std::vector<SCROW>& rRows );
diff --git a/sc/source/core/data/column2.cxx b/sc/source/core/data/column2.cxx
index 912428f..5ef16b9 100644
--- a/sc/source/core/data/column2.cxx
+++ b/sc/source/core/data/column2.cxx
@@ -48,6 +48,7 @@
#include <scmatrix.hxx>
#include <rowheightcontext.hxx>
#include <tokenstringcontext.hxx>
#include <recursionhelper.hxx>
#include <editeng/eeitem.hxx>
@@ -2831,7 +2832,7 @@ formula::VectorRefArray ScColumn::FetchVectorRefArray( SCROW nRow1, SCROW nRow2
return formula::VectorRefArray(formula::VectorRefArray::Invalid);
}
bool ScColumn::HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2 )
bool ScColumn::HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2, const ScFormulaCellGroupRef& mxGroup )
{
if (nRow1 > nRow2)
return false;
@@ -2858,6 +2859,12 @@ bool ScColumn::HandleRefArrayForParallelism( SCROW nRow1, SCROW nRow2 )
{
// Loop inside the formula block.
(*itCell)->MaybeInterpret();
// child cell's Interpret could result in calling dependency calc
// and that could detect a cycle involving mxGroup
// and do early exit in that case.
if (mxGroup->mbPartOfCycle)
return false;
}
nRow += nEnd - nOffset;
break;
diff --git a/sc/source/core/data/document.cxx b/sc/source/core/data/document.cxx
index f970fd4..58777dc 100644
--- a/sc/source/core/data/document.cxx
+++ b/sc/source/core/data/document.cxx
@@ -1803,13 +1803,13 @@ void ScDocument::UnlockAdjustHeight()
--nAdjustHeightLock;
}
bool ScDocument::HandleRefArrayForParallelism( const ScAddress& rPos, SCROW nLength )
bool ScDocument::HandleRefArrayForParallelism( const ScAddress& rPos, SCROW nLength, const ScFormulaCellGroupRef& mxGroup )
{
SCTAB nTab = rPos.Tab();
if (!TableExists(nTab))
return false;
return maTabs[nTab]->HandleRefArrayForParallelism(rPos.Col(), rPos.Row(), rPos.Row()+nLength-1);
return maTabs[nTab]->HandleRefArrayForParallelism(rPos.Col(), rPos.Row(), rPos.Row()+nLength-1, mxGroup);
}
bool ScDocument::CanFitBlock( const ScRange& rOld, const ScRange& rNew )
diff --git a/sc/source/core/data/formulacell.cxx b/sc/source/core/data/formulacell.cxx
index 2de28fc..dc13f05 100644
--- a/sc/source/core/data/formulacell.cxx
+++ b/sc/source/core/data/formulacell.cxx
@@ -529,6 +529,7 @@ ScFormulaCellGroup::ScFormulaCellGroup() :
mbInvariant(false),
mbSubTotal(false),
mbSeenInPath(false),
mbPartOfCycle(false),
meCalcState(sc::GroupCalcEnabled)
{
}
@@ -1474,6 +1475,15 @@ void ScFormulaCell::Interpret()
{
ScRecursionHelper& rRecursionHelper = pDocument->GetRecursionHelper();
if (mxGroup && mxGroup->mbSeenInPath)
{
// This call arose from a dependency calculation and
// we just found a cycle.
// This will mark all elements in the cycle as parts-of-cycle
ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, mxGroup.get());
return;
}
#if DEBUG_CALCULATION
static bool bDebugCalculationInit = true;
if (bDebugCalculationInit)
@@ -1529,13 +1539,6 @@ void ScFormulaCell::Interpret()
{
pDocument->IncInterpretLevel();
bool bCheckForFGCycle = mxGroup && !pDocument->IsThreadedGroupCalcInProgress() &&
mxGroup->meCalcState == sc::GroupCalcEnabled &&
ScCalcConfig::isThreadingEnabled();
bool bPopFormulaGroup = false;
if (bCheckForFGCycle)
bPopFormulaGroup = rRecursionHelper.PushFormulaGroup(mxGroup.get());
#if DEBUG_CALCULATION
aDC.enterGroup();
bool bGroupInterpreted = InterpretFormulaGroup();
@@ -1547,9 +1550,6 @@ void ScFormulaCell::Interpret()
InterpretTail( pDocument->GetNonThreadedContext(), SCITP_NORMAL);
#endif
if (bPopFormulaGroup)
rRecursionHelper.PopFormulaGroup();
pDocument->DecInterpretLevel();
}
@@ -2452,7 +2452,10 @@ void ScFormulaCell::SetDirtyVar()
bDirty = true;
mbPostponedDirty = false;
if (mxGroup && mxGroup->meCalcState == sc::GroupCalcRunning)
{
mxGroup->meCalcState = sc::GroupCalcEnabled;
mxGroup->mbPartOfCycle = false;
}
// mark the sheet of this cell to be calculated
//#FIXME do we need to revert this remnant of old fake vba events? pDocument->AddCalculateTable( aPos.Tab() );
@@ -4164,13 +4167,15 @@ struct ScDependantsCalculator
{
ScDocument& mrDoc;
const ScTokenArray& mrCode;
const ScFormulaCellGroupRef& mxGroup;
const SCROW mnLen;
const ScAddress& mrPos;
ScDependantsCalculator(ScDocument& rDoc, const ScTokenArray& rCode, const ScFormulaCell& rCell, const ScAddress& rPos) :
mrDoc(rDoc),
mrCode(rCode),
mnLen(rCell.GetCellGroup()->mnLength),
mxGroup(rCell.GetCellGroup()),
mnLen(mxGroup->mnLength),
mrPos(rPos)
{
}
@@ -4303,16 +4308,6 @@ struct ScDependantsCalculator
// Trim data array length to actual data range.
SCROW nTrimLen = trimLength(aRefPos.Tab(), aRefPos.Col(), aRefPos.Col(), aRefPos.Row(), mnLen);
// Fetch double array guarantees that the length of the
// returned array equals or greater than the requested
// length.
formula::VectorRefArray aArray;
if (nTrimLen)
aArray = mrDoc.FetchVectorRefArray(aRefPos, nTrimLen);
if (!aArray.isValid())
return false;
aRangeList.Join(ScRange(aRefPos.Col(), aRefPos.Row(), aRefPos.Tab(),
aRefPos.Col(), aRefPos.Row() + nTrimLen - 1, aRefPos.Tab()));
@@ -4391,7 +4386,7 @@ struct ScDependantsCalculator
for (auto nCol = rRange.aStart.Col(); nCol <= rRange.aEnd.Col(); nCol++)
{
if (!mrDoc.HandleRefArrayForParallelism(ScAddress(nCol, rRange.aStart.Row(), rRange.aStart.Tab()),
rRange.aEnd.Row() - rRange.aStart.Row() + 1))
rRange.aEnd.Row() - rRange.aStart.Row() + 1, mxGroup))
return false;
}
}
@@ -4407,12 +4402,9 @@ bool ScFormulaCell::InterpretFormulaGroup()
auto aScope = sc::FormulaLogger::get().enterGroup(*pDocument, *this);
ScRecursionHelper& rRecursionHelper = pDocument->GetRecursionHelper();
if (rRecursionHelper.GetRecursionCount())
if (mxGroup->mbPartOfCycle)
{
// Do not attempt to interpret a group when calculations are already
// running, otherwise we may run into a circular reference hell. See
// tdf#95748
aScope.addMessage("group calc disabled during recursive calculation.");
aScope.addMessage("This formula-group is part of a cycle");
return false;
}
@@ -4444,57 +4436,85 @@ bool ScFormulaCell::InterpretFormulaGroup()
// ScFormulaCell::InterpretTail()
RecursionCounter aRecursionCounter( rRecursionHelper, this);
bool bDependencyComputed = false;
bool bDependencyCheckFailed = false;
// Preference order:
// First try OpenCL, but only if actual OpenCL is available (i.e. no SwInterpreter).
// Then try threading and as the last one try SwInterpreter.
if( ScCalcConfig::isOpenCLEnabled())
if( InterpretFormulaGroupOpenCL(aScope))
if( InterpretFormulaGroupOpenCL(aScope, bDependencyComputed, bDependencyCheckFailed))
return true;
if( InterpretFormulaGroupThreading(aScope))
if( InterpretFormulaGroupThreading(aScope, bDependencyComputed, bDependencyCheckFailed))
return true;
return InterpretFormulaGroupOpenCL(aScope);
return InterpretFormulaGroupOpenCL(aScope, bDependencyComputed, bDependencyCheckFailed);
}
bool ScFormulaCell::CheckComputeDependencies(sc::FormulaLogger::GroupScope& rScope)
{
ScRecursionHelper& rRecursionHelper = pDocument->GetRecursionHelper();
// iterate over code in the formula ...
// ensure all input is pre-calculated -
// to avoid writing during the calculation
bool bOKToParallelize = false;
{
ScFormulaGroupCycleCheckGuard aCycleCheckGuard(rRecursionHelper, mxGroup.get());
if (mxGroup->mbPartOfCycle)
{
mxGroup->meCalcState = sc::GroupCalcDisabled;
rScope.addMessage("found circular formula-group dependencies");
return false;
}
ScDependantsCalculator aCalculator(*pDocument, *pCode, *this, mxGroup->mpTopCell->aPos);
bOKToParallelize = aCalculator.DoIt();
}
if (rRecursionHelper.IsInRecursionReturn())
{
mxGroup->meCalcState = sc::GroupCalcDisabled;
rScope.addMessage("Recursion limit reached, cannot thread this formula group now");
return false;
}
if (mxGroup->mbPartOfCycle)
{
mxGroup->meCalcState = sc::GroupCalcDisabled;
rScope.addMessage("found circular formula-group dependencies");
return false;
}
if (!bOKToParallelize)
{
mxGroup->meCalcState = sc::GroupCalcDisabled;
rScope.addMessage("could not do new dependencies calculation thing");
return false;
}
return true;
}
// To be called only from InterpretFormulaGroup().
bool ScFormulaCell::InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope& aScope)
bool ScFormulaCell::InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope& aScope,
bool& bDependencyComputed,
bool& bDependencyCheckFailed)
{
static const bool bThreadingProhibited = std::getenv("SC_NO_THREADED_CALCULATION");
if (!bThreadingProhibited &&
if (!bDependencyCheckFailed && !bThreadingProhibited &&
pCode->IsEnabledForThreading() &&
ScCalcConfig::isThreadingEnabled())
{
// iterate over code in the formula ...
// ensure all input is pre-calculated -
// to avoid writing during the calculation
ScDependantsCalculator aCalculator(*pDocument, *pCode, *this, mxGroup->mpTopCell->aPos);
// Disable or hugely enlarge subset for S/W group
// threading interpreter
bool bOKToThread = aCalculator.DoIt();
if (pDocument->GetRecursionHelper().IsInRecursionReturn())
if(!bDependencyComputed && !CheckComputeDependencies(aScope))
{
mxGroup->meCalcState = sc::GroupCalcDisabled;
aScope.addMessage("Recursion limit reached, cannot thread this formula group now");
bDependencyComputed = true;
bDependencyCheckFailed = true;
return false;
}
if (!bOKToThread)
{
mxGroup->meCalcState = sc::GroupCalcDisabled;
aScope.addMessage("could not do new dependencies calculation thing");
return false;
}
if (mxGroup->meCalcState == sc::GroupCalcDisabled)
{
aScope.addMessage("found circular formula-group dependencies");
return false;
}
bDependencyComputed = true;
const static bool bHyperThreadingActive = tools::cpuid::hasHyperThreading();
@@ -4584,7 +4604,9 @@ bool ScFormulaCell::InterpretFormulaGroupThreading(sc::FormulaLogger::GroupScope
}
// To be called only from InterpretFormulaGroup().
bool ScFormulaCell::InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& aScope)
bool ScFormulaCell::InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& aScope,
bool& bDependencyComputed,
bool& bDependencyCheckFailed)
{
bool bCanVectorize = pCode->IsEnabledForOpenCL();
switch (pCode->GetVectorState())
@@ -4622,6 +4644,18 @@ bool ScFormulaCell::InterpretFormulaGroupOpenCL(sc::FormulaLogger::GroupScope& a
return false;
}
if (bDependencyCheckFailed)
return false;
if(!bDependencyComputed && !CheckComputeDependencies(aScope))
{
bDependencyComputed = true;
bDependencyCheckFailed = true;
return false;
}
bDependencyComputed = true;
// TODO : Disable invariant formula group interpretation for now in order
// to get implicit intersection to work.
if (mxGroup->mbInvariant && false)
diff --git a/sc/source/core/data/table1.cxx b/sc/source/core/data/table1.cxx
index 3129eff..76cd876 100644
--- a/sc/source/core/data/table1.cxx
+++ b/sc/source/core/data/table1.cxx
@@ -2309,7 +2309,7 @@ formula::VectorRefArray ScTable::FetchVectorRefArray( SCCOL nCol, SCROW nRow1, S
return aCol[nCol].FetchVectorRefArray(nRow1, nRow2);
}
bool ScTable::HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2 )
bool ScTable::HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2, const ScFormulaCellGroupRef& mxGroup )
{
if (nRow2 < nRow1)
return false;
@@ -2317,7 +2317,7 @@ bool ScTable::HandleRefArrayForParallelism( SCCOL nCol, SCROW nRow1, SCROW nRow2
if ( !IsColValid( nCol ) || !ValidRow( nRow1 ) || !ValidRow( nRow2 ) )
return false;
return aCol[nCol].HandleRefArrayForParallelism(nRow1, nRow2);
return aCol[nCol].HandleRefArrayForParallelism(nRow1, nRow2, mxGroup);
}
ScRefCellValue ScTable::GetRefCellValue( SCCOL nCol, SCROW nRow )
diff --git a/sc/source/core/tool/recursionhelper.cxx b/sc/source/core/tool/recursionhelper.cxx
index 665ee2a..0c185db 100644
--- a/sc/source/core/tool/recursionhelper.cxx
+++ b/sc/source/core/tool/recursionhelper.cxx
@@ -109,9 +109,7 @@ bool ScRecursionHelper::PushFormulaGroup(ScFormulaCellGroup* pGrp)
{
--nIdx;
assert(nIdx >= 0);
auto& eCalcState = aFGList[nIdx]->meCalcState;
if (eCalcState == sc::GroupCalcEnabled)
eCalcState = sc::GroupCalcDisabled;
aFGList[nIdx]->mbPartOfCycle = true;
} while (aFGList[nIdx] != pGrp);
return false;
@@ -131,4 +129,16 @@ void ScRecursionHelper::PopFormulaGroup()
aFGList.pop_back();
}
ScFormulaGroupCycleCheckGuard::ScFormulaGroupCycleCheckGuard(ScRecursionHelper& rRecursionHelper, ScFormulaCellGroup* pGrp) :
mrRecHelper(rRecursionHelper)
{
mbShouldPop = mrRecHelper.PushFormulaGroup(pGrp);
}
ScFormulaGroupCycleCheckGuard::~ScFormulaGroupCycleCheckGuard()
{
if (mbShouldPop)
mrRecHelper.PopFormulaGroup();
}
/* vim:set shiftwidth=4 softtabstop=4 expandtab: */
