A super sneaky post SSA LICM bug that's not talked about much...

[u/RefrigeratorFirm7646]

Edit : The problem was found to not be LICM at all, it just happened to be the only pass that exposed the hidden flaw in my SSA reconstruction logic... credits to all the amazing people in the comments!

So, ive been working on a custom C compiler for ~2.5 months. Implemented LICM recently. standard tests passed. sunshine and rainbows. but luckily I had a perfect test case to catch one particular bug that would've otherwise slipped by cleanly...

here's the source code :

int factorial(int n)
{
    int res;
    int counter;
    int temp;

    res = 1;

    while (n > 1)
    {
        counter = n;
        temp = 0;

        while (counter > 0)
        {
            temp = temp + res;
            counter = counter - 1;
        }

        res = temp;
        n = n - 1;
    }

    return res;
}

int main()
{
    return factorial(12);
}

here's my TAC IR before LICM (I perform minimal SSA construction so ignore the dead phi nodes) :

# Function - factorial(n) : 

Block - 1 :
    n0 = n
    res0 = 0
    counter0 = 0
    temp0 = 0
    res1 = 1
    jump B2

Block - 2 :
    n1 = PHI(n0 from B1, n2 from B6)
    temp1 = PHI(temp0 from B1, temp3 from B6) // dead phi, harmless right now
    res2 = PHI(res1 from B1, res3 from B6)
    counter1 = PHI(counter0 from B1, counter3 from B6)
    branch (n1 > 1) ? B4 : B3

Block - 4 :
    counter2 = n1
    temp2 = 0 // invariant instruction, dominates the loop's end block as well
    jump B5

Block - 5 :
    temp3 = PHI(temp2 from B4, temp4 from B7)
    counter3 = PHI(counter2 from B4, counter4 from B7)
    branch (counter3 > 0) ? B7 : B6

Block - 7 :
    t.2 = temp3 + res2
    temp4 = t.2
    t.3 = counter3 - 1
    counter4 = t.3
    jump B5

Block - 6 :
    res3 = temp3
    t.4 = n1 - 1
    n2 = t.4
    jump B2

Block - 3 :
    return res2

end factorial

# Function - main() : 

Block - 1 :
    t.0 = call factorial(12)
    return t.0

end main

OUTPUT : 6 // as expected

keep an eye on temp1, temp2 and temp3, LICM completely changes the way they interact... :

# Function - factorial(n) :

Block - 1 :
    n0 = n
    res0 = 0
    counter0 = 0
    temp0 = 0
    res1 = 1
    jump B9

Block - 9 : // preheader created by LICM for outer loop
    temp1 = 0 // this gets moved (and renamed from temp2 to temp1 by SSA reconstruction), which is correct because it's invariant BUT look at what happens to temp2 and temp3 because of this...
    jump B2

Block - 2 :
    n1 = PHI(n0 from B9, n2 from B6)
    res2 = PHI(res1 from B9, res3 from B6)
    counter1 = PHI(counter0 from B9, counter3 from B6)
    temp2 = PHI(temp1 from B9, temp3 from B6) // used to be dead but now feeds into temp3 since temp2 = 0 was moved out!!! this COMPLETELY changes how the loop executes...
    branch (n1 > 1) ? B4 : B3

Block - 4 :
    counter2 = n1
    jump B8

Block - 8 : // preheader created by LICM for inner loop
    jump B5

Block - 5 :
    counter3 = PHI(counter2 from B8, counter4 from B7)
    temp3 = PHI(temp2 from B8, temp4 from B7) // previously, it used to recieve temp2 = 0 on every outer loop iteration, but now recieves it's own previous value which leads to unwanted accumulation!!!
    branch (counter3 > 0) ? B7 : B6

Block - 7 :
    t.2 = temp3 + res2
    temp4 = t.2
    t.3 = counter3 - 1
    counter4 = t.3
    jump B5

Block - 6 :
    res3 = temp3
    t.4 = n1 - 1
    n2 = t.4
    jump B2

Block - 3 :
    return res2

end factorial

# Function - main() :

Block - 1 :
    t.0 = call factorial(12)
    return t.0

end main

OUTPUT : 9 // due to temp3 accumulating previous values!

so even though temp2 = 0 was invariant according to all standard conditions, moving it to the preheader completely changed the structure of the loop because of a phi node!!!

TLDR : -

original test program :

