Revision bf97c297435104ff8a3ed265757874e2f63268e9 authored by Shuhei Kadowaki on 21 December 2021, 17:05:57 UTC, committed by Shuhei Kadowaki on 08 January 2022, 04:57:06 UTC
This commit allows elimination of mutable φ-node (and its predecessor mutables allocations).
As an contrived example, it allows this `mutable_ϕ_elim(::String, ::Vector{String})`
to run without any allocations at all:
```julia
function mutable_ϕ_elim(x, xs)
r = Ref(x)
for x in xs
r = Ref(x)
end
return r[]
end
let xs = String[string(gensym()) for _ in 1:100]
mutable_ϕ_elim("init", xs)
@test @allocated(mutable_ϕ_elim("init", xs)) == 0
end
```
This mutable ϕ-node elimination is still limited though.
Most notably, the current implementation doesn't work if a mutable
allocation forms multiple ϕ-nodes, since we check allocation eliminability
(i.e. escapability) by counting usages counts and thus it's hard to
reason about multiple ϕ-nodes at a time.
For example, currently mutable allocations involved in cases like below
will still not be eliminated:
```julia
code_typed((Bool,String,String),) do cond, x, y
if cond
ϕ2 = ϕ1 = Ref(x)
else
ϕ2 = ϕ1 = Ref(y)
end
ϕ1[], ϕ2[]
end
\# more realistic example
mutable struct Point{T}
x::T
y::T
end
add(a::Point, b::Point) = Point(a.x + b.x, a.y + b.y)
function compute(a::Point{ComplexF64}, b::Point{ComplexF64})
for i in 0:(100000000-1)
a = add(add(a, b), b)
end
a.x, a.y
end
```
I'd say this limitation should be addressed by first introducing a better
abstraction for reasoning escape information. More specifically, I'd like
introduce EscapeAnalysis.jl into Julia base first, and then gradually
adapt it to improve our SROA pass, since EA will allow us to reason about
all escape information imposed on whatever object more easily and should
help us get rid of the complexities of our current SROA implementation.
For now, I'd like to get in this enhancement even though it has the
limitation elaborated above, as far as this commit doesn't introduce
latency problem (which is unlikely).
1 parent a9c6daf
abi_x86.cpp
//===-- abi_x86.cpp - x86 ABI description -----------------------*- C++ -*-===//
//
// LDC – the LLVM D compiler
//
// This file is distributed under the BSD-style LDC license:
//
// Copyright (c) 2007-2012 LDC Team.
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
// * Neither the name of the LDC Team nor the names of its contributors may be
// used to endorse or promote products derived from this software without
// specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
// ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
// (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
// LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
// ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
// SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
//
//===----------------------------------------------------------------------===//
//
// The ABI implementation used for 32 bit x86 targets.
//
//===----------------------------------------------------------------------===//
struct ABI_x86Layout : AbiLayout {
STATIC_INLINE bool is_complex_type(jl_datatype_t *dt)
{
static jl_sym_t *Complex_sym = NULL;
if (Complex_sym == NULL)
Complex_sym = jl_symbol("Complex");
return jl_is_datatype(dt) && dt->name->name == Complex_sym && dt->name->module == jl_base_module;
}
inline bool is_complex64(jl_datatype_t *dt) const
{
return is_complex_type(dt) && jl_tparam0(dt) == (jl_value_t*)jl_float32_type;
}
inline bool is_complex128(jl_datatype_t *dt) const
{
return is_complex_type(dt) && jl_tparam0(dt) == (jl_value_t*)jl_float64_type;
}
bool use_sret(jl_datatype_t *dt, LLVMContext &ctx) override
{
size_t size = jl_datatype_size(dt);
if (size == 0)
return false;
if (is_complex64(dt) || (jl_is_primitivetype(dt) && size <= 8))
return false;
return true;
}
bool needPassByRef(jl_datatype_t *dt, AttrBuilder &ab, LLVMContext &ctx, Type *Ty) override
{
size_t size = jl_datatype_size(dt);
if (is_complex64(dt) || is_complex128(dt) || (jl_is_primitivetype(dt) && size <= 8))
return false;
ab.addByValAttr(Ty);
return true;
}
Type *preferred_llvm_type(jl_datatype_t *dt, bool isret, LLVMContext &ctx) const override
{
if (!isret)
return NULL;
// special case Complex{Float32} as a return type
if (is_complex64(dt))
return T_int64;
return NULL;
}
};
Computing file changes ...
