Hallo, ich brauche etwas Klarstellung zur allgemeinen Möglichkeiten der Register- bzw. Variablenoptimierung beim Kompilieren von Assemblercode. Ich weiss, Asssembler kennt keine Variablen, sondern nur Bits und Bytes. Deswegen geht es ja eigentlich darum, möglichst weniger Register im Code zu verwenden. Nehmen wir an, wir haben eine Assemblersprache, bei der es keine Sprünge, Rekursionen und es werden keine zeitkritichen Quellcodes erstellt. -> Somit steht eine Voraussetzung für eine mögliche Optimierung: Der Assemblercode wird exakt Zeile für Zeile abgearbeitet, von oben nach unten. Nun, wenn ich jetzt der Compiler wäre, dem gesagt wird "optimiere die Register im erstellten Assemblercode", dann würde ich als aller erstes alle vorkommenden Register im Code nach gelesenen und geschriebenen Registern aufteilen -> ich gehe jede Zeile des Codes durch und schau, welches Register in dieser Zeile gelesen und welches geschrieben wird und dann erstelle ich mir zwei Listen (Read Register und Write Register)mit den Namen dieser Register. Im zweiten Schritt würde ich durch den Vergleich der beiden Listen und der Nummer der Zeilen, wo die nur geschriebenen Register vorkommen, rausfinden welche Register, ab welcher Zeile ich mit neuen Werten beschreiben kann. Im dritten Schritt wuerde ich alle Register-"Kandidaten", ab den entsprechenden Zeilen, welche nur noch gelesen werden, mit den Werten der Register aus der "Write Register" Liste beschreiben und übrig gebliebene "Write Register" Namen löschen = Ergebnis weniger verwendeter Register. Ich hoffe ich liege mit meinen Ausführungen nicht arg daneben und falls ja, genau deswegen schreibe ich ja, damit ich hier aufgeklärt werde. Mit besten Grüßen, bmtil.
M. V. schrieb: > Hallo, ich brauche etwas Klarstellung zur allgemeinen Möglichkeiten der > Register- bzw. Variablenoptimierung beim Kompilieren von Assemblercode. > Ich weiss, Asssembler kennt keine Variablen, sondern nur Bits und Bytes. > Deswegen geht es ja eigentlich darum, möglichst weniger Register im Code > zu verwenden. Nehmen wir an, wir haben eine Assemblersprache, bei der es > keine Sprünge, Rekursionen und es werden keine zeitkritichen Quellcodes > erstellt. -> Somit steht eine Voraussetzung für eine mögliche > Optimierung: > > Der Assemblercode wird exakt Zeile für Zeile abgearbeitet, von oben nach > unten. > > Nun, wenn ich jetzt der Compiler wäre, dem gesagt wird "optimiere die > Register im erstellten Assemblercode", dann würde ich als aller erstes > alle vorkommenden Register im Code nach gelesenen und geschriebenen > Registern aufteilen -> ich gehe jede Zeile des Codes durch und schau, > welches Register in dieser Zeile gelesen und welches geschrieben wird > und dann erstelle ich mir zwei Listen (Read Register und Write > Register)mit den Namen dieser Register. > > Im zweiten Schritt würde ich durch den Vergleich der beiden Listen und > der Nummer der Zeilen, wo die nur geschriebenen Register vorkommen, > rausfinden welche Register, ab welcher Zeile ich mit neuen Werten > beschreiben kann. Liveness-Analysis, Datenflussanalyse, CFG (Control-Flow-Graph) > Im dritten Schritt wuerde ich alle Register-"Kandidaten", ab den > entsprechenden Zeilen, welche nur noch gelesen werden, mit den Werten > der Register aus der "Write Register" Liste beschreiben und übrig > gebliebene "Write Register" Namen löschen = Ergebnis weniger verwendeter > Register. > Ich hoffe ich liege mit meinen Ausführungen nicht arg daneben und falls > ja, genau deswegen schreibe ich ja, damit ich hier aufgeklärt werde. > > Mit besten Grüßen, bmtil. Allgemeines Stichwort wäre Registerallokator. Wenn es optimal werden soll, ist das Problem NP-vollständig (da das Problem gleich zum Graphenfärben ist). Für das speziellere Problem einen Ausdruck mit möglichst wenigen Registern zu berechnen gibt es den Sethi-Ullman-Algorithmus: https://en.wikipedia.org/wiki/Sethi%E2%80%93Ullman_algorithm
M. V. schrieb: > Der Assemblercode wird exakt Zeile für Zeile abgearbeitet, von oben nach > unten. Meist geht es nicht um die Anzahl Register, sondern um die Laufzeit. Dann ist diese Annahme heutzutage oft nicht mehr sinnvoll. Schon in-order CPUs führen ggf. mehrere Operation pro Takt durch, wodurch die Abhängigkeiten und deren zeitlicher Abstand in den Fokus rücken.
Vielen Dank für die Antworten, das hilft mir definitiv weiter. Der Grund wieso ich frage ist, ich habe zwei Assemblercode Beispiele liegen, beide Quellcodes tun ein und das selbe. Es geht um Weißlichtinterferometrie. Ein Assemblerbeispiel ist vom Compiler erstellt und nicht optmiert -> benötigt ~1500 Variablen. Selbes Programm vom Menschen geschrieben, in langer Arbeit allerdings -> ~100 Variablen. Schon krasser Unterschied wie ich finde und ich frage mich auch, ob ein Optimierer den cCompilergenerierten Code auf ähnliche Anzahl Variablen bringen kann.
M. V. schrieb: > Ein Assemblerbeispiel ist vom Compiler erstellt und nicht optmiert was meinst du mit "nicht optmiert"? keine Optimierung im Compiler eingeschaltet oder nicht nachträglich optmiert? Wenn es vorher C code war, kann man auch dort geschickt Programmieren (oder halt genau das Gegenteil)
M. V. schrieb: > Ein Assemblerbeispiel ist vom Compiler erstellt und nicht optmiert -> > benötigt ~1500 Variablen. Selbes Programm vom Menschen geschrieben, in > langer Arbeit allerdings -> ~100 Variablen. Das ist ungefähr der Unterschied zwischen dem Rindvieh auf der Weide und der fertigen Scheibe im Hamburger. ;-)
Mit "nicht optimiert" meine ich, der Compiler besitzt noch keine Optimieroption. Vorher war es ein Simulink Modell. A. K. schrieb: > Das ist ungefähr der Unterschied zwischen dem Rindvieh auf der Weide und > der fertigen Scheibe im Hamburger. ;-) Eben genau das habe ich mir auch gedacht. Jetzt brauche ich das theoretische Know-How um aus der Kuh eine Köstlichkeit zu zubereiten.
:
Bearbeitet durch User
Nächste Uni-Bibliothek, Abteilung Informatik, Regal "Compilerbau". Und überspring alles in Deutsch, die lingua franca der Branche ist Englisch.
> Und überspring alles in Deutsch, die lingua franca der Branche ist > Englisch. Das ist der übliche Unfug, der hier so von den Rentner verbreitet wird. --- Das beste Buch, das zum Compilerbau gibt, dürfte das Drachenbuch sein und dies gibt es in einer erstklassigen Übersetzung. https://www.amazon.de/Compiler-Prinzipien-Techniken-Werkzeuge-Pearson/dp/3827370973
Sodan schrieb: >> Und überspring alles in Deutsch, die lingua franca der Branche ist >> Englisch. > > Das ist der übliche Unfug, der hier so von den Rentner verbreitet wird. Naja, wie so oft in der Informatik ist die richtige Antwort: Kommt drauf an! Es gibt Buecher, z.B. Moderne Betriebsysteme (3. Auflage) von Tanenbaum, da kann ich auch nur sagen: Nimm bloss nicht die deutsche Ausgabe! Die ist so schlecht uebersetzt, dass man viele Saetze 5x lesen muss, um zu verstehen was gemeint ist. Andere Buecher, wie z.B. zu C++, Python usw. kann man ruhig deutsche Ausgaben kaufen. Auch die deutschen Ausgaben von Compilerbau (Teil 1 & 2) von '99 sind sehr gut. https://www.amazon.de/Compilerbau-Tle-Tl-1-Alfred-Aho/dp/3486252941 Solange die Uebersetzungen gut sind, spricht nichts dagegen die deutsche Ausgabe zu lesen. Fachbegriffe werden nur in den allerwenigsten Faellen eingedeutscht. Solange "Server" nicht mit "Servierer", "Client" nicht mit "Kunde/Klient", "online" und "offline" nicht mit "anschnur" und "abschnur", und "Youtube" nicht mit "DuRoehre" uebersetzt werden, ist alles okay ;)
M. V. schrieb: > Mit "nicht optimiert" meine ich, der Compiler besitzt noch keine > Optimieroption. Vorher war es ein Simulink Modell. > > A. K. schrieb: >> Das ist ungefähr der Unterschied zwischen dem Rindvieh auf der Weide und >> der fertigen Scheibe im Hamburger. ;-) > > Eben genau das habe ich mir auch gedacht. Jetzt brauche ich das > theoretische Know-How um aus der Kuh eine Köstlichkeit zu zubereiten. Für einen realen Prozessor oder was theoretisches? Im ersteren Fall: Compilerbau/Code-Optimierung ist zwar ein sehr schönes Feld, aber alles andere als einfach. Gerade das Optimieren ist alles andere als trivial. Angefangen mit brauchbarem IR (Intermediate Representation, bspw. GIMPLE beim gcc oder LLVM IR 1)), SSA, Control-/Data-Flow-Analysis, dann alle auf dem IR möglichen Optimierungen (u.a. Loop-invariant code motion, Common Subexpression Elimination, Constant Folding/Propagation, Pipelining usw.), dann alles maschinenspezifische Registerallokation, Instruction-Scheduling, Reordering), Interprocedural Optimization/Link-Time-Optimization usw. usf. Wenn einen das Thema nicht wirklich interessiert und/oder nicht viel Zeit für das Vorhaben da ist, würde ich hier maximal IR für bspw. LLVM erzeugen oder noch früher ansetzen und einfachen C-Code erzeugen und diesen einem Compiler zum Optimieren überlassen. 1) http://llvm.org/docs/LangRef.html https://gcc.gnu.org/onlinedocs/gccint/GIMPLE.html Edit: @Drachenbuch. Das ist wie mit allen Lehrbüchern. Den einen schmeckts, den anderen nicht. Engineering a Compiler oder auch Crafting a Compiler with C kann man sich ebenso ansehen oder für den Anfang https://people.inf.ethz.ch/wirth/CompilerConstruction/index.html
:
Bearbeitet durch User
M. V. schrieb: > Ein Assemblerbeispiel ist vom Compiler erstellt und nicht optmiert -> > benötigt ~1500 Variablen. Selbes Programm vom Menschen geschrieben, in > langer Arbeit allerdings -> ~100 Variablen. Ein Compiler kann nicht in Deinen Kopf schauen. Du mußt ihm als Mensch schon sagen, welches minimale Format und welchen Gültigkeitsbereich die Variablen haben sollen. Nur dann kann er sie optimieren. Gerne wird dem Compiler gesagt, Du mußt int benutzen, obwohl char ausreichen würde. Das verdoppelt schonmal den Speicherbedarf. Und gerade Anfänger schmeißen mit globalen Variablen nur so um sich. Dem Compiler sagt man damit: "Finger weg, die gelten ewig". Nur lokale Variablen darf der Compiler optimieren.
M. V. schrieb: > Mit "nicht optimiert" meine ich, der Compiler besitzt noch keine > Optimieroption. Vorher war es ein Simulink Modell. Du willst doch nicht sagen, dass die eigens einen Compiler implementieren willst?
> Du willst doch nicht sagen, dass die eigens einen Compiler > implementieren willst? Aus dem Modell wurde mit dem "Compiler" (es ist kein richtiger Compiler, nur ein Matlab Projekt) ein Assemblercode erzeugt. Das geht auch nur mit den Modellen, die mit einer dafuer vorgesehen Bibliothek erstellt wurden.
Peter D. schrieb: > Ein Compiler kann nicht in Deinen Kopf schauen. Du mußt ihm als Mensch > schon sagen, welches minimale Format und welchen Gültigkeitsbereich die > Variablen haben sollen. Nur dann kann er sie optimieren. Deswegen kann man ja in C den Scope der Variablen minimieren, und seit C99 sogar in einer for-Schleife die Schleifenvariable direkt deklarieren. > Gerne wird dem Compiler gesagt, Du mußt int benutzen, obwohl char > ausreichen würde. Das verdoppelt schonmal den Speicherbedarf. Kann aber speziell auf ARM Sinn ergeben, weil int dort schneller ist. Wirklich sauber und portabel ist das dann natürlich mit den C99-Fast-Datentypen.
>Deswegen geht es ja eigentlich darum, möglichst weniger Register im Code >zu verwenden. Was für ein Schwachsinn. Der Code soll besser werden wenn man die Ressourcen der CPU NICHT möglichst vollständig ausnutzt?
Beitrag #4854104 wurde von einem Moderator gelöscht.
Rolf schrieb im Beitrag #4854104: > Ansonsten sollte man schon mit seinen Ressourcen haushalten, man weiß ja > nicht, wozu man einzelne Register womöglich noch brauchen kann. Der Code ist bekannt. Was soll da noch kommen, wofür man Reserve vorhalten müsse? Mit den Ressourcen haushalten heisst im Fall eines Compilers, sie soweit für die Leistung sinnvoll auch vollständig zu nutzen. Ein Compiler betrachtet den Code nach jeder Änderung neu und optimiert vollständig neu. Anders kann es sich bei einem Assembler-Programmierer verhalten. Der muss vielleicht damit rechnen, dass sich der Code ändert und könnte deshalb deine Ressourcen-Schere im Kopf haben. Denn der Asm-Programmierer schreibt seinen Code nicht jedesmal neu. Genau dieser Unterschied in der Herangehensweise führt beispielsweise dazu, dass ein Asm-Programmer nur ungern ein "switch" Statement als Entscheidungsbaum implementiert. Weil der Baum bei jeder Änderung der Fälle neu aussieht. Dem Compiler ist das völlig egal.
:
Bearbeitet durch User
Nur um zu sehen, ob Du unter 'Register' etwas anderes als der Rest hier verstehst: wie viele Registrr hat Deine CPU, wie viele werden vom Programm genutzt?
M. V. schrieb: > beim Kompilieren > von Assemblercode Assemblercode wird assembliert, Hochsprachencode kompiliert.
üblicherweise ist die Anzahl der Register in Prozessoren fix. Also mehr Register als vorhanden können nicht benutzt werden und warum sollte man weniger verwenden? Ach werden Register oft vom RAM in das Register und vom Register in das RAM benutzt. Warum sollte also eine Aufteilung in Lese und Schreibe Register erfolgen? Ich denke wenn du nicht einen Compiler oder Assembler für eine Architektur entwickelst, dann brauchst du dir über darüber keine Gedanken machen.
Uff, ganz schöne Diskussion hier losgetreten, wollte ich gar nicht. >Assemblercode wird assembliert, >Hochsprachencode kompiliert. Das ist natuerlich voellig korrekt, man sollte die Fachbegriffe nicht vertauschen. >Nur um zu sehen, ob Du unter 'Register' etwas anderes als der Rest hier >verstehst: wie viele Registrr hat Deine CPU, wie viele werden vom >Programm genutzt? Ich habe keine explizite Hardware mit der ich arbeite. Ich arbeite mit Simulink Modellen, von denen aus der ASM Code erstellt wird. Für welche Hardware genau, weiss ich leider nicht. Den ASM Code soll später ein "Softcore" eines FPGAs verarbeiten glaube ich. Auch eigens Entwicklung des Fachgebiets. Der ganze "Simulink zu ASM Compiler" ist leider ein mehrere Jahre altes Brownfield Projekt in dem ich angefangen habe zu arbeiten. Und ich bin jetzt soweit, dass ich endlich in dem Projekt weit genug blicke, dass ich mit meiner Aufgabe der Variablenoptimierung (sind ja eigentlich Register) beginnen kann. Das Projekt liefert mir eben einen unoptimierten Code+Variablenliste. Mit Hilfe dieser Daten und Kenntnisse über die spezielle ASM_Sprache, die für das Projekt entwickelt wurde, habe ich in Matlab einen Textparser geschrieben, der eben die Register, die verwendet werden in Lese und Schreiberegister aufteilen kann. Beste Grüße und vielen Dank für die Anregungen.
:
Bearbeitet durch User
M. V. schrieb: > Ich habe keine explizite Hardware mit der ich arbeite. Ich arbeite mit > Simulink Modellen, von denen aus der ASM Code erstellt wird. Für welche > Hardware genau, weiss ich leider nicht. Den ASM Code soll später ein > "Softcore" eines FPGAs verarbeiten glaube ich. Auch eigens Entwicklung > des Fachgebiets. D.h. du erzeugst nur eine Art Zwischencode (wie z.B. in Java oder .net) und keinen echten Assemblercode. Assembler ist nämlich immer hochgradig spezifisch für die Plattform. Sag das doch gleich, dass das eben KEIN Assembler ist. M. V. schrieb: > Der ganze "Simulink zu ASM Compiler" ist leider ein mehrere Jahre altes > Brownfield Projekt in dem ich angefangen habe zu arbeiten. Und ich bin > jetzt soweit, dass ich endlich in dem Projekt weit genug blicke, dass > ich mit meiner Aufgabe der Variablenoptimierung (sind ja eigentlich > Register) beginnen kann. Das Projekt liefert mir eben einen > unoptimierten Code+Variablenliste. Mit Hilfe dieser Daten und Kenntnisse > über die spezielle ASM_Sprache, die für das Projekt entwickelt wurde, > habe ich in Matlab einen Textparser geschrieben, der eben die Register, > die verwendet werden in Lese und Schreiberegister aufteilen kann. Ohne Wissen über die zugrunde liegende Plattform zu optimieren kann nur scheitern. Was, wenn euer Softcore sowieso 32 oder mehr Register haben wird? Ich denke ihr solltet euch mal grundlegende Gedanken über das Projekt machen und was ich erreichen wollt. Optimierung nur der Optimierung willens macht nur Arbeit und bezweckt genau gar nichts. Man muss sich das schon sehr gut überlegen...
Dr. schrieb: > Optimierung nur der Optimierung > willens macht nur Arbeit und bezweckt genau gar nichts. Im Uni-Umfeld kriegt man damit Veröffentlichungen und damit Geld. M. V. schrieb: > Ich habe keine explizite Hardware mit der ich arbeite. Ich arbeite mit > Simulink Modellen, von denen aus der ASM Code erstellt wird. Ist das auch wirklich Assembler oder nur ein Assembler-artiger Zwischencode? Wie wird dieser Code später in die Hardware reinkommen, gibt es da noch einen Zwischenschritt? M. V. schrieb: > Den ASM Code soll später ein > "Softcore" eines FPGAs verarbeiten glaube ich. Softcores in FPGAs sind relativ langsam, insofern wird die Performance ohnehin nicht besonders toll sein. Wenn ihr definitiv auf einen Prozessor hinarbeitet (und nicht auf feste Logik), dann ist es vielleicht sinnvoll, keinen Assemblercode zu erzeugen, sondern z.B. mittelprächtigen C-Code. Ein guter C-Compiler wie gcc oder llvm kann daraus Code für deine Zielarchitektur erzeugen, der deutlich besser sein wird als das, was du zu Fuß machst. Dem gcc ist es egal, ob du 100 oder 500 Variablen hast. Wenn er nachweisen kann, dass du nie mehr als 12 gleichzeitig brauchst, dann wird er den Registerverbrauch schon passend hinoptimieren. Arc N. schrieb: > Allgemeines Stichwort wäre Registerallokator. Wenn es optimal werden > soll, ist das Problem NP-vollständig (da das Problem gleich zum > Graphenfärben ist). Wenn man die Registerallokation innerhalb der SSA-Form erledigt, dann lässt sich der Graph auch in polynomialer Zeit optimal färben. SSA wird von allen großen Compilern genutzt, aber ob sie auch den Allokator benutzen, weiß ich nicht.
S. R. schrieb: > M. V. schrieb: >> Den ASM Code soll später ein >> "Softcore" eines FPGAs verarbeiten glaube ich. > > Softcores in FPGAs sind relativ langsam, insofern wird die Performance > ohnehin nicht besonders toll sein. > > Wenn ihr definitiv auf einen Prozessor hinarbeitet (und nicht auf feste > Logik), dann ist es vielleicht sinnvoll, keinen Assemblercode zu > erzeugen, sondern z.B. mittelprächtigen C-Code. Ein guter C-Compiler wie > gcc oder llvm kann daraus Code für deine Zielarchitektur erzeugen, der > deutlich besser sein wird als das, was du zu Fuß machst. ACK. Allerdings zeigt die Erfahrung, dass selbst namhafte Hardwarehersteller bzw. deren Hardware-Designer nicht weiter denken (können) als bis zu Assembler-Code. Um eine Architektur zu bekommen, um sinnvoll einen der führenden Compiler darauf anpassen zu können, beaucht's daher fast notwendig ein Co-Design von Hardware, Simulatur und Compiler: Bereits bevor es Silizium gibt, gibt es einen Simulator, der das angestrebte Design möglichst getreu umsetzt und der einem Compilerhersteller zur Verfügung steht. Die Compilerbauer können also bereits mit der Implementation beginnen, noch bevor es Hardware gibt, und idealerweise gibt es mit Release der Hardware bereits ausgereifte Tools (Simulator, Assembler, Linker, Compiler, Debugger, Standard-Bibliotheken, Board-Support (z.B. Header für SFRs, ...)). Falls sich bestimmte Features seitens des Compilers als schlecht, hinderlich, überflüssig, fehlend, fehleranfällig o.ö erweisen, gibt es Rückmeldung an die Hardware-Jungs, die das dann berücksichtigen. > Arc N. schrieb: >> Allgemeines Stichwort wäre Registerallokator. Wenn es optimal werden >> soll, ist das Problem NP-vollständig (da das Problem gleich zum >> Graphenfärben ist). > > Wenn man die Registerallokation innerhalb der SSA-Form erledigt, dann > lässt sich der Graph auch in polynomialer Zeit optimal färben. SSA wird > von allen großen Compilern genutzt, aber ob sie auch den Allokator > benutzen, weiß ich nicht. GCC nuntzt SSA, allerdings nicht mehr zur Registerallokation — das geschieht nach SSA auf einer hardware-näheren Darstellung (RTL). Polynomiale Laufzeit ist übrigens nicht ausreichend: In GCC ist z.B. jeglicher Algorithmus tabu, der nicht mindestens linearistische Laufzeit hat. Bereits quadratische Algorithmen sind damit gestorben :-) sowohl was Laufzeit als auch was Speicherplatz angeht. Und ja, auch GCC verwendet Graphenfärbung zur Registerallokation, aber wie bei vielen anderen "harten" Problemen auch (z.B. Scheduling) besteht die Kunst darin, linearistische Algorithmen abzuleiten, die zwar keine optimale Lösung mehr garantieren, aber immer noch saugut sind. Und neben der reinen R-Zuordnung hat ein R-Allocator auch noch andere Aufgaben zu erledigen, z.B. Life-Range-Splitting: Wenn es nicht genügend Register gibt, werden einige in den Frame ausgelager, und die Frage ist dann, welche Register und zu welchem Zeitpunkt diese gesichert und restauriert werden. Und dafür muss passender Spill-Code erzeugt werden, dito wenn noch genügend Register da sind, aber nicht die passende Registerklasse. Evtl. lohnt auch Rematerialisierung, d.h. anstatt eines Spills wird ein bekannter Wert neu berechnet. Der Aufwand für solche Implementierungen wird von Unbedarften i.d.R. drastisch unterschätzt.
Hallo, wir haben uns auf die Bezeichnung "Model based assembly code generator" geeignet. Der Assembler Code, den wir verwenden ist auch Eigenentwicklung mit eigenen Spezifikationen. Auf höheren (oder unteren?) Abstraktionsebenen (auch so ein tolles Wort), quasi bei den Vorprojekten passiert schon jede Menge Optimierung. Der erzeugte Zwischencode wird von einem bereits fertigem Compiler in Binärcode übersetzt, der Binärcode kommt dann auf die Hardware. Da Graphenfärbung NP vollständig ist, ist es ja nicht notwendig, dass die Variablenreduktion optimal verlaeuft, moeglichst gut sollte sie sein. Ich glaube nicht, dass man dieses Projekt mit GCC oder ähnlichen Compilern vergleichen kann, da die Hardware Frage nicht wirklich geklärt ist, und somit wichtige "Randbedinungen" fehlen. Grüße.
Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.