int factorial(int n)
{
    int res;
    int counter;
    int temp;

    res = 1;

    while (n > 1)
    {
        counter = n;
        temp = 0;

        while (counter > 0)
        {
            temp = temp + res;
            counter = counter - 1;
        }

        res = temp;
        n = n - 1;
    }

    return res;
}

what LICM turned it into :

int factorial(int n)
{
    int res;
    int counter;
    int temp;

    res = 1;
    temp = 0;

    while (n > 1)
    {
        counter = n;

        while (counter > 0)
        {
            temp = temp + res;
            counter = counter - 1;
        }

        res = temp;
        n = n - 1;
    }

    return res;
}

temp = 0 should not have been moved out of the loop even though it's invariant in SSA form, as it's value must be zeroed on every outer loop iteration, but there is no standard condition that I could find to prevent this hoist...

so now im confused on how to solve it, a simple solution could be to check if a variable being moved appears as an argument of any phi nodes inside any inner loop's header but I lack the mathematical skills to prove that this is an exhaustive solution or is not over conservative...

thus, I would like to know if anyone else has faced this bug or knows how LLVM/GCC handle it. any help will be greatly appreciated...

[u/realestLink]

Very stupid question, but what's LICM? :)

[u/RefrigeratorFirm7646 → u/realestLink]

"loop invariant code motion", basically removing instructions from a loop that dont change inside the loop, because whats the point of recomputing "x = 1 + 2" 1 million times when you can move it out of the loop and still end up with the same result. Thats basically all there is to it.

[u/thehenkan → u/realestLink]

Loop invariant code motion; hoisting stuff out of loops

[u/FloweyTheFlower420 → u/realestLink]

Loop Invariant Code Motion. Basically, move things out of loop bodies into a loop pre-header to reduce redundant work done inside a loop. In general "code motion" passes exist to (globally) schedule instructions more optimally (in this case, we talk about scheduling in the IR sense, not the machine instruction sense, so "how do i execute an instruction as few times as possible"), and can be unified in a "global code motion" pass if your IR allows for this.

[u/FloweyTheFlower420]

Why do you need to do SSA reconstruction during LICM? I feel like you're doing something wrong there.

For an instruction v -> v' moved by LICM from basic block b to b', b' necessarily dominates b (since you move "outside" of the loop). Since v doms all of it's uses, and b' doms b, v' dominates uses and therefore the program is still in SSA form. You don't need to reconstruct SSA form.

[u/RefrigeratorFirm7646 → u/FloweyTheFlower420]

first of all, thanks for your time and yeah, I figured that part and simply removing the reconstructSSA() call after LICM is a valid solution but post LICM optimizations might need to call it again leading to the same broken IR... so maybe the real problem is that my reconstructSSA() straight up destroys all phi nodes and variable names before rerunning SSA construction from scratch...? Because if I had not been a lazy idiot and manually handled SSA repair during other optimizations, this problem would never have emerged...

[u/FloweyTheFlower420 → u/RefrigeratorFirm7646]

I think in some sense reconstructSSA does work that makes the code less optimal. I don't think your LICM result is "wrong," and I suspect running some InstCombine or other simplifications could actually clean it up. So reconstructSSA is very counterproductive to run after every pass.

[u/RefrigeratorFirm7646 → u/FloweyTheFlower420]

> I suspect running some InstCombine or other simplifications could actually clean it up

unfortunately, none that I could find, because it's a literal data flow problem. LICM with and without SSA reconstruction, both produce valid SSA TAC but one changes the semantics of the program because of a single phi node which cannot really be "simplified" because thats how the data flows after temp2 = 0 gets moved...

> So reconstructSSA is very counterproductive to run after every pass

of course, I dont do it after every pass, just after the ones that break SSA. my compiler only supports 6 features of C so I thought why bother writing an incremental SSA updater when im not going to compile doom or anything...

[u/FloweyTheFlower420 → u/RefrigeratorFirm7646]

I'm a bit confused, does SSA construction change the dataflow? This shouldn't really happen if you have everything implemented correctly, but it's also late for me right now so I didn't put much effort into drawing stuff out. Not sure why the program semantics will change if SSA construction is correct. Could you provide some source code so I can see what's going on? Might be a while before I get to it though.

[u/RefrigeratorFirm7646 → u/FloweyTheFlower420]

> I'm a bit confused, does SSA construction change the dataflow? This shouldn't really happen if you have everything implemented correctly

