dead assignment to

Compiler Optimizations

• Address Optimization
• Alias Optimization by Address
• Alias Optimization Const Qualifier
• Alias Optimization by Type
• Array Bounds Optimization
• Bitfield Optimization
• Branch Elimination
• Loop Collapsing
• Instruction Combining
• Constant Folding
• Constant Propagation
• CSE Elimination

Dead Code Elimination

• Ineger Divide Optimization
• Expression Simplification
• Forward Store
• Loop Fusion
• Garbage Collection
• If Optimization
• Function Inlining
• Invarrant Expression Elimination
• Block Mergin
• Integer Mod Optimization
• Integer Multiply Optimization
• New Optimization
• Pointer Optimization
• Printf Optimization
• Value Range Optimization
• Register Allocation
• Strength Reduction
• String Optimization
• Tail Recursion
• Try/Catch Block Optimization
• Loop Unrolling
• Unswitching
• Volatile Optimization

Code that is unreachable or that does not affect the program (e.g. dead stores) can be eliminated.

In the example below, the value assigned to i is never used, and the dead store can be eliminated. The first assignment to global is dead, and the third assignment to global is unreachable; both can be eliminated.

Below is the code fragment after dead code elimination.

Get notified in your email when a new post is published to this blog

Optimizing C++ Code : Dead Code Elimination

August 9th, 2013 0 0

If you have arrived in the middle of this blog series, you might want instead to begin at the beginning .

This post examines the optimization called Dead-Code-Elimination, which I’ll abbreviate to DCE.  It does what it says: discards any calculations whose results are not actually used by the program.

Now, you will probably assert that your code calculates only results that are used, and never any results that are not used: only an idiot, after all, would gratuitously add useless code – calculating the first 1000 digits of pi , for example, whilst also doing something useful.  So when would the DCE optimization ever have an effect?

The reason for describing DCE so early in this series is that it could otherwise wreak havoc and confusion throughout our  exploration of other, more interesting optimizations: consider this tiny example program, held in a file called Sum.cpp :

int main() {     long long s = 0;     for (long long i = 1; i <= 1000000000; ++i) s += i; }

We are interested in how fast the loop executes, calculating the sum of the first billion integers.  (Yes, this is a spectacularly silly example, since the result has a closed formula, taught in High school.  But that’s not the point)

Build this program with the command:   CL /Od /FA Sum.cpp   and run with the command Sum .  Note that this build disables optimizations, via the /Od switch.  On my PC, it takes about 4 seconds to run.  Now try compiling optimized-for-speed, using CL /O2 /FA Sum.cpp .  On my PC, this version runs so fast there’s no perceptible delay.  Has the compiler really done such a fantastic job at optimizing our code?  The answer is no (but in a surprising way, also yes):

Let’s look first at the code it generates for the /Od case, stored into Sum.asm .  I have trimmed and annotated the text to show only the loop body:

       mov    QWORD PTR s$[rsp], 0                     ;; long long s = 0        mov    QWORD PTR i$1[rsp], 1                    ;; long long i = 1        jmp    SHORT $LN3@main    $LN2@main :        mov    rax, QWORD PTR i$1[rsp]                  ;; rax = i        inc    rax                                      ;; rax += 1        mov    QWORD PTR i$1[rsp], rax                  ;; i = rax   $LN3@main :        cmp    QWORD PTR i$1[rsp], 1000000000           ;; i <= 1000000000 ?        jg     SHORT $LN1@main                          ;; no – we’re done        mov    rax, QWORD PTR i$1[rsp]                  ;; rax = i        mov    rcx, QWORD PTR s$[rsp]                   ;; rcx = s        add    rcx, rax                                 ;; rcx += rax        mov    rax, rcx                                 ;; rax = rcx        mov    QWORD PTR s$[rsp], rax                   ;; s = rax        jmp    SHORT $LN2@main                        & nbsp; ;; loop $LN1@main:

The instructions look pretty much like you would expect.  The variable i is held on the stack at offset i$1 from the location pointed-to by the RSP register; elsewhere in the asm file, we find that i$1 = 0.  We use the RAX register to increment i .  Similarly, variable s is held on the stack (at offset s$ from the location pointed-to by the RSP register; elsewhere in the asm file, we find that s$ = 8).  The code uses RCX to calculate the running sum each time around the loop.

Notice how we load the value for i from its “home” location on the stack, every time around the loop; and write the new value back to its “home” location.  The same for the variable s .  We could describe this code as “naïve” – it’s been generated by a dumb compiler (i.e., one with optimizations disabled).  For example, it’s wasteful to keep accessing memory for every iteration of the loop, when we could have kept the values for i and s in registers throughout.

So much for the non-optimized code.  What about the code generated for the optimized case?  Let’s look at the corresponding Sum.asm for the optimized, /O2 , build.  Again, I have trimmed the file down to just the part that implements the loop body, and the answer is:

                                                       ;; there’s nothing here!

Yes – it’s empty!  There are no instructions that calculate the value of s .  

Well, that answer is clearly wrong, you might say.  But how do we know the answer is wrong?  The optimizer has reasoned that the program does not actually make use of the answer for s at any point; and so it has not bothered to include any code to calculate it.  You can’t say the answer is wrong, unless you check that answer, right?

We have just fallen victim to, been mugged in the street by, and lost our shirt to, the DCE optimization.  If you don’t observe an answer, the program (often) won’t calculate that answer. 

You might view this effect in the optimizer as analogous, in a profoundly shallow way, to a fundamental result in Quantum Physics, often paraphrased in articles on popular science as “ If a tree falls in the forest, and there’s nobody around to hear, does it make a sound?”

Well, let’s “observe” the answer in our program, by adding a printf of variable s , into our code, as follows:

#include <stdio.h> int main() {     long long s = 0;     for (long long i = 1; i <= 1000000000; ++i) s += i;     printf(“%lld “, s); } 

The /Od version of this program prints the correct answer, still taking about 4 seconds to run.  The /O2 version prints the same, correct answer, but runs much faster.   (See the optional section below for the value of “much faster” – in fact, the speedup is around 7X)

At this point, we have explained the main point of this blog post: always be very careful in analyzing compiler optimizations, and in measuring their benefit, that we are not being misled by DCE.  Here are four steps to help notice, and ward off, the unasked-for attention of DCE:

• Check that the timings have not suddenly improved by an order of magnitude
• Examine the generated code (using the /FA switch)
• If in doubt add a strategic printf
• Put the code of interest into its own .CPP file, separate from the one holding main .  This works, so long as you do not request whole-program optimization (via the /GL switch, that we’ll cover later)

However, we can wring several more interesting lessons from this tiny example.  I have marked these sections below as “Optional-1” through “Optional-4”.

Optional-1 : codegen for /o2.

Why is our /O2 version (including a printf to defeat DCE), so much faster than the /Od version?  Here is the code generated for the loop of the /O2 version, extracted from the Sum.asm file:

       xor    edx, edx        mov    eax, 1         mov    ecx, edx        mov    r8d, edx        mov    r9d, edx        npad   13 $LL3@main :        inc    r9        add    r8, 2        add    rcx, 3        add    r9, rax                           ;; r9  = 2  8 18 32 50 …        add    r8, rax                           ;; r8  = 3 10 21 36 55 …        add    rcx, rax                          ;; rcx = 4 12 24 40 60 …        add    rdx, rax                          ;; rdx = 1  6 15 28 45 …        add    rax, 4                            ;; rax = 1  5  9 13 17 …        cmp    rax, 1000000000                   ;; i <= 1000000000 ?        jle    SHORT $LL3@main                   ;; yes, so loop back

Note that the loop body contains approximately the same number of instructions as the non-optimized build, and yet it runs much faster.  That’s mostly because the instructions in this optimized loop use registers, rather than memory locations.  As we all know, accessing a register is much faster than accessing memory.  Here are approximate latencies that demonstrate how memory access can slow your program to a snail’s pace:

So, the non-optimized version is reading and writing to stack locations, which will quickly migrate into L2 (10 cycle access time) and L1 cache (4 cycle access time).  Both are slower than if all the calculation is done in registers, with access times around a single cycle.

But there’s more going on here to make the code run faster.  Notice how the /Od version increments the loop counter by 1 each time around the loop.  But the /O2 version increments the loop counter (held in register RAX) by 4 each time around the loop.  Eh?

The optimizer has unrolled the loop.  So it adds four items together on each iteration, like this:

