We introduce a "dead code" optimization like pass on the AST.
The goal is to simplify away, in a `SequenceNode`, everything that
follows a node with sports a `nofallthrough behavior.
Delay the `SwitchBreaksFixer` beautify pass run.
Specifically, we run it last, as this pass computes information used
only by the backend, and the information it depends upon may be
invalidated by some passes that transform `switch`es (as the
`simplifyDualSwitch` pass).
Delay as much as possible the loop promotion passes, in order to catch
more opportunities.
Specifically, we now perform the loop promotion after the dual case
`switch` promotion pass.
Implement a new beautify pass which simplifies away `SwitchBreakNode`s
that constitute the entire body of `case`s in `switch`es, that do not,
have a `default` case. In such situations indeed, the semantics is,
preserved by removing the `SwitchBreakNode`s.
Various improvements to the debug graphs for `restructure-cfg` and
`beautify`:
- Normalize casing and syntax of debug graphs.
- Improve the graph folders name and layout.
- Implement `CFGDumper` and `ASTDumper` for when we need a serialization
with incremental indexes.
- Remove old and stale graph serializations.
We introduce the `InlineDispatcherSwitch` beautify pass. Its goal is to
try and inline the body of some of the `case`s of a exit dispatcher, in
place of the `SetNode` corresponding to that `case`, if this doesn't
introduce duplication in the code (i.e., a single `SetNode` for that
specific case value is present).
Additionally, if the inlining procedure is able to completely remove the
necessity of an exit dispatcher altogether, the pass removes it.
The pass is able to handle chains of weaved dispatcher `switch`es
referring to the same original dispatcher `switch`, by handling the
inline operation and the possible simplification level-wise.
The inlining procedure, cannot take place if a `SetNode` is contained in
the body of the case we are trying to inline, since this can possibly
break the semantics of the state variable of a loop, by placing a
`SetNode` in a more internal loop.
We introduce the PromoteCallNoReturn beautification pass. Its goal is to
restructure sequence of statements, in order to have `call`s to
`noreturn` functions as _inlined_ in the middle of the statement
sequence, and leave _non local control flow statements_ at the end of
that scope. E.g., we prefer:
```
if (cond)
call noreturnfunc();
return;
```
to
```
if (!cond)
return;
call noreturnfunc();
```
In order to do this, contextually, we restructure the routine computing
the `fallthrough` property, in order to be able to differentiate between
the _non local control flow statements_, a call to a `noreturn`
function, or a generic mix of the two (useful when combining results
from the two situations above).
The new analysis is also used in the `promoteNoFallThrough` promotion
pass.
This commits reorders the beautifiers so that do-while loops are matched
before while loops.
This has the effect that loops that can be matched both as while and
do-while loops end up matched as do-while.
The consequence is that we generate C code with a layout that is much
more similar to assembly, and prevents duplicating code to recompute the
condition of the while.
Move the `simplifyImplicitContinue` at the end of the beautify pass,
after all the pass that modify the anatomy of the ASTTree.
Before this change, the pass was run before some changes that moved some
`continue`s in positions where they are not considered implicit.
Added an assertion which checks that during the `noFallThrough`
promotion phase, no implicit `ContinueNode` is present.
Improve the `fallThroughScope` computation, in order to handle calls to
`NoReturn` functions in the analysis, representing the fact that they
induce a `noFallthrough` scope (i.e., execution will not ever resume
after the call, and therefore we can later improve the nesting of the
code with the `promoteNoFallthrough` pass).
We introduce a simplification step, which looks for `switch`es that can
be reduced to simpler `if` statements.
Specifically, the logic is the following:
1) When we identify a `switch` statement composed by a single `case` and
a possible default, we transform it into an `if` with the `case` now
corresponding to the `then`, and the `default` corresponding to the
`else`, if present.
2) When we identify a `switch` statement composed by two `case`s, and no
`default` is present, we can promote it to an `if` with `then` `else`
branches.
Other key details:
- The promotion happens only if we can identify at least one of the
`case`s that have a single element in the `case` label. If this is not
the case, we do not promote one to RHS of the `if` condition.
- A new `CompareNode` class, inheriting from `ExprNode`, is created, in
order to represent the equality or inequality condition of an `IfNode`
instance that is the result of the promotion. This `CompareNode` can
represent for the LHS both an `llvm::Value` or the `loop_state_var`,
while it embeds the RHS constant which completes the comparison.
- We remove `SwitchBreak` AST nodes that may now appear as children of
an `if` node promoted from a `switch`.
- We introduce in the `CompareNode` the `weaved` concept. Indeed, if a
promotion of a weaved `switch` happens, we should avoid the
serialization of the instructions leading to the computation of the
condition of the original `switch`, because they have been already
emitted by the main related dominating `switch`.
We also introduce an additional simplification step, which takes care
of:
- Promoting `!(==)` to `(!=)` and `!(!=)` to `(==)`, if the inner
equal/not equal is represented via a `CompareNode`.
- Promoting `x == 0` to `!x` and `x != 0` to `x`.
To be able to correctly emit (or not) the instructions computing a
condition of an `IfNode`, we need to add the `EmittBB` flag, an
additional parameter to the `buildGHASTCondition` function, which
controls the emission of the statements of a basic block computing a
condition.
Consequently, the `IfNode` acquires a `IsWeaved` field, which is used to
mirror the property having the same name on `SwitchNode`. Being now
possible a promotion from a dual `SwitchNode` to an `IfNode`, we need to
represent this property on the `IfNode` too.
The `default` `case` is now a standard `case`, and it is identified only
by having the `label` set empty.
Therefore, a list of beautify and transformation actions now do not need
special casing in order to handle the `default` `case`, which is reached
during the standard iteration over the `case`s.
A special accessor is still necessary, in order to correctly emit the
`default` `case` in the backend.
Introduce implicit statements simplification phase, specifically:
- A implicit `return` simplification: `return` statements in `void`
type functions, which are not followed by any other scope, can be
omitted.
- A implicit `continue` simplification: `continue` statements whose
fallthrough leads directly to the end of the cycle scope (i.e., to
execute another iteration of the enclosing loop), can be omitted.
In order to avoid the printing of the implicit `return`, we need an
additional `emitReturn` parameter in the `emitBasicBlock` method of the
`CCodeGenerator` class.
This commit drops some old broken code that was a leftover from when
MarkAssignments didn't inject calls to Assign, and that was poorly
migrated to Assign, causing it to be dead code.
This commit fixes a bug in the hasSideEffects function, used to evaluate
if an ExprNode has side effects.
Before this commit, when calling hasSideEffects on a NotNode, the
return value was true if the operand of NotNode **did not** have side
effects, which is wrong.
This commit changes the behaviour so that a NotNode has side effects if
and only if its only operand has side effects.
This commit fixes a bug in the hasSideEffects function, used to evaluate
if an ExprNode has side effects.
Before this commit, when calling hasSideEffects on an AndNode, the
return value was true if **both** the LHS and RHS of the AndNode had
side effects, which is wrong.
This commit changes the behaviour so that if **either** LHS **or** the
RHS of the And have any side effect, than hasSideEffects returns true
for the And.
Before this commit, the simplifyShortCircuit beautifier did not recur on
the then/else branch of an IfNode, basically stopping recursion very
early and potentially missing a lot of beautification opportunities.
Introduce the hybrid beautifier aiming to simplify double `not`s (one on
the IR side (e.g., a `icmp ne`), and one on the `ExprNode` side on the
`GHAST` in the form of a `NotNode`.
To do this hybrid beautifier, we basically need to do the following:
- Implement a preliminary collection phase which computes which
`ExprNode`s are affected by which `BasicBlock`.
- Compute the so-called consesus, i.e., verify that for all the
`ExprNode`s affected by a certain `BasicBlock`, the transformation
would be beneficial in terms of output. Basically:
1) That the number of `!(!=)` transformed into `(==)` outscores the
number of correlated `(!=)` which are transformed into `!(==)`.
2) That the number of `!(==)` transformed into `(!=)` outscores the
number of correlated `(==)` which are transformed into `!(!=)`.
- Actually perform the transformation for those situations where the
consensus agrees.
A bug introduced no loop promotion by mistake, we now correctly exit the
loop promotion routine if the loop has been already promoted to `while`
or `do-while` loop.
This commit does various things oriented at reducing the number of local
variables emitted in C:
- MarkAssignments now know that @Copy and @Assign involving
@LocalVariable only have side effects that affect the local variable
itself; this enables to reduce the number of times we're forced to
emit a local variable due to interfering side effects
- Drop the @AssignmentMarker FunctionTag; AddAssignmentMarkerPass now
doesn't emit @AssignmentMarker anymore; instead it emits groups of
@LocalVariable, @Copy, and @Assign, which benefit from the previous
point
- Drop 2 MarkAssignments::Reasons: HasManyUses and HasUsesOutsideOfBB;
both these have now been aggregated into the AlwaysAssign reason for
simplicity, representing all reasons non involving side effects
- Update BeautifyGHAST and how it reasons about side effects when
beautifying; before this commit it used @AssignmentMarker, now it
looks at @Assign
- Simplify ExitSSA; before this commit it was trying hard to be smart on
where it emitted the store instructions representing the incoming
values of the PHI that was being destroyed; this seemed smart when we
originally did it but it generated C code that was not really better
to read, so this useless complexity is finally gone
The beautification library was split into a separate library for
historical reason, having to do with LLVM passes, their dependencies,
and dirty hacks we had around.
Now the LLVM passes, and the hacks are gone, so we can merge back
everything together.
Alessandro Di Federico