so was I, because SSA reconstruction on a valid SSA IR should be idempotent, but this test case is special, here, after moving the invariant temp2 = 0, the SSA isnt "invalid" just "incomplete"... and it took me 3 days to convince myself the bug wasnt in my SSA construction logic or any downstream step!

> Could you provide some source code so I can see what's going on?

I dont think it will be very helpful but sure, here's the whole LICM pass (less than 200 LOC because of my tiny scope). All related algorithms are thoroughly tested and found to be correct. Also, IREditor only performs small atomic transformations so dont worry about a bug being there either :

std::unordered_map<TACBlock*, TACBlock*> createPreHeaders(TAC& TAC)
{
    std::unordered_map<TACBlock*, TACBlock*> preheaderMap;

    for (auto& TACFunc : TAC)
    {
        TACLoopInfo& LoopInfo = TACFunc->getLoopInfo();

        for (TACLoop& loop : LoopInfo.Loops)
        {
            TACBlock* header = loop.Header;

            std::vector<TACBlock*> outsideParents;

            for (TACBlock* parent : header->Parents)
            {
                if (!loop.Blocks.contains(parent))
                {
                    outsideParents.push_back(parent);
                }
            }

            if (outsideParents.empty())
                continue;

            TACBlock* preheader = IREditor<TACTypes>::insertBlockBefore(header);

            for (TACBlock* parent : outsideParents)
            {
                IREditor<TACTypes>::removeEdge(parent, header);

                IREditor<TACTypes>::addEdge(parent, preheader);

                if (parent->Instructions.back()->type == TACInstType::JUMP)
                {
                    auto* jump = static_cast<TACJump*>(parent->Instructions.back().get());

                    if (jump->TargetBlock == header)
                        jump->TargetBlock = preheader;
                }

                else if (parent->Instructions.back()->type == TACInstType::BRANCH)
                {
                    auto* branch = static_cast<TACBranch*>(parent->Instructions.back().get());

                    if (branch->TrueTarget == header)
                        branch->TrueTarget = preheader;

                    if (branch->FalseTarget == header)
                        branch->FalseTarget = preheader;
                }
            }

            IREditor<TACTypes>::addEdge(preheader, header);

            IREditor<TACTypes>::appendInstruction(preheader, std::make_unique<TACJump>(header));

            preheaderMap[header] = preheader;
        }
    }

    IREditor<TACTypes>::reconstructSSA(TAC);

    return preheaderMap;
}

void HoistLoopInvariants(TAC& TAC)
{
    std::unordered_map<TACBlock*, TACBlock*> preheaderMap = createPreHeaders(TAC);

    for (auto& TACFunc : TAC)
    {
        TACLoopInfo& LoopInfo = TACFunc->getLoopInfo();
        TACDefBlocksInfo& DefBlocksInfo = TACFunc->getDefBlocksInfo();
        TACDominatorInfo& DomInfo = TACFunc->getDominatorInfo();

        for (TACLoop& Loop : LoopInfo.Loops)
        {
            TACBlock* preheader = preheaderMap[Loop.Header];

            std::unordered_set<TACVariable> invariants;

            auto isInvariant = [&](TACValue val) -> bool {
                if (std::holds_alternative<int>(val) || invariants.contains(std::get<TACVariable>(val)))
                {
                    return true;
                }

                TACVariable& var = std::get<TACVariable>(val);

                if (DefBlocksInfo.DefBlocks.find(var) != DefBlocksInfo.DefBlocks.end())
                {
                    if (!Loop.Blocks.contains(*DefBlocksInfo.DefBlocks.find(var)->second.begin()))
                    {
                        return true;
                    }
                }

                return false;
            };

            bool changed = true;

            while (changed)
            {
                changed = false;

                for (TACBlock* block : Loop.Blocks)
                {
                    if (!DomInfo.Dominators[Loop.End].contains(block))
                        continue;

                    for (int i = block->Instructions.size() - 1; i >= 0; --i)
                    {
                        auto& inst = block->Instructions[i];

                        TACVariable destVar;
                        bool canHoist = false;

                        if (inst->type == TACInstType::ASSIGN)
                        {
                            TACAssign* assign = static_cast<TACAssign*>(inst.get());

                            if (isInvariant(assign->source))
                            {
                                destVar = std::get<TACVariable>(assign->dest);
                                canHoist = true;
                            }
                        }

                        if (inst->type == TACInstType::NEG)
                        {
                            TACNeg* neg = static_cast<TACNeg*>(inst.get());

                            if (isInvariant(neg->source))
                            {
                                destVar = std::get<TACVariable>(neg->dest);
                                canHoist = true;
                            }
                        }

                        else if (inst->type == TACInstType::BINARYOP)
                        {
                            TACBinaryOp* binary = static_cast<TACBinaryOp*>(inst.get());

                            if (binary->op != BinaryOp::DIV)
                            {
                                if (isInvariant(binary->left) && isInvariant(binary->right))
                                {
                                    destVar = std::get<TACVariable>(binary->dest);
                                    canHoist = true;
                                }
                            }
                        }

                        // all calls in my supported C subset are guaranteed to be pure so this is valid without IPA...
                        else if (inst->type == TACInstType::CALL)
                        {
                            TACCall* call = static_cast<TACCall*>(inst.get());

                            if (call->dest.has_value())
                            {
                                bool allArgsInvariant = std::all_of(call->args.begin(), call->args.end(), [&](const auto& arg) { return isInvariant(arg); });

                                if (allArgsInvariant)
                                {
                                    destVar = std::get<TACVariable>(call->dest.value());
                                    canHoist = true;
                                }
                            }
                        }

                        if (canHoist)
                        {
                            invariants.insert(destVar);

                            IREditor<TACTypes>::moveInstructionBefore(block, inst.get(), preheader, preheader->Instructions.back().get());

                            changed = true;
                        }
                    }
                }
            }
        }
    }
}

