Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit efb6f47

Browse filesBrowse files
knewbury01knewbury01
authored
Merge pull request #891 from github/michaelrfairhurst/compatible-types-performance-fix-alt
Michaelrfairhurst/compatible types performance fix alt
2 parents 0edeb8f + 7e0ff96 commit efb6f47
Copy full SHA for efb6f47

9 files changed

+346
-115
lines changed

‎c/cert/src/rules/DCL40-C/IncompatibleFunctionDeclarations.ql

Copy file name to clipboardExpand all lines: c/cert/src/rules/DCL40-C/IncompatibleFunctionDeclarations.ql
+10-2Lines changed: 10 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,12 @@ import codingstandards.c.cert
1919
import codingstandards.cpp.types.Compatible
2020
import ExternalIdentifiers
2121

22+
predicate interestedInFunctions(FunctionDeclarationEntry f1, FunctionDeclarationEntry f2) {
23+
not f1 = f2 and
24+
f1.getDeclaration() = f2.getDeclaration() and
25+
f1.getName() = f2.getName()
26+
}
27+
2228
from ExternalIdentifiers d, FunctionDeclarationEntry f1, FunctionDeclarationEntry f2
2329
where
2430
not isExcluded(f1, Declarations2Package::incompatibleFunctionDeclarationsQuery()) and
@@ -29,10 +35,12 @@ where
2935
f1.getName() = f2.getName() and
3036
(
3137
//return type check
32-
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig>::equalReturnTypes(f1, f2)
38+
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig, interestedInFunctions/2>::equalReturnTypes(f1,
39+
f2)
3340
or
3441
//parameter type check
35-
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig>::equalParameterTypes(f1, f2)
42+
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig, interestedInFunctions/2>::equalParameterTypes(f1,
43+
f2)
3644
) and
3745
// Apply ordering on start line, trying to avoid the optimiser applying this join too early
3846
// in the pipeline

‎c/misra/src/rules/RULE-23-5/DangerousDefaultSelectionForPointerInGeneric.ql

Copy file name to clipboardExpand all lines: c/misra/src/rules/RULE-23-5/DangerousDefaultSelectionForPointerInGeneric.ql
+8-12Lines changed: 8 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -20,18 +20,14 @@ import codingstandards.cpp.types.LvalueConversion
2020
import codingstandards.cpp.types.SimpleAssignment
2121

2222
predicate typesCompatible(Type t1, Type t2) {
23-
TypeEquivalence<TypesCompatibleConfig, TypeFromGeneric>::equalTypes(t1, t2)
23+
TypeEquivalence<TypesCompatibleConfig, relevantTypes/2>::equalTypes(t1, t2)
2424
}
2525

