Context Sensitive Analysis

A method for handling methods

Christian Gram Kalhauge

Table of Contents

  1. Why Method Calls are complicated.
  2. Context Sensitive Analysis

Questions

  1. Why are method calls complicated?

  2. Why would you use context sensitive analysis?

  3. What is the drawback of a context sensitive analysis?

Why Method Calls are complicated. (§1)

int id(int i) { 
  return i; // Where to return to?
} 

int main() { 
  int x = id(1);
  int y = id(0);
  return x + y;
}

The Trivial Solution: In-lining (§1.1)

int id(int i) { 
  return i; // Where to return to?
} 

int main() { 
  int x = id(1);
  int y = id(0);
  return x + y;
}
int main() { 
  return 1 + 0;
}

Abstract Call Plumbing (§1.2)

Parameters for caller Locals of caller Return Address Parameters for callee Locals of callee Return Address Enter your text here Frame Pointer Stack Pointer top of stack Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here Enter your text here

The call stack. Notice how the return address is stored secretly among the local variables. By R. S. Shaw (modified) - Own work, Public Domain link

ι↦2ι×𝐒𝐭𝐚𝐭𝐞‾

Abstract Call Plumbing

int id(int i) { 
  // { main:1} x {+}
  return i;       
  // updates the results of main:1 with {+}
} 

int main() { 
  int x = id(1); // result {+} 
  int y = id(0); // yet not computed
  return x + y;  // yet not computed
}
int id(int i) { 
  // { main:1, main:2} x {0, +}
  return i;       
  // updates the results of main:1 and main:2 with {0, +}
} 

int main() { 
  int x = id(1); // result {0, +} 
  int y = id(0); // result {0, +} 
  return x + y;  // result {+}
}

Nigthmare!

int id(int i) { 
  // { main:1, main:2} x {0, +}
  return i;       
  // updates the results of main:1 and main:2 with {0, +}
} 

int main() { 
  int x = id(1); // result {0, +} 
  int y = id(0); // result {0, +} 
  return x / y;  // result BUG!
}

Context Sensitive Analysis (§2)

Full Call Stack Context (§2.1)

ι+↦2ι*×𝐒𝐭𝐚𝐭𝐞‾
int main() {
  int x = id(0); // main:1 -> {} x {0}
  int y = id(1); // not yet computed
  return x / y;  // not yet computed
}

int id(int x) {
  // main:1,id:1 -> {main:1} x { 0 }
  return x  
}
int main() {
  int x = id(0); // main:1 -> {} x {0}
  int y = id(1); // main:1 -> {} x {+}
  return x / y;  // main:1 -> {} x {0}
}

int id(int x) {
  // Now we keep two state:
  // main:1,id:1 -> {main:1} x { 0 }
  // main:2,id:1 -> {main:2} x { + }
  return x  
}

Be aware!

  • Exponential Blow-out!

  • Recursive Functions!

(k-CFA) Limited Context Sensitivity (§2.2)

  • Only keep the last k call-sites

  • k=1 is often enough.

Questions

  1. Why are method calls complicated?

  2. Why would you use context sensitive analysis?

  3. What is the drawback of a context sensitive analysis?