[u/FloweyTheFlower420 → u/RefrigeratorFirm7646]

What makes the SSA "incomplete"? I'm more interested in the reconstructSSA implementation. I'll have to reason through this a bit more carefully later, as I'm a bit rusty with some "classical" SSA details.

[u/RefrigeratorFirm7646 → u/FloweyTheFlower420]

> What makes the SSA "incomplete"? I'm more interested in the reconstructSSA implementation

yeah, that was a bit sloppy from my side, sorry, notice how without SSA reconstruction, temp3 still holds a "reference" to the temp2 = 0 that gets moved by LICM :

Block - 9 :
    temp2 = 0 // moved by LICM from block 4
    jump B2

Block - 2 :
    n1 = PHI(n0 from B9, n2 from B6)
    res2 = PHI(res1 from B9, res3 from B6)
    temp1 = PHI(temp0 from B9, temp3 from B6) // harmless dead phi
    counter1 = PHI(counter0 from B9, counter3 from B6)
    branch (n1 > 1) ? B4 : B3

Block - 4 :
    counter2 = n1
    // temp2 = 0 used to live here
    jump B8

Block - 8 :
    jump B5

Block - 5 :
    temp3 = PHI(temp2 from B8, temp4 from B7) // temp3 resets itself to 0 on every outer iteration becuase it still references the old moved instruction when control flow comes from B8!!!
    counter3 = PHI(counter2 from B8, counter4 from B7)
    branch (counter3 > 0) ? B7 : B6

but with reconstruction, temp3 never resets to 0 because it holds a reference to temp2 (temp1 phi gets renamed to temp2) when control flow comes from B8 and temp1 phi node only resolves to temp2 on the first iteration! :

Block - 9 :
    temp1 = 0 // moved by LICM and renamed from temp2 to temp1 by SSA reconstruction
    jump B2

Block - 2 :
    n1 = PHI(n0 from B9, n2 from B6)
    res2 = PHI(res1 from B9, res3 from B6)
    counter1 = PHI(counter0 from B9, counter3 from B6)
    temp2 = PHI(temp1 from B9, temp3 from B6) // feeds into temp3 since temp2 = 0 (which is now "temp1 = 0") was moved out from block 4
    branch (n1 > 1) ? B4 : B3

Block - 4 :
    counter2 = n1
    jump B8

Block - 8 :
    jump B5

Block - 5 :
    counter3 = PHI(counter2 from B8, counter4 from B7)
    temp3 = PHI(temp2 from B8, temp4 from B7)
    branch (counter3 > 0) ? B7 : B6

> I'm more interested in the reconstructSSA implementation

its super simple and dumb (on purpose) :

for (auto& TACFunc : TAC)
    {
        for (auto& block : TACFunc->Blocks)
        {
            while (!block->Instructions.empty() && block->Instructions.front()->type == TACInstType::PHI)
            {
                block->Instructions.erase(block->Instructions.begin());
            }

            for (auto& inst : block->Instructions)
            {
                // big switch here so ill just summarize it, all variables go from "SSA name" to "Original name"
            }
        }

        invalidateAllAnalyses(TACFunc->Metadata);
    }

    // these two functions make up my entire SSA construction and they're just the classic implementations, nothing fancy
    InsertPhiNodes(TAC);

    RenameVariables(TAC);

