?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
* added compilers lcc and bcc (linux86)
[mascara-docs.git] / compilers / lcc / src / simp.c
blobea26ab69336c23f3d0829f324636b10f8f93b1a0
1 #include "c.h"
2 #include <float.h>
3
4
5 #define foldcnst(TYPE,VAR,OP) \
6 if (l->op == CNST+TYPE && r->op == CNST+TYPE) \
7 return cnsttree(ty, l->u.v.VAR OP r->u.v.VAR)
8 #define commute(L,R) \
9 if (generic(R->op) == CNST && generic(L->op) != CNST) \
10 do { Tree t = L; L = R; R = t; } while(0)
11 #define xfoldcnst(TYPE,VAR,OP,FUNC)\
12 if (l->op == CNST+TYPE && r->op == CNST+TYPE\
13 && FUNC(l->u.v.VAR,r->u.v.VAR,\
14 ty->u.sym->u.limits.min.VAR,\
15 ty->u.sym->u.limits.max.VAR, needconst)) \
16 return cnsttree(ty, l->u.v.VAR OP r->u.v.VAR)
17 #define xcvtcnst(FTYPE,SRC,DST,VAR,EXPR) \
18 if (l->op == CNST+FTYPE) do {\
19 if (!explicitCast\
20 && ((SRC) < DST->u.sym->u.limits.min.VAR || (SRC) > DST->u.sym->u.limits.max.VAR))\
21 warning("overflow in converting constant expression from `%t' to `%t'\n", l->type, DST);\
22 if (needconst\
23 || !((SRC) < DST->u.sym->u.limits.min.VAR || (SRC) > DST->u.sym->u.limits.max.VAR))\
24 return cnsttree(ty, (EXPR)); } while(0)
25 #define identity(X,Y,TYPE,VAR,VAL) \
26 if (X->op == CNST+TYPE && X->u.v.VAR == VAL) return Y
27 #define zerofield(OP,TYPE,VAR) \
28 if (l->op == FIELD \
29 && r->op == CNST+TYPE && r->u.v.VAR == 0)\
30 return eqtree(OP, bittree(BAND, l->kids[0],\
31 cnsttree(unsignedtype, \
32 (unsigned long)fieldmask(l->u.field)<<fieldright(l->u.field))), r)
33 #define cfoldcnst(TYPE,VAR,OP) \
34 if (l->op == CNST+TYPE && r->op == CNST+TYPE) \
35 return cnsttree(inttype, (long)(l->u.v.VAR OP r->u.v.VAR))
36 #define foldaddp(L,R,RTYPE,VAR) \
37 if (L->op == CNST+P && R->op == CNST+RTYPE) { \
38 Tree e = tree(CNST+P, ty, NULL, NULL);\
39 e->u.v.p = (char *)L->u.v.p + R->u.v.VAR;\
40 return e; }
41 #define ufoldcnst(TYPE,EXP) if (l->op == CNST+TYPE) return EXP
42 #define sfoldcnst(OP) \
43 if (l->op == CNST+U && r->op == CNST+I \
44 && r->u.v.i >= 0 && r->u.v.i < 8*l->type->size) \
45 return cnsttree(ty, (unsigned long)(l->u.v.u OP r->u.v.i))
46 #define geu(L,R,V) \
47 if (R->op == CNST+U && R->u.v.u == 0) do { \
48 warning("result of unsigned comparison is constant\n"); \
49 return tree(RIGHT, inttype, root(L), cnsttree(inttype, (long)(V))); } while(0)
50 #define idempotent(OP) if (l->op == OP) return l->kids[0]
51
52 int needconst;
53 int explicitCast;
54 static int addi(long x, long y, long min, long max, int needconst) {
55 int cond = x == 0 || y == 0
56 || (x < 0 && y < 0 && x >= min - y)
57 || (x < 0 && y > 0)
58 || (x > 0 && y < 0)
59 || (x > 0 && y > 0 && x <= max - y);
60 if (!cond && needconst) {
61 warning("overflow in constant expression\n");
62 cond = 1;
63 }
64 return cond;
65
66
67 }
68
69 static int addd(double x, double y, double min, double max, int needconst) {
70 int cond = x == 0 || y == 0
71 || (x < 0 && y < 0 && x >= min - y)
72 || (x < 0 && y > 0)
73 || (x > 0 && y < 0)
74 || (x > 0 && y > 0 && x <= max - y);
75 if (!cond && needconst) {
76 warning("overflow in constant expression\n");
77 cond = 1;
78 }
79 return cond;
80
81
82 }
83
84 static Tree addrtree(Tree e, long n, Type ty) {
85 Symbol p = e->u.sym, q;
86
87 if (p->scope == GLOBAL
88 || p->sclass == STATIC || p->sclass == EXTERN)
89 NEW0(q, PERM);
90 else
91 NEW0(q, FUNC);
92 q->name = stringd(genlabel(1));
93 q->sclass = p->sclass;
94 q->scope = p->scope;
95 assert(isptr(ty) || isarray(ty));
96 q->type = isptr(ty) ? ty->type : ty;
97 q->temporary = p->temporary;
98 q->generated = p->generated;
99 q->addressed = p->addressed;
100 q->computed = 1;
101 q->defined = 1;
102 q->ref = 1;
103 if (p->scope == GLOBAL
104 || p->sclass == STATIC || p->sclass == EXTERN) {
105 if (p->sclass == AUTO)
106 q->sclass = STATIC;
107 (*IR->address)(q, p, n);
108 } else {
109 Code cp;
110 addlocal(p);
111 cp = code(Address);
112 cp->u.addr.sym = q;
113 cp->u.addr.base = p;
114 cp->u.addr.offset = n;
115 }
116 e = tree(e->op, ty, NULL, NULL);
117 e->u.sym = q;
118 return e;
119 }
120
121 /* div[id] - return 1 if min <= x/y <= max, 0 otherwise */
122 static int divi(long x, long y, long min, long max, int needconst) {
123 int cond = y != 0 && !(x == min && y == -1);
124 if (!cond && needconst) {
125 warning("overflow in constant expression\n");
126 cond = 1;
127 }
128 return cond;
129
130
131 }
132
133 static int divd(double x, double y, double min, double max, int needconst) {
134 int cond;
135
136 if (x < 0) x = -x;
137 if (y < 0) y = -y;
138 cond = y != 0 && !(y < 1 && x > max*y);
139 if (!cond && needconst) {
140 warning("overflow in constant expression\n");
141 cond = 1;
142 }
143 return cond;
144
145 }
146
147 /* mul[id] - return 1 if min <= x*y <= max, 0 otherwise */
148 static int muli(long x, long y, long min, long max, int needconst) {
149 int cond = (x > -1 && x <= 1) || (y > -1 && y <= 1)
150 || (x < 0 && y < 0 && -x <= max/-y)
151 || (x < 0 && y > 0 && x >= min/y)
152 || (x > 0 && y < 0 && y >= min/x)
153 || (x > 0 && y > 0 && x <= max/y);
154 if (!cond && needconst) {
155 warning("overflow in constant expression\n");
156 cond = 1;
157 }
158 return cond;
159
160
161 }
162
163 static int muld(double x, double y, double min, double max, int needconst) {
164 int cond = (x >= -1 && x <= 1) || (y >= -1 && y <= 1)
165 || (x < 0 && y < 0 && -x <= max/-y)
166 || (x < 0 && y > 0 && x >= min/y)
167 || (x > 0 && y < 0 && y >= min/x)
168 || (x > 0 && y > 0 && x <= max/y);
169 if (!cond && needconst) {
170 warning("overflow in constant expression\n");
171 cond = 1;
172 }
173 return cond;
174
175
176 }
177 /* sub[id] - return 1 if min <= x-y <= max, 0 otherwise */
178 static int subi(long x, long y, long min, long max, int needconst) {
179 return addi(x, -y, min, max, needconst);
180 }
181
182 static int subd(double x, double y, double min, double max, int needconst) {
183 return addd(x, -y, min, max, needconst);
184 }
185 Tree constexpr(int tok) {
186 Tree p;
187
188 needconst++;
189 p = expr1(tok);
190 needconst--;
191 return p;
192 }
193
194 int intexpr(int tok, int n) {
195 Tree p = constexpr(tok);
196
197 needconst++;
198 if (p->op == CNST+I || p->op == CNST+U)
199 n = cast(p, inttype)->u.v.i;
200 else
201 error("integer expression must be constant\n");
202 needconst--;
203 return n;
204 }
205 Tree simplify(int op, Type ty, Tree l, Tree r) {
206 int n;
207
208 if (optype(op) == 0)
209 op = mkop(op, ty);
210 switch (op) {
211 case ADD+U:
212 foldcnst(U,u,+);
213 commute(r,l);
214 identity(r,l,U,u,0);
215 break;
216 case ADD+I:
217 xfoldcnst(I,i,+,addi);
218 commute(r,l);
219 identity(r,l,I,i,0);
220 break;
221 case CVI+I:
222 xcvtcnst(I,l->u.v.i,ty,i,(long)extend(l->u.v.i,ty));
223 break;
224 case CVU+I:
225 if (l->op == CNST+U) {
226 if (!explicitCast && l->u.v.u > ty->u.sym->u.limits.max.i)
227 warning("overflow in converting constant expression from `%t' to `%t'\n", l->type, ty);
228 if (needconst || !(l->u.v.u > ty->u.sym->u.limits.max.i))
229 return cnsttree(ty, (long)extend(l->u.v.u,ty));
230 }
231 break;
232 case CVP+U:
233 xcvtcnst(P,(unsigned long)l->u.v.p,ty,u,(unsigned long)l->u.v.p);
234 break;
235 case CVU+P:
236 xcvtcnst(U,(void*)l->u.v.u,ty,p,(void*)l->u.v.u);
237 break;
238 case CVP+P:
239 xcvtcnst(P,l->u.v.p,ty,p,l->u.v.p);
240 break;
241 case CVI+U:
242 xcvtcnst(I,l->u.v.i,ty,u,((unsigned long)l->u.v.i)&ones(8*ty->size));
243 break;
244 case CVU+U:
245 xcvtcnst(U,l->u.v.u,ty,u,l->u.v.u&ones(8*ty->size));
246 break;
247
248 case CVI+F:
249 xcvtcnst(I,l->u.v.i,ty,d,(double)l->u.v.i);
250 case CVU+F:
251 xcvtcnst(U,l->u.v.u,ty,d,(double)l->u.v.u);
252 break;
253 case CVF+I:
254 xcvtcnst(F,l->u.v.d,ty,i,(long)l->u.v.d);
255 break;
256 case CVF+F: {
257 float d = 0.0f;
258 if (l->op == CNST+F) {
259 if (l->u.v.d < ty->u.sym->u.limits.min.d)
260 d = ty->u.sym->u.limits.min.d;
261 else if (l->u.v.d > ty->u.sym->u.limits.max.d)
262 d = ty->u.sym->u.limits.max.d;
263 else
264 d = l->u.v.d;
265 }
266 xcvtcnst(F,l->u.v.d,ty,d,(double)d);
267 break;
268 }
269 case BAND+U:
270 foldcnst(U,u,&);
271 commute(r,l);
272 identity(r,l,U,u,ones(8*ty->size));
273 if (r->op == CNST+U && r->u.v.u == 0)
274 return tree(RIGHT, ty, root(l), cnsttree(ty, 0UL));
275 break;
276 case BAND+I:
277 foldcnst(I,i,&);
278 commute(r,l);
279 identity(r,l,I,i,ones(8*ty->size));
280 if (r->op == CNST+I && r->u.v.u == 0)
281 return tree(RIGHT, ty, root(l), cnsttree(ty, 0L));
282 break;
283
284 case MUL+U:
285 commute(l,r);
286 if (l->op == CNST+U && (n = ispow2(l->u.v.u)) != 0)
287 return simplify(LSH, ty, r, cnsttree(inttype, (long)n));
288 foldcnst(U,u,*);
289 identity(r,l,U,u,1);
290 break;
291 case NE+I:
292 cfoldcnst(I,i,!=);
293 commute(r,l);
294 zerofield(NE,I,i);
295 break;
296
297 case EQ+I:
298 cfoldcnst(I,i,==);
299 commute(r,l);
300 zerofield(EQ,I,i);
301 break;
302 case ADD+P:
303 foldaddp(l,r,I,i);
304 foldaddp(l,r,U,u);
305 foldaddp(r,l,I,i);
306 foldaddp(r,l,U,u);
307 commute(r,l);
308 identity(r,retype(l,ty),I,i,0);
309 identity(r,retype(l,ty),U,u,0);
310 if (isaddrop(l->op)
311 && ((r->op == CNST+I && r->u.v.i <= longtype->u.sym->u.limits.max.i
312 && r->u.v.i >= longtype->u.sym->u.limits.min.i)
313 || (r->op == CNST+U && r->u.v.u <= longtype->u.sym->u.limits.max.i)))
314 return addrtree(l, cast(r, longtype)->u.v.i, ty);
315 if (l->op == ADD+P && isaddrop(l->kids[1]->op)
316 && ((r->op == CNST+I && r->u.v.i <= longtype->u.sym->u.limits.max.i
317 && r->u.v.i >= longtype->u.sym->u.limits.min.i)
318 || (r->op == CNST+U && r->u.v.u <= longtype->u.sym->u.limits.max.i)))
319 return simplify(ADD+P, ty, l->kids[0],
320 addrtree(l->kids[1], cast(r, longtype)->u.v.i, ty));
321 if ((l->op == ADD+I || l->op == SUB+I)
322 && l->kids[1]->op == CNST+I && isaddrop(r->op))
323 return simplify(ADD+P, ty, l->kids[0],
324 simplify(generic(l->op)+P, ty, r, l->kids[1]));
325 if (l->op == ADD+P && generic(l->kids[1]->op) == CNST
326 && generic(r->op) == CNST)
327 return simplify(ADD+P, ty, l->kids[0],
328 simplify(ADD, l->kids[1]->type, l->kids[1], r));
329 if (l->op == ADD+I && generic(l->kids[1]->op) == CNST
330 && r->op == ADD+P && generic(r->kids[1]->op) == CNST)
331 return simplify(ADD+P, ty, l->kids[0],
332 simplify(ADD+P, ty, r->kids[0],
333 simplify(ADD, r->kids[1]->type, l->kids[1], r->kids[1])));
334 if (l->op == RIGHT && l->kids[1])
335 return tree(RIGHT, ty, l->kids[0],
336 simplify(ADD+P, ty, l->kids[1], r));
337 else if (l->op == RIGHT && l->kids[0])
338 return tree(RIGHT, ty,
339 simplify(ADD+P, ty, l->kids[0], r), NULL);
340 break;
341
342 case ADD+F:
343 xfoldcnst(F,d,+,addd);
344 commute(r,l);
345 break;
346 case AND+I:
347 op = AND;
348 ufoldcnst(I,l->u.v.i ? cond(r) : l); /* 0&&r => 0, 1&&r => r */
349 break;
350 case OR+I:
351 op = OR;
352 /* 0||r => r, 1||r => 1 */
353 ufoldcnst(I,l->u.v.i ? cnsttree(ty, 1L) : cond(r));
354 break;
355 case BCOM+I:
356 ufoldcnst(I,cnsttree(ty, (long)extend((~l->u.v.i)&ones(8*ty->size), ty)));
357 idempotent(BCOM+U);
358 break;
359 case BCOM+U:
360 ufoldcnst(U,cnsttree(ty, (unsigned long)((~l->u.v.u)&ones(8*ty->size))));
361 idempotent(BCOM+U);
362 break;
363 case BOR+U:
364 foldcnst(U,u,|);
365 commute(r,l);
366 identity(r,l,U,u,0);
367 break;
368 case BOR+I:
369 foldcnst(I,i,|);
370 commute(r,l);
371 identity(r,l,I,i,0);
372 break;
373 case BXOR+U:
374 foldcnst(U,u,^);
375 commute(r,l);
376 identity(r,l,U,u,0);
377 break;
378 case BXOR+I:
379 foldcnst(I,i,^);
380 commute(r,l);
381 identity(r,l,I,i,0);
382 break;
383 case DIV+F:
384 xfoldcnst(F,d,/,divd);
385 break;
386 case DIV+I:
387 identity(r,l,I,i,1);
388 if ((r->op == CNST+I && r->u.v.i == 0)
389 || (l->op == CNST+I && l->u.v.i == ty->u.sym->u.limits.min.i
390 && r->op == CNST+I && r->u.v.i == -1))
391 break;
392 xfoldcnst(I,i,/,divi);
393 break;
394 case DIV+U:
395 identity(r,l,U,u,1);
396 if (r->op == CNST+U && r->u.v.u == 0)
397 break;
398 if (r->op == CNST+U && (n = ispow2(r->u.v.u)) != 0)
399 return simplify(RSH, ty, l, cnsttree(inttype, (long)n));
400 foldcnst(U,u,/);
401 break;
402 case EQ+F:
403 cfoldcnst(F,d,==);
404 commute(r,l);
405 break;
406 case EQ+U:
407 cfoldcnst(U,u,==);
408 commute(r,l);
409 zerofield(EQ,U,u);
410 break;
411 case GE+F: cfoldcnst(F,d,>=); break;
412 case GE+I: cfoldcnst(I,i,>=); break;
413 case GE+U:
414 geu(l,r,1); /* l >= 0 => (l,1) */
415 cfoldcnst(U,u,>=);
416 if (l->op == CNST+U && l->u.v.u == 0) /* 0 >= r => r == 0 */
417 return eqtree(EQ, r, l);
418 break;
419 case GT+F: cfoldcnst(F,d, >); break;
420 case GT+I: cfoldcnst(I,i, >); break;
421 case GT+U:
422 geu(r,l,0); /* 0 > r => (r,0) */
423 cfoldcnst(U,u, >);
424 if (r->op == CNST+U && r->u.v.u == 0) /* l > 0 => l != 0 */
425 return eqtree(NE, l, r);
426 break;
427 case LE+F: cfoldcnst(F,d,<=); break;
428 case LE+I: cfoldcnst(I,i,<=); break;
429 case LE+U:
430 geu(r,l,1); /* 0 <= r => (r,1) */
431 cfoldcnst(U,u,<=);
432 if (r->op == CNST+U && r->u.v.u == 0) /* l <= 0 => l == 0 */
433 return eqtree(EQ, l, r);
434 break;
435 case LSH+I:
436 identity(r,l,I,i,0);
437 if (l->op == CNST+I && r->op == CNST+I
438 && r->u.v.i >= 0 && r->u.v.i < 8*l->type->size
439 && muli(l->u.v.i, 1<<r->u.v.i, ty->u.sym->u.limits.min.i, ty->u.sym->u.limits.max.i, needconst))
440 return cnsttree(ty, (long)(l->u.v.i<<r->u.v.i));
441 if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) {
442 warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i);
443 break;
444 }
445
446 break;
447 case LSH+U:
448 identity(r,l,I,i,0);
449 sfoldcnst(<<);
450 if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) {
451 warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i);
452 break;
453 }
454
455 break;
456
457 case LT+F: cfoldcnst(F,d, <); break;
458 case LT+I: cfoldcnst(I,i, <); break;
459 case LT+U:
460 geu(l,r,0); /* l < 0 => (l,0) */
461 cfoldcnst(U,u, <);
462 if (l->op == CNST+U && l->u.v.u == 0) /* 0 < r => r != 0 */
463 return eqtree(NE, r, l);
464 break;
465 case MOD+I:
466 if (r->op == CNST+I && r->u.v.i == 1) /* l%1 => (l,0) */
467 return tree(RIGHT, ty, root(l), cnsttree(ty, 0L));
468 if ((r->op == CNST+I && r->u.v.i == 0)
469 || (l->op == CNST+I && l->u.v.i == ty->u.sym->u.limits.min.i
470 && r->op == CNST+I && r->u.v.i == -1))
471 break;
472 xfoldcnst(I,i,%,divi);
473 break;
474 case MOD+U:
475 if (r->op == CNST+U && ispow2(r->u.v.u)) /* l%2^n => l&(2^n-1) */
476 return bittree(BAND, l, cnsttree(ty, r->u.v.u - 1));
477 if (r->op == CNST+U && r->u.v.u == 0)
478 break;
479 foldcnst(U,u,%);
480 break;
481 case MUL+F:
482 xfoldcnst(F,d,*,muld);
483 commute(l,r);
484 break;
485 case MUL+I:
486 commute(l,r);
487 xfoldcnst(I,i,*,muli);
488 if (l->op == CNST+I && r->op == ADD+I && r->kids[1]->op == CNST+I)
489 /* c1*(x + c2) => c1*x + c1*c2 */
490 return simplify(ADD, ty, simplify(MUL, ty, l, r->kids[0]),
491 simplify(MUL, ty, l, r->kids[1]));
492 if (l->op == CNST+I && r->op == SUB+I && r->kids[1]->op == CNST+I)
493 /* c1*(x - c2) => c1*x - c1*c2 */
494 return simplify(SUB, ty, simplify(MUL, ty, l, r->kids[0]),
495 simplify(MUL, ty, l, r->kids[1]));
496 if (l->op == CNST+I && l->u.v.i > 0 && (n = ispow2(l->u.v.i)) != 0)
497 /* 2^n * r => r<<n */
498 return simplify(LSH, ty, r, cnsttree(inttype, (long)n));
499 identity(r,l,I,i,1);
500 break;
501 case NE+F:
502 cfoldcnst(F,d,!=);
503 commute(r,l);
504 break;
505 case NE+U:
506 cfoldcnst(U,u,!=);
507 commute(r,l);
508 zerofield(NE,U,u);
509 break;
510 case NEG+F:
511 ufoldcnst(F,cnsttree(ty, -l->u.v.d));
512 idempotent(NEG+F);
513 break;
514 case NEG+I:
515 if (l->op == CNST+I) {
516 if (needconst && l->u.v.i == ty->u.sym->u.limits.min.i)
517 warning("overflow in constant expression\n");
518 if (needconst || l->u.v.i != ty->u.sym->u.limits.min.i)
519 return cnsttree(ty, -l->u.v.i);
520 }
521 idempotent(NEG+I);
522 break;
523 case NOT+I:
524 op = NOT;
525 ufoldcnst(I,cnsttree(ty, !l->u.v.i));
526 break;
527 case RSH+I:
528 identity(r,l,I,i,0);
529 if (l->op == CNST+I && r->op == CNST+I
530 && r->u.v.i >= 0 && r->u.v.i < 8*l->type->size) {
531 long n = l->u.v.i>>r->u.v.i;
532 if (l->u.v.i < 0)
533 n |= ~0UL<<(8*l->type->size - r->u.v.i);
534 return cnsttree(ty, n);
535 }
536 if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) {
537 warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i);
538 break;
539 }
540
541 break;
542 case RSH+U:
543 identity(r,l,I,i,0);
544 sfoldcnst(>>);
545 if (r->op == CNST+I && (r->u.v.i >= 8*ty->size || r->u.v.i < 0)) {
546 warning("shifting an `%t' by %d bits is undefined\n", ty, r->u.v.i);
547 break;
548 }
549
550 break;
551 case SUB+F:
552 xfoldcnst(F,d,-,subd);
553 break;
554 case SUB+I:
555 xfoldcnst(I,i,-,subi);
556 identity(r,l,I,i,0);
557 break;
558 case SUB+U:
559 foldcnst(U,u,-);
560 identity(r,l,U,u,0);
561 break;
562 case SUB+P:
563 if (l->op == CNST+P && r->op == CNST+P)
564 return cnsttree(ty, (long)((char *)l->u.v.p - (char *)r->u.v.p));
565 if (r->op == CNST+I || r->op == CNST+U)
566 return simplify(ADD, ty, l,
567 cnsttree(inttype, r->op == CNST+I ? -r->u.v.i : -(long)r->u.v.u));
568 if (isaddrop(l->op) && r->op == ADD+I && r->kids[1]->op == CNST+I)
569 /* l - (x + c) => l-c - x */
570 return simplify(SUB, ty,
571 simplify(SUB, ty, l, r->kids[1]), r->kids[0]);
572 break;
573 default:assert(0);
574 }
575 return tree(op, ty, l, r);
576 }
577 /* ispow2 - if u > 1 && u == 2^n, return n, otherwise return 0 */
578 int ispow2(unsigned long u) {
579 int n;
580
581 if (u > 1 && (u&(u-1)) == 0)
582 for (n = 0; u; u >>= 1, n++)
583 if (u&1)
584 return n;
585 return 0;
586 }
587