26-
class TypeFromGeneric extends Type {
27-
TypeFromGeneric() {
28-
exists(C11GenericExpr g |
29-
(
30-
this = g.getAssociationType(_) or
31-
this = g.getControllingExpr().getFullyConverted().getType()
32-
)
33-
)
34-
}
26+
predicate relevantTypes(Type a, Type b) {
27+
exists(C11GenericExpr g |
28+
a = g.getAnAssociationType() and
29+
b = getLvalueConverted(g.getControllingExpr().getFullyConverted().getType())
30+
)
3531
}
3632

3733
predicate missesOnPointerConversion(Type provided, Type expected) {
@@ -40,11 +36,11 @@ predicate missesOnPointerConversion(Type provided, Type expected) {
4036
// But 6.5.16.1 simple assignment constraints would have been satisfied:
4137
(
4238
// Check as if the controlling expr is assigned to the expected type:
43-
SimpleAssignment<TypeFromGeneric>::satisfiesSimplePointerAssignment(expected, provided)
39+
SimpleAssignment<relevantTypes/2>::satisfiesSimplePointerAssignment(expected, provided)
4440
or
4541
// Since developers typically rely on the compiler to catch const/non-const assignment
4642
// errors, don't assume a const-to-non-const generic selection miss was intentional.
47-
SimpleAssignment<TypeFromGeneric>::satisfiesSimplePointerAssignment(provided, expected)
43+
SimpleAssignment<relevantTypes/2>::satisfiesSimplePointerAssignment(provided, expected)
4844
)
4945
}
5046

‎c/misra/src/rules/RULE-8-3/DeclarationsOfAFunctionSameNameAndType.ql

Copy file name to clipboardExpand all lines: c/misra/src/rules/RULE-8-3/DeclarationsOfAFunctionSameNameAndType.ql
+9-2Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,6 +16,11 @@ import cpp
1616
import codingstandards.c.misra
1717
import codingstandards.cpp.types.Compatible
1818

19+
predicate interestedInFunctions(FunctionDeclarationEntry f1, FunctionDeclarationEntry f2) {
20+
not f1 = f2 and
21+
f1.getDeclaration() = f2.getDeclaration()
22+
}
23+
1924
from FunctionDeclarationEntry f1, FunctionDeclarationEntry f2, string case, string pluralDo
2025
where
2126
not isExcluded(f1, Declarations4Package::declarationsOfAFunctionSameNameAndTypeQuery()) and
@@ -24,12 +29,14 @@ where
2429
f1.getDeclaration() = f2.getDeclaration() and
2530
//return type check
2631
(
27-
not FunctionDeclarationTypeEquivalence<TypeNamesMatchConfig>::equalReturnTypes(f1, f2) and
32+
not FunctionDeclarationTypeEquivalence<TypeNamesMatchConfig, interestedInFunctions/2>::equalReturnTypes(f1,
33+
f2) and
2834
case = "return type" and
2935
pluralDo = "does"
3036
or
3137
//parameter type check
32-
not FunctionDeclarationTypeEquivalence<TypeNamesMatchConfig>::equalParameterTypes(f1, f2) and
38+
not FunctionDeclarationTypeEquivalence<TypeNamesMatchConfig, interestedInFunctions/2>::equalParameterTypes(f1,
39+
f2) and
3340
case = "parameter types" and
3441
pluralDo = "do"
3542
or

‎c/misra/src/rules/RULE-8-3/DeclarationsOfAnObjectSameNameAndType.ql

Copy file name to clipboardExpand all lines: c/misra/src/rules/RULE-8-3/DeclarationsOfAnObjectSameNameAndType.ql
+9-10Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -16,15 +16,6 @@ import cpp
1616
import codingstandards.c.misra
1717
import codingstandards.cpp.types.Compatible
1818

19-
class RelevantType extends Type {
20-
RelevantType() {
21-
exists(VariableDeclarationEntry decl |
22-
(relevantPair(decl, _) or relevantPair(_, decl)) and
23-
decl.getType() = this
24-
)
25-
}
26-
}
27-
2819
predicate relevantPair(VariableDeclarationEntry decl1, VariableDeclarationEntry decl2) {
2920
not decl1 = decl2 and
3021
not decl1.getVariable().getDeclaringType().isAnonymous() and
@@ -43,12 +34,20 @@ predicate relevantPair(VariableDeclarationEntry decl1, VariableDeclarationEntry
4334
)
4435
}
4536

37+
predicate relevantTypes(Type a, Type b) {
38+
exists(VariableDeclarationEntry varA, VariableDeclarationEntry varB |
39+
a = varA.getType() and
40+
b = varB.getType() and
41+
relevantPair(varA, varB)
42+
)
43+
}
44+
4645
from VariableDeclarationEntry decl1, VariableDeclarationEntry decl2
4746
where
4847
not isExcluded(decl1, Declarations4Package::declarationsOfAnObjectSameNameAndTypeQuery()) and
4948
not isExcluded(decl2, Declarations4Package::declarationsOfAnObjectSameNameAndTypeQuery()) and
5049
relevantPair(decl1, decl2) and
51-
not TypeEquivalence<TypeNamesMatchConfig, RelevantType>::equalTypes(decl1.getType(),
50+
not TypeEquivalence<TypeNamesMatchConfig, relevantTypes/2>::equalTypes(decl1.getType(),
5251
decl2.getType())
5352
select decl1,
5453
"The object $@ of type " + decl1.getType().toString() +

‎c/misra/src/rules/RULE-8-4/CompatibleDeclarationFunctionDefined.ql

Copy file name to clipboardExpand all lines: c/misra/src/rules/RULE-8-4/CompatibleDeclarationFunctionDefined.ql
+15-2Lines changed: 15 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,17 @@ import codingstandards.c.misra
1919
import codingstandards.cpp.Identifiers
2020
import codingstandards.cpp.types.Compatible
2121

22+
predicate interestedInFunctions(FunctionDeclarationEntry f1, FunctionDeclarationEntry f2) {
23+
f1.getDeclaration() instanceof ExternalIdentifiers and
24+
f1.isDefinition() and
25+
f1.getDeclaration() = f2.getDeclaration() and
26+
// This condition should always hold, but removing it affects join order performance.
27+
f1.getName() = f2.getName() and
28+
not f2.isDefinition() and
29+
not f1.isFromTemplateInstantiation(_) and
30+
not f2.isFromTemplateInstantiation(_)
31+
}
32+
2233
from FunctionDeclarationEntry f1
2334
where
2435
not isExcluded(f1, Declarations4Package::compatibleDeclarationFunctionDefinedQuery()) and
@@ -38,10 +49,12 @@ where
3849
f2.getDeclaration() = f1.getDeclaration() and
3950
(
4051
//return types differ
41-
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig>::equalReturnTypes(f1, f2)
52+
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig, interestedInFunctions/2>::equalReturnTypes(f1,
53+
f2)
4254
or
4355
//parameter types differ
44-
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig>::equalParameterTypes(f1, f2)
56+
not FunctionDeclarationTypeEquivalence<TypesCompatibleConfig, interestedInFunctions/2>::equalParameterTypes(f1,
57+
f2)
4558
or
4659
//parameter names differ
4760
parameterNamesUnmatched(f1, f2)

‎c/misra/src/rules/RULE-8-4/CompatibleDeclarationObjectDefined.ql

Copy file name to clipboardExpand all lines: c/misra/src/rules/RULE-8-4/CompatibleDeclarationObjectDefined.ql
+8-8Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -19,13 +19,13 @@ import codingstandards.c.misra
1919
import codingstandards.cpp.Identifiers
2020
import codingstandards.cpp.types.Compatible
2121

22-
class RelevantType extends Type {
23-
RelevantType() {
24-
exists(VariableDeclarationEntry decl |
25-
count(VariableDeclarationEntry others | others.getDeclaration() = decl.getDeclaration()) > 1 and
26-
decl.getType() = this
27-
)
28-
}
22+
predicate relevantTypes(Type a, Type b) {
23+
exists(VariableDeclarationEntry varA, VariableDeclarationEntry varB |
24+
not varA = varB and
25+
varA.getDeclaration() = varB.getDeclaration() and
26+
a = varA.getType() and
27+
b = varB.getType()
28+
)
2929
}
3030

3131
from VariableDeclarationEntry decl1
@@ -37,7 +37,7 @@ where
3737
not exists(VariableDeclarationEntry decl2 |
3838
not decl2.isDefinition() and
3939
decl1.getDeclaration() = decl2.getDeclaration() and
40-
TypeEquivalence<TypesCompatibleConfig, RelevantType>::equalTypes(decl1.getType(),
40+
TypeEquivalence<TypesCompatibleConfig, relevantTypes/2>::equalTypes(decl1.getType(),
4141
decl2.getType())
4242
)
4343
select decl1, "No separate compatible declaration found for this definition."

‎change_notes/2025-04-25-improve-type-comparison-performance.md

Copy file name to clipboard
+6Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
- `RULE-8-3`, `RULE-8-4`, `DCL40-C`, `RULE-23-5`: `DeclarationsOfAFunctionSameNameAndType.ql`, `DeclarationsOfAnObjectSameNameAndType.ql`, `CompatibleDeclarationOfFunctionDefined.ql`, `CompatibleDeclarationObjectDefined.ql`, `IncompatibleFunctionDeclarations.ql`, `DangerousDefaultSelectionForPointerInGeneric.ql`:
2+
- Added pragmas to alter join order on function parameter equivalence (names and types).
3+
- Refactored expression which the optimizer was confused by, and compiled into a cartesian product.
4+
- Altered the module `Compatible.qll` to compute equality in two stages. Firstly, all pairs of possible type comparisons (including recursive comparisons) are found, then those pairwise comparisons are evaluated in a second stage. This greatly reduces the number of comparisons and greatly improves performance.
5+
- `RULE-23-5`: `DangerousDefaultSelectionForPointerInGeneric.ql`:
6+
- Altered the module `SimpleAssignment.qll` in accordance with the changes to `Compatible.qll`.

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.