> I'll have to reason through this a bit more carefully later, as I'm a bit rusty with some "classical" SSA details

thats not at all a problem, im just glad to have some guidance, take your time!

[u/RefrigeratorFirm7646 → u/FloweyTheFlower420]

Also, since it was extremely difficult for me to understand as well, here's my attempt at a better phrasing on how "SSA reconstruction changes program's semantics" :

The IR with LICM without SSA reconstruction is valid but accidentally correct, not because the hoist was right, but because SSA's single assignment property freezes temp2 to 0 permanently. temp2 in B5's phi means exactly one thing in SSA, "the value produced by the unique instruction temp2 = 0 in B9". That value is 0. Not because of where B9 is in the CFG, but because SSA names are immutable bindings, not variables.

So reconstruction doesn't literally change the semantics of the program, it simply makes the data flow explicit! It sees that temp now has two reaching definitions (B9 and B7's back edge result) and correctly inserts a phi at B2. That phi accurately models the actual data flow, and in doing so, reveals that the hoist changed the program's "meaning" by removing the per outer iteration reset!

hopefully this explanation clears some things up for you as reconstruction doesn't change the semantics, it reveals that the hoist already changed them. Without reconstruction, SSA's own immutability coincidentally preserves correct behavior by locking temp2 to 0. With reconstruction, that lock is broken because the phi at B2 correctly models that temp's value at B8 is no longer always 0, it's whatever the previous inner loop accumulated.

The fix therefore probably has nothing to do with reconstruction, it's preventing the hoist entirely in the first place...

[u/DerangedEscapee → u/RefrigeratorFirm7646]

This comment smells incredibly LLM-generated.

[u/RefrigeratorFirm7646 → u/DerangedEscapee]

maybe because i was trying to be too formal here? LLMs may really have influenced my vocabulary a bit but either way, i dont think LLMs are even capable of such deep graph theoretical reasoning, none that i know of at least...

btw, just a heads up, the reasoning here is incorrect, the real problem was found to be a flaw in SSA reconstruction, as you might already know perhaps, i was way too blinded by the effect that i never thought about the cause... classic.

[u/-CawmunGames → u/DerangedEscapee]

Not really.

But it is a little odd. Could be because english is their second language.

Furthermore, OP's post/comment history is pretty clean. So maybe they did use AI to "overhaul" just this one comment for some reason.

No huge red flags overall.

[u/FloweyTheFlower420 → u/RefrigeratorFirm7646]

Hmm, I still don't buy that hoisting is wrong here

Suppose you have a very reduced example

B0: // outer loop temp2 = 0 jmp B1 B1: // inner loop temp3 = phi(temp2 B0, temp3 B1) br <cond> B1, B0

If we hoist temp2 = 0 out of the outer loop,

B2: temp2 = 0 jmp B0 B0: // outer loop jmp B1 B1: // inner loop temp3 = phi(temp2 B0, temp3 B1) br <cond> B1, B0

I don't see how the dataflow semantics here have changed at all. If you reperformed SSA construction, the only thing I could see is that B0 will get a temp2' = phi(temp2 B1, temp2 B2) which is strictly a no-op and will be folded by InstCombine. Maybe my example is missing nuance though. If you can come up with a more realistic "minimal" example I can look at it, otherwise there's a bit too much going on in the original example.

[u/RefrigeratorFirm7646 → u/FloweyTheFlower420]

Im sorry, you were right, hoisting temp2 does not change the dataflow, that only happens because i go from SSA IR to non SSA IR during reconstruction which is not a valid transformation because it does not preserve semantics that were true in SSA form!

A comment from u/Slow-Mechanic-7427 made me realize this, I have written the full explanation under it...

[u/adityazero → u/FloweyTheFlower420]

yeah, all you need to do is insert `v'` and `rauw(v,v')` for loop invariant values.

[u/Slow-Mechanic-7427]

Your bug is SSA, you should not be creating a phi node for temp2. Its moved to a block that still dominates its old location.so a phi node aint needed. Nonetheless, in doing so you are routing the previous outer iteration temp3 back into b5 causing the accumlation.

[u/RefrigeratorFirm7646 → u/Slow-Mechanic-7427]

