Skip to main content

Browse the archive

Revision 53401f1cb4e829b3a0d74295473c9a48fff2bbab authored by Keno Fischer on 29 October 2020, 21:36:53 UTC, committed by Keno Fischer on 29 October 2020, 21:48:17 UTC 
Improve optimization of harmless call cycles
 
When inference detects a call cycle, one of two things could happen:
1. It determines that in order for inference to converge it needs
   to limit the signatures of some methods to something more general, or
2. The cycle is determined to be harmless at the inference level (because
   though there is a cycle in the CFG there is no dependency cycle of
   type information).

In the first case, we simply disable optimizations, which is sensible,
because we're likely to have to recompute some information anyway,
when we actually get there dynamically.

In the second case however, we do do optimizations, but it's a bit
of an unusual case. In particular, inference usually delivers
methods to inlining in postorder (meaning callees get optimized
before their callers) such that a caller can always inline a callee.

However, if there is a cycle, there is of course no unique postorder
of functions, since by definition we're looking a locally strongly
connected component. In this case, we would just essentially pick
an arbitrary order (and moreover, depending on the point at which
we enter the cycle and subsequently cached, leading to potential
performance instabilities, depending on function order).
However, the arbitrary order is quite possibly
suboptimal. For example in #36414, we have a cycle
randn -> _randn -> randn_unlikely -> rand. In this cycle the author
of this code expected both `randn` and `_randn` to inline and
annotated the functions as such. However, in 1.5+ the order we happed
to pick would have inlined randn_unlikely into _randn (had it not
been marked noinline), with a hard call break between randn and
_randn, whch is problematic from a performance standpoint.

This PR aims to address this by introducing a heuristic: If some
functions in a cycle are marked as `@noinline`, we want to make
sure to infer these last (since they won't ever be inlined anyway).
To ensure this happens, while restoring postorder if this happens
to break the cycle, we perform a DFS traversal rooted at any `@noinline`
functions and then optimize the functions in the cycle in DFS-postorder.
Of course still may still not be a true postorder in the inlining
graph (if the `@noinline` functions don't break the cycle), but
even in that case, it should be no worse than the default order.

Fixes #36414
Closes #37234
1 parent 0d5c38b
Raw File
.clang-format 
Language: Cpp
Standard: Cpp11
AccessModifierOffset: -4
AlignAfterOpenBracket: Align
AlignConsecutiveAssignments: false
AlignConsecutiveDeclarations: false
AlignConsecutiveMacros: false
AlignEscapedNewlines: Left
AlignOperands: true
AlignTrailingComments: false
AllowAllArgumentsOnNextLine: true
AllowAllConstructorInitializersOnNextLine: true
AllowAllParametersOfDeclarationOnNextLine: true
AllowShortBlocksOnASingleLine: Never
AllowShortCaseLabelsOnASingleLine: true
AllowShortFunctionsOnASingleLine: Inline
AllowShortIfStatementsOnASingleLine: Never
AllowShortLambdasOnASingleLine: All
AllowShortLoopsOnASingleLine: false
AlwaysBreakAfterDefinitionReturnType: None
AlwaysBreakAfterReturnType: None
AlwaysBreakBeforeMultilineStrings: false
AlwaysBreakTemplateDeclarations: true
BinPackArguments: true
BinPackParameters: true
BreakBeforeBinaryOperators: None
BreakBeforeBraces: Stroustrup
BreakBeforeInheritanceComma: false
BreakBeforeTernaryOperators: false
BreakConstructorInitializers: BeforeColon
BreakConstructorInitializersBeforeComma: false
BreakInheritanceList: BeforeColon
BreakStringLiterals: false
ColumnLimit: 92
CommentPragmas: '^ IWYU pragma:'
CompactNamespaces: false
ConstructorInitializerAllOnOneLineOrOnePerLine: true
ConstructorInitializerIndentWidth: 2
ContinuationIndentWidth: 4
Cpp11BracedListStyle: true
DeriveLineEnding: true
DerivePointerAlignment: false
DisableFormat: false
ExperimentalAutoDetectBinPacking: false
FixNamespaceComments: false
IncludeBlocks: Preserve
IncludeCategories:
  - Regex:           '^(<|"(llvm|llvm-c|clang|clang-c)/)'
    Priority:        2
  - Regex:           '^<.*'
    Priority:        3
  - Regex:           '.*'
    Priority:        1
IncludeIsMainSourceRegex: ''
IndentCaseLabels: false
IndentGotoLabels: false
IndentPPDirectives: None
IndentWidth: 4
IndentWrappedFunctionNames: false
KeepEmptyLinesAtTheStartOfBlocks: false
MacroBlockBegin: ''
MacroBlockEnd: ''
MaxEmptyLinesToKeep: 2
NamespaceIndentation: None
PenaltyBreakAssignment: 2
PenaltyBreakBeforeFirstCallParameter: 30
PenaltyBreakComment: 300
PenaltyBreakFirstLessLess: 120
PenaltyBreakString: 1000
PenaltyBreakTemplateDeclaration: 10
PenaltyExcessCharacter: 1000000
PenaltyReturnTypeOnItsOwnLine: 60
PointerAlignment: Right
ReflowComments: true
SortIncludes: true
SortUsingDeclarations: true
SpaceAfterCStyleCast: false
SpaceAfterLogicalNot: false
SpaceAfterTemplateKeyword: false
SpaceBeforeAssignmentOperators: true
SpaceBeforeCpp11BracedList: false
SpaceBeforeCtorInitializerColon: true
SpaceBeforeInheritanceColon: true
SpaceBeforeParens: ControlStatements
SpaceBeforeRangeBasedForLoopColon: true
SpaceBeforeSquareBrackets: false
SpaceInEmptyBlock: false
SpaceInEmptyParentheses: false
SpacesBeforeTrailingComments: 1
SpacesInAngles: false
SpacesInCStyleCastParentheses: false
SpacesInConditionalStatement: false
SpacesInContainerLiterals: true
SpacesInParentheses: false
SpacesInSquareBrackets: false
TabWidth: 8
UseCRLF: true
UseTab: Never
ForEachMacros:
  - JL_TRY
  - JL_CATCH
StatementMacros:
  - bi_fintrinsic
  - bi_iintrinsic_fast
  - bi_intrinsic_ctype
  - bool_fintrinsic
  - bool_iintrinsic_fast
  - bool_intrinsic_ctype
  - checked_intrinsic_ctype
  - cvt_iintrinsic
  - fpiseq_n
  - fpislt_n
  - ter_fintrinsic
  - ter_intrinsic_ctype
  - un_fintrinsic
  - un_fintrinsic_withtype
  - un_iintrinsic_ctype
  - uu_iintrinsic_ctype
back to top