Datenstruktur/Algorithmus zur Verwaltung von Lebenszeiten



  • Hallo Leute,
    ich habe gerade eine totale Gedankenblockade wie ich mein Problem effizient & elegant lösen könnte.
    Also, ich habe einen Three Address Code und möchte die Lebenszeiten von Werten bestimmen.

    Mein aktueller Algorithmus ist dass ich den Code Schritt für Schritt durchgehe und für jeden Parameter/Resultat jeder Instruktion einen Eintrag in einer Tabelle erzeuge die den Zeitpunkt der letzten und der ersten Benutzung enthält. Bzw. wenn für diesen Wert bereits ein Eintrag besteht verschiebe ich den Zeitpunkt der letzten Benutzung.
    Das funktioniert soweit auch ganz gut. Die Tabelle ist über eine Hashtable implementiert die den Wert-Handle auf seine logische Lebenszeit abbildet.

    Mein Problem ist es jetzt damit etwas anzufangen. Mir erscheinen grundlegende Fragen unnötig kompliziert.
    Zb. wie viele Lebenszeiten maximal überlappen.
    Oder wenn ich versuche Code für eine Register Maschine daraus zu generieren.

    Bei beiden Problemen fällt mir nichts Besseres ein als durchzusteppen und echt für jeden Schritt die komplette Tabelle zu überprüfen ob ein neuer Wert "geboren wird". Bei der Registerallokation kann man zwar noch ein paar Optimierungen vornehmen aber O(n²) bleibt was bei viel Code recht inakzeptabel klingt vor allem da viele Hashtable-Lookups erforderlich sind.

    Bessere Ideen?
    Danke & Grüße,
    Ethon



  • Ethon schrieb:

    ich habe gerade eine totale Gedankenblockade wie ich mein Problem effizient & elegant lösen könnte.
    Also, ich habe einen Three Address Code und möchte die Lebenszeiten von Werten bestimmen.

    Ich weiß nicht, wie es den anderen geht, aber ich kann mit dieser Problembeschreibung nichts anfangen. Gar nichts.



  • Okay, simples Beispiel:

    sin((a + b) * (a + b) / c)
    

    würde den optimierten Code

    t1 = a
    t2 = b
    t3 = t1 + t2
    t4 = t3 * t3
    t5 = c
    t6 = t4 / t5
    t7 = sin t6
    

    produzieren.

    Die Lebenszeiten wären:

    t1 : 1-3
    t2 : 2-3
    t3 : 3-4
    t4 : 4-6
    t5 : 5-6
    t6 : 6-7
    t7 : 7-7

    Eine Registermaschine würde 3 Register brauchen um diesen Ausdruck auszuwerten - angenommen Ziel- und Quellregister sind nie identisch.
    3 da bei der Auswertung von t3 und t6 jeweils 3 Werte lebendig sind.
    Dieser Wert interessiert mich unter anderem - aber auch bei sehr großen Codestücken mit Werten mit langer Lebenszeit.



  • Okay, kann sogar ein konkretes Beispiel samt Sourcecode liefern. 🙂

    Code (Fibonacci):

    a = 0
    b = 1
    while b < 1000000:
    {
        print(b)
        c = a + b
        a = b
        b = c
    }
    

    3-Address-Code dazu:

    %0	:= NOP
    %1	:= $a = 0
    %2	:= NOP
    %3	:= $b = 1
    %4	:= $b
    %5	:= NOP
    %6	:= %4 < 1000000
    %7	:= jump if %6 is false to %20
    %8	:= $print
    %9	:= $b
    %10	:= %8(%9)
    %11	:= $a
    %12	:= $b
    %13	:= %11 + %12
    %14	:= $c = %13
    %15	:= $b
    %16	:= $a = %15
    %17	:= $c
    %18	:= $b = %17
    %19	:= jump %4
    

    Lebenszeiten:

    $a : (1, 18)
    $b : (3, 18)
    $c : (14, 18)
    $print : (8, 10)
    %6 : (6, 7)
    %13 : (13, 14)
    $print is used undefined
    

    So bestimme ich derzeit die Lebenszeiten der Werte:

    struct LifetimeAnalysisResults
    {
    	Lifetime[string] namedValueLifetime;
    	Lifetime[IrHandle] tempValueLifetime;
    	string[IrHandle] aliases;
        string[] undefined;
    
    	void setStored(string name, ulong pos)
    	{
    		if(!(name in namedValueLifetime))
    			namedValueLifetime[name] = Lifetime(pos, pos);
            else
                namedValueLifetime[name].last = pos;
    	}
    
    	void setLoaded(string name, ulong pos)
    	{
    		Lifetime* lt = (name in namedValueLifetime);
    		if(!lt)
            {
                undefined ~= name;
    			namedValueLifetime[name] = Lifetime(pos, pos);
                lt = (name in namedValueLifetime);
            }
    		lt.last = pos;
    	}
    
        void setAliasCreated(IrHandle h, string name)
        {
            aliases[h] = name;
        }
    
    	void setTempCreated(IrHandle h, ulong pos)
    	{
    		assert(!(h in tempValueLifetime));
    		tempValueLifetime[h] = Lifetime(pos, pos);
    	}
    
    	void setTempUsed(IrHandle h, ulong pos)
        {
    		setLifetimeEnd(h, pos);
    	}
    
    	void setLifetimeEnd(IrHandle h, ulong last)
    	{
    		string* name = (h in aliases);
    		if(name)
            {
                assert(*name in namedValueLifetime);
    			namedValueLifetime[*name].last = last;
            }
    		else
            {
                assert(h in tempValueLifetime);
    			tempValueLifetime[h].last = last;
            }
    	}
    
        void handleJump(ulong pos, ulong jumpTo)
        {
            if(jumpTo < pos)
            {
                foreach(nval; namedValueLifetime.keys)
                {
                    Lifetime* lt = (nval in namedValueLifetime);
                    if(lt.first <= jumpTo)
                        lt.last = pos - 1;
                }
            }
        }
    
        bool isEndOfLifetime(string name, ulong pos)
        {
            Lifetime* lt = (name in namedValueLifetime);
            assert(lt);
            return 
        }
    
        void dump(File f)
        {
            foreach(nval; namedValueLifetime.keys.sort)
                f.writeln("$", nval, " : ", namedValueLifetime[nval].toString());
    
            foreach(tval; tempValueLifetime.keys.sort)
                f.writeln("%", tval, " : ", tempValueLifetime[tval].toString());
    
            foreach(nval; undefined.sort)
                f.writeln("$", nval, " is used undefined");
        }
    }
    
    void analyseLifetime(ref LifetimeAnalysisResults res, ref CodeBuffer buffer)
    {
        foreach(i, code; buffer.buffer)
        {
            switch(code.type)
            {
                case IrCode.Type.Constant:
                {
                    res.setTempCreated(i, i);
                    break;
                }
    
                case IrCode.Type.Unary:
                {
                    if(code.unary.arg.type == IrCode.Operand.Type.Handle)
                        res.setTempUsed(code.unary.arg.handle, i);
                    res.setTempCreated(i, i);
                    break;
                }
    
                case IrCode.Type.Binary:
                {
                    if(code.binary.lhs.type == IrCode.Operand.Type.Handle)
                        res.setTempUsed(code.binary.lhs.handle, i);
                    if(code.binary.rhs.type == IrCode.Operand.Type.Handle)
                        res.setTempUsed(code.binary.rhs.handle, i);    
                    res.setTempCreated(i, i);
                    break;
                }
    
                case IrCode.Type.Load:
                {
                    res.setLoaded(code.load.valueName, i);
                    res.setAliasCreated(i, code.load.valueName);
                    break;
                }
    
                case IrCode.Type.Store:
                {
                    if(code.store.arg.type == IrCode.Operand.Type.Handle)
                        res.setTempUsed(code.store.arg.handle, i); 
    
                    res.setStored(code.store.valueName, i);
                    res.setAliasCreated(i, code.store.valueName);
                    break;
                }
    
                case IrCode.Type.Call:
                {
                    if(code.call.target.type == IrCode.Operand.Type.Handle)
                        res.setTempUsed(code.call.target.handle, i);
    
                    foreach(curArg; code.call.args)
                    {
                        if(curArg.type == IrCode.Operand.Type.Handle)
                            res.setTempUsed(curArg.handle, i);
                    }
                    break;
                }
    
                case IrCode.Type.Jump:
                {
                    if(code.jump.when != IrCode.Jump.JumpWhen.Always)
                    {
                        if(code.jump.cond.type == IrCode.Operand.Type.Handle)
                            res.setTempUsed(code.jump.cond.handle, i);
                    }
                    res.handleJump(i, code.jump.target);
                    break;
                }
    
                default:
                    break;
            }
        }
    }
    


  • Ich mag mich irren, aber ist das nicht ein Problem, das von Drachenbuck&Co. erschöpfend behandelt wird?



  • Mal nur dieser kleine Teil:

    Ethon schrieb:

    Die Lebenszeiten wären:

    t1 : 1-3
    t2 : 2-3
    t3 : 3-4
    t4 : 4-6
    t5 : 5-6
    t6 : 6-7
    t7 : 7-7

    Eine Registermaschine würde 3 Register brauchen um diesen Ausdruck auszuwerten - angenommen Ziel- und Quellregister sind nie identisch.
    3 da bei der Auswertung von t3 und t6 jeweils 3 Werte lebendig sind.
    Dieser Wert interessiert mich unter anderem - aber auch bei sehr großen Codestücken mit Werten mit langer Lebenszeit.

    Kannst du da nicht einfach ein (unordered_)set nehmen?

    Du schaust einfach, zu welcher Zeit wie viele Register aktiv sind:

    1: insert t1
    2: insert t2
    3: remove t1, remove t2
    4: insert t4, remove t3
    

    Dann simulierst du das mit einem set und die maximale Anzahl Einträge ist die minimale Zahl der Register.



  • Sieht aus wie ein Färbungsproblem in Intervallgraphen.


Log in to reply