s = (1 + 2 + 3 + 4) + (5 + 6 + 7 + 8) + (9 + 10 + 11 + 12) + (13 + . . .

By unrolling this loop, the test for loop-end is made every four iterations, rather than on every iteration – so the CPU spends more time doing useful work than forever checking whether it can stop yet!

Also, rather than accumulate the results into a single location, it has decided to use 4 separate registers, to accumulate 4 partial sums, like this:

RDX = 1 + 5 +  9 + 13 + …  =  1,  6, 15, 28 … R9  = 2 + 6 + 10 + 14 + …  =  2,  8, 18, 32 … R8  = 3 + 7 + 11 + 15 + …  =  3, 10, 21, 36 … RCX = 4 + 8 + 12 + 16 + …  =  4, 12, 24, 40 …

At the end of the loop, it adds the partial sums, in these four registers, together, to get the final answer.

(I will leave it as an exercise for the reader how the optimizer copes with a loop whose trip count is not a multiple of 4)

Optional-2 : Accurate Performance Measurements

Earlier, I said that the /O2 version of the program, without a printf inhibitor , “runs so fast there’s no perceptible delay”.  Here is a program that makes that statement more precise:

#include <stdio.h> #include <windows.h> int main() {   LARGE_INTEGER start, stop;   QueryPerformanceCounter(&start);     long long s = 0;     for (long long i = 1; i <= 1000000000; ++i) s += i;   QueryPerformanceCounter(&stop);   double diff = stop.QuadPart – start.QuadPart;   printf(“%f”, diff); }

It uses QueryPerformanceCounter to measure the elapsed time.  (This is a “sawn-off” version of a high-resolution timer described in a previous blog).  There are lots of caveats to bear in-mind when measuring performance (you might want to browse a list I wrote previously ), but they don’t matter for this particular case, as we shall see in a moment:

On my PC, the /Od version of this program prints a value for   diff of about 7 million somethings .  (The units of the answer don’t matter – just know that the number gets bigger as the program takes longer to run).  The /O2 version prints a value for diff of 0.  And the cause, as explained above, is our friend DCE.

When we add a printf to prevent DCE, the /Od version runs in about 1 million somethings – a speedup of about 7X.

Optional-3 : x64 Assembler “widening”

If we look carefully again at the assembler listings in this post, we find a few surprises in the part of the program that initializes our registers:

       xor    edx, edx                          ;; rdx = 0     (64-bit!)        mov    eax, 1                            ;; rax = i = 1 (64-bit!)        mov    ecx, edx                          ;; rcx = 0     (64-bit!)        mov    r8d, edx                          ;; r8  = 0     (64-bit!)        mov    r9d, edx                          ;; r9  = 0     (64-bit!)        npad   13    &nbs p;                           ;; multi-byte nop alignment padding $LL3@main:

Recall first that the original C++ program uses long long variables for both the loop counter and the sum.  In the VC++ compiler, these map onto 64-bit integers.  So we should expect the generated code to make use of x64’s 64-bit registers.

We already explained, in a previous post, that xor reg, reg is a compact way to zero out the contents of reg .  But our first instruction is apply x

Discussion are closed.

Securing a compiler transformation

• Published: 15 January 2018
• Volume 53 , pages 166–188, ( 2018 )

Cite this article

• Chaoqiang Deng 1 &
• Kedar S. Namjoshi 2  

407 Accesses

4 Citations

1 Altmetric

Explore all metrics

A compiler optimization may be correct and yet be insecure. This work focuses on the common optimization that removes dead (i.e., useless) store instructions from a program. This operation may introduce new information leaks, weakening security while preserving functional equivalence. This work presents a polynomial-time algorithm for securely removing dead stores. The algorithm is necessarily approximate, as it is shown that determining whether new leaks have been introduced by dead store removal is undecidable in general. The algorithm uses taint and control-flow information to determine whether a dead store may be removed without introducing a new information leak. A notion of secure refinement is used to establish the security preservation properties of other compiler transformations. The important static single assignment optimization is, however, shown to be inherently insecure.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

Securing a Compiler Transformation

Trace-Relating Compiler Correctness and Secure Compilation

Securing the SSA Transform

Abadi M (1998) Protection in programming-language translations. In: Larsen KG, Skyum S, Winskel G (eds) Automata, languages and programming, 25th international colloquium, ICALP’98, Aalborg, Denmark, July 13–17, 1998, Proceedings. Lecture notes in computer science, vol 1443. Springer, pp 868–883. https://doi.org/10.1007/BFb0055109

Almeida JB, Barbosa M, Barthe G, Dupressoir F, Emmi M (2016) Verifying constant-time implementations. In: Holz T, Savage S (eds) 25th USENIX security symposium, USENIX security 16, Austin, TX, USA, August 10–12, 2016. USENIX Association, pp 53–70. https://www.usenix.org/conference/usenixsecurity16/technical-sessions/presentation/almeida

Bell D, LaPadula L (1973) Secure computer systems: mathematical foundations, vol 1-III. Technical Report of ESD-TR-73-278, The MITRE Corporation

Ceara D, Mounier L, Potet M (2010) Taint dependency sequences: a characterization of insecure execution paths based on input-sensitive cause sequences. In: Third international conference on software testing, verification and validation, ICST 2010, Paris, France, April 7–9, 2010. Workshops Proceedings, pp 371–380. https://doi.org/10.1109/ICSTW.2010.28

de Amorim AA, Collins N, DeHon A, Demange D, Hritcu C, Pichardie D, Pierce BC, Pollack R, Tolmach A (2014) A verified information-flow architecture. In: Jagannathan S, Sewell P (eds) The 41st annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’14, San Diego, CA, USA, January 20–21, 2014. ACM, pp 165–178. https://doi.org/10.1145/2535838.2535839

Deng C, Namjoshi KS (2016) Securing a compiler transformation. In: Rival X (Ed) Static analysis: 23rd international symposium, SAS 2016, Edinburgh, UK, September 8–10, 2016, Proceedings. Lecture notes in computer science, vol 9837. Springer, pp 170–188. https://doi.org/10.1007/978-3-662-53413-7_9

Deng C, Namjoshi KS (2017) Securing the SSA transform. In: Ranzato F (Ed) Static analysis: 24th international symposium, SAS 2017, New York, NY, USA, August 30–September 1, 2017, Proceedings. Lecture notes in computer science, vol 10422. Springer, pp 88–105. https://doi.org/10.1007/978-3-319-66706-5_5

Denning DE (May 1975) Secure information flow in computer systems. Ph.D. Thesis, Purdue University

Denning DE, Denning PJ (1977) Certification of programs for secure information flow. Commun ACM 20(7):504–513. https://doi.org/10.1145/359636.359712

Article   MATH   Google Scholar  

D’Silva V, Payer M, Song DX (2015) The correctness-security gap in compiler optimization. In: 2015 IEEE symposium on security and privacy workshops, SPW 2015, San Jose, CA, USA, May 21–22, 2015. IEEE Computer Society, pp 73–87. https://doi.org/10.1109/SPW.2015.33

Fournet C, Swamy N, Chen J, Dagand P, Strub P, Livshits B (2013) Fully abstract compilation to JavaScript. In: Giacobazzi R, Cousot R (eds) The 40th annual ACM SIGPLAN-SIGACT symposium on principles of programming languages, POPL ’13, Rome, Italy, January 23–25, 2013. ACM, pp 371–384. https://doi.org/10.1145/2429069.2429114

Gondi K, Bisht P, Venkatachari P, Sistla AP, Venkatakrishnan VN (2012) SWIPE: eager erasure of sensitive data in large scale systems software. In: Bertino E, Sandhu RS (eds) Second ACM conference on data and application security and privacy, CODASPY 2012, San Antonio, TX, USA, February 7–9, 2012. ACM, pp 295–306. https://doi.org/10.1145/2133601.2133638

Howard M (2002) When scrubbing secrets in memory doesn’t work. http://archive.cert.uni-stuttgart.de/bugtraq/2002/11/msg00046.html . Also https://cwe.mitre.org/data/definitions/14.html

Namjoshi KS, Zuck LD (2013) Witnessing program transformations. In: Logozzo F, Fähndrich M (eds) Static analysis: 20th international symposium, SAS 2013, Seattle, WA, USA, June 20–22, 2013. Proceedings. Lecture notes in computer science, vol 7935. Springer, pp 304–323. https://doi.org/10.1007/978-3-642-38856-9_17

Necula G (2000) Translation validation of an optimizing compiler. In: Proceedings of the ACM SIGPLAN conference on principles of programming languages design and implementation (PLDI). pp 83–95

Papadimitriou CH (1994) Computational complexity. Addison-Wesley, Reading, MA

MATH   Google Scholar  

Patrignani M, Agten P, Strackx R, Jacobs B, Clarke D, Piessens F (2015) Secure compilation to protected module architectures. ACM Trans Program Lang Syst 37(2):6. https://doi.org/10.1145/2699503

Article   Google Scholar  

Pnueli A, Shtrichman O, Siegel M (1998) The code validation tool (CVT)—automatic verification of a compilation process. Softw Tools Technol Transf 2(2):192–201

Smith G (2015) Recent developments in quantitative information flow (invited tutorial). In: 30th Annual ACM/IEEE symposium on logic in computer science, LICS 2015, Kyoto, Japan, July 6–10, 2015. IEEE, pp 23–31. https://doi.org/10.1109/LICS.2015.13

Volpano DM, Irvine CE, Smith G (1996) A sound type system for secure flow analysis. J Comput Secur 4(2/3):167–188. https://doi.org/10.3233/JCS-1996-42-304

Yang Z, Johannesmeyer B, Olesen AT, Lerner S, Levchenko K (2017) Dead store elimination (still) considered harmful. In: Kirda E, Ristenpart T (eds) 26th USENIX security symposium, USENIX security 2017, Vancouver, BC, Canada, August 16–18, 2017. USENIX Association, pp 1025–1040. https://www.usenix.org/conference/usenixsecurity17/technical-sessions/presentation/yang

Zuck LD, Pnueli A, Goldberg B (2003) VOC: A methodology for the translation validation of optimizing compilers. J. UCS 9(3):223–247

Google Scholar  

Download references

Acknowledgements

We would like to thank Lenore Zuck, V. N. Venkatakrishnan, Sanjiva Prasad, and Michael Emmi for helpful discussions and comments on this research. We would also like to thank the anonymous referees for a careful reading of the paper and helpful comments and suggestions. This work was supported, in part, by DARPA under agreement number FA8750-12-C-0166. The U.S. Government is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of DARPA or the U.S. Government. The second author was supported by Grant CCF-1563393 from the National Science Foundation during the preparation of this paper.

Author information

Authors and affiliations.

New York University, New York, NY, USA

Chaoqiang Deng

Bell Laboratories, Nokia, Murray Hill, NJ, USA

Kedar S. Namjoshi

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Kedar S. Namjoshi .

1.1 Hardness of security checking for finite-state programs

Checking the security of a dead store elimination given as a triple ( P ,  Q ,  D ) is PSPACE -complete for finite-state programs.

Consider the complement problem of checking whether a transformation from P to Q is insecure. By definition, this is so if there exists a triple ( a ,  b ,  c ) which is leaky for Q but not for P . Determining whether ( a ,  b ,  c ) is leaky can be done in deterministic polynomial space, by simulating the program on the input pairs ( a ,  c ) and ( b ,  c ). Non-termination is detected in a standard way by adding an n -bit counter, where \(2^{n}\) is an upper bound on the size of the search space: the number n is linear in the number of program variables. A non-deterministic machine can guess the triple ( a ,  b ,  c ), then check that the triple is leaky for Q but not leaky for P . Thus, checking insecurity is in non-deterministic PSPACE , which is in PSPACE by Savitch’s theorem.

To show hardness, consider the problem of deciding whether a finite-state program with no inputs or outputs terminates, which is PSPACE -complete by a simple reduction from the IN-PLACE-ACCEPTANCE problem [ 16 ]. Given such a program R , let h be a fresh high security input variable and l a fresh low-security state variable, both Boolean, with l initialized to \( false \) . Define program P as: “ \(R ;\,l \,:=\,h;\,l \,:=\, false \) ”, and program Q as: “ \(R;\,l \,:=\,h\) ”. As the final assignment to l in P is dead, Q is a correct result of dead store elimination on P . Consider the triple \((h= true ,h= false ,\_)\) . If R terminates, then Q has distinct final values for l for the two executions arising from inputs \((h= true ,\_)\) and \((h= false ,\_)\) , while P does not, so the transformation is insecure. If R does not terminate, there are no terminating executions for Q , so Q has no leaky triples and the transformation is trivially secure. Hence, R is non-terminating if, and only if, the transformation from P to Q is secure. \(\square \)

1.2 Hardness of security checking for loop-free finite-state programs

We consider the triple ( P ,  Q ,  D ) which defines a dead store elimination, and ask whether Q is at least as secure as P . We show this is hard, even for the very simple program structure where all variables are Boolean, and assignments are limited to the basic forms \(x \,:=\,y\) or \(x \,:=\,c\) , where x ,  y are variables and c is a Boolean constant. Some of the variables will be designated as high-security, depending on context.

To simplify exposition, we will use a general assignment of the form \(x \,:=\,e\) where e is a Boolean formula. This can be turned into a simple loop-free program of size O (| e |) by introducing fresh variables for each sub-tree of e and turning Boolean operators into if-then-else constructs. (E.g., \(x \,:=\,((y\;\vee \;w) \;\wedge \;z)\) is first turned into \(t_1 \,:=\,y \;\vee \;w;\, t_2 \,:=\,z;\, x \,:=\,t_1 \;\wedge \;t_2\) , then the Boolean operators are expanded out, e.g., the first assignment becomes \(\;\mathsf {if}\;y \;\mathsf {then}\;t_1 \,:=\, true \;\mathsf {else}\;t_1 \,:=\,w \;\mathsf {fi}\;\) ).

Checking the security of a dead store elimination given as a triple ( P ,  Q ,  D ) is co- NP -complete for loop-free programs.

Consider the complement problem of checking whether a transformation from P to Q is insecure. Note that P and Q have the same set of low-security variables.

We first show that this problem is in NP . By definition, an insecurity exists if and only if there is a leaky triple ( a ,  b ,  c ) for Q which is not leaky for P . Given a triple ( a ,  b ,  c ) and a program, say P , a machine can deterministically test whether the triple is leaky for P by simulating the pair of executions from ( a ,  c ) and ( b ,  c ), keeping track of the current low-security state and the last output value for each execution. This simulation takes time polynomial in the program length, as the program is loop-free. A non-deterministic machine can guess a triple ( a ,  b ,  c ) in polynomial time (these are assignments of values to variables), then use the simulation to check first that the triple is not leaky for P and then that it is leaky for Q , and accept if both statements are true. Thus, checking insecurity is in NP.

To show NP-hardness, let \(\phi \) be a propositional formula over N variables \(x_1,\ldots ,x_N\) . Let y be a fresh Boolean variable. Let the x -variables be the low-security inputs, and let y be a high security input. Let z be a low-security variable, which starts at \( false \) . Define Q ( x ,  y ) as the program \(z := (\phi \;\wedge \;y)\) , and let P ( x ,  y ) be the program \(Q;\, z := false \) . As the final assignment in P is dead, Q is a correct outcome of dead store elimination applied to P . (Note: the programs P and Q may be turned into the simpler form by expanding out the assignment to y as illustrated above, marking all freshly introduced variables as low-security.

Suppose \(\phi \) is satisfiable. Let \(\overline{m}\) be a satisfying assignment for \(\overline{x}\) . Define the inputs \((\overline{x}=\overline{m},y= true )\) and \((\overline{x}=\overline{m},y= false )\) . In Q , the final value of z from those inputs is \( true \) or \( false \) depending on value of y , so the triple \(t = (y= true ,y= false ,\overline{x}=\overline{m})\) is leaky for Q . However, in P , the final value of z is always \( false \) , regardless of y , and t is not leaky for P . Hence, the elimination of dead store from P is insecure. If \(\phi \) is unsatisfiable then, in Q , the final value of z is always \( false \) regardless of y , so the transformation is secure. I.e., the transformation is insecure if, and only if, \(\phi \) is satisfiable, which shows NP-hardness. \(\square \)

1.3 Soundness of the taint proof system

Proposition 2.

If \(\{\mathcal {E}\}\, {S}\, \{\mathcal {F}\}\) and \(\mathcal {E'} \sqsubseteq \mathcal {E}\) and \(\mathcal {F} \sqsubseteq \mathcal {F'}\) , then \(\{\mathcal {E'}\}\, {S}\, \{\mathcal {F'}\}\) .

Consider s ,  t such that \((s, t) \models \mathcal {E'}\) and \({s}\xrightarrow []{S}{s'}\) and \({t}\xrightarrow []{S}{t'}\) .

\(\square \)

If \(\{\mathcal {E}\}\, {S}\, \{\mathcal {F}\}\) , variable x is tainted in \(\mathcal {E}\) and S does not modify x , then x is tainted in \(\mathcal {F}\) .

(Sketch) Here we prove that \(\mathcal {E}(x)\) implies \(\mathcal {F}(x)\) by induction on the structure of S . If S is an assignment, this is clearly true by the assignment rule. For a sequence \(S_1; S_2\) such that \(\{\mathcal {E}\}\, {S_1}\, \{\mathcal {G}\}\) and \(\{\mathcal {G}\}\, {S_2}\, \{\mathcal {F}\}\) , this is true by the induction hypothesis: \(\mathcal {E}(x)\) implies \(\mathcal {G}(x)\) which implies \(\mathcal {F}(x)\) . For a loop, by the inference rule, the loop invariant environment \(\mathcal {I}\) must be such that \(\mathcal {E}\sqsubseteq \mathcal {I}\) , so \(\mathcal {I}(x)\) holds. As \(\mathcal {I}\sqsubseteq \mathcal {F}\) , \(\mathcal {F}(x)\) holds. For a conditional, as \(\mathcal {E}(x)\) holds by assumption and \(\{\mathcal {E}\}\, {S_1}\, \{\mathcal {F}\}\) and \(\{\mathcal {E}\}\, {S_2}\, \{\mathcal {F}\}\) hold, by the induction hypothesis, \(\mathcal {F}(x)\) holds. \(\square \)

Consider a structured program P with a proof of \(\{\mathcal {E}\}\, {P}\, \{\mathcal {F}\}\) . For all initial states ( s ,  t ) such that \((s,t) \models \mathcal {E}\) : if \({s}\xrightarrow []{P}{s'}\) and \({t}\xrightarrow []{P}{t'}\) , then \((s',t') \models \mathcal {F}\) .

S is \(\mathsf {skip}\) or \(\mathsf {out}(e)\) :

Consider states \(s=(m, p)\) , \(t=(n, q)\) , \(s'=(m', p')\) and \(t'=(n', q')\) such that \({s}\xrightarrow []{S}{s'}\) and \({t}\xrightarrow []{S}{t'}\) hold. By the semantics of \(\mathsf {skip}\) and \(\mathsf {out}(e)\) , \(s'=s\) and \(t'=t\) . Thus, if \((s, t)\models \mathcal {E}\) , then \((s', t')\models \mathcal {E}\) .

S is an assignment \(x \,:=\,e\) :

Consider states \(s=(m, p)\) , \(t=(n, q)\) , \(s'=(m', p')\) and \(t'=(n', q')\) such that \({s}\xrightarrow []{S}{s'}\) and \({t}\xrightarrow []{S}{t'}\) hold. By the semantics of assignment, it is clear that \(p'=p[x\leftarrow p(e)]\) , \(q'=q[x\leftarrow q(e)]\) , and \(m'=n'\) denotes the program location immediately after the assignment. Assume \((s, t)\models \mathcal {E}\) , we want to prove \((s', t')\models \mathcal {F}\) , or more precisely, \(\forall v: \lnot \mathcal {F}(v) \Rightarrow p'(v)=q'(v)\) .

Consider variable y different from x . If \(\mathcal {F}(y)\) is false, so is \(\mathcal {E}(y)\) , hence \(p(y)=q(y)\) since \((s, t)\models \mathcal {E}\) . As \(p'(y)=p(y)\) and \(q'(y)=q(y)\) , we get \(p'(y)=q'(y)\) as desired.

Consider variable x . If \(\mathcal {F}(x)\) is false, so is \(\mathcal {E}(e)\) , hence only untainted variables in \(\mathcal {E}\) appear in e . As \((s, t)\models \mathcal {E}\) , those variables must have equal values in s and t , thus \(p(e)=q(e)\) . Since \(p'=p[x\leftarrow p(e)]\) , \(q'=q[x\leftarrow q(e)]\) , we know \(p'(x)=q'(x)\) .

Consider states s and t such that \({s}\xrightarrow []{S_1; S_2}{s'}\) and \({t}\xrightarrow []{S_1; S_2}{t'}\) . There must exist intermediate states \(s''\) and \(t''\) such that \({s}\xrightarrow []{S_1}{s''}\) , \({t}\xrightarrow []{S_1}{t''}\) , \({s''}\xrightarrow []{S_2}{s'}\) and \({t''}\xrightarrow []{S_2}{t'}\) . Now suppose \((s, t)\models \mathcal {E}\) , we have:

Conditional : For a statement S , we use Assign ( S ) to represent the set of variables assigned in S . The following two cases are used to infer \(\{\mathcal {E}\}\, {S}\, \{\mathcal {F}\}\) for a conditional:

Let S = \(\;\mathsf {if}\;c\;\mathsf {then}\;S_1\;\mathsf {else}\;S_2\;\mathsf {fi}\;\) , states \(s=(m, p), t=(n, q), s'=(m', p'), t'=(n', q')\) . Suppose \((s, t) \models \mathcal {E}\) , \({s}\xrightarrow []{S}{s'}\) , \({t}\xrightarrow []{S}{t'}\) .

Case A: \(\mathcal {E}(c)=\text {false}\) , hence by definition of \((s, t) \models \mathcal {E}\) , we know \(p(c) = q(c)\) . Thus, both successors \(s'\) and \(t'\) result from the same branch, say \(S_1\) . By the hypothesis that \(\{\mathcal {E}\}\, {S_1}\, \{\mathcal {F}\}\) and \((s, t) \models \mathcal {E}\) , we have \((s', t') \models \mathcal {F}\) .

Case B: \(\mathcal {E}(c)=\text {true}\) , hence \(s'\) and \(t'\) may result from different branches of S . To show that \((s', t') \models \mathcal {F'}\) , let x be a variable untainted in \(\mathcal {F'}\) . By the definition of \(\mathcal {F'}\) , there must be no assignment to x in either \(S_1\) or \(S_2\) . Hence, \(p'(x)=p(x)\) and \(q'(x)=q(x)\) .

If \(p(x)=q(x)\) , then \(p'(x)=q'(x)\) . Otherwise, consider \(p(x)\ne q(x)\) , and we show that this cannot be the case. As \((s, t) \models \mathcal {E}\) , x must be tainted in \(\mathcal {E}\) . As x is not modified in \(S_1\) and \(\{\mathcal {E}\}\, {S_1}\, \{\mathcal {F}\}\) holds, by Lemma  7 (below), x is tainted in \(\mathcal {F}\) . Since \(\mathcal {F}\sqsubseteq \mathcal {F'}\) , x is tainted in \(\mathcal {F'}\) , which is a contradiction. Hence, we show that \(p'(x)=q'(x)\) for any variable x untainted in \(\mathcal {F'}\) . Clearly, \(m'=n'\) , thus \((s', t') \models \mathcal {F'}\) .

While Loop :

Let states s ,  t be such that \((s, t) \models \mathcal {E}\) , and \(s', t'\) be the states reached from s ,  t at the end of the while loop. By \(\mathcal {E}\sqsubseteq \mathcal {I}\) , \((s, t) \models \mathcal {I}\) . We want to prove that \((s', t') \models \mathcal {I}\) , so that by \(\mathcal {I}\sqsubseteq \mathcal {F}\) , we can have \((s', t') \models \mathcal {F}\) .

Let the trace from s to \(s'\) be \(s=s_0, s_1, \ldots , s_n=s'\) where \(s_i\) are states at the start of successive loop iterations. Similarly, let the trace from t to \(t'\) be \(t=t_0, t_1, \ldots , t_m=t'\) . Without loss of generality, assume that \(n > m\) , then we can pad the t -trace with sufficiently many \(\mathsf {skip}\) actions (i.e., the same as “ \(\;\mathsf {if}\;c\;\mathsf {then}\;S\;\mathsf {else}\;\mathsf {skip}\;\mathsf {fi}\;\) ” where the evaluation of c is false) to make the two traces of the same length. The final state of padded t -trace is still \(t'\) . For the rest of proof, we assume that \(n = m\) and prove by induction on n that \((s_i, t_i) \models \mathcal {I}\) .

The induction basis \((s_0=s, t_0=t) \models \mathcal {I}\) holds. Then, assume the claim that for \(k\ge 0\) , \((s_k, t_k) \models \mathcal {I}\) . From the hypothesis “ \(\{\mathcal {I}\}\, {\;\mathsf {if}\;c\;\mathsf {then}\;S\;\mathsf {else}\;\mathsf {skip}\;\mathsf {fi}\;}\, \{\mathcal {I}\}\) ” of the inference rule, we get \((s_{k+1}, t_{k+1}) \models \mathcal {I}\) as well. Hence, \((s'=s_n, t'=t_m) \models \mathcal {I}\) holds. \(\square \)

Taint analysis for control-flow graphs

In this section, we describe how to adjust the taint proof system to apply to control-flow graphs (CFGs). We assume that a control-flow graph has a single entry node and a single exit node. A program is defined by its control flow graph, which is a graph where each node is a basic block and edges represent control flow. A basic block is a sequence of assignments to program variables.

The entry and exit nodes are special. All other nodes fall into one of three classes. The partitioning makes it easier to account for taint values and propagation.

A merge node has multiple incoming edges and a \(\phi \) function \(x \leftarrow \!\phi \!((x_1,e_1), \ldots , (x_n,e_n))\) for every variable x , which (simultaneously over all variables) assigns x the value of \(x_1\) if control is transferred through edge \(e_1\) , the value of \(x_2\) if control is transferred through edge \(e_2\) and so forth,

A basic node, which is a single assignment statement, and

A branch node, which is either an unconditional branch to the following node, or a conditional branch on condition c , through edge \(e_t\) if c is true, and through edge \(e_f\) if c is false.

The edge relations are special. The entry node has a single merge node as a successor and no incoming edge. The exit node has itself as the single successor, and behaves like a \(\mathsf {skip}\) . Every merge node has a single successor, which is a basic node. Every basic node has a single successor, which is either a basic or a branch node. Every successor of a branch node is either a merge node or the exit node.

A taint annotation for a control-flow graph is an assignment of environments to every CFG edge. An annotation is valid if the following conditions hold:

The assignment to the outgoing edge from the entry node has high-security input variables set to H ( \( true \) ) and all other variables set to L ( \( false \) ),

For a merge node with assignments \(x \leftarrow \phi ((x_1,e_1), \ldots , (x_n,e_n))\) , incoming edges annotated with \(\mathcal {E}_1,\ldots ,\mathcal {E}_n\) and outgoing edge annotated with \(\mathcal {F}\) , for all i : \(\{{\mathcal {E}_i}\} {x \leftarrow x_i} \{{F}\}\) holds. Note that here all \(\phi \) assignments are gathered into one to keep the notation simple,

For a basic node with assignment statement S , incoming edge annotated with \(\mathcal {E}\) and outgoing edge annotated with \(\mathcal {F}\) , the assertion \(\{{\mathcal {E}}\} {S} \{{\mathcal {F}}\}\) holds,

For an unconditional branch node with incoming edge annotated with \(\mathcal {E}\) and outgoing edge annotated with \(\mathcal {F}\) , \(\{{\mathcal {E}}\} {\mathsf {skip}} \{{\mathcal {F}}\}\) holds, and

For an conditional branch node \(\;\mathsf {if}\;c\;\mathsf {then}\;e_t \;\mathsf {else}\;e_f \;\mathsf {fi}\;\) , with incoming edge annotated with \(\mathcal {E}\) and outgoing edges annotated with \(\mathcal {F}_t\) and \(\mathcal {F}_f\) , respectively:

\(\{{\mathcal {E}}\} {\mathsf {skip}} \{{\mathcal {F}_t}\}\) and \(\{{\mathcal {E}}\} {\mathsf {skip}} \{{\mathcal {F}_f}\}\) hold, and

If \(\mathcal {E}(c)\) is true (i.e., c is tainted in \(\mathcal {E}\) ), then let d be the the immediate post-dominator for this branch node. Node d must be a merge node, say with incoming edges \(f_1,\ldots ,f_k\) . Let \(\mathcal {F}_1,\ldots ,\mathcal {F}_k\) be the environments assigned, respectively, to those edges. Let \(\mathsf {Assign}(n,d)\) be an over-approximation of the set of variables assigned to on all paths from the current branch node n to d . Then, for all \(x \in \mathsf {Assign}(n,d)\) , and for all i : it must be the case that \(\mathcal {F}_i(x)= true \) .

A structured program turns into a control flow graph with a special (reducible) structure. It is straightforward to check that a valid structured proof annotation turns into a valid CFG annotation for the graph obtained from the structured program.

1.1 Soundness

We have the following soundness theorem. Informally, the theorem states that if (the node from) edge f post-dominates (the node from) edge e , then computations starting from states consistent with e ’s annotation to f result in states which are consistent with f ’s annotation. It follows that terminating computations starting from states consistent with the entry edge annotation result in states consistent with the exit edge annotation. We write \({(s,e)} {\mathop {\longrightarrow }\limits ^{p}} {(s',f)}\) to indicate that there is a path (a sequence of edges \(e_0=e,e_1,\ldots ,e_k=f\) such that the target of \(e_{i}\) is the source of \(e_{i+1}\) , for all i ) from e to f , and that \(s'\) at edge f is obtained from state s at edge e by the actions along that path.

For a given CFG: let e be an edge incident on node n , and let f be an outgoing edge from node m which post-dominates n . Let \(\mathcal {E}, \mathcal {F}\) be the annotations for edges e and f , respectively. For states s ,  t such that \((s,t) \models \mathcal {E}\) and states u ,  v and paths p ,  q such that \({(s,e)} {\mathop {\longrightarrow }\limits ^{p}} {(u,f)}\) and \({(t,e)} {\mathop {\longrightarrow }\limits ^{q}} {(v,f)}\) , it is the case that \((u,v) \models \mathcal {F}\) .

The proof is by induction on the sum of the lengths of paths p and q , where the length is the number of edges on the path.

The base case is when the sum is 2. Then \(m=n\) , and f is an outgoing edge of node n . The validity conditions ensure that \(\{{\mathcal {E}}\} {S} \{{\mathcal {F}}\}\) hold, where S is the statement associated with n . It follows that \((u,v) \models \mathcal {F}\) .

Assume inductively that the claim holds when the sum is at most k , for \(k \ge 0\) . Now suppose the sum is \(k+1\) . The argument goes by cases on the type of node n .

n is a merge node, a basic node, or an unconditional branch node. Then it has a single successor node, say \(n'\) , via some edge \(e'\) . Let \(\mathcal {E'}\) be the annotation on \(e'\) . By the conditions on a valid annotation, \(\{{\mathcal {E}}\} {S} \{{\mathcal {E'}}\}\) holds, where S is the statement associated with n . Thus, for the immediate successors \(s',t'\) of s ,  t along the paths p ,  q (respectively), \((s',t') \models \mathcal {E'}\) . As \(n'\) is the immediate post-dominator of n and all post-dominators of n are linearly ordered, m is a post-dominator of \(n'\) . The suffixes \(p',q'\) of the paths p ,  q starting at \(e'\) have smaller total length. By the induction hypothesis, as \((s',t') \models \mathcal {E'}\) , it follows that \((u,v) \models \mathcal {F}\) .

n is a conditional branch node with condition c and successor edges \(e_t,e_f\) leading to successor nodes \(n_t,n_f\) . There are two cases to consider.

The branch condition is tainted, i.e., \(\mathcal {E}(c)= true \) . Let \(n'\) be the immediate post-dominator of n . This must be a merge node by the canonical structure of the CFG, with a single outgoing edge, say \(g'\) . By the constraints on valid annotation, if \(\mathcal {G}\) is the annotation on \(g'\) , then \(\mathcal {G}(x)= true \) if variable x is assigned to on a path from n to \(n'\) . Hence, if \(\mathcal {G}(x)= false \) , then x has no assignment on such a path, in particular, it has no assignment on the segments \(p'\) of p and \(q'\) of q from n to the first occurrence of \(n'\) . Let \(s',t'\) be the states after execution of \(p'\) and \(q'\) (resp.). Then, \(s'(x)=s(x)\) and \(t'(x)=t(x)\) . By the contrapositive of Lemma  7 , \(\mathcal {E}(x)= false \) . As \((s,t) \models \mathcal {E}\) , it follows that \(s(x)=t(x)\) and, therefore, \(s'(x)=t'(x)\) . This shows that \((s',t') \models \mathcal {G}\) . As the suffixes \(p'',q''\) of the paths p ,  q after \(n'\) have smaller total length, and m is a post-dominator of \(n'\) (recall that all post-dominators of n are linearly ordered and \(n'\) is the first), from the induction hypothesis, it follows that \((u,v) \models \mathcal {F}\) .

The branch condition is untainted, i.e., \(\mathcal {E}(c)= false \) . Thus, \(s(c)=t(c)\) , so the paths p ,  q have a common successor, say \(n_t\) , through edge \(e_t\) . The validity conditions imply that \(\{{\mathcal {E}}\} {\mathsf {skip}} \{{\mathcal {E}_t}\}\) hold, where \(\mathcal {E}_t\) is the annotation for edge \(e_t\) . Hence, \((s,t) \models \mathcal {E}_t\) . As m is a post-dominator of n , it is also a post-dominator of \(n_t\) . The suffixes \(p',q'\) of p ,  q from \(n_t\) have smaller total length; hence, by the induction hypothesis, \((u,v) \models \mathcal {F}\) . \(\square \)

Rights and permissions

Reprints and permissions

About this article

Deng, C., Namjoshi, K.S. Securing a compiler transformation. Form Methods Syst Des 53 , 166–188 (2018). https://doi.org/10.1007/s10703-017-0313-8

Download citation

Published : 15 January 2018

Issue Date : October 2018

DOI : https://doi.org/10.1007/s10703-017-0313-8

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Compiler correctness
• Verification
• Find a journal
• Publish with us
• Track your research

# Programming Assignment 3

A3: dead code detection, # 1 assignment objectives.

• Implement a dead code detector for Java.

Dead code elimination is a common compiler optimization in which dead code is removed from a program, and its most challenging part is the detection of dead code. In this programming assignment, you will implement a dead code detector for Java by incorporating the analyses you wrote in the previous two assignments, i.e., live variable analysis and constant propagation . In this document, we will define the scope of dead code (in this assignment) and your task is to implement a detector to recognize them.

Now, we suggest that you first setup the Tai-e project for Assignment 3 (in A3/tai-e/ of the assignment repo) by following Setup Tai-e Assignments .

# 2 Introduction to Dead Code Detection

Dead code is the part of program which is unreachable (i.e., never be executed) or is executed but whose results are never used in any other computation. Eliminating dead code does not affect the program outputs, meanwhile, it can shrink program size and improve the performance. In this assignment, we focus on two kinds of dead code, i.e., unreachable code and dead assignment .

# 2.1 Unreachable Code

Unreachable code in a program will never be executed. We consider two kinds of unreachable code, control-flow unreachable code and unreachable branch , as introduced below.

Control-flow Unreachable Code . In a method, if there exists no control-flow path to a piece of code from the entry of the method, then the code is control-flow unreachable. An example is the code following return statements . Return statements are exits of a method, so the code following them is unreachable. For example, the code at lines 4 and 5 below is control-flow unreachable:

Detection : such code can be easily detected with control-flow graph (CFG) of the method. We just need to traverse the CFG from the method entry and mark reachable statements. When the traversal finishes, the unmarked statements are control-flow unreachable.

Unreachable Branch . There are two kinds of branching statements in Java: if statement and switch statement, which could form unreachable branches.

For an if-statement, if its condition value is a constant, then one of its two branches is certainly unreachable in any executions, i.e., unreachable branch, and the code inside that branch is unreachable. For example, in the following code snippet, the condition of if-statement at line 3 is always true, so its false-branch (line 6) is an unreachable branch.

For a switch-statement, if its condition value is a constant, then case branches whose values do not match that condition may be unreachable in any execution and become unreachable branches. For example, in the following code snippet, the condition value ( x ) of switch-statement at line 3 is always 2, thus the branches “ case 1 ” and “ default ” are unreachable. Note that although branch “ case 3 ” does not match the condition value (2) either, it is still reachable as the control flow can fall through to it via branch “ case 2 ”.

Detection : to detect unreachable branches, we need to perform a constant propagation in advance, which tells us whether the condition values are constants, and then during CFG traversal, we do not enter the corresponding unreachable branches.

# 2.2 Dead Assignment

A local variable that is assigned a value but is not read by any subsequent instructions is referred to as a dead assignment, and the assigned variable is dead variable (opposite to live variable ). Dead assignments do not affect program outputs, and thus can be eliminated. For example, the code at lines 3 and 5 below are dead assignments.

Detection : to detect dead assignments, we need to perform a live variable analysis in advance. For an assignment, if its LHS variable is a dead variable (i.e., not live), then we could mark it as a dead assignment, except one case as discussed below.

open in new window . For example, expr is a method call ( x = m() ) which could have many side-effects. For this issue, we have provided an API for you to check whether the RHS expression of an assignment may have side-effects (described in Section 3.2 ). If so, you should not report it as dead code for safety, even x is not live.

# 3 Implementing a Dead Code Detector

# 3.1 tai-e classes you need to know.

To implement a dead code detector, you need to know CFG , IR , and the classes about the analysis results of live variable analysis and constant propagation (such as CPFact , DataflowResult , etc.), which you have been used in previous assignments. Below we will introduce more classes about CFG and IR that you will use in this assignment.

pascal.taie.analysis.graph.cfg.Edge

This class represents the edges in CFG (as a reminder, the nodes of CFG are Stmt ). It provides method getKind() to obtain the kind of the edges (to understand the meaning of each kind, you could read the comments in class Edge.Kind ), and you could check the edge kind like this:

In this assignment, you need to concern four kinds of edges: IF_TRUE , IF_FALSE , SWITCH_CASE , and SWITCH_DEFAULT . IF_TRUE and IF_FALSE represent the two outgoing edges from if-statement to its branches, as shown in this example:

SWITCH_CASE and SWITCH_DEFAULT represent the outgoing edges from switch-statement to its case and default branches, as shown in this example:

For SWITCH_CASE edges, you could obtain their case values (e.g., 1 and 3 in the above example) by getCaseValue() method.

pascal.taie.ir.stmt.If (subclass of Stmt )

This class represents if-statement in the program.

Note that in Tai-e’s IR, while-loop and for-loop are also converted to If statement. For example, this loop (written in Java):

will be converted to Tai-e’s IR like this:

Hence, your implementation should be able to detect dead code related to loops, e.g., if a and b are constants and a <= b , then your analysis should report that x = 233 is dead code.

pascal.taie.ir.stmt.SwitchStmt (subclass of Stmt )

This class represents switch statement in the program. You could read its source code and comments to decide how to use it.

pascal.taie.ir.stmt.AssignStmt (subclass of Stmt )

This class represents assignment (i.e., x = ...; ) in the program. You might think it as similar to class DefinitionStmt that you have seen before. The relation between these two classes is shown in this partial class hierarchy:

Actually, AssignStmt is one of two subclasses of DefinitionStmt (another one is Invoke , which represents method call/invocation in the program). It means that AssignStmt represents all assignments except the ones whose right-hand side expression is method call. AssignStmt is used in this assignment to recognize dead assignments. As mentioned in Section 2.2 , method calls could have many side-effects, thus the statements like x = m(); will not be considered as dead assignments even though x is not used later. Thus, you only need to consider AssignStmt as dead assignments.

pascal.taie.analysis.dataflow.analysis.DeadCodeDetection

This class implements dead code detection. It is incomplete, and you need to finish it as explained in Section 3.2 .

# 3.2 Your Task [Important!]

Your task is to implement one API of DeadCodeDetection :

• Set<Stmt> analyze(IR)

This method takes an IR of a method as input, and it is supposed to return a set of dead code in the IR . Your task is to recognize two kinds of dead code described in Section 2 , i.e., unreachable code and dead assignments , and add them into the resulting set.

Dead code detection depends on the analysis results of live variable analysis and constant propagation. Thus, to make dead code detection work, you need to finish LiveVariableAnalysis.java and ConstantPropagation.java . You could copy your implementation from previous assignments. Besides, you also need a complete worklist solver that supports both forward and backward data-flow analyses. You could copy your implementation of Solver.java and WorkListSolver.java from Assignment 2 , and then complete Solver.initializeBackward() and WorkListSolver.doSolveBackward() . Note that you don’t need to submit these source files in this assignment, so that even though your implementation of previous assignments is not entirely correct, it does not affect your score of this assignment.

• In this assignment, Tai-e will automatically run live variable analysis and constant propagation before dead code detection. We have provided the code in DeadCodeDetection.analyze() to obtain the analysis results of these two analyses for the given IR , so that you could directly use them. Besides, this analyze() method contains the code to obtain the CFG for the IR .
• As mentioned in Section 2.2 , the RHS expression of some assignments may have side-effects, and thus cannot be considered as dead assignments. We have provided an auxiliary method hasNoSideEffect(RValue) in DeadCodeDetection for you to check if a RHS expression may have side-effects or not.
• During the CFG traversal, you should use CFG.getOutEdgesOf() to query the successors to be visited later. This API returns the outgoing edges of given node in the CFG, so that you could use the information on the edges (introduced in Section 3.1 ) to help detect unreachable branches.
• You could use ConstantPropagation.evaluate() to evaluate the condition value of if- and switch-statements when detecting unreachable branches.

# 4 Run and Test Your Implementation

You can run the analyses as described in Set Up Tai-e Assignments . In this assignment, Tai-e performs live variable analysis, constant propagation, and dead code detection for each method of input class. To help debugging, it outputs the results of all three analyses:

The OUT facts are null and no dead code is reported as you have not finished the analyses yet. After you implement the analyses, the output should be:

open in new window .

We provide test driver pascal.taie.analysis.dataflow.analysis.DeadCodeTest for this assignment, and you could use it to test your implementation as described in Set Up Tai-e Assignments .

# 5 General Requirements

In this assignment, your only goal is correctness. Efficiency is not your concern.

DO NOT distribute the assignment package to any others.

Last but not least, DO NOT plagiarize. The work must be all your own!

# 6 Submission of Assignment

Your submission should be a zip file, which contains your implementation of

• DeadCodeDetection.java

# 7 Grading

You can refer to Grade Your Programming Assignments to use our online judge to grade your completed assignments.

The points will be allocated for correctness. We will use your submission to analyze the given test files from the src/test/resources/ directory, as well as other tests of our own, and compare your output to that of our solution.

• Engineering Mathematics
• Discrete Mathematics
• Operating System
• Computer Networks
• Digital Logic and Design
• C Programming
• Data Structures
• Theory of Computation
• Compiler Design
• Computer Org and Architecture
• Introduction to Syntax Analysis in Compiler Design
• Parsing | Set 1 (Introduction, Ambiguity and Parsers)
• Bottom-up or Shift Reduce Parsers | Set 2
• SLR, CLR and LALR Parsers | Set 3
• Shift Reduce Parser in Compiler
• Classification of Top Down Parsers
• Operator grammar and precedence parser in TOC
• Syntax Directed Translation in Compiler Design
• S - attributed and L - attributed SDTs in Syntax directed translation
• Runtime Environments in Compiler Design
• Intermediate Code Generation in Compiler Design
• Three address code in Compiler
• Compiler Design | Detection of a Loop in Three Address Code

Code Optimization in Compiler Design

• Introduction of Object Code in Compiler Design
• Data flow analysis in Compiler

The code optimization is the synthesis phase is a program transformation technique, which tries to improve the intermediate code by making it consume fewer resources (i.e. CPU, Memory) so that faster-running machine code will result. Compiler optimizing process should meet the following objectives :

• The optimization must be correct, it must not, in any way, change the meaning of the program.
• Optimization should increase the speed and performance of the program.
• The compilation time must be kept reasonable.
• The optimization process should not delay the overall compiling process.

When to Optimize? 

Optimization of the code is often performed at the end of the development stage since it reduces readability and adds code that is used to increase the performance. 

Why Optimize? 

Optimizing an algorithm is beyond the scope of the code optimization phase. So the program is optimized. And it may involve reducing the size of the code. So, optimization helps to:

• Reduce the space consumed and increases the speed of compilation.
• Manually analyzing datasets involves a lot of time. Hence, we make use of software like Tableau for data analysis. Similarly, manually performing the optimization is also tedious and is better done using a code optimizer.
• An optimized code often promotes re-usability.

Types of Code Optimization: The optimization process can be broadly classified into two types:

• Machine Independent Optimization: This code optimization phase attempts to improve the intermediate code to get a better target code as the output. The part of the intermediate code which is transformed here does not involve any CPU registers or absolute memory locations.
• Machine Dependent Optimization: Machine-dependent optimization is done after the target code has been generated and when the code is transformed according to the target machine architecture. It involves CPU registers and may have absolute memory references rather than relative references. Machine-dependent optimizers put efforts to take maximum advantage of the memory hierarchy.

Code Optimization is done in the following different ways:

1. Compile Time Evaluation:

2. variable propagation:, 3. constant propagation:  .

• If the value of a variable is a constant, then replace the variable with the constant. The variable may not always be a constant.

Example: 

4. Constant Folding: 

• Consider an expression : a = b op c and the values b and c are constants, then the value of a can be computed at compile time.

Note: Difference between Constant Propagation and Constant Folding: 

• In Constant Propagation, the variable is substituted with its assigned constant where as in Constant Folding, the variables whose values can be computed at compile time are considered and computed. 

5. Copy Propagation: 

• It is extension of constant propagation.
• After a is assigned to x, use a to replace x till a is assigned again to another variable or value or expression.
• It helps in reducing the compile time as it reduces copying.

Example : 

6. Common Sub Expression Elimination: 

• In the above example, a*b and x*b is a common sub expression.

7. Dead Code Elimination: 

•  Copy propagation often leads to making assignment statements into dead code.
• A variable is said to be dead if it is never used after its last definition.
• In order to find the dead variables, a data flow analysis should be done.

8. Unreachable Code Elimination: 

• First, Control Flow Graph should be constructed.
• The block which does not have an incoming edge is an Unreachable code block.
• After constant propagation and constant folding, the unreachable branches can be eliminated.  

9. Function Inlining: 

• Here, a function call is replaced by the body of the function itself.
• This saves a lot of time in copying all the parameters, storing the return address, etc.

10. Function Cloning: 

• Here, specialized codes for a function are created for different calling parameters.
• Example: Function Overloading

11. Induction Variable and Strength Reduction: 

• An induction variable is used in the loop for the following kind of assignment i = i + constant. It is a kind of Loop Optimization Technique. 
• Strength reduction means replacing the high strength operator with a low strength.

Examples: 

Loop Optimization Techniques: 

1. Code Motion or Frequency Reduction: 

• The evaluation frequency of expression is reduced.
• The loop invariant statements are brought out of the loop. 

2. Loop Jamming: 

• Two or more loops are combined in a single loop. It helps in reducing the compile time.

3. Loop Unrolling: 

• It helps in optimizing the execution time of the program by reducing the iterations.
• It increases the program’s speed by eliminating the loop control and test instructions.

Where to apply Optimization? 

Now that we learned the need for optimization and its two types,now let’s see where to apply these optimization.

• Source program: Optimizing the source program involves making changes to the algorithm or changing the loop structures. The user is the actor here.
• Intermediate Code: Optimizing the intermediate code involves changing the address calculations and transforming the procedure calls involved. Here compiler is the actor.
• Target Code: Optimizing the target code is done by the compiler. Usage of registers, and select and move instructions are part of the optimization involved in the target code.
• Local Optimization: Transformations are applied to small basic blocks of statements. Techniques followed are  Local Value Numbering and Tree Height Balancing.
• Regional Optimization: Transformations are applied to Extended Basic Blocks. Techniques followed are Super Local Value Numbering and Loop Unrolling.
• Global Optimization: Transformations are applied to large program segments that include functions, procedures, and loops. Techniques followed are Live Variable Analysis and Global Code Replacement.
• Interprocedural Optimization:   As the name indicates, the optimizations are applied inter procedurally. Techniques followed are Inline Substitution and Procedure Placement.

Advantages of Code Optimization:

Improved performance: Code optimization can result in code that executes faster and uses fewer resources, leading to improved performance.

Reduction in code size: Code optimization can help reduce the size of the generated code, making it easier to distribute and deploy.

Increased portability: Code optimization can result in code that is more portable across different platforms, making it easier to target a wider range of hardware and software.

Reduced power consumption: Code optimization can lead to code that consumes less power, making it more energy-efficient.

Improved maintainability: Code optimization can result in code that is easier to understand and maintain, reducing the cost of software maintenance.

Disadvantages of Code Optimization:

Increased compilation time: Code optimization can significantly increase the compilation time, which can be a significant drawback when developing large software systems.

Increased complexity: Code optimization can result in more complex code, making it harder to understand and debug.

Potential for introducing bugs: Code optimization can introduce bugs into the code if not done carefully, leading to unexpected behavior and errors.

Difficulty in assessing the effectiveness: It can be difficult to determine the effectiveness of code optimization, making it hard to justify the time and resources spent on the process.

Please Login to comment...

Similar reads, improve your coding skills with practice.

What kind of Experience do you want to share?

Navigation Menu

Search code, repositories, users, issues, pull requests..., provide feedback.

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly.

To see all available qualifiers, see our documentation .

• Notifications You must be signed in to change notification settings

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement . We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Run dead assignment elimination on global scope. #368

blickly commented Apr 29, 2014

eevee commented May 7, 2014 • edited by Dominator008 Loading

Sorry, something went wrong.

acleung commented May 7, 2014 • edited by Dominator008 Loading

nicks commented May 7, 2014

acleung commented May 9, 2014

No branches or pull requests

CA1 — Dead Code Eliminator

Project overview.

CA1 is due 2/9 at 11PM.

Compilers Assignments 1 through 5 will direct you to design and build an optimizing compiler for Cool. Each assignment will cover an intermediate step along the path to a complete optimizing compiler.

You may do this assignment in OCaml, Haskell, JavaScript, Python, or Ruby. (There are no language restrictions for Compilers Assignments.) (If you don't know what to do, OCaml and Haskell are likely the best languages for the compiler and optimizer. Python is a reasonable third choice.)

You may work in a team of two people for this assignment. You may work in a team for any or all subsequent Compilers Assignments. You do not need to keep the same teammate. The course staff are not responsible for finding you a willing teammate.

For this assignment you will write a dead code eliminator for three-address code based on live variable dataflow analysis of single methods.

• serializes and deserializes Cool Three-Address Code (TAC) format.
• identifies basic blocks in TAC to create a control flow graph (CFG).
• uses basic dataflow analysis to remove dead code.

The Specification

You must create three artifacts:

Your program must ouput a revised, valid .cl-tac file to standard output . The output should be the same as the input but with dead code removed. Your program will consist of a number of source files, all in the same programming language.

• A plain ASCII text file called readme.txt describing your design decisions and choice of test cases. See the grading rubric. A paragraph or two should suffice.
• Test cases test1.cl-tac and test2.cl-tac . These should be samples of code where it is tricky to remove dead code.

Three Address Code Example

Three-address code is a simplified representation focusing on assignments to variables and unary or binary operators.

In three address code, the expression (1+3)*7 must be broken down so that the addition and multiplication operations are each handled separately. (The exact format is described in the next section.)

As a second example, the code below reads in an integer and computes its absolute value (by checking to see if it is negative and subtracting it from zero if so):

Note the use of labels, conditional branches and unconditional jumps. You can use the cool reference compiler to evaluate .cl-tac files:

The .cl-tac File Format

Your program should serialize and deserialize file.cl-tac files representing three-address code.

A .cl-tac file is text-based and line-based. Your program must support Unix, Mac and Windows text files — regardless of where you, personally, developed your program. Note that lines can be delineated by carriage returns, new lines, or both (e.g., the regular expression [\r\n]+ may be helpful).

You can use cool --tac file.cl to produce file.cl-tac for the first method in that Cool file. Thus you can use the Cool reference compiler to produce three address code for you automatically, given Cool source code. You should do this to test your CA1 code.

Three-Address Code Deserialization

Dead code elimination.

A variable is live if it may be needed in the future. That is, an assignment to variable v at point p is live if there exists a path from p to the function exit along which v is read before it is overwritten.

For example:

On the fourth line, the assignment to d is dead because d is not subsequently used. Dead assignments can be removed. Often eliminating one piece of dead code can reveal additional dead code:

In above example, the assignment to d is not dead (yet!) but the assignment to e is dead. Once the assignment to e is eliminated, the assignment to d becomes dead and can then be eliminated. Thus, live variable analysis and dead code elimination must be repeated until nothing further changes.

You will use the live variable analysis form of data-flow analysis to determine which assignments are dead code.

Function calls with I/O side effects should never be eliminated.

Basic Blocks and Control-Flow Graphs

A basic block is a sequence of instructions with only one control-flow entry and one control-flow exit. That is, once you start executing the instructions in a basic block, you must execute all of them — you cannot jump out early or jump in half-way through.

As part of this assignment you will also implement a global dataflow analysis that operates on multiple basic blocks (that together form one entire method). A control-flow graph is a graph in which the nodes are basic blocks and the edges represent potential control flow.

Your assignment will have the following stages:

You can do basic testing as follows:

• $ cool --tac file.cl --out original $ cool --tac --opt file.cl --out ref_optimized $ my-dce original.cl-tac > my_optimized.cl-tac $ cool ref_optimized.cl-tac > optimized.output $ cool my_optimized.cl-tac > my.output $ diff optimized.output my.output $ cool --profile ref_optimized.cl-tac | grep STEPS $ cool --profile my_optimized.cl-tac | grep STEPS

Passing --opt and --tac to the reference compiler will cause the reference compiler to perform dead code elimination before emitting the .cl-tac file.

Video Guides

A number of Video Guides are provided to help you get started on this assignment on your own. The Video Guides are walkthroughs in which the instructor manually completes and narrates, in real time, aspects of this assignment.

If you are still stuck, you can post on the forum, approach the TAs, or approach the professor. The use of online instructional content outside of class weakly approximates a flipped classroom model . Click on a video guide to begin, at which point you can watch it fullscreen or via Youtube if desired.

What To Turn In For CA1

You must turn in a zip file containing these files:

Your zip file may also contain:

Submit the file to the course autograding website.

Working In Pairs

You may complete this project in a team of two. Teamwork imposes burdens of communication and coordination, but has the benefits of more thoughtful designs and cleaner programs. Team programming is also the norm in the professional world.

Students on a team are expected to participate equally in the effort and to be thoroughly familiar with all aspects of the joint work. Both members bear full responsibility for the completion of assignments. Partners turn in one solution for each programming assignment; each member receives the same grade for the assignment. If a partnership is not going well, the teaching assistants will help to negotiate new partnerships. Teams may not be dissolved in the middle of an assignment. If your partner drops the class at the last minute you are still responsible for the entire assignment.

If you are working in a team, exactly one team member should submit a CA1 zipfile. That submission should include the file team.txt , a one-line flat ASCII text file that contains the email address of your teammate. Don't include the @virgnia.edu bit. Example: If ph4u and wrw6y are working together, ph4u would submit ph4u-ca1.zip with a team.txt file that contains the word wrw6y . Then ph4u and wrw6y will both receive the same grade for that submission.

Grading Rubric

• Grading (out of 50)
• 32 points for autograder tests
• +.1 point for each passed test case (320 total)
• 10 points for valid test1.cl-tac and test2.cl-tac files
• +5 points each — high quality tests
• +2 points each — valid tests that do not stress dead code elimination or live variable analysis
• +0 points — test cases showing no effort
• 8 points for README.txt file
• +8 points — a clear, thorough description of design
• +4 points — a vague or unclear description omitting details
• +0 points — little effort or if you submit an RTF/DOC/PDF instead of a plain TXT file
• If you are in a group: -10 points if you do not submit a correct team.txt file

JavaScript disabled

You have to enable JavaScript in your browser's settings in order to use the eReader.

Or try downloading the content offline

Did you know?

Reader environment loaded

Loading publication (1.1 MB)

Large documents might take a while

• Open Source Software
• Business Software
• For Vendors
• SourceForge Podcast
• Site Documentation
• Subscribe to our Newsletter
• Support Request

Dead assignment not eliminated

The small device c compiler (sdcc), targeting 8-bit architectures.

• Mailing Lists
• Support Requests
• Feature Requests
• Experimental svn for mirroring experiments
• Create Ticket
• Closed Tickets
• Open Non-PIC
• Open Tickets
• Formatting Help

#2012 Dead assignment not eliminated

From the muldiv regression test, muldiv_storage_static_type_char_attr_none asm code for c code line 89:

; genAssign mov #0xCE,*_testDiv_sloc0_1_0 ; genAssign mov #0xD1,*_testDiv_sloc0_1_0

(this is from hc08, on osome ther ports, such as z80, the issue is masked by the peephole optimizer) I wonder why dead code elimination doesn't kill the first assignment.

• Category : --> redundancy elimination

• status : open --> pending-out-of-date
• assigned_to : Philipp Klaus Krause
• Category : redundancy elimination --> other

I cannot reproduce this in current SDCC [r10516] . It probably got fixed long ago.

• status : pending-out-of-date --> closed-out-of-date

Log in to post a comment.

• Skip to main content
• Keyboard shortcuts for audio player

The Kamala Harris coconut tree meme, explained as best we can

Lexie Schapitl

Rachel Treisman

Vice President Kamala Harris speaks to members of the Alpha Kappa Alpha Sorority at the Kay Bailey Hutchison Convention Center on July 10 in Dallas. Brandon Bell/Getty Images hide caption

For more on Biden's decision and the now open 2024 race, head to the NPR Network's live updates page .

In the weeks before President Biden announced he would not be seeking reelection , some Democrats online rallied behind Vice President Kamala Harris to become the party’s new nominee. And their symbol became the coconut tree.

Not long after Biden announced on Sunday he was dropping out of the race, Colorado Gov. Jared Polis tweeted out just three emojis : a coconut, a palm tree and an American flag. EMILYs LIST, the PAC focused on electing Democratic women, explicitly endorsed Harris in a tweet and, in a more subtle show of support, also added the tree and the coconut to its username. And Democratic Sen. Brian Schatz of Hawaii posted a picture of himself climbing up a coconut tree , adding, "Madam Vice President, we are ready to help."

🥥 🌴 🇺🇸 — Jared Polis (@jaredpolis) July 21, 2024

So how did the coconut tree emerge as the emblem of Harris' most devoted, or at least most-online followers? It's a story more than a year in the making.

Why are we even talking about coconut trees?

The “coconut tree” meme originates from a May 2023 speech Harris gave at a White House event for advancing opportunities for Hispanic Americans.

At one point near the end of her remarks, Harris talked about how the initiative's work would be focused on young people, but it should also take into account the needs of their families, teachers and communities, "because none of us just live in a silo."

We’re proud to endorse @kamalaharris as the next president of the United States because we know she is a qualified accomplished leader. She is the only candidate positioned to win against Trump in November, and the best voice to define the stakes in this election! #allinforkamala pic.twitter.com/CmdgImMaDz — EMILYs List 🥥🌴 (@emilyslist) July 21, 2024

"Everything is in context," Harris said, before launching into the now-famous anecdote.

"My mother ... would give us a hard time sometimes, and she would say to us, 'I don’t know what’s wrong with you young people. You think you just fell out of a coconut tree?' " Harris said with a laugh. "You exist in the context of all in which you live and what came before you."

The moment was first meme’d in earnest in February of this year, when for a period of time, one could not open X, formerly known as Twitter, without seeing clips of or oblique references to those remarks.

this video is literally like medicine to me. i watch it once every week or two and every time i do i get an enduring hit of light euphoria for the next 45 minutes pic.twitter.com/eIF6Rwiir0 — charlie squire (@evil_female) February 9, 2024

But the meme took on new life this summer , after President Biden’s disastrous debate performance fueled speculation that he might step aside as the Democratic nominee. Harris’ supporters, also known as the KHive, were waiting in the wings.

Since then, the moment has been remixed into Charli XCX’s “ Von Dutch ” and Britney Spears’ " Gimme More ." Democratic operatives have spoken of being “ coconut-pilled .” The meme flourished into 2028 debate fan fiction . Google searches for "coconut tree" started climbing in the U.S. in early July.

Like all of us, the coconut tree moment exists in the context of all in which it lives and what came before it. Which is to say, it’s part of a larger set of memes surrounding Kamala Harris’ political persona. Harris has been spawning memes longer than she’s been vice president. We Did It, Joe , is likely the most well-known. But her laugh , her bus , her dance moves and her love of Venn diagrams have all become social media fodder.

We did it, @JoeBiden . pic.twitter.com/oCgeylsjB4 — Kamala Harris (@KamalaHarris) November 7, 2020

So why did the coconut tree break through?

It's impossible to say why any particular meme — political or otherwise — catches fire over another. But part of Harris’ persona as portrayed on the internet is just that she   brings an energy that’s in stark contrast to President Biden and former President Donald Trump.

“We want something to laugh at and laugh with. And that's what Kamala does. And I think the coconut tree clip is a perfect example of that,” said Rebecca Jennings, a senior correspondent at Vox covering internet culture. 

Put another way, Harris — even being 59 and the incumbent vice president —represented something new in a campaign defined by old. And that stoked some enthusiasm among voters who were very unenthused.

“There's a sense of, like, nihilism that's like – OK, we have to do this again , and we have to do Trump and Biden again ,” Jennings said. “And so when you see clips of Kamala, it's like, well, at least that's fun to watch. At least it's, you know, not the same thing we've been seeing on screens for 10 years. It's a break in the just the drudgery of what what everyone thought this election was going to be.”

Young Democrats — among the most dissatisfied with Biden as a candidate, and the most online — also helped fuel the movement. As Washington Post internet culture reporter Taylor Lorenz wrote : "Harris’s new online prominence could help give the Democratic Party new prominence with young people — including major content creators — who are hesitant to vote for Biden again due to his climate policies, support of Israel’s war in Gaza, mishandling of the ongoing pandemic, and signing a bill that could ban TikTok."

One man's gaffe is another man's meme

From the coconut trees to the Venn diagrams, the Harris memes embrace what detractors might consider a gaffe. Trump, for instance, has dubbed Harris " laughing Kamala ," saying the laugh makes her seem "crazy."

Take another example, which grew out of one of Harris' go-to lines dating back to her 2020 presidential run: “I can imagine what can be, unburdened by what has been.”

The RNC compiled a supercut of Harris being "unburdened" and shared it on social media, arguing that it shows she is “unoriginal, annoying, and highly incompetent.” But the attacks aren’t sticking, as her supporters have taken ownership of the line and the laughter.

Jennings said it’s reminiscent of the critiques hurled at Trump throughout his political career, only to be welcomed by his base.

“People like the fact that he was saying offensive things,” Jennings said. "And I think it's strange for Republicans to kind of now be on the other end of that – which is making all these, you know, memes and videos of Kamala being goofy and quirky and the left being like, “Hell, yeah, brother.”

• election 2024
• Kamala Harris
• internet memes

Olympic fencer reveals she was 7 months pregnant while competing

An Egyptian Olympian has revealed she competed at the 2024 Olympics in Paris while seven months pregnant.

NOTE: The video is from a previous report.

Nada Hafez, competing in her third Olympics, shared the news on Instagram Monday, captioning two photos of herself competing with the words, "7 MONTHS PREGNANT OLYMPIAN!"

"What appears to you as two players on the podium, they were actually three! It was me, my competitor, & my yet-to-come to our world, little baby!," Hafez wrote, later adding, "This specific Olympics was different; Three times *Olympian* but this time carrying a little Olympian one!"

Hafez reached the round of 16 by defeating American Elizabeth Tartakovsky in women's saber Monday, before falling to Jeon Hayoung of South Korea.

Hafez shared her pregnancy news publicly following her loss, writing in her Instagram post, "My baby & I had our fair share of challenges, be it both physical & emotional."

"The rollercoaster of pregnancy is tough on its own, but having to fight to keep the balance of life & sports was nothing short of strenuous, however worth it," she continued. "I'm writing this post to say that pride fills my being for securing my place in the round of 16!"

Hafez also thanked her husband, whom she wed in 2023, and her family for sharing their "trust" with her.

In addition to the Paris Olympics, Hafez also competed in the 2021 Olympics in Tokyo and 2016 Olympics in Rio de Janeiro.

The Paris Olympics is perhaps the most family friendly Olympics in history thanks to a nursery that gives athlete parents a space to spend time with their children during the Games.

Paris organizers and the International Olympic Committee say their Olympic Village nursery is a first for an Olympic Games, according to The Associated Press.

Related Topics

• PREGNANT WOMAN
• U.S. & WORLD

Top Stories

VP Harris to give eulogy at service for Rep. Sheila Jackson Lee | LIVE

• 16 minutes ago

Dad killed in front of family in Fort Bend Co. home invasion: Deputies

Russia frees Evan Gershkovich, Paul Whelan in prisoner swap | LIVE

• 7 minutes ago

15-year-old allegedly attacked neighbor before stabbing her: HCSO

Neighbors say home leaning at work site after Beryl is 'an eyesore'

13 Investigates tries to confront woman accused of surrogacy scam

Less Saharan haze expected Thursday, rain chances return this weekend

• 36 minutes ago

Carrie Underwood announced as new 'American Idol' judge

• 3 hours ago

• WEATHER ALERT Heat Advisory Full Story
• ABC7 New York 24/7 Eyewitness News Stream Watch Now
• THE LOOP | NYC Weather and Traffic Cams Watch Now
• WATCH LIVE: Breaking news and other events from ABC Watch Now

Man accused of damaging Secret Service vehicles guarding VP Harris's stepdaughter in New York

The Secret Service said that at no point was Ella Emhoff in danger

NEW YORK -- A Manhattan software developer was arrested and charged Tuesday with damaging the license plate covers on two SUVs belonging to a Secret Service detail assigned to Vice President Kamala Harris' stepdaughter.

The man, Harry Heymann, appeared to be a supporter of a small group of citizen activists who call attention to - and sometimes personally modify - the obstructed license plates often used by motorists to evade tolls and traffic enforcement in New York.

Heymann, 45, approached the unmarked vehicles outside a Tribeca restaurant, then broke off their license plate covers on the back, according to a criminal complaint.

The vehicles belonged to Secret Service agents assigned to protect the vice president's stepdaughter, Ella Emhoff, as she ate lunch at Bubby's, a nearby restaurant. Video obtained by TMZ showed Emhoff being ushered into a black SUV and a man being led away in handcuffs.

"At no point was any protectee in danger as a result of this incident," said James Byrne, a spokesperson for the Secret Service.

Heymann was charged with obstructing governmental administration and criminal mischief. He did not respond to a voicemail and his attorney declined to comment.

Drivers in New York often use illegal plate covers to avoid tolling systems and traffic cameras that rely on automated license plate readers.

In recent years, a small group of citizen activists have taken countermeasures to stop drivers from obscuring their license plates. Gersh Kuntzman, the editor of news site Streetsblog NYC, popularized the efforts in 2022 with a series of videos - and a recent Daily Show appearance - showing him personally "un-defacing" license plates.

Kuntzman and his followers have used markers to redraw plate numbers that have been scraped away, removed tape and stickers, fixed bent plates or unscrewed coverings that render plates unreadable. Their repair efforts often focus on the private vehicles of law enforcement officers and court system personnel parked near police precincts and courthouses.

An X profile associated with Heymann showed dozens of posts about obscured license plates and illegally parked police vehicles in Manhattan.

"I do feel a certain amount of responsibility here," Kuntzman told The Associated Press Wednesday.

A spokesperson for the Secret Service didn't respond to a question about why the two vehicles featured license plate covers.

"Like this gentleman who may or may not have broken the law, I have been outraged by the way in which public officials, including those whose job it is to enforce the law, have willfully broken the law and made our roads less safe," Kuntzman added.

He continued: "As members of the public, we do have a responsibility to play a role in keeping the roadways safe. If that means cleaning up a piece of state property that is required by law to be readable, I'm OK with that. That said, I have never messed with the Secret Service."

* Get Eyewitness News Delivered

* More New York City news

* Send us a news tip

* Download the abc7NY app for breaking news alerts

* Follow us on YouTube

Submit a tip or story idea to Eyewitness News

Have a breaking news tip or an idea for a story we should cover? Send it to Eyewitness News using the form below. If attaching a video or photo, terms of use apply.

Related Topics

• NEW YORK CITY
• U.S. & WORLD
• KAMALA HARRIS
• SECRET SERVICE

Top Stories

Russia frees Evan Gershkovich, Paul Whelan in prisoner swap | LIVE

• 7 minutes ago

Suspected drunk driver in LI nail salon crash charged with murder

• 2 hours ago

Toddler falls more than 10 feet down into sump pump drain

Carrie Underwood announced as new 'American Idol' judge

• 3 hours ago

AccuWeather: Hotter, spot PM storms

• 36 minutes ago

Schools of dead fish, swarming birds causing a stink in South Jersey

2 men slashed in separate incidents on the subway in the Bronx, Queens

• 13 minutes ago

Steam leak spews asbestos, impacts traffic on Upper East Side

Advertisement

Supported by

Gunman at Trump Rally Was Often a Step Ahead of the Secret Service

Text messages, obtained exclusively by The Times, indicate that some law enforcement officers were aware of Thomas Crooks earlier than previously known. And he was aware of them.

• Share full article

By Haley Willis Aric Toler David A. Fahrenthold and Adam Goldman

The reporters analyzed video clips, photos and law enforcement documents to supplement key interviews for this article.

Nearly 100 minutes before former President Donald J. Trump took the stage in Butler, Pa., a local countersniper who was part of the broader security detail let his colleagues know his shift was ending.

“Guys I am out. Be safe,” he texted to a group of colleagues at 4:19 p.m. on July 13. He exited the second floor of a warehouse that overlooked the campaign rally site, leaving two other countersnipers behind.

Outside, the officer noticed a young man with long stringy hair sitting on a picnic table near the warehouse. So at 4:26 p.m., he texted his colleagues about the man, who was outside the fenced area of the Butler Fair Show grounds where Mr. Trump was to appear. He said that the person would have seen him come out with his rifle and “knows you guys are up there.”

The countersniper who sent the texts confirmed to The New York Times that the individual he saw was later identified as the gunman.

By 5:10 p.m., the young man was no longer on the picnic table. He was right below the countersnipers, who were upstairs in a warehouse owned by AGR International. One of the countersnipers took pictures of him, according to a law enforcement after-action report, which along with the texts from the Beaver County Emergency Services Unit was provided to The Times by the office of Senator Charles E. Grassley, Republican of Iowa. The text messages were independently verified by The Times.

International

position of

local snipers

photographed

Gunman first

first spotted at

picnic table

We are having trouble retrieving the article content.

Please enable JavaScript in your browser settings.

Thank you for your patience while we verify access. If you are in Reader mode please exit and  log into  your Times account, or  subscribe  for all of The Times.

Thank you for your patience while we verify access.

Already a subscriber?  Log in .

Want all of The Times?  Subscribe .

LIVE: Simone Biles and Suni Lee face off in individual all-around finals

Boxers previously barred from women's events will fight in Paris Olympics

Two boxers who were disqualified from competing with women at a global event last year have been permitted to fight in the Paris Olympics, the International Olympic Committee confirmed.

Imane Khelif of Algeria and Lin Yu‑ting of Taiwan failed to meet gender eligibility tests at the Women’s World Boxing Championships in New Delhi last year, prompting their disqualifications. But they have been cleared to compete in the women’s 66-kilogram and women’s 57-kilogram matches in Paris this week, the IOC confirmed in an email Tuesday.

 At the time of their disqualifications, the president of the International Boxing Association, which governs the World Boxing Championships, alleged that the boxers’ chromosome tests came back as XY (women typically have two X chromosomes, while men typically have an X and a Y chromosome).

“Based on DNA tests, we identified a number of athletes who tried to trick their colleagues into posing as women,” the association’s president, Umar Kremlev, told Russia’s Tass news agency at the time. “According to the results of the tests, it was proved that they have XY chromosomes. Such athletes were excluded from competition.”

Khelif and Lin have both always competed as women, and there’s no indication that either identifies as transgender or intersex, the latter referring to those born with sex characteristics that don’t fit strictly into the male-female gender binary.

Following her disqualification last year, Khelif told Algeria’s Ennahar TV that some “did not want Algeria to win a gold medal.” 

“This is a conspiracy and a big conspiracy, and we will not be silent about it,” she said. 

Lin does not appear to have commented publicly on her disqualification.

Related stories:

• A record 193 LGBTQ athletes to compete in Paris Olympics
• Grindr disables location services in Olympic Village to protect LGBTQ athletes
• Olympic opening ceremony drag performance resembling Last Supper rankles conservatives

In an email Tuesday, the IOC said that “all athletes participating in the boxing tournament of the Olympic Games Paris 2024 comply with the competition’s eligibility and entry regulations, as well as all applicable medical regulations.”

The IOC updated its rules regarding athletes’ gender eligibility, including its transgender participation guidelines,  in 2021 to defer to each sport’s governing body. The IOC no longer recognizes the IBA as the governing body over Olympic boxing, and instead refers to the Paris 2024 Boxing Unit — an ad-hoc unit developed by the IOC — for its eligibility standards.

Critics in the United States, where the issue of whether trans women should be permitted to compete in women’s sports has been hotly debated in recent years, condemned the inclusion of Khelif and Lin in this week’s competition. Some questioned whether their participation was fair to other female competitors , while others directed incendiary language toward the boxers.

Khelif is scheduled to compete against Italy’s Angela Carini on Thursday, and Lin is scheduled to fight against Uzbekistan’s Sitora Turdibekova on Friday.

For more from NBC Out, sign up for our weekly newsletter.

Matt Lavietes is a reporter for NBC Out.

TS EAMCET 2024: Round 2 Seat Allotment Self Reporting Window Ends Tomorrow, Check Details

Published By : Suramya Sunilraj

Trending Desk

Last Updated: August 01, 2024, 09:00 IST

Telangana, India

The TS EAMCET 2024 Round 3 Counselling will commence from August 8 (Representational/ PTI Photo)

Candidates who are assigned seats in Round 2 but do not report to the allotted college will not be eligible to exercise options in the final phase of counselling

The Telangana State Council of Higher Education (TSCHE) declared the Round 2 seat allotment result for the Telangana State Engineering, Agriculture and Medical Common Entrance Test (TS EAMCET) 2024. Candidates who have been assigned a seat must pay tuition fees and self-report to the assigned institute by tomorrow, August 2, 2024. In the Round 2 counselling process, candidates are required to physically report to their respective colleges.

Students who registered for the counselling process can check the TS EAMCET 2024 seat allotment result via the official website at tgeapcet.nic.in.  To access the TS EAMCET 2024 Round 2 seat allotment result, candidates must enter their login information, which includes their registration number and date of birth.

TS EAMCET 2024 Round 2 Seat Allotment Result: Steps To Check

Step 1: Go to the official website at tgeapcet.nic.in

Step 2: On the homepage, look for and click on the ‘TS EAMCET 2024 seat allotment result link.

Step 3: As a new window opens, enter the required credentials such as registration number, hall ticket number and date of birth. Then click on submit.

Step 4: The TS EAMCET 2024 seat allotment result will appear on the screen.

Step 5: Check and download the result.

In Round 2 of TS EAMCET counselling, candidates must report physically to their designated college. In addition, candidates must submit a set of photocopies of their certificates as well as the original transfer certificate (TC) to the designated college.

TS EAMCET Counselling 2024: List of Documents to Carry

– Class 6 to Class 12 pass certificate

– TS EAMCET 2024 Rank Card and Admit Card

– Candidate’s Aadhaar Card

– Caste Certificate (if applicable)

– Transfer Certificate (TC) from the school last attended

– In the case of non-local candidates, domicile credentials are required if their parents have lived in Telangana for more than ten years.

– Certificate for students requesting reservation under PwD/Children of Armed Personnel (CAP), NCC/Sports/Minority Certificate

– Residential Certificate for candidates who have not had any institutionalised education.

Candidates who are assigned seats in Round 2 but do not report to the allotted college will not be eligible to exercise options in the final phase of counselling. Meanwhile, the TS EAMCET 2024 Round 3 Counselling will begin on August 8.

• college admissions

• Stack Overflow for Teams Where developers & technologists share private knowledge with coworkers
• Advertising & Talent Reach devs & technologists worldwide about your product, service or employer brand
• OverflowAI GenAI features for Teams
• OverflowAPI Train & fine-tune LLMs
• Labs The future of collective knowledge sharing
• About the company Visit the blog

Collectives™ on Stack Overflow

Find centralized, trusted content and collaborate around the technologies you use most.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

Get early access and see previews of new features.

how to deal with bug "dead store to local variable" in java?

I wrote a simple test code. It is a circle. I suppose most people can image what is a circle class, so I will not paste it.

In the test code, I try to test the circle constructor with invalid point, and assume to throw an exception. But a bug occures. I check online, but still do not know how to solve the problem. Is there any one can help me? Thanks

code information, bug is in the last sentence of following code

Bug: Dead store to testCircle in CircleTest.testIllegalCenter()

This instruction assigns a value to a local variable, but the value is not read or used in any subsequent instruction. Often, this indicates an error, because the value computed is never used.

Note that Sun's javac compiler often generates dead stores for final local variables. Because FindBugs is a bytecode-based tool, there is no easy way to eliminate these false positives.

• My guess is that since test Circle is never used the compiler doesn't even compile the statement, and the constructor is never called –  Thayne Commented Apr 11, 2014 at 5:42
• I would assert it against null –  Karthik Kalyanasundaram Commented Apr 11, 2014 at 5:42
• 1 (offtopic)Is it really useful to run findbug against testcode? –  Jayan Commented Apr 11, 2014 at 5:46
• 3 Why would you bother assigning the Circle to a variable? Since you are just testing the constructor, you can just write new Circle(VALID_RADIUS, INVALID_POINT, VALID_COLOR); without the assignment. Then you won't get this error. –  Dawood ibn Kareem Commented Apr 11, 2014 at 5:47
• If you are testing this class, how you know without printing it out that the output will be correct? Findbug is doing its work perfectly by pointing this out. Please add a statement after that line to check if at least one of the field is populated with what you expect ie. as said by @Karthik Kalyanasundaram assert(testCircle.radius) –  bgth Commented Apr 11, 2014 at 5:49

Just remove the variable and call the constructor like this:

Your Answer

Reminder: Answers generated by artificial intelligence tools are not allowed on Stack Overflow. Learn more

Sign up or log in

Post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged java debugging findbugs or ask your own question .

• Featured on Meta
• Announcing a change to the data-dump process
• We've made changes to our Terms of Service & Privacy Policy - July 2024

Hot Network Questions

• Did the BBC ask for extra line spacing?
• An SF story where an orangutan writes a book that is published
• Is the phrase "Amazon is having best prices" grammatically correct?
• NDSolve gets the wrong answer! How get NDSolve to correctly solve this "stiff" equation?
• How to limit the number of files printed by ls and print them in columns like ls prints normally?
• Had there ever been a self-ejecting FDR/CDR?
• Why are there no 12V/5A USB PD chargers/batteries?
• Is it possible to use "sshd_config" to prevent root login only after a user has logged in via ssh?
• "Man cannot live by bread alone." — Is there any logical explanation why this idiom doesn't have an article before "man"?
• Child's teddies "being mean" after dark
• Are there non-religious variants of moral realism that defend the existence of objectively evil thoughts, intentions, and desires?
• Python Regex to match the FIRST repetition of a digit
• Does the throttling profile data for any STS missions exist?
• Distribution after Combining Two Sets of Normal Distribution Samples
• What would a planet need to have a sustained blood-based water cycle?
• Good publisher versus self publishing
• Washed my passport by mistake, can that cause a problem?
• Does GDPR's "Legitimate Interest" allow spam?
• Check if \tikZ \pic is defined or not
• What is the translation of "nosebleed section" in French?
• What is the best way to close this small gap in the tile?
• Semisimplicity for representations of a compact group
• Entire grant budget is just 1 person's salary
• is there any way to add amps to a vintage battery charger using an additional transformer?

• LIVE DISCOURSE
• BLOG / OPINION
• SUBMIT PRESS RELEASE
• Advertisement
• Knowledge Partnership
• Media Partnership
• Law & Governance

Policeman in Maharashtra Found Dead in Apparent Suicide

A policeman named ajay giri, assigned to the security detail of bjp mla rekha khedekar in maharashtra’s buldhana district, reportedly committed suicide using his service revolver. he was found dead in his government quarters. an investigation has been initiated by the local police..

A policeman assigned to secure a Maharashtra-based MLA reportedly took his own life on Wednesday, according to local police.

The officer, identified as Ajay Giri, was part of the Buldhana district police and served as the security guard for BJP MLA Rekha Khedekar from Chikhli.

The 38-year-old allegedly shot himself with his service revolver at his Buldhana residence. Despite being rushed to the district hospital, he was declared dead on arrival. The motive remains unclear, and an investigation is underway.

(With inputs from agencies.)

• READ MORE ON:
• Maharashtra
• Rekha Khedekar
• service revolver
• investigation

Investigation Launched into Trump Rally Security Breach

U.s. commerce department targets chinese-connected vehicles in national security crackdown, intense fire exchange between security forces and terrorists in doda forest, ifad and senegal launch €27.8 million programme to boost food security and smallholder farmers’ resilience, enhanced security in delhi and other cities ahead of muharram processions.

Tragedy Strikes Pilgrims: Electrocution Incident in Jharkhand

Adidas Expects Soccer Trend to Continue till 2025 as Sales Surge

Nasdaq Futures Surge Amid Bullish Chip Forecast as Microsoft Falters

The Hidden Mental Load: Unequal Cognitive Housework and Its Toll on Women's ...

Latest news, historic east-west prisoner exchange completes in ankara, paris olympics propel nbcuniversal to record ad sales and viewer engagement, suryakumar yadav returns to mumbai after triumphant t20i series win against sri lanka, global reactions to east-west prisoner swap highlight tensions.

OPINION / BLOG / INTERVIEW

Tripletvinet: scalable, platform-agnostic solution for detecting and mitigating fake videos, from landlocked to land of opportunity: paraguay's path to prosperity, vietnam's economy shows signs of recovery amidst global challenges, water wars and climate change: addressing resource conflicts in the horn of africa, connect us on.

• ADVERTISEMENT
• KNOWLEDGE PARTNERSHIP
• MEDIA PARTNERSHIP
• Agro-Forestry
• Art & Culture
• Economy & Business
• Energy & Extractives
• Law & Governance
• Science & Environment
• Social & Gender
• Urban Development
• East and South East Asia
• Europe and Central Asia
• Central Africa
• East Africa
• Southern Africa
• West Africa
• Middle East and North Africa
• North America
• Latin America and Caribbean

OTHER LINKS

• Write for us
• Submit Press Release
• Opinion / Blog / Analysis
• Business News
• Entertainment News
• Technology News
• Law-order News
• Lifestyle News
• National News
• International News

OTHER PRODUCTS

Email: [email protected] Phone: +91-720-6444012, +91-7027739813, 14, 15

© Copyright 2024

Lewiston Sun Journal

Account Subscription: ACTIVE

Questions about your account? Our customer service team can be reached at [email protected] during business hours at (207) 791-6000 .

• Boston Red Sox

Red Sox shake up roster to add trade additions

Reese McGuire and Chase Anderson are designated for assignment as Boston adds James Paxton and Danny Jansen to the roster.

You are able to gift 5 more articles this month.

Anyone can access the link you share with no account required. Learn more .

With a Lewiston Sun Journal subscription, you can gift 5 articles each month.

It looks like you do not have any active subscriptions. To get one, go to the subscriptions page .

Loading....

The Red Sox designated catcher Reese McGuire for assignment on Sunday, a day after they completed a trade with the Blue Jays for catcher Danny Jansen. Gene J. Puskar/Associated Press

BOSTON — The Red Sox added two trade additions to their active roster Sunday – and cut two veteran players to make room for them.

Backup catcher Reese McGuire and long reliever Chase Anderson were both designated for assignment to make room on the roster for starter James Paxton and catcher Danny Jansen, who are both active Sunday for the Red Sox’s game against the Yankees. Jansen will start against Yankees lefty Carlos Rodón as the designated hitter and hit seventh. Paxton is expected to make his first start since being traded back to the Red Sox against Seattle on Tuesday night.

Boston also claimed right-handed pitcher Yohan Ramirez off waivers from the Dodgers. They have one open spot on the 40-man roster after designating Triple-A reliever Alex Speas for assignment Saturday.

Both McGuire and Anderson have been with the Red Sox since Opening Day. The moves are not a surprise considering the recent performance of both players but are to be considered a small clubhouse shakeup because of their veteran status.

McGuire, who was acquired in a deadline deal with the White Sox almost exactly two years ago, went 8 for 24 with two homers and a 1.010 OPS on Boston’s season-opening, 10-game road trip, but has cooled off significantly in the months since. McGuire, a left-handed hitter, has batted just .172 with three extra-base hits in 31 games since May. It’s clear the Red Sox were looking to upgrade the backup catcher position by acquiring Jansen, adding a right-handed bench option in the process.

Jansen will also mix in at designated hitter to spell Masataka Yoshida against lefties.

In all, McGuire hit .264 with seven homers, 46 RBI and a .686 OPS in 160 games with the Red Sox over the last three years.

Anderson took the loss in Saturday’s extra-innings defeat against the Yankees, allowing three runs (two earned) in the top of the 10th. Originally signed in the final days of spring training after he opted out of a minor league deal with the Pirates, Anderson filled his role as the mop-up man throughout the early part of the season but has struggled as of late. Pitching in mostly low-leverage situations, the 36-year-old has a 4.85 ERA in 52 innings over 27 games. He has a 5.54 ERA since April 25.

Cooper Criswell, who was bumped from the rotation when the Sox acquired James Paxton, will take the long-man role in the bullpen.

Modify your screen name

Join the Conversation

Please sign into your Sun Journal account to participate in conversations below. If you do not have an account, you can register or subscribe . Questions? Please see our FAQs .

Your commenting screen name has been updated.

Send questions/comments to the editors.

« Previous

Red Sox acquire Blue Jays catcher Danny Jansen

Next »

Yankees extend Boston’s slump with 8-2 win

GoFundMe page set up for girls killed in Mechanic Falls

Mother, two young daughters found dead at mechanic falls apartment, ‘devil bird’ from southern states spotted in maine for the first time, locally-owned pet supply store opens in auburn, dixfield man charged with possessing methamphetamine, crack cocaine, member log in.

Please enter your username and password below. Already a subscriber but don't have one? Click here .

Not a subscriber? Click here to see your options