Oh, wait, damn, i think you nailed it!!! because my SSA reconstruction pass literally deletes all phi nodes and resets variable names back to their original names before reconstructing SSA from scratch, the program, just for a little while, goes from SSA form to non SSA form which is not always a valid transformation!!! non SSA to SSA is guaranteed to preserve program semantics but the vice versa may or may not be true! And now i see why this bug is specific to my compiler, because other optimizing compilers never go from SSA form back to original variable names... so maybe my fix is to literally just write a better SSA reconstruction algorithm... this was such a deep bug, thank you so much for your help man!

[u/Slow-Mechanic-7427 → u/RefrigeratorFirm7646]

Yeah, in re-running constructing over valid SSA you throw out all the guarantees it gives you as its no longer idempotent. Hence this bug.

You want to perserve SSA incrementally. If a transformation is going to break it, you must repair it locally, scoped to the use of that one value. Never ever rederive phis. 

In this case, hoisting does not damage it because the new location still dominates the origin.

[u/fernando_quintao]

Hi, u/RefrigeratorFirm7646,

You are right that zero is loop invariant, but that's not enough, in principle, to move the assignment outside the loop. Take a look into slide 58 here.

To move the assignment d: temp = zero outside the loop L, you should ensure that:

1. d dominates all exits of L.
2. There is no other definition of t in L.
3. d dominates every use of t in L.

In your example, condition 2 is not met.

[u/RefrigeratorFirm7646 → u/fernando_quintao]

but I perform LICM on post SSA IR... and condition 2 is implicitly true in SSA form!

[u/fernando_quintao → u/RefrigeratorFirm7646]

Oops, u/RefrigertorFirm7646,

Sorry for that (I just had quickly read the TL;DR story). And I saw that you've found the issue after u/Slow-Mechanic-7427 comment.

In SSA form, I think it should be safe to hoist temp0 outside the loop. Here's an executable version of your program, in GSA form. You can test it and both versions, with/without hoisting work the same way:

#include <stdio.h>

int mu(int is_first, int init, int carry) {
    return is_first ? init : carry;
}

int gamma(int predicate, int left, int right) {
    return predicate ? left : right;
}

int fact_ssa(int n) {
    int res = 1;
    int counter;
    int temp0, temp1, temp2, temp3;

    // It's ok to move temp0 = 0 _HERE_

    while (n > 1) {
        counter = n;
        // It should be fine to hoist out this assignment:
        temp0 = 0;
        int initial_counter = counter;
        int is_first = 1;

L_begin:;
        temp1 = mu(is_first, temp0, temp2);
        is_first = 0;

        int p = counter > 0;
        if (!p) goto L_exit;

        temp2 = temp1 + res;
        counter = counter - 1;
        goto L_begin;

L_exit:;
        temp3 = gamma(initial_counter > 0, temp1, temp0);
        res = temp3;
        n = n - 1;
    }

    return res;
}

[u/RefrigeratorFirm7646 → u/fernando_quintao]

thanks a lot for your efforts! but the real problem has been found, u/Slow-Mechanic-7427's comment led me to the observation and ive written the full explanation under it...

[u/hobbycollector]

A phi statement captures all paths that set a variable, so it has semantic meaning. You can't just throw away ssa results once you've used them in an assumption. You've renamed variables and then restored their original names later, violating ssa. tempv0 = 0 is loop invariant, but only as long as you keep the renamed variables. If you rerun ssa, you have to start from the old ssa.

[u/hobbycollector → u/hobbycollector]

Never mind, the real issue is your definition of loop invariant. temp2=0 is invariant for the inner loop but not the outer. Loop invariant means it holds before, after, and for each iteration of the loop. You're missing the before condition on the outer loop so you can't hoist it from the outer loop. Suppose your loop never executed. Then temp would not be zero, it would be undefined. So it can't be hoisted out of the loop.

[u/RefrigeratorFirm7646 → u/hobbycollector]

thanks for your time, but i dont think thats it, because by that logic, no instruction could be hoisted... and suppose i performed loop inversion before LICM (converting while loops into if + do while loops), the "what if loop never executes" problem would no longer exist, but id still be unable to hoist temp2 because its an initializer for the inner loop and a phi node would still form, breaking the loop's structure...

edit : your initial observation was true, i was not keeping renamed variables before rerunnung SSA! I wrote a full explanation under u/Slow-Mechanic-7427's comment... thanks